Now that we have defined an interpreter for our language, we can begin to add new features to the language. Remember, the goal is not necessarily to develop efficient implementations, but to study the meaning of various language features.
You must understand the interpreter we are defining or you won't understand the rest of the class. Please see the TA or the instructor if you're having trouble understanding the interpreter.
No language, of course, can do without conditional evaluation. This section describes the process of adding conditional expressions to our language. The general procedure for adding a new feature is:
The last step can include defining auxiliary functions so support the evaluation of the new feature.
The BNF for conditional expressions will be as follows:
| The BNF for <expression> (with conditionals) |
|---|
|
The abstract syntax has fields for each of the non-terminals in the new production.
We implement this by adding a new production to our grammar for SLLGEN:
(expression
("if" expression "then" expression "else" expression)
if-exp)
If we were writing our parser by hand, we'd modify the code to recognize this new production, including recursing three times: once for each subexpression.
Notice that the specification for SLLGEN says to generate an if-exp abstract syntax record when
an if expression is parsed.
This adds a new case to the expression datatype corresponding to the abstract syntax as follows:
(if-exp
(test-exp expression?)
(true-exp expression?)
(false-exp expression?))
(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)))
;; ----
(else (eopl:error 'eval-expression "Not here:~s" exp))
)))
The evaluation strategy recurses three times, once for each time <expression> appears on the right-hand side of the BNF. Note, however, that in execution, it either recurses on the then-exp or on the else-exp but not both. This behavior is defined in terms of the Scheme if expression. One must understand how if works in Scheme to understand how if works in our language.
The conditional expression is defined in terms of one auxiliary function, true-value?. When we recurse on the test-exp, we will get value that is one of the legal values in the new language, either a number of a procedure. There are no booleans.
To avoid adding a boolean type to the language, we will interpret numbers as boolean values: a zero representing false and any other value representing true. The function true-value? coerces values in the new language to legal values in the defining language (Scheme) so that they can be used:
(define true-value?
(lambda (x)
(not (zero? x))))
Using the read-eval-print loop, we can test conditional expressions:
--> if 1 then 2 else 3 2 --> if -(3, +(1, 2)) then 2 else 3 3
In this section, we add a let expression to our language to allow local bindings. The new expressions will have the following form:
let x = 5
y = 6
in +(x, y)
These local bindings provide static scoping: the body of the let expression is evaluated in an environment containing bindings for the variables in the let expression.
The BNF for let expressions can be generally defined as follows:
| The BNF for <expression> (with 'let') |
|---|
|
We implement this by adding a new production to our grammar for SLLGEN:
(expression
("let" (arbno identifier "=" expression) "in" expression)
let-exp)
If we were writing our parser by hand, we'd modify the code to recognize this new production, including recursing once for each initialization expression and once for the body.
Notice that the specification for SLLGEN says to generate a let-exp abstract syntax record when
an if expression is parsed.
This adds a new case to the expression datatype corresponding to the abstract syntax as follows:
(let-exp
(ids (list-of symbol?))
(rands (list-of expression?))
(body expression?))
From the BNF, we expect that we will recurse once on the body of the
let expression and also recurse once for each expression in the
declarations. When we recurse on the body, we must
have an environment with new bindings corresponding to the declarations.
This is why we have an environment parameter as part of eval-expression: so that
we can specify the environment in which to evaluate things.
The behavior for let is that the
expressions in the declarations are evaluated in the current environment,
which is then extended to include bindings of those
values. The body of the let expression is then evaluated in this new
environment:
(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) ;\new4
(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))))
;; ----
(else (eopl:error 'eval-expression "Not here:~s" exp))
)))
Don't be confused by the let expressions inside the expression
defining the let expression in our new language. We're not
implementing the ELL let just by using a Scheme let. The use
of a Scheme let expression is just for code readability--could have just as easily
written the code without it. What does implement the ELL let are the
calls to eval-rands, extend-env, and eval-expression.
Note that we use eval-rands to evaluate the list of expressions created from the declarations. This function clearly evaluates any list of expressions, not just operands.
You must not get confused from your past training and start thinking that extend-env side-effects the environment and that it is permanently changed (as it might be in a language such as Pascal or C). When eval-expression returns from the recursive call evaluating the body of the let expression, the environment will be unchanged.
We can use the REP loop, to test let expressions:
--> let x = 1
in let y = +(x,3)
z = 4
in add1(-(y,z))
1
--> let x = 1
in let x = +(x,2)
in add1(x)
4
Last updated at 9:54 am on Friday, August 27, 2004.