News for hackers. Stuff that matters.
Re:SICP 2.6: Church Numerals (2011) by lisper on Monday May 12, 2014 @03:15AM (#7731518)
Here's what the factorial function on Church numerals ends up looking like if you expand it out:

    ((λ (f) ((λ (g) (g g)) (λ (h) (λ (x) ((f (h h)) x)))))
   (λ (f)
      (λ (n)
         (if ((λ (p a b) (p a b)) ((λ (n) (n (λ (x) (λ (x y) y)) (λ (x y) x))) n) t nil)
           ((λ (n) (λ (f x) (f (n f x)))) (λ (f x) x))
           ((λ (m n) (m ((λ (m n) (λ (f x) (m f (n f x)))) n) (λ (f x) x)))
            n (f ((λ (n) (λ (f x) (n (λ (g h) (h (g f))) (λ (u) x) (λ (u) u)))) n)))))))
Note the use of the Y combinator to implement recursion :-)

Here it is in action computing the factorial of 6:

    ? (((λ (f) ((λ (g) (g g)) (λ (h) (λ (x) ((f (h h)) x)))))
   (λ (f)
      (λ (n)
         (if ((λ (p a b) (p a b)) ((λ (n) (n (λ (x) (λ (x y) y)) (λ (x y) x))) n) t nil)
           ((λ (n) (λ (f x) (f (n f x)))) (λ (f x) x))
           ((λ (m n) (m ((λ (m n) (λ (f x) (m f (n f x)))) n) (λ (f x) x)))
            n (f ((λ (n) (λ (f x) (n (λ (g h) (h (g f))) (λ (u) x) (λ (u) u)))) n)))))))
  ((λ (n) (λ (f x) (f (n f x))))
   ((λ (n) (λ (f x) (f (n f x))))
    ((λ (n) (λ (f x) (f (n f x))))
     ((λ (n) (λ (f x) (f (n f x))))
      ((λ (n) (λ (f x) (f (n f x))))
       ((λ (n) (λ (f x) (f (n f x))))
        (λ (f x) x))))))))
    #<COMPILED-LEXICAL-CLOSURE #x30200105130F>
    ? (funcall * '1+ 0)
    720
Re:SICP 2.6: Church Numerals (2011) by tromp on Monday May 12, 2014 @10:07AM (#7732735)
Church factorial can be implemented without recursion though.

Hint: consider a function that maps the pair <n,n!> to <(n+1),(n+1)!> ...

Re:SICP 2.6: Church Numerals (2011) by tromp on Monday May 12, 2014 @11:19AM (#7733210)
Here is Church factorial in graphical notation:

  ┬──────────────────────
  │ ┬────────────── ─ ┬ ┬
  │ ┼─┬───────┬──── ┬ │ │
  │ ┼─┼───────┼─┬── │ │ │
  │ │ ┼─┬─┬── ┼─┼─┬ │ │ │
  │ │ ┼─┼─┼─┬ │ ├─┘ │ │ │
  │ │ └─┤ ├─┘ ├─┘   │ │ │
  │ │   ├─┘   │     │ │ │
  │ └───┤     │     │ │ │
  │     ├─────┘     │ │ │
  └─────┤           │ │ │
        └───────────┤ │ │
                    └─┤ │
                      └─┘
Re:SICP 2.6: Church Numerals (2011) by lisper on Monday May 12, 2014 @12:13PM (#7733592)
That's pretty cool looking, but I have no idea what I'm looking at. Does this notation have a name? Is it documented somewhere? (Hm, I wonder how hard it would be to write a parser for it. :-)
Re:SICP 2.6: Church Numerals (2011) by tromp on Monday May 12, 2014 @01:11PM (#7733994)
That's my graphical notation for lambda calculus, documented at http://www.cwi.nl/~tromp/cl/diagrams.html

Btw, here's an even shorter version of factorial:

  ┬────────────────
  ┼─────────────┬──
  │ ──┬──────── ┼ ┬
  │ ┬─┼─┬────── │ │
  │ │ │ ┼─┬─┬── │ │
  │ │ │ ┼─┼─┼─┬ │ │
  │ │ │ └─┤ ├─┘ │ │
  │ │ │   ├─┘   │ │
  │ │ ├───┘     │ │
  │ ├─┘         │ │
  └─┤           │ │
    └───────────┤ │
                └─┘
In de-Bruijn notation it is \\2 (\\1 (2 (\\3 2 (2 1)))) (\2) (\1), which in conventional notation is \n\f.n (\x\m.m (x (\a\b.m a (a b)))) (\x.f) (\x.x)
Re:SICP 2.6: Church Numerals (2011) by lisper on Wednesday May 14, 2014 @04:39PM (#7746265)
BTW, is there a description of how this works written up anywhere? I tried to reverse-engineer it and got lost in lambdas. (I did manage to translate it into Scheme and verify empirically that it works!)
Re:SICP 2.6: Church Numerals (2011) by lisper on Wednesday May 14, 2014 @12:28PM (#7744570)
Wow! That is wicked-cool! Thanks!
Re:SICP 2.6: Church Numerals (2011) by lisper on Monday May 12, 2014 @12:15PM (#7733607)
Whether the loop is recursive or iterative you still need a loop, so you still need a Y combinator.
Re:SICP 2.6: Church Numerals (2011) by tromp on Monday May 12, 2014 @01:12PM (#7734002)
You don't need Y if you apply a Church numeral instead, which gives you a bounded iteration.
Re:SICP 2.6: Church Numerals (2011) by lisper on Tuesday May 13, 2014 @11:24AM (#7738569)
Ah, good point!