So far, we have only the primitive procedures in our interpreter. In this lecture, we'll add user-defined procedures. Although being able to define your own procedures is a powerful feature of a programming language, it's really quite simple to implement.
The BNF and abstract syntax for user defined procedures will be as follows:
| The BNF for <expression> (with user defined procedures) |
|---|
|
Using this syntax we can write programs like this one:
let f = proc(y,z) *(y, -(z, 5))
in (f 2 8)
Notice that we've used a different syntactic style for calling user-defined procedures than for calling primitive (built-in) ones. This is purely for convenience. We could also have them parse the same way, then figure out in our interpreter which was being used.
The proc form is a type of expression, so we can use a proc wherever an expression is allowed:
(proc (y,z) *(y, -(z, 5)) 2 8)
As a motivation to the following discussion of behavior for user defined procedures, consider the following expression in our new language:
let x = 5 in
let f = proc(y,z) *(y, -(z, x))
x = 28 in
(f 2 8)
What is the value of this expression? Does the free x in the definition of f evaluate to 5 or 28?
This question is the heart of static vs. dynamic scoping:
For our interpreter, we'll implement static scoping. Thus, the value of the above expression is 6 since x evaluates to 5.
To facilitate this behavior, we must associate the environment in which the procedure is created with the procedure so that when it is run, we can use it to evaluate the body of the procedure.
A structure that has a procedure and the environment in which to evaluate it is called a closure. We can model a closure using a record that stores the formal parameters, the body, and the current environment:
(define-datatype procval procval?
(closure
(ids (list-of symbol?))
(body expression?)
(env environment?)))
(The type name procval is short for procedure value.)
When we evaluate a procedure expression (creation, not call), we merely package up its formals, bodies, and the environment in a closure. eval-expression becomes:
(define eval-expression
(lambda (exp env)
(cases expression exp
(lit-exp (datum) datum)
(var-exp (id) (apply-env env id))
(primapp-exp (prim rands)
(let ((args (eval-rands rands env)))
(apply-primitive prim args)))
(if-exp (test-exp true-exp false-exp)
(if (true-value? (eval-expression test-exp env))
(eval-expression true-exp env)
(eval-expression false-exp env)))
(let-exp (ids rands body)
(let ((args (eval-rands rands env)))
(eval-expression body (extend-env ids args env))))
; new clause for building procedures
(proc-exp (ids body) (closure ids body env))
(else (eopl:error 'eval-expression "Not here:~s" exp))
)))
Note that we don't evaluate the body of the procedure here; the whole idea of a procedure is to delay evaluation of the body until a later time.
We're still not done, of course, since we've defined only how to evaluate a
procedure expression, but not how to apply (call) a procedure. To do this, we
need to add another clause to eval-expression to handle the
app-exp case:
(define eval-expression
(lambda (exp env)
(cases expression exp
(lit-exp (datum) datum)
(var-exp (id) (apply-env env id))
(primapp-exp (prim rands)
(let ((args (eval-rands rands env)))
(apply-primitive prim args)))
(if-exp (test-exp true-exp false-exp)
(if (true-value? (eval-expression test-exp env))
(eval-expression true-exp env)
(eval-expression false-exp env)))
(let-exp (ids rands body)
(let ((args (eval-rands rands env)))
(eval-expression body (extend-env ids args env))))
; new clause for building procedures
(proc-exp (ids body) (closure ids body env))
; new clause for applying procedures
(app-exp (rator rands)
(let ((proc (eval-expression rator env))
(args (eval-rands rands env)))
(if (procval? proc)
(apply-procval proc args)
(eopl:error 'eval-expression
"Attempt to apply non-procedure ~s" proc))))
(else (eopl:error 'eval-expression "Not here:~s" exp))
)))
Notice that this just calls a new apply-procval procedure. So, what do we do when we apply a procedure? The process has three steps:
Here's how we implement that:
(define apply-procval
(lambda (proc args)
(cases procval proc
(closure (ids body env)
(eval-expression body (extend-env ids args env))))))
To apply a closure, we evaluate the body of the closure in the environment created by extending the environment of the closure with the formal parameters of the closure bound to the arguments.
As we have discussed before, let expressions are simply syntactic sugar for procedures, so we could dispense with them in the eval-expression code if we wanted to. What would your interpreter have to do instead? (One of your upcoming homework problems will implement this.)
Using the example from earlier:
let x = 5 in
let f = proc(y,z) *(y, -(z, x))
x = 28 in
(f 2 8)
The data structures that are built right before the (f 2 8) call look like this:
During the (f 2 8) call, they look like this:
Note: this material is not in your textbook.
In this implementation, user-defined functions are first-class, but primitive ones are not. Lets change that so that primitives are first-class, too.
procval to include both closures and primitives.primitive records. apply-procval, we need to figure out whether the proc
to apply is a closure or a primitive and call apply-closure
or apply-primitive respectively.We can use the same production we added for an app-exp, but we need to remove the
primitive-app production and the entire primitive nonterminal.
We also need to extend our lexical specification for identifiers:
(identifier
((or letter "_" "-" "?" "+" "-" "*")
(arbno (or letter digit "_" "-" "?" "+" "-" "*")))
Since procedure values (our procval records) can now be either closures or built-in primitives, let's extend our definition:
(define-datatype procval procval?
(closure
(ids (list-of symbol?))
(body expression?)
(env environment?))
(primitive
(prim symbol?)))
Since these built-in functions are just like other variables, they must be added to the initial environment:
(define primitives '(+ - * add1 sub1))
(define init-env
(lambda ()
(extend-env
'(i v x)
'(1 5 10)
(extend-env
primitives
(map primitive primitives)
(empty-env)))))
Since both user-defined procedures and predefined primitives parse the same
way as an app-exp, we have to remove the prim-app
case. The app-exp case is handled the same way (we always call
apply-procval), but we need to extend apply-procval
to handle both closures or primitives):
(define apply-procval
(lambda (proc args)
(cases procval proc
(closure (ids body env)
(apply-closure ids body env))
(primitive (prim)
(apply-primitive prim args)))))
We define the new apply-closure function to do the same thing we used to do for closures:
(define apply-closure
(lambda (ids args env)
(eval-expression body (extend-env ids args env))
))
The apply-primitive procedure also changes but is similar to what
it used to do:
(define apply-primitive
(lambda (prim args)
(case prim
('+ () (+ (car args) (cadr args)))
('- () (- (car args) (cadr args)))
('* () (* (car args) (cadr args)))
('add1 () (+ (car args) 1))
('sub1 () (- (car args) 1))
)))
The complete interpreter for Lecture 18.
The complete interpreter for the alternative implementation of primitive procedures.
Last updated at 9:54 am on Friday, August 27, 2004.