Merge lp:~mgiuca/mars/atom into lp:mars

[Matt Giuca]

Added 'atoms' to instruction set, removed ld_intlit and ld_ctorsym, and changed code generator to generate atoms rather than instructions where possible.

Note that there may be a bug in typedict. See atom_type (it has an XXX). Whereas before, we would have loaded the ctorsym into a variable (which would have been given the correct local type), we are now pulling the type directly out of the global typedef, and ignoring its varset. Therefore, the varset of ctorsyms may be in the wrong namespace for local variables. Check this before merging.

[lp:~mgiuca/mars/atom]

1266. By Matt Giuca on 2011-10-18

Added test case ctorsym-unify for LP: #877111.

1267. By Matt Giuca on 2011-10-18

Test case ctorsym-unify: Added description, and a new test function that passes Nil as the only argument to a function.

1268. By Matt Giuca on 2011-10-20

typedict: XXX comment refers to bug LP: #877111.

1269. By Matt Giuca on 2011-10-20

typedict: Changed atom_type to thread a varset, so that it can augment the varset with ctorsym type variables.
Update code that uses it -- calls augment_globalref with the augmented varset.
Note: Currently atom_type doesn't actually update the varset.

1270. By Matt Giuca on 2011-10-20

test case ctorsym-unify: cons now calls show on the two arguments, so that it requires the 'a' type dict.
This doesn't really change the test case, but it makes the output more clearly correct (since foo will pass the correct type dictionary).

1271. By Matt Giuca on 2011-10-20

test case ctorsym: Added a new case, nil_id.
It currently passes, but when I tried to fix LP: #877111 it broke, so best to have it in here.
(reverse in the prelude broke; this is a simplified version of the same problem).

1272. By Matt Giuca on 2011-10-20

typedict: augment_instr_globalrefs now uses the augmented varset from calling atom_type on a new_closure instruction (previously only did it for a call_global).
This doesn't have any effect now, but fixing atom_type to augment the varset properly would break on new_closure (see the nil_id case in the test file ctorsym-unify).

1273. By Matt Giuca on 2011-10-20

typedict: atom_type now merges the ctorsym's varset into the local one and updates the type.
Now it performs type unification on a consistent namespace.
Fixes LP: #877111.

1274. By Matt Giuca on 2011-10-21

interpret: Fix long lines.

[Matt Giuca (mgiuca)]

Approved.

review: Approve

=== modified file 'doc/dev/isa.rst'
--- doc/dev/isa.rst	2011-05-11 08:14:46 +0000
+++ doc/dev/isa.rst	2011-10-21 03:33:25 +0000
@@ -111,25 +111,22 @@
 The basic instructions form the body of a basic block. Each block may have
 zero or more basic instructions.
 
+Many instructions accept an *atom*, which refers to one of the following:
+
+* A variable name,
+* An arbitrary-precision integer, or
+* A constant symbol (parameterless constructor). This MUST be the name of a
+  constant symbol, not a constructor function.
+
 :samp:`nop`
     Does nothing.
 
 :samp:`mov {dest} {source}`
-    Copies the value of variable `source` to `dest`.
-
-:samp:`ld_intlit {dest} {value}`
-    Assigns the integer `value` to `dest`. `value` is an arbitrary-precision
-    integer.
+    Copies the value of atom `source` to variable `dest`.
 
 :samp:`ld_arraylit {dest} {sources}`
     Creates a new array, with the values of the variables listed in `sources`
-    as its elements, and assigns it to `dest`. `sources` is a list of
-    variable names.
-
-:samp:`ld_ctorsym {dest} {ctor}`
-    Loads the constant symbol constructor `ctor` to `dest`. This sets the
-    variable to that constant value. `ctor` MUST be the name of a constant
-    symbol, not a constructor function.
+    as its elements, and assigns it to `dest`. `sources` is a list of atoms.
 
 :samp:`ld_cgc {dest} {cgc}`
     Loads the value of a computable global constant `cgc` to `dest`. This may
@@ -160,7 +157,7 @@
     Destructively modifies a field of an object, by index of a given
     constructor. Fields are indexed by parameters of the constructor used to
     create the object (0 is the first parameter, etc).
-    Copies the value of variable `value` to field number `index` of variable
+    Copies the value of atom `value` to field number `index` of variable
     `source`, mutating the object referenced by `source`.
     `source` MUST be a variable of an algebraic data type. It MUST be
     statically known to have been constructed with constructor `ctor`. This
@@ -175,7 +172,7 @@
     object (0 is the first parameter, etc).
     Creates a new object with constructor `ctor`. Initialises all fields of
     the new object with the values of the fields in `source`, except for field
-    number `index`, which is initialised to the value of variable `value`.
+    number `index`, which is initialised to the value of atom `value`.
     Assigns the new object to `dest`.
     `source` MUST be a variable of an algebraic data type. It MUST be
     statically known to have been constructed with constructor `ctor`. This
@@ -189,7 +186,7 @@
     result to `dest`. Constructs a new function object with the parameters and
     result of the closure template.
     `func` MUST be the name of a closure template.
-    `args` is a list of variables containing the arguments. It MUST contain
+    `args` is a list of atoms containing the arguments. It MUST contain
     the exact number of closure variables expected by `func`, and any
     supplied arguments must be of correct types.
 
@@ -203,7 +200,7 @@
     Calls a function from local variable `func`, supplying arguments `args`
     and assigning the result to `dest`.
     `func` MUST be a variable containing a function value. `args` is a list of
-    variables containing the arguments. It MUST contain the exact number of
+    atoms containing the arguments. It MUST contain the exact number of
     arguments expected by `func`, of correct types.
     The execution may cause side-effects or fail to return.
 
@@ -211,7 +208,7 @@
     Calls constructor function `ctor`, supplying arguments `args` and
     assigning the result to `dest`.
     `ctor` MUST not be the name of a constant symbol.
-    `args` is a list of variables containing the arguments. It MUST contain
+    `args` is a list of atoms containing the arguments. It MUST contain
     the exact number of arguments expected by `ctor`, of correct types.
 
 :samp:`call_global {dest} {func} {args}`
@@ -219,7 +216,7 @@
     result to `dest`.
     `func` MUST not be the name of a computable global constant or
     constructor.
-    `args` is a list of variables containing the arguments. It MUST contain
+    `args` is a list of atoms containing the arguments. It MUST contain
     the exact number of arguments expected by `func`, of correct types.
     The execution may cause side-effects or fail to return.
 
@@ -252,7 +249,7 @@
     for the rather complicated algorithm that performs this translation.
 
 :samp:`cond_branch {if} {then} {else}`
-    Conditional branch based on the value of the `if` variable, which MUST be
+    Conditional branch based on the value of the `if` atom, which MUST be
     an :type:`Int`. If `if` is not equal to 0, branches to the `then` block.
     Otherwise, branches to the `else` block.
 
 
=== modified file 'src/ast_cfg.m'
--- src/ast_cfg.m	2011-10-10 12:38:16 +0000
+++ src/ast_cfg.m	2011-10-21 03:33:25 +0000
@@ -51,19 +51,21 @@
 :- pred func_to_cfg(progtable::in, function::in, function::out,
     list(function)::out) is det.
 
-% expr_to_instrs(+PT, +Expr, -VarName, -Instrs, -Types, -SynthFuncs,
+% expr_to_instrs(+PT, +Expr, -Atom, -Instrs, -Types, -SynthFuncs,
 %   !ASTState).
-% Converts a single expression into a sequence of low-level instructions
-% which compute the expression and assign it to a variable (possibly a
-% new temporary variable name). Returns the assigned variable name in VarName.
+% Takes a single expression. If it is atomic (a variable name, int literal or
+% constructor symbol), returns it as an Atom. Otherwise, compiles the
+% expression into a sequence of low-level instructions which compute the
+% expression and assign it to a new temporary variable name). Returns the
+% assigned variable name in Atom.
 % (May clobber the temporary variable namespace, as there is no block or
 % subscript information given). Useful for stand-alone statements.
 % Also produces map of types of all variables bound by the instructions.
-:- pred expr_to_instrs(progtable::in, varset::in, expr::in, varname::out,
+:- pred expr_to_instrs(progtable::in, varset::in, expr::in, atom::out,
     list(instr)::out, map(varname, typeval)::out, list(function)::out,
     ast_state::in, ast_state::out) is det.
 
-% expr_to_instrs_post_ssa(+PT, +Varset, +BlockID, +Expr, -VarName, -Instrs,
+% expr_to_instrs_post_ssa(+PT, +Varset, +BlockID, +Expr, -Atom, -Instrs,
 % -Types, -SynthFuncs, !BlockTempCount).
 % Special version of expr_to_instrs, with some important restrictions:
 % - Variables in the expr must already be in SSA form, will not be converted.
@@ -71,7 +73,7 @@
 % subscripts on the temporaries. BlockTempCount is the ID of the next
 % available temporary in this block; it will be updated.
 :- pred expr_to_instrs_post_ssa(progtable::in, varset::in, int::in, expr::in,
-    varname::out, list(instr)::out, map(varname, typeval)::out,
+    atom::out, list(instr)::out, map(varname, typeval)::out,
     list(function)::out, int::in, int::out) is det.
 
 % basic_stmt_to_instrs(+PT, +BasicStmt, -Instrs, -Types, -SynthFuncs,
@@ -831,17 +833,17 @@
               pretty.string_pattern(P)).
 pattern_type(pattern(_, yes(T))) = T.
 
-% exprs_to_instrs(+PT, +BlockID, +Ctx, +Exprs, -VarNames, -Instrs, -Types,
+% exprs_to_instrs(+PT, +BlockID, +Ctx, +Exprs, -Atoms, -Instrs, -Types,
 %   !SubscriptMap).
 :- pred exprs_to_instrs(progtable::in, varset::in, int::in, context::in,
-    list(expr)::in, list(varname)::out, list(instr)::out, type_map::out,
+    list(expr)::in, list(atom)::out, list(instr)::out, type_map::out,
     subscript_map::in, subscript_map::out,
     list(function)::in, list(function)::out) is det.
-exprs_to_instrs(PT, Varset, BlockID, Ctx, Es, VarNames, Instrs, Types,
+exprs_to_instrs(PT, Varset, BlockID, Ctx, Es, Atoms, Instrs, Types,
     !SubscriptMap, !SynthFuncs) :-
-    exprs_to_instrs_(PT, Varset, BlockID, Ctx, Es, Types, [], VarNamesRev, [],
+    exprs_to_instrs_(PT, Varset, BlockID, Ctx, Es, Types, [], AtomsRev, [],
         LLInstrsRev, !SubscriptMap, !SynthFuncs),
-    list.reverse(VarNamesRev, VarNames),
+    list.reverse(AtomsRev, Atoms),
     list.reverse(LLInstrsRev, LLInstrs),
     % "Condense" the list-of-lists into a flat list of instructions
     list.condense(LLInstrs, Instrs).
@@ -851,37 +853,37 @@
 % Instrs is a list of lists (to be flattened). The outer list is reversed, the
 % inner list is not -- this is to allow prepending.
 :- pred exprs_to_instrs_(progtable::in, varset::in, int::in, context::in,
-    list(expr)::in, type_map::out, list(varname)::in, list(varname)::out,
+    list(expr)::in, type_map::out, list(atom)::in, list(atom)::out,
     list(list(instr))::in, list(list(instr))::out,
     subscript_map::in, subscript_map::out,
     list(function)::in, list(function)::out) is det.
-exprs_to_instrs_(_PT, _Varset, _BlockID, _Ctx, [], map.init, !VarNames,
+exprs_to_instrs_(_PT, _Varset, _BlockID, _Ctx, [], map.init, !Atoms,
                  !Instrs, !SubscriptMap, !SynthFuncs).
-exprs_to_instrs_(PT, Varset, BlockID,Ctx,[E|Es],Types,!VarNames, !Instrs,
+exprs_to_instrs_(PT, Varset, BlockID,Ctx,[E|Es],Types,!Atoms, !Instrs,
     !SubscriptMap, !SynthFuncs) :-
     % Create a new variable name and generate instructions for each expr
-    expr_to_instrs(PT, Varset, BlockID, Ctx, E, V, Is, Types0, !SubscriptMap,
+    expr_to_instrs(PT, Varset, BlockID, Ctx, E, A, Is, Types0, !SubscriptMap,
                    !SynthFuncs),
-    !:VarNames = [V | !.VarNames],
+    !:Atoms = [A | !.Atoms],
     !:Instrs = [Is | !.Instrs],     % Do not flatten Is; keep as list of lists
-    exprs_to_instrs_(PT, Varset, BlockID, Ctx, Es, Types1, !VarNames, !Instrs,
+    exprs_to_instrs_(PT, Varset, BlockID, Ctx, Es, Types1, !Atoms, !Instrs,
                      !SubscriptMap, !SynthFuncs),
     Types = type_map_union(Types0, Types1).
 
-% expr_to_instrs(+BlockID, +Ctx, +Expr, -VarName, -Instrs, !SubscriptMap).
-% Converts a single expression into a sequence of low-level instructions
-% which compute the expression and assign it to a variable (possibly a
-% new temporary variable name). Returns the assigned variable name in VarName.
-:- pred expr_to_instrs(progtable::in, varset::in, int::in, context::in,
+% expr_to_instrs_var(+BlockID, +Ctx, +Expr, -VarName, -Instrs, !SubscriptMap).
+% Same as expr_to_instrs, but always produces a variable. (Atomic non-variable
+% expressions such as integer literals are converted into separate
+% instructions.)
+:- pred expr_to_instrs_var(progtable::in, varset::in, int::in, context::in,
     expr::in, varname::out, list(instr)::out, type_map::out,
     subscript_map::in, subscript_map::out,
     list(function)::in, list(function)::out) is det.
-expr_to_instrs(PT, Varset, BlockID, Ctx, E, V, Is, Types, !SubscriptMap,
+expr_to_instrs_var(PT, Varset, BlockID, Ctx, E, V, Is, Types, !SubscriptMap,
     !SynthFuncs) :-
     ( E = expr(varref(Var), _) ->
         % Special case -- expr_to_instrs_as will generate a mov.
         % We can avoid this by not generating a temp var, and just returning
-        % the variable name (with no instructions at all).
+        % the variable name as an atom (with no instructions at all).
         V = Var,
         Is = [],
         Types = map.init
@@ -891,6 +893,34 @@
             !SubscriptMap, !SynthFuncs)
     ).
 
+% expr_to_instrs(+BlockID, +Ctx, +Expr, -Atom, -Instrs, !SubscriptMap).
+% Converts a single expression into a sequence of low-level instructions
+% which compute the expression and assign it to a variable (possibly a
+% new temporary variable name). Returns the assigned variable name in VarName.
+:- pred expr_to_instrs(progtable::in, varset::in, int::in, context::in,
+    expr::in, atom::out, list(instr)::out, type_map::out,
+    subscript_map::in, subscript_map::out,
+    list(function)::in, list(function)::out) is det.
+expr_to_instrs(PT, Varset, BlockID, Ctx, E, A, Is, Types, !SubscriptMap,
+    !SynthFuncs) :-
+    ( E = expr(intlit(Val), _) ->
+        % Special case -- expr_to_instrs_var will generate a mov.
+        % We can avoid this by just returning the int as an atom.
+        A = intatom(Val),
+        Is = [],
+        Types = map.init
+    ; E = expr(ctorref(Name), _), ir.ctor_is_cgc(PT, Name) ->
+        % Special case -- expr_to_instrs_var will generate a mov.
+        % We can avoid this by just returning the ctorsym as an atom.
+        A = ctorsym(Name),
+        Is = [],
+        Types = map.init
+    ;
+        expr_to_instrs_var(PT, Varset, BlockID, Ctx, E, V, Is, Types,
+            !SubscriptMap, !SynthFuncs),
+        A = varname(V)
+    ).
+
 % XXX The *public* version of expr_to_instrs expects non-SSA variable names;
 % it will convert them to SSA form.
 % Conversely, the *private* version of expr_to_instrs expects
@@ -923,7 +953,7 @@
 expr_to_instrs_as(_PT, _Varset, _BlockID, Ctx, E@expr(intlit(Val),_), V, Is,
     Types, !SubscriptMap, !SynthFuncs) :-
     Types = expr_typemap(V, E),
-    Is = [instr(ld_intlit(V, Val), Ctx)].
+    Is = [instr(mov(V, intatom(Val)), Ctx)].
 expr_to_instrs_as(PT, Varset, BlockID, Ctx, E@expr(arraylit(Elems0),_), V, Is,
     Types, !SubscriptMap, !SynthFuncs) :-
     Types0 = expr_typemap(V, E),
@@ -934,7 +964,7 @@
 expr_to_instrs_as(_PT, _Varset, _BlockID, Ctx, E@expr(varref(Var),_), V, Is,
     Types, !SubscriptMap, !SynthFuncs) :-
     Types = expr_typemap(V, E),
-    Is = [instr(mov(V, Var), Ctx)].
+    Is = [instr(mov(V, varname(Var)), Ctx)].
 expr_to_instrs_as(PT, _Varset, _BlockID, Ctx, E@expr(globalref(Name),_), V,
     Is, Types, !SubscriptMap, !SynthFuncs) :-
     Types = expr_typemap(V, E),
@@ -952,8 +982,8 @@
     Types = expr_typemap(V, E),
     % The instruction will depend upon the type of constructor
     ( ir.ctor_is_cgc(PT, Name) ->
-        % Algebraic constant. ld_ctorsym instruction.
-        Is = [instr(ld_ctorsym(V, Name), Ctx)]
+        % Algebraic constant. mov instruction, loading the ctorsym.
+        Is = [instr(mov(V, ctorsym(Name)), Ctx)]
     ;
         % Constructor function. Generate synthetic closure template; no cvars.
         parcall_ctor_closure_template(PT, Name, 0, CTName, !SynthFuncs),
@@ -1005,7 +1035,7 @@
         Is1 = [instr(call_ctor(V, CtorName, Args), Ctx)],
         Is = Is0 ++ Is1
     ;
-        expr_to_instrs(PT, Varset, BlockID, Ctx, Func0, Func, Is0, Types1,
+        expr_to_instrs_var(PT, Varset, BlockID, Ctx, Func0, Func, Is0, Types1,
             !SubscriptMap, !SynthFuncs),
         exprs_to_instrs(PT, Varset, BlockID, Ctx, Args0, Args, Is1, Types2,
             !SubscriptMap, !SynthFuncs),
@@ -1174,8 +1204,8 @@
     % Calculate the condition expression at the end of BBCurrent
     apply_def_map_to_expr(DefMap, Ctx, Ctrl0, Ctrl),
     BlockID = ref_id(BBCurrent, !.CFG),
-    expr_to_instrs(PT, Varset, BlockID, Ctx, Ctrl, CtrlVar, CtrlInstrs,
-                   Types0, SubscriptMap0, SubscriptMap, !SynthFuncs),
+    expr_to_instrs_var(PT, Varset, BlockID, Ctx, Ctrl, CtrlVar, CtrlInstrs,
+                       Types0, SubscriptMap0, SubscriptMap, !SynthFuncs),
     cfg.append_instrs(BBCurrent, CtrlInstrs, !CFG),
     % Convert all patterns to use SSA variables, and generate CFG code for the
     % bodies of all case statements. The resulting Cases contains goto
@@ -1884,7 +1914,7 @@
     RetType = ObjType,
     InstrBuilder = (func(Dst, Ctor, Idx) =
                     i_fieldreplace(Dst, svname("object"), Ctor, Idx,
-                                   svname("value"))).
+                                   varname(svname("value")))).
 
 % fieldfunc_set(Typedef, FieldName, FieldType) builds a field set function.
 :- func fieldfunc_set(typedef, string, typeval) = function.
@@ -1897,7 +1927,7 @@
     RetType = ObjType,
     InstrBuilder = (func(_Dst, Ctor, Idx) =
                     i_fieldset(svname("object"), Ctor, Idx,
-                               svname("value"))).
+                               varname(svname("value")))).
 
 % fieldfunc_(Typedef, FieldName, FuncName, Params, RetType, InstrBuilder,
 %            Obj, RetVar)
@@ -1958,7 +1988,7 @@
                    list.map(func(B-_) = B, Preds), !CFG),
         ( RetVar = yes(RetN) ->
             % If RetVar, return the given variable name
-            cfg.append_instr(Exit, instr(mov(retvname, RetN),
+            cfg.append_instr(Exit, instr(mov(retvname, varname(RetN)),
                 Typedef^typedef_context), !CFG),
             % The "Dst variables" should never have been assigned; don't put
             % them in the localtable
@@ -2008,24 +2038,19 @@
     cfg.append_predecessor(Bl, Pred, !CFG),
     Msg = string.format("%s instance has no field \"%s\"",
         [s(Typedef^typedef_name), s(FieldName)]),
-    list.map_foldl2((pred(Chr::in, V::out, ID::in, ID+1::out, C0::in, C::out)
-            is det :-
-            V = qvname(qvname(tempvname, cfg.ref_id(Bl, C0)), ID),
-            I = instr(ld_intlit(V, integer(char.to_int(Chr))), Ctx),
-            cfg.append_instr(Bl, I, C0, C)
-        ), string.to_char_list(Msg), CharVars, 0, _, !CFG),
+    CharAtoms = list.map(func(Chr) = intatom(integer(char.to_int(Chr))),
+        string.to_char_list(Msg)),
     % Call the 'error' built-in with this message as a Mars string
     MsgVar = qvname(tempvname, cfg.ref_id(Bl, !.CFG)),
-    MsgInstr = instr(ld_arraylit(MsgVar, CharVars), Ctx),
+    MsgInstr = instr(ld_arraylit(MsgVar, CharAtoms), Ctx),
     cfg.append_instr(Bl, MsgInstr, !CFG),
     % Assign the result to a new variable
     Dst = qvname(retvname, cfg.ref_id(Bl, !.CFG)),
-    Instr = instr(call_global(Dst, "error", [MsgVar]), Ctx),
+    Instr = instr(call_global(Dst, "error", [varname(MsgVar)]), Ctx),
     cfg.append_instr(Bl, Instr, !CFG),
     Term = branch(Exit, Ctx),
     cfg.set_terminator(Bl, Term, !CFG),
-    TypeMap = map(func(V) = V-types.const("Int"), CharVars) ++
-        [MsgVar-types.app(types.const("Array"), [types.const("Int")])].
+    TypeMap = [MsgVar-types.app(types.const("Array"), [types.const("Int")])].
 
 % -------------------------------------------------------------------------- %
 % Closure template generation
 
=== modified file 'src/cfg.m'
--- src/cfg.m	2011-10-08 06:55:14 +0000
+++ src/cfg.m	2011-10-21 03:33:25 +0000
@@ -51,7 +51,7 @@
 :- type bbref(S).
 
 % A phi is a phi statement in Static Single Assignment notation.
-% It maps a variable name V onto a mapping from bbrefs to varnames.
+% It maps a variable name V onto a mapping from bbrefs to atoms.
 % The bbref is a predecessor block P, and the varname is V0.
 % That is to say, "if you just came from block P, set V to the value of V0".
 :- type phi(S)
 
=== modified file 'src/interactive.m'
--- src/interactive.m	2011-10-21 03:11:44 +0000
+++ src/interactive.m	2011-10-21 03:33:25 +0000
@@ -385,8 +385,13 @@
                         yes(types.app(types.const("Array"),
                                       [types.const("Int")]))),
         ast_cfg.expr_to_instrs(!.State^st_progtable, !.State^st_localvarset,
-            ShowExpr, VarName, Instrs0, Types_Raw, SynthFuncs,
+            ShowExpr, Atom, Instrs0, Types_Raw, SynthFuncs,
             !.State^st_aststate, NewASTState0),
+        ( Atom = ir.varname(VarName_) ->
+            VarName = VarName_
+        ;
+            error("expr_to_instrs returned non-variable")
+        ),
         % Return the name of the temporary
         Result = yes(VarName)
     ;
 
=== modified file 'src/interpret.m'
--- src/interpret.m	2011-10-21 03:11:44 +0000
+++ src/interpret.m	2011-10-21 03:33:25 +0000
@@ -162,6 +162,21 @@
             ir.varname_string(VarName))
     ).
 
+% atom_value(+Atom, -Value, !Env, !IO)
+% Converts an atom into a runtime value.
+% If the atom is a variable, searches the environment for that variable, and
+% aborts if it is not found. Similarly, ctor symbols abort if not found.
+% Unfortunately, requires a mutable environment and IO, due to the very
+% backwards way in which we construct constructor symbol terms.
+:- pred atom_value(atom::in, value::out, env::in, env::out, io::di, io::uo)
+    is det.
+atom_value(varname(VarName), Value, !Env, !IO) :-
+    local_search_det(!.Env, VarName, Value).
+atom_value(intatom(I), Value, !Env, !IO) :-
+    Value = val_int(I).
+atom_value(ctorsym(Name), Value, !Env, !IO) :-
+    read_ctor(Name, Value, !Env, !IO).
+
 % global_search(Env, VarName, Value)
 % Searches an environment for a global variable of the given name, and returns
 % its value.
@@ -455,13 +470,14 @@
         Result = Result0
     ).
 
-% read_var_into_vector(!Env, VectorRef, VarName, !IO).
-% Reads a local variable, and appends its value onto the end of the vector.
+% read_atom_into_vector(!Env, VectorRef, Atom, !IO).
+% Reads a local variable or atom, and appends its value onto the end of the
+% vector.
 % Uses IO as the vector's store.
-:- pred read_var_into_vector(vectorref(value, io)::in, varname::in,
+:- pred read_atom_into_vector(vectorref(value, io)::in, atom::in,
     env::in, env::out, io::di, io::uo) is det.
-read_var_into_vector(VectorRef, VarName, !Env, !IO) :-
-    local_search_det(!.Env, VarName, Value),
+read_atom_into_vector(VectorRef, Atom, !Env, !IO) :-
+    atom_value(Atom, Value, !Env, !IO),
     vectorref.add(VectorRef, Value, !IO).
 
 % Insert a set of new functions into the runtime environment.
@@ -490,11 +506,11 @@
     io::di, io::uo) is det.
 exec_instr_(nop, _Ctx, !Env, !IO).
 exec_instr_(mov(Dst, Src), _Ctx, !Env, !IO) :-
-    local_search_det(!.Env, Src, Result),
+    atom_value(Src, Result, !Env, !IO),
     env_assign_local(Dst, Result, !Env).
 exec_instr_(i_fieldset(ValName, ICtor, Idx, SrcName), _Ctx, !Env, !IO) :-
     local_search_det(!.Env, ValName, Val),
-    local_search_det(!.Env, SrcName, Src),
+    atom_value(SrcName, Src, !Env, !IO),
     ( Val = val_term(Term) ->          % Must match supplied Ctor name
         store.get_mutvar(Term, marsterm(Ctor, Fields0), !IO),
         field_check_ctor(ICtor, Ctor),                  % May abort
@@ -516,7 +532,7 @@
 exec_instr_(i_fieldreplace(Dst, ValName, ICtor, Idx, SrcName), _Ctx,
     !Env, !IO) :-
     local_search_det(!.Env, ValName, Val),
-    local_search_det(!.Env, SrcName, Src),
+    atom_value(SrcName, Src, !Env, !IO),
     ( Val = val_term(Term0) ->          % Must match supplied Ctor name
         store.get_mutvar(Term0, marsterm(Ctor, Fields0), !IO),
         field_check_ctor(ICtor, Ctor),                  % May abort
@@ -536,18 +552,13 @@
     store.new_mutvar(marsterm(Ctor, Fields), Term, !IO),
     Result = val_term(Term),
     env_assign_local(Dst, Result, !Env).
-exec_instr_(ld_intlit(Dst, I), _Ctx, !Env, !IO) :-
-    env_assign_local(Dst, val_int(I), !Env).
 exec_instr_(ld_arraylit(Dst, Elems), _Ctx, !Env, !IO) :-
     % Create a new, empty vector of values
     Capacity = good_vector_capacity(list.length(Elems)),
     vectorref.init(Capacity, VectorRef, !IO),
     % Evaluate each expression, populating the vector
-    list.foldl2(read_var_into_vector(VectorRef), Elems, !Env, !IO),
+    list.foldl2(read_atom_into_vector(VectorRef), Elems, !Env, !IO),
     env_assign_local(Dst, val_array(VectorRef), !Env).
-exec_instr_(ld_ctorsym(Dst, Name), _Ctx, !Env, !IO) :-
-    read_ctor(Name, Result, !Env, !IO),
-    env_assign_local(Dst, Result, !Env).
 exec_instr_(ld_cgc(Dst, Name), _Ctx, !Env, !IO) :-
     read_cgc(Name, Result, !Env, !IO),
     env_assign_local(Dst, Result, !Env).
@@ -569,28 +580,28 @@
 exec_instr_(new_closure(Dst, Func, Args), _Ctx, !Env, !IO) :-
     % Evaluate Func and Arg (eagerly)
     global_search_det(!.Env, Func, FuncVal),
-    list.map(local_search_det(!.Env), Args, ArgVals),
+    list.map_foldl2(atom_value, Args, ArgVals, !Env, !IO),
     % Curry Args in Func, but do not evaluate
     partial_apply_vals(FuncVal, ArgVals, Result),
     env_assign_local(Dst, Result, !Env).
 exec_instr_(call(Dst, Func, Args), _Ctx, !Env, !IO) :-
     % Evaluate Func and Arg (eagerly)
     local_search_det(!.Env, Func, FuncVal),
-    list.map(local_search_det(!.Env), Args, ArgVals),
+    list.map_foldl2(atom_value, Args, ArgVals, !Env, !IO),
     % Apply Arg to Func
     apply_vals(FuncVal, ArgVals, Result, !Env, !IO),
     env_assign_local(Dst, Result, !Env).
 exec_instr_(call_ctor(Dst, Ctor, Args), _Ctx, !Env, !IO) :-
     % Evaluate Ctor and Arg (eagerly)
     read_ctor(Ctor, CtorVal, !Env, !IO),
-    list.map(local_search_det(!.Env), Args, ArgVals),
+    list.map_foldl2(atom_value, Args, ArgVals, !Env, !IO),
     % Apply Arg to Ctor
     apply_vals(CtorVal, ArgVals, Result, !Env, !IO),
     env_assign_local(Dst, Result, !Env).
 exec_instr_(call_global(Dst, Func, Args), _Ctx, !Env, !IO) :-
     % Evaluate Func and Arg (eagerly)
     global_search_det(!.Env, Func, FuncVal),
-    list.map(local_search_det(!.Env), Args, ArgVals),
+    list.map_foldl2(atom_value, Args, ArgVals, !Env, !IO),
     % Apply Arg to Func
     apply_vals(FuncVal, ArgVals, Result, !Env, !IO),
     env_assign_local(Dst, Result, !Env).
@@ -763,7 +774,7 @@
         exec_cases(CFG, BBRef, !Env, ControlVal, Cases, Default, !IO)
     ;
         Term = cond_branch(Cond, Then, Else, _),
-        local_search_det(!.Env, Cond, CondVal),
+        atom_value(Cond, CondVal, !Env, !IO),
         ( CondVal = val_int(integer(0)) ->
             % False
             exec_block(CFG, BBRef, Else, !Env, !IO)
 
=== modified file 'src/ir.m'
--- src/ir.m	2011-10-10 12:38:16 +0000
+++ src/ir.m	2011-10-21 03:33:25 +0000
@@ -185,6 +185,15 @@
             % repeating until the condition is zero.
     ;       while(expr,stmt_block).
 
+% atom: An atomic value which may be given as input to various instructions.
+:- type atom
+            % A variable name
+    --->    varname(varname)
+            % An integer literal (note: arbitrary precision)
+    ;       intatom(integer)
+            % A constructor symbol (parameterless constructor names only)
+    ;       ctorsym(string).
+
 % instr: A low-level statement with no control flow, sub-statements or
 % sub-expressions. Used by only the CFG program representation.
 :- type instr
@@ -195,21 +204,16 @@
 :- type instr_
             % NOP instruction (equivalent of pass statement)
     --->    nop
-            % Copy instruction. Copies a value from one variable to another.
-    ;       mov(varname, varname)
+            % Copy instruction. Copies a value from an atom to a variable.
+    ;       mov(varname, atom)
             % Field update (destructive). (S, C, I, V) <=> S.I := V
             % (See ld_field)
-    ;       i_fieldset(varname, string, int, varname)
+    ;       i_fieldset(varname, string, int, atom)
             % Field replace (non-destructive).
             % (R, S, C, I, V) <=> R := % S.I <- V (See ld_field)
-    ;       i_fieldreplace(varname, varname, string, int, varname)
-            % Load an integer literal. (Note arbitrary precision).
-    ;       ld_intlit(varname, integer)
+    ;       i_fieldreplace(varname, varname, string, int, atom)
             % Construct an array from a list of variables.
-    ;       ld_arraylit(varname, list(varname))
-            % Load a symbolic constant constructor into a variable.
-            % String is the name of the ctor (must not take arguments).
-    ;       ld_ctorsym(varname, string)
+    ;       ld_arraylit(varname, list(atom))
             % Load the value of a computable global constant into a variable.
             % String is the name of the CGC. Its body may be executed.
     ;       ld_cgc(varname, string)
@@ -219,15 +223,15 @@
     ;       ld_field(varname, varname, string, int)
             % Create closure from closure template. (Result, Function, Args).
             % Function must be a global closure template (not a ctor or CGC).
-    ;       new_closure(varname, string, list(varname))
+    ;       new_closure(varname, string, list(atom))
             % Local function call. (Result, Function, Args).
-    ;       call(varname, varname, list(varname))
+    ;       call(varname, varname, list(atom))
             % Constructor function call. (Result, Ctor, Args).
             % Ctor is the name of a constructor.
-    ;       call_ctor(varname, string, list(varname))
+    ;       call_ctor(varname, string, list(atom))
             % Global function call. (Result, Function, Args).
             % Function must be a global function (not a ctor or CGC).
-    ;       call_global(varname, string, list(varname)).
+    ;       call_global(varname, string, list(atom)).
 
 % terminator_instr: An instruction which may only appear at the end of a basic
 % block in the CFG representation. These roughly are the equivalents of the
@@ -250,7 +254,7 @@
             % Conditional branch instruction. Expr must be of type Int.
             % Evaluates Expr, then branches to the first basic block if it is
             % nonzero, or the second basic block if it is zero.
-    ;       cond_branch(varname, bbref(S), bbref(S), context.context)
+    ;       cond_branch(atom, bbref(S), bbref(S), context.context)
             % Unconditionally branches to the given basic block.
     ;       branch(bbref(S), context.context)
             % "Null terminator". It is a semantic error if a block with a null
 
=== modified file 'src/pretty.m'
--- src/pretty.m	2011-10-09 08:12:06 +0000
+++ src/pretty.m	2011-10-21 03:33:25 +0000
@@ -358,6 +358,11 @@
     io.write_string(":\n", !IO),
     foldl(print_stmt(Indent+1), Stmts, !IO).
 
+:- func atom_string(atom) = string.
+atom_string(varname(VarName)) = ir.varname_string(VarName).
+atom_string(intatom(I)) = integer.to_string(I).
+atom_string(ctorsym(Name)) = Name.
+
 :- pred print_instr(int::in, instr::in, io::di, io::uo) is det.
 print_instr(Indent, Instr, !IO) :-
     print_instr_(Indent, Instr ^ instr_instr, !IO),
@@ -371,35 +376,25 @@
     indent(Indent, !IO),
     io.write_string(ir.varname_string(Dst), !IO),
     io.write_string(" = ", !IO),
-    io.write_string(ir.varname_string(Src), !IO).
+    io.write_string(atom_string(Src), !IO).
 print_instr_(Indent, i_fieldset(Target, Ctor, Idx, Expr), !IO) :-
     indent(Indent, !IO),
     io.write_string(fieldref_str(Target, Ctor, Idx), !IO),
     io.write_string(" =! ", !IO),
-    io.write_string(ir.varname_string(Expr), !IO).
+    io.write_string(atom_string(Expr), !IO).
 print_instr_(Indent, i_fieldreplace(Dst, Target, Ctor, Idx, Expr), !IO) :-
     indent(Indent, !IO),
     io.write_string(ir.varname_string(Dst), !IO),
     io.write_string(" = ", !IO),
     io.write_string(fieldref_str(Target, Ctor, Idx), !IO),
     io.write_string(" := ", !IO),
-    io.write_string(ir.varname_string(Expr), !IO).
-print_instr_(Indent, ld_intlit(Dst, I), !IO) :-
-    indent(Indent, !IO),
-    io.write_string(ir.varname_string(Dst), !IO),
-    io.write_string(" = ", !IO),
-    io.write_string(integer.to_string(I), !IO).
+    io.write_string(atom_string(Expr), !IO).
 print_instr_(Indent, ld_arraylit(Dst, Elems), !IO) :-
     indent(Indent, !IO),
     io.write_string(ir.varname_string(Dst), !IO),
     io.write_string(" = ", !IO),
     io.write_string("[" ++ string.join_list(", ",
-        list.map(ir.varname_string, Elems)) ++ "]", !IO).
-print_instr_(Indent, ld_ctorsym(Dst, Name), !IO) :-
-    indent(Indent, !IO),
-    io.write_string(ir.varname_string(Dst), !IO),
-    io.write_string(" = ", !IO),
-    io.write_string(Name, !IO).
+        list.map(atom_string, Elems)) ++ "]", !IO).
 print_instr_(Indent, ld_cgc(Dst, Name), !IO) :-
     indent(Indent, !IO),
     io.write_string(ir.varname_string(Dst), !IO),
@@ -413,26 +408,25 @@
     indent(Indent, !IO),
     io.write_string(ir.varname_string(Dst), !IO),
     io.write_string(" = @", !IO),
-    ArgsStr = string.join_list(", ", list.map(ir.varname_string, Args)),
+    ArgsStr = string.join_list(", ", list.map(atom_string, Args)),
     io.write_string(Func ++ "{" ++ ArgsStr ++ "}", !IO).
 print_instr_(Indent, call(Dst, Func, Args), !IO) :-
     indent(Indent, !IO),
     io.write_string(ir.varname_string(Dst), !IO),
     io.write_string(" = ", !IO),
-    ArgsStr = string.join_list(", ",
-        list.map(ir.varname_string, Args)),
+    ArgsStr = string.join_list(", ", list.map(atom_string, Args)),
     io.write_string(ir.varname_string(Func) ++ "(" ++ ArgsStr ++ ")", !IO).
 print_instr_(Indent, call_ctor(Dst, Ctor, Args), !IO) :-
     indent(Indent, !IO),
     io.write_string(ir.varname_string(Dst), !IO),
     io.write_string(" = ", !IO),
-    ArgsStr = string.join_list(", ", list.map(ir.varname_string, Args)),
+    ArgsStr = string.join_list(", ", list.map(atom_string, Args)),
     io.write_string(Ctor ++ "(" ++ ArgsStr ++ ")", !IO).
 print_instr_(Indent, call_global(Dst, Func, Args), !IO) :-
     indent(Indent, !IO),
     io.write_string(ir.varname_string(Dst), !IO),
     io.write_string(" = @", !IO),
-    ArgsStr = string.join_list(", ", list.map(ir.varname_string, Args)),
+    ArgsStr = string.join_list(", ", list.map(atom_string, Args)),
     io.write_string(Func ++ "(" ++ ArgsStr ++ ")", !IO).
 
 :- func fieldref_str(varname, string, int) = string.
@@ -461,7 +455,7 @@
     !IO) :-
     indent(Indent, !IO),
     io.write_string("if ", !IO),
-    io.write_string(ir.varname_string(Cond), !IO),
+    io.write_string(atom_string(Cond), !IO),
     io.write_string(" goto ", !IO),
     io.write_string(cfg.ref_name(ThenPart, CFG), !IO),
     io.write_string(" else goto ", !IO),
 
=== modified file 'src/typedict.m'
--- src/typedict.m	2011-10-11 11:38:29 +0000
+++ src/typedict.m	2011-10-21 03:33:25 +0000
@@ -1224,7 +1224,9 @@
     ; Instr0 = new_closure(Dst, Name, Args) ->
         ( tables.lookup_local(!.LT, Dst, DstType) ->
             FuncType = DstType,
-            ( map(tables.lookup_local(!.LT), Args, ArgTypes_) ->
+            ( map_foldl(atom_type(PT, !.LT), Args, ArgTypes_, Varset, VSA) ->
+                % See below
+                VarsetAug = VSA,
                 ArgTypes = ArgTypes_,
                 ( DstType = types.app(types.functype, _) ->
                     true
@@ -1239,15 +1241,19 @@
             error("augment_instr_globalrefs: Not in LT: " ++
                 ir.varname_string(Dst))
         ),
-        augment_globalref(PT, PTAug, Varset, Rigids, TDVars, Name, FuncType,
-                          ArgTypes, TDExprs, !RequiredVars),
+        augment_globalref(PT, PTAug, VarsetAug, Rigids, TDVars, Name,
+                          FuncType, ArgTypes, TDExprs, !RequiredVars),
         % new_closure has the type dicts prepended to its argument list
         generate_expr_code(PTAug, Varset, Rigids, BlockID, TDExprs,
             TDArgs, PreInstrs, !LT, !BlockTempCount),
         Instr = new_closure(Dst, Name, TDArgs ++ Args)
     ; Instr0 = call_global(Dst, Name, Args) ->
         ( tables.lookup_local(!.LT, Dst, DstType) ->
-            ( map(tables.lookup_local(!.LT), Args, ArgTypes) ->
+            ( map_foldl(atom_type(PT, !.LT), Args, ArgTypes, Varset, VSA) ->
+                % atom_type may add new varset items due to ctorsyms.
+                % augment_globalref must use this augmented varset.
+                % (See LP: #877111)
+                VarsetAug = VSA,
                 FuncType = types.app(types.functype, ArgTypes ++ [DstType])
             ;
                 error("augment_instr_globalrefs: Arg not in LT")
@@ -1256,8 +1262,8 @@
             error("augment_instr_globalrefs: Not in LT: " ++
                 ir.varname_string(Dst))
         ),
-        augment_globalref(PT, PTAug, Varset, Rigids, TDVars, Name, FuncType,
-                          [], TDExprs, !RequiredVars),
+        augment_globalref(PT, PTAug, VarsetAug, Rigids, TDVars, Name,
+                          FuncType, [], TDExprs, !RequiredVars),
         ( method_builtin(Name), TDExprs = [TDExpr] ->
             % call to show or eq -- replace with field access
             MethodExpr0 = expr(fieldref(TDExpr, Name), no),
@@ -1266,7 +1272,11 @@
             generate_expr_code(PTAug, Varset, Rigids, BlockID, [MethodExpr],
                 MethodVars, PreInstrs, !LT, !BlockTempCount),
             ( MethodVars = [MethodVar] ->
-                Instr = call(Dst, MethodVar, Args)
+                ( MethodVar = varname(MethodVarName) ->
+                    Instr = call(Dst, MethodVarName, Args)
+                ;
+                    error("augment_instr_globalrefs: call to non-var atom")
+                )
             ;
                 error("augment_instr_globalrefs: generate_expr_code failed")
             )
@@ -1282,18 +1292,31 @@
     ),
     Instrs = PreInstrs ++ [InitInstr^instr_instr := Instr].
 
+% Get the type of an atom. Fail if it cannot be found.
+:- pred atom_type(progtable::in, localtable::in, atom::in, typeval::out,
+    varset::in, varset::out) is semidet.
+atom_type(_PT, LT, varname(VarName), Ty, !Varset) :-
+    tables.lookup_local(LT, VarName, Ty).
+atom_type(_PT, _LT, intatom(_), types.const("Int"), !Varset).
+atom_type(PT, _LT, ctorsym(Name), Ty, !Varset) :-
+    tables.lookup_ctor(PT, Name, Typedef, _),
+    ir.ctor_type(Typedef, Name, CtorVarset, Ty0),
+    % Add the varset of this ctor into the local varset namespace, and update
+    % the type so is is in the local namespace.
+    types.varset_mergeone(CtorVarset, !Varset, Ty0, Ty).
+
 % generate_expr_code(+PT, +Varset, +Rigids, +BlockID, +Exprs, -VarNames,
 % -Instrs, !LT, !BlockTempCount).
 % Generate code for a sequence of expressions (using ast_cfg). Concatenate all
 % the generated instructions together, update the localtable and temp count,
-% and produce a list of var names corresponding to the input expressions.
+% and produce a list of atoms corresponding to the input expressions.
 :- pred generate_expr_code(progtable::in, varset::in, list(var)::in, int::in,
-    list(expr)::in, list(varname)::out, list(instr)::out,
+    list(expr)::in, list(atom)::out, list(instr)::out,
     localtable::in, localtable::out, int::in, int::out) is det.
-generate_expr_code(PT, Varset, _Rigids, BlockID, Exprs, VarNames, Instrs, !LT,
+generate_expr_code(PT, Varset, _Rigids, BlockID, Exprs, Atoms, Instrs, !LT,
     !BlockTempCount) :-
     list_map4_foldl(ast_cfg.expr_to_instrs_post_ssa(PT, Varset, BlockID),
-                    Exprs, VarNames, InstrLists, TypeMaps, SynthFuncses,
+                    Exprs, Atoms, InstrLists, TypeMaps, SynthFuncses,
                     !BlockTempCount),
     Instrs = list.condense(InstrLists),
     ( list.condense(SynthFuncses) : list(function) = [] ->
 
=== modified file 'src/usedef.m'
--- src/usedef.m	2011-10-09 08:12:06 +0000
+++ src/usedef.m	2011-10-21 03:33:25 +0000
@@ -151,26 +151,27 @@
     Uses = uses_cond_uses(UsesSet),
     Defs = uses_cond_uses(DefsSet).
 
+:- func atoms_vars(list(atom)) = list(varname).
+atoms_vars(Atoms) = Vars :-
+    list.filter_map(pred(varname(VarName)::in, VarName::out) is semidet,
+        Atoms, Vars).
+
 instr_use_def(Instr, Uses, Defs) :-
     instr_use_def_(Instr ^ instr_instr, Uses, Defs).
 :- pred instr_use_def_(instr_::in, set(varname)::out, set(varname)::out)
     is det.
 instr_use_def_(nop, set.init, set.init).
 instr_use_def_(mov(Dst, Src), Uses, Defs) :-
-    set.singleton_set(Uses, Src),
+    Uses = set(atoms_vars([Src])),
     set.singleton_set(Defs, Dst).
 instr_use_def_(i_fieldset(Obj, _CtorIdxMap, _Msg, Var), Uses, set.init) :-
     % Note: No defs, as the variable is being mutated, not assigned to.
-    Uses = set([Obj, Var]).
+    Uses = set([Obj | atoms_vars([Var])]).
 instr_use_def_(i_fieldreplace(Dst, Obj, _CtorIdxMap, _Msg, Var), Uses, Defs):-
-    Uses = set([Obj, Var]),
-    set.singleton_set(Defs, Dst).
-instr_use_def_(ld_intlit(Dst, _I), set.init, Defs) :-
+    Uses = set([Obj | atoms_vars([Var])]),
     set.singleton_set(Defs, Dst).
 instr_use_def_(ld_arraylit(Dst, Elems), Uses, Defs) :-
-    Uses = set(Elems),
-    set.singleton_set(Defs, Dst).
-instr_use_def_(ld_ctorsym(Dst, _Name), set.init, Defs) :-
+    Uses = set(atoms_vars(Elems)),
     set.singleton_set(Defs, Dst).
 instr_use_def_(ld_cgc(Dst, _Name), set.init, Defs) :-
     set.singleton_set(Defs, Dst).
@@ -178,16 +179,16 @@
     set.singleton_set(Uses, Obj),
     set.singleton_set(Defs, Dst).
 instr_use_def_(new_closure(Dst, _Func, Args), Uses, Defs) :-
-    Uses = set(Args),
+    Uses = set(atoms_vars(Args)),
     set.singleton_set(Defs, Dst).
 instr_use_def_(call(Dst, Func, Args), Uses, Defs) :-
-    Uses = set([Func|Args]),
+    Uses = set([Func | atoms_vars(Args)]),
     set.singleton_set(Defs, Dst).
 instr_use_def_(call_ctor(Dst, _Ctor, Args), Uses, Defs) :-
-    Uses = set(Args),
+    Uses = set(atoms_vars(Args)),
     set.singleton_set(Defs, Dst).
 instr_use_def_(call_global(Dst, _Func, Args), Uses, Defs) :-
-    Uses = set(Args),
+    Uses = set(atoms_vars(Args)),
     set.singleton_set(Defs, Dst).
 
 instrs_use_def(Instrs, Uses, Defs) :-
@@ -199,7 +200,7 @@
     set.singleton_set(Uses0, Control),
     Uses = uses_cond_uses(Uses0).
 terminator_instr_use_def(cond_branch(Cond, _Then, _Else,_), Uses, map.init) :-
-    set.singleton_set(Uses0, Cond),
+    Uses0 = set(atoms_vars([Cond])),
     Uses = uses_cond_uses(Uses0).
 terminator_instr_use_def(branch(_Target,_), map.init, map.init).
 terminator_instr_use_def(null_terminator(_), map.init, map.init).
 
=== added file 'test/cases/compiler/ctorsym-unify.mar'
--- test/cases/compiler/ctorsym-unify.mar	1970-01-01 00:00:00 +0000
+++ test/cases/compiler/ctorsym-unify.mar	2011-10-21 03:33:25 +0000
@@ -0,0 +1,29 @@
+type List(a):
+    Cons(head :: a, tail :: List(a))
+    Nil
+
+def cons(y :: a, xs :: List(a)) :: List(a):
+    show(y)
+    show(xs)
+    return Cons(y, xs)
+
+def show_list(x :: List(a)) :: Array(Int):
+    return show(x)
+
+def id(x :: a) :: a = x
+
+# Test that we can take the Nil constructor :: List(a) and pass it to a
+# function of local type (b, List(b)) -> List(b) without unification problems.
+# LP: #877111
+def foo(one :: a, two :: b) :: List(b):
+    return cons(two, Nil)
+
+# Test that we can curry Nil into id (this broke when we tried to fix the
+# above bug)
+def nil_id() :: () -> List(t):
+    return id(Nil, ...)
+
+# Test that we can pass the typedict for Nil :: List(a) to another function
+# when passed directly as a constructor symbol atom.
+def bar(one :: a, two :: b) :: Array(Int):
+    return show(Nil)