Hacker News Reader

Comment by tromp | Hacker News Reader

    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

[2] https://www.ioccc.org/2012/tromp/

[3] https://github.com/tromp/AIT/blob/master/uni.js#L56

View on HN

What 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.

My 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/

[2] https://github.com/augustss/MicroHs

Thanks 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.

Yes; 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/concatena...

> 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

A 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.

You'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.

    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);

Interestingly enough, the sounds escaping my mouth while looking at that match the argument list.

I 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()));

It'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.

Do you think there’s a different basis set of combinators besides S, K that could produce a smaller self interpreter than lambda calculus?

> let A = (x) => (y) => (z) => x(z)(y((w) => z))

What is w?

The 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.

Reply on news.ycombinator.com