Some Scheme Greg Sullivan 16.410/16.413 September 8, 2004 / 2 Outline ? ? A mix of Scheme- general programming tutorial Procedures – recursion – lists – structures specific details, and Sept. 8, 2003 16.410 16.413 Intro. to Scheme Scheme syntax ?Data 1 Programming Languages ? Control – Conditionals – Loops – Functions, function calls – Exceptions – Threads ?Data – Scalars: booleans, numbers, strings – Records / Structures – Classes, types Sept. 8, 2003 16.410/16.413 Intro. to Scheme 3 / 4 Scheme A language for describing computational processes: – Governed by rules for: expression has a value, 1. Syntax: Legal expressions have rules by which they are constructed from simpler pieces. 2. Semantics “evaluated”. 3. Every value has a Sept. 8, 2003 16.410 16.413 Intro. to Scheme Precise sequence of steps used to infer new information from a set of data. : (Almost) every which is “returned” when an expression is type. 2 Syntax constants / scalars abstractions (functions) (“self-evaluating”) (lambda (x) (+ x 1) 42, “hello, world”, function calls 3.1415, #t, #f (+ x 4) definitions (define succ (lambda (x) (+ x )) (+ (succ x) 4) (define x 32) “special forms” (keyword …) variable references (if (> x max) x max), (set! x 44) x (let ((x 5)) (+ x 3)), etc. Sept. 8, 2003 16.410/16.413 Intro. to Scheme 5 / 6 Read-Eval-Print Execution world (+ 3 (* 4 5)) PRINT 23 EVAL Applies rules READ Sept. 8, 2003 16.410 16.413 Intro. to Scheme Visible world Internal representation for expression Visible world Value of expression 3 / 7 Language elements – combinations / applications / function calls ? applies a procedure to a set of arguments: (+ 2 3) ? getting values of sub- expressions, then applying operator to values of arguments is a procedure Close paren A combination Evaluate by Sept. 8, 2003 16.410 16.413 Intro. to Scheme Open paren Expression whose value Other expressions / 8 Mathematical operators are just names (+ 3 5) ? 8 ? undef ? 10 fred (define + *) (+ 3 4) (define fred +) (fred 4 6) ? How do we explain this? ? + is bound to a value which is a procedure Sept. 8, 2003 16.410 16.413 Intro. to Scheme ?+ is just a name ? line 2 binds the name to that same value ? Even more surprising: 4 / 9 Language elements – Procedural abstraction ? use procedures To process something parameters body as a value. Need to capture ways of doing things – multiply it by itself ?Special form – creates a procedure and returns it Sept. 8, 2003 16.410 16.413 Intro. to Scheme (lambda (x) (* x x)) Language elements – Procedural abstraction ? Use a lambda expression anywhere you would use a procedure ((lambda (x) (* x x)) 5) ? Can give it a name – (define square (lambda (x) (* x x))) – (square 5) ? 25 ? (define (f x y z) …)) is shorthand for (define f (lambda (x y z) …)) – (define (square x) (* x x)) Sept. 8, 2003 16.410/16.413 Intro. to Scheme 10 5 / Procedures are Values Too ? (define twice (lambda (f x) (f (f x)))) ? (twice square 2) = ? 11 Sept. 8, 2003 16.410 16.413 Intro. to Scheme / A less trivial procedure: factorial ? (if (= 4 4) 2 3) ==> 2 (if (= 4 5) 2 3) ==> 3 (= 4 4) ==> #t ) (= 4 5) ==> #f (define fact (lambda (n) (if (= n 1) 1 ( ( ) ( Compute n factorial, defined as n! = n(n-1)(n-2)(n-3)...1 ?if special form ?predicate = (false) n-1 12 )! Sept. 8, 2003 16.410 16.413 Intro. to Scheme predicate consequent alternative tests numerical equality (true (* n (fact (- n 1)))))) ?Notice that n! = n * [ n-1) n-2 ...] = n * if n > 1 6 / (fact 3) (* 3 (fact 2)) (* 3 (* 2 (fact 1))) (* 3 (* 2 1)) (* 3 2) 6 13 Sept. 8, 2003 16.410 16.413 Intro. to Scheme (if (= 3 1) 1 (* 3 (fact (- 3 1)))) (if #f 1 (* 3 (fact (- 3 1)))) (* 3 (fact (- 3 1))) (* 3 (if (= 2 1) 1 (* 2 (fact (- 2 1))))) (* 3 (if #f 1 (* 2 (fact (- 2 1))))) (* 3 (* 2 (fact (- 2 1)))) (* 3 (* 2 (if (= 1 1) 1 (* 1 (fact (- 1 1)))))) (* 3 (* 2 (if #t 1 (* 1 (fact (- 1 1)))))) (define fact(lambda (n) (if (= n 1)1(* n (fact (- n 1)))))) / algorithms 1. wishful thinking 2. decompose the problem 1. Wishful thinking – – assume it exists. smaller version of the problem. How to design recursive want to implement fact? – BUT, only solves a 14 OK, Sept. 8, 2003 16.410 16.413 Intro. to Scheme ? follow the general pattern: 3. identify non-decomposable (smallest) problems Assume the desired procedure exists. 7 / 2. Decompose the problem 1. solve a smaller instance (using wishful thinking) 2. creativity! design the strategy before coding. (n-1)! – (define fact convert the smaller solutions to the desired solution – n! = n(n-1)(n-2)... = n[(n-1)(n-2)...] = n * solve the smaller instance, multiply it by n to get solution 15 Sept. 8, 2003 16.410 16.413 Intro. to Scheme ? Solve a problem by ? Step 2 requires –Must (lambda (n) (* n (fact (- n 1))))) / 3. Identify non-decomposable problems ? by itself and solve directly. ? ( ) ( ( Decomposing not enough identify the "smallest" problems Define 1! = 1 = n 1 16 ) 1 Sept. 8, 2003 16.410 16.413 Intro. to Scheme ?Must AKA “the base case”. define fact (lambda (n (if * n (fact (- n 1))))) 8 / General form of recursive algorithms , base case, recursive case ( ) ) 1 : ? smallest (non-decomposable) problem recursive case: larger (decomposable) problem 17 ))) ? base case Sept. 8, 2003 16.410 16.413 Intro. to Scheme ?test define fact (lambda (n (if (= n 1 ; test for base case ; base case (* n (fact (- n 1)) ; recursive case Avoiding Recursion ? In factorial, * was pending for each level of (define (fact n) (let loop ((n n) (answer 1)) 18 recursion. Consumes stack space. – How can we avoid that? (if (= n 1) answer (loop (- n 1) (* answer n))))) Sept. 8, 2003 16.410/16.413 Intro. to Scheme 9 / Iteration as Recursion ? ? (define (fact n) (letrec ((fact-helper (lambda (n answer) answer (fact-helper n 1))) Scheme uses “tail call optimization” A tail call is a call with nothing left but to return the answer. (if (= n 1) 19 Sept. 8, 2003 16.410 16.413 Intro. to Scheme (fact-helper (- n 1) (* answer n)))))) / Outline ? ? A mix of Scheme- general programming tutorial Procedures – recursion – lists – structures specific details, and 20 Sept. 8, 2003 16.410 16.413 Intro. to Scheme Scheme syntax ?Data 10 Pairs, Lists car cdr ? (cons 1 2) => (1 . 2) 1 2 ?() car cdr car cdr ? (cons 1 (cons 2 ())) 1 2 () ? (list 1 2) ? ‘(1 2) ? (pair? (cons 1 2)) (pair? (list 1 2 3)) => #t ? (list? (cons 1 2) => #f /Sept. 8, 2003 16.410 16.413 Intro. to Scheme 21 / Sum a list ? return sum. ?1 st (define (sum l) (if (null? l) 0 (+ (car l) (sum (cdr l))))) Assuming list is a flat list of numbers, (define (sum l) …) solution – use recursion. 22 Sept. 8, 2003 16.410 16.413 Intro. to Scheme 11 / Sum list, iterative version ? (define (sum l) (let loop ((l l) (answer 0)) answer (loop (cdr l) (+ answer (car l)))))) Now construct an iterative version (if (null? l) 23 Sept. 8, 2003 16.410 16.413 Intro. to Scheme / ? ? (fold operator initial-value list) (fold + 0 ‘(1 2 3 4)) = 10 (define (fold op initial l) (if (null? l) initial (op (car l) (fold op initial (cdr l))))) (define (list-product l) (fold * 1 l)) How about list product? Abstract from list sum. 24 Sept. 8, 2003 16.410 16.413 Intro. to Scheme 12 / Trees ? – Tree<C> = List<Tree<C>> | Leaf<C> – Leaf<C> = C ? – leaf? – countleaves, scaletree 2 4 6 8 2 6 8 4 root subtrees Type Definition: Examples: 25 Sept. 8, 2003 16.410 16.413 Intro. to Scheme Operations: children or / countleaves – base case: count of an empty tree is 0 – base case: count of a leaf is 1 – Implementation: ? Strategy recursive strategy: the count of a tree is the sum of the countleaves of each child in the tree. 26 Sept. 8, 2003 16.410 16.413 Intro. to Scheme (define (countleaves tree) (cond ((null? tree) 0) ;base case ((leaf? tree) 1) ;base case (else ;recursive case (+ (countleaves (car tree)) (countleaves (cdr tree)))))) (define (leaf? x) (not (pair? x))) 13 / The End Still to come: ? ? Structures / Records Exceptions (continuations) 27 Sept. 8, 2003 16.410 16.413 Intro. to Scheme ?Macros / car car car car cdr cdr cdr cdr 28 Sept. 8, 2003 16.410 16.413 Intro. to Scheme 14 list-ref ? ; return nth, 0-based, element of l ; #f if n > (length l) (define (list-ref l n) … ) (define (list-ref l n) (cond ((null? l) #f) ((= 0 n) (car l)) (else (list-ref (cdr l) (- n 1))))) /Sept. 8, 2003 16.410 16.413 Intro. to Scheme 29 / The Define special form ? define-rule: (define <name> <value expression>) – – – (define pi 3.14) e v a l d e f i n e -r u l e p r i n t ? world ? world "pi --> 3.14" name pi 3.14 Environment visible execution undefined value 30 Sept. 8, 2003 16.410 16.413 Intro. to Scheme evaluate 2nd operand only, returning a value. name in 1st operand position is bound to that value. returned value of the define expression is undefined scheme versions differ 15