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)