4 ms·

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

by js8 1y ago

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.

tromp 1y ago
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/ https://crypto.stanford.edu/~blynn/compiler/ [2] https://github.com/augustss/MicroHs https://github.com/augustss/MicroHs
- js8 1y ago
  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.
  - tromp 1y ago
    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/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

by js8 1y ago

tromp 1y ago

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/ https://crypto.stanford.edu/~blynn/compiler/ [2] https://github.com/augustss/MicroHs https://github.com/augustss/MicroHs

js8 1y ago
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.
- tromp 1y ago
  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/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