Denoted values are values that can be associated to variables in the language. The relation between a variable and its value is called denotation (the variable name denotes a value).
Before writing an interpreter, we must distinguish between meta- and object-language. The meta-language is the language in which we write the interpreter (we use Scheme). The object-language is the language we are describing and that is evaluated by the interpreter.
In the definition of the object-language, we rely on some features of the meta-language. For example, if we allow ourselves to use a meta-language with assignment and mutable data-structures, then it is easy to simulate assignment in the object language. We can, however, restrict ourselves, and force ourselves not to use the mutation facilities of the meta-language if we want to gain a better understanding of what is involved. During the course of the investigation, we will impose on ourselves various such restrictions to understand different aspects of the object-language.
<exp> ::= <integer-literal>
| <varref>
| <operator> <operands>
<operator> ::= <varref> | (<exp>)
<operands> ::= () | (<operand> {; <operand>})
<operand> ::= <exp>
<varref> ::= <var>
The following abstract syntax is defined:
lit(datum) app(rator rands) varref(var)A first interpreter for this language is defined as follows:
(define eval-exp
(lambda (exp)
(cases expr exp
(lit (datum) datum)
(varref (var) (apply-env init-env var))
(app (rator rands)
(let ((proc (eval-exp rator))
(args (eval-rands rands)))
(apply-proc proc args)))
(else (error "invalid abstract syntax: " exp)))))
(define eval-rands
(lambda (rands)
(map eval-exp rands)))
Define procedures:
<procedure> ::= <prim-op>
<prim-op> ::= <addition> +
| <substraction> -
| <multiplication> *
| <division> /
Abstract syntax: prim-proc (prim-op)
(define (apply-proc proc args)
(cases proc
(prim-proc (prim-op) (apply-prim-op prim-op args))
(else (error "Invalid proc: " proc))))
(define (apply-prim-op op args)
(case prim-op
((+) (+ (car args) (cadr args)))
((-) (- (car args) (cadr args)))
((*) (* (car args) (cadr args)))))
Note that in this solution, the primitive operation is an expressed value
(that is, the expression "+" is a valid expression in L0, whose value is
the primitive procedure (prim-proc +).
Here are some semantic questions we can already ask on L0 based on the
interpreter definition:
<exp> ::= if <exp> then <exp> else <exp>And the corresponding abstract syntax is:
(if-exp (test expr?)
(then expr?)
(else expr?))
The computation rule we add to the interpreter is:
(define eval-expr
(lambda (e)
(cases expr e
(lit (datum) datum)
(varref (var) (apply-env init-env var))
(if-exp (test then else)
(let ((tv (eval-exp test)))
(if (true-val? tv)
(eval-exp then)
(eval-exp else))))
(app (rator rands)
(let ((proc (eval-exp rator))
(args (eval-rands rands)))
(apply-proc proc args))))))
;; Determine when an expressed value is considered true in L1
(define true-val?
(lambda (e) (if (eqv? e 0) #f #t)))
;; Apply-proc and eval-rands do not change from above.
Some semantic questions we can ask about L1:
An environment is a finite function from symbols to denoted values.
(empty-env): create the empty environment.
(extend-env symbols denvals env):
create a new environment nenv such that:
when symbols = {s1, s2, ..., sn} and
denvals = {val1, val2, ..., valn} then
nenv(si) = vali for any si in symbols and
nenv(s) = env(s) for any other symbol.
(apply-env env s): returns the denoted value of env on s.
In L2, we will work with the same set of expressed values (Numbers) and
determine that the set of denoted values is the same set (Numbers).
The new syntax to introduce local variables is:
<expr> ::= let { <var> = <expr> }* in <expr>
with the associated abstract syntax:
(let-expr (vars (list-of symbol?))
(vals (list-of expr?))
(body expr?))
With this new syntax, the following expressions belong to L2:
let x = 1
y = 2 in
let x = 2 in
+(x, y)
We now define a computation rule which will insure that L2 is a
lexically scoped language - that is, the let-computation rule will
be such that the link between a varref and the corresponding binding
position in a let can be determined through syntactic analysis in a
way similar to the free/bound analysis discussed in the lambda calculus
in a previous lesson.
To this end, we must modify the signature of the interpreter. Up to
L1, we used an interpreter eval-exp with the following
signature:
eval-expr: Expr --> NumberWe now modify it to be:
eval-expr: Expr x Env --> NumberThat is, the interpreter now evaluates an expression within a given environment. The new computation rule is shown in the following interpreter:
(define eval-expr
(lambda (e env)
(cases expr e
(lit (datum) datum)
(varref (var) (apply-env env var))
(if-exp (test then else)
(let ((tv (eval-exp test env)))
(if (true-val? tv)
(eval-exp then env)
(eval-exp else env))))
(app (rator rands)
(let ((proc (eval-exp rator env))
(args (eval-rands rands env)))
(apply-proc proc args)))
(let-exp (vars vals body)
(let ((expvals (eval-rands vals env)))
(eval-exp body
(extend-env vars expvals env)))))))
(define (eval-rands rands env)
(map (lambda (rand) (eval-exp rand env)) rands))
(define (apply-proc proc expvals)
(cases proc
(prim-proc (prim-op) (apply-prim-op prim-op expvals))
(else (error "Invalid proc: " proc))))
(define (apply-prim-op op args)
(case prim-op
((+) (+ (car args) (cadr args)))
((-) (- (car args) (cadr args)))
((*) (* (car args) (cadr args)))
((/) (/ (car args) (cadr args)))))
Semantic questions we can ask about L2 based on this interpreter definition:
Is L2 lexically scoped? (This can be proven inductively.) In which environment
are the values of the let computed? In which order are the variable bindings
computed?
<expr> ::= proc ( { <var> }* ) <expr>
with the following abstract syntax:
(proc (vars (list-of symbol?))
(body expr?))
Because of this decision, we must extend the expressed values domain. Up to L2,
the expressed values domain was simply Numbers. Now, we must add the
possibility that the result of a computation is a closure or a number.
A closure captures the environment that was active at the time the procedure
expression is computed. Consider the following example program in L3:
let x = 2 in
let p = proc (y) +(y, x) in
let x = 5 in
p(10)
This reduces to: 12 (and not 15).
We therefore define a new domain of expressed values as follows - and take
the opportunity to clean up the case of primitive operators (which were
"hidden" expressed values up to now):
(define-datatype expval expval?
(number (datum number?))
(prim-proc (prim-op primitive-op?))
(closure (formals (list-of symbol?))
(body expr?)
(c-env env?)))
(define primitive-op? (lambda (e) (memv? e '(+ * - /))))
We keep working with a domain of denoted values equal to the domain of expressed
values.
The new evaluation rules for procedures and applications appear in bold in
the following interpreter definition:
(define eval-expr
(lambda (e env)
(cases expr e
(lit (datum) (number datum)) ;; Change to expval
(prim-proc (prim-op) e) ;; Proper handling of primitives
(varref (var) (apply-env env var))
(if-exp (test then else)
(let ((tv (eval-exp test env)))
(if (true-val? tv)
(eval-exp then env)
(eval-exp else env))))
(app (rator rands)
(let ((proc (eval-exp rator env))
(args (eval-rands rands env)))
(apply-proc proc args)))
(let-exp (vars vals body)
(let ((expvals (eval-rands vals env)))
(eval-exp body
(extend-env vars expvals env))))
(proc (vars body)
(closure vars body env)))))
(define (eval-rands rands env)
(map (lambda (rand) (eval-exp rand env)) rands))
(define (apply-proc proc expvals)
(cases proc
(prim-proc (prim-op) (apply-prim-op prim-op expvals))
(closure (vars body c-env)
(eval-exp body
(extend-env vars expvals c-env)))))
(define (apply-prim-op op args)
(case prim-op
((+) (+ (car args) (cadr args)))
((-) (- (car args) (cadr args)))
((*) (* (car args) (cadr args)))
((/) (/ (car args) (cadr args)))))