X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=advanced_lambda.mdwn;h=d23245cfdd88f2e8ecc4fd9e0cdea9e954199b19;hp=6760ae7f17256bbe596cdece2eac41aac5b6d299;hb=dc9298c6718ec9bc63550ec6bc6b5a187f235e50;hpb=0a6cb8dd4a9460b13006f75f6a5b84d434aba212 diff --git a/advanced_lambda.mdwn b/advanced_lambda.mdwn index 6760ae7f..d23245cf 100644 --- a/advanced_lambda.mdwn +++ b/advanced_lambda.mdwn @@ -3,31 +3,7 @@ #Version 4 lists: Efficiently extracting tails# -An advantage of the v3 lists and v3 (aka "Church") numerals is that they -have a recursive capacity built into their skeleton. So for many natural -operations on them, you won't need to use a fixed point combinator. Why is -that an advantage? Well, if you use a fixed point combinator, then the terms -you get -won't be strongly normalizing: whether their reduction stops at a normal form -will depend on what evaluation order you use. Our online [[lambda evaluator]] -uses normal-order reduction, so it finds a normal form if there's one to be -had. But if you want to build lambda terms in, say, Scheme, and you wanted to -roll your own recursion as we've been doing, rather than relying on Scheme's -native `let rec` or `define`, then you can't use the fixed-point combinators -`Y` or `Θ`. Expressions using them will have non-terminating -reductions, with Scheme's eager/call-by-value strategy. There are other -fixed-point combinators you can use with Scheme (in the [week 3 notes](/week3/#index7h2) they -were `Y′` and `Θ′`. But even with -them, evaluation order still matters: for some (admittedly unusual) -evaluation strategies, expressions using them will also be non-terminating. - -The fixed-point combinators may be the conceptual stars. They are cool and -mathematically elegant. But for efficiency and implementation elegance, it's -best to know how to do as much as you can without them. (Also, that knowledge -could carry over to settings where the fixed point combinators are in -principle unavailable.) - -This is why the v3 lists and numbers are so lovely. However, one disadvantage +Version 3 lists and Church numerals are lovely, because they have their recursive capacity built into their very bones. However, one disadvantage to them is that it's relatively inefficient to extract a list's tail, or get a number's predecessor. To get the tail of the list `[a;b;c;d;e]`, one will basically be performing some operation that builds up the tail afresh: at