Locals & Functions

Pen and paper in pairs

(let ((x 1))
  (let ((x 2)
        (y 3))
    (+ x y)))

(let ((x 1))
  (let* ((x 2)
         (y 3))
    (+ x y)))

;; A

(let1 (x 1)
  (+ x x))

;; B

(let1 (x 1)
  (let1 (y 2)
    (+ x y)))

;; C

(let1 (x 1)
  (let1 (y 2)
    (let1 (x 4)
      (+ x y))))

;; D

(let1 (x 1)
  (+ (let1 (y 2)
       (let1 (x 3)
         (+ x y)))
     x))

;; E

(let1 (x 1)
  (+ (let1 (y 2)
       (let1 (x 3)
         (+ x y)))
     x
     (let1 (y 4)
       (let1 (x 5)
         (+ x y)))))

Interpreting programming languages

Local

Racket has the let form to make local bindings.

(let ((x 1)
      (y 2))
  (+ x y))

For our fragment of Racket we will define a more limited form of let which only binds a single identifier and so needs one fewer pair of parentheses.

(let1 (x 1)
  (+ x x))

We expect this to evaluate to 2.

We begin with our conditional language and we see that we need to add two classes to the definition of the AST:

A variable which takes a symbol, and
A let1 form which takes
- a variable (x above),
- an ast-node for the expression to evaluate to bind to the variable (just 1 above), and
- a further ast-node to contain the body of the let1, ((+ x x) above)

(defclass var (ast-node)
  ((v :type symbol :initarg :v)))

(defclass let1 (ast-node)
  ((var :type var :initarg :var)
   (varex :type ast-node :initarg :varex)
   (body :type ast-node :initarg :body)))

Our parser also needs a new clause in its ematch to parse a let1 expression

(`(let (,var ,varex) ,body) (make-instance 'let1
                              :var (make-instance 'var :v var)
                              :varex (parse varex)
                              :body (parse body)))

To maintain a collection of bindings from variables to values, we define an environment. We use a list of pairs. We put them in a structure so that we can use the type of that structure later.

(deftype Environment () t) ; not further specified

(defparameter empty-env nil)

(defun extend (var val env)
  "Extend the environment ENV with a binding of VAR to VAL."
  (cons (cons var val) env))

(defun lookup (var env)
  "Lookup the value associated with VAR in ENV."
  (or (cdr (assoc var env))
      (error "Environment does not contain ~a" var)))

Here is an example of the desired behaviour.

(let ((env0 empty-env))
  (let ((env1 (extend 'x 2 env0)))
    (let ((env2 (extend 'y 3 env1)))
      (let ((env3 (extend 'y 4 env2)))
        (+ (lookup 'x env3)
           (lookup 'y env3)
           (lookup 'y env2))))))

Now we need to adapt interpret so that it can handle an AST in a given environment which is passed down to subexpressions. We add new methods for variables and let1 forms.

We use the defmethod-bind macro. Here is an example of its usage.

(defclass foo ()
   ((bar :initarg :ibar :accessor abar)
    (baz :initarg :ibaz :accessor abaz)))

(defparameter foo-inst (make-instance 'foo :ibar 8 :ibaz 9))

(defmethod-bind foomethod ((foo bar baz))
    ((x (+ bar 1))
     (y (* baz 2)))
  (list x y))

(foomethod foo-inst) ; => (9 18)

(defmethod-bind foomethod ((foo (nbar bar) (nbaz baz)))
    ((x (+ nbar 1))
     (y (* nbaz 2)))
  (list x y))

(defgeneric interpret (ast env)
  (:documentation "Interpret an AST in environment ENV and return a VALUE."))

(defmethod-bind interpret ((num n) env)
    ()
  (declare (ignore env))
  (make-instance 'numval :n n))

(defmethod-bind interpret ((var v) env)
    ()
  (lookup v env))

(defmethod-bind interpret ((arith-binary-op op l r) env)
    (((:slots (nl n)) (interpret l env))
     ((:slots (nr n)) (interpret r env)))
  (make-instance 'numval :n (funcall op nl nr)))

(defmethod-bind interpret ((== l r) env)
    (((:slots (nl n)) (interpret l env))
     ((:slots (nr n)) (interpret r env)))
  (make-instance 'boolval :b (= nl nr)))

(defmethod-bind interpret ((ift test then else) env)
    (((:slots b) (interpret test env)))
  (interpret (if b then else) env))

(defmethod-bind interpret ((let1 var varex body) env)
    (((:slots v) var))
  (interpret body (extend v (interpret varex env) env)))

Note in particular the last method for let1. It interprets the body in an environment extended with the new binding.

Also note the method for interpreting a variable. It merely looks up the variable in the environment.

In tests/racket/local.lisp there is a full set of tests for a variety of let1 forms.

(5am::explain! (5am:run 'tolk/local/tests::let1-execute))

The Tolk Python Parser

The Python AST
- Note name has a context, ctx. See Variables
- The Python AST in Python
The Python Parser parses strings of Python code and outputs instances of the Python AST.
The Python Parser has a test suite containing many examples of the use of parse-python

Locals & Functions

Pen and paper in pairs

Interpreting programming languages

Local

The Tolk Python Parser

etc