I. inductively specified data (2.1) A. inductive specification ------------------------------------------ INDUCTIVE SPECIFICATION (2.1) EXAMPLES The set N of natural numbers is the smallest set such that: 1. 0 is in N 2. if i in N, then i+1 is in N Let Digit = {0,1,2,3,4,5,6,7,8,9} The set Numeral of numerals is the smallest set such that 1. 2. ------------------------------------------ Why isn't N = {..., -2, -1, 0, 1, 2, ...}? ------------------------------------------ FOR YOU TO DO Let symbol be the set of symbols. Specify the set (list symbol), i.e., the set of lists of symbols. ------------------------------------------ B. use of grammars in programming languages ------------------------------------------ THE USE OF GRAMMARS IN PROGRAMMING LANGUAGES In definition: !--------------------------------------! ! all strings over alphabet ! ! !---------------------------------! ! ! ! regular grammar ! ! ! ! !-----------------------------! ! ! ! ! ! context-free grammar ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !-----------------------------! ! ! ! !---------------------------------! ! !--------------------------------------! In implementation (parsing): input tokens ========> lexer ========> parser ! ! trees v code gen ! ! code v object module ------------------------------------------ Why do programming languages typically use 2 layers of grammar? C. Backus-Naur Form (BNF) (2.1.2) ------------------------------------------ BACKUS-NAUR FORM (BNF) (2.1.2) ::= ( ) ::= ( . ) Notation, terms: ::= syntactic category, non-terminal terminal rule, production ALTERNATIVE SHORTHAND ::= ( ) | ( . ) KLEENE STAR AND PLUS ::= ( {}* ) ::= ( {}+ ) ------------------------------------------ ------------------------------------------ KLEENE STAR AND PLUS USED IN REGULAR GRAMMARS ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 ::= {}+ ::= a | ... | z | A | ... | Z ::= - | _ | + | * | ? | / | ! | ::= | ::= {}* {}* ------------------------------------------ ------------------------------------------ FOR YOU TO DO Given and , write a grammar for that includes the following examples: 3 x (5 + 4) (x + ((7 * 8) / y)) (9 - z) ------------------------------------------ ------------------------------------------ DERIVATIONS Replace one non-terminal using a rule at each step Grammar: ::= ( ) | ( . ) Derivation of (fly): ==> Grammar: ::= ( {}* ) Derivation of (fly): ==> ------------------------------------------ how does this help in defining a programming language? ------------------------------------------ FOR YOU TO DO Consider the following grammar: ::= | | ( lambda ( {}+ ) ) | ( {}+ ) ::= ::= If the following are s, then give a derivation, else show why there is no derivation. a. x b. ((lambda (x) x) 3) c. f(3, 4) ------------------------------------------ D. Using BNF to specify data (2.1.3) ------------------------------------------ USING BNF TO SPECIFY DATA (2.1.3) ::= ( {}* ) ::= ( ) | ( . ) ::= ( . ) ::= ( . ) ::= ( . ( {}* )) ::= () | ::= ( . ) ::= ------------------------------------------ What would be the base case for a procedure that took a as an argument? What would the recursive case be? What are the cases for a ? What would the recursive case be? What are the cases for ? ------------------------------------------ SPECIFYING SCHEME DATA ::= | | | | | | | ::= ( {}* ) ::= ( . ) ::= #( {}* ) ::= ::= ------------------------------------------ How would you specify without using the Kleene star? ------------------------------------------ CONTEXT-FREE vs. CONTEXT-SENSITIVE ::= () | ( ::= ------------------------------------------ What would make this into a binary search tree? Is there any way to specify this in a context-free grammar? E. induction (2.1.4) (omit) II. recursively specified programs (2.2) A. tips (summary) ------------------------------------------ TIPS FOR REDUCING HOMEWORK TIME FOR RECURSIVE PROGRAMS 1. Write out your own examples if needed a. base case(s) b. related simpler example 2. What are the types? Write it down (define num-of ;; TYPE: ------------------------------------------ ------------------------------------------ TIPS CONTINUED 3. Use an outline that matches the grammar for the input data type. ::= | ::= ( {}* ) 4. Use helping procedures for the types. (load-from-lib (define num-of ;; TYPE:(-> (symbol sym-exp) ;; number) ------------------------------------------ ------------------------------------------ MORE TIPS 5. One type, one grammar, one recursion. Don't mix 2 recursions in a procedure. 6. Recurse for each helping procedure. ------------------------------------------ B. deriving recursive programs from examples ------------------------------------------ DERIVATION FROM RELATED EXAMPLES (fact 5) = 120 (fact 4) = 24 (fact 3) = 6 (fact 0) = 1 ------------------------------------------ What's the type? What are the cases? What is the answer for the base case? How to decompose? Where is the recursion? How do we get from the answer for the recursion to what we want? ------------------------------------------ HOW IT WORKS (fact 5) = ((lambda (n) (if ...)) 5) = (if (zero? 5) 1 (* 5 (fact (sub1 5)))) = (* 5 (fact (sub1 5))) = (* 5 (fact 4)) = (* 5 (* 4 (fact 3))) = (* 5 (* 4 (* 3 (fact 2)))) = (* 5 (* 4 (* 3 (* 2 (fact 1))))) = (* 5 (* 4 (* 3 (* 2 (* 1 (fact 0)))))) = (* 5 (* 4 (* 3 (* 2 (* 1 1))))) = (* 5 (* 4 (* 3 (* 2 1)))) = (* 5 (* 4 (* 3 2))) = (* 5 (* 4 6)) = (* 5 24) = 120 ------------------------------------------ ------------------------------------------ FLAT RECURSION ON LISTS (map add1 '(4 5 6)) ==> (5 6 7) (map add1 '(5 6)) ==> (6 7) (map add1 '(6)) ==> (7) (map add1 '()) ==> () (define map ;; TYPE: (-> ((-> (S) T) (list S)) ;; (list T)) (lambda (f ls) ------------------------------------------ What's the outline? how do you make 5 from 4? how do you make the list (5 6 7) from the lists (4 5 6) and (6 7)? ------------------------------------------ FOR YOU TO DO (IN PAIRS) (xerox '(3 9 2)) ==> (3 3 9 9 2 2) (xerox '(9 2)) ==> (9 9 2 2) (xerox '()) ==> () ------------------------------------------ What's a related example? What's the type? How do you make (3 9 9 2 2) from (3 9 2) and (9 9 2 2)? How do you make (3 3 9 9 2 2) from (3 9 2) and (3 9 9 2 2)? C. deriving programs from BNF specifications of argument types (2.2.1) 1. recursion over flat lists ------------------------------------------ RECURSION PATTERNS THAT MATCH THE GRAMMAR FOR INPUT (remove-first 'x '()) ==> () (remove-first 'x '(x y z x)) ==> (y z x) (remove-first 'x '(a x y z)) ==> (a y z) Grammar for input data: ::= () | ( . ) Outline that matches grammar: (define remove-first ;; TYPE: (-> (symbol (list symbol)) ;; (list symbol)) (lambda (s los) ------------------------------------------ What examples are we missing? Which argument has an inductively specified type? ------------------------------------------ FOR YOU TO DO (IN PAIRS) (remove 'x '()) ==> () (remove 'x '(x y z x)) ==> (y z) (remove 'x '(a x y z x)) ==> (a y z) Any other examples you want? What's the type? What's the structure of the code? Write it! ------------------------------------------ How does this differ from remove-first? 2. recursion over s-lists and sym-exps (trees) ------------------------------------------ S-LIST AND SYM-EXP RECURSION (subst 'x 'y (parse-s-list '())) ==> () (subst 'k 'a (parse-s-list '(a b c d a))) ==> (k b c d k) (subst 'b 'a (parse-s-list '((a a) (c)))) ==> ((b b) (c)) (subst 'k 'a (parse-s-list '(a ((b () a)) ((a ()))))) ==> (k ((b () k)) ((k ()))) ::= ( {}* ) ::= | (define subst ;; TYPE: (-> (symbol symbol ------------------------------------------ any other examples we could use? What's the type? What does the grammar tell us about cases? recursion? ------------------------------------------ FOR YOU TO DO (IN PAIRS) Using the sym-exp helpers. Write: remove-sym-exp : (-> (symbol sym-exp) (list sym-exp)) remove-s-list : (-> (symbol (list sym-exp)) (list (list sym-exp))) Examples: (remove-sym-exp 'z (parse-sym-exp 'a)) ==> (a) (remove-sym-exp 'z (parse-sym-exp 'z)) ==> () (remove-sym-exp 'z (parse-sym-exp '())) ==> (()) (remove-sym-exp 'z (parse-sym-exp '(w z (y z) () (x)))) ==> ((w (y) () (x))) (remove-s-list 'z (parse-s-list '())) ==> (()) (remove-s-list 'z (parse-s-list '(z (y z) () (x)))) ==> (((y) () (x))) ------------------------------------------ 3. using map 4. recursion over lambda calculus grammar ------------------------------------------ RECURSION OVER LAMBDA-1 (count-varrefs (parse-lambda-1 'x))) ==> 1 (count-varrefs (parse-lambda-1 '(x y))) ==> 2 (count-varrefs (parse-lambda-1 '(lambda (x) x))) ==> 1 (count-varrefs (parse-lambda-1 '(f (lambda (x) x)))) Grammar: (define count-varrefs ;; TYPE: (lambda (exp) ------------------------------------------ Would more examples help? What other questions should we ask? ------------------------------------------ FOR YOU TO DO (IN PAIRS) Using the helping procedures varref?, lambda?, varref->var, lambda->body, app->rator, app->rand, set-of, set-union write a procedure for: (all-varrefs (parse-lambda-1 'x)) ==> (x) (all-varrefs (parse-lambda-1 '(x y))) ==> (x y) (all-varrefs (parse-lambda-1 '(lambda (x) y))) ==> (y) (all-varrefs (parse-lambda-1 '(f (lambda (x) (x (f x)))))) ==> (f x) Grammar: ::= | (lambda () ) | ( ) ::= ::= ------------------------------------------ How would this change if we added quote to the grammar? D. tail recursion (p. 50) ------------------------------------------ FULL vs. TAIL RECURSION def: a procedure is tail recursive if full recursion trace: (list-sum '(3 5 7)) = (+ 3 (list-sum '(5 7))) = (+ 3 (+ 5 (list-sum '(7)))) = (+ 3 (+ 5 (+ 7 (list-sum '())))) = (+ 3 (+ 5 (+ 7 0))) = (+ 3 (+ 5 7)) = (+ 3 12) = 15 tail recursion trace: (list-sum '(3 5 7)) = (list-sum-iter '(3 5 7) 0) = (list-sum-iter '(5 7) 3) = (list-sum-iter '(7) 8) = (list-sum-iter '() 15) = 15 ------------------------------------------ Which of these is more like a while loop? ------------------------------------------ FULL vs. TAIL RECURSION (define list-sum ; fully recursive ;; TYPE: (-> ((list number)) number) (lambda (lon) (if (null? lon) 0 (+ (car lon) (list-sum (cdr lon)))))) (define list-sum ; tail recursive ;; TYPE: (-> ((list number)) number) (lambda (lon) ------------------------------------------ ------------------------------------------ FOR YOU TO DO (IN PAIRS) Write a tail-recursive procedure for: (reverse '()) ==> () (reverse '(a b c)) ==> (c b a) (reverse '(x y z h)) ==> (h z y x) ------------------------------------------ do our questions still work? ------------------------------------------ WHEN YOU NEED AN ACCUMULATOR When working with vectors (define vector-sum ;; TYPE: (-> ((vector number)) number) (lambda (von) (partial-vector-sum von (vector-length von)))) (define partial-vector-sum ;; TYPE: (-> ((vector number) number) ;; number) (lambda (von n) (if (zero? n) 0 (+ (vector-ref von (- n 1)) (partial-vector-sum von (- n 1)))))) ------------------------------------------ ------------------------------------------ WHEN TO USE TAIL RECURSION 1. When working with strings or vectors (define vector-sum ;; TYPE: (-> ((vector number)) number) (lambda (von) (partial-vector-sum von (vector-length von) 0))) (define partial-vector-sum ;; TYPE: (-> ((vector number) number ;; number) ;; number) (lambda (von n acc) (if (zero? n) (partial-vector-sum von (- n 1)) (+ (vector-ref von (- n 1)) acc)))) ------------------------------------------ ------------------------------------------ WHEN TO USE TAIL RECURSION 2. To return directly to caller (since no pending computations) (define list-product ;; TYPE: (-> ((list number)) number) (lambda (lon) (prod-iter lon 1))) (define 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))))))) ------------------------------------------ What in C/C++ is like a tail recursion? ------------------------------------------ CORRESPONDENCE TO WHILE LOOP struct Cons {int car; Cons *cdr}; // C++ typedef Cons *ConsPtr; int list_product(ConsPtr *lon) { int acc = 1; while (!(lon == NULL)) { if (lon->car == 0) { return 0; } else { acc = acc * lon->car; lon = lon->cdr; } } return acc; } (define list-product ; Scheme (lambda (lon) (prod-iter lon 1))) (define prod-iter (lambda (lon acc) (if (null? lon) acc (if (zero? (car lon)) 0 (prod-iter (cdr lon) (* acc (car lon))))))) ------------------------------------------ E. summary What are the key ideas for designing tail recursion? When should you use tail recursion? How do you design a fully recursive program? What are the questions to ask?