X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=topics%2Fweek4_fixed_point_combinators.mdwn;h=ed22cfff6225d1841de515a7e2821532aa29be39;hp=601ad813bdd87e87521b80a0965e8803cbc1219a;hb=6694165ac4d6edab602b3ad3651d0a5931b36a0e;hpb=a29958c3e11fa8ae383aacff54ce7f405def0705;ds=sidebyside diff --git a/topics/week4_fixed_point_combinators.mdwn b/topics/week4_fixed_point_combinators.mdwn index 601ad813..ed22cfff 100644 --- a/topics/week4_fixed_point_combinators.mdwn +++ b/topics/week4_fixed_point_combinators.mdwn @@ -293,6 +293,7 @@ The strategy we will present will turn out to be a general way of finding a fixed point for any lambda term. + ## Deriving Y, a fixed point combinator ## How shall we begin? Well, we need to find an argument to supply to @@ -533,7 +534,7 @@ to *the tail* of the list we were evaluating its application to at the previous ## Fixed-point Combinators Are a Bit Intoxicating ## -[[tatto|/images/y-combinator-fixed.jpg]] +[[tatto|/images/y-combinator-fixed.png]] There's a tendency for people to say "Y-combinator" to refer to fixed-point combinators generally. We'll probably fall into that usage ourselves. Speaking correctly, though, the Y-combinator is only one of many fixed-point combinators. @@ -553,9 +554,9 @@ then this is a fixed-point combinator: For those of you who like to watch ultra slow-mo movies of bullets piercing apples, here's a stepwise computation of the application of a recursive function. We'll use a function `sink`, which takes one -argument. If the argument is boolean true (i.e., `\x y. x`), it +argument. If the argument is boolean true (i.e., `\y n. y`), it returns itself (a copy of `sink`); if the argument is boolean false -(`\x y. y`), it returns `I`. That is, we want the following behavior: +(`\y n. n`), it returns `I`. That is, we want the following behavior: sink false <~~> I sink true false <~~> I