I. orientation ------------------------------------------ WHERE ARE WE? Chapters 1-2 basic concepts and Scheme 3 syntax and data abstraction syntax-directed programming 4 (lambda calculus and) imperatives 5.1 interpreter basics 5.2 conditionals 5.3 local binding 5.4 procedures 5.5 assignment 5.6 recursion 5.7 dynamic-binding 6 parameter passing 7 OO features 8-9 control ------------------------------------------ ------------------------------------------ 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 (5.1) A. overview ------------------------------------------ WHAT AN INTERPRETER DOES (5.1) concrete syntax | v abstract --------> Expressed syntax Value ------------------------------------------ B. language design What's the difference between an expressed and denoted value? ------------------------------------------ DESIGN OF THE DEFINED LANGUAGE 1. What values? Expressed Value = Number + Procedure Denoted Value = Number + Procedure 2. What grammar? (concrete syntax) ::= | | ::= | () ::= ( ) | ( {, }*) ::= ::= ------------------------------------------ ------------------------------------------ FOR YOU TO DO (IN PAIRS) 1. Give 4 examples of in the grammar 2. Give 2 examples of things that are expressions in Scheme, but not in grammar ------------------------------------------ Why is the grammar for operands like that? Could it be simplified? C. implementation What cases are there in the syntax of ? ------------------------------------------ ABSTRACT SYNTAX ------------------------------------------ Does this look familiar? How can that be when the concrete syntax is Algol-like? 1. domains ------------------------------------------ DOMAINS def: the domain *Denoted-Value* is def: the domain *Expressed-Value* is To start, the defined languge will have: Denoted-Value = Number + Procedure Expressed-Value = Number + Procedure ------------------------------------------ ------------------------------------------ DENOTED-VALUE OPERATIONS ;; found in ch5-1-denoted-value.scm number->denoted : (-> (number) Denoted-Value) denoted->number : (-> (Denoted-Value) number) procedure->denoted : (-> ((prim-proc T)) Denoted-Value) denoted->procedure : (-> (Denoted-Value) (prim-proc T)) ------------------------------------------ ------------------------------------------ EXPRESSED-VALUE OPERATIONS ;; found in ch5-1-expressed-value.scm number->expressed : (-> (number) Expressed-Value) expressed->number : (-> (Expressed-Value) number) procedure->expressed : (-> ((prim-proc T)) Expressed-Value) expressed->procedure : (-> (Expressed-Value) (prim-proc T)) denoted->expressed : (-> (Denoted-Value) Expressed-Value) expressed->denoted : (-> (Expressed-Value) Denoted-Value) ------------------------------------------ 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: 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 (define init-env ; TYPE: Environment ------------------------------------------ 4. procedures a. design and abstract syntax ------------------------------------------ WHAT PROCEDURES TO BUILD-IN? Concrete syntax: ::= + | - | * | add1 | sub1 Abstract syntax: (define-record ------------------------------------------ What information do we need to store? b. application ------------------------------------------ APPLYING PROCEDURE REPS (define apply-proc ;; TYPE: (-> (Procedure ;; (list Expressed-Value)) ;; Expressed-Value) (lambda (proc args) (variant-case proc (prim-proc (prim-op) (else (error "Invalid procedure:" proc))))) ------------------------------------------ What else could this check? Now what should be the initial environment? What would be needed to add division as a primitive? What would be needed to add zero as the name of a constant? Could we just define apply-proc as apply? c. tracing it ------------------------------------------ TRACING THE INTERPRETER > (trace eval-exp eval-rands) > (trace apply-proc apply-env) > (load-from-lib "ch5-1.scm") > (load-from-lib "ch5-1.scm") > (load-from-lib "rep5-1.scm") > (read-eval-print) --> 3; CALL eval-exp #(lit 3) RETN eval-exp 3 3 --> +; CALL eval-exp #(varref +) CALL apply-env #(extend...) + RETN apply-env #(prim-proc +) RETN eval-exp #(prim-proc +) #(prim-proc +) ------------------------------------------ ------------------------------------------ MORE TRACES --> +(3,4); CALL eval-exp #(app #(varref +) (#(lit 3) #(lit 4))) CALL eval-exp #(varref +) CALL apply-env #(extend...) + RETN apply-env #(prim-proc +) RETN eval-exp #(prim-proc +) CALL eval-rands (#(lit 3) #(lit 4)) CALL eval-exp #(lit 3) RETN eval-exp 3 CALL eval-exp #(lit 4) RETN eval-exp 4 RETN eval-rands (3 4) CALL apply-proc #(prim-proc +) (3 4) RETN apply-proc 7 RETN eval-exp 7 7 ------------------------------------------ 5. front-end a. run ------------------------------------------ PARSING ;;; $PUB/lib/ch5-1.scm ... (load-from-lib "ch5-char-parser.scm") ... (define eval-exp ...) ;;; $PUB/lib/char-parser-connections.scm ... (define parse character-string-parser) ;;; $PUB/lib/run5-1.scm (load-from-lib "char-parser-connections.scm") (define run ; one-shot interpreter ;; TYPE: (-> (
) Expressed-Value) (lambda (x) ------------------------------------------ ------------------------------------------ USING IT > (load-from-lib "ch5-1.scm") loading $PUB/lib/ch5-1.scm ... loading $PUB/lib/undefine-read-eval-print. loading $PUB/lib/undefine-run.scm ... > (load-from-lib "run5-1.scm") loading $PUB/lib/run5-1.scm ... loading $PUB/lib/char-parser-connections.s > (run "5") > ------------------------------------------ b. read-eval-print loop ------------------------------------------ A READ-EVAL-PRINT LOOP ;; $PUB/lib/rep5-1.scm (load-from-lib "appendix-f.scm") ;;; override of App. F for sections 5.1-2 (define eval-print ;; TYPE: (-> (parsed-form) void) (lambda (tree) USING IT > (load-from-lib "ch5-1.scm") > (load-from-lib "rep5-1.scm") > (read-eval-print) --> --> ------------------------------------------ III. Conditional Evaluation (5.2) ------------------------------------------ CONDITIONALS (5.2) 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. ------------------------------------------ IV. Local Binding (5.3) A. syntax ------------------------------------------ NAMING AND LET (5.3) 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 ENVIRONMENTS ;;; Figure 5.3.1 : page 149 (define eval-exp ;; TYPE: (-> (parsed-exp Environment) ;; Expressed-Value) (lambda (exp env) (variant-case exp (lit (datum) (number->expressed datum)) (varref (var) (denoted->expressed (apply-env var))) (app (rator rands) (let ((proc (expressed->procedure (eval-exp rator ))) (args (eval-rands rands ))) (apply-proc proc args))) (if (test-exp then-exp else-exp) (if (true-value? (expressed->number (eval-exp test-exp ))) (eval-exp then-exp ) (eval-exp else-exp ))) (else (error "Invalid abstract syntax: " exp))))) ------------------------------------------ ------------------------------------------ EVAL-RANDS (define eval-rands ;; TYPE: (-> ((list parsed-exp) ;; Environment) ;; (list Expressed-Value)) (lambda (rands ) (map (lambda (rand) (eval-exp rand )) rands))) ------------------------------------------ ------------------------------------------ FOR YOU TO DO Add to this interpreter the clause for let ------------------------------------------ How does your clause make the scope rules for let work out? Does this result in any redundant code? V. Procedures (5.4) A. syntax ------------------------------------------ PROCEDURES (5.4) Concrete syntax: ::= proc ::= ( ) | ( ) ::= {,}* Examples: Abstract syntax: ------------------------------------------ What should be the abstract syntax? B. closures ------------------------------------------ PROCEDURE SCOPING Example: let x = 5 in let addx = proc (i) +(i, x); x = 41 in addx(3) FOR YOU TO DO (IN PAIRS) 1. Which x should addx find? 2. What should be the value of a proc expression? 3. How would you complete this equation? Procedure = Primitive Procedure + 4. Make the changes needed in eval-exp and apply-proc ------------------------------------------ To get lexical scoping, what do we have to do? So what should be the value of a proc expression? C. sugars ------------------------------------------ SUGARS IN THE INTERPRETER Can let be a syntactic sugar now? ;;; In file eval-form-0.scm ;; Grammar: ;; ::= (define eval-form ;; TYPE: (-> (parsed-form) ;; Expressed-Value) (lambda (form) (eval-exp init-env))) ;;; In file run.scm (define run ;; TYPE: (-> () Expressed-Value) (lambda (x) (eval-form (parse x)))) ------------------------------------------ D. second-class procedures (may omit or make homework) What are the defined language's expressed values currently? ------------------------------------------ SECOND-CLASS PROCEDURES What would we have to do to make procedures more like those in C? ------------------------------------------ What syntax change? Could the syntax be simplified then? What about the implementation can be simplified? Do we still need closures? What about C++? What would we have to change to make them as in FORTRAN-77? What syntax change? VI. Variable Assignment (5.5) A. syntax ------------------------------------------ ASSIGNMENT (5.5) Concrete syntax: ::= := Examples: x := 3 y := +(y, x) Abstract syntax: ------------------------------------------ What are the advantages of this concrete syntax vs. FORTRAN or C? B. semantics How would you describe an assignment? 1. domains ------------------------------------------ PROBLEM WITH ENVIRONMENTS Currently: Environment = -> Denoted Value Denoted Value = Number + Procedure Can an expression change the environment like assignment should? Example: let x = 5 in let addx = proc(n) +(n,x); first = proc(ignored) addx(20) in first(x := 10) ------------------------------------------ How could we make that happen? ------------------------------------------ USING CELLS Change to: Environment = -> Denoted Value Denoted Value = where Expressed Value = Number + Procedure + Void In file ch5-5-denoted-value.scm (load-from-lib "cell.scm") In file ch5-5-denoted-value.def (defrep Denoted-Value (cell Expressed-Value)) (deftype make-cell (-> (Expressed-Value) Denoted-Value)) (deftype cell-ref (-> (Denoted-Value) Expressed-Value)) (deftype cell-set! (-> (Denoted-Value Expressed-Value) void)) (deftype cell-swap! (-> (Denoted-Value Denoted-Value) void)) ------------------------------------------ ------------------------------------------ CONVERTING BETWEEN EXPRESSED AND DENOTED VALUES In file ch5-5-expressed-value.scm (define denoted->expressed ;; TYPE: (-> (Denoted-Value) ;; Expressed-Value) (define expressed->denoted ;; TYPE: (-> (Expressed-Value) ;; Denoted-Value) ------------------------------------------ 2. semantic functions ------------------------------------------ THE INTERPRETER WITH ASSIGNMENT What changes to the interpreter? ;;; Figure 5.5.1 : page 157 (define eval-exp (lambda (exp env) (variant-case exp (lit (datum) (number->expressed datum)) (app (rator rands) (let ((proc (expressed->procedure (eval-exp rator env))) (args (eval-rands rands env))) (apply-proc proc args))) (varref (var) (apply-env env var) ;; ... (varassign (var exp) ------------------------------------------ ------------------------------------------ APPLYING PROCEDURES (define apply-proc ;; TYPE: (-> (Procedure ;; (list Expressed-Value)) ;; Expressed-Value) (lambda (proc args) (variant-case proc (prim-proc (prim-op) (apply-prim-op prim-op args)) (closure (formals body env) (eval-exp body (extend-env formals env))) (else (error "Invalid procedure: " proc))))) def: an L-value is def: an R-value is ------------------------------------------ What is the type of the second argument to extend-env? And what is that? And what is the type of args? So what should be the second argument here? Why don't we do that just before we apply a procedure, and not here in apply-proc? What else needs to be changed in the interpreter? Why? C. sequencing (exercise 5.5.4) Once we have sequencing and assignment, what other syntax could we have in the defined language? D. semantic ideas (exercise 5.5.9) VII. Recursion (5.6) A. top-level recursion ------------------------------------------ RECURSION FROM TOP-LEVEL DEFINITIONS (5.6) Syntax: ::= | define = define fact = proc(i) if zero(i) then 1 else *(i, fact(sub1(i))); What environment is remembered by the closure? What environment is the closure stored in? ------------------------------------------ ------------------------------------------ CHANGES DUE TO DEFINE init-env [ *-]--> (extend-env (list 'add1 ...) (list (make-cell (procedure->expressed (make-prim-proc 'add1)) ...)) the-empty-env) What's wrong with the following? (set! init-env (extend-env (list 'fact) (list (make-cell (procedure->expressed (make-closure '(i) (parse "if ...") )))) init-env)) ------------------------------------------ ------------------------------------------ FIXING IT (begin (set! init-env (extend-env (list 'fact) init-env)) ------------------------------------------ Does this work for mutual recursion? B. letrecproc Will the define trick work in a language with nested recursive procdures? 1. syntax ------------------------------------------ LETRECPROC Concrete syntax: ::= letrecproc in ::= {;}* ::= = Examples: letrecproc fact(x) = if zero(x) then 1 else *(x, fact(sub1(x))) in fact(342) Abstract syntax: (define-record letrecproc (procdecls body)) (define-record procdecl (var formals body)) ------------------------------------------ Why is this restricted to procedure declarations? 2. semantics as a syntactic sugar How could we give a semantics to letrecpoc? ------------------------------------------ SYNTACTIC SUGAR FOR LETRECPROC letrecproc ohNo (i) = wow(wow(i)); wow (x) = ohNo(ohNo(x)) in ohNo(2) ==> ------------------------------------------ How does this work? ------------------------------------------ CHANGES DUE TO LETRECPROC init-env [ *-]--> (extend-env (list 'add1 ...) (list (make-cell (procdure->expressed (make-prim-proc 'add1)) ...)) the-empty-env) env1 --> (extend-env (list 'ohNo 'wow) (list (make-cell (number->expressed 0)) (make-cell (number->expressed 0))) init-env) proc(i) wow(wow(i)) ==> (make-closure '(i) (parse "wow(wow(i))") _____) proc (x) ohNo(ohNo(x)) ==> (make-closure '(x) (parse "ohNo(ohNo(x))")))) _____) ------------------------------------------ How would you declare this example in C? 3. semantics without circular environments (optional) ------------------------------------------ SEMANTICS WITHOUT CIRCULAR ENVIRONMENTS (define-record extended-rec-env (vars vals oldenv)) (define extend-rec-env ;; TYPE: (-> ((list procdecl) ;; Environment) ;; Environment) (lambda (procdecls env) (make-extended-rec-env (map procdecl->var procdecls) (list->vector ; corrected! (map (lambda (procdecl) (make-proc (procdecl->formals procdecl) (procdecl->body procdecl))) procdecls)) env))) (define apply-env ;; TYPE: (-> (Environment symbol) ;; Expressed-Value) (lambda (env var) (variant-case env ; corrected below! (extended-rec-env (vars vals oldenv) (let ((p (ribassoc var vars vals '*fail*))) (if (eq? p '*fail*) (apply-env oldenv var) (else ...)))) ------------------------------------------ ------------------------------------------ ADDITION TO EVAL-EXP ;;; Figure 5.4.1 : page 154 (no cells!) (define eval-exp (lambda (exp env) (variant-case exp (letrecproc (procdecls body) ------------------------------------------ C. sugar for letrec with no defined order of evaluation (skip) ------------------------------------------ LETREC SUGAR WITH UNDEFINED EVAL ORDER letrec one2 = cons(1, begin print(12); proc() two1 end); two1 = cons(2, begin print(21); proc() one2 end) in car((cdr(one2))()) ==> let one2 = 0; two1 = 0 in begin let g104 = cons(1, begin print(12); proc() two1 end); g105 = cons(2, begin print(21); proc() one2 end) in begin one2 := g104; two1 := g105; 0 end; car((cdr(one2))()) end ------------------------------------------ with our current sugar, which should get printed first: 12 or 21? Do we want to say that in the language definition? What in Scheme doesn't have a defined order of evaluation? VIII. Dynamic Scope and Dynamic Assignment (5.7) A. utility of dynamic constructs ------------------------------------------ UTILITY OF DYNAMIC SCOPE/ASSIGNMENT (5.7) changing implicit parameters: let stdout = port in p(1,2) let font = italic in format(mytext) stdout := port during p(1,2) font := italic during 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. dynamic scope (5.7.1) 1. background 2. domains ------------------------------------------ DOMAINS FOR DYNAMIC SCOPING Environment = -> Denoted-Value Denoted-Value = Cell(Expressed-Value) Expressed-Value = Number + + List(Expressed-Value) + Void Procedure-Text = ------------------------------------------ What helper functions come with these domains? 3. interpreter Where will the procdure get its environment then? ------------------------------------------ INTERPRETER WITH DYNAMIC SCOPE (5.7.1) (define eval-exp (lambda (exp env) (variant-case exp (lit (datum) (number->expressed datum)) (varref (var) (denoted->expressed (apply-env env var))) (app (rator rands) (let ((proc (expressed->procedure-text (eval-exp rator env))) (args (eval-rands rands env))) (proc (formals body) (varassign (var exp) (void->expressed (cell-set! (apply-env env var) (eval-exp exp env)))) ;; ... (else (error "Invalid abstract syntax:" exp))))) ------------------------------------------ ------------------------------------------ APPLY-PROC FOR DYNAMIC SCOPE ;; abstract syntax of procedure texts (define-record proc (formals body)) ;; dynamic scoping version (define apply-proc (lambda (proc args (variant-case proc (prim-proc (prim-op) (apply-prim-op prim-op args)) (proc (formals body) (eval-exp body (extend-env formals (map expressed->denoted args) (else (error "Invalid procedure-text:" proc))))) ------------------------------------------ What is the domain Expressed-Value again? 4. behavior ------------------------------------------ BEHAVIOR WITH DYNAMIC SCOPE let three = 3 in let add3 = proc(i) +(i, three); three = 5 in *(three, add3(2)) ------------------------------------------ ------------------------------------------ DEFINITIONS A *dynamic binding* is extant References to a dynamically-bound variable refer to the ------------------------------------------ What's the difference from static scoping? ------------------------------------------ FOR YOU TO DO ;; Fig 5.7.3 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? ------------------------------------------ What kind of scoping does the Unix shell use? LaTeX? APL? 5. optimizing the interpreter, pages 169 (bottom) to 171 (skip) Which is faster for variable access, dynamic or static? Is there any way to speed up variable access with dynamic scope? 6. 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? 7. reasoning problems (pages 173ff) Is alpha conversion valid with dynamic scope? beta? eta? ------------------------------------------ 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)) ------------------------------------------ Could you do type checking at compile time if have dynamic scope? C. dynamic assignment 1. idea ------------------------------------------ EXTENT AND SCOPE def: the *extent* of a binding is It can be either - indefinite = - dynamic = ALTERNATIVES scope binding \ extent indefinite dynamic lexical dynamic ------------------------------------------ 2. syntax ------------------------------------------ DYNAMIC ASSIGNMENT Concrete syntax: ::= := during Examples: directory := codedir during compile() let x = 4 in let p = proc(y) +(y, x) in +(x := 7 during p(1), p(2)) abstract syntax: (define-record dynassign (var exp body)) ------------------------------------------ What environment is used to evaluate each ? 3. semantics How would you implement this? ------------------------------------------ IMPLEMENTATION (define eval-exp (lambda (exp env) (variant-case exp (lit (datum) (number->expressed datum)) ;; ... (dynassign (var exp body) (let ((v-cell (apply-env env var)) (saved-cell (make-cell (eval-exp exp env)))) ------------------------------------------ Why does the cell-swap! come after? D. evaluation Which is better: dynamic assignment or dynamic scoping?