Chapter 10 Functions

Functions are like jumps. But: they return. Where does a return return to? Idea: continuations. Return address becomes another argument. Push on the stack or passed in a register.

As first-class values: use function pointer. Indirect vs direct calls.

10.1 Example

def f(x: Int) = x + g();

def g() = 2;

def h(x: Int, y: Boolean): Int = {
  val z = if (y) {
    f(x + 1)
  } else {
    x - 1
  };
  z * x
};
def k(f: Int => Int): Int = f(0);

10.2 Syntax

<type>   ::= <ident> | <type> '=>' <type>  // '=>' is right associative
           | '('[<type>[','<type>]*]')' '=>' <type>
<atom>   ::= <number> | <bool> | '()'
           | '('<simp>')'
           | <ident>
<tight>  ::= <atom>['('[<simp>[','<simp>]*]')']*
           | '{'<exp>'}'
<uatom>  ::= [<op>]<tight> // Previously atom
<simp>   ::= ... // same as before
<exp>    ::= ... // same as before
<arg>    ::= <ident>':'<type>
<prog>   ::=
   ['def'<ident>'('[<arg>[','<arg>]*]')'[':' <type>] '=' <simp>';']*
           <exp>

10.3 AST

case class FunType(args: List[(String,Type)], rte: Type) extends Type
case class Arg(name: String, atp: Type, pos: Position)
case class FunDef(name: String, args: List[Arg], rte: Type, fbody: Tree)
        extends Tree

case class LetRec(funs: List[Tree], body: Tree) extends Tree
case class App(fun: Tree, args: List[Tree]) extends Tree

10.4 Semantics

  • Argument names must be distinct. Arguments behave like immutable variables.
  • Functions can be recursive (even mutually recursive)
  • Function application is left associative, i.e f(1)(3) will be parsed as App(App(“f”, 1), 3)
  • We don’t allow overloading, i.e a function can not have the same name than another one even with different arguments.
  • We allow functions to be stored in variables, used as parameters and returns from other functions.

10.5 Type Checking

case class FunType(args: List[(String,Type)], rte: Type) extends Type

A function type is well-formed if all of its argument types and its return type are well-formed.

A function type ‘tp’ conforms to type ‘pt’ if all of the following hold:

  1. ‘pt’ is a function type or UnknownType
  2. ‘pt’ has the same number of arguments as ‘tp’
  3. the type of ‘pt’ argument #n conforms to the type of ‘tp’ argument #n (note the inversion)
  4. the return type of ‘tp’ conforms to the return type of ‘pt’

Example:

  • (Int, Boolean) => Int conforms to ??? (result: (Int, Boolean) => Int)
  • Int => Int conforms to Int => Int
  • Int => Int does not conform to Boolean - rule #1
  • ??? => Int conforms to Int => Int (result: Int => Int)
  • Int => Int does not conform to ??? => Int - rule #3
  • Int => Boolean does not conform to Int => Int - rule #4
  • ??? => Boolean conforms to Int => ??? (result: Int => Boolean)
         Env,a1:T1,...,an:Tn |- fb: T
------------------------------------------------[FunDef]
 Env |- FunDef(f, a1...an, T, fb) : (T1...Tn) => T


  Env,f1:FT1,...,fn:FTn |- f1: FT1
               ...
  Env,f1:FT1,...,fn:FTn |- fn: FTn
   Env,f1:FT1,...,fn:FTn |- b : T
----------------------------------[LetRec]
    Env |- LetRec(f1...fn, b): T



       Env |- f: (T1,...,Tn) => T
       Env |- a1: T1
       ...
       Env |- an: Tn
----------------------------------[App]
  Env |- App(f, List(a1,...,an)): T

10.6 Interpreter

What does a function call mean?

                  // LetRec(List(
def f(x: Int) = { //   FunDef("f", List(Arg("x", IntType)), ???,
  x + 1           //     Prim("+", Ref("x"), Lit(1))
};                //   )),
f(1)              //   App(Ref("f"), List(Lit(1)))
                  // )
def f(x: Int) = { g(x) + 1 };
def g(x: Int): Int = 2 * x;
f(1 + 1)
def f(x: Int): Int = { g(x) + 1 };
def g(x: Int): Int = if (x == 0) 0 else f(x-1);
f(1)

Implementation:

abstract class Val
case class Cst(x: Any) extends Val
case class Func(args: List[String], fbody: Exp, env: Env) extends Val

def eval(exp: Exp)(env: Env): Val = exp match {
  case LetRec(funs, body) =>
    val funcs = funs map { case f$@$FunDef(n, _, _, _) => (n, eval(f)(env)) }
    funcs foreach { case (_, f$@$Func(_, _, _)) => f.withVals(funcs) }
    eval(body)(env.withVals(funcs))
  case FunDef(name, args, rte, fbody) =>
    Func(args map { arg => arg.name }, fbody, env)
  case App(f, args) =>
    val eargs = args map { arg => eval(arg)(env) }
    val Func(fargs, fbody, fenv) = eval(f)(env)
    eval(fbody)(fenv.withVals(fargs zip eargs))
}

10.7 Compilation: Calling Conventions

One of the main concepts we have been using so far is convention.

Our compiler only generates code that uses registers ‘sp’ and above and which puts the result in ‘sp’.

Thus, we can keep intermediate results and know which memory locations are available at any given point.

How should we call a function from any point in the program without losing data?

Example:

def f(x: Int) = 1 + x;

val y = f(1);
val z = f(2);
y + z

  • Argument passing: %rdi, %rsi, %rdx, %rcx, %r8, %r9
  • Return: use call and ret
    • call pushes the instruction pointer on the stack, and jumps to the label
    • ret pops the return address from the stack and jumps to it
    • Corollary: we need to reset the stack before calling ret
  • Return value will be saved in %rax
  • Before calling a function, all intermediate values will be saved on the stack

10.8 Where Are We?

Today, we learned the following:

  • Type checking functions
  • Interpreting functions
  • Calling conventions