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-ingadd1:

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


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

funvalue to the heap and replaces thefunexpression with the newly cre-ated reference. The ASM then follows the usual rules forletsimplification 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.

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.+'


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


add1 (add1 0) !

>' :'

add1 ( ) !

Figure 15.10: The ASM just after the call to the inneradd1has 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 theadd1function’s argumentx.

In the example program above, after creating a binding foradd1on the stack, we reach a situation in which the worskspace contains the expres-sionadd1 (add1 0). We can simplify the innermostadd1by 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 byadd1 0was going to be a valueANSWER. Then the we should eventually simplify workspace by replacing inner function call,

(add1 0), withANSWERto 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 theANSWERshould 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 argumentsv1. . .vK.3 Then there will be stack bindings added forx17→

v1. . .xJ 7→vJ. In our running example, the add1function takes only one argument calledx, 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 afunexpression of the

Figure 15.10 shows the state of the ASM just after the inner call toadd1 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 theANSWERto 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 value1, which is the answer of the inner call toadd1.

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 valuev) with the last saved workspace (and also popping it from the stack), replacing the answer “hole” with the valuev.

In our running example, after the workspace in Figure 15.10 simplifies to the value 1, the ASM will pop the binding forxfrom the stack, restore the workspace toadd1 1(where the hole has been replaced by1), 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

formfun (xL:tL) .. (xN:tN) -> body, whereLisJ+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&




x" 1"

y" 1"

Figure 15.11:The state of the ASM just before doing the imperative update to thep2.x field. Note thatp1andp2are aliases—they point to the same record in the heap.

Nel documento Programming Languages and Techniques Lecture Notes for CIS 120 Steve Zdancewic Stephanie Weirich University of Pennsylvania February 9, 2014 (pagine 143-146)