Functions

Pen and paper in pairs

(* (+ 3 4) (+ 5 6))

(if (= 1 2)
    (+ 3 4)
    (+ 5 6))

(define (double x)
  (+ x x))

(define (quadruple x)
  (double (double x)))

(+ 4 5)

(define (const5 _)
  5)

(+ (quadruple 3)
   (const5 6))

(let ((x 1))

  (define (f y)
    (+ x y))

  (let ((x 2))
    (f 3)))

Context

Functions

(define (f x y)
  (+ (* 2 x) y))

(define f (lambda (x y)
   (+ (* 2 x) y)))

We now extend local, our language of arithmetic with conditionals and locals, by adding function definitions and application of defined functions. For now we limit ourselves to functions of a single argument. We write our language definition in ./src/racket/functions.lisp

We need to add two new variants to our AST, one for a function which we will call a lambda1 with a parameter and a body, and another which we will call apply1 for an application of a function to an expression of our language. Of course we can not apply any functions expression, only lambdas; we will deal with this later.

(defclass lambda1 (ast-node)
  ((var :type symbol :initarg :var)
   (body :type ast-node :initarg :body)))

(defclass apply1 (ast-node)
  ((fun :type ast-node :initarg :fun)
   (arg :type ast-node :initarg :arg)))

We add corresponding cases to functions:parse.

(defmethod parse (sexp)
  (ematch sexp
    ((type number) (make-instance 'num :n sexp))
    ((type symbol) (make-instance 'var :v sexp))
    (`(+ ,l ,r) (make-instance 'plus :l (parse l) :r (parse r)))
    (`(* ,l ,r) (make-instance 'mult  :l (parse l) :r (parse r)))
    (`(= ,l ,r) (make-instance '== :l (parse l) :r (parse r)))
    (`(if ,test ,then ,else) (make-instance 'ift
                               :test (parse test)
                               :then (parse then)
                               :else (parse else)))
    (`(let (,var ,varex) ,body) (make-instance 'let1
                                  :var (make-instance 'var :v var)
                                  :varex (parse varex)
                                  :body (parse body)))
    (`(lambda ,var ,body) (make-instance 'lambda1
                            :var (make-instance 'var :v var)
                            :body (parse body)))
    (`(,fun ,arg) (make-instance 'apply1 :fun (parse fun) :arg (parse arg)))))

We add some tests to parse expressions of the form

(let1 (f (lambda x (+ x x)))
  (f 3))

(let1 (x 3)
  (let1 (f (lambda y (+ x y)))
    (f 3)))

(5am:run! 'tolk/functions/tests::function-parse)

Now we turn to evaluation. Until now we have two values in our language: numbers and Booleans. Clearly a function is neither of these. So we add a function value class to our language. We need to store three things in our function value:

its parameter,
its body and
the environment in which the function is defined.

More about the environment later.

(defclass funval (value)
  ((parameter :type symbol :initarg :parameter)
   (body :type ast-node :initarg :body)
   (env :type Environment :initarg :env)))

With this in mind we turn to interpreting our function language AST. Our interpreter needs methods for lambda1 and apply1. The former is straightforward; we merely have to include the environment. The latter is somewhat more complex since we need to interpret the function body in the function's environment extended by a binding of the function parameter to the interpretation of the argument.

(defmethod-bind interpret ((lambda1 var body) env)
    (((:slots v) var))
  (make-instance 'funval :parameter v :body body :env env))

(defmethod-bind interpret ((apply1 fun arg) env)
    (((:slots parameter body (funenv env)) (interpret fun env)))
  (interpret body (extend parameter (interpret arg env) funenv)))

We add some tests to check for the subtleties of environment extension.

(5am:run! 'tolk/functions/tests::function-execute)

Note that we can not yet interpret recursive functions directly since the environment for a recursive call to a function can not contain a binding for that function.

(signals simple-error
  (execute '(let1 (fact (lambda n
                          (if (= 0 n)
                              1
                              (* n (fact (+ n -1))))))
             (fact 4)))
  "Environment does not contain: FACT.")

It's worth noting that this would not work in Racket either for the same reason.

(let ((fact (lambda (n)
              (if (= 0 n)
                  1
                  (* n (fact (- n 1)))))))
  (fact 4))

What we can do however is use the Y-combinator to effect recursion.

(is (= 24 (f-evaluate '(let1 (y (lambda f
                                  ((lambda i
                                     (i i))
                                   (lambda i
                                     (f (lambda x
                                          ((i i) x)))))))
                        (let1 (fact (y (lambda f
                                         (lambda n
                                           (if (= 0 n)
                                               1
                                               (* n (f (+ n -1))))))))
                            (fact 4))))))

A nice way of deriving the Y-combinator in the Scheme programming language (which for these purposes is the same as the Racket programming language) can be found here.

There are more direct ways of interpreting recursion but they would require us to deal with mutation, which we now turn to.

etc

student evaluation