X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=week4.mdwn;h=150e88354cd7f8b56884ffe201e3afd1255693ba;hp=bc154aea1195830c5858a716055ec250c4229a3e;hb=ca367b32e54d5816fcea12dd590a76306901d1ae;hpb=5fa25870987fce498870f06907422cee6a0bb8b1
diff --git a/week4.mdwn b/week4.mdwn
index bc154aea..150e8835 100644
--- a/week4.mdwn
+++ b/week4.mdwn
@@ -276,6 +276,35 @@ can just deliver that answer, and not branch into any further recursion. If
you've got the right evaluation strategy in place, everything will work out
fine.
+--
+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..
+
+--
+
But what if you're using v3 lists? What options would you have then for
aborting a search?