lambda_advanced.mdwn

   1 #Miscellaneous challenges and advanced topics, for untyped lambda calculus#
   2
   3 1.      How would you define an operation to reverse a list? (Don't peek at the
   4 [[lambda_library]]! Try to figure it out on your own.) Choose whichever
   5 implementation of list you like. Even then, there are various strategies you
   6 can use.
   7
   8
   9 2.      An advantage of the v3 lists and v3 (aka "Church") numerals is that they
  10         have a recursive capacity built into their skeleton. So for many natural
  11         operations on them, you won't need to use a fixed point combinator. Why is
  12         that an advantage? Well, if you use a fixed point combinator, then the terms
  13         you get
  14         won't be strongly normalizing: whether their reduction stops at a normal form
  15         will depend on what evaluation order you use. Our online [[lambda evaluator]]
  16         uses normal-order reduction, so it finds a normal form if there's one to be
  17         had. But if you want to build lambda terms in, say, Scheme, and you wanted to
  18         roll your own recursion as we've been doing, rather than relying on Scheme's
  19         native `let rec` or `define`, then you can't use the fixed-point combinators
  20         `Y` or <code>&Theta;</code>. Expressions using them will have non-terminating
  21         reductions, with Scheme's eager/call-by-value strategy. There are other
  22         fixed-point combinators you can use with Scheme (in the [[week 3]] notes they
  23         were <code>Y&prime;</code> and <code>&Theta;&prime;</code>. But even with
  24         those evaluation order still matters: for some (admittedly unusual)
  25         evaluation strategies, expressions using them will also be non-terminating.
  26
  27         The fixed-point combinators may be the conceptual heros. They are cool and
  28         mathematically elegant. But for efficiency and implementation elegance, it's
  29         best to know how to do as much as you can without them. (Also, that knowledge
  30         could carry over to settings where the fixed point combinators are in
  31         principle unavailable.)
  32
  33         This is why the v3 lists and numbers are so lovely. However, one disadvantage
  34         to them is that it's relatively inefficient to extract a list's tail, or get a
  35         number's predecessor. To get the tail of the list [a;b;c;d;e], one will
  36         basically be performing some operation that builds up the tail afresh: at
  37         different stages, one will have built up [e], then [d;e], then [c;d;e], and
  38         finally [b;c;d;e]. With short lists, this is no problem, but with longer lists
  39         it takes longer and longer. And it may waste more of your computer's memory
  40         than you'd like. Similarly for obtaining a number's predecessor.
  41
  42         The v1 lists and numbers on the other hand, had the tail and the predecessor
  43         right there as an element, easy for the taking. The problem was just that the
  44         v1 lists and numbers didn't have recursive capacity built into them, in the
  45         way the v3 implementations do.
  46
  47         A clever approach would marry these two strategies.
  48
  49         Version 3 makes the list [a; b; c; d; e] look like this:
  50
  51                 \f z. f a (f b (f c (f d (f e z))))
  52
  53         or in other words:
  54
  55                 \f z. f a <the result of folding f and z over the tail>
  56
  57         Instead we could make it look like this:
  58
  59                 \f z. f a <the tail itself> <the result of folding f and z over the tail>
  60
  61         That is, now f is a function expecting *three* arguments: the head of the
  62         current list, the tail of the current list, and the result of continuing to
  63         fold f over the tail, with a given base value z.
  64
  65         Call this a **version 4** list. The empty list could be the same:
  66
  67                 empty === \f z. z
  68
  69         The list constructor would be:
  70
  71                 make_list === \h t. \f z. f h t (t f z)
  72
  73         It differs from the version 3 `make_list` only in adding the extra argument
  74         `t` to the new, outer application of `f`.
  75
  76         Similarly, 5 as a v3 or Church numeral looks like this:
  77
  78                 \s z. s (s (s (s (s z))))
  79
  80         or in other words:
  81
  82                 \s z. s <the result of applying s to z (pred 5)-many times>
  83
  84         Instead we could make it look like this:
  85
  86                 \s z. s <pred 5> <the result of applying s to z (pred 5)-many times>
  87
  88         That is, now s is a function expecting *two* arguments: the predecessor of the
  89         current number, and the result of continuing to apply s to the base value z
  90         predecessor-many times.
  91
  92         Jim had the pleasure of "inventing" these implementations himself. However,
  93         unsurprisingly, he wasn't the first to do so. See for example [Oleg's report
  94         on P-numerals](http://okmij.org/ftp/Computation/lambda-calc.html#p-numerals).
  95
  96
  97 3.      Implementing (self-balancing) trees
  98
  99