I. syntax abstraction (SICP p. 11) ------------------------------------------ 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? Which is the sugar, the shorter, less tedious version, or the translation? II. logical connectives (SICP, p. 19; Little Schemer, chapter 2) ------------------------------------------ LOGICAL CONNECTIVES problem: verbosity (deftype member? (forall (T) (-> (T (list-of T)) boolean))) (define member? (lambda (e ls) (if (not (null? ls)) (if (equal? e (car ls)) #t (member? e (cdr ls))) #f))) solution: (define member? (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" (deftype foo? (-> (datum) boolean)) (define foo? (lambda (x) (if (pair? x) (if (number? (car x)) #t (number? (cdr x))) #f))) Define the predicate (deftype two-elem-list? (-> (datum) boolean) to test whether a datum is a list of length two. ------------------------------------------ III. branching (SICP 1.1.6, Little Lisper, chapter 2) A. cond ------------------------------------------ COND problem: - nested ifs are hard to read - they don't match grammar well (deftype count-varrefs (-> (lambda-exp) number)) (define count-varrefs (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 (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 (skip, we won't need this) ------------------------------------------ CASE 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))) ------------------------------------------ IV. local binding constructs A. let (SICP pp. 63-64) ------------------------------------------ THE PROBLEMS SOLVED BY LET (double-reverse-sublist '((a b) (c d))) ==> ((b a) (b a) (d c) (d c)) (deftype double-reverse-sublist (forall (T) (-> ((list-of (list-of T))) (list-of (list-of T))))) (define (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 (deftype double-reverse-sublist (forall (T) (-> ((list-of (list-of T))) (list-of (list-of T))))) (define double-reverse-sublist (lambda (lst) (if (null? lst) '() ------------------------------------------ ------------------------------------------ SUBSTITUTING THE DEFINITION OF CONS-TWICE (deftype double-reverse-sublist (forall (T) (-> ((list-of (list-of T))) (list-of (list-of T))))) (define double-reverse-sublist (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 (deftype double-reverse-sublist (forall (T) (-> ((list-of (list-of T))) (list-of (list-of T))))) (define double-reverse-sublist (lambda (lst) (if (null? lst) '() (cons elem (cons elem ls)) ;; or more usually... (define double-reverse-sublist (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 (SICP p. 391, EOPL p. 23) ------------------------------------------ LET HELPS AVOID NAMESPACE CLUTTER (deftype circle-area (-> (number number) number)) (define circle-area (let ((pi 3.14159)) (lambda (radius) (* pi (* radius radius))))) ------------------------------------------ ------------------------------------------ DOES LET WORK FOR PROCEDURES? (deftype list-product (-> ((list-of number)) number)) (define list-product (let ((prod-iter (has-type (-> ((list-of 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 (deftype list-product (-> ((list-of number)) number)) (define list-product (letrec ((prod-iter (has-type (-> ((list-of 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? (has-type (-> (number) boolean) (lambda (n) (if (zero? n) (even? (- n 1)))))) (even? (has-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 (deftype subst (-> (symbol symbol (list-of symbol)) (list-of symbol))) (define subst ------------------------------------------ ------------------------------------------ FOR YOU TO DO (IN PAIRS) Using a letrec, define: expt: (-> (number) number) Examples: (expt 4 0) = 1 (expt 3 1) = 3 (expt 3 2) = 9 (expt 3 3) = 27 ------------------------------------------ 3. 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? V. The define sugar in Scheme A. problem ------------------------------------------ PROBLEM Tedious syntax, common pattern (define square (lambda (x) (* x x))) (define compose (lambda (f g) (lambda (x) (f (g x))))) ------------------------------------------ ------------------------------------------ SUGAR FOR DEFINE IN SCHEME (define (square x) (* x x)) (define (compose f g) (lambda (x) (f (g x)))) Desugaring rule: (define (name v1 ...) body) ==> ------------------------------------------ What are the advantages of this? 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?