I. orientation ------------------------------------------ WHERE ARE WE? Chapters 1-2.2 basic concepts in languages functional programming (in Scheme) 2.3 lambda calculus, var bindings, scope 3 syntax abstraction data abstraction 4 reasoning about procedures imperative programming 5 interpreter basics 6 parameter passing 7 OO features ------------------------------------------ II. syntax abstraction (EOPL 3) ------------------------------------------ THE IDEA OF SYNTAX ABSTRACTION problem: users doing same thing over and over making local bindings deeply nesting if expressions ... but it's solution: examples: terms: syntactic sugar syntax abstraction macro desugaring ------------------------------------------ How is this like procedural abstraction? How is this like data abstraction? Which is the sugar, the shorter, less tedious version, or the translation? III. local binding constructs (3.1) A. let (3.1.1) ------------------------------------------ THE PROBLEMS SOLVED BY LET (double-reverse-sublist '((a b) (c d))) ==> ((b a) (b a) (d c) (d c)) (define double-reverse-sublist ;; TYPE: (-> ((list (list T))) ;; (list (list T))) (lambda (lst) (if (null? lst) '() (cons (reverse (car lst)) (cons (reverse (car lst)) (double-reverse-sublist (cdr lst))))))) problems: ------------------------------------------ What's the time complexity of reverse? How much slower is the code than it would be if didn't have to repeat that computation? What mechanism do we have, so far, that binds names to values? ------------------------------------------ REWRITES TO AVOID REPEATED COMPUTATION (define double-reverse-sublist ;; TYPE: (-> ((list (list T))) ;; (list (list T))) (lambda (lst) (if (null? lst) '() ------------------------------------------ ------------------------------------------ SUBSTITUTING THE DEFINITION OF CONS-TWICE (define double-reverse-sublist ;; TYPE: (-> ((list (list T))) ;; (list (list T))) (lambda (lst) (if (null? lst) '() ((lambda (elem ls) (cons elem (cons elem ls))) (reverse (car lst)) (double-reverse-sublist (cdr lst)))))) ------------------------------------------ What do other languages do to avoid recomputation? ------------------------------------------ USING LET (define double-reverse-sublist ;; TYPE: (-> ((list (list T))) ;; (list (list T))) (lambda (lst) (if (null? lst) '() (cons elem (cons elem ls)) ;; or more usually... (define double-reverse-sublist ;; TYPE: (-> ((list (list T))) ;; (list (list T))) (lambda (lst) (if (null? lst) '() (cons elem (cons elem (double-reverse-sublist (cdr lst)))) ------------------------------------------ What is this like in other langauges? ------------------------------------------ SYNTAX OF LET ::= | ... SEMANTICS OF LET (let ((var1 exp1) ... (varn expn)) body) = ------------------------------------------ What is this equal to? ------------------------------------------ FOR YOU TO DO (IN PAIRS) 1. What is the difference between the following? (define x 9) (let ((x 3)) (let ((y (+ x 4))) (* x y))) ; and (define x 9) (let ((x 3) (y (+ x 4))) (* x y)) Hints: what is the desugared form? draw arrows from the varrefs to the var declarations. ------------------------------------------ How would you define the region of a var decl in a let? the scope? B. letrec (3.1.2) ------------------------------------------ LET HELPS AVOID NAMESPACE CLUTTER (define circle-area ;; TYPE: (-> (number number) number) (let ((pi 3.14159)) (lambda (radius) (* pi (* radius radius))))) ------------------------------------------ ------------------------------------------ DOES LET WORK FOR PROCEDURES? (define list-product ;; TYPE: (-> ((list number)) number) (let ((prod-iter ;; TYPE: (-> ((list number) number) ;; number) (lambda (lon acc) (if (null? lon) acc (if (zero? (car lon)) 0 (prod-iter (cdr lon) (* acc (car lon)))))))) (lambda (lon) (prod-iter lon 1)))) ------------------------------------------ What does the recursive call of prod-iter refer to? Why doesn't that work? 1. syntax ------------------------------------------ LETREC (define list-product ;; TYPE: (-> ((list number)) number) (letrec ((prod-iter ;; TYPE: (-> ((list number) number) ;; number) (lambda (lon acc) (if (null? lon) acc (if (zero? (car lon)) 0 (prod-iter (cdr lon) (* acc (car lon)))))))) (lambda (lon) (prod-iter lon 1)))) SYNTAX ::= | ... ::= (lambda ) ::= ({}*) | ::= ------------------------------------------ How are local declarations of recursive procedures handled in other langauges? Is there any difference from Scheme? ------------------------------------------ FOR YOU TO DO (IN PAIRS) fill in the following, so that it returns the indicated value (letrec ((odd? ;; TYPE: (-> (number) boolean) (lambda (n) (if (zero? n) (even? (- n 1))))) (even? ;; TYPE: (-> (number) boolean) (odd? (- n 1)) )) (list (odd? 227) (even? 342))) ==> (#t #t) ------------------------------------------ 2. advantages and disadvantages ------------------------------------------ ADVANTAGES OF USING LETREC - namespace control - avoid passing (define subst ------------------------------------------ ------------------------------------------ FOR YOU TO DO (IN PAIRS) Using tail-recursion and a letrec, define: expt: (-> (number) number) Examples: (expt 4 0) = 1 (expt 3 1) = 3 (expt 3 2) = 9 (expt 3 3) = 27 ------------------------------------------ 3. free and bound variables ------------------------------------------ FREE VARIABLES IN LET AND LETREC x \in FV(E) if E is (let ((v1 E1) (v2 E2) ... (vn En)) B) and x \in FV(E) if E is (letrec ((v1 E1) (v2 E2) ... (vn En)) B) and FOR YOU TO DO Define the BV(E) when E is a let or letrec ------------------------------------------ 4. summary What is the region of a variable definition in a let compared to a letrec? What are the advantages of using letrec? Any disadvantages? 5. semantics (optional) ------------------------------------------ SEMANTICS OF LETREC Want it to be a syntactic sugar. So want some Y such that: (letrec ((var lexp)) body) = (let ((var (Y lexp))) body) Y should have "unrolling property": ((Y lexp) arg ...) = (lexp[(Y lexp)/var] arg ...) This allows one to expand out enough recursive calls to evaluate a call. ------------------------------------------ ------------------------------------------ UNROLLINGS (letrec ((fact ;; TYPE: (-> (number) number) (lambda (n) (if (zero? n) 1 (* n (fact (- n 1))))))) (fact 3)) = ((Y (lambda (n) (if (zero? n) 1 (* n (fact (- n 1)))))) 3) = ((lambda (n) (if (zero? n) 1 (* n ((Y (lambda (n) (if (zero? n) 1 (* n (fact (- n 1)))))) (- n 1))))) 3) = (* 3 ((Y (lambda (n) (if (zero? n) 1 (* n (fact (- n 1)))))) 2)) ------------------------------------------ What's this if we unroll it again? ------------------------------------------ MAKING Y PRACTICAL Y has to satisfy the unrolling property: ((Y lexp) args) = (lexp[(Y lexp)/var] args) But this isn't a sugar yet, because - haven't written Y yet - can't write it, because Y doesn't have access to the code in lexp in order to do the substitution. Solution: - pass (lambda (var) lexp) to Y, so can make substitution, because ((lambda (var) lexp) z) = lexp[z/var] ------------------------------------------ ------------------------------------------ THE NEW SUGAR (letrec ((var lexp)) body) = (let ((var (Y (lambda (var) lexp)))) body) Y must satisfy: ((Y (lambda (var) lexp)) arg ...) = (lexp[(Y (lambda (var) lexp))/var] arg ...) = letting g = (lambda (var) lexp), Y must satisfy: ((Y g) arg ...) = (g (Y g) arg ...) So just use that to define it: (define Y ;; TYPE: (-> ((-> ((-> (datum ...) T)) ;; (-> (datum ...) T))) ;; (-> (datum ...) T)) (lambda (g) (lambda args (apply (g (Y g)) args)))) ------------------------------------------ does Y have the unrolling property? ------------------------------------------ EXAMPLE (define fact-gen ;; TYPE: (-> ((-> (number) number)) ;; (-> (number) number)) (lambda (f) (lambda (n) (if (zero? n) 1 (* n (f (- n 1))))))) (let ((fact (Y fact-gen))) (fact 2)) = ((Y fact-gen) 2) = ((fact-gen (Y fact-gen)) 2) = ((lambda (n) (if (zero? n) 1 (* n ((Y fact-gen) (- n 1))))) 2) = (* 2 ((Y fact-gen) 1)) ------------------------------------------ a. multiple bindings (can omit) ------------------------------------------ SEMANTICS FOR MULTIPLE BINDINGS (letrec ((var1 exp1) ... (varn expn)) body) = (let ((*list-of-defs* (Y (lambda (*list-of-defs*) (list (apply (lambda (var1 ... varn) exp1) *list-of-defs*) ... (apply (lambda (var1 ... varn) expn) *list-of-defs*) ))))) (apply (lambda (var1 ... varn) body) *list-of-defs*)) where *list-of-defs* is not free in the original letrec. ------------------------------------------ IV. logical connectives (3.2) ------------------------------------------ LOGICAL CONNECTIVES (3.2) problem: verbosity (define member? ;; TYPE: (-> (T (list T)) boolean) (lambda (e ls) (if (not (null? ls)) (if (equal? e (car ls)) #t (member? e (cdr ls))) #f))) solution: (define member? ;; TYPE: (-> (T (list T)) boolean) (lambda (e ls) TERMS short-circuit evaluation conditional-evaluation ------------------------------------------ Can or evaluate all its arguments? What would happen? ------------------------------------------ SYNTAX OF LOGICAL CONNECTIVES ::= SEMANTICS ------------------------------------------ What's this like in other languages? in C? in Pascal? ------------------------------------------ FOR YOU TO DO Rewrite the following using "and" and "or" (define foo? ;; TYPE: (-> (datum) boolean) (lambda (x) (if (pair? x) (if (number? (car x)) #t (number? (cdr x))) #f))) Define the predicate is-application? : (-> (datum) boolean) to test whether a datum is a list of length two. ------------------------------------------ V. branching (3.3) A. cond (3.3.1) ------------------------------------------ COND (3.3) problem: - nested ifs are hard to read - they don't match grammar well (define count-varrefs ;; TYPE: (-> (lambda-exp) number) (lambda (exp) (if (varref? exp) 1 (if (lambda? exp) (count-varrefs (lambda->body exp)) (+ (count-varrefs (app->rator exp)) (count-varrefs (app->rand exp))))))) (define count-varrefs ;; TYPE: (-> (lambda-exp) number) (lambda (exp) ------------------------------------------ How would you write this in C or C++? ------------------------------------------ SYNTAX ::= ( cond {}+ ) ::= ( ) ::= ( else ) ::= ::= SEMANTICS (cond (test1 body1) (test2 body2) ... (testn bodyn) (else bodye)) ------------------------------------------ B. case (3.3.2) ------------------------------------------ CASE (3.3.2) problem: comparing the value of expression to many numbers, chars, symbols is tedious (let ((pos (list-index x ls))) (cond ((= pos 0) 'first) ((= pos 1) 'second) ((= pos 2) 'third) ((or (= pos 3) (= pos 4)) 'higher) (else 'too-high))) ------------------------------------------ What's this like in C/C++? In Pascal? What's different about this from the C/C++ statement? ------------------------------------------ SYNTAX ::= ( case {}+ ) ::= ( ) ::= ( {}+ ) ::= | | ::= ( else ) ::= SEMANTICS (let ((*key* e)) (case e (cond (kl1 b1) ((memv *key* 'kl1) b1) (kl2 b2) ((memv *key* 'kl2) b2) ... ... (kln bn) ((memv *key* 'kl3) b3) (else be)) (else be))) ------------------------------------------ can you do exercises 3.3.3 and 3.3.4? VI. summary of syntax abstraction A. translational or sugaring approach to extending languages ------------------------------------------ MAKING THE LANGUAGE SWEETER Syntactic abstraction = syntactic sugar problem: solution: advantages: ------------------------------------------ What statements in C are defined by syntactic sugar in this way? B. automation principle ------------------------------------------ AUTOMATION PRINCIPLE A language should automate Examples: Bonus: ------------------------------------------ What examples have we seen?