Re:SICP 2.6: Church Numerals (2011)
by gshubert17 on Sunday May 11, 2014 @05:33PM
(#7730088)
Tom Stuart used various Church encodings in his presentation "Programming with Nothing" [1] [2]. He used nothing in the Ruby language but creating procs and calling procs. He demonstrated this by implementing the fizz-buzz program in nothing but procs.
Re:SICP 2.6: Church Numerals (2011)
by brianmwaters_hn on Sunday May 11, 2014 @07:12PM
(#7730424)
What's really interesting beyond just type coercion and "increment," is the way addition, multiplication, and exponentiation were implemented by Church and Rosser back in the 30's (see https://en.wikipedia.org/wiki/Lambda_calculus). Rather than using SICP-style recursion to count down to zero and repeatedly apply inc/add/mul, they took advantage of some of the special properties of Church numerals. A year later, and I still have not really wrapped my head around their solutions. Maybe you will fare better.
For a real challenge, try to implement the decrement function. Legend has it, Rosser thought of the solution while on the dentist's chair. (It is a bit heavier on code than the other Church numeral functions, but conceptually simple - and was a creative idea at the time, before functional programming had really come into being.)
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. :-)
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 dizzystar on Monday May 12, 2014 @12:08AM
(#7731179)
Oh man. I worked through SICP when I was just starting to program. Little did I know that no other book would be so full of gems and enlightenment like this[0]. Some of the stuff stopped me dead and caused me to daze off for several minutes.
What's amazing is that I feel like I didn't fully "get" a large portion of the book. I could work through it again in a few years and learn something from every page.
[0]Other books come close, but the impact of this book will stay with me forever.
Re:SICP 2.6: Church Numerals (2011)
by bridger on Monday May 12, 2014 @12:03AM
(#7731169)
When I was doing this exercise with a friend on Understudy, he found solutions to multiplication and exponentiation too. I'm still trying to wrap my head around the exponentiation. Passing a number to another number?!
Re:SICP 2.6: Church Numerals (2011)
by rspeer on Monday May 12, 2014 @01:33AM
(#7731328)
Let's use "twice" as the name of Church numeral 2, and "thrice" as the name of numeral 3.
If you look at the input and output of thrice, it looks like this:
(function that gets applied once) -> (function that gets applied 3 times)
What if we used the output as the input again?
(function that gets applied once) -> (function that gets applied 3 times) -> (function that gets applied 9 times)
We have a name for what we just did to the "thrice" function, and that name is "twice". So that's (twice thrice), and we can see it makes something happen 3^2 = 9 times.
Re:SICP 2.6: Church Numerals (2011)
by iano on Sunday May 11, 2014 @08:37PM
(#7730636)
Along the same vane from the math world is how natural numbers (which can then be used to build the reals, etc) are represented using only empty sets. Pretty awesome.
[1] http://codon.com/programming-with-nothing
[2] http://computationbook.com
For a real challenge, try to implement the decrement function. Legend has it, Rosser thought of the solution while on the dentist's chair. (It is a bit heavier on code than the other Church numeral functions, but conceptually simple - and was a creative idea at the time, before functional programming had really come into being.)
Here it is in action computing the factorial of 6:
Hint: consider a function that maps the pair <n,n!> to <(n+1),(n+1)!> ...
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)What's amazing is that I feel like I didn't fully "get" a large portion of the book. I could work through it again in a few years and learn something from every page.
[0]Other books come close, but the impact of this book will stay with me forever.
If you look at the input and output of thrice, it looks like this:
What if we used the output as the input again? We have a name for what we just did to the "thrice" function, and that name is "twice". So that's (twice thrice), and we can see it makes something happen 3^2 = 9 times.See http://en.wikipedia.org/wiki/Set-theoretic_definition_of_nat...
I came just after 2.5 which was already an awesome magic trick.