Merge lp:~mgiuca/mars/closure-templates into lp:mars

[Matt Giuca]

Removed parcall, parcall_ctor and parcall_global instructions. Replaced with new closure template functions and the new_closure instruction.

The code generator (ast_cfg) is now much more powerful, and transforms each instance of partial application into a synthetic function. The resulting code is much easier to deal with in backend implementations. Completely addresses bug #744760.

[lp:~mgiuca/mars/closure-templates]

1263. By Matt Giuca on 2011-05-11

interpret: Changed show behaviour for functions; no longer prints the function name and displays 'closure' instead of 'curried'.
This reflects the new semantics of function objects. Any lifted function object will now have a meaningless name, so it doesn't make sense to show it.
Also, closures are no longer necessarily curried, since we could introduce lambda expressions.
Sadly, this means we can no longer see the name of a function object at runtime, or distinguish between built-ins, constructors, thunks etc (since they are all wrapped in closure templates).

[Matt Giuca (mgiuca)]

review: Approve

=== modified file 'doc/dev/isa.rst'
--- doc/dev/isa.rst	2011-05-11 04:53:53 +0000
+++ doc/dev/isa.rst	2011-05-11 05:12:31 +0000
@@ -183,6 +183,22 @@
 
     See the notes for ``ld_field``.
 
+:samp:`new_closure {dest} {func} {args}`
+    Creates a new closure object from a closure template function `func`.
+    Curries arguments `args` into the template's closure vars, assigning the
+    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
+    the exact number of closure variables expected by `func`, and any
+    supplied arguments must be of correct types.
+
+    Ordinary functions cannot be converted into first-class function objects;
+    to accomplish this, a closure template with no closure variables must be
+    created, and loaded with ``new_closure`` and no `args`.
+    Therefore, backends SHOULD optimise for the special case where `args` is
+    empty, to avoid constructing a new closure object where possible.
+
 :samp:`call {dest} {func} {args}`
     Calls a function from local variable `func`, supplying arguments `args`
     and assigning the result to `dest`.
@@ -191,17 +207,6 @@
     arguments expected by `func`, of correct types.
     The execution may cause side-effects or fail to return.
 
-:samp:`parcall {dest} {func} {args}`
-    Partial function application of local variable `func`. Curries arguments
-    `args` into the function, assigning the result to `dest`.
-    Constructs a new function object which expects any remaining arguments
-    which were not supplied in `args`, and calls `func` with the curried
-    arguments, followed by the remaining arguments.
-    `func` MUST be a variable containing a function value. `args` is a list of
-    variables containing the arguments. It MUST contain no more than the
-    number of arguments expected by `func`, and any supplied arguments must be
-    of correct types.
-
 :samp:`call_ctor {dest} {ctor} {args}`
     Calls constructor function `ctor`, supplying arguments `args` and
     assigning the result to `dest`.
@@ -209,21 +214,6 @@
     `args` is a list of variables containing the arguments. It MUST contain
     the exact number of arguments expected by `ctor`, of correct types.
 
-:samp:`parcall_ctor {dest} {ctor} {args}`
-    Partial function application of global function `ctor`. Curries arguments
-    `args` into the constructor function, assigning the result to `dest`.
-    Constructs a new function object which expects any remaining arguments
-    which were not supplied in `args`, and calls `ctor` with the curried
-    arguments, followed by the remaining arguments.
-    `ctor` MUST not be the name of a constant symbol.
-    `args` is a list of variables containing the arguments. It MUST contain no
-    more than the number of arguments expected by `ctor`, and any supplied
-    arguments must be of correct types.
-
-    When `args` is empty, this instruction simply loads a constructor function
-    into a local variable. Backends SHOULD optimise for this special case, to
-    avoid constructing a new closure object where possible.
-
 :samp:`call_global {dest} {func} {args}`
     Calls global function `func`, supplying arguments `args` and assigning the
     result to `dest`.
@@ -233,22 +223,6 @@
     the exact number of arguments expected by `func`, of correct types.
     The execution may cause side-effects or fail to return.
 
-:samp:`parcall_global {dest} {func} {args}`
-    Partial function application of global function `func`. Curries arguments
-    `args` into the function, assigning the result to `dest`.
-    Constructs a new function object which expects any remaining arguments
-    which were not supplied in `args`, and calls `func` with the curried
-    arguments, followed by the remaining arguments.
-    `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 no
-    more than the number of arguments expected by `func`, and any supplied
-    arguments must be of correct types.
-
-    When `args` is empty, this instruction simply loads a global function into
-    a local variable. Backends SHOULD optimise for this special case, to avoid
-    constructing a new closure object where possible.
-
 ..
 
 Terminator instructions

=== modified file 'misc/mars-asm.vim'
--- misc/mars-asm.vim	2011-05-06 09:00:09 +0000
+++ misc/mars-asm.vim	2011-05-11 05:12:31 +0000
@@ -45,7 +45,7 @@
 
 syn keyword marsStatement	return pass goto
 syn keyword marsStatement	def nextgroup=marsFunction skipwhite
-syn match   marsFunction	"[a-z_:][a-zA-Z0-9_:]*" contained
+syn match   marsFunction	"[a-z_:][a-zA-Z0-9_:;]*" contained
 syn keyword marsTypedef		type nextgroup=marsTypeName skipwhite
 syn match   marsTypeName	"[A-Z_:][a-zA-Z0-9_:]*" contained
 syn keyword marsStatement	var nextgroup=marsDecl skipwhite

=== modified file 'src/ast_cfg.m'
--- src/ast_cfg.m	2011-04-20 03:38:39 +0000
+++ src/ast_cfg.m	2011-05-11 05:12:31 +0000
@@ -48,9 +48,11 @@
 % - There exists a viable code path which does not return a value.
 % - There is an attempt to read from a variable which may not have been
 %   assigned on some or all code paths.
-:- pred func_to_cfg(progtable::in, function::in, function::out) is det.
+:- pred func_to_cfg(progtable::in, function::in, function::out,
+    list(function)::out) is det.
 
-% expr_to_instrs(+PT, +Expr, -VarName, -Instrs, -Types, !ASTState).
+% expr_to_instrs(+PT, +Expr, -VarName, -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.
@@ -58,11 +60,11 @@
 % 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,
-    list(instr)::out, map(varname, typeval)::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,
-% -Types, !BlockTempCount).
+% -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.
 % The caller must supply the BlockID and BlockTempCount, for generating unique
@@ -70,9 +72,10 @@
 % 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,
-    int::in, int::out) is det.
+    list(function)::out, int::in, int::out) is det.
 
-% basic_stmt_to_instrs(+PT, +BasicStmt, -Instrs, -Types, !ASTState).
+% basic_stmt_to_instrs(+PT, +BasicStmt, -Instrs, -Types, -SynthFuncs,
+%   !ASTState).
 % Converts a single basic statement into a sequence of low-level instructions
 % which do the same thing. This will potentially assign many temporary
 % variables.
@@ -80,7 +83,7 @@
 % subscript information given). Useful for stand-alone statements.
 % Also produces map of types of all variables bound by the instructions.
 :- pred basic_stmt_to_instrs(progtable::in, varset::in, basic_stmt::in,
-    list(instr)::out, map(varname, typeval)::out,
+    list(instr)::out, map(varname, typeval)::out, list(function)::out,
     ast_state::in, ast_state::out) is det.
 
 % Given a typedef, produces a list of CFG functions, three for each named
@@ -111,6 +114,10 @@
 % BlockID is the ID of the current block.
 :- func var_to_ssa(ast_state, int, varname) = varname.
 
+% Remove any functions with duplicate names, favouring those earlier in the
+% list. Useful for dealing with lists of synthetic functions.
+:- func remove_dup_funcs(list(function)) = list(function).
+
 % -------------------------------------------------------------------------- %
 % -------------------------------------------------------------------------- %
 
@@ -129,6 +136,8 @@
 :- import_module bool.
 :- import_module require.
 :- import_module char.
+:- import_module unit.
+:- use_module term.
 
 :- import_module cfg.
 :- import_module typecheck.
@@ -137,14 +146,18 @@
 :- import_module pretty.
 
 prog_to_cfg(PT, program(Nodes0), program(Nodes)) :-
-    prog_nodes_to_cfg(PT, Nodes0, Nodes).
+    prog_nodes_to_cfg(PT, Nodes0, Nodes1, [], SynthFuncs0),
+    % Insert the synthetic functions into the program
+    SynthFuncs = list.reverse(remove_dup_funcs(SynthFuncs0)),
+    Nodes = Nodes1 ++ map(func(F) = pfunction(F), SynthFuncs).
 
 :- pred prog_nodes_to_cfg(progtable::in,
-    list(program_node)::in, list(program_node)::out) is det.
-prog_nodes_to_cfg(_, [], []).
-prog_nodes_to_cfg(PT, [Node0|Nodes0], NewNodes ++ Nodes) :-
+    list(program_node)::in, list(program_node)::out,
+    list(function)::in, list(function)::out) is det.
+prog_nodes_to_cfg(_, [], [], !SynthFuncs).
+prog_nodes_to_cfg(PT, [Node0|Nodes0], NewNodes ++ Nodes, !SynthFuncs) :-
     ( Node0 = pfunction(Func0) ->
-        func_to_cfg(PT, Func0, Func),
+        func_to_cfg(PT, Func0, Func, !SynthFuncs),
         NewNodes = [pfunction(Func)]
     ; Node0 = ptypedef(Typedef) ->
         % Generate 3 functions for each named field
@@ -157,7 +170,7 @@
     ;
         NewNodes = [Node0]
     ),
-    prog_nodes_to_cfg(PT, Nodes0, Nodes).
+    prog_nodes_to_cfg(PT, Nodes0, Nodes, !SynthFuncs).
 
 :- pred new_def_map(def_map::out) is det.
 new_def_map(Map) :-
@@ -195,23 +208,31 @@
 :- func type_map_union_list(list(type_map)) = type_map.
 type_map_union_list(Ts) = foldl(type_map_union, Ts, map.init).
 
-func_to_cfg(PT, !Func) :-
-    % Create a new defmap with all of the params.
+func_to_cfg(PT, !Func, SynthFuncs) :-
+    func_to_cfg(PT, !Func, [], SynthFuncs).
+
+:- pred func_to_cfg(progtable::in, function::in, function::out,
+    list(function)::in, list(function)::out) is det.
+func_to_cfg(PT, !Func, !SynthFuncs) :-
+    % Create a new defmap with all of the closure vars and params.
     new_def_map(DefMap0),
-    Params = !.Func ^ func_params,
-    (
-        % No parameters
-        Params = no,
-        ParamList = [],
-        DefMap = DefMap0,
-        Types = map.init
-    ;
-        Params = yes(ParamList),
-        foldl(def_map_insert_param, ParamList, DefMap0, DefMap),
-        Types = map.from_assoc_list(map(func({N,T}) = svname(N)-T, ParamList))
-    ),
+    MaybeCVars = !.Func ^ func_cvars,
+    (
+        MaybeCVars = no, CVars = []
+    ;
+        MaybeCVars = yes(CVars)
+    ),
+    MaybeParams = !.Func ^ func_params,
+    (
+        MaybeParams = no, Params = []
+    ;
+        MaybeParams = yes(Params)
+    ),
+    ParamList = CVars ++ Params,
+    foldl(def_map_insert_param, ParamList, DefMap0, DefMap),
+    Types = map.from_assoc_list(map(func({N,T}) = svname(N)-T, ParamList)),
     func_body_to_cfg(PT, DefMap, !.Func^func_varset, ParamList, Types,
-        !.Func ^ func_context, !.Func ^ func_body, CFGBody),
+        !.Func ^ func_context, !.Func ^ func_body, CFGBody, !SynthFuncs),
     !:Func = !.Func ^ func_body := CFGBody.
 
 % Note: def_map argument should have all of the function's parameters already
@@ -219,17 +240,19 @@
 % function's parameters' types.
 :- pred func_body_to_cfg(progtable::in, def_map::in, varset::in,
     list({string, _})::in, type_map::in, context::in,
-    func_body::in, func_body::out) is det.
+    func_body::in, func_body::out, list(function)::in, list(function)::out)
+    is det.
 func_body_to_cfg(_PT, _DefMap, _Varset, _Params, _Types, _Ctx,
-    B@func_builtin, B).
+    B@func_builtin, B, !SynthFuncs).
 func_body_to_cfg(_PT, _DefMap, _Vset, _Params, _Types, _Ctx,
-    B@func_body_cfg(_,_), B).
+    B@func_body_cfg(_,_), B, !SynthFuncs).
 func_body_to_cfg(PT, DefMap0, Varset, Params, Types0, Ctx,
-    func_body_ast(Decls0,Stmts), NewFuncBody):-
+    func_body_ast(Decls0,Stmts), NewFuncBody, !SynthFuncs):-
     NewFuncBody = 'new func_body_cfg'(LT, CFG),
     % Insert all of the function's locals into the defmap, unbound
     foldl(def_map_insert_local, Decls0, DefMap0, DefMap),
-    ast_to_cfg(PT, Varset, DefMap, Ctx, Stmts, Types0, Types_Raw, CFG),
+    ast_to_cfg(PT, Varset, DefMap, Ctx, Stmts, Types0, Types_Raw, CFG,
+               !SynthFuncs),
     % Dereference all the types
     map.map_values_only(types.deref(Varset), Types_Raw, Types),
     % Get the full list of locals, in "variable ID order"
@@ -243,9 +266,9 @@
 % control flow graph, translating the code.
 % This also performs error checking (see func_to_cfg).
 :- some [S] pred ast_to_cfg(progtable::in, varset::in, def_map::in,
-    context::in, stmt_block::in, type_map::in, type_map::out, cfg(S)::out)
-    is det.
-ast_to_cfg(PT, Varset, DefMap, Ctx, Stmts, !Types, CFG) :-
+    context::in, stmt_block::in, type_map::in, type_map::out, cfg(S)::out,
+    list(function)::in, list(function)::out) is det.
+ast_to_cfg(PT, Varset, DefMap, Ctx, Stmts, !Types, CFG, !SynthFuncs) :-
     some [!CFG]
     (
         % Need to create the entry block and exit block so that
@@ -255,7 +278,7 @@
         Entry = cfg.get_entry(!.CFG),
         Exit = cfg.get_exit(!.CFG),
         stmt_block_to_cfg(PT, Varset, Stmts, Entry, Exit, DefMap, NewTypes,
-            map.init,AfterPredMap, map.init, ExitPredMap, !CFG),
+            map.init,AfterPredMap, map.init, ExitPredMap, !CFG, !SynthFuncs),
         !:Types = type_map_union(!.Types, NewTypes),
         % The union of AfterPredMap and ExitPredMap contains information about
         % all predecessors to Exit. Use this to compute phi instructions for
@@ -652,35 +675,36 @@
 :- pred stmt_block_to_cfg(progtable::in, varset::in, stmt_block::in,
     bbref(S)::in, bbref(S)::in, def_map::in, type_map::out,
     pred_map(S)::in, pred_map(S)::out, pred_map(S)::in, pred_map(S)::out,
-    cfg(S)::in, cfg(S)::out) is det.
+    cfg(S)::in, cfg(S)::out, list(function)::in, list(function)::out) is det.
 stmt_block_to_cfg(PT, Varset, Stmts, BBCurrent, BBAfter, DefMap, Types,
-    !AfterPredMap, !ExitPredMap, !CFG) :-
+    !AfterPredMap, !ExitPredMap, !CFG, !SynthFuncs) :-
     map.init(SubscriptMap),
     stmt_block_to_cfg(PT, Varset, Stmts, BBCurrent, BBAfter, SubscriptMap,
-        DefMap, Types, !AfterPredMap, !ExitPredMap, !CFG).
+        DefMap, Types, !AfterPredMap, !ExitPredMap, !CFG, !SynthFuncs).
 
 :- pred stmt_block_to_cfg(progtable::in, varset::in, stmt_block::in,
     bbref(S)::in, bbref(S)::in, subscript_map::in, def_map::in, type_map::out,
     pred_map(S)::in, pred_map(S)::out,
-    pred_map(S)::in, pred_map(S)::out, cfg(S)::in, cfg(S)::out) is det.
+    pred_map(S)::in, pred_map(S)::out, cfg(S)::in, cfg(S)::out,
+    list(function)::in, list(function)::out) is det.
 stmt_block_to_cfg(_PT, _Varset, [], BBCurrent, BBAfter, _SubscriptMap,
-    DefMap, map.init, !AfterPredMap, !ExitPredMap, !CFG) :-
+    DefMap, map.init, !AfterPredMap, !ExitPredMap, !CFG, !SynthFuncs) :-
     % Special case for empty block - just branch to BBAfter.
     add_to_pred_map(BBCurrent, DefMap, BBAfter, !AfterPredMap, !CFG),
     cfg.set_terminator(BBCurrent, branch(BBAfter, blank_context), !CFG).
 stmt_block_to_cfg(PT, Varset, [S], BBCurrent, BBAfter, SubscriptMap, DefMap,
-    Types, !AfterPredMap, !ExitPredMap, !CFG) :-
+    Types, !AfterPredMap, !ExitPredMap, !CFG, !SynthFuncs) :-
     % Base-case for the last statement in a block - compile statement into
     % BBCurrent, but end up by branching to BBAfter.
     stmt_to_cfg_last(PT, Varset, S, BBCurrent, BBAfter, SubscriptMap, DefMap,
-        Types, !AfterPredMap, !ExitPredMap, !CFG).
+        Types, !AfterPredMap, !ExitPredMap, !CFG, !SynthFuncs).
 stmt_block_to_cfg(PT, Varset, [S|Ss@[_|_]], BBCurrent, BBAfter, SubscriptMap0,
-    DefMap0, Types, !AfterPredMap, !ExitPredMap, !CFG) :-
+    DefMap0, Types, !AfterPredMap, !ExitPredMap, !CFG, !SynthFuncs) :-
     % Compile a single statement into BBCurrent. BBContinue is the block to
     % compile subsequent statements into (may be equal to BBCurrent).
     stmt_to_cfg(PT, Varset, S, BBCurrent, BBContinue, Terminated, Types0,
         SubscriptMap0, SubscriptMap, DefMap0, DefMap, !ExitPredMap,
-        !CFG),
+        !CFG, !SynthFuncs),
     % Compile subsequent statements into BBContinue, if not terminated.
     % If Terminated is 'yes', the rest of this block is inaccessible, so DO
     % NOT generate code for it. This doesn't just save time -- it is NECESSARY
@@ -693,7 +717,7 @@
     ;
         Terminated = no,
         stmt_block_to_cfg(PT, Varset, Ss, BBContinue, BBAfter, SubscriptMap,
-            DefMap, Types1, !AfterPredMap, !ExitPredMap, !CFG),
+            DefMap, Types1, !AfterPredMap, !ExitPredMap, !CFG, !SynthFuncs),
         Types = type_map_union(Types0, Types1)
     ).
 
@@ -718,18 +742,19 @@
 :- pred stmt_to_cfg(progtable::in, varset::in, stmt::in,
         bbref(S)::in, bbref(S)::out, bool::out, type_map::out,
         subscript_map::in, subscript_map::out, def_map::in, def_map::out,
-        pred_map(S)::in, pred_map(S)::out, cfg(S)::in, cfg(S)::out) is det.
+        pred_map(S)::in, pred_map(S)::out, cfg(S)::in, cfg(S)::out,
+        list(function)::in, list(function)::out) is det.
 stmt_to_cfg(PT, Varset, basic_stmt(S,Ctx), !BBRef, no, Types, !SubscriptMap,
-    !DefMap, !ExitPredMap, !CFG) :-
+    !DefMap, !ExitPredMap, !CFG, !SynthFuncs) :-
     basic_stmt_to_cfg(PT, Varset, S, Ctx, !.BBRef, Types, !SubscriptMap,
-        !DefMap, !CFG).
+        !DefMap, !CFG, !SynthFuncs).
 stmt_to_cfg(PT, Varset, compound_stmt(S,Ctx), BBCurrent, BBAfter, Terminated,
-    Types, !SubscriptMap, !DefMap, !ExitPredMap, !CFG) :-
+    Types, !SubscriptMap, !DefMap, !ExitPredMap, !CFG, !SynthFuncs) :-
     % Generate a target block for the compound statement to branch to
     cfg.new_basic_block(BBAfter, !CFG),
     compound_stmt_to_cfg(PT, Varset, S, Ctx, BBCurrent, BBAfter,
         !.SubscriptMap, !.DefMap, Types, map.init, AfterPredMap, !ExitPredMap,
-        !CFG),
+        !CFG, !SynthFuncs),
     % AfterPredMap contains information about all predecessors to BBAfter.
     % Use this to compute phi instructions for BBAfter and update DefMap.
     AfterID = ref_id(BBAfter, !.CFG),
@@ -759,18 +784,20 @@
 :- pred stmt_to_cfg_last(progtable::in, varset::in, stmt::in, bbref(S)::in,
     bbref(S)::in, subscript_map::in, def_map::in, type_map::out,
     pred_map(S)::in, pred_map(S)::out, pred_map(S)::in, pred_map(S)::out,
-    cfg(S)::in, cfg(S)::out) is det.
+    cfg(S)::in, cfg(S)::out, list(function)::in, list(function)::out) is det.
 stmt_to_cfg_last(PT, Varset, basic_stmt(S,Ctx), BBCurrent, BBAfter,
-    SubscriptMap, DefMap, Types, !AfterPredMap, !ExitPredMap, !CFG) :-
+    SubscriptMap, DefMap, Types, !AfterPredMap, !ExitPredMap, !CFG,
+    !SynthFuncs) :-
     basic_stmt_to_cfg(PT, Varset, S, Ctx, BBCurrent, Types, SubscriptMap, _,
-        DefMap, NewDefMap, !CFG),
+        DefMap, NewDefMap, !CFG, !SynthFuncs),
     % Branch to the provided BBAfter
     add_to_pred_map(BBCurrent, NewDefMap, BBAfter, !AfterPredMap, !CFG),
     cfg.set_terminator(BBCurrent, branch(BBAfter, Ctx), !CFG).
 stmt_to_cfg_last(PT, Varset, compound_stmt(S,Ctx), BBCurrent, BBAfter,
-    SubscriptMap, DefMap, Types, !AfterPredMap, !ExitPredMap, !CFG) :-
+    SubscriptMap, DefMap, Types, !AfterPredMap, !ExitPredMap, !CFG,
+    !SynthFuncs) :-
     compound_stmt_to_cfg(PT, Varset, S, Ctx, BBCurrent, BBAfter, SubscriptMap,
-        DefMap, Types, !AfterPredMap, !ExitPredMap, !CFG).
+        DefMap, Types, !AfterPredMap, !ExitPredMap, !CFG, !SynthFuncs).
 
 %%% LOW-LEVEL STATEMENT-COMPILATION PREDICATES %%%
 % Either of the above two statement compilation predicates may call either of
@@ -796,11 +823,12 @@
 %   !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,
-    subscript_map::in, subscript_map::out) is det.
+    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,
-    !SubscriptMap) :-
+    !SubscriptMap, !SynthFuncs) :-
     exprs_to_instrs_(PT, Varset, BlockID, Ctx, Es, Types, [], VarNamesRev, [],
-        LLInstrsRev, !SubscriptMap),
+        LLInstrsRev, !SubscriptMap, !SynthFuncs),
     list.reverse(VarNamesRev, VarNames),
     list.reverse(LLInstrsRev, LLInstrs),
     % "Condense" the list-of-lists into a flat list of instructions
@@ -813,17 +841,19 @@
 :- 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(list(instr))::in, list(list(instr))::out,
-    subscript_map::in, subscript_map::out) is det.
+    subscript_map::in, subscript_map::out,
+    list(function)::in, list(function)::out) is det.
 exprs_to_instrs_(_PT, _Varset, _BlockID, _Ctx, [], map.init, !VarNames,
-                 !Instrs, !SubscriptMap).
+                 !Instrs, !SubscriptMap, !SynthFuncs).
 exprs_to_instrs_(PT, Varset, BlockID,Ctx,[E|Es],Types,!VarNames, !Instrs,
-    !SubscriptMap) :-
+    !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, V, Is, Types0, !SubscriptMap,
+                   !SynthFuncs),
     !:VarNames = [V | !.VarNames],
     !:Instrs = [Is | !.Instrs],     % Do not flatten Is; keep as list of lists
     exprs_to_instrs_(PT, Varset, BlockID, Ctx, Es, Types1, !VarNames, !Instrs,
-                     !SubscriptMap),
+                     !SubscriptMap, !SynthFuncs),
     Types = type_map_union(Types0, Types1).
 
 % expr_to_instrs(+BlockID, +Ctx, +Expr, -VarName, -Instrs, !SubscriptMap).
@@ -832,8 +862,10 @@
 % 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, varname::out, list(instr)::out, type_map::out,
-    subscript_map::in, subscript_map::out) is det.
-expr_to_instrs(PT, Varset, BlockID, Ctx, E, V, Is, Types, !SubscriptMap) :-
+    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,
+    !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
@@ -844,7 +876,7 @@
     ;
         new_temp_variable(BlockID, V, !SubscriptMap),
         expr_to_instrs_as(PT, Varset, BlockID, Ctx, E, V, Is, Types,
-            !SubscriptMap)
+            !SubscriptMap, !SynthFuncs)
     ).
 
 % XXX The *public* version of expr_to_instrs expects non-SSA variable names;
@@ -852,87 +884,93 @@
 % Conversely, the *private* version of expr_to_instrs expects
 % already-converted SSA variables.
 % This disparity should probably be resolved.
-expr_to_instrs(PT, Varset, E0, V, Is, Ts, ast_state(SM0,DM), ast_state(SM,DM))
-    :-
+expr_to_instrs(PT, Varset, E0, V, Is, Ts, SynthFuncs,
+    ast_state(SM0,DM), ast_state(SM,DM)) :-
     Ctx = context.blank_context,
     apply_def_map_to_expr(DM, Ctx, E0, E),
-    expr_to_instrs(PT, Varset, 0, Ctx, E, V, Is, Ts, SM0, SM).
+    expr_to_instrs(PT, Varset, 0, Ctx, E, V, Is, Ts, SM0, SM, [], SynthFuncs).
 
-expr_to_instrs_post_ssa(PT, Varset, BlockID, E, V, Is, Ts, !BlockTempCount) :-
+expr_to_instrs_post_ssa(PT, Varset, BlockID, E, V, Is, Ts, SynthFuncs,
+    !BlockTempCount) :-
     Ctx = context.blank_context,
     % Don't need defmap; it already is in SSA form
     % Create submap -- we only need the temporary variable subscript
     SM0 = map.from_assoc_list([tempvname - !.BlockTempCount]),
-    expr_to_instrs(PT, Varset, BlockID, Ctx, E, V, Is, Ts, SM0, SM),
+    expr_to_instrs(PT, Varset, BlockID, Ctx, E, V, Is, Ts, SM0, SM, [],
+        SynthFuncs),
     !:BlockTempCount = map.lookup(SM, tempvname).
 
 % expr_to_instrs_as(+PT, +BlockID, +Ctx, +Expr, +VarName, -Instrs, -Types,
-%   !SubscriptMap).
+%   !SubscriptMap, !SynthFuncs).
 % Like expr_to_instrs, but it assigns to a specific VarName as given.
 % (This is less efficient as it may generate a mov instruction).
 :- pred expr_to_instrs_as(progtable::in, varset::in, int::in, context::in,
     expr::in, varname::in, list(instr)::out, type_map::out,
-    subscript_map::in, subscript_map::out) is det.
+    subscript_map::in, subscript_map::out,
+    list(function)::in, list(function)::out) is det.
 expr_to_instrs_as(_PT, _Varset, _BlockID, Ctx, E@expr(intlit(Val),_), V, Is,
-    Types, !SubscriptMap) :-
+    Types, !SubscriptMap, !SynthFuncs) :-
     Types = expr_typemap(V, E),
     Is = [instr(ld_intlit(V, Val), Ctx)].
 expr_to_instrs_as(PT, Varset, BlockID, Ctx, E@expr(arraylit(Elems0),_), V, Is,
-    Types, !SubscriptMap) :-
+    Types, !SubscriptMap, !SynthFuncs) :-
     Types0 = expr_typemap(V, E),
     exprs_to_instrs(PT, Varset, BlockID, Ctx, Elems0, Elems, Is0, Types1,
-        !SubscriptMap),
+        !SubscriptMap, !SynthFuncs),
     Types = type_map_union(Types0, Types1),
     Is = Is0 ++ [instr(ld_arraylit(V, Elems), Ctx)].
 expr_to_instrs_as(_PT, _Varset, _BlockID, Ctx, E@expr(varref(Var),_), V, Is,
-    Types, !SubscriptMap) :-
+    Types, !SubscriptMap, !SynthFuncs) :-
     Types = expr_typemap(V, E),
     Is = [instr(mov(V, Var), Ctx)].
 expr_to_instrs_as(PT, _Varset, _BlockID, Ctx, E@expr(globalref(Name),_), V,
-    Is, Types, !SubscriptMap) :-
+    Is, Types, !SubscriptMap, !SynthFuncs) :-
     Types = expr_typemap(V, E),
     % The instruction will depend upon the type of variable
     ( ir.global_is_cgc(PT, Name) ->
         % Computable global constant. ld_cgc instruction.
         Is = [instr(ld_cgc(V, Name), Ctx)]
     ;
-        % Global function. parcall_global instruction, with no arguments.
-        Is = [instr(parcall_global(V, Name, []), Ctx)]
+        % Global function. Generate a synthetic closure template; no cvars.
+        parcall_global_closure_template(PT, Name, 0, CTName, !SynthFuncs),
+        Is = [instr(new_closure(V, CTName, []), Ctx)]
     ).
 expr_to_instrs_as(PT, _Varset, _BlockID, Ctx, E@expr(ctorref(Name),_), V, Is,
-    Types, !SubscriptMap) :-
+    Types, !SubscriptMap, !SynthFuncs) :-
     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)]
     ;
-        % Constructor function. parcall_ctor instruction, with no arguments.
-        Is = [instr(parcall_ctor(V, Name, []), Ctx)]
+        % Constructor function. Generate synthetic closure template; no cvars.
+        parcall_ctor_closure_template(PT, Name, 0, CTName, !SynthFuncs),
+        Is = [instr(new_closure(V, CTName, []), Ctx)]
     ).
 expr_to_instrs_as(PT, Varset, BlockID, Ctx, E@expr(fieldref(Obj0, Field),_),
-    V, Is, Types, !SubscriptMap) :-
+    V, Is, Types, !SubscriptMap, !SynthFuncs) :-
     Types0 = expr_typemap(V, E),
     expr_to_instrs(PT, Varset, BlockID, Ctx, Obj0, Obj, Is0, Types1,
-                   !SubscriptMap),
+                   !SubscriptMap, !SynthFuncs),
     Types = type_map_union(Types0, Types1),
     % All fields have a special function generated to handle this; call it
     FuncName = ir.fieldfunc_name_ref(expr_typedef(PT, Varset, Obj0), Field),
     Is = Is0 ++ [instr(call_global(V, FuncName, [Obj]), Ctx)].
 expr_to_instrs_as(PT, Varset, BlockID, Ctx,
-    E@expr(fieldreplace(Obj0, Field, Val0),_), V, Is, Types, !SubscriptMap) :-
+    E@expr(fieldreplace(Obj0, Field, Val0),_), V, Is, Types, !SubscriptMap,
+    !SynthFuncs) :-
     Types0 = expr_typemap(V, E),
     expr_to_instrs(PT, Varset, BlockID, Ctx, Obj0, Obj, Is0, Types1,
-        !SubscriptMap),
+        !SubscriptMap, !SynthFuncs),
     expr_to_instrs(PT, Varset, BlockID, Ctx, Val0, Val, Is1, Types2,
-        !SubscriptMap),
+        !SubscriptMap, !SynthFuncs),
     Types = type_map_union(Types0, type_map_union(Types1, Types2)),
     % All fields have a special function generated to handle this; call it
     FuncName = ir.fieldfunc_name_replace(expr_typedef(PT,Varset,Obj0), Field),
     Is2 = [instr(call_global(V, FuncName, [Obj, Val]), Ctx)],
     Is = Is0 ++ Is1 ++ Is2.
 expr_to_instrs_as(PT, Varset, BlockID, Ctx, E@expr(app(Func0, Args0),_), V,
-    Is, Types, !SubscriptMap) :-
+    Is, Types, !SubscriptMap, !SynthFuncs) :-
     Types0 = expr_typemap(V, E),
     (
         Func0 = expr(globalref(FuncName), _),
@@ -940,7 +978,7 @@
     ->
         % Special case -- call to a global function name
         exprs_to_instrs(PT, Varset, BlockID, Ctx, Args0, Args, Is0, Types1,
-            !SubscriptMap),
+            !SubscriptMap, !SynthFuncs),
         Types = type_map_union(Types0, Types1),
         Is1 = [instr(call_global(V, FuncName, Args), Ctx)],
         Is = Is0 ++ Is1
@@ -950,21 +988,21 @@
     ->
         % Special case -- call to a constructor function
         exprs_to_instrs(PT, Varset, BlockID, Ctx, Args0, Args, Is0, Types1,
-            !SubscriptMap),
+            !SubscriptMap, !SynthFuncs),
         Types = type_map_union(Types0, Types1),
         Is1 = [instr(call_ctor(V, CtorName, Args), Ctx)],
         Is = Is0 ++ Is1
     ;
         expr_to_instrs(PT, Varset, BlockID, Ctx, Func0, Func, Is0, Types1,
-            !SubscriptMap),
+            !SubscriptMap, !SynthFuncs),
         exprs_to_instrs(PT, Varset, BlockID, Ctx, Args0, Args, Is1, Types2,
-            !SubscriptMap),
+            !SubscriptMap, !SynthFuncs),
         Types = type_map_union(Types0, type_map_union(Types1, Types2)),
         Is2 = [instr(call(V, Func, Args), Ctx)],
         Is = Is0 ++ Is1 ++ Is2
     ).
 expr_to_instrs_as(PT, Varset, BlockID, Ctx, E@expr(parapp(Func0, Args0),_), V,
-    Is, Types, !SubscriptMap) :-
+    Is, Types, !SubscriptMap, !SynthFuncs) :-
     Types0 = expr_typemap(V, E),
     (
         Func0 = expr(globalref(FuncName), _),
@@ -972,9 +1010,12 @@
     ->
         % Special case -- parcall to a global function name
         exprs_to_instrs(PT, Varset, BlockID, Ctx, Args0, Args, Is0, Types1,
-            !SubscriptMap),
+            !SubscriptMap, !SynthFuncs),
         Types = type_map_union(Types0, Types1),
-        Is1 = [instr(parcall_global(V, FuncName, Args), Ctx)],
+        % Generate a synthetic closure template
+        parcall_global_closure_template(PT, FuncName, length(Args), CTName,
+            !SynthFuncs),
+        Is1 = [instr(new_closure(V, CTName, Args), Ctx)],
         Is = Is0 ++ Is1
     ;
         Func0 = expr(ctorref(CtorName), _),
@@ -982,17 +1023,28 @@
     ->
         % Special case -- parcall to a constructor function
         exprs_to_instrs(PT, Varset, BlockID, Ctx, Args0, Args, Is0, Types1,
-            !SubscriptMap),
+            !SubscriptMap, !SynthFuncs),
         Types = type_map_union(Types0, Types1),
-        Is1 = [instr(parcall_ctor(V, CtorName, Args), Ctx)],
+        % Generate a synthetic closure template
+        parcall_ctor_closure_template(PT, CtorName, length(Args), CTName,
+            !SynthFuncs),
+        Is1 = [instr(new_closure(V, CTName, Args), Ctx)],
         Is = Is0 ++ Is1
     ;
         expr_to_instrs(PT, Varset, BlockID, Ctx, Func0, Func, Is0, Types1,
-            !SubscriptMap),
+            !SubscriptMap, !SynthFuncs),
         exprs_to_instrs(PT, Varset, BlockID, Ctx, Args0, Args, Is1, Types2,
-            !SubscriptMap),
+            !SubscriptMap, !SynthFuncs),
         Types = type_map_union(Types0, type_map_union(Types1, Types2)),
-        Is2 = [instr(parcall(V, Func, Args), Ctx)],
+        % Generate a synthetic closure template
+        ( Func0^expr_type = yes(FuncType_) ->
+            FuncType = FuncType_
+        ;
+            error("expr_to_instrs_as: Parcall target has no type")
+        ),
+        parcall_closure_template(PT, FuncType, length(Args), CTName,
+            !SynthFuncs),
+        Is2 = [instr(new_closure(V, CTName, [Func|Args]), Ctx)],
         Is = Is0 ++ Is1 ++ Is2
     ).
 
@@ -1014,10 +1066,10 @@
         error("expr_typedef: Expr type was not user-defined")
     ).
 
-basic_stmt_to_instrs(PT, Varset, BasicStmt, Instrs, Types,
+basic_stmt_to_instrs(PT, Varset, BasicStmt, Instrs, Types, SynthFuncs,
         ast_state(SM0,DM0), ast_state(SM,DM)) :-
     basic_stmt_to_instrs(PT, Varset, 0, BasicStmt, context.blank_context,
-        Types, Instrs, SM0, SM, DM0, DM).
+        Types, Instrs, SM0, SM, DM0, DM, [], SynthFuncs).
 
 % basic_stmt_to_instrs(+PT, +BlockID, +BasicStmt, +Ctx, -Types, -Instrs,
 %   !SubscriptMap).
@@ -1027,23 +1079,24 @@
 % newly-defined variables.
 :- pred basic_stmt_to_instrs(progtable::in, varset::in, int::in,
     basic_stmt::in, context::in, type_map::out, list(instr)::out,
-    subscript_map::in, subscript_map::out, def_map::in, def_map::out) is det.
+    subscript_map::in, subscript_map::out, def_map::in, def_map::out,
+    list(function)::in, list(function)::out) is det.
 basic_stmt_to_instrs(_PT, _Varset, _BlockID, pass, _Ctx, map.init, [],
-    !SubscriptMap, !DefMap).
+    !SubscriptMap, !DefMap, !SynthFuncs).
 basic_stmt_to_instrs(PT, Varset, BlockID, assign(V0, E0), Ctx, Types, Is,
-    !SubscriptMap, !DefMap) :-
+    !SubscriptMap, !DefMap, !SynthFuncs) :-
     apply_def_map_to_expr(!.DefMap, Ctx, E0, E),
     new_ssa_variable(BlockID, V0, V, !SubscriptMap, !DefMap),
     expr_to_instrs_as(PT, Varset, BlockID, Ctx, E, V, Is, Types,
-        !SubscriptMap).
+        !SubscriptMap, !SynthFuncs).
 basic_stmt_to_instrs(PT, Varset, BlockID, fieldset(Obj0, Field, Val0), Ctx,
-    Types, Is, !SubscriptMap, !DefMap) :-
+    Types, Is, !SubscriptMap, !DefMap, !SynthFuncs) :-
     apply_def_map_to_expr(!.DefMap, Ctx, Obj0, Obj1),
     apply_def_map_to_expr(!.DefMap, Ctx, Val0, Val1),
     expr_to_instrs(PT, Varset, BlockID, Ctx, Obj1, Obj, Is0, Types0,
-        !SubscriptMap),
+        !SubscriptMap, !SynthFuncs),
     expr_to_instrs(PT, Varset, BlockID, Ctx, Val1, Val, Is1, Types1,
-        !SubscriptMap),
+        !SubscriptMap, !SynthFuncs),
     % All fields have a special function generated to handle this; call it
     % Note: the '/set' functions return the object; ignore the result
     new_temp_variable(BlockID, V, !SubscriptMap),
@@ -1053,10 +1106,11 @@
     Is2 = [instr(call_global(V, FuncName, [Obj, Val]), Ctx)],
     Is = Is0 ++ Is1 ++ Is2.
 basic_stmt_to_instrs(PT, Varset, BlockID, eval(E0), Ctx, Types, Is,
-    !SubscriptMap, !DefMap) :-
+    !SubscriptMap, !DefMap, !SynthFuncs) :-
     apply_def_map_to_expr(!.DefMap, Ctx, E0, E),
     % The variable _T is assigned to, then thrown away.
-    expr_to_instrs(PT, Varset, BlockID, Ctx, E, _T, Is, Types, !SubscriptMap).
+    expr_to_instrs(PT, Varset, BlockID, Ctx, E, _T, Is, Types, !SubscriptMap,
+                   !SynthFuncs).
 
 % basic_stmt_to_cfg(+PT, +Varset, +BasicStmt, +Ctx, +BBCurrent, -Types,
 %   !SubscriptMap, !DefMap, !CFG).
@@ -1066,12 +1120,12 @@
 :- pred basic_stmt_to_cfg(progtable::in, varset::in, basic_stmt::in,
     context::in, bbref(S)::in, type_map::out,
     subscript_map::in, subscript_map::out, def_map::in, def_map::out,
-    cfg(S)::in, cfg(S)::out) is det.
+    cfg(S)::in, cfg(S)::out, list(function)::in, list(function)::out) is det.
 basic_stmt_to_cfg(PT, Varset, Stmt, Ctx, BBCurrent, Types, !SubscriptMap,
-    !DefMap, !CFG) :-
+    !DefMap, !CFG, !SynthFuncs) :-
     BlockID = ref_id(BBCurrent, !.CFG),
     basic_stmt_to_instrs(PT, Varset, BlockID, Stmt, Ctx, Types, Instrs,
-                         !SubscriptMap, !DefMap),
+                         !SubscriptMap, !DefMap, !SynthFuncs),
     cfg.append_instrs(BBCurrent, Instrs, !CFG).
 
 % compound_stmt_to_cfg(+CompoundStmt, +Varset, +Ctx, +BBCurrent, +BBAfter,
@@ -1090,30 +1144,33 @@
 :- pred compound_stmt_to_cfg(progtable::in, varset::in, compound_stmt::in,
     context::in, bbref(S)::in, bbref(S)::in, subscript_map::in, def_map::in,
     type_map::out, pred_map(S)::in, pred_map(S)::out,
-    pred_map(S)::in, pred_map(S)::out, cfg(S)::in, cfg(S)::out) is det.
+    pred_map(S)::in, pred_map(S)::out, cfg(S)::in, cfg(S)::out,
+    list(function)::in, list(function)::out) is det.
 compound_stmt_to_cfg(PT, Varset, return(Expr), Ctx, BBCurrent, _BBAfter,
-    SubscriptMap, DefMap0, Types, !AfterPredMap, !ExitPredMap, !CFG) :-
+    SubscriptMap, DefMap0, Types, !AfterPredMap, !ExitPredMap, !CFG,
+    !SynthFuncs) :-
     % Return is expressed in CFG as $RET = expr, followed by a branch to the
     % exit block.
     basic_stmt_to_cfg(PT, Varset, assign(retvname, Expr), Ctx, BBCurrent,
-        Types, SubscriptMap, _, DefMap0, DefMap, !CFG),
+        Types, SubscriptMap, _, DefMap0, DefMap, !CFG, !SynthFuncs),
     ExitBlock = cfg.get_exit(!.CFG),
     add_to_pred_map(BBCurrent, DefMap, ExitBlock, !ExitPredMap, !CFG),
     cfg.set_terminator(BBCurrent, branch(ExitBlock, Ctx), !CFG).
 compound_stmt_to_cfg(PT, Varset, switch(Ctrl0, Cases0), Ctx, BBCurrent,
-    BBAfter, SubscriptMap0, DefMap, Types, !AfterPredMap, !ExitPredMap, !CFG)
-    :-
+    BBAfter, SubscriptMap0, DefMap, Types, !AfterPredMap, !ExitPredMap, !CFG,
+    !SynthFuncs) :-
     % 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),
+                   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
     % statements for each generated block.
-    list.map_foldl3(case_stmt_to_jmp(PT, Varset, BBAfter, DefMap),
-                    Cases0, CasesTypes, !AfterPredMap, !ExitPredMap, !CFG),
+    list.map_foldl4(case_stmt_to_jmp(PT, Varset, BBAfter, DefMap),
+                    Cases0, CasesTypes, !AfterPredMap, !ExitPredMap, !CFG,
+                    !SynthFuncs),
     Cases = map(fst, CasesTypes),
     % Now begin switch factoring transformation
     % Convert each case statement to a matcher (flatten the patterns)
@@ -1125,18 +1182,18 @@
     map.foldl(generate_case_block_phis, PhiTable, !CFG).
 compound_stmt_to_cfg(PT, Varset, if_then_else(Cond0,ThenPart,ElsePart), Ctx,
     BBCurrent, BBAfter, SubscriptMap, DefMap, Types, !AfterPredMap,
-    !ExitPredMap, !CFG) :-
+    !ExitPredMap, !CFG, !SynthFuncs) :-
     % Calculate the condition expression at the end of BBCurrent
     apply_def_map_to_expr(DefMap, Ctx, Cond0, Cond),
     BlockID = ref_id(BBCurrent, !.CFG),
     expr_to_instrs(PT, Varset, BlockID, Ctx, Cond, CondVar, CondInstrs,
-                   Types0, SubscriptMap, _),
+                   Types0, SubscriptMap, _, !SynthFuncs),
     cfg.append_instrs(BBCurrent, CondInstrs, !CFG),
     % Create a new basic block for the "then" part.
     cfg.new_basic_block(ThenEnter, !CFG),
     cfg.append_predecessor(ThenEnter, BBCurrent, !CFG),
     stmt_block_to_cfg(PT, Varset, ThenPart, ThenEnter, BBAfter, DefMap,
-        Types1, !AfterPredMap, !ExitPredMap, !CFG),
+        Types1, !AfterPredMap, !ExitPredMap, !CFG, !SynthFuncs),
     ( list.is_empty(ElsePart) ->
         % Branch straight to the "after" block if the condition fails
         add_to_pred_map(BBCurrent, DefMap, BBAfter, !AfterPredMap, !CFG),
@@ -1148,7 +1205,7 @@
         cfg.new_basic_block(ElseEnter, !CFG),
         cfg.append_predecessor(ElseEnter, BBCurrent, !CFG),
         stmt_block_to_cfg(PT, Varset, ElsePart, ElseEnter, BBAfter, DefMap,
-            Types2, !AfterPredMap, !ExitPredMap, !CFG),
+            Types2, !AfterPredMap, !ExitPredMap, !CFG, !SynthFuncs),
         % Have the current block terminate by branching into the then/else
         % blocks
         cfg.set_terminator(BBCurrent,
@@ -1156,7 +1213,8 @@
         Types = type_map_union(Types0, type_map_union(Types1, Types2))
     ).
 compound_stmt_to_cfg(PT, Varset, while(Cond0, Body), Ctx, BBCurrent, BBAfter,
-    SubscriptMap, DefMap, Types, !AfterPredMap, !ExitPredMap, !CFG) :-
+    SubscriptMap, DefMap, Types, !AfterPredMap, !ExitPredMap, !CFG,
+    !SynthFuncs) :-
     % Create a new basic block for the condition and body
     cfg.new_basic_block(CondBlock, !CFG),
     cfg.new_basic_block(BodyEnter, !CFG),
@@ -1176,7 +1234,7 @@
     % Do the whole fixpoint. Updates CFG by setting CondBlock's phis, and
     % compiling Body.
     while_fixpoint(PT, Varset, CondBlock, BodyEnter, Body, CondBlockPredMap,
-        Types0, !ExitPredMap, DefMap, CondBlockDefMap, !CFG),
+        Types0, !ExitPredMap, DefMap, CondBlockDefMap, !CFG, !SynthFuncs),
 
     % CondBlock branches to BodyBlock or BBAfter, based on the condition
     % Note: Use append_predecessor (not add_to_pred_map) because CondBlock is
@@ -1189,7 +1247,7 @@
     apply_def_map_to_expr(CondBlockDefMap, Ctx, Cond0, Cond),
     BlockID = ref_id(CondBlock, !.CFG),
     expr_to_instrs(PT, Varset, BlockID, Ctx, Cond, CondVar, CondInstrs,
-                   Types1, SubscriptMap, _),
+                   Types1, SubscriptMap, _, !SynthFuncs),
     Types = type_map_union(Types0, Types1),
     cfg.append_instrs(CondBlock, CondInstrs, !CFG),
     cfg.set_terminator(CondBlock, cond_branch(CondVar,BodyEnter,BBAfter,Ctx),
@@ -1205,23 +1263,25 @@
 :- pred while_fixpoint(progtable::in, varset::in, bbref(S)::in, bbref(S)::in,
     stmt_block::in, pred_map(S)::in, type_map::out,
     pred_map(S)::in, pred_map(S)::out,
-    def_map::in, def_map::out, cfg(S)::in, cfg(S)::out) is det.
+    def_map::in, def_map::out, cfg(S)::in, cfg(S)::out,
+    list(function)::in, list(function)::out) is det.
 while_fixpoint(PT, Varset, CondBlock, BodyEnter, Body, CondPredMap, Types,
-    !ExitPredMap, !DefMap, !CFG) :-
+    !ExitPredMap, !DefMap, !CFG, !SynthFuncs) :-
     % First iteration, assume there are no phis
     while_fixpoint_(PT, Varset, CondBlock, BodyEnter, Body, CondPredMap, [],
-        Types, !ExitPredMap, !DefMap, !CFG).
+        Types, !ExitPredMap, !DefMap, !CFG, !SynthFuncs).
 
 :- pred while_fixpoint_(progtable::in, varset::in, bbref(S)::in, bbref(S)::in,
     stmt_block::in, pred_map(S)::in, list(phi(S))::in, type_map::out,
     pred_map(S)::in, pred_map(S)::out,
-    def_map::in, def_map::out, cfg(S)::in, cfg(S)::out) is det.
+    def_map::in, def_map::out, cfg(S)::in, cfg(S)::out,
+    list(function)::in, list(function)::out) is det.
 while_fixpoint_(PT, Varset, CondBlock, BodyEnter, Body, CondPredMap0, Phis0,
-    Types, !ExitPredMap, !CondDefMap, !CFG) :-
+    Types, !ExitPredMap, !CondDefMap, !CFG, !SynthFuncs) :-
     % Compute CondPredMap (after another iteration of the body)
     stmt_block_to_cfg(PT, Varset, Body, BodyEnter, CondBlock, !.CondDefMap,
         Types0, CondPredMap0, CondPredMap, !ExitPredMap, !.CFG,
-        PotentialFinalCFG),
+        PotentialFinalCFG, !SynthFuncs),
     % Now we can compute the phis for the cond block
     CondBlockID = ref_id(CondBlock, !.CFG),
     reconcile_def_maps(CondBlockID, CondPredMap, Phis, _, CondDefMap1),
@@ -1235,7 +1295,8 @@
     ;
         % Now iterate till fixpoint
         while_fixpoint_(PT, Varset, CondBlock, BodyEnter, Body, CondPredMap,
-            Phis, Types, !ExitPredMap, CondDefMap1, !:CondDefMap, !CFG)
+            Phis, Types, !ExitPredMap, CondDefMap1, !:CondDefMap, !CFG,
+            !SynthFuncs)
     ).
 
 % Intermediate representation of a case statement -- still contains recursive
@@ -1705,11 +1766,12 @@
 :- pred case_stmt_to_jmp(progtable::in, varset::in,
     bbref(S)::in, def_map::in, case_stmt::in,
     pair(jmp_case_stmt(S), type_map)::out, pred_map(S)::in, pred_map(S)::out,
-    pred_map(S)::in, pred_map(S)::out, cfg(S)::in, cfg(S)::out) is det.
+    pred_map(S)::in, pred_map(S)::out, cfg(S)::in, cfg(S)::out,
+    list(function)::in, list(function)::out) is det.
 case_stmt_to_jmp(PT, Varset, BBAfter, DefMap,
     case_stmt(Pattern0, Stmts, Ctx),
     jmp_case_stmt(Pattern, BBFirst, Ctx) - Types, !AfterPredMap, !ExitPredMap,
-    !CFG) :-
+    !CFG, !SynthFuncs) :-
     % New basic block for the body of the case statement
     cfg.new_basic_block(BBFirst, !CFG),
     % Traverse the pattern and uniquely label each newly-introduced
@@ -1723,7 +1785,8 @@
     % Generate the code for the body of the case statement, using the new
     % subscript map (which includes the newly-bound variables)
     stmt_block_to_cfg(PT,Varset,  Stmts, BBFirst, BBAfter, SubscriptMap,
-        InnerScopeDefMap, Types1, !AfterPredMap, !ExitPredMap, !CFG),
+        InnerScopeDefMap, Types1, !AfterPredMap, !ExitPredMap, !CFG,
+        !SynthFuncs),
 
     Types = type_map_union(Types0, Types1).
 
@@ -1895,7 +1958,8 @@
         [retvname-RetType|map(func(N-T) = svname(N)-T, Params) ++ LT_Dst]),
     Body = 'new func_body_cfg'(LT, CFG),
     Ctx = Typedef^typedef_context,
-    Func = function(FuncName, Params_, RetType, Varset, [],Rigids, Body, Ctx).
+    Func = function(FuncName, no, Params_, RetType, Varset, [],Rigids, Body,
+                    Ctx).
 
 :- pred fieldfunc_block(
     func(varname, string, int) = instr_::in, typedef::in, bbref(S)::in,
@@ -1939,3 +2003,232 @@
     cfg.set_terminator(Bl, Term, !CFG),
     TypeMap = map(func(V) = V-types.const("Int"), CharVars) ++
         [MsgVar-types.app(types.const("Array"), [types.const("Int")])].
+
+% -------------------------------------------------------------------------- %
+% Closure template generation
+% -------------------------------------------------------------------------- %
+
+% parcall_global_closure_template(PT, Target, N)
+% Builds a closure template which takes N cvars, and any remaining
+% required parameters, and calls Target.
+:- pred parcall_global_closure_template(tables.progtable::in, string::in,
+    int::in, string::out, list(function)::in, list(function)::out).
+parcall_global_closure_template(PT, Target, N, Name, !SynthFuncs) :-
+    ( tables.lookup_function(PT, Target, Callee_) ->
+        Callee = Callee_
+    ;
+        error("parcall_global_closure_template: Not found: " ++ Target)
+    ),
+    (
+        Callee^func_params = yes(CalleeParams)
+    ;
+        Callee^func_params = no,
+        error("parcall_global_closure_template: Parcall to CGC")
+    ),
+    (
+        Callee^func_cvars = yes(_),
+        error("parcall_global_closure_template: Parcall to closure template")
+    ;
+        Callee^func_cvars = no
+    ),
+    ir.function_type(Callee, _, CalleeType),
+    RetType = Callee^func_ret_type,
+    Varset = Callee^func_varset,
+    Rigids = Callee^func_rigids,
+
+    build_closure_template(PT, globalref(Target), Target, CalleeParams,
+        CalleeType, RetType, Varset, Rigids, N, Name, !SynthFuncs).
+
+% parcall_ctor_closure_template(PT, Target, N)
+% Builds a closure template which takes N cvars, and any remaining
+% required parameters, and calls Target, which is a global constructor.
+:- pred parcall_ctor_closure_template(tables.progtable::in, string::in,
+    int::in, string::out, list(function)::in, list(function)::out).
+parcall_ctor_closure_template(PT, Target, N, Name, !SynthFuncs) :-
+    ( tables.lookup_ctor(PT, Target, Typedef_, Ctor_) ->
+        Typedef = Typedef_, Ctor = Ctor_
+    ;
+        error("parcall_ctor_closure_template: Not found: " ++ Target)
+    ),
+    (
+        Ctor^ctor_args = yes(CalleeMaybeParams)
+    ;
+        Ctor^ctor_args = no,
+        error("parcall_ctor_closure_template: Parcall to ctor constant")
+    ),
+    % Give a name to each unnamed argument
+    list.map_foldl((pred(MaybeName-Ty::in, {Nm,Ty}::out, I::in, I+1::out)
+                    is det :-
+                    (
+                        MaybeName = yes(Nm)
+                    ;
+                        MaybeName = no,
+                        % Use the colon to ensure no overlap with the named
+                        % parameters
+                        Nm = "p:" ++ string(I)
+                    )), CalleeMaybeParams, CalleeParams, 1, _),
+    ( ir.ctor_type(Typedef, Target, _, CalleeType_) ->
+        CalleeType = CalleeType_
+    ;
+        error("parcall_ctor_closure_template: Ctor not found in own typedef")
+    ),
+    typedef_type(Typedef, RetType),
+    Varset = Typedef^typedef_varset,
+    Rigids = varset.vars(Varset),
+
+    build_closure_template(PT, ctorref(Target), Target, CalleeParams,
+        CalleeType, RetType, Varset, Rigids, N, Name, !SynthFuncs).
+
+% Common code for building closure templates
+:- pred build_closure_template(tables.progtable::in, expr_::in, string::in,
+    list({string, typeval})::in, typeval::in, typeval::in, varset::in,
+    list(term.var)::in, int::in, string::out,
+    list(function)::in, list(function)::out).
+build_closure_template(PT, Target, TargetName, CalleeParams, CalleeType,
+    RetType, Varset, Rigids, N, Name, !SynthFuncs) :-
+    CTemp0 = function(Name, CVars, Params, RetType, Varset, TDVars, Rigids,
+                      Body, Ctx),
+    ( N > 0 ->
+        Name = "ct:" ++ TargetName ++ ":" ++ string(N)
+    ;
+        % Special name, with no number on the end
+        % (represents a simple function lifter; conceptually not currying)
+        Name = "ct:" ++ TargetName
+    ),
+    % Split func_params into N CVars and remaining Params
+    ( list.split_list(N, CalleeParams, YesCVars, YesParams) ->
+        CVars = yes(YesCVars),
+        Params = yes(YesParams)
+    ;
+        error("build_closure_template: N > number of params")
+    ),
+    TDVars = [],        % Populated later (by typedict)
+    Ctx = context.blank_context,
+
+    % Build the body:
+    %   return Callee(*CalleeParams)
+    ArgNames = map(func({Nm,Ty}) = expr(varref(svname(Nm)), yes(Ty)),
+                   CalleeParams),
+    RetExpr = expr(app(expr(Target,yes(CalleeType)), ArgNames), yes(RetType)),
+    Body = func_body_ast([], [compound_stmt(return(RetExpr), Ctx)]),
+
+    % Compile it into CFG form
+    % Note: InnerSynthFuncs should be empty, but if there are any we handle it
+    func_to_cfg(PT, CTemp0, CTemp, InnerSynthFuncs),
+    !:SynthFuncs = [CTemp|InnerSynthFuncs ++ !.SynthFuncs].
+
+% parcall_closure_template(PT, TargetType, N)
+% Builds a closure template which takes a function F of type TargetType (a
+% function type), and N cvars of the types of the first N arguments to
+% TargetType and any remaining required parameters, and calls F.
+% Used for partial application to lifted functions.
+:- pred parcall_closure_template(tables.progtable::in, typeval::in,
+    int::in, string::out, list(function)::in, list(function)::out).
+parcall_closure_template(PT, TargetType, N, Name, !SynthFuncs) :-
+    CTemp0 = function(Name, CVars, Params, RetType, Varset, TDVars, Rigids,
+                      Body, Ctx),
+    Name = "ct:ty:" ++ type_to_identifier(TargetType) ++ ":" ++ string(N),
+    (
+        TargetType = types.app(types.functype, ArgRetTypes),
+        list.split_last(ArgRetTypes, ArgTypes_, RetType_)
+    ->
+        ArgTypes = ArgTypes_, RetType = RetType_
+    ;
+        error("parcall_closure_template: Parcall to non-function type")
+    ),
+    % Give a name to each argument
+    list.map_foldl(pred(Ty::in, {"p_" ++ string(I), Ty}::out, I::in, I+1::out)
+                    is det, ArgTypes, ArgNameTypes, 1, _),
+    TargetName = "f",
+    TargetNameType = {"f", TargetType},
+    % Split ArgTypes into N CVars and remaining Params
+    ( list.split_list(N, ArgNameTypes, YesCVars, YesParams) ->
+        % Prepend the first cvar, which is the function object itself
+        CVars = yes([TargetNameType|YesCVars]),
+        Params = yes(YesParams)
+    ;
+        error("parcall_closure_template: N > number of params")
+    ),
+    % The varset can be empty (no variables are named or bound)
+    Varset = varset.init,
+    TDVars = [],
+    % All type variables in TargetType are rigids in this closure template
+    Rigids = types.vars(TargetType),
+    Ctx = context.blank_context,
+
+    % Build the body:
+    %   return f(*ArgNames)
+    ArgNames = map(func({Nm,Ty}) = expr(varref(svname(Nm)), yes(Ty)),
+                   ArgNameTypes),
+    RetExpr = expr(app(expr(varref(svname(TargetName)), yes(TargetType)),
+                       ArgNames),
+                   yes(RetType)),
+    Body = func_body_ast([], [compound_stmt(return(RetExpr), Ctx)]),
+
+    % Compile it into CFG form
+    % Note: InnerSynthFuncs should be empty, but if there are any we handle it
+    func_to_cfg(PT, CTemp0, CTemp, InnerSynthFuncs),
+    !:SynthFuncs = [CTemp|InnerSynthFuncs ++ !.SynthFuncs].
+
+% Convert a Mars type to a string which uniquely identifies that type and is a
+% valid Mars identifier (beginning with a lowercase letter, and allowed to
+% contain semicolons).
+% Used for generating closure template names.
+% Note that this does not use a varset; any type variables are expected to be
+% unbound and their names will be normalised.
+:- func type_to_identifier(typeval) = string.
+type_to_identifier(Type) = Name :-
+    % We use an unfriendly syntax to ensure that the result is an unambiguous
+    % identifier. We assume that all constant type names have a fixed arity,
+    % except for function arrow types.
+    % Constant types are prefixed with c and suffixed with ;.
+    % The function arrow type (->) consist of an f followed by the arity of
+    %   the type (note: this is one more than the arity of the function; a
+    %   function that takes 2 arguments has type arity 3).
+    %   Functions not used in applications are just written as f.
+    % Type variables consist of a v followed by a non-negative integer
+    %   identifying the variable.
+    % Type application concatenates all arguments, then the type function
+    %   (reverse-polish notation).
+    % Examples:
+    %   Mars Type               Encoded type name
+    %   Int                     cInt;
+    %   ->                      f       (function arrow type, non-application)
+    %   -> :: (*, *, *) -> *    f3      (function of 2 arguments)
+    %   c                       v2      (third available type variable)
+    %   Array(Int)              cInt;cArray;
+    %   a -> b                  v0v1f2
+    %   (a, List(a)) -> List(a) v0v0cList;v0cList;f3
+    ( Type = types.const(TyName) ->
+        Name = "c" ++ TyName ++ ";"
+    ; Type = types.functype ->
+        Name = "f"
+    ; Type = types.variable(Var) ->
+        Name = "v" ++ string(term.var_id(Var):int)
+    ; Type = types.app(Fun, Args) ->
+        ( Fun = types.functype ->
+            % Special case for function used in application
+            FunName = "f" ++ string(length(Args):int)
+        ;
+            FunName = type_to_identifier(Fun)
+        ),
+        ArgNames = map(type_to_identifier, Args),
+        Name = string.append_list(ArgNames) ++ FunName
+    ;
+        error("ast_cfg.type_to_identifier: Invalid type")
+    ).
+
+remove_dup_funcs(Funcs) = FilteredFuncs :-
+    list.map_foldl((pred(F::in, MayF::out, Seen0::in, Seen::out) is det :-
+            ( map.insert(Seen0, F^func_name, unit, Seen_) ->
+                % First occurence of the function name -- keep
+                Seen = Seen_,
+                MayF = yes(F)
+            ;
+                % Already seen -- drop this occurence
+                Seen = Seen0,
+                MayF = no
+            )
+        ), Funcs, MaybeFuncs, map.init, _),
+    list.filter_map(pred(yes(F)::in, F::out) is semidet,
+        MaybeFuncs, FilteredFuncs).

=== modified file 'src/builtins.m'
--- src/builtins.m	2011-02-16 06:00:19 +0000
+++ src/builtins.m	2011-05-11 05:12:31 +0000
@@ -107,7 +107,8 @@
 % Comparison %
 
 :- func func_eq = function.
-func_eq = function("eq", yes([{"x", types.variable(A)},
+func_eq = function("eq", no,
+                         yes([{"x", types.variable(A)},
                               {"y", types.variable(A)}]),
                            types.const("Int"),
                            Varset, [A], [A],
@@ -116,7 +117,7 @@
     varset.new_named_var(varset.init, "a", A, Varset).
 
 :- func func_impure_is = function.
-func_impure_is = function("__impure_is",
+func_impure_is = function("__impure_is", no,
                             yes([{"x", types.variable(A)},
                                  {"y", types.variable(A)}]),
                            types.const("Int"),
@@ -126,7 +127,8 @@
     varset.new_named_var(varset.init, "a", A, Varset).
 
 :- func func_cmp = function.
-func_cmp = function("cmp", yes([{"x", types.const("Int")},
+func_cmp = function("cmp", no,
+                           yes([{"x", types.const("Int")},
                                 {"y", types.const("Int")}]),
                             types.const("Int"),
                             varset.init, [], [],
@@ -136,7 +138,8 @@
 % Arithmetic %
 
 :- func func_add = function.
-func_add = function("add", yes([{"x", types.const("Int")},
+func_add = function("add", no,
+                           yes([{"x", types.const("Int")},
                                 {"y", types.const("Int")}]),
                            types.const("Int"),
                            varset.init, [], [],
@@ -144,7 +147,8 @@
                            ctx).
 
 :- func func_sub = function.
-func_sub = function("sub", yes([{"x", types.const("Int")},
+func_sub = function("sub", no,
+                           yes([{"x", types.const("Int")},
                                 {"y", types.const("Int")}]),
                            types.const("Int"),
                            varset.init, [], [],
@@ -152,7 +156,8 @@
                            ctx).
 
 :- func func_mul = function.
-func_mul = function("mul", yes([{"x", types.const("Int")},
+func_mul = function("mul", no,
+                           yes([{"x", types.const("Int")},
                                 {"y", types.const("Int")}]),
                            types.const("Int"),
                            varset.init, [], [],
@@ -160,7 +165,8 @@
                            ctx).
 
 :- func func_div = function.
-func_div = function("div", yes([{"x", types.const("Int")},
+func_div = function("div", no,
+                           yes([{"x", types.const("Int")},
                                 {"y", types.const("Int")}]),
                            types.const("Int"),
                            varset.init, [], [],
@@ -168,7 +174,8 @@
                            ctx).
 
 :- func func_mod = function.
-func_mod = function("mod", yes([{"x", types.const("Int")},
+func_mod = function("mod", no,
+                           yes([{"x", types.const("Int")},
                                 {"y", types.const("Int")}]),
                            types.const("Int"),
                            varset.init, [], [],
@@ -178,7 +185,7 @@
 % Array %
 
 :- func func_array = function.
-func_array = function("array",
+func_array = function("array", no,
                            yes([{"length", types.const("Int")},
                                 {"default", types.variable(A)}]),
                            types.app(types.const("Array"),
@@ -189,7 +196,7 @@
     varset.new_named_var(varset.init, "a", A, Varset).
 
 :- func func_array_ref = function.
-func_array_ref = function("array_ref",
+func_array_ref = function("array_ref", no,
                            yes([{"array", types.app(types.const("Array"),
                                                     [types.variable(A)])},
                                 {"index", types.const("Int")}]),
@@ -200,7 +207,7 @@
     varset.new_named_var(varset.init, "a", A, Varset).
 
 :- func func_impure_array_set = function.
-func_impure_array_set = function("__impure_array_set",
+func_impure_array_set = function("__impure_array_set", no,
                            yes([{"array", types.app(types.const("Array"),
                                                     [types.variable(A)])},
                                 {"index", types.const("Int")},
@@ -213,7 +220,7 @@
     varset.new_named_var(varset.init, "a", A, Varset).
 
 :- func func_array_replace = function.
-func_array_replace = function("array_replace",
+func_array_replace = function("array_replace", no,
                            yes([{"array", types.app(types.const("Array"),
                                                     [types.variable(A)])},
                                 {"index", types.const("Int")},
@@ -226,7 +233,7 @@
     varset.new_named_var(varset.init, "a", A, Varset).
 
 :- func func_array_length = function.
-func_array_length = function("array_length",
+func_array_length = function("array_length", no,
                            yes([{"array", types.app(types.const("Array"),
                                                     [types.variable(A)])}]),
                            types.const("Int"),
@@ -236,7 +243,7 @@
     varset.new_named_var(varset.init, "a", A, Varset).
 
 :- func func_impure_array_append = function.
-func_impure_array_append = function("__impure_array_append",
+func_impure_array_append = function("__impure_array_append", no,
                            yes([{"array", types.app(types.const("Array"),
                                                     [types.variable(A)])},
                             {"value", types.variable(A)}]),
@@ -248,7 +255,7 @@
     varset.new_named_var(varset.init, "a", A, Varset).
 
 :- func func_impure_array_extend = function.
-func_impure_array_extend = function("__impure_array_extend",
+func_impure_array_extend = function("__impure_array_extend", no,
                            yes([{"array", types.app(types.const("Array"),
                                                     [types.variable(A)])},
                                 {"values", types.app(
@@ -262,7 +269,7 @@
     varset.new_named_var(varset.init, "a", A, Varset).
 
 :- func func_array_add = function.
-func_array_add = function("array_add",
+func_array_add = function("array_add", no,
                            yes([{"array", types.app(types.const("Array"),
                                                     [types.variable(A)])},
                                 {"value", types.variable(A)}]),
@@ -273,7 +280,7 @@
     varset.new_named_var(varset.init, "a", A, Varset).
 
 :- func func_array_concat = function.
-func_array_concat = function("array_concat",
+func_array_concat = function("array_concat", no,
                            yes([{"array1", types.app(types.const("Array"),
                                                      [types.variable(A)])},
                                 {"array2", types.app(
@@ -286,7 +293,7 @@
     varset.new_named_var(varset.init, "a", A, Varset).
 
 :- func func_impure_array_delete = function.
-func_impure_array_delete = function("__impure_array_delete",
+func_impure_array_delete = function("__impure_array_delete", no,
                            yes([{"array", types.app(types.const("Array"),
                                                     [types.variable(A)])},
                                 {"index", types.const("Int")}]),
@@ -298,7 +305,7 @@
     varset.new_named_var(varset.init, "a", A, Varset).
 
 :- func func_array_remove = function.
-func_array_remove = function("array_remove",
+func_array_remove = function("array_remove", no,
                            yes([{"array", types.app(types.const("Array"),
                                                     [types.variable(A)])},
                                 {"index", types.const("Int")}]),
@@ -312,7 +319,7 @@
 % IO %
 
 :- func func_put_char = function.
-func_put_char = function("put_char",
+func_put_char = function("put_char", no,
                            yes([{"c", types.const("Int")}]),
                            types.const("Int"),
                            varset.init, [], [],
@@ -320,7 +327,7 @@
                            ctx).
 
 :- func func_get_char = function.
-func_get_char = function("get_char",
+func_get_char = function("get_char", no,
                            yes([]),
                            types.const("Int"),
                            varset.init, [], [],
@@ -328,7 +335,7 @@
                            ctx).
 
 :- func func_get_env = function.
-func_get_env = function("get_env",
+func_get_env = function("get_env", no,
                            yes([{"name", types.app(types.const("Array"),
                                                    [types.const("Int")])}]),
                            types.app(types.const("Array"),
@@ -340,7 +347,8 @@
 % Miscellaneous %
 
 :- func func_show = function.
-func_show = function("show", yes([{"x", types.variable(A)}]),
+func_show = function("show", no,
+                           yes([{"x", types.variable(A)}]),
                            types.app(types.const("Array"),
                                      [types.const("Int")]),
                            Varset, [A], [A],
@@ -349,7 +357,7 @@
     varset.new_named_var(varset.init, "a", A, Varset).
 
 :- func func_error = function.
-func_error = function("error",
+func_error = function("error", no,
                            yes([{"msg", types.app(types.const("Array"),
                                                   [types.const("Int")])}]),
                            types.variable(A),

=== modified file 'src/callgraph.m'
--- src/callgraph.m	2011-04-19 08:42:16 +0000
+++ src/callgraph.m	2011-05-11 05:12:31 +0000
@@ -224,8 +224,8 @@
 
 :- pred instr_callee(instr_::in, string::out) is semidet.
 instr_callee(ld_cgc(_, Callee), Callee).
+instr_callee(new_closure(_, Callee, _), Callee).
 instr_callee(call_global(_, Callee, _), Callee).
-instr_callee(parcall_global(_, Callee, _), Callee).
 
 % -------------------------------------------------------------------------- %
 % Strongly connected components / topological sorting

=== modified file 'src/executor.m'
--- src/executor.m	2011-01-31 09:01:36 +0000
+++ src/executor.m	2011-05-11 05:12:31 +0000
@@ -65,6 +65,11 @@
     pred is_thunk(progtable::in, E::in, string::in, bool::out, io::di, io::uo)
         is det,
 
+    % Insert a new function into the runtime environment.
+    % Behaviour is undefined if the function already exists.
+    pred add_function(progtable::in, function::in, E::in, E::out,
+        io::di, io::uo) is det,
+
     % Executes an instruction, updating the executor environment as a result.
     % Also threads IO, because computations (in Mars) may modify state or have
     % other side-effects.
@@ -132,6 +137,7 @@
         var_string(univ_executor_value(Env), Varname, Str, !IO),
     var_int(E, Varname, Int, !IO) :- var_int(E, Varname, Int, !IO),
     is_thunk(PT, E, Varname, Bool, !IO) :- is_thunk(PT, E, Varname, Bool,!IO),
+    add_function(PT, F, !E, !IO) :- add_function(PT, F, !E, !IO),
     exec_instr(PT, LT, Instr, E0, univ_executor(E), !IO) :-
         exec_instr(PT, LT, Instr, univ_executor_value(E0), E, !IO)
 ].

=== modified file 'src/interactive.m'
--- src/interactive.m	2011-02-17 07:50:58 +0000
+++ src/interactive.m	2011-05-11 05:12:31 +0000
@@ -384,17 +384,30 @@
                         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, !.State^st_aststate,
-            NewASTState0),
+            ShowExpr, VarName, Instrs0, Types_Raw, SynthFuncs0,
+            !.State^st_aststate, NewASTState0),
         % Return the name of the temporary
         Result = yes(VarName)
     ;
         % Convert the statement into executable (low-level) instructions
         ast_cfg.basic_stmt_to_instrs(!.State^st_progtable,
-            !.State^st_localvarset, Stmt, Instrs0, Types_Raw,
+            !.State^st_localvarset, Stmt, Instrs0, Types_Raw, SynthFuncs0,
             !.State^st_aststate, NewASTState0),
         Result = no
     ),
+    % Load the SynthFuncs into the program tables and executor environment
+    list.filter((pred(F::in) is semidet :-
+            \+ tables.lookup_function(!.State^st_progtable, F^func_name, _)
+        ), SynthFuncs0, SynthFuncs),
+    list.foldl(tables.update_progtable_function,
+        ast_cfg.remove_dup_funcs(SynthFuncs), !.State^st_progtable, PT),
+    list.foldl(tables.update_progtable_function,
+        ast_cfg.remove_dup_funcs(SynthFuncs), !.State^st_progtable_aug,PTAug),
+    list.foldl2(executor.add_function(PT), SynthFuncs,
+                !.State^st_env, NewEnv1, !IO),
+    !State^st_progtable := PT,
+    !State^st_progtable_aug := PTAug,
+    !State^st_env := NewEnv1,
     % Dereference all the types
     map.map_values_only(types.deref(!.State^st_localvarset), Types_Raw,Types),
     % State^st_localtable has already been updated after typechecking.

=== modified file 'src/interpret.m'
--- src/interpret.m	2011-04-20 03:34:02 +0000
+++ src/interpret.m	2011-05-11 05:12:31 +0000
@@ -78,6 +78,7 @@
     pred(var_string/5) is interpret.var_string,
     pred(var_int/5) is interpret.var_int,
     pred(is_thunk/6) is interpret.is_thunk,
+    pred(add_function/6) is interpret.add_function,
     pred(exec_instr/7) is interpret.exec_instr
 ].
 
@@ -298,39 +299,37 @@
 % Converts a function to its string representation for debugging purposes
 % (inside angle brackets, for the output of 'show').
 :- func show_func(runtime_func) = string.
-show_func(Func) = "<" ++ IsCurried ++ WhatIs ++ More ++ ">" :-
+show_func(Func) = "<" ++ IsClosure ++ WhatIs ++ ">" :-
     Func = runtime_func(Args, IsThunk, FuncData),
     ( IsThunk = yes ->
         (
-            FuncData = func_user(_, F),
-            WhatIs = "thunk " ++ F ^ func_name
-        ;
-            FuncData = func_ctor(Name, _),
-            WhatIs = "constructor thunk " ++ Name
-        ;
-            FuncData = func_builtin(Name, _),
-            WhatIs = "built-in thunk " ++ Name
+            FuncData = func_user(_, _),
+            WhatIs = "thunk"
+        ;
+            FuncData = func_ctor(_, _),
+            WhatIs = "constructor thunk"
+        ;
+            FuncData = func_builtin(_, _),
+            WhatIs = "built-in thunk"
         )
     ;
         (
-            FuncData = func_user(_, F),
-            WhatIs = "function " ++ F ^ func_name
-        ;
-            FuncData = func_ctor(Name, _),
-            WhatIs = "constructor function " ++ Name
-        ;
-            FuncData = func_builtin(Name, _),
-            WhatIs = "built-in function " ++ Name
+            FuncData = func_user(_, _),
+            WhatIs = "function"
+        ;
+            FuncData = func_ctor(_, _),
+            WhatIs = "constructor function"
+        ;
+            FuncData = func_builtin(_, _),
+            WhatIs = "built-in function"
         )
     ),
     (
         Args = [],
-        IsCurried = "",
-        More = ""
+        IsClosure = ""
     ;
         Args = [_|_],
-        IsCurried = "curried ",
-        More = "(...)"
+        IsClosure = "closure "
     ).
 
 % Get the value of a local string variable from the environment.
@@ -465,6 +464,13 @@
     local_search_det(!.Env, VarName, Value),
     vectorref.add(VectorRef, Value, !IO).
 
+% Insert a new function into the runtime environment.
+:- pred add_function(progtable::in, function::in, env::in, env::out,
+    io::di, io::uo) is det.
+add_function(PT, Func, !Env, !IO) :-
+    func_globalmap(PT, Func^func_name, Func, !.Env^prog_globals, NewGlobals),
+    !Env^prog_globals := NewGlobals.
+
 % Executes an instruction, updating the environment as a result.
 % Also threads IO, because computations (in Mars) may modify state or have
 % other side-effects.
@@ -556,6 +562,13 @@
         error("Interpreter Error: Field reference to something not an ADT")
     ),
     env_assign_local(Dst, Result, !Env).
+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),
+    % 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),
@@ -563,13 +576,6 @@
     % Apply Arg to Func
     apply_vals(FuncVal, ArgVals, Result, !Env, !IO),
     env_assign_local(Dst, Result, !Env).
-exec_instr_(parcall(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),
-    % Curry Args in Func, but do not evaluate
-    partial_apply_vals(FuncVal, ArgVals, Result),
-    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),
@@ -577,13 +583,6 @@
     % Apply Arg to Ctor
     apply_vals(CtorVal, ArgVals, Result, !Env, !IO),
     env_assign_local(Dst, Result, !Env).
-exec_instr_(parcall_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),
-    % Curry Args in Ctor, but do not evaluate
-    partial_apply_vals(CtorVal, ArgVals, Result),
-    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),
@@ -591,13 +590,6 @@
     % Apply Arg to Func
     apply_vals(FuncVal, ArgVals, Result, !Env, !IO),
     env_assign_local(Dst, Result, !Env).
-exec_instr_(parcall_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),
-    % Curry Args in Func, but do not evaluate
-    partial_apply_vals(FuncVal, ArgVals, Result),
-    env_assign_local(Dst, Result, !Env).
 
 % field_check_ctor(Ctor, ObjCtor) checks whether two constructor names
 % (presumably one from an instruction and one from an object) match.
@@ -643,14 +635,19 @@
     Body = Func ^ func_body,
     ( Body = func_body_cfg(_Decls, CFG) ->
         % Create a new local varmap, with the arguments
+        CVars = Func ^ func_cvars,
+        (
+            CVars = no, YesCVars = []
+        ;
+            CVars = yes(YesCVars)
+        ),
         Params = Func ^ func_params,
         (
-            Params = no,
-            InitVarMap = varmap_init
+            Params = no, YesParams = []
         ;
-            Params = yes(YesParams),
-            bind_args(YesParams, Args, varmap_init, InitVarMap)
+            Params = yes(YesParams)
         ),
+        bind_args(YesCVars ++ YesParams, Args, varmap_init, InitVarMap),
         % Backup locals and initialise a new local table
         LocalsBackup = !.Env ^ prog_locals,
         !Env ^ prog_locals := InitVarMap,

=== modified file 'src/ir.m'
--- src/ir.m	2011-04-20 03:34:02 +0000
+++ src/ir.m	2011-05-11 05:12:31 +0000
@@ -217,22 +217,17 @@
             % (R, S, C, I) <=> R := S.I
             % Undefined behaviour S was not built by constructor C.
     ;       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))
             % Local function call. (Result, Function, Args).
     ;       call(varname, varname, list(varname))
-            % Partial local function application. (Result, Function, Args).
-    ;       parcall(varname, varname, list(varname))
             % Constructor function call. (Result, Ctor, Args).
             % Ctor is the name of a constructor.
     ;       call_ctor(varname, string, list(varname))
-            % Partial constructor function application. (Result, Ctor, Args).
-            % Ctor is the name of a constructor.
-    ;       parcall_ctor(varname, string, list(varname))
             % Global function call. (Result, Function, Args).
             % Function must be a global function (not a ctor or CGC).
-    ;       call_global(varname, string, list(varname))
-            % Partial global function application. (Result, Function, Args).
-            % Function must be a global function (not a ctor or CGC).
-    ;       parcall_global(varname, string, list(varname)).
+    ;       call_global(varname, string, list(varname)).
 
 % 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
@@ -297,10 +292,13 @@
             % Integer literal. Matches exactly this value.
     ;       case_intlit(integer).
 
-% Top-level definition of a function or computable global constant (CGC).
+% Top-level definition of a function, computable global constant (CGC) or
+% closure template (CT).
 :- type function
     --->    function(
                 func_name     :: string,
+                % The closure variables; 'no' unless this is a CT.
+                func_cvars    :: maybe(list({string, typeval})),
                 % The function parameters, or 'no' for a CGC.
                 % Note: yes([]) is a 0-argument function, while no is a CGC.
                 func_params   :: maybe(list({string, typeval})),
@@ -427,6 +425,12 @@
 % names are used - but then, the Python backend does that anyway).
 :- func varname_to_string_dodgy(varname) = string.
 
+% global_is_ct(PT, Varname) succeeds if Varname names a global variable which
+% is a closure template (function with closure variables). Fails if it is
+% a regular function or a CGC.
+% Aborts if Varname does not name a global variable at all.
+:- pred global_is_ct(tables.progtable::in, string::in) is semidet.
+
 % global_is_cgc(PT, Varname) succeeds if Varname names a global variable which
 % is a computable global constant (function without arguments). Fails if it is
 % a regular function.
@@ -624,6 +628,13 @@
 varname_to_string_dodgy(qvname(BaseName, Qual)) =
     varname_to_string_dodgy(BaseName) ++ "_" ++ string.from_int(Qual).
 
+global_is_ct(PT, Varname) :-
+    ( tables.lookup_function(PT, Varname, Func) ->
+        Func ^ func_cvars = yes(_)  % Can fail
+    ;
+        error(string.format("ir.global_is_ct: %s not a global",[s(Varname)]))
+    ).
+
 global_is_cgc(PT, Varname) :-
     ( tables.lookup_function(PT, Varname, Func) ->
         Func ^ func_params = no     % Can fail

=== modified file 'src/parsem.m'
--- src/parsem.m	2011-02-16 06:00:19 +0000
+++ src/parsem.m	2011-05-11 05:12:31 +0000
@@ -398,7 +398,8 @@
 % Consumes a single function.
 :- pred function(function::out, tokenparser::in, tokenparser::out) is semidet.
 function(
-    function(FuncName, Params, RetType, Varset, [],Rigids, Body, Context)) -->
+    function(FuncName, no, Params, RetType, Varset, [], Rigids, Body,
+             Context)) -->
     some [!Varset, !VarNames] (
         {varset.init(!:Varset)},
         {map.init(!:VarNames)},

=== modified file 'src/pretty.m'
--- src/pretty.m	2011-05-11 04:08:48 +0000
+++ src/pretty.m	2011-05-11 05:12:31 +0000
@@ -412,6 +412,13 @@
     indent(Indent, !IO),
     io.format("%s = %s", [s(ir.varname_to_string_noescape(Dst)),
         s(fieldref_str(Obj, Ctor, Idx))], !IO).
+print_instr_(Indent, new_closure(Dst, Func, Args), !IO) :-
+    indent(Indent, !IO),
+    io.write_string(ir.varname_to_string_noescape(Dst), !IO),
+    io.write_string(" = @", !IO),
+    ArgsStr = string.join_list(", ",
+        list.map(ir.varname_to_string_noescape, Args)),
+    io.write_string(Func ++ "{" ++ ArgsStr ++ "}", !IO).
 print_instr_(Indent, call(Dst, Func, Args), !IO) :-
     indent(Indent, !IO),
     io.write_string(ir.varname_to_string_noescape(Dst), !IO),
@@ -420,14 +427,6 @@
         list.map(ir.varname_to_string_noescape, Args)),
     io.write_string(
         ir.varname_to_string_noescape(Func) ++ "(" ++ ArgsStr ++ ")", !IO).
-print_instr_(Indent, parcall(Dst, Func, Args), !IO) :-
-    indent(Indent, !IO),
-    io.write_string(ir.varname_to_string_noescape(Dst), !IO),
-    io.write_string(" = ", !IO),
-    ArgsStr = string.join_list(", ",
-        list.map(ir.varname_to_string_noescape, Args) ++ ["..."]),
-    io.write_string(
-        ir.varname_to_string_noescape(Func) ++ "(" ++ ArgsStr ++ ")", !IO).
 print_instr_(Indent, call_ctor(Dst, Ctor, Args), !IO) :-
     indent(Indent, !IO),
     io.write_string(ir.varname_to_string_noescape(Dst), !IO),
@@ -435,13 +434,6 @@
     ArgsStr = string.join_list(", ",
         list.map(ir.varname_to_string_noescape, Args)),
     io.write_string(Ctor ++ "(" ++ ArgsStr ++ ")", !IO).
-print_instr_(Indent, parcall_ctor(Dst, Ctor, Args), !IO) :-
-    indent(Indent, !IO),
-    io.write_string(ir.varname_to_string_noescape(Dst), !IO),
-    io.write_string(" = ", !IO),
-    ArgsStr = string.join_list(", ",
-        list.map(ir.varname_to_string_noescape, Args) ++ ["..."]),
-    io.write_string(Ctor ++ "(" ++ ArgsStr ++ ")", !IO).
 print_instr_(Indent, call_global(Dst, Func, Args), !IO) :-
     indent(Indent, !IO),
     io.write_string(ir.varname_to_string_noescape(Dst), !IO),
@@ -449,13 +441,6 @@
     ArgsStr = string.join_list(", ",
         list.map(ir.varname_to_string_noescape, Args)),
     io.write_string(Func ++ "(" ++ ArgsStr ++ ")", !IO).
-print_instr_(Indent, parcall_global(Dst, Func, Args), !IO) :-
-    indent(Indent, !IO),
-    io.write_string(ir.varname_to_string_noescape(Dst), !IO),
-    io.write_string(" = @", !IO),
-    ArgsStr = string.join_list(", ",
-        list.map(ir.varname_to_string_noescape, Args) ++ ["..."]),
-    io.write_string(Func ++ "(" ++ ArgsStr ++ ")", !IO).
 
 :- func fieldref_str(varname, string, int) = string.
 fieldref_str(Obj, Ctor, Idx) = string.format("%s.[%s: %d]",
@@ -542,6 +527,16 @@
 print_function_head(Func, !IO) :-
     io.write_string(Func^func_name, !IO),
     (
+        Func^func_cvars = no
+    ;
+        Func^func_cvars = yes(CVars),
+        io.write_string("{", !IO),
+        io.write_string(string.join_list(", ",
+                            list.map(string_param(Func^func_varset), CVars)),
+                        !IO),
+        io.write_string("}", !IO)
+    ),
+    (
         Func^func_params = no
     ;
         Func^func_params = yes(Params),

=== modified file 'src/tables.m'
--- src/tables.m	2011-02-14 12:48:18 +0000
+++ src/tables.m	2011-05-11 05:12:31 +0000
@@ -338,6 +338,13 @@
 
 build_localtable(Func, !Table) :-
     (
+        Func^func_cvars = no
+    ;
+        Func^func_cvars = yes(CVars),
+        list.foldl(add_to_localtable_string(Func, "closure-var"), CVars,
+            !Table)
+    ),
+    (
         Func^func_params = no
     ;
         Func^func_params = yes(Params),

=== modified file 'src/typecheck.m'
--- src/typecheck.m	2011-01-19 07:44:29 +0000
+++ src/typecheck.m	2011-05-11 05:12:31 +0000
@@ -227,6 +227,12 @@
         VarName = svname(UnqualVarName),
         tables.lookup_function(PT, UnqualVarName, Func)
     ->
+        ( ir.global_is_ct(PT, UnqualVarName) ->
+            context.throw_error("Reference to closure template: "
+                ++ UnqualVarName, Ctx)
+        ;
+            true
+        ),
         % Found in global function table - get its type and varset
         function_type(Func, FuncVarset, Type0),
         % Augment our own varset with this function's varset and
@@ -238,6 +244,12 @@
     ).
 expr_type_(Ctx, PT, _LT, !Varset, _Rigids, E@globalref(VarName), E, Type) :-
     ( tables.lookup_function(PT, VarName, Func) ->
+        ( ir.global_is_ct(PT, VarName) ->
+            context.throw_error("Reference to closure template: " ++ VarName,
+                                Ctx)
+        ;
+            true
+        ),
         % Found in global function table - get its type and varset
         function_type(Func, FuncVarset, Type0),
         % Augment our own varset with this function's varset and
@@ -713,6 +725,13 @@
     Ctx = !.Func^func_context,
     % Type/kind check the params and ret type - must all be of kind *
     (
+        !.Func^func_cvars = no
+    ;
+        !.Func^func_cvars = yes(CVars),
+        check_types_star(Ctx, PT, !.Func^func_varset,
+                         list.map(func({_,B})=B, CVars))
+    ),
+    (
         !.Func^func_params = no
     ;
         !.Func^func_params = yes(Params),
@@ -795,13 +814,20 @@
     !.Func^func_body = func_body_ast(Decls0, Stmts),
     Varset0 = !.Func^func_varset,
     (
+        !.Func^func_cvars = no,
+        CVars = []
+    ;
+        !.Func^func_cvars = yes(FuncCVars),
+        CVars = map(func({N,_}) = svname(N), FuncCVars)
+    ),
+    (
         !.Func^func_params = no,
         Params = []
     ;
         !.Func^func_params = yes(FuncParams),
         Params = map(func({N,_}) = svname(N), FuncParams)
     ),
-    DeclsSet = set(assoc_list.keys(Decls0) ++ Params),
+    DeclsSet = set(assoc_list.keys(Decls0) ++ CVars ++ Params),
     % Get the set of all variables bound in the function's body
     BoundVars0 = remove_dups(boundvars_stmts(Stmts)),
     % ... which are not already explicitly declared

=== modified file 'src/typedict.m'
--- src/typedict.m	2011-04-19 08:42:16 +0000
+++ src/typedict.m	2011-05-11 05:12:31 +0000
@@ -163,12 +163,42 @@
         Arities = set(ArityList)
     ).
 
-:- func to_cfg(progtable, function) = function.
-to_cfg(PT, FuncAST) = FuncCFG :-
+% Updates PTAug, adding any new synthetic functions.
+:- pred to_cfg(progtable::in, function::in, function::out,
+    progtable::in, progtable::out, list(function)::in, list(function)::out)
+    is det.
+to_cfg(PT, FuncAST, FuncCFG, !PTAug, !SynthFuncs) :-
+    to_cfg(PT, _, FuncAST, FuncCFG, !PTAug, !SynthFuncs).
+% Also updates PT; this can be ignored long-term, but augment_cfg() requires
+% the PT to have the synthfuncs.
+:- pred to_cfg(progtable::in, progtable::out, function::in, function::out,
+    progtable::in, progtable::out, list(function)::in, list(function)::out)
+    is det.
+to_cfg(!PT, FuncAST, FuncCFG, !PTAug, !SynthFuncs) :-
+    typecheck.add_implicit_decls(FuncAST, FuncAST_Decls),
+    tables.build_localtable(FuncAST_Decls, LT),
+    typecheck.check_function(!.PT, LT, FuncAST_Decls, FuncAST_Checked),
+    ast_cfg.func_to_cfg(!.PT, FuncAST_Checked, FuncCFG, SynthFuncs),
+    list.foldl(update_progtable_function, SynthFuncs, !PT),
+    list.foldl(update_progtable_function, SynthFuncs, !PTAug),
+    !:SynthFuncs = SynthFuncs ++ !.SynthFuncs.
+
+% Same as to_cfg, but augment function and all synth funcs
+% Updates PTAug, adding any new synthetic functions.
+:- pred augment_cfg(progtable::in, function::in, function::out,
+    progtable::in, progtable::out, list(function)::in, list(function)::out)
+    is det.
+augment_cfg(PT, FuncAST, FuncCFGAug, !PTAug, !SynthFuncs) :-
     typecheck.add_implicit_decls(FuncAST, FuncAST_Decls),
     tables.build_localtable(FuncAST_Decls, LT),
     typecheck.check_function(PT, LT, FuncAST_Decls, FuncAST_Checked),
-    ast_cfg.func_to_cfg(PT, FuncAST_Checked, FuncCFG).
+    ast_cfg.func_to_cfg(PT, FuncAST_Checked, FuncCFG, SynthFuncs0),
+    % Augment the new synthetic functions
+    SynthFuncs1 = list.map(augment(PT, !.PTAug), SynthFuncs0),
+    list.foldl(update_progtable_function, SynthFuncs0, PT, PTWithSynth),
+    list.foldl(update_progtable_function, SynthFuncs1, !PTAug),
+    !:SynthFuncs = SynthFuncs1 ++ !.SynthFuncs,
+    FuncCFGAug = augment(PTWithSynth, !.PTAug, FuncCFG).
 
 :- func augment(progtable, progtable, function) = function.
 augment(PT, PTAug, Func0) = Func :-
@@ -179,10 +209,6 @@
     % Should never happen:
     require(set.empty(ReqVars), "augment: Rigid missing from TDVars").
 
-% augment_cfg: Apply AST->CFG then augment.
-:- func augment_cfg(progtable, progtable, function) = function.
-augment_cfg(PT, PTAug, Func) = augment(PT, PTAug, to_cfg(PT, Func)).
-
 % Generate the standard boilerplate code for type-dictionary-augmented
 % programs. Return it as a list of new program nodes.
 % The argument is the set of all function arities in the program (each of
@@ -240,29 +266,32 @@
         error("generate_boilerplate: :Dict not in progtable")
     ),
     % CFGise, augment and re-add user-defined functions, CGCs and dicts
-    some [!PTAug] (
+    some [!PTAug, !SynthFuncs] (
         !:PTAug = !.PT,
+        !:SynthFuncs = [],
         foldl(update_progtable_function, FieldFuncs, !PTAug),
-        DictInt = augment_cfg(!.PT, !.PTAug, dict_int),
+        augment_cfg(!.PT, dict_int, DictInt, !PTAug, !SynthFuncs),
         update_progtable_function(DictInt, !PTAug),
-        ShowArray = augment_cfg(!.PT, !.PTAug, show_array),
+        augment_cfg(!.PT, show_array, ShowArray, !PTAug, !SynthFuncs),
         update_progtable_function(ShowArray, !PTAug),
-        EqArray = augment_cfg(!.PT, !.PTAug, eq_array),
+        augment_cfg(!.PT, eq_array, EqArray, !PTAug, !SynthFuncs),
         update_progtable_function(EqArray, !PTAug),
-        DictArray = augment_cfg(!.PT, !.PTAug, dict_array),
+        augment_cfg(!.PT, dict_array, DictArray, !PTAug, !SynthFuncs),
         update_progtable_function(DictArray, !PTAug),
-        EqFunc = to_cfg(!.PT, eq_func),
+        to_cfg(!.PT, eq_func, EqFunc, !PTAug, !SynthFuncs),
         update_progtable_function(EqFunc, !PTAug),
         PT_DF = !.PT,
-        DictFuncsA = list.map(to_cfg(PT_DF), DictFuncs),
+        list.map_foldl2(to_cfg(PT_DF), DictFuncs, DictFuncsA, !PTAug,
+                        !SynthFuncs),
         list.foldl(update_progtable_function, DictFuncsA, !PTAug),
-        ShowFree = to_cfg(!.PT, show_free),
+        to_cfg(!.PT, show_free, ShowFree, !PTAug, !SynthFuncs),
         update_progtable_function(ShowFree, !PTAug),
-        EqFree = to_cfg(!.PT, eq_free),
+        to_cfg(!.PT, eq_free, EqFree, !PTAug, !SynthFuncs),
         update_progtable_function(EqFree, !PTAug),
-        DictFree = to_cfg(!.PT, dict_free),
+        to_cfg(!.PT, dict_free, DictFree, !PTAug, !SynthFuncs),
         update_progtable_function(DictFree, !PTAug),
-        PTAug = !.PTAug
+        PTAug = !.PTAug,
+        SynthFuncs = list.reverse(!.SynthFuncs)
     ),
 
     % Now store the user-defined types and functions in the program
@@ -280,7 +309,8 @@
         pfunction(ShowFree),
         pfunction(EqFree),
         pfunction(DictFree)
-    ].
+    % Add the synthetic functions to the program
+    ] ++ list.map(func(F) = pfunction(F), SynthFuncs).
 
 :- func ctx = context.context.
 ctx = context("typedict", 1, 1, stack.init).
@@ -289,7 +319,7 @@
 
 % def builtin show_int :: Int -> Array(Int)
 :- func show_int = function.
-show_int = function("show:Int",
+show_int = function("show:Int", no,
                 yes([{"x", types.const("Int")}]),
                 types.app(types.const("Array"),
                           [types.const("Int")]),
@@ -299,7 +329,7 @@
 
 % def builtin eq_int :: (Int, Int) -> Int
 :- func eq_int = function.
-eq_int = function("eq:Int",
+eq_int = function("eq:Int", no,
                 yes([{"x", types.const("Int")},
                      {"y", types.const("Int")}]),
                 types.const("Int"),
@@ -309,7 +339,7 @@
 
 % def builtin show_func :: (a) -> Array(Int)
 :- func show_func = function.
-show_func = function("show:func",
+show_func = function("show:func", no,
                 yes([{"x", types.variable(A)}]),
                 types.app(types.const("Array"),
                           [types.const("Int")]),
@@ -357,7 +387,7 @@
 
 % def dict:Int :: :Dict(Int) = :Dict(show:Int, eq:Int)
 :- func dict_int = function.
-dict_int = function("dict:Int",
+dict_int = function("dict:Int", no,
                 no,
                 types.app(types.const(":Dict"),
                           [types.const("Int")]),
@@ -385,7 +415,7 @@
 %     res = array_concat(res, "]")
 %     return res
 :- func show_array = function.
-show_array = function("show:Array",
+show_array = function("show:Array", no,
                 yes([{"x", types.app(types.const("Array"),
                                      [types.variable(A)])}]),
                 types.app(types.const("Array"),
@@ -469,7 +499,7 @@
 %        i = add(i, 1)
 %    return 1
 :- func eq_array = function.
-eq_array = function("eq:Array",
+eq_array = function("eq:Array", no,
                 yes([{"x", types.app(types.const("Array"),
                                      [types.variable(A)])},
                      {"y", types.app(types.const("Array"),
@@ -529,7 +559,7 @@
 % def dict:Array :: :Dict(Array(a)):
 %     return :Dict(show_Array, eq_Array)
 :- func dict_array = function.
-dict_array = function("dict:Array",
+dict_array = function("dict:Array", no,
                 no,
                 types.app(types.const(":Dict"),
                           [types.app(types.const("Array"),
@@ -548,7 +578,7 @@
 % def eq:func(x :: a, y :: a) :: Int:
 %     return error("Functions cannot be compared for equality")
 :- func eq_func = function.
-eq_func = function("eq:func",
+eq_func = function("eq:func", no,
                 yes([{"x", types.variable(A)},
                      {"y", types.variable(A)}]),
                 types.const("Int"),
@@ -568,7 +598,7 @@
 %       :: :Dict((a, ..., y) -> z):
 %     return :Dict(show:func, eq:func)
 :- func dict_func(int) = function.
-dict_func(Arity) = function("dict:func:" ++ string(Arity),
+dict_func(Arity) = function("dict:func:" ++ string(Arity), no,
                 yes(list.map_corresponding(
                     func(N, V) = {"dict:t_" ++ string(N),
                         types.app(types.const(":Dict"), [types.variable(V)])},
@@ -594,7 +624,7 @@
 % def show:free(x :: a) :: Array(Int):
 %     return error("eq:free")
 :- func show_free = function.
-show_free = function("show:free",
+show_free = function("show:free", no,
                 yes([{"x", types.variable(A)}]),
                 types.app(types.const("Array"), [types.const("Int")]),
                 Varset, [], [A],
@@ -610,7 +640,7 @@
 % def eq:free(x :: a, y :: a) :: Int:
 %     return error("eq:free")
 :- func eq_free = function.
-eq_free = function("eq:free",
+eq_free = function("eq:free", no,
                 yes([{"x", types.variable(A)},
                      {"y", types.variable(A)}]),
                 types.const("Int"),
@@ -627,7 +657,7 @@
 % def dict:free :: :Dict(a):
 %     return :Dict(show:free, eq:free)
 :- func dict_free = function.
-dict_free = function("dict:free",
+dict_free = function("dict:free", no,
                 no,
                 types.app(types.const(":Dict"),
                           [types.variable(A)]),
@@ -693,10 +723,17 @@
     ),
     % Now generate the augmented versions. We do not insert them into
     % the PT (since we are generating an unaugmented PT).
-    ShowA = augment_cfg(PT, PTAug, Show),
-    EqA = augment_cfg(PT, PTAug, Eq),
-    DictA = augment_cfg(PT, PTAug, Dict),
-    ShowEqDict = [pfunction(ShowA), pfunction(EqA), pfunction(DictA)].
+    some [!SynthFuncs, !PTAug] (
+        !:SynthFuncs = [],
+        !:PTAug = PTAug,
+        augment_cfg(PT, Show, ShowA, !PTAug, !SynthFuncs),
+        augment_cfg(PT, Eq, EqA, !PTAug, !SynthFuncs),
+        augment_cfg(PT, Dict, DictA, !PTAug, !SynthFuncs),
+        _ = !.PTAug,        % Not needed
+        SynthFuncNodes = map(func(F) = pfunction(F), !.SynthFuncs)
+    ),
+    ShowEqDict = [pfunction(ShowA), pfunction(EqA), pfunction(DictA)]
+        ++ SynthFuncNodes.
 
 % Field names as used in our patterns in user-defined type functions
 % String is an optional prefix (use "" for nothing).
@@ -737,7 +774,7 @@
 %         case CtorN(f_CtorN_0, f_CtorN_1, ..., f_CtorN_n):
 %             ...
 :- func generate_user_show(typedef) = function.
-generate_user_show(Typedef) = function("show:" ++ Typedef^typedef_name,
+generate_user_show(Typedef) = function("show:" ++ Typedef^typedef_name, no,
     yes([{"x", ObjType}]),
     types.app(types.const("Array"),
               [types.const("Int")]),
@@ -822,7 +859,7 @@
 %             ...
 %     return 1
 :- func generate_user_eq(typedef) = function.
-generate_user_eq(Typedef) = function("eq:" ++ Typedef^typedef_name,
+generate_user_eq(Typedef) = function("eq:" ++ Typedef^typedef_name, no,
     yes([{"x", ObjType}, {"y", ObjType}]),
     types.const("Int"),
     Varset, [], varset.vars(Varset),
@@ -869,7 +906,7 @@
     ).
 
 :- func generate_user_dict(typedef) = function.
-generate_user_dict(Typedef) = function("dict:" ++ Typedef^typedef_name,
+generate_user_dict(Typedef) = function("dict:" ++ Typedef^typedef_name, no,
     no,
     types.app(types.const(":Dict"), [ObjType]),
     Varset, [], varset.vars(Varset),
@@ -1003,7 +1040,16 @@
                 Name = "dict:" ++ varset.lookup_name(Varset, Var, "t_"),
                 Type = types.app(types.const(":Dict"), [types.variable(Var)])
             ), TypeVars),
-        !Func^func_params := yes(TDArgs ++ Params),
+        (
+            !.Func^func_cvars = yes(CVars),
+            % Closure template. Prepend TDArgs to closure variables.
+            !Func^func_cvars := yes(TDArgs ++ CVars)
+        ;
+            !.Func^func_cvars = no,
+            % Not a closure template (CGC or function).
+            % Prepend TDArgs to regular parameters.
+            !Func^func_params := yes(TDArgs ++ Params)
+        ),
         % Update the local table. Importantly, we need to insert these
         % variables starting from index 1 in the LT (the first argument).
         ( !.Func^func_body = func_body_cfg(LT0, Body) ->
@@ -1083,7 +1129,7 @@
     ( Instr0 = ld_cgc(Dst, Name) ->
         ( tables.lookup_local(!.LT, Dst, DstType) ->
             augment_globalref(PT, PTAug, Varset, Rigids, TDVars, Name,
-                              DstType, TDExprs, !RequiredVars)
+                              DstType, [], TDExprs, !RequiredVars)
         ;
             error("augment_instr_globalrefs: Not in LT: " ++
                 ir.varname_to_string_noescape(Dst))
@@ -1098,6 +1144,30 @@
                 TDArgs, PreInstrs, !LT, !BlockTempCount),
             Instr = call_global(Dst, Name, TDArgs)
         )
+    ; Instr0 = new_closure(Dst, Name, Args) ->
+        ( tables.lookup_local(!.LT, Dst, DstType) ->
+            FuncType = DstType,
+            ( map(tables.lookup_local(!.LT), Args, ArgTypes_) ->
+                ArgTypes = ArgTypes_,
+                ( DstType = types.app(types.functype, _) ->
+                    true
+                ;
+                    error("augment_instr_globalrefs: New-closure to "
+                          ++ "non-function")
+                )
+            ;
+                error("augment_instr_globalrefs: Arg not in LT")
+            )
+        ;
+            error("augment_instr_globalrefs: Not in LT: " ++
+                ir.varname_to_string_noescape(Dst))
+        ),
+        augment_globalref(PT, PTAug, Varset, 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) ->
@@ -1110,9 +1180,9 @@
                 ir.varname_to_string_noescape(Dst))
         ),
         augment_globalref(PT, PTAug, Varset, Rigids, TDVars, Name, FuncType,
-                          TDExprs, !RequiredVars),
+                          [], TDExprs, !RequiredVars),
         ( method_builtin(Name), TDExprs = [TDExpr] ->
-            % ld_func of show or eq -- replace with field access
+            % call to show or eq -- replace with field access
             MethodExpr0 = expr(fieldref(TDExpr, Name), no),
             typecheck.expr_type(blank_context, PTAug, !.LT, Rigids,
                 MethodExpr0, MethodExpr, Varset, _),
@@ -1129,41 +1199,6 @@
                 TDArgs, PreInstrs, !LT, !BlockTempCount),
             Instr = call_global(Dst, Name, TDArgs ++ Args)
         )
-    ; Instr0 = parcall_global(Dst, Name, Args) ->
-        ( tables.lookup_local(!.LT, Dst, DstType) ->
-            ( map(tables.lookup_local(!.LT), Args, ArgTypes) ->
-                ( DstType = types.app(types.functype, RemTypes) ->
-                    FuncType = types.app(types.functype, ArgTypes ++ RemTypes)
-                ;
-                    error("augment_instr_globalrefs: Parcall to non-function")
-                )
-            ;
-                error("augment_instr_globalrefs: Arg not in LT")
-            )
-        ;
-            error("augment_instr_globalrefs: Not in LT: " ++
-                ir.varname_to_string_noescape(Dst))
-        ),
-        augment_globalref(PT, PTAug, Varset, Rigids, TDVars, Name, FuncType,
-                          TDExprs, !RequiredVars),
-        ( method_builtin(Name), TDExprs = [TDExpr] ->
-            % ld_func of show or eq -- replace with field access
-            MethodExpr0 = expr(fieldref(TDExpr, Name), no),
-            typecheck.expr_type(blank_context, PTAug, !.LT, Rigids,
-                MethodExpr0, MethodExpr, Varset, _),
-            generate_expr_code(PTAug, Varset, Rigids, BlockID, [MethodExpr],
-                MethodVars, PreInstrs, !LT, !BlockTempCount),
-            ( MethodVars = [MethodVar] ->
-                Instr = parcall(Dst, MethodVar, Args)
-            ;
-                error("augment_instr_globalrefs: generate_expr_code failed")
-            )
-        ;
-            % parcall_global has the type dicts prepended to its argument list
-            generate_expr_code(PTAug, Varset, Rigids, BlockID, TDExprs,
-                TDArgs, PreInstrs, !LT, !BlockTempCount),
-            Instr = parcall_global(Dst, Name, TDArgs ++ Args)
-        )
     ;
         PreInstrs = [],
         Instr = Instr0
@@ -1180,24 +1215,31 @@
     localtable::in, localtable::out, int::in, int::out) is det.
 generate_expr_code(PT, Varset, _Rigids, BlockID, Exprs, VarNames, Instrs, !LT,
     !BlockTempCount) :-
-    list_map3_foldl(ast_cfg.expr_to_instrs_post_ssa(PT, Varset, BlockID),
-                    Exprs, VarNames, InstrLists, TypeMaps, !BlockTempCount),
+    list_map4_foldl(ast_cfg.expr_to_instrs_post_ssa(PT, Varset, BlockID),
+                    Exprs, VarNames, InstrLists, TypeMaps, SynthFuncses,
+                    !BlockTempCount),
     Instrs = list.condense(InstrLists),
+    ( list.condense(SynthFuncses) : list(function) = [] ->
+        true
+    ;
+        % These references should not include any partial application
+        error("generate_expr_code: Synthetic functions were created")
+    ),
     list.foldl(map.foldl(tables.update_localtable), TypeMaps, !LT).
 
-% augment_globalref(PT, PTAug, Rigids, Name, Type, TDArgs).
+% augment_globalref(PT, PTAug, Rigids, Name, Type, CVTypes, TDArgs).
 % Returns the list of type dictionary actual parameter names to augment onto
 % the front of a reference to the global variable called Name.
 % Rigids are the rigid type variables of the caller (which may not be
 % unified).
 % Type is the "actual" type of the global -- that is, the type of the global
 % with all variables replaced with monomorphic variables local to the caller.
+% CVTypes is similar, but for the types of the actual CVars.
 :- pred augment_globalref(progtable::in, progtable::in, varset::in,
-    list(var)::in, list(var)::in, string::in, typeval::in, list(expr)::out,
-    set(var)::in, set(var)::out)
-    is det.
+    list(var)::in, list(var)::in, string::in, typeval::in, list(typeval)::in,
+    list(expr)::out, set(var)::in, set(var)::out) is det.
 augment_globalref(PT, PTAug, ActualVarset, ActualRigids, ActualTDVars, Name,
-    ActualType, TDArgs, !RequiredVars) :-
+    ActualType0, ActualCVTypes, TDArgs, !RequiredVars) :-
     ( tables.lookup_function(PT, Name, Func_) ->
         Func = Func_
     ;
@@ -1210,13 +1252,41 @@
     ),
     % Found in global function table - get its type and varset
     function_type(Func, FormalVarset, FormalType0),
+    % If this is a CT, pretend it isn't by prepending the actual/formal CT
+    % types onto the actual/formal function types.
+    (
+        Func^func_cvars = yes(FormalCVars),
+        FormalCVTypes = map(func({_,T}) = T, FormalCVars),
+        ( FormalType0 = types.app(types.functype, FArgTypes) ->
+            FormalType1 = types.app(types.functype,
+                                    FormalCVTypes ++ FArgTypes)
+        ;
+            error("augment_globalref: CT, but formal type not a function")
+        ),
+        ( ActualType0 = types.app(types.functype, AArgTypes) ->
+            ActualType = types.app(types.functype,
+                                    ActualCVTypes ++ AArgTypes)
+        ;
+            error("augment_globalref: CT, but actual type not a function")
+        )
+    ;
+        Func^func_cvars = no,
+        (
+            ActualCVTypes = [],
+            FormalType1 = FormalType0,
+            ActualType = ActualType0
+        ;
+            ActualCVTypes = [_|_],
+            error("augment_globalref: ActualCVTypes supplied for non-CT")
+        )
+    ),
     % The list of variables we need to supply type dicts for
     FormalRigids0 = Func^func_rigids,
     % Augment our actual (local) varset with this function's (formal)
     % varset and translate the function's type to refer to the combined
     % varset. Also translate the rigids to the combined varset.
     types.varset_mergeone_rename(FormalVarset, ActualVarset, Varset0,
-        FormalType0, FormalType, FormalRigids0, FormalRigids),
+        FormalType1, FormalType, FormalRigids0, FormalRigids),
     % Translate the function's TDVars (expected type dicts) to the
     % combined varset
     TDVars = list.map(map.lookup(

=== modified file 'src/usedef.m'
--- src/usedef.m	2011-04-20 03:34:02 +0000
+++ src/usedef.m	2011-05-11 05:12:31 +0000
@@ -179,24 +179,18 @@
 instr_use_def_(ld_field(Dst, Obj, _CtorIdxMap, _Msg), Uses, Defs) :-
     set.singleton_set(Uses, Obj),
     set.singleton_set(Defs, Dst).
+instr_use_def_(new_closure(Dst, _Func, Args), Uses, Defs) :-
+    Uses = set(Args),
+    set.singleton_set(Defs, Dst).
 instr_use_def_(call(Dst, Func, Args), Uses, Defs) :-
     Uses = set([Func|Args]),
     set.singleton_set(Defs, Dst).
-instr_use_def_(parcall(Dst, Func, Args), Uses, Defs) :-
-    Uses = set([Func|Args]),
-    set.singleton_set(Defs, Dst).
 instr_use_def_(call_ctor(Dst, _Ctor, Args), Uses, Defs) :-
     Uses = set(Args),
     set.singleton_set(Defs, Dst).
-instr_use_def_(parcall_ctor(Dst, _Ctor, Args), Uses, Defs) :-
-    Uses = set(Args),
-    set.singleton_set(Defs, Dst).
 instr_use_def_(call_global(Dst, _Func, Args), Uses, Defs) :-
     Uses = set(Args),
     set.singleton_set(Defs, Dst).
-instr_use_def_(parcall_global(Dst, _Func, Args), Uses, Defs) :-
-    Uses = set(Args),
-    set.singleton_set(Defs, Dst).
 
 instrs_use_def(Instrs, Uses, Defs) :-
     % Process each instruction, and compute the sets of uses and defs

=== modified file 'src/util.m'
--- src/util.m	2011-02-11 02:41:54 +0000
+++ src/util.m	2011-05-11 05:12:31 +0000
@@ -78,6 +78,12 @@
     out, in, out) is det.
 % Add more modes as required.
 
+:- pred list_map4_foldl(pred(L, M, N, O, P, A, A), list(L), list(M), list(N),
+    list(O), list(P), A, A).
+:- mode list_map4_foldl(pred(in, out, out, out, out, in, out) is det, in, out,
+    out, out, out, in, out) is det.
+% Add more modes as required.
+
 :- pred list_map_foldr(pred(L, M, A, A), list(L), list(M), A, A).
 :- mode list_map_foldr(pred(in, out, in, out) is det, in, out, in, out)
     is det.
@@ -389,6 +395,12 @@
     P(H0, H1, H2, H3, !A),
     list_map3_foldl(P, T0, T1, T2, T3, !A).
 
+list_map4_foldl(_, [], [], [], [], [], !A).
+list_map4_foldl(P, [H0 | T0], [H1 | T1], [H2 | T2], [H3 | T3], [H4 | T4], !A)
+    :-
+    P(H0, H1, H2, H3, H4, !A),
+    list_map4_foldl(P, T0, T1, T2, T3, T4, !A).
+
 list_map_foldr(_, [], [], !A).
 list_map_foldr(P, [H0 | T0], [H | T], !A) :-
     list_map_foldr(P, T0, T, !A),