Prelude
• Anotherplacewhereyouhaveencounteredthenotions of free and bound variables, and lexical scope.
• A wonderful article about integrals in the April 18, 2010 New York Times: It Slices, it dices! http://opinionator.blogs.nytimes.com/2010/04/18/it- slices-it-dices/?th&emc=th
Final E&C Example
The following two Scheme expressions are evaluated (in the order shown here):
>(define f
(lambda (x)
(let ([a (lambda (y z)
(+ x y z))])
(lambda (b)
(a (+ 5 b) x))))
>((f 3) 4)
1
A12 details
CSSE 304 Day 19
Environment ADT Environment Representations (Interpreter Project Intro if there is time left)
2
We now know how environments are supposed to behave. Next question: How can we implement them?
ENVIRONMENT ADT
Summary of EoPL Section 2.2 (details on the following slides)
• Principle from Section 2.1
• Environment ADT
– Environment Interface
– Representation/Implementation Approaches
3
Principle from Section 2.1
–Data abstraction leads to representation independence
Environment ADT
• An environment maps a finite set of symbols to a set of associated (Scheme) values
• Thus, an environment is a finite function
• Logically, an environment has the form { (s1, v1), (s2, v2), … (sn, vn) } ,
where the si are all distinct.
• But we need a little more detail in order to get the “lexical scoping” effect.
4
Environment interface If f is an environment, and s, s1, …, sk are all symbols, then
(empty-env) (apply-env f s)
(extend-env ‘(s1 … sk) ‘(v1 … vk)
f )
Recall that x means “the representation of the abstract object x”
f(s)
g
(representation of the empty set)
(get the value associated with s in the environment f)
(all symbols si must be distinct, the vi may be any Scheme values)
where g(s) is
vi ifs=si forsomei,1ik f(s) otherwise
empty-env and extend-env are constructors;
apply-env is an observer (getter)
Examples of the use of this interface
If f is an environment, and s, s1, …, sk are all symbols, then
(empty-env) (apply-env f s)
(extend-env ‘(s1 … sk)
‘(v1 … vk) f )
(representation of the empty set) f(s) (get the value associated with s
in the environment f)
(all symbols si must be distinct, the vi may be any Scheme values)
g where g(s) is
vi ifs=si forsomei,1ik
f(s) otherwise
5
Implementation preliminaries Auxiliary procedures
(define list-find-position ; returns pos of sym in los (or #f) (lambda (sym los)
(list-index (lambda (sym1) (eqv? sym1 sym)) los)))
(define list-index ; finds pos of list item satisfying pred (or #f) (lambda (pred ls)
(cond
((null? ls) #f)
((pred (car ls)) 0)
(else (let ((list-index-r (list-index pred (cdr ls))))
(if (number? list-index-r)
(+ list-index-r 1)
#f))))))
Representation 1
• We first do an easy implementation, then aim for a more efficient one
• Take advantage of Scheme’s first-class procedures
• Represent an environment by a procedure
• Each environment procedure takes a symbol as an argument
• This is straightforward
– Just translate the formal definitions into code
• We will do this same process later for other ADTs
6
Environment interface If f is an environment, and s, s1, …, sk are all symbols, then
(empty-env) (apply-env f s)
(extend-env ‘(s1 … sk) ‘(v1 … vk)
f )
Recall that x means “the representation of the abstract object x”
f(s)
g
(representation of the empty set)
(get the value associated with s in the environment f)
(all of the si must be distinct,
the vi may be any Scheme values) where g(s) is
vi ifs=si forsomei,1ik f(s) otherwise
empty-env and extend-env are constructors;
apply-env is an observer (getter)
Representation 1: empty environment
(define empty-env
(lambda () ; what should the rest be?
; recall that we are implementing
; environments as Scheme procedures.
7
Representation 1: empty environment
(define empty-env
(lambda ()
(lambda (sym)
(eopl:error ‘apply-env
“No binding for ~s”
sym))))
Representation 1: apply-env
(define apply-env
(lambda (env sym) ; what should the rest be?
8
Representation 1: extend-env
(define extend-env
(lambda (syms vals env) ; what should the rest be?
Representation 2
• Use data structures to represent environments.
– in particular, variant records created using
define-datatype
– Note that the actual code for looking up symbols is the same as before, but now it is in apply-env.
9
Define the environment datatype
(define-datatype environment
environment?
[empty-env-record]
[extended-env-record
(syms (list-of symbol?))
(vals (list-of scheme-value?))
(env environment?)])
How should scheme-value? be defined? (define scheme-value?
Define the environment datatype
(define-datatype environment
environment?
[empty-env-record]
[extended-env-record
(syms (list-of symbol?))
(vals (list-of scheme-value?))
(env environment?)])
How should scheme-value? be defined? (define scheme-value?
(lambda (v) #t))
10
Implementation 2 – the two constructors
(define empty-env
(lambda ()
(define extend-env
(lambda (syms vals env)
Implementation 2 – the two constructors
(define empty-env
(lambda ()
(empty-env-record)))
(define extend-env
(lambda (syms vals env)
(extended-env-record syms
vals
env)))
11
Implementation 2:
The observer (accessor) procedure
(define apply-env
(lambda (env sym)
(cases environment env
[empty-env-record ()
(errorf ‘apply-env
“No binding for ~s” sym)]
[extended-env-record (syms vals env)
(let ([pos (list-find-position sym
syms)])
(apply-env env sym)))])))
(if (number? pos)
(list-ref vals pos)
Comparisons of the two representations?
Representation 3
Represent environment as a list of lists
::= ((({
Three examples:
(((a b) (3 4)) ((c) (2)))
(((a b) (3 4)) ((c a x) (2 3 #f)))
()
(define apply-env
(lambda (env sym)
(if (null? env)
(eopl:error ‘apply-env “No binding for ~s” sym)
(let ((syms (car (car env)))
(vals (cadr (car env)))
(env (cdr env)))
(let ((pos (rib-find-position sym syms)))
(if (number? pos)
(list-ref vals pos)
(apply-env env sym)))))))
(define rib-find-position list-find-position)
*Code that is green will change in Representation 4 (a slight variation of Representation 3)
(define extend-env
(lambda (syms vals env)
(cons (list syms vals) env)))
(define empty-env
(lambda ()
‘()))
Sometimes called a “ribcage” structure
12
Rep 4 adds two improvements
1. Make each rib a pair instead of a list – saves space and lookup time
2. Replace the list of values in each rib by a vector of values
– So we can replace linear-time list‐ref by constant- time vector‐ref
• (((a b). #(3 4)) ((c a x). #(2 3 #f)))
Representation 4
Ribcage structure with these improvements
13
Implementing the ribcage (slide 1)
(define empty-env
(lambda ()
‘()))
(define extend-env
(lambda (syms vals env)
(cons (cons syms (list->vector vals))
env)))
Implementing the ribcage (slide 2)
(define apply-env
(lambda (env sym)
(if (null? env)
(error ‘apply-env “No binding for ~s” sym)
(let ((syms (car (car env)))
(vals (cdr (car env)))
(env (cdr env)))
(let ([pos (rib-find-position sym syms)])
(if (number? pos)
(vector-ref vals pos)
(apply-env env sym)))))))
14
Compare with “List of lists” implementation
(define apply-env
(lambda (env sym)
(if (null? env)
(error ‘apply-env “No binding for ~s” sym)
(let ((syms (car (car env)))
(vals (cadr (car env)))
(env (cdr env)))
(let ([pos (rib-find-position sym syms)])
(if (number? pos)
(list-ref vals pos)
(apply-env env sym)))))))
Implementation 5 callbacks (continuations)
• This is what I use in the interpreter code.
• Change the interface so apply-env expects:
1. An environment
2. A symbol, the variable to be looked up
3. A “succeed” callback function, applied to the value of the variable if the variable is found
4. A “fail” callback function, applied ot no arguments if the variable is not found.
15
apply-env with callbacks
This is a modification of Representation 2; we could
modify Representation 3 or 4 in a similar way.
(define apply-env
(lambda (env sym succeed fail)
(cases environment env
[empty-env-record
(fail)]
[extended-env-record (syms vals env)
(let ([pos (list-find-position sym syms)]) (if (number? pos)
(succeed (list-ref vals pos)) (apply-env env sym succeed fail)))])))
INTERPRETER PROJECT INTRODUCTION
16
Ready to write an interpreter!
• We have
– A parser that produces abstract expression trees
– error checking
– environments
– lexical-address
– A knowledge of how closures and environments work
– Soon we will also have CPS • The rest is mostly details
Assignments weeks 6-10
Assignment Tentative due date Emphasis
13 (team) Day 22 primitive procedures, literals, lambda, let, if
14 (team) Day24 expand-syntax, cond, and, or, while etc.
15 (individual) Day 26 CPS, memoize, multi-value returns
16 (team) Day 29 letrec, named let, while loop as syntax expansion
17 (team) Days 32 and 33 define, set!, reference parameters
18 (team) Days 35 and 37 CPS with data structure continuations, call/cc,
advanced features
19 (individual) Day 39 Imperative form
Extra credit Demo it by 2:00 PM TBA 150 points Wednesday of exam week
17