) Abstraction Elements of a Language(or Engineering Design) Primitives, means of combination means of abstraction What weve seen Procedural Abstraction. ambda-captures common patterns and Deep question #2: Functional programming substitution model Are there things we can't compute Conventional interfaces Deep question #3 list-oriented programming Where does our comp nal power higher order procedures (of recursion) come from (2)Data, State and Objects (3)Language Design and Implementation Data Abstraction Evaluation-meta-circular evaluator Primitive, Compound, Symbolic Data eval& apply Contracts, Abstract Data Types lazy evaluatio Mutation: need ironment model dynamic scoping list structured data and memory management Deep question Some Simple Procedures define(1。op- forever)(1。op- forever)) every expression stand for a va ( return-s 9 rever returns Expression does not stand for a value not well defi
1 1 6.001 SICP Computability • What we've seen... • Deep question #1: • Does every expression stand for a value? • Deep question #2: • Are there things we can't compute? • Deep question #3: • Where does our computational power (of recursion) come from? 2 (1) Abstraction • Elements of a Language (or Engineering Design) • Primitives, means of combination, means of abstraction • Procedural Abstraction: • Lambda – captures common patterns and "how to" knowledge • Functional programming & substitution model • Conventional interfaces: • list-oriented programming • higher order procedures 3 (2) Data, State and Objects • Data Abstraction • Primitive, Compound, & Symbolic Data • Contracts, Abstract Data Types • Selectors, constructors, operators, ... • Mutation: need for environment model • Managing complexity • modularity • data directed programming • object oriented programming 4 (3) Language Design and Implementation • Evaluation – meta-circular evaluator • eval & apply • Language extensions & design • lazy evaluation • dynamic scoping • Register machines • ec-eval and universal machines • compilation • list structured data and memory management 5 Deep Question #1 Does every expression stand for a value? 6 Some Simple Procedures • Consider the following procedures (define (return-seven) (+ 3 4)) (define (loop-forever) (loop-forever)) • So (return-seven) 7 (loop-forever) [never returns!] • Expression (loop-forever) does not stand for a value; not well defined
Deep Question #2 Mysteries of Infinity Countability Two sets of numbers(or other objects) are said to have the them. this means each element in the first set Are there well-defined things that to exactly one element in the second set, cannot be compute Any set of same cardinality as the integers is called integers)same size as (even integers): n> 2n (integers)same size as(squares): n>n2 integers) same size as (rational numbers) Countable- rational numbers Uncountable- real numbers As many integers as rational numbers(no more, no less). The eal numbers between o and 1 is uncountable f: Represent a real number by its decimal expansion 111y1如15/16/17/1 ly require an infinite number of digits), e.g. 0.49373 Assume there are a countable number of such numbers Then can arbitrarily number them, as in this table: 51/52/53/54/55/56/57/5 #20.33333333 ng between the set of rationals and set of integers as move alon countability is false, re more reals than integers There are more functions than programs halts? There are a countable number of procedures: e.g. can write Even simple procedures can cause deep difficulties every program in a binary(integer)form, 100110100110 to check procedures before running Assume there are a countable number of predicate them to catch accidental infinite loops nctions, i.e. mappings from an integer arg to the value 0 or 1. Then we can arbitrarily number these functions Assume a procedure halts? exists halts? p) →舞ff 010 halts? is well specified-has a clear value for its inputs function by complementing the diagonals. By construction (halts? return-seven) #t this predicate cannot be in the list(of all integers, of all halts? loop-forever) #f programs). Thus there are more predicate functions than there are procedures erin, Kaiser, and Kngh, Concede Abstradiors, p. 114, P 1999
2 7 Deep Question #2 Are there well-defined things that cannot be computed? 8 Mysteries of Infinity: Countability • Two sets of numbers (or other objects) are said to have the same cardinality (or size) if there is a one-to-one mapping between them. This means each element in the first set matches to exactly one element in the second set, and vice versa. • Any set of same cardinality as the integers is called countable. • {integers} same size as {even integers}: n 2n • {integers} same size as {squares}: nn2 • {integers} same size as {rational numbers} 9 Countable – rational numbers • As many integers as rational numbers (no more, no less). Proof: 1 2 3 4 5 6 7… 1 1/1 2/1 3/1 4/1 5/1 6/1 7/1 … 2 1/2 2/2 3/2 4/2 5/2 6/2 7/2 … 3 1/3 2/3 3/3 4/3 5/3 6/3 7/3 … 4 1/4 2/4 3/4 4/4 5/4 6/4 7/4 … 5 1/5 2/5 3/5 4/5 5/5 6/5 7/5 … • Mapping between the set of rationals and set of integers – match integers to rationals starting from 1 as move along line 10 Uncountable – real numbers • The set of real numbers between 0 and 1 is uncountable, i.e. there are more of them than there are integers: • Proof: Represent a real number by its decimal expansion (may require an infinite number of digits), e.g. 0.49373 • Assume there are a countable number of such numbers. Then can arbitrarily number them, as in this table: #1 0. 4 9 3 7 3 0 0 0 ... #2 0. 3 3 3 3 3 3 3 3 ... #3 0. 5 8 7 5 3 2 1 4 ... • Pick a new number by adding 1 (modulo 10) to every element on the diagonal, e.g. 0.437... becomes 0.548… This number cannot be in the list! The assumption of countability is false, and there are more reals than integers 11 There are more functions than programs • There are a countable number of procedures: e.g. can write every program in a binary (integer) form, 100110100110 • Assume there are a countable number of predicate functions, i.e. mappings from an integer arg to the value 0 or 1. Then we can arbitrarily number these functions: #1 0 1 0 1 1 0 … #2 1 1 0 1 0 1 … #3 0 0 1 0 1 0 … • Use Cantor Diagonalization again! Define a new predicate function by complementing the diagonals. By construction this predicate cannot be in the list (of all integers, of all programs). Thus there are more predicate functions than there are procedures. 12 halts? • Even simple procedures can cause deep difficulties. Suppose we wanted to check procedures before running them to catch accidental infinite loops. • Assume a procedure halts? exists: (halts? p) #t if (p) terminates #f if (p) does not terminate • halts? is well specified – has a clear value for its inputs (halts? return-seven) #t (halts? loop-forever) #f Halperin, Kaiser, and Knight, "Concrete Abstractions," p. 114, ITP 1999
The Halting Theorem: Procedure halts? cannot exist. Too bad! Proof (informal): Assume halts? exists as specified. (define (contradict-halts) (if (halts? contradict-halts) Where does the power of recursion come from? (loop-forever) ??? Wow! If contradict-halts halts, then it loops forever. ontradiction! Assumption that halts? exists must be wrong From Whence recursion? Infinite Recursion without Define Perhaps the ability comes from the ability to dEFINE a We have notion of lambda, which abstracts out the patten procedure and call that pr Example: the infinite loop as the purest or simplest ((1 ambda(1。p)(1。ep)) (lambda (loop) (loop))) define(loop)(1。p)) Can we generate recursion without DEFINE-ie is Not quite: problem is that loop requires one argument, and omething other than the power to name at the heart of the first app n is okay, but the second one isnt recursion? →((1 ambda(p)(。op)) missing arg Infinite Recursion without Define Harnessing recursion Better is recursion But do we still (((h)(hh)): an anonymous infinite loop eed the power to name(define)in order to do anything λh)chh))) For example, computing factorials h))) (if (=n o) 《H →【H (* n (fact ( )))) →(HH Can we compute factorials without explicitly "naming "such Can generate infinite recursion with only lambda apply
3 13 The Halting Theorem: Procedure halts? cannot exist. Too bad! • Proof (informal): Assume halts? exists as specified. (define (contradict-halts) (if (halts? contradict-halts) (loop-forever) #t)) (contradict-halts) ?????? • Wow! If contradict-halts halts, then it loops forever. • Contradiction! Assumption that halts? exists must be wrong. 14 Deep Question #3 Where does the power of recursion come from? 15 From Whence Recursion? • Perhaps the ability comes from the ability to DEFINE a procedure and call that procedure from within itself? • Example: the infinite loop as the purest or simplest invocation of recursion: (define (loop) (loop)) • Can we generate recursion without DEFINE – i.e. is something other than the power to name at the heart of recursion? 16 Infinite Recursion without Define • We have notion of lambda, which abstracts out the pattern of computation and parameterizes that computation. Perhaps try: ((lambda (loop) (loop)) (lambda (loop) (loop))) • Not quite: problem is that loop requires one argument, and the first application is okay, but the second one isn't: ((lambda (loop) (loop)) ____ ) ; missing arg 17 • Better is .... ((λ(h) (h h)) ; an anonymous infinite loop! (λ(h) (h h))) • Run the substitution model: ((λ(h) (h h)) (λ(h) (h h))) = (H H) (H H) (H H) ... • Can generate infinite recursion with only lambda & apply Infinite Recursion without Define H (shorthand) 18 Harnessing recursion • So lambda (not naming) gives us recursion. But do we still need the power to name (define) in order to do anything practical or useful? • For example, computing factorials: (define (fact n) (if (= n 0) 1 (* n (fact (- n 1))))) • Can we compute factorials without explicitly "naming" such a procedure?
Harnessing our anonymous recursion o we s We need to subdue the infinite recursion how to λ(h)[hh)) prevent (o Q)from spinning out of control? We'd like to do something each time we recurse: (λh)((x)((f(hh))x)) a)((h)) h)(2(x)((f(hh))x)) (o Q) 0(x)((f(DD))x)) (f (f(o Q))) b: ((r (DD))x) E(QQ)).. So our first step in least it generates the"stack up So(dD)results in something very finite-a proc p"of f as That procedure object has the germ or seed (DD) inside we expect in recursion it- the potential for further recursion Parameterize(capture f) (QQ) In our funky recursive form(DD), f is a free variable →(f【(..((QQ))..) λ(h)((x)(fchh))x))) a(h)((x)((fchh))x)))) D e: it ev is tD ftse by sel ((x)(((DD))x)) Can clean this up: formally parameterize what we have so B: (ur (DD)】x》 (DD) temporarily halts the recursion and gives λ(f)((h)((x)(f(hh))x)) echanism to control that recursion: λ(h)(λ(x)((fchh))x))) 1. trigger proc body by applying it to number 2. Let f decide what to do- call other procedures The Y Combinator How to Design F to Work with Y? ((f)(((h) ((x) ((f (hh))x))) (Y F)=(D λ(h)0λ(x)((f(hh))x)))) design F so that we control the recursion. What (Y F)=(DD When we feed (Y E)a number, what happens b:((2 (DD))x) (YF)# →(# F should take a proc efore. but now f is bour form e. When we b:((F (D D))x) 2.(F proc)should eval to a re get th →(F20) controlled recursive capability we saw earli number
4 19 ((λ(h) (h h)) ; our anonymous infinite loop (λ(h) (h h))) • We'd like to do something each time we recurse: ((λ(h) (f (h h))) (λ(h) (f (h h)))) = (Q Q) Harnessing our anonymous recursion Q (shorthand) (f (Q Q)) (f (f (Q Q))) (f (f (f ... (f (Q Q))..) • So our first step in harnessing recursion results in infinite recursion... but at least it generates the "stack up" of f as we expect in recursion 20 • We need to subdue the infinite recursion – how to prevent (Q Q) from spinning out of control? ((λ(h) (λ(x) ((f (h h)) x))) (λ(h) (λ(x) ((f (h h)) x)))) = (D D) (λ(x) ((f (D D)) x)) How do we stop the recursion? p: x b: ((f (D D)) x) • So (D D) results in something very finite – a procedure! • That procedure object has the germ or seed (D D) inside it – the potential for further recursion! 21 (Q Q) (f (f (f ... (f (Q Q))..) (D D) (λ(x) ((f (D D)) x)) Compare p: x b: ((f (D D)) x) • (Q Q) is uncontrolled by f; it evals to itself by itself • (D D) temporarily halts the recursion and gives us mechanism to control that recursion: 1. trigger proc body by applying it to number 2. Let f decide what to do – call other procedures 22 • In our funky recursive form (D D), f is a free variable: ((λ(h) (λ(x) ((f (h h)) x))) (λ(h) (λ(x) ((f (h h)) x)))) = (D D) • Can clean this up: formally parameterize what we have so it can take f as an argument: (λ(f) ((λ(h) (λ(x) ((f (h h)) x))) (λ(h) (λ(x) ((f (h h)) x))))) = Y Parameterize (capture f) 23 (λ(f) ((λ(h) (λ(x) ((f (h h)) x))) (λ(h) (λ(x) ((f (h h)) x))))) = Y • So (Y F) = (D D) as before, but now f is bound to some form F. When we use the Y combinator on a procedure F, we get the controlled recursive capability of (D D) we saw earlier. The Y Combinator p: x b: ((F (D D)) x) 24 (Y F) = (D D) • Want to design F so that we control the recursion. What form should F take? • When we feed (Y F) a number, what happens? ((Y F) #) ( #) ((F ) #) How to Design F to Work with Y? p: x b: ((F (D D)) x) p: x b: ((F (D D)) x) 1. F should take a proc 2. (F proc) should eval to a procedure that takes a number p: x b: ((F (D D)) x)
Implication of 2: F Can End the Recursion Example: An f that Terminates a recursion P: uIR ((proc) ((F OA B (λ(n)(if(=n0)1..))0) If we write e to bottom out for some values of n ))) Lets ve can implement a base case Implication of 1: F Should have Proc as Arg Implication of 1: F should have Proc as Arg The more complicated(confusing) issue is how to arrange Question is: how do we appropriately use proc inside E for F to take a proc of the form we need: (# We need F to conform to: (Ep0)0) b:((E [DD)) x) ((E(D A magine that F uses this proc somewhere inside itself (proc λ(n)(if(=n0)1..))#) 主f(=#0) (n) (if (= n o) Good! We get the eval of the inner body of F with n=# Implication of 1: F should have Proc as Arg So What is proc? Lets repeat that. Consider our procedure (proc # -when called inside the body of F (if ( n o) is just the inner body of F with n=#, and proc= (*n(proc(-n1)))))) So consider ld! It requires a very complicated b: ((E (DD)) x) er for everything to work recursively as (if (= n 0) get this complicated proc? Y makes (*n(pr(-n1)))))) B:( DD》》x)
5 25 ((F ) #) Implication of 2: F Can End the Recursion p: x b: ((F (D D)) x) F = (λ(proc) (λ(n) ...)) • Can use this to complete a computation, depending on value of n: F = (λ(proc) (λ(n) (if (= n 0) 1 ...))) Let's try it! 26 F = (λ(proc) (λ(n) (if (= n 0) 1 ...))) So ((F ) 0) ((λ(n) (if (= n 0) 1 ...)) 0) 1 • If we write F to bottom out for some values of n, we can implement a base case! Example: An F That Terminates a Recursion p: x b: ((F (D D)) x) 27 • The more complicated (confusing) issue is how to arrange for F to take a proc of the form we need: We need F to conform to: ((F ) 0) • Imagine that F uses this proc somewhere inside itself F = (λ(proc) (λ(n) (if (= n 0) 1 ... (proc #) ...))) = (λ(proc) (λ(n) (if (= n 0) 1 ... ( #) ...))) Implication of 1: F Should have Proc as Arg p: x b: ((F (D D)) x) p: x b: ((F (D D)) x) 28 • Question is: how do we appropriately use proc inside F? • Well, when we use proc, what happens? ( #) ((F (D D)) #) ((F ) #) ((λ(n) (if (= n 0) 1 ...)) #) (if (= # 0) 1 ...) Good! We get the eval of the inner body of F with n=# Implication of 1: F Should have Proc as Arg p: x b: ((F (D D)) x) p: x b: ((F (D D)) x) 29 • Let's repeat that: (proc #) -- when called inside the body of F ( #) is just the inner body of F with n = #, and proc = • So consider F = (λ(proc) (λ(n) (if (= n 0) 1 (* n (proc (- n 1)))))) Implication of 1: F Should have Proc as Arg p: x b: ((F (D D)) x) p: x b: ((F (D D)) x) 30 • Consider our procedure F = (λ(proc) (λ(n) (if (= n 0) 1 (* n (proc (- n 1)))))) • This is pretty wild! It requires a very complicated form for proc in order for everything to work recursively as desired. • How do we get this complicated proc? Y makes it for us! (Y F) = (D D) => = proc So What is proc? p: x b: ((F (D D)) x)
Putting it all together Y Combinator: the Essence of recursion (xF)10) (《()(ah)a(x)(E(hh))x))) (￥F)x)=((DD)x)=((F(YF))x) (h)a(x)((f(hh))x)))) The power of controlled recursion λ(fact) No define- on (if (= n o) lambda and the power *n(fact(-n1)))))) λ()((h)((((hh)x) 3 f(hh)) x))))) The Power and its limits to control infinite recursion one step at a time But there are limits- remember the halting theoren Y人
6 31 Putting it all together ( (Y F) 10) = ( ((λ(f) ((λ(h) (λ(x) ((f (h h)) x))) (λ(h) (λ(x) ((f (h h)) x))))) (λ(fact) (λ(n) (if (= n 0) 1 (* n (fact (- n 1))))))) 10) (* 10 (* ... (* 3 (* 2 (* 1 1))) 3628800 No define – only lambda and the power of Y combinator! 32 Y Combinator: The Essence of Recursion ((Y F) x) = ((D D) x) = ((F (Y F)) x) The power of controlled recursion! (λ(f) ((λ(h) (λ(x) ((f (h h)) x))) (λ(h) (λ(x) ((f (h h)) x))))) 33 The Power and Its Limits • λ empowers you to capture knowledge • Y empowers you to reach toward the infinite – to control infinite recursion one step at a time • But there are limits – remember the halting theorem! 34