I. inductively sets of data (EOPL2e 1.1) A. inductive specification ------------------------------------------ INDUCTIVE SPECIFICATION (1.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-of 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) (1.1.2) ------------------------------------------ BACKUS-NAUR FORM (BNF) (1.1.2) ::= ( ) ::= ( . ) Notation, terms: ::= syntactic category, non-terminal terminal rule, production ALTERNATIVE SHORTHAND ::= ( ) | ( . ) ------------------------------------------ ------------------------------------------ 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) ------------------------------------------ ------------------------------------------ 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 ::= - | _ | + | * | ? | / | ! | ::= | ::= {}* {}* ------------------------------------------ ------------------------------------------ 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 (1.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 (deftype count-sym-exp ------------------------------------------ ------------------------------------------ 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 (deftype count-sym-exp (-> (symbol sym-exp) number)) (define count-sym-exp ------------------------------------------ ------------------------------------------ MORE TIPS 5. One type, one grammar, one recursion. Don't mix 2 recursions in a procedure. 6. Recurse for each helping procedure. ------------------------------------------ --------------------------------------------------------- MORE TIPS 7. When debugging, work bottom up from subexpressions (define sym 'x) (define slist (parse-s-list '(y (x)))) (null? slist) (count-sym-exp (car slist)) (cdr slist) ... --------------------------------------------------------- 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 ------------------------------------------ ------------------------------------------ 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 (1.2.1) 1. recursion over flat lists ------------------------------------------ RECURSION PATTERNS THAT MATCH THE GRAMMAR FOR INPUT (insert-before 'x 'q '()) ==> () (insert-before 'x 'q '(x y z x)) ==> (q x y z x) (insert-before 'x 'q '(a x y z)) ==> (a q x y z) Grammar for input data: ::= () | ( . ) Outline that matches grammar: (deftype insert-before (-> (symbol symbol (list-of symbol)) (list-of symbol))) (define insert-before (lambda (where what los) ------------------------------------------ What examples are we missing? Which argument has an inductively specified type? ------------------------------------------ FOR YOU TO DO (IN PAIRS) (remove 'x 'q '()) ==> () (remove 'x 'q '(x y z x)) ==> (q x y z q x) (remove 'x 'q '(a x y z x)) ==> '(a q x y z q x) Any other examples you want? What's the type? What's the structure of the code? Write it! ------------------------------------------ How does this differ from insert-before? 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 ()))) ::= ( {}* ) ::= | (deftype subst (-> (symbol symbol (define subst ------------------------------------------ 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: (deftype remove-sym-exp (-> (symbol sym-exp) (list-of sym-exp))) (deftype remove-s-list (-> (symbol (list-of sym-exp)) (list-of 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-var-exps (parse-lambda-1-exp 'x)) ==> 1 (count-var-exps (parse-lambda-1-exp '(x y))) ==> 2 (count-var-exps (parse-lambda-1-exp '((x z) y))) ==> 3 (count-var-exps (parse-lambda-1-exp '(lambda (x) x))) ==> 1 (count-var-exps (parse-lambda-1-exp '(f (lambda (x) x)))) Grammar: (deftype count-var-exps (define count-var-exps (lambda (exp) ------------------------------------------ Would more examples help? What other questions should we ask? ------------------------------------------ FOR YOU TO DO (IN PAIRS) Using the helping procedures var-exp?, lambda-exp?, var-exp->var, lambda-exp->body, app-exp->rator, app-exp->rand, set, set-union write a procedure for: (deftype all-var-exps (-> (lambda-1-exp) (set-of symbol))) (all-var-exps (parse-lambda-1-exp 'x)) ==> (x) (all-var-exps (parse-lambda-1-exp '(x y))) ==> (x y) (all-var-exps (parse-lambda-1-exp '(lambda (x) y))) ==> (y) (all-var-exps (parse-lambda-1-exp '(f (lambda (x) (x (f x)))))) ==> (f x) Grammar: ::= | (lambda () ) | ( ) ------------------------------------------ How would this change if we added quote to the grammar? D. tail recursion (1.2.3) 1. motivation ------------- FIBONACCI NUMBERS Each pair of rabbits has 2 kids. Mate every month Bear young 2 months after birth # of pairs of rabbits: 1 ; end of month 1 1 ; end of month 2 2 = 1 + 1 ; month 3 3 = 1 + 2 ; month 4 5 = 2 + 3 ; month 5 8 = 3 + 5 ; month 6 13 = 5 + 8 ; month 7 ------------- How many at the end of month 8? ------------------------------------------ FULLY RECURSIVE VERSION (deftype fib (-> (number) number)) (define fib (lambda (n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2)))))) ------------------------------------------ 2. definition ------------------------------------------ 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 (deftype list-sum (-> ((list-of number)) number)) (define list-sum ; fully recursive (lambda (lon) (if (null? lon) 0 (+ (car lon) (list-sum (cdr lon)))))) (deftype list-sum (-> ((list-of number)) number)) (define list-sum ; tail recursive (lambda (lon) ------------------------------------------ ------------------------------------------ TAIL RECURSIVE VERSION OF FIB How would we design fib to be tail recursive? ------------------------------------------ ------------------------------------------ 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? 3. When to use tail recursion ------------------------------------------ WHEN TO USE TAIL RECURSION 1. When working with vectors or strings (deftype vector-sum (-> ((vector-of number)) number)) (define vector-sum (lambda (von) (partial-vector-sum von (vector-length von) 0))) (deftype partial-vector-sum (-> ((vector-of number) number number) number))) (define partial-vector-sum (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) (deftype list-product (-> ((list-of number)) number)) (define list-product (lambda (lon) (prod-iter lon 1))) (deftype (-> ((list-of number) number) number)) (define prod-iter (lambda (lon acc) (if (null? lon) acc (if (zero? (car lon)) 0 (prod-iter (cdr lon) (* acc (car lon))))))) ------------------------------------------ 4. correspondence to loops What in C/C++ is like a tail recursion? ------------------------------------------ CORRESPONDENCE TO WHILE LOOP struct Cons {int car; Cons *cdr}; // C++ int list_product(Cons *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))))))) ------------------------------------------ 5. when to use an accumulator ------------------------------------------ WHEN YOU NEED AN ACCUMULATOR When working with vectors, strings (deftype vector-sum (-> ((vector-of number)) number)) (define vector-sum (lambda (von) (partial-vector-sum von (vector-length von)))) (deftype partial-vector-sum (-> ((vector-of number) number) number) (define partial-vector-sum (lambda (von n) (if (zero? n) 0 (+ (vector-ref von (- n 1)) (partial-vector-sum von (- n 1)))))) ------------------------------------------ E. summary What are the key ideas for designing tail recursion? When should you use tail recursion? When shouldn't you use tail recursion? How do you design a fully recursive program? What are the questions to ask?