Losh doesn't use Church numerals, though, he represents numbers as lists. The fact that lists are also represented as functions is a diversion; his number three doesn't represent a function f -> x -> x that returns the threefold composition of its first argument applied to its second.
I didn't get too much into the original article but my impression is that he is using Scot encoding (essentially a 1-to1 translation of pattern matching) instead of church encoding (somethign equivalent to folds).
Scott encoding doesn't get much publicity but its perfectly valid and much more intuitive, IMO.
There must be some confusion here. For "the threefold composition of its first argument applied to its second" the type should be "(x -> x) -> x -> x".
For anyone curious of the λ-calculus, and why the Y-Combinator plays an important role in the turing completeness of this, please check out the excellent Y-not series by Jim Weirich[0]
[0] http://www.neo.com/2012/11/13/y-not-adventures-in-functional...
Comments
For people who are interested. The theoretical foundations for this is lambda-calculus created by Alonso Church.
Encoding integers with lambda is called the curch encoding: http://en.wikipedia.org/wiki/Church_numerals
Functional programming in general is built upon the foundations laid out by him.
Actually the domainname of hackernews (ycombinator) has a lot todo with lambda calculus.
Losh doesn't use Church numerals, though, he represents numbers as lists. The fact that lists are also represented as functions is a diversion; his number three doesn't represent a function f -> x -> x that returns the threefold composition of its first argument applied to its second.
I didn't get too much into the original article but my impression is that he is using Scot encoding (essentially a 1-to1 translation of pattern matching) instead of church encoding (somethign equivalent to folds).
Scott encoding doesn't get much publicity but its perfectly valid and much more intuitive, IMO.
Also this encoding is cool:
http://okmij.org/ftp/tagless-final/course/Boehm-Berarducci.h...
There must be some confusion here. For "the threefold composition of its first argument applied to its second" the type should be "(x -> x) -> x -> x".
Right, I was (stupidly, it was early!) just using "f" as a shorthand for a function type like x -> x.
For anyone curious of the λ-calculus, and why the Y-Combinator plays an important role in the turing completeness of this, please check out the excellent Y-not series by Jim Weirich[0] [0] http://www.neo.com/2012/11/13/y-not-adventures-in-functional...
All you need is S and K - all the rest is syntactic sugar, even Y.
:-)
SKI combinator is indeed another explanation of why the λ-calculus is turing complete : http://en.wikipedia.org/wiki/SKI_combinator_calculus
And for a pretty nice demonstration of (untyped) lambda calculus, http://codon.com/programming-with-nothing