The goal of this challenge is to compare how well different programming languages support functional programming, by seeing how much code it takes to implement BLC8, the simplest functional programming language

BLC8 is the bytewise variant of Binary Lambda Calculus, as described in my 2012 IOCCC entry at https://www.ioccc.org/2012/tromp/hint.html :

BLC was developed to make Algorithmic Information Theory, the theory of smallest programs, more concrete. It starts with the simplest model of computation, the lambda calculus, and adds the minimum amount of machinery to enable binary input and output.

More specifically, it defines a universal machine, which, from an input stream of bits, parses the binary encoding of a lambda calculus term, applies that to the remainder of input (translated to a lazy list of booleans, which have a standard representation in lambda calculus), and translates the evaluated result back into a stream of bits to be output.

Lambda is encoded as 00, application as 01, and the variable bound by the n'th enclosing lambda (denoted n in so-called De Bruijn notation) as 1^{n}0. That’s all there is to BLC!

For example the encoding of lambda term S = \x \y \z (x z) (y z), with De Bruijn notation \ \ \ (3 1) (2 1), is 00 00 00 01 01 1110 10 01 110 10

In the closely related BLC8 language, IO is byte oriented, translating between a stream of bytes and a list of length-8 lists of booleans.

A 0 bit is represented by the lambda term B0 = \x0 \x1 x0, or \ \ 2 in De Bruijn notation, while a 1 bit is B1 = \x0 \x1 x1, or \ \ 1 in De Bruijn notation.

The empty list is represented by the lambda term Nil = B1. The pair of terms M and N is represented by the term <M,N> = \z z M N, or \ 1 M N in De Bruijn notation. A list of k terms M1 .. Mk is represented by repeating pairing ending in Nil: <M1, <M2, ... <Mk, Nil> ... >

A byte is represented by the list of its 8 bits from most to least significant. Standard input is represented as a list of bytes, with the end of input (EOF) represented as Nil.

The BLC8 interpreter must parse the encoding of a lambda term from concatenated initial bytes of standard input and apply the parsed term to the remaining bytes of input. Then, assuming that this results in another byte list, that result must be translated back into bytes on standard output.

So it should behave like the IOCCC entry when run without arguments.

Test cases.

On input " Hello" or "*Hello", the output should be "Hello".

On input of https://www.ioccc.org/2012/tromp/hilbert.Blc followed by "123" it should output

` _   _   _   _ 
| |_| | | |_| |
|_   _| |_   _|
 _| |_____| |_ 
|  ___   ___  |
|_|  _| |_  |_|
 _  |_   _|  _ 
| |___| |___| |

So my IOCCC entry demonstrated that the programming language C needs 650 characters to implement BLC8 (it also implemented bitwise BLC, but removing that support wouldn't save many characters). It needs that many because C has very poor support for functional programming. No lambdas or closures. BLC itself needs only 43 bytes, demonstrating its much lower functional cost. I would like to see how other languages compare. How many characters does rust need? Or LISP?

Sample implementations in Perl, JavaScript, Python, and Ruby can be found in https://github.com/tromp/AIT How much shorter can each of these be made?

  • 2
    \$\begingroup\$ This is very unclear to me. Also what's the competitive goal? If codegolf is the goal then you need to add that tag. Suggest moving this to the sandbox. Also links shouldn't be used in a post as they go out-of-date and no longer work. \$\endgroup\$
    – Noodle9
    Commented Jan 30 at 11:57
  • 1
    \$\begingroup\$ I want to compare different programming languages in terms of functional programming support. Added the codegolf tag. \$\endgroup\$
    – John Tromp
    Commented Jan 30 at 14:55
  • \$\begingroup\$ The link goes to a Blc file which my browser doesn't know how to open. Could you perhaps include it in the challenge as plain text? \$\endgroup\$
    – xnor
    Commented Jan 31 at 6:36
  • 1
    \$\begingroup\$ This seems like two separate challenges piped together: Decoding BLC and this, with extra requirements on the second part \$\endgroup\$
    – Joao-3
    Commented Jan 31 at 16:19
  • 1
    \$\begingroup\$ This challenge differs from the other lambda calculus interpreter one in that the syntax here is simpler and completely fixed while it leaves much more freedom for the runtime since you don't have to show reduction steps, and the runtime could be based on something different like combinatory logic. \$\endgroup\$
    – John Tromp
    Commented Feb 1 at 7:44


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.