X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?a=blobdiff_plain;ds=inline;f=advanced_lambda.mdwn;h=d23245cfdd88f2e8ecc4fd9e0cdea9e954199b19;hb=40f8c745a271a15e718e2a52a94f4ef27a152d80;hp=6760ae7f17256bbe596cdece2eac41aac5b6d299;hpb=6c76653f70358ec2dd633335e378bf8ef98fe215;p=lambda.git
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