LARA

Local, Higher-Order, and Dispatched Procedures

Simple Local (Nested) Procedures

Nested functions can access outside functions. 

def saveData(f : File) = {
  def wr(s : String) = {
    writeStringToFile(f, s)
  }
  def wrInt(x : Int) = {
    wr(integerToString(x))
  }
  wr("<body>")
  wr("This is my page.")
  wrInt(2008)
  wr("</body>")
}

Here function 'wr' accesses both 's' and 'f'

  • note that 'f' can be at different places relative to stack top

How does code for 'wr' access 'f' ?

Several alternative solutions:

  1. pass extra 'static link' for the enclosing function ('saveData' for 'wr')
    • chase links when
  2. maintain global display array of most recent procedure of static nesting depth 'i'
    • avoids chasing links
  3. make enclosing function arguments explicit: lambda lifting
    • modifies both function definition and function call

Previous example after lambda lifting is simply: 

def wr(s : String, f : File) = {
  writeStringToFile(f, s)
}
def wrInt(x : Int, f : File) = {
  wr(integerToString(x), f)
}
def saveData(f : File) = {
  wr("<body>", f)
  wr("This is my page.", f)
  wrInt(2008, f)
  wr("</body>", f)
}

Global Function Pointers

To pass global functions, we simply pass their addresses

We need to know the calling convention for all function values that can be called 

var exlaim = "!!!"
 
def simpleNotify(msg : String) = {
  println(msg)
}
def noisyNotify(msg : String) = {
  beep(1024)
  popUp(msg)
  beep(2048)
  popUp(msg + exclaim)
  beep(512)
}
def alarm(time : Int, notify : msg -> unit) = {
  if (currentTime==time) {
    alert("Wake up!")
  }
}
alarm(0700, simpleAlert)
alarm(0800, noisyAlert)

When 'notify' is called in 'alarm', it will be passed string argument on stack

  • it knows how to access global variables

This works in e.g. C and Pascal

Higher-Order Functions

None of the previous techniques works when nested functions are returned as arguments

Consider example: 

  def greet(firstLine : String, message : String) = {
    println(firstLine)
    println(message)
  }
 
  def getGreeter(title : String) : String => unit = {
    var myLine = "Dear " + title
    def myGreeter(name : String) = {
      println(myLine + " " + name)
      myLine = myLine + " "
      println("How are you doing today?")
    }
    myGreeter
  }
 
  val g = getGreeter("Mr")
  val g1 = getGreeter("")
  g("Santa")
  g1("Schmutzli")

When g returns a function, how can this function know what the value of 'myLine' is?

  • 'myLine' value must remain even after 'getGreeter' returns
  • cannot allocate frame for getGreeter on stack, must use heap
  • to invoke 'g' and 'g1' must obtain both code pointer and frame pointer

A pair of code and frame pointer is called closure

Higher-order function can be encoded as an object with 'apply' method (as in Scala)

  • closure is then an object with one method

More details:

  • Tiger book, Chapter 15
  • Simon L. Peyton Jones, The Implementation of Functional Programming Languages, Prentice-Hall, 1987

Dynamic Method Dispatch in Object-Oriented Languages

How do we know which method is invoked here in the following: 

var x : Object;
println(x.toString())

The invoked method depends on the dynamic type of 'x'.

We can view the method to execute as object field (of function type)

Simple implementation: store function pointers in the object

But all objects have same code pointers

  • introduce a table for each dynamic type, Virtual method table (vtable)
  • dynamic type of object give a pointer to corresponding vtable

How can we call methods in supertypes?

  • for single inheritance, we arrange methods in sequence, from superclass to subclass
  • superclasses ignore entries from subclass

More information: