3 ms·
For people who are interested. The theoretical foundations for this is lambda-calculus created by Alonso Church. Encoding integers with lambda is called the cu
by TeeWEE 14y ago
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 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.
- arethuza 14y agoAll you need is S and K - all the rest is syntactic sugar, even Y. :-)
- arianvanp 14y agoSKI combinator is indeed another explanation of why the λ-calculus is turing complete : http://en.wikipedia.org/wiki/SKI_combinator_calculus http://en.wikipedia.org/wiki/SKI_combinator_calculus
- masklinn 14y agoAnd for a pretty nice demonstration of (untyped) lambda calculus, http://codon.com/programming-with-nothing http://codon.com/programming-with-nothing
- arianvanp 14y agoFor 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-programming-part-i http://www.neo.com/2012/11/13/y-not-adventures-in-functional...
- kenko 14y agoLosh 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.
- ufo 14y agoI 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.
- tome 14y agoAlso this encoding is cool: http://okmij.org/ftp/tagless-final/course/Boehm-Berarducci.html http://okmij.org/ftp/tagless-final/course/Boehm-Berarducci.h...
- tome 14y agoThere 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".
- kenko 14y agoRight, I was (stupidly, it was early!) just using "f" as a shorthand for a function type like x -> x.