I. orientation ------------------------------------------ WHERE ARE WE? Chapters basic concepts and Scheme syntax abstraction 1 induction and recursion 2 data abstraction 3 environment-passing interpreters 3.1 simple interpreter 3.2 the front end 3.3 conditionals 3.4 local binding 3.5 procedures 3.6 recursion 3.9 statements 3.8 parameter passing 4 types 5 objects and classes 6 objects and types ------------------------------------------ ------------------------------------------ WHY? Use interpreters to: - explain semantics of features - play with behavior of features - play with changes to features HOW Plan: - start with simple interpreter - add features ------------------------------------------ II. A Simple Interpreter (3.1) A. overview ------------------------------------------ WHAT AN INTERPRETER DOES (3.1) concrete syntax | v abstract --------> Expressed syntax Value ------------------------------------------ B. language design ------------------------------------------ DESIGN OF THE DEFINED LANGUAGE 1. What values? Expressed Value = Number Denoted Value = Number 2. What grammar? (concrete syntax) ::= "a-program (exp)" ::= "lit-exp (datum)" | "var-exp (id) | "primapp-exp (prim ( {}*(,) ) rands)" ::= + | - | * | add1 | sub1 ------------------------------------------ What's the difference between the defined and defining languages? What's the difference between an expressed and denoted value? ------------------------------------------ FOR YOU TO DO (IN PAIRS) 1. Give 4 examples of in the defined language's grammar. 2. Give 2 examples of things that are expressions in Scheme, but not in the defined language's grammar ------------------------------------------ Why is the grammar for operands like that? Could it be simplified? C. implementation What cases are there in the syntax of ? Of ? ------------------------------------------ ABSTRACT SYNTAX (define-datatype program program? (a-program (exp expression?))) (define-datatype expression expression? (lit-exp (datum number?)) (var-exp (id symbol?)) (primapp-exp (prim primitive?) (rands (list-of expression?)))) (define-datatype primitive primitive? (add-prim) (subtract-prim) (mult-prim) (incr-prim) (decr-prim)) ------------------------------------------ Does this look familiar? How can that be when the concrete syntax is Algol-like? 1. domains ------------------------------------------ DOMAINS def: the domain *Expressed-Value* is def: the domain *Denoted-Value* is To start, the defined languge will have: Expressed-Value = Number Denoted-Value = Expressed-Value ------------------------------------------ ------------------------------------------ EXPRESSED-VALUE OPERATIONS ;; upcasts (deftype number->expressed (-> (number) Expressed-Value)) ;; downcasts (deftype expressed->number (-> (Expressed-Value) number)) ;; debugging (deftype expressed->printable (-> (Expressed-Value) datum)) ;; tests (deftype number->expressed? (-> (Expressed-Value) boolean)) (define-datatype Expressed-Value expval? (number->expressed (num number?))) ------------------------------------------ How would you program expressed->number? number->expressed? ? 2. interpreter itself ------------------------------------------ SIMPLE INTERPRETER ------------------------------------------ What order of evaluation does this specify? Is the ordering between arguments specified? Will this run as is? What's left to program? 3. environments a. definition and implementation ------------------------------------------ ENVIRONMENTS Def: an *environment* is a mapping from variable names to denoted values: Expressed-Value = Number Denoted-Value = Expressed-Value Environment = -> Denoted-Value ------------------------------------------ Can you ever have an infinite domain in this mapping? How shall we implement them? b. initial environment What goes in the initial environment? ------------------------------------------ INITIAL ENVIRONMENT (deftype init-env (-> () environment)) (define init-env ------------------------------------------ What would be needed to add zero as the name of a constant? 4. primitives ------------------------------------------ APPLYING PRIMITIVES (deftype apply-primitive (-> (primitive (list-of Expressed-Value)) Expressed-Value)) (define apply-primitive (lambda (prim args) (cases primitive prim ------------------------------------------ What would be needed to add division as a primitive? What else could this check? Anything else that has to change? 5. front-end (3.2) ------------------------------------------ THE FRONT END at run-time off-line program string | lexical grammar v v !---------! !-----------! ! scanner ! <====== ! SLLGEN ! !---------! !-----------! | | token stream grammar v v !---------! !-----------! ! parser ! <====== ! SLLGEN ! !---------! !-----------! | | abstract syntax | tree for program v !---------------! ! eval-program ! !---------------! | v Expressed-Value ------------------------------------------ a. non-interactive ------------------------------------------ ;; file ch3-1.scm (define the-lexical-spec '((whitespace (whitespace) skip) (comment ("%" (arbno (not #\newline))) skip) (identifier (letter (arbno (or letter digit "_" "-" "?"))) symbol) (number (digit (arbno digit)) number))) (define the-grammar '((program (expression) a-program) (expression (number) lit-exp) (expression (identifier) var-exp) (expression (primitive "(" (separated-list expression ",") ")") primapp-exp) (primitive ("+") add-prim) (primitive ("-") subtract-prim) (primitive ("*") mult-prim) (primitive ("add1") incr-prim) (primitive ("sub1") decr-prim) )) (deftype scan&parse (-> (string) program)) (define scan&parse (sllgen:make-string-parser the-lexical-spec the-grammar)) (deftype run (-> (string) Expressed-Value)) (define run (lambda (string) (eval-program (scan&parse string)))) ------------------------------------------ ------------------------------------------ USING IT > (require (lib "ch3-1.scm" "lib342")) > (run "5") > ------------------------------------------ b. read-eval-print loop ------------------------------------------ A READ-EVAL-PRINT LOOP ;; file ch3-1.scm (deftype read-eval-print (-> () poof)) (define read-eval-print (lambda () ((sllgen:make-rep-loop "--> " (lambda (pgm) (eval-program pgm)) (sllgen:make-stream-parser the-lexical-spec the-grammar))))) USING IT > (require (lib "ch3-1.scm" "lib342")) > (read-eval-print) --> --> ------------------------------------------ c. tracing it (if have time, do on computer) ------------------------------------------ TRACING THE INTERPRETER (IN CHEZ SCHEME) > (require (lib "ch3-1-modified-in-class.scm" "lib342")) > (trace eval-expression eval-rands) > (trace apply-primitive apply-env) > (read-eval-print) --> 3 |(eval-expression (lit-exp 3) (extended-env-record (i v x) #((number->expressed 1) (number->expressed 5) (number->expressed 10)) (empty-env-record))) |3 3 --> i |(eval-expression (var-exp i) (extended-env-record (i v x) #((number->expressed 1) (number->expressed 5) (number->expressed 10)) (empty-env-record))) | (apply-env (extended-env-record (i v x) #((number->expressed 1) (number->expressed 5) (number->expressed 10)) (empty-env-record)) i) | 1 |1 1 ------------------------------------------ ------------------------------------------ MORE TRACES --> +(3,i) |(eval-expression (primapp-exp (add-prim) ((lit-exp 3) (var-exp i))) (extended-env-record (i v x) #((number->expressed 1) (number->expressed 5) (number->expressed 10)) (empty-env-record))) | (eval-rands ((lit-exp 3) (var-exp i)) (extended-env-record (i v x) #((number->expressed 1) (number->expressed 5) (number->expressed 10)) (empty-env-record))) | |(eval-expression (var-exp i) (extended-env-record (i v x) #((number->expressed 1) (number->expressed 5) (number->expressed 10)) (empty-env-record))) | | (apply-env (extended-env-record (i v x) #((number->expressed 1) (number->expressed 5) (number->expressed 10)) (empty-env-record)) i) | | 1 | |1 | |(eval-expression (lit-exp 3) (extended-env-record (i v x) #((number->expressed 1) (number->expressed 5) (number->expressed 10)) (empty-env-record))) | |3 | (3 1) |(apply-primitive (add-prim) (3 1)) |4 4 --> ------------------------------------------ III. Conditional Evaluation (3.3) ------------------------------------------ CONDITIONALS (3.3) What should be the concrete syntax for if-expressions in the defined language? ------------------------------------------ What would this be like if we had a distinction between statements and expressions? ------------------------------------------ FOR YOU TO DO IN GROUPS Close your books. 1. What should the abstract syntax be? 2. What type should the test have? 3. Write the part you need to add to the interpreter, and any needed code. 4. Do any primitive procedures need to be built-in to make this useful? Write the necessary changes for them. ------------------------------------------ A. semantic implications and variations What options do we have for representing truth values? B. example, adding unless ------------------------------------------ ADDING UNLESS EXPRESSIONS new syntax: (expression ("unless" expression "do" expression) unless-exp) new ASTs: (unless-exp (test-exp expression?) (false-exp expression?)) New clauses in eval-expression: ------------------------------------------ IV. Local Binding (3.4) A. syntax ------------------------------------------ NAMING AND LET (3.4) Concrete syntax: ::= let { = }* in Examples: let x = 5 y = 6 in +(x, y) let x = 3 in let x = *(x, x) in +(x, x) Abstract syntax: ------------------------------------------ What should the values of the examples be? B. scoping What should the scope rules be? Where are we going to record the values of these variables? Will that work with the scoping? If the interpreter took both an expression and an environment, what would have to change? ------------------------------------------ INTERPRETER WITH LET (deftype eval-expression (-> (expression environment) Expressed-Value)) (define eval-expression (lambda (exp env) (cases expression exp (lit-exp (datum) (number->expressed datum)) (var-exp (id) (apply-env env id)) ; ... ------------------------------------------ C. semantic implications and variations How does this make the scope rules for let work out? 1. sequential let V. Procedures (3.5) A. syntax ------------------------------------------ PROCEDURES (3.5) Concrete syntax: ::= ... | proc ( {}*(,) ) | ( {}* ) Examples: Abstract syntax: ------------------------------------------ What should be the abstract syntax? does this abstract syntax look familiar? B. semantics 1. scoping ------------------------------------------ SEMANTICS OF PROCEDURES What scope rules for procedures? let three = 3 in let add3 = proc (y) +(y, three) in let three = 100 in (add3 2) ------------------------------------------ 2. domains ------------------------------------------ DOMAINS Expressed-Value = Number + ProcVal Denoted-Value = Expressed-Value (define-datatype Expressed-Value expval? (number->expressed (num number?)) (procval->expressed (pv procval?))) ------------------------------------------ 3. procedure values ------------------------------------------ PROCEDURE VALUES AS A DATATYPE Want: (apply-procval (closure ids body env) args) = (eval-expression body (extend-env ids args env)) Use this to define apply-procval : closure : ------------------------------------------ Which is the constructor? observer? ------------------------------------------ PROCEDURAL REP OF PROCVAL (define closure (lambda (ids body env) (define apply-procval (lambda (proc args) ------------------------------------------ ------------------------------------------ FOR YOU TO DO Convert the procedural rep of ProcVal to an AST rep ------------------------------------------ 4. the interpreter ------------------------------------------ THE INTERPRETER (figure 3.7) (deftype eval-expression (-> (expression environment) Expressed-Value)) (define eval-expression (lambda (exp env) (cases expression exp (primapp-exp (prim rands) (let ((args (eval-rands rands env))) (apply-primitive prim args))) ... (proc-exp (ids body) (app-exp (rator rands) ------------------------------------------ C. semantic implications and variations 1. examples 2. lexical addresses (exercises 3.23-3.28) 3. dynamic binding (aka. dynamic scoping, exercises 3.30-3.33) a. motivation ------------------------------------------ UTILITY OF DYNAMIC BINDING changing implicit parameters: let stdout = port in p(1,2) let font = italic in format(mytext) exception handlers: try { // Java syntax mydata.read(System.in); return mydata.average(); } catch (NoDataException e) { System.err.println("no data!"); return POSITIVE_INFINITY; } catch (ArithmeticExecption a) { System.err.println("no data!"); return POSITIVE_INFINITY; } ------------------------------------------ Why couldn't stdout simply be a global variable? Why not pass these around as parameters? What's like this in the Unix shell? Why wouldn't the handlers be bound statically? b. history c. domains ------------------------------------------ DOMAINS FOR DYNAMIC SCOPING Expressed-Value = Number + ProcText (define-datatype ProcText ProcText? (procedure-text (ids (list-of symbol?)) (body expression?))) ------------------------------------------ What's missing? So when you apply a procedure text, where does the environment come from? d. behavior ------------------------------------------ BEHAVIOR WITH DYNAMIC SCOPE let three = 3 in let add3 = proc(i) +(i, three) three = 5 in *(three, (add3 2)) ------------------------------------------ What's the difference from static scoping? ------------------------------------------ FOR YOU Consider: let a = 3 in let p = proc() +(x, a) f = proc(x, y) *((p), y) a = 5 in *(a, (f let a = 2 in a 1)) TO DO: What is the value with dynamic scoping? Does it make sense with static scoping? ------------------------------------------ e. the funarg problem ------------------------------------------ THE FUNARG PROBLEM let G = 6.670e-11 in let gravForce = proc(m1) proc(r) proc(m2) /(*(G, *(m1, m2)), *(r,r)) in (((gravForce 5.96e24) 6.37e6) 68) ------------------------------------------ what will happen with dynamic scope? f. reasoning problems (exercise 3.33) Can we change formal parameter names and their uses without affecting the meaning of a program? ------------------------------------------ COUNTER-EXAMPLE let a = 3 in let p = proc() +(x, a) f = proc(x, y) *((p), y) a = 5 in *(a, (f let a = 2 in a, 1)) vs. let a = 3 in let p = proc() +(x, a) f = proc(x, a) *((p), a) %% *** a = 5 in *(a, (f let a = 2 in a 1)) ------------------------------------------ Can we replace a call to a procedure with its body, substituting the actuals for the formals in the body? Can we change "proc(x) (f x)" to "f"? Could you do type checking at compile time if have dynamic scope? VI. Recursion (3.6) A. the problem ------------------------------------------ WHY DOESN'T LET WORK FOR RECURSION? What does the interpreter with let do for the following? let fact = proc(x) if zero?(x) then 1 else *(x, (fact sub1(x))) in (fact 342) ------------------------------------------ How could we fix that? B. syntax ------------------------------------------ LETREC EXPRESSIONS Examples: letrec fact(x) = if zero?(x) then 1 else *(x, (fact sub1(x))) in (fact 342) letrec even(n) = if zero?(n) then 1 else (odd sub1(n)) odd(k) = if zero?(k) then 0 else (even sub1(k)) in (odd 541) Concrete syntax: ::= ------------------------------------------ ------------------------------------------ Abstract syntax: (define-datatype expression expression? ... (letrec-exp (proc-names (list-of symbol?)) (idss (list-of (list-of symbol?))) (bodies (list-of expression?)) (letrec-body expression?)) ) ------------------------------------------ C. semantics What do we want letrec to do, in essence? ------------------------------------------ (deftype eval-expression (-> (expression environment) Expressed-Value)) (define eval-expression (lambda (exp env) (cases expression exp (var-exp (id) (apply-env env id)) ; ... (proc-exp (ids body) (procval->expressed (closure ids body env))) (letrec-exp (proc-names idss bodies letrec-body) (eval-expression letrec-body (extend-env-recursively proc-names idss bodies env))) ))) ------------------------------------------ ------------------------------------------ SPECIFICATION OF EXTEND-ENV-RECURSIVELY Let e2 = (extend-env-recursively proc-names idss bodies e) - if name is in proc-names and if ids and body are the corresponding formal parameter list and procedure body, then (apply-env e2 name) = (closure ids body e2) - if name is not in proc-names, then (apply-env e2 name) = (apply-env e name) ------------------------------------------ D. implementation What different ways could we represent environments? 1. procedural representation ------------------------------------------ PROCEDURAL REPRESENTATION OF ENVIRONMENTS ; (defrep (environment (-> (symbol) Expressed-Value))) (define apply-env (lambda (env sym) (env sym))) ;; ... (define extend-env (lambda (ids vals env) (lambda (sym) (let ((pos (list-index sym ids))) (if (<= 0 pos) (list-ref vals pos) (apply-env env sym)))))) ;; Figure 3.9, see ch3-6-1.scm (define extend-env-recursively (lambda (proc-names idss bodies old-env) ------------------------------------------ How does this satisfy the specification? 2. AST representation ------------------------------------------ AST REPRESENTATION OF ENVIRONMENTS (define-datatype environment environment? ; ... (extend-env-recursively (proc-names (list-of symbol?)) (idss (list-of (list-of symbol?))) (bodies (list-of expression?)) (env environment?))) (define apply-env (lambda (env sym) (cases environment env ;; ... (extend-env-recursively (proc-names idss bodies old-env) (let ((pos (list-index sym proc-names))) (if (<= 0 pos) (procval->expressed (closure (list-ref idss pos) (list-ref bodies pos) env)) (apply-env old-env sym))))))) ------------------------------------------ 3. Optimizations How often are closures built? Is that necessary? ------------------------------------------ MUTUALLY RECURSIVE ENVIRONMENTS AND CLOSURES letrec even(n) = if zero?(n) then 1 else (odd sub1(n)) odd(k) = if zero?(k) then 0 else (even sub1(k)) in ... We want e2 = (extend-env-recursively '(even odd) '((n) (k)) (list <> <>) e) to be such that, (apply-env e2 even) = (closure '(n) < e2) (apply-env e2 odd) = (closure '(k) < e2) ------------------------------------------ ------------------------------------------ THE CODE (ch3-6-3.scm) (define-datatype environment environment? (empty-env-record) (extended-env-record (syms (list-of symbol?)) (vec vector?) (env environment?)) ) (define extend-env-recursively (lambda (proc-names idss bodies old-env) ------------------------------------------ E. semantic implications and variations Do mutually recursive environments and closures cause any problems for tools? What about top-level definitions? How to make them recursive? How would you do a "namedlet" expression? VII. Variable Assignment (3.7) A. syntax ------------------------------------------ ASSIGNMENT (3.7) Examples: set x = 3 set y = +(y, x) Concrete syntax: ::= set = Abstract syntax: (define-datatype expression expression? ; ... ------------------------------------------ B. semantics How would you describe an assignment? 1. domains ------------------------------------------ PROBLEM WITH ENVIRONMENTS Currently: Environment = symbol -> Denoted-Value Denoted Value = Expressed-Value Expressed-Value = Number + ProcVal Can an expression change the environment like assignment should? Example: let x = 5 in let addx = proc(n) +(n,x) in let first = proc(ignored) addx(20) in first(set x = 10) ------------------------------------------ How could we make that happen? ------------------------------------------ REFERENCES We add an operation to environments: (deftype apply-env-ref (-> (environment symbol) (ref-of Expressed-Value))) We use the following ADT (deftype deref (forall (T) (-> ((ref-of T)) T))) (deftype setref! (forall (T) (-> ((ref-of T) T) void))) Where, for all types T, if r is a (ref-of T), and ev, ev2 are values of type T ev = (begin (setref! r ev) (deref r)) ev = (begin (setref! r ev2) (setref! r ev) (deref r)) ------------------------------------------ ------------------------------------------ NEW DOMAINS Expressed-Value = Number + ProcVal Denoted-Value = Ref(Expressed-Value) Environment = symbol -> Denoted-Value ------------------------------------------ 2. implementation a. reference ADT ------------------------------------------ IMPLEMENTATION OF THE REFERENCE ADT ;; file reference-3-7.scm (module reference-3-7 (lib "typedscm.ss" "lib342") (provide ref-of a-ref deref setref!) (define-datatype reference reference? (a-ref (position integer?) (vec vector?))) (deftype primitive-deref (forall (T) (-> ((ref-of T)) T))) (define primitive-deref (lambda (ref) (cases reference ref (a-ref (pos vec) (vector-ref vec pos))))) (deftype primitive-setref! (forall (T) (-> ((ref-of T) T) void))) (define primitive-setref! (lambda (ref val) (cases reference ref (a-ref (pos vec) (vector-set! vec pos val))))) (define deref (lambda (ref) (primitive-deref ref))) (define setref! (lambda (ref val) (primitive-setref! ref val))) ) ;; end module ------------------------------------------ b. environment ADT ------------------------------------------ CHANGES TO ENVIRONMENT IMPLEMENTATION (define-datatype environment environment? (empty-env-record) (extended-env-record (syms (list-of symbol?)) (vec vector?) (env environment?)) ) ; ... (define extend-env (lambda (syms vals env) (extended-env-record syms (list->vector vals) env))) (define apply-env-ref (lambda (env sym) (cases environment env (empty-env-record () (eopl:error 'apply-env-ref "No binding for ~s" sym)) (extended-env-record (syms vals env) (let ((pos (list-index sym syms))) (if (<= 0 pos) (a-ref pos vals) ; ** (apply-env-ref env sym))))))) (define apply-env (lambda (env sym) (deref (apply-env-ref env sym)))) ------------------------------------------ 3. interpreter ------------------------------------------ THE INTERPRETER WITH ASSIGNMENT What changes to the interpreter? ;;; Figure 3.15, p. 103 (define eval-expression (lambda (exp env) (cases expression exp (var-exp (id) (apply-env env id)) ;; ... ------------------------------------------ 4. Changes to init-env Are any changes needed in init-env? C. semantic implications and variations 1. result What is the value returned by an assignment expression? What other options are there? 2. sequencing (exercise 3.39) Once we have sequencing and assignment, what other syntax could we have in the defined language? 3. references and call-by-value How are storage locations represented in the interpreter? ------------------------------------------ CALL-BY-VALUE Example: let x = 100 in let p = proc(y) let d = set y = add1(y) in y in +((p x), (p x)) What does this return? Example: let x = 100 in let p = proc(y) let d = set x = add1(y) in x in +((p x), (p x)) What does this return? ------------------------------------------ Where does the location that set y = add1(y) come from? Why are these results different? Where does the location that set x = add1(y) come from? So When are the storage locations created? 4. explicit allocation, dereferencing (as in BCPL, exercise 3.41) (skip) What happens if we make location expressed values, with operations cell, contents, and setcell? ------------------------------------------ let g = let count = cell(0) in proc() begin setcell( count, add1(contents(count))) contents(count) end in +((g), (g)) ------------------------------------------ How would you do something like the C/C++ address-of (&) operator? 5. arrays (exercise 3.42) (homework problem) What primitives would you add to add arrays to the language? 6. constant bindings (exercise 3.45) (skipped) How would you implement something like C++ "const" variables or Java "final" variables? 7. dynamic assignment or fluid binding (exercise 3.47) 8. semantic ideas (exercise 3.48) (skip)