3 ms·
At one point I was seriously fascinated by the lambda calculus and particularly the S and K combinators - two very simple functions that you can build any compu
by arethuza 12y ago
At one point I was seriously fascinated by the lambda calculus and particularly the S and K combinators - two very simple functions that you can build any computation from:
http://en.wikipedia.org/wiki/SKI_combinator_calculus http://en.wikipedia.org/wiki/SKI_combinator_calculus
More recently I found out about the U combinator which is a single combinator that can be used to define S & K:
http://en.wikipedia.org/wiki/Iota_and_Jot http://en.wikipedia.org/wiki/Iota_and_Jot
Having a system that implemented recursion using the Y combinator in terms of S & K and have it actually compute stuff was rather amusing. I'd be fascinated to see what it would look like using just U.
- lisper 12y agoIt would look like a very (very!) long string of U's. :-) You might enjoy this: http://www.flownet.com/ron/lambda-calculus.html http://www.flownet.com/ron/lambda-calculus.html
- arethuza 12y agoActually, one of the many things I learned from doing a final year project for my CS degree on "benchmarking" different sets of combinators was how to write a garbage collector - I was doing this in '87/'88 on a Unix mini (HLH Orion) and memory was tight and my trees were comparatively huge!
- tome 12y agoPresumably a tree of U's.
- lisper 12y agoOh, right. Good point. It's worth noting, BTW, in case anyone is still following this thread, that what is going on here in all of these single-instruction languages is not particularly interesting. You're just encoding the program semantics in the arguments, or in the structure of the tree, or the length of the program, or something like that, rather than in the instructions.