Recursive Functions

The content of this chapter is available as a Scala file here.

Recursion

Let's try to write a function that computes the sum of the first \( n \) integers. Let's pretend we do not know that the sum of the first \( n \) integers is \( n * (n + 1) / 2 \) and instead compute the sum in a loop. Let's try to do this in FAE (with If0):

val sumattempt = wth("sum", Fun("n", If0("n", 0, Add("n", Ap("sum", Add("n", -1))))), Ap("sum", 10))

sumattempt won't work and yield an unbound identifier error (why?). An alternative would be to use a variant of the y combinator to support recursion properly, but today we want to talk about direct support for recursion. More specifically, we want a language construct Letrec that is similar to with, except that the bound String can be used in the expression the String is bound to:

Letrec(x: String, e: Exp, body: Exp)

With this new construct our language looks like this:

object Syntax {
  enum Exp:
    case Num(n: Int)
    case Id(name: String)
    case Add(lhs: Exp, rhs: Exp)
    case If0(cond: Exp, thenExp: Exp, elseExp: Exp)
    case Fun(param: String, body: Exp)
    case Ap(funExpr: Exp, argExpr: Exp)
    case Letrec(x: String, e: Exp, body: Exp)

  object Exp:
    implicit def num2exp(n: Int): Exp = Num(n)
    implicit def id2exp(s: String): Exp = Id(s)
    def wth(x: String, xdef: Exp, body: Exp): Exp = Ap(Fun(x, body), xdef)
}

import Syntax._
import Exp._

Using Letrec, our example can be expressed as follows.

val sum = Letrec("sum", Fun("n", If0("n", 0, Add("n", Ap("sum", Add("n", -1))))), Ap("sum", 10))

Let's now consider the semantics of Letrec. Consider the evaluation of Letrec(x, e, body) in an environment env. What environment should we use to evaluate e and body, respectively? Using env for e will produce a ClosureV(Fun("n", ..."sum"'...), env), and hence the environment when evaluating body will be envbody = env + (x -> ClosureV(Fun("n", ..."sum"...), env)).

This is bad, because the env in the closure does not contain a binding for "sum" and hence the recursive invocation will fail. The environment in the closure must contain a mapping for "sum". Hence envbody should look like

  envbody = env + (x -> ClosureV(Fun("n", ..."sum"...),
                                 env + ("sum" -> ClosureV(Fun("n", ..."sum"...), env)))

This looks better, but now the second closure contains an environment with no binding of "sum". What we need is an environment that satisfies the equation:

  envbody == env + (x -> ClosureV(Fun("n", ..."sum"..), envbody))

Obviously envbody must be circular. There are different ways to create such a circular environment. We will choose mutation to create a circle. More specifically, we introduce a mutable pointer to a value class ValuePointer which will be initialized with a null pointer.

In the Letrec case, we put such a ValuePointer in the environment and evaluate the (recursive) expression in that environment. Then we update the pointer with the result of evaluating that expression.

The only other change we need to make is to dereference a potential value pointer in the Id case. We deal with the necessary case distinction by a polymorphic value method. Due to the mutual recursion between ValueHolder and Value the definitions are put into an object.

object Values {
  trait ValueHolder {
    def value: Value
  }
  sealed abstract class Value extends ValueHolder { def value = this }
  case class ValuePointer(var v: Value) extends ValueHolder { def value = v }
  case class NumV(n: Int) extends Value
  case class ClosureV(f: Fun, env: Env) extends Value
  type Env = Map[String, ValueHolder]
}

import Values._  // such that we do not have to write Values.ValueHolder etc.

The interpreter is unchanged except for the additional Letrec case and the modified Id case.

def eval(e: Exp, env: Env): Value = e match {
  case Num(n: Int) => NumV(n)
  case Id(x) => env(x).value  // dereference potential ValuePointer
  case If0(cond, thenExp, elseExp) => eval(cond, env) match {
    case NumV(0) => eval(thenExp, env)
    case _ => eval(elseExp, env)
  }
  case Add(l, r) => {
    (eval(l, env), eval(r, env)) match {
      case (NumV(v1), NumV(v2)) => NumV(v1 + v2)
      case _ => sys.error("can only add numbers")
    }
  }
  case f@Fun(param, body) => ClosureV(f, env)
  case Ap(f, a) => eval(f, env) match {
    case ClosureV(f, closureEnv) => eval(f.body, closureEnv + (f.param -> eval(a, env)))
    case _ => sys.error("can only apply functions")
  }
  case Letrec(x, e, body) => {
    val vp = ValuePointer(null)  // initialize pointer with null
    val newenv = env + (x -> vp)  // evaluate e in the environment extended with the placeholder
    vp.v = eval(e, newenv)         // create the circle in the environment
    eval(body, newenv) // evaluate body in circular environment
  }
}

The sum of numbers from 1 to 10 should be 55.

assert(eval(sum, Map.empty) == NumV(55))

// These test cases were contributed by rzhxeo (Sebastian Py)
var func = Fun("n", If0("n", 0, Ap("func", Add("n", -1))))
var test1 = Letrec("func", func, Ap("func", 1))
var test2 = Letrec("func", Ap(Fun("notUsed", func), 0), Ap("func", 1))
assert(eval(test1, Map()) == NumV(0))
assert(eval(test2, Map()) == NumV(0))