4 ms·
Needs more combinators! It's already got Y, so why not SKI (http://en.wikipedia.org/wiki/SKI_combinator_calculus http://en.wikipedia.org/wiki/SKI_combinator_ca
by JadeNB 12y ago
Needs more combinators! It's already got Y, so why not SKI (http://en.wikipedia.org/wiki/SKI_combinator_calculus http://en.wikipedia.org/wiki/SKI_combinator_calculus) or BCKW (http://en.wikipedia.org/wiki/B,C,K,W_system http://en.wikipedia.org/wiki/B,C,K,W_system)?
(I'm not sure if it's kosher to link to it—if not, then please let me know and I'll remove it—but I implemented a SKI combinator reducer in Perl regexes a while back: http://perlmonks.org/?node_id=809842 http://perlmonks.org/?node_id=809842 .)
- cstrahan 12y agoNice! I'll have to read that in full later tonight - thanks for sharing! This was mostly just me trying to wrap my head around Church encodings and such, but I could surely do with a couple more combinators in there :).
- JadeNB 12y agoJust a warning: at least for me, once I got started, it became addictive to try, Oulipo-like (http://en.wikipedia.org/wiki/Oulipo http://en.wikipedia.org/wiki/Oulipo), to write simple programmes in these ever-more-restrictive languages. I was helped along immensely by Hindley–Seldin (http://www.cambridge.org/us/academic/subjects/computer-science/programming-languages-and-applied-logic/lambda-calculus-and-combinators-introduction-2nd-edition http://www.cambridge.org/us/academic/subjects/computer-scien...) and, for, as one would expect, a more friendly but still thoroughly mathematical introduction, Smullyan (http://en.wikipedia.org/wiki/To_Mock_a_Mockingbird http://en.wikipedia.org/wiki/To_Mock_a_Mockingbird). I am not alone in my admiration for the latter; see, for example, http://www.angelfire.com/tx4/cus/combinator/birds.html http://www.angelfire.com/tx4/cus/combinator/birds.html. EDIT to add: Speaking of 'Mockingbird' articles, you may be interested in Appendix A of http://dkeenan.com/Lambda/index.htm http://dkeenan.com/Lambda/index.htm, whose author discusses another interpretation, attributed there to Barendregt, of Booleans and numerals. For someone who regards the Church encoding as 'intuitive', they were very surprising!