First Class Functions

Functions as Values

We have functions, but they are second-class entities in our languages: they don’t have the same abilities as other values.

For example, the following is rejected:

with a multiple error messages:

Errors found!
tests/input/hof.diamond:(2:3)-(4:1): Function 'it' is not defined

         2|    it(5)
               ^^

tests/input/hof.diamond:7:3-7: Unbound variable 'incr'

         7|  f(incr)
               ^^^^

This is because the Env only holds

  • parameters, and
  • let-bound variables

and not function definitions.

But for the many reasons we saw in CSE 130 – we want to treat functions like values. For example, if you run the above in Python you get:

Flashback: How do we compile incr?

We compile each function down into a sequence of instructions corresponding to its body.

becomes:

What is the value of a function?

So now, lets take a step back. Suppose we want to compile

Attempt 1: What is the value of the parameter it ?

IDEA: Use the label where incr lives!

How to pass the value of the parameter ?

So now the main expression

f(incr)

can be compiled to:

QUIZ: What are suitable terms for ?1 and ?2 ?

?1 ?2
A label_def_incr_start labal_def_f_start
B label_def_f_start labal_def_incr_start
C label_def_f_start labal_def_f_start
D label_def_incr_start labal_def_incr_start

Strategy Progression

  1. Representation = Start-Label

    • Problem: How to do run-time checks of valid args?

Yay, that was easy! How should the following behave?

Lets cheat and see what Python does:

Problem: Ensure Valid Number of Arguments?

How to make sure

  • f(incr) succeeds, but
  • f(add) fails

With proper run-time error?

  1. Where does the run-time check happen?
  2. What information is needed for the check?

Key: Need to also store the function’s arity

  • The number of arguments required by the function

Strategy Progression

  1. Representation = Start-Label

    • Problem: How to do run-time checks of valid args?
  2. Representation = (Arity, Start-Label)

Attempt 2: What is the value of the parameter it ?

IDEA: Use a tuple of (arity, label)

We can now compile a call

  e(x1,...,xn)

via the following strategy:

  1. Evaluate the tuple e
  2. Check that e[0] is equal to n (else arity mismatch error)
  3. Call the function at e[1]

Example

Lets see how we would compile this

We need to map the variable

incr

to the tuple

(1, label_def_incr_start)

But where will we store this information?

Strategy Progression

  1. Representation = Start-Label

    • Problem: How to do run-time checks of valid args?
  2. Representation = (Arity, Start-Label)

    • Problem: How to map function names to tuples?
  3. Lambda Terms Make functions just another expression!

Attempt 3: Lambda Terms

So far, we could only define functions at top-level

  • First-class functions are like any other expression,

  • Can define a function, wherever you have any other expression.

Language Syntax
Haskell \(x1,...,xn) -> e
Ocaml fun (x1,...,xn) -> e
JS (x1,...,xn) => { return e }
C++ [&](x1,...,xn){ return e }

Example: Lambda Terms

We can now replace def as:

Implementation

As always, to the details! Lets figure out:

Representation

  1. How to store function-tuples

Types:

  1. Remove Def
  2. Add lambda to Expr

Transforms

  1. Update tag and ANF
  2. Update checker
  3. Update compile

Implementation: Representation

Represent lambda-tuples'' orfunction-tuples’’ via a special tag:

Type LSB
number xx0
boolean 111
pointer 001
function 101

In our code:

So, Function Values represented just like a tuples

  • padding, ESI etc.
  • but with tag 101.

Crucially, we can get 0-th, or 1-st elements from tuple.

Question: Why not use plain tuples?

Implementation: Types

First, lets look at the new Expr type

  • No more Def

So we represent a function-definition as:

and a function call as:

Transforms: Tag

This is pretty straight forward (do it yourself)

Transforms: ANF

QUIZ:

Does e need to be

  • A Immediate
  • B ANF
  • C None of the above

Transforms: ANF

QUIZ:

Do es need to be

  • A Immediate
  • B ANF
  • C None of the above

Transforms: ANF

The App case, fun + args should be immediate

  • Need the values to push on stack and make the call happen!

Just like function calls (in diamondback), except

  • Must also handle the callee-expression (named e below)

Transforms: ANF

QUIZ:

Does e need to be

  • A Immediate
  • B ANF
  • C None of the above

Transforms: ANF

The Lam case, the body will be executed (when called)

  • So we just need to make sure its in ANF (like all the code!)

Transforms: Checker

We just have Expr (no Def) so there is a single function:

  • How shall we implement ?1 ?

  • How shall we implement ?2 ?

  • How shall we implement ?3 ?

Transforms: Compiler

Finally, lets see how to convert Expr into Asm, two separate cases:

  • Lam : definitions

  • App : calls

Transforms: Compiler: Lam

QUESTION: Why do we start with the IJmp?

Transforms: Compiler: App

Recall! IDEA: Use a tuple of (arity, label)

We can now compile a call

  e(x1,...,xn)

via the following strategy:

  1. Evaluate the tuple e
  2. Check that e[0] is equal to n (else arity mismatch error)
  3. Call the function at e[1]

A Problem: Scope

Consider the following program:

A Problem Magnified: Dynamically Created Functions

Will it work? How about this variant:

  • add(1) should evaluate to a function-that-adds-1
  • add(10) should evaluate to a function-that-adds-10

Yet, its the same code

  • same arity
  • same start-label

Problem: How can we represent different behaviors?

Free and Bound Variables

A variable x is bound inside an expression e if

  • x is a let-bound variable inside e.
  • x is a formal parameter in e, OR

A variable x is free inside an expression e if

  • x is not bound inside e

For example consider the expression e :

  • m, t are bound inside e, but,
  • n is free inside e

Computing Free Variables

Lets write a function to compute the set of free variables.

Question Why Set ?

lambda (x1,x2,x3): e

let x = y + 10 in x + z

A. {x} B. {} C. { gobble_gobble }

TODO-IN-CLASS

Free Variables and Lambdas

Free Variables of a lambda

  • Those whose values come from outside
  • Should use the same values whenever we “call” the lambda.

For example:

should evaluate to (6, 15, 30)

  • plus1 be like lambda (m): 1 + m
  • plus1 be like lambda (m): 10 + m

Achieving Closure

(Recall from CSE 130)

Key Idea: Each function value must store its free variables

represent plus1 as:

(arity, code-label, [n := 1])

represent plus10 as:

(arity, code-label, [n := 10])

Same code, but different free variables.

Strategy Progression

  1. Representation = Start-Label

    • Problem: How to do run-time checks of valid args?
  2. Representation = (Arity, Start-Label)

    • Problem: How to map function names to tuples?
  3. Lambda Terms Make functions just another expression!

    • Problem: How to store local variables?
  4. Function Value (Arity, Start-Label, Free_1, ... , Free_N)

    • Ta Da!

Closures: Strategy

What if we have multiple free variables?

represent plus10 as:

(arity, code-label, [x := 4], [y := 6])

represent plus20 as:

(arity, code-label, [x := 7], [y := 13])

Example

Lets see how to evaluate

TODO: PIC

Example

Lets see how to evaluate

TODO: PIC

Implementation

Representation

  1. How to store closures

Types:

  • Same as before

Transforms

  1. Update tag and ANF
    • as before
  2. Update checker

  3. Update compile

Representation

We can represent a closure as a tuple of

(arity, code-ptr, free-var-1, ... free-var-N)

which means, following the convention for tuples, as:

-------------------------------------------------------------------------
| N + 2 | arity | code-ptr | var1 | var2 | ... | varN | (maybe padding) |
-------------------------------------------------------------------------

Where each cell represents 32-bits / 4-bytes / 1-word.

Note: (As with all tuples) the first word contains the #elements of the tuple.

  • Which, in this case, it is N + 2

Transforms: Checker

What environment should we use to check a Lam body ?

QUIZ How shall we implement ?vEnv ?

A. addsEnv vEnv []

B. addsEnv vEnv xs

C. addsEnv emptyEnv xs

Transforms: Compile

Question How does the called function know the values of free vars?

  • Needs to restore them from closure tuple

  • Needs to access the closure tuple!

… But how shall we give the called function access to the tuple?

By passing the tuple as an extra parameter

Transforms: Compile

Calls App

  1. Push parameters
  2. Push closure-pointer-parameter
  3. Call code-label
  4. Pop params + pointer

Definitions Lam

  1. Compute free-vars x1,…,xn
  2. Generate code-block
  • Restore free vars from closure-pointer-parameter
  • Execute function body (as before)
  1. Allocate tuple (arity, code-label, x1, ... , xn)

Transforms: Compile Calls

  1. Push parameters
  2. Push closure-pointer
  3. Call code-label
  4. Pop params + pointer

Transforms: Compile Definitions

  1. Compute free-vars y1,…,yn
  2. Generate code-block
  • Restore free vars from closure-pointer-parameter
  • Execute function body (as before)
  1. Allocate tuple (arity, code-label, y1, ... , yn)

Creating Closure Tuples

To create the actual closure-tuple we need

  • the free-variables ys
  • the env from which to values of the free variables.

Generating Code Block

To restore ys we use the closure-ptr passed in at [EBP+8] – the special first parameter – to copy the free-vars ys onto the stack.

A Problem: Recursion

Oops, how do we write:

If we try

We get a variable unbound error!

Errors found!
tests/input/fac-bad.fdl:5:20-23: Unbound variable 'fac'

         5|                 n * fac(n-1))

We need to teach our compiler that its ok to use the name fac inside the body!

Solution: Named Functions

We have a new form of named functions

  • Like Ocaml’s let rec

Which looks like this:

Representing Named Functions

We extend Expr to handle such functions as:

Note that we parse the code

as the Expr

Compiling Named Functions

Mostly, this is left as an exercise to you.

Non-Recursive functions

  • i.e. f does not appear inside e in Fun f xs e
  • Treat Fun f xs e as Lam xs e
  • … Everything should just work.

Recursive

  • i.e. f does appear inside e in Fun f xs e
  • Can you think of a simple tweak to the Lam strategy that works?

Recap: Functions as Values

We have functions, but they are second-class entities in our languages: they don’t have the same abilities as other values.

  1. Representation = Start-Label

    • Problem: How to do run-time checks of valid args?
  2. Representation = (Arity, Start-Label)

    • Problem: How to map function names to tuples?
  3. Lambda Terms Make functions just another expression!

    • Problem: How to store local variables?
  4. Function Value (Arity, Start-Label, Free_1, ... , Free_N)

    • Ta Da!

Next: Adding static type inference

  • Faster! Gets rid of those annoying (and slow!) run-time checks
  • Safer! Catches problems at compile-time, when easiest to fix!