Some scheme Greg Sullivan 16410/16413 September 8, 2004 Outline Scheme syntax · Procedures A mix of scheme- recursion specific details, and general programming tutorial lists struct sept.8,2003 16.41016.413 Intro. to scheme 2
Some Scheme Greg Sullivan 16.410/16.413 September 8, 2004 / 2 Outline • • A mix of Schemegeneral 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 Functions function calls Threads Data Scalars: booleans, numbers, strings Records/ structures Classes, types sept.8.2003 16.41016.413 Intro. to scheme Scheme A language for describing computational processes Precise sequence of steps used to infer new information from a set of data Governed by rules for: 1. Syntax: Legal expressions have rules by which they are constructed from simpler pieces 2. Semantics:(Almost)every expression has a value which is "returned"when an expression is evaluated 3. Every value has a type. sept.8,2003 16.41016.413 Intro. to scheme
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”) ambda(x)(什x1) 42. hello, world function calls 3.1415,#,# (+(succ x)4) (define X 32) “ special forms”( keyword…) variable references (if ( x max)x max),(set! X 44) t X sept.8.2003 16.41016.413 Intro. to scheme Read-Eval-Print Visible world (+3(*45) READ repres EVAL Applies rules Value of ey Execution world PRINT sept.8,2003 16.41016.413 Intro. to scheme 3
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
Language elements combinations / applications function calls A combination applies a procedure to a set of arguments +23) Close paren Other expressions Open paren Expression whose value Evaluate by getting values of sub expressions, then applying operator to values of arguments sept.8.2003 16.41016.413 Intro. to scheme Mathematical operators are just names (+35) 今8 (define fred + undef (fred 4 6) 10 .+ Is Just a name is bound to a value which is a procedure line 2 binds the name fred to that same value · Even more surprising (define+*) (+34) sept.8,2003 16.41016.413 Intro. to scheme
/ 7 Language elements – combinations / applications / function calls • applies a procedure to a set of arguments: (+ 2 3) • getting values of subexpressions, 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
Language elements Procedural abstraction Need to capture ways of doing things use procedures parameters (lambda(x)(xx)k body To process something multiply it by itself Special form -creates a procedure and returns it as a value sept.8.2003 16.41016.413 Intro. to scheme 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)3 25 (define(fx y z..))is shorthand (define f(lambda(xy z).) (define (square X)C*XX) sept.8,2003 16.410/16.413 Intro. to scheme 5
/ 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)=? sept.8.2003 16.41016.413 Intro to Scheme A less trivial procedure: factorial Compute n factorial, defined as n! n(n-1)(n-2)(n-3).1 (n-1)(n-2).]=n*(n-1)!ifn>1 (define fact 主 (*n(f ests numerical equality (=44)==>#t true false) 主f(= Sept. 8, 2003 predicate 16.410/1604194qtlbe Schemalternative
/ Procedures are Values Too • (define twice (lambda (f x) (f (f x)))) • (twice square 2) = ? Sept. 8, 2003 16.410 16.413 Intro. to Scheme 11 / 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 predicate consequent 16.410 16.413 Intro. to Scheme alternative tests numerical equality (true (* n (fact (- n 1)))))) •Notice that n! = n * [ n-1) n-2 ...] = n * if n > 1 6
(define fact(lambda (n) (if(=n1)1(*n(fact(-n1)))))) (fact 3) 主f(=31)1(*3(fact(-31)))) (主f#f1(*3(fact(-31)))) (*3(fact(-31))) (*3(act2)) (*3(￡(=21)1(*2(fact(-21))))) (★3(主f#￡1(★2(￡act(-21))))) (*3(*2(fact(-21)))) (*3(*2(fact1))) (*3(*2(if(=11)1(*1(￡act(-11)))))) (★3(★2(￡#1(*1(fact(-11)))))) (*3(*21)) sept.8.2003 16.41016.413 Intro to Scheme How to design recursive algorithms follow the general pattern 1. wishful thinking 2. decompose the problem 3. identify non-decomposable(smallest) problems 1. Wishful thinking Assume the desired procedure exists want to implement fact? OK, assume it exists BUT, only solves a smaller version of the problem sept.8,2003 16.41016.413 Intro. to scheme
/ (fact 3) (* 3 (fact 2)) (* 3 (* 2 (fact 1))) (* 3 (* 2 1)) (* 3 2) 6 Sept. 8, 2003 16.410 16.413 Intro. to Scheme 13 (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 Solve a problem by 1. solve a smaller instance (using wishful thinking) 2. convert the smaller solutions to the desired solution Step 2 requires creativity Must design the strategy before coding n!=n(n-1)(n-2)…=n[(n-1)(n2).]=n*(n-1)! solve the smaller instance, multiply it by n to get solution (define fact lambda(n)( n (fact(n 1)) sept.8.2003 16.41016.413 Intro to Scheme 3. Identify non-decomposable problems Decomposing not enough by itself Must identify the"smallest"problems and solve directly. AKa the base case Define 1!=1 (define fact lambda( if(=n1)1 (*n(fact(-n1))) sept.8,2003 16.41016.413 Intro. to scheme 8
/ 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 Sept. 8, 2003 16.410 16.413 Intro. to Scheme 15 • 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 test base case. recursive case (define fact (lambda(n) (if( n 1) test for base case base case (n (fact(-n 1)); recursive case base case: smallest(non-decomposable) problem recursive case: larger(decomposable) problem sept.8.2003 16.41016.413 Intro to Scheme Avoiding Recursion In factorial, was pending for each level recursion. Consumes stack space How can we avoid that? (define(fact n let loop(n n)(answer 1)) f(=n1) answer (loop(n 1)(answer n)) sept.8,2003 16.410/16.413 Intro. to scheme 9
/ 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 Scheme uses tail call optimization A tail call is a call with nothing left but to return the answer (define(fact n (letrec((fact-helper (lambda(n answer) f(=n1) answer (fact-helper(n 1)(answer n)) (fact-helper n 1)) sept.8.2003 16.41016.413 Intro to Scheme Outline Scheme syntax · Procedures A mix of scheme- recursion specific details, and Data general programming tutorial lists structure sept.8,2003 16.41016.413 Intro. to scheme 10
/ 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) Sept. 8, 2003 16.410 16.413 Intro. to Scheme 19 (fact-helper (- n 1) (* answer n)))))) / Outline • • A mix of Schemegeneral programming tutorial Procedures – recursion – lists – structures specific details, and Sept. 8, 2003 16.410 16.413 Intro. to Scheme 20 Scheme syntax • Data 10