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? How could we avoid the repition in inductive specifictions? 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 for reducing time What were the tips for reducing time on recursive list problems? ------------------------------------------ MORE TIPS FOR SAVING TIME WHEN DOING RECURSIVE PROBLEMS 6. Assume a parser handles syntax errors in input. 7. Use helping procedures to access parts of the syntax. 8. One procedure per nonterminal. Don't mix 2 recursions in a procedure. 9. Use these tips for each procedure you write ------------------------------------------ B. multiple alternatives, helpers ------------------------------------------ ASSUME A PARSER ::= hot | warm | cold Parsing (parse-temperature 'hot) ==> hot (parse-temperature 'warm) ==> warm (parse-temperature 'cold) ==> cold (parse-temperature 'tepid) ~~> error (parse-temperature 23) ~~> error ------------------------------------------ So, when you have a procedure that takes a input, what can you assume about that input? ------------------------------------------ USE HELPING PROCEDURES (require (lib "temperature-mod.scm" "lib342")) Constructors: hot : (-> () temperature) warm : (-> () temperature) cold : (-> () temperature) Tests (discriminators): hot? : (-> (temperature) boolean) warm? : (-> (temperature) boolean) cold? : (-> (temperature) boolean) Comments to aid memory ::= hot "hot ()" | warm "warm ()" | cold "cold ()" ------------------------------------------ ------------------------------------------ FOLLOW THE GRAMMAR Problem: (make-warmer (parse-temperature 'cold)) ==> warm (make-warmer (parse-temperature 'warm)) ==> hot (make-warmer (parse-temperature 'hot)) ==> hot ------------------------------------------ What's the type? What's the outline? Can you write it? C. multiple nonterminals, no recursion (skip if low on time) ------------------------------------------ PHONE NUMBER GRAMMAR ::= ( . ) "phone-number (exchange subscriber)" ::= "exchange (number)" ::= "subscriber (number)" ------------------------------------------ ------------------------------------------ HELPING PROCEDURES In phone-number-mod.scm: phone-number : (-> (exchange subscriber) phone-number) exchange : (-> (number) exchange) subscriber : (-> (number) subscriber) phone-number->exchange : (-> (phone-number) exchange) phone-number->subscriber : (-> (phone-number) subscriber) exchange->number : (-> (exchange) number) subscriber->number : (-> (subscriber) number) ------------------------------------------ ------------------------------------------ FOR YOU TO DO Write to-string : (-> (phone-number) string) (to-string (parse-phone-number (555 . 1212))) ==> "555-1212" ------------------------------------------ D. multiple alternatives ------------------------------------------ LAMBDA-1-EXP GRAMMAR ::= "var-exp (id)" | ( lambda ( ) ) "lambda-exp (id body)" | ( ) "app-exp (rator rand)" ------------------------------------------ Does this look like anything familiar? ------------------------------------------ HELPING PROCEDURES FOR LAMBDA-1 var-exp? : (-> (lambda-1-exp) boolean) lambda-exp? : (-> (lambda-1-exp) boolean) app-exp? : (-> (lambda-1-exp) boolean) var-exp->id : (-> (lambda-1-exp) symbol) lambda-exp->id : (-> (lambda-1-exp) symbol) lambda-exp->body : (-> (lambda-1-exp) lambda-1-exp) app-exp->rator : (-> (lambda-1-exp) lambda-1-exp) app-exp->rand : (-> (lambda-1-exp) lambda-1-exp) var-exp : (-> (symbol) lambda-1-exp) lambda-exp : (-> (symbol lambda-1-exp) lambda-1-exp) app-exp : (-> (lambda-1-exp lambda-1-exp) lambda-1-exp) ------------------------------------------ Which are tests? Constructors? Observers? ------------------------------------------ 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)))) ==> 2 (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, and set-union write a procedure for: 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) ------------------------------------------ How would this change if we added quote to the grammar? E. combinations ------------------------------------------ STATEMENTS AND EXPRESSIONS ::= "exp-stmt (exp)" | (set! ) "set-stmt (id exp)" ::= "var-exp (id)" | "num-exp (num)" | (begin {}* ) "begin-exp (stmts exp)" where is a Scheme ------------------------------------------ What are the helping procedures? How does this recurse? How many procedures would we use to solve a problem over this grammar? ------------------------------------------ EXAMPLE PROBLEM targets : (-> (statement) (set-of symbol)) (targets (parse-statement 'x)) = (set ) (targets (parse-statement '(set! x 3))) = (set x) (targets (parse-statement '(set! x (begin (set! y 4) y)))) = (set x y) ------------------------------------------ What are the base cases? What other examples would be useful? Any related simpler examples? How many procedures? What are examples for the other procedure? III. tail recursion (1.2.3) A. 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)))))) ------------------------------------------ B. 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? C. 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))))))) ------------------------------------------ D. 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))))))) ------------------------------------------ E. 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)))))) ------------------------------------------ F. 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?