There are three parts to simplifying functions: moving function values to the heap, calling a function, and returning a value computed by a function to some enclosing workspace.

The first of these steps is very straight forward. Recall from §10.1 that
top-level function declarations are just short hand for naming an
anony-mous function. For example, the following are equivalent ways of
defin-ing^{add1}:

**let** add1 **(x:int) :** **int** **=** x **+** **1** **in**
add1 **(add1** **0)**

and

**let** add1 **=** **fun** **(x:int) :** **int** **->** x **+** **1** **in**
add1 **(add1** **0)**

The ASM therefore simplifies the first expression to the second before
proceeding. Since anonymous functions like^{(fun} (x:int) : int -> x + 1)

are one of the three kinds of heap data (see §15.2), the ASM just moves the

**fun**value to the heap and replaces the** ^{fun}**expression with the newly
cre-ated reference. The ASM then follows the usual rules for

**simplification to create a binding for the function name on the stack. Figure 15.9 shows how the example program above looks after following these simplification rules.**

^{let}Simplifying function call expressions is more difficult. The issue is that, in general, the function call may itself be nested within a larger expression that will require further simplification after the function returns its com-puted value. To model this situation faithfully, the ASM must therefore keep track of where in the surrounding expression the value computed by a function call should be returned to once the function is done.

x+1 !

/&012+.$3' (4.$1' 53.+'

67(89:;'(+0)#<'9:88'

fun (x:int) -> x + 1!

.==8'

add1 (add1 0) !

>' :'

add1 ( ) !

Figure 15.10: The ASM just after the call to the inner^{add1}has been simplified. The
stack contains a saved workspace whose hole marks where the answer of this function
call should be returned. It also contains a binding for the^{add1}function’s argument^{x}.

In the example program above, after creating a binding for^{add1}on the
stack, we reach a situation in which the worskspace contains the
expres-sionadd1 (add1 0). We can simplify the innermost^{add1}by looking up the
reference in the stack as usual. Then we’re ready to do the function call—

in general, a function call is ready to simplify if the function is a reference
and all of its arguments are values. Suppose that we magically knew that
the answer computed by^{add1 0}was going to be a value^{ANSWER}. Then the
we should eventually simplify workspace by replacing inner function call,

(add1 0), with^{ANSWER}to obtain a new workspaceadd1 ANSWER.
To achieve that goal, the ASM simplifies a function call like this:

First it saves the current workspace to the stack, marking the spot
where the^{ANSWER}should go with a “hole”. In our example, since the
orig-inal workspace wasans1 (ans1 0), the saved workspace when doing the
inner call will beans1 (____), where the^{____}marks the “hole” to which
the answer will be returned.

Second, the ASM adds new stack bindings for each of the called func-tion’s parameters. Suppose that the function being called has the shape

**fun** (x1:t1) ... (xN:tN) -> bodyin the heap and it is being called with
the arguments^{v1}. . .^{vK}.^{3} Then there will be stack bindings added for^{x1}7→

v1. . .^{xJ} 7→vJ. In our running example, the ^{add1}function takes only one
argument called^{x}, so only one binding will be added to the stack.

Third, the workspace is replaced by the body of the function.^{4}

3In general there can be fewer arguments than the function requires, which corre-sponds to the case of partial application.

4In the case of partial application, the workspace is replaced by a** ^{fun}**expression of the

Figure 15.10 shows the state of the ASM just after the inner call to^{add1}
has been simplified.

Once the function call has been initiated and the function body is in the workspace, simplification continues as usual. This process may in-volve adding more bindings to the stack, doing yet more function calls, or allocating new data structures in the heap.

Assuming that the code of the function body eventually terminates
with some value, the ASM is in a situation in which the result of the
func-tion should be returned as the^{ANSWER}to the corresponding workspace that
was saved on the stack at the time that the function was called. For
exam-ple, after a few steps of simplification, the workspace in Figure 15.10 will
contain only the value^{1}, which is the answer of the inner call to^{add1}.

When this happens—that is, when the workspace contains a value and
there is at least on saved workspace on the stack—the ASM returns the
value to the old workspace. It does so by popping (i.e. removing) all of
the stack bindings that have been introduced since the last workspace was
saved on the stack. It then replaces the current workspace (which just
contains some value^{v}) with the last saved workspace (and also popping
it from the stack), replacing the answer “hole” with the value^{v}.

In our running example, after the workspace in Figure 15.10 simplifies
to the value ^{1}, the ASM will pop the binding for^{x}from the stack, restore
the workspace to^{add1 1}(where the hole has been replaced by^{1}), and then
pop the saved workspace. Simplification then proceeds as usual.

Lecture 12 contains an extended animation of the ASM simplification for a more complex example, which shows how to run the following pro-gram:

**let rec** append **(l1:** **’a** **list) (l2:** **’a** **list) :** **’a** **list** **=**
**begin match** l1 **with**

**|** Nil **->** l2

**|** Cons(h, t) -> Cons(h, append t l2)
**end in**

**let** a **=** Cons(1, Nil) **in**

**let** b **=** Cons(2, Cons(3, Nil)) **in**
append a b

form** ^{fun}** (xL:tL) .. (xN:tN) -> body, where

^{L}is

^{J+1}. To properly continue simplifica-tion will, in this case, require the use of a closure. See §17.1.

let ans : int = .x <- 17; p1.x"

.(/0"123+& 4'230& 5+21&

67489:;&41/#%$&9:88&

18&

19&

x" ^{1"}

y" ^{1"}

Figure 15.11:The state of the ASM just before doing the imperative update to the^{p2.x}
field. Note that^{p1}and^{p2}are aliases—they point to the same record in the heap.