4 ms·
let A = (x) => (y) => (z) => x(z)(y((w) => z)) Just need to combine this a few times. let K = A(A(A))(A(A(A))(A)(A)(A)(A)(A); // (x) => (y) => x let S
by tromp 1y ago
let A = (x) => (y) => (z) => x(z)(y((w) => z))
Just need to combine this a few times.
let K = A(A(A))(A(A(A))(A)(A)(A)(A)(A); // (x) => (y) => x
let S = A(A(A(A)(A(A)(A(A)))(A(A(A(A)((A(A)))))))(A)(A); // (x) => (y) => (z) => x(z)(y(z))
> “I would never be caught dead using Lambda calculus. It’s a bloated language.”
Actually, combinatory logic is more bloated than lambda calculus, generally needing more bits to express the same program [1]. One can argue that lambda calculus is one of the most concise languages ever [2].
> Dana smirks. “Well, yeah. JavaScript is an eager language. Can’t use the Y combinator.”
Eager languages can be made lazy by wrapping arguments in lambdas with dummy arguments, as done in the Javascript BLC interpreter [3].
[1] https://tromp.github.io/cl/LC.pdf https://tromp.github.io/cl/LC.pdf
[2] https://www.ioccc.org/2012/tromp/ https://www.ioccc.org/2012/tromp/
[3] https://github.com/tromp/AIT/blob/master/uni.js#L56 https://github.com/tromp/AIT/blob/master/uni.js#L56
- teiferer 1y ago> let A = (x) => (y) => (z) => x(z)(y((w) => z)) What is w?
- tromp 1y agoThe name for a dummy argument that is not used. We could also write A as \x y z => x z (y (K z)), since K is the const function that ignores its second argument and returns the first.
- js8 1y agoWhat is interesting though, the fastest interpreters for lambda calculus (such as yours uni.c) work by translating the term to combinatory logic (although with a bigger base than S,K) and calculating with it.
- tromp 1y agoMy uni.c was based on Ben Lynn's combinatory logic VM to which he compiled a large subset of Haskell [1] in a winning IOCCC entry. Lennart Augustsson made an even more comprehensive Haskell implementation with a combinator based runtime [2]. [1] https://crypto.stanford.edu/~blynn/compiler/ https://crypto.stanford.edu/~blynn/compiler/ [2] https://github.com/augustss/MicroHs https://github.com/augustss/MicroHs
- js8 1y agoThanks for the pointer to MicroHS, looks interesting. BTW, this is probably obvious to you, there are also 5 combinators to which you can directly translate (with proper parentheses) the bits of BLC expression and it sort of self-evaluates in combinatory logic. The self-evaluation works with the stack of de Bruijn terms as the second argument. One combinator represents lambda abstraction which puts a term to the stack, another is S which represents application, two combinators are used to drop/select the de Bruijn term from the stack and there needs to be another combinator to mark the end of input.
- tromp 1y agoYes; that's sort of how the lambda calculus self-interpreter works. There's another connection too, where a lambda term is obtained from its binary code by successive applying an initial term to true or false [1]. [1] https://cstheory.stackexchange.com/questions/32309/concatenative-binary-lambda-calculus-combinatory-logic https://cstheory.stackexchange.com/questions/32309/concatena...
- username223 1y ago> https://crypto.stanford.edu/~blynn/compiler/ioccc.html https://crypto.stanford.edu/~blynn/compiler/ioccc.html Good stuff -- thanks for sharing. IOCCC, like Perl Golf, is brilliantly absurd. https://www.perlmonks.org/?node_id=759963 https://www.perlmonks.org/?node_id=759963
- voidmain 1y agoI think there must be typos in your K and S - the parentheses do not match. I get (with no warranty express or implied): let K = A(A(A))(A(A(A))(A)(A)(A)(A)(A)); let S = A(A(A(A)(A(A)(A(A)))(A(A(A(A)(A(A)))))))(A)(A); > Eager languages can be made lazy by wrapping arguments in lambdas with dummy arguments So, something like this? let A = x => y => z => () => x()(z())(y()(w=>z()));
- tromp 1y agoIt's possible that I messed up in transcribing from my working code K = A (A A) (A (A A) A A A A A); S = A (A (A A (A A (A A))(A (A (A A (A A)))))) A A; that assumes application is left associative. > So, something like this? > let A = x => y => z => () => x()(z())(y()(w=>z())); The javascript code I linked to would change an application like x(z) in A's definition to x ((a) => z(a)), which is really just an eta-expansion of the argument, and would similarly treat the other 2 applications in the definition.
- jandrese 1y agolet K = A(A(A))(A(A(A))(A)(A)(A)(A)(A); let S = A(A(A(A)(A(A)(A(A)))(A(A(A(A)((A(A)))))))(A)(A); Interestingly enough, the sounds escaping my mouth while looking at that match the argument list.
- nmilo 1y agoA bloated language means the language has bloat i.e unnecessary features, e.g C++ is a bloated version of C even if you can write the same programs in less code.
- tromp 1y agoYou're right; I should have said "In a sense" instead of "actually", since I consider the less common bloat in codesize rather than the more common bloat in features.
- SupaShotty 1y agoDo you think there’s a different basis set of combinators besides S, K that could produce a smaller self interpreter than lambda calculus?