Index: src/AST/TypeEnvironment.cpp
===================================================================
--- src/AST/TypeEnvironment.cpp	(revision 361bf012e550db91b38f772bfbc7cb7ed2e49033)
+++ src/AST/TypeEnvironment.cpp	(revision 53449a48dee3324f96932ed8c4befe2756837314)
@@ -52,5 +52,5 @@
 	for ( const auto & i : open ) {
 		if ( first ) { first = false; } else { out << ' '; }
-		out << i.first << "(" << i.second << ")";
+		out << i.first.typeString() << "(" << i.second << ")";
 	}
 }
@@ -62,6 +62,9 @@
 		if(first) first = false;
 		else out << " ";
-		if( deterministic_output && isUnboundType(var) ) out << "[unbound]";
-		else out << var;
+
+		if( deterministic_output ) out << "[unbound]";
+		else out << "_" << var.formal_usage << "_" << var.expr_id << "_";
+
+		out << var.base->name;
 	}
 	out << ")";
@@ -79,5 +82,5 @@
 }
 
-const EqvClass * TypeEnvironment::lookup( const std::string & var ) const {
+const EqvClass * TypeEnvironment::lookup( const TypeInstType::TypeEnvKey & var ) const {
 	for ( ClassList::const_iterator i = env.begin(); i != env.end(); ++i ) {
 		if ( i->vars.find( var ) != i->vars.end() ) return &*i;
@@ -106,5 +109,5 @@
 
 void TypeEnvironment::add( const FunctionType::ForallList & tyDecls ) {
-	for ( const TypeDecl * tyDecl : tyDecls ) {
+	for ( auto & tyDecl : tyDecls ) {
 		env.emplace_back( tyDecl );
 	}
@@ -119,12 +122,14 @@
 void TypeEnvironment::writeToSubstitution( TypeSubstitution & sub ) const {
 	for ( const auto & clz : env ) {
-		std::string clzRep;
+		TypeInstType::TypeEnvKey clzRep;
+		bool first = true;
 		for ( const auto & var : clz.vars ) {
 			if ( clz.bound ) {
 				sub.add( var, clz.bound );
-			} else if ( clzRep.empty() ) {
+			} else if ( first ) {
 				clzRep = var;
+				first = false;
 			} else {
-				sub.add( var, new TypeInstType{ clzRep, clz.data.kind } );
+				sub.add( var, new TypeInstType{ clzRep } );
 			}
 		}
@@ -141,8 +146,8 @@
 	struct Occurs : public ast::WithVisitorRef<Occurs> {
 		bool result;
-		std::set< std::string > vars;
+		std::unordered_set< TypeInstType::TypeEnvKey > vars;
 		const TypeEnvironment & tenv;
 
-		Occurs( const std::string & var, const TypeEnvironment & env )
+		Occurs( const TypeInstType::TypeEnvKey & var, const TypeEnvironment & env )
 		: result( false ), vars(), tenv( env ) {
 			if ( const EqvClass * clz = tenv.lookup( var ) ) {
@@ -154,7 +159,7 @@
 
 		void previsit( const TypeInstType * typeInst ) {
-			if ( vars.count( typeInst->name ) ) {
+			if ( vars.count( *typeInst ) ) {
 				result = true;
-			} else if ( const EqvClass * clz = tenv.lookup( typeInst->name ) ) {
+			} else if ( const EqvClass * clz = tenv.lookup( *typeInst ) ) {
 				if ( clz->bound ) {
 					clz->bound->accept( *visitor );
@@ -165,5 +170,5 @@
 
 	/// true if `var` occurs in `ty` under `env`
-	bool occurs( const Type * ty, const std::string & var, const TypeEnvironment & env ) {
+	bool occurs( const Type * ty, const TypeInstType::TypeEnvKey & var, const TypeEnvironment & env ) {
 		Pass<Occurs> occur{ var, env };
 		maybe_accept( ty, occur );
@@ -280,10 +285,10 @@
 	// remove references from bound type, so that type variables can only bind to value types
 	ptr<Type> target = bindTo->stripReferences();
-	auto tyvar = open.find( typeInst->name );
+	auto tyvar = open.find( *typeInst );
 	assert( tyvar != open.end() );
 	if ( ! tyVarCompatible( tyvar->second, target ) ) return false;
-	if ( occurs( target, typeInst->name, *this ) ) return false;
-
-	auto it = internal_lookup( typeInst->name );
+	if ( occurs( target, *typeInst, *this ) ) return false;
+
+	auto it = internal_lookup( *typeInst );
 	if ( it != env.end() ) {
 		if ( it->bound ) {
@@ -308,5 +313,5 @@
 	} else {
 		env.emplace_back(
-			typeInst->name, target, widen.first && widen.second, data );
+			*typeInst, target, widen.first && widen.second, data );
 	}
 	return true;
@@ -318,6 +323,6 @@
 		WidenMode widen, const SymbolTable & symtab
 ) {
-	auto c1 = internal_lookup( var1->name );
-	auto c2 = internal_lookup( var2->name );
+	auto c1 = internal_lookup( *var1 );
+	auto c2 = internal_lookup( *var2 );
 
 	// exit early if variables already bound together
@@ -333,5 +338,5 @@
 	if ( c1 != env.end() ) {
 		if ( c1->bound ) {
-			if ( occurs( c1->bound, var2->name, *this ) ) return false;
+			if ( occurs( c1->bound, *var2, *this ) ) return false;
 			type1 = c1->bound;
 		}
@@ -340,5 +345,5 @@
 	if ( c2 != env.end() ) {
 		if ( c2->bound ) {
-			if ( occurs( c2->bound, var1->name, *this ) ) return false;
+			if ( occurs( c2->bound, *var1, *this ) ) return false;
 			type2 = c2->bound;
 		}
@@ -378,15 +383,15 @@
 	} else if ( c1 != env.end() ) {
 		// var2 unbound, add to env[c1]
-		c1->vars.emplace( var2->name );
+		c1->vars.emplace( *var2 );
 		c1->allowWidening = widen1;
 		c1->data.isComplete |= data.isComplete;
 	} else if ( c2 != env.end() ) {
 		// var1 unbound, add to env[c2]
-		c2->vars.emplace( var1->name );
+		c2->vars.emplace( *var1 );
 		c2->allowWidening = widen2;
 		c2->data.isComplete |= data.isComplete;
 	} else {
 		// neither var bound, create new class
-		env.emplace_back( var1->name, var2->name, widen1 && widen2, data );
+		env.emplace_back( *var1, *var2, widen1 && widen2, data );
 	}
 
@@ -452,5 +457,5 @@
 }
 
-TypeEnvironment::ClassList::iterator TypeEnvironment::internal_lookup( const std::string & var ) {
+TypeEnvironment::ClassList::iterator TypeEnvironment::internal_lookup( const TypeInstType::TypeEnvKey & var ) {
 	for ( ClassList::iterator i = env.begin(); i != env.end(); ++i ) {
 		if ( i->vars.count( var ) ) return i;
