Closures

Free Variable, Closed Expression

Definition

A free variable in an expression is a variable that is not bound/defined in the expression.

An expression is closed if it has no free variables.

Closures

// Anonymous functions = lambdas
// Function values = first-class functions
// Closures

def procedure(x: Int) = { x + 1 }

var increase: Int => Int = procedure
increase(5) // 6

increase = { x => x + 2 }
increase(5)                 // 7
List(5, 6, 7).map(increase) // List(7, 8, 9)

def twice(fun: Int => Int): Int => Int = {
    x => fun(fun(x))
}
increase = twice(increase)
increase(5) // 9

increase = { x => x + increment } // Increment is a free variable, where should we get it from?

// Create a closure
def increaseBy(increment: Int): Int => Int = {
    x => x + increment
}

increase = increaseBy(3)
increase(5) // 8

List(increaseBy(1), increaseBy(2), increaseBy(3)).map(fun => fun(5)) // List(6, 7, 8)
List(1, 2, 3).map(increaseBy).map(fun => fun(5))                     // List(6, 7, 8)

What is in the lists in the last two lines? Each of these increaseBy(1), increaseBy(2), etc does something a bit different.

In CS241E LACS, we don't have anonymous functions, so instead, we would write:

def increaseBy(increment: Int): Int => Int = {
    def procedure(x: Int): Int = {
        x + increment
    }

    procedure
}

Definition

A closure is a pair of:

Code of a function body (e.g function Pointers in C)
- Implemented as a label to the inner function
An environment that gives values to the free variables in the function's body
- Take the frame of the "constructor" and set the static link of the inner function to it, saved at closure creation

var functionValue: Int => Int

def constructor(a: Int) Int => Int = {
    var b = a * 2
    
    def proc(c: Int): Int = {
        a + b + c
    }
    
    proc
}

functionValue = constructor(42)
functionValue(5) // 42 + 84 + 5 = 131

Closure Operations

Info

We have 2 stages, closure creation and closure call.

Table

Stage	When
Evaluate args	Call
Compute static link	Creation
Allocate param chunk	Call
Copy temp vars into params	Call
`LIS 8`, `use label`	Creation
`JALR 8`	Call closure

Consider the code:

def increaseBy(increment: Int): Int => Int = {
    def procedure(x: Int): Int = {
        x + increment
    }

    procedure
}

Closure creation
- Function pointer: label to address of the inner procedure (procedure)
- Environment: address of the frame of the the closure creator (increaseBy). That is, we treat it like a normal call.
Closure call
- Code address: code of inner procedure (procedure), load with JALR
- Pass the environment (frame of increaseBy) which includes the free variables (increment)

Call closure like normal function
Function value is Code
- Code that reads var. functionValue into Reg.result (R3)

Variable Extent

See Variables#Extent

Info

A free variable in a closure exists as long as the closure "instance" still exists.

In the code above, we may use the increment variable later, after exiting from the scope of increaseBy.

Solution: allocate frame/params of procedure creator on the heap, not on the stack.

Which procedures need their frames on the heap?

Safe, conservative choice: all enclosing procedures because the produced function may access any outer variables
More aggressive approach: look through the body of the produced function and list which variables are accessed, then only allocate those variables on the heap
Even more: separate variables that are accessed by the produced function from those that are not, and only allocate the former on the heap

Any produced function also needs its frame and parameters allocated on the heap.

Closure Representation

Since we need two addresses, allocate a chunk of size 2 containing the 2 addresses.