Binary lambda calculus

From Esolang
Jump to navigation Jump to search

Binary lambda calculus (BLC) is an extremely small Turing-complete language which can be represented as a series of bits or bytes. Unlike Binary combinatory logic, another binary language with a similar acronym, it is capable of input and output.

De Bruijn Index

I suggest knowing what a De Bruijn index is before trying to understand this language. In case you don't want to do that, here's an explanation. The explanation also features lambda calculus code which has more parentheses than normal in order to better map onto BLC.

Lambda calculus can use names to denote the term corresponding to each lambda, like the following example.

λxλy.y

This function takes in two inputs x and y and outputs the final one it took in. In this, you know that the term y is referring to the second lambda, the one with y after it. But the term names are arbitrary, which is even more annoying when all you have is binary.

A De Bruijn index can be used to replace the term in lambda calculus without naming the term. The index is a number which counts from the final lambda in the scope until it finds the lambda which the term is referencing.

In BLC, this number starts from 1. So the De Bruijn index in BLC basically indicates how many lambdas the term has had to encounter before finding the lambda it's actually referencing, with 1 referring to the last lambda, 2 to the second-last, 3 to the third-last, etc.

The following code is equivalent to the code above, but using a De Bruijn index.

λλ.1

Note that this is in the scope. It is possible for there to be lambdas that are in a different scope, meaning that the lambdas.

Here are some examples of lambda calculus with named terms and lambda calculus with De Bruijn indices. I have deliberately put spaces between the numbers so it's easier to understand what's going on.

Command Description Notes
λxλy.(yx) λλ.(2 1) outputs in opposite order
λxλyλz.((xz)(yz)) λλλ.((3 1)(2 1)) S combinator
λx.(xλy.(yy)) λ.(1λ.(1 1)) takes in one input, outputs that input and this other lambda. Note the lambda doesn't need parentheses before it.
λxλy.((x λz.(zz))y) λλ.((2 λ.(1 1)) 1) Note that 1 replaces y and 2 replaces x. They can't be arguments of the inner lambda, so they treat it like it doesn't exist.

BLC Syntax

The BLC program is a sequence of bits read left to right. The following commands are defined. Feel free to change how the commands are explained if you think it's too confusing.

  • 00x = Lambda function with body x
  • x0, where x is one or more "1" bits = the number of "1" bits serves as the De Bruijn index
    • For example 10 corresponds to a De Bruijn index of 1, 110 to 2, 1110 to 3, etc.
    • To be clear, this means 10 refers to the final lambda, 110 to the second-last, 1110 to the third-last, etc.
  • 01xy, where x and y are more code = x is applied to y.
    • By default, the output of a lambda is one term in this language. Using 01 allows the function to output both x and y, which is the same as applying x to y in lambda calculus because both of the outputs are also lambdas.
    • If you want to take in one input and output it twice, you would write 00011010 = 00 01 10 10.
    • If you want to take in two inputs and output the first one three times, you would write 00000101110110110 = 00 00 01 01 110 110 110.
    • If you want to output code directly starting with 00, it doesn't need to have 01 directly before it. If there is a term before the function, then 01 is needed before the term.

It is possible for the code to have padding at the right end, i.e. code which doesn't affect the result of the command. This fact is especially useful when trying to use bytes to represent this language.

Basic Program Information

A program is a lambda calculus term that transforms an input to an output. Standard input is represented as a list of boolean values, and standard output has the same format.

A set bit in BLC is 0000110 (True), and an unset bit is 000010 (False), which are the normal lambda calculus representations of these values.

0000110 = 00 00 110
*taking two inputs (with the two lambda functions represented by 00), return the second argument from the inside i.e. the first argument

000010 = 00 00 10 
*taking two inputs (with the two lambda functions represented by 00), return the innermost / last argument i.e. the second argument

The empty list, called nil, is 000010 (False).

A list with multiple elements is represented by the pairing or cons function 00010110xy, where x is the head of the list and y is the tail.

00010110xy = 00 01 01 10 x y
*taking one input, output that input, the head of the list, and the tail of the list

You might expect programs to consist of multiple bytes, considering all of these have been six bits or over. However, printing out input in this language is done through the code 0010, which takes one input (which is the innermost by default) and prints it out. Because padding is ignored and lambdas only output one term by default in this language, a program consisting of just a cat can be represented by any bytes between 32 (00100000) and 47 (00101111) because everything after 0010 is ignored (remember that you have to type 00011010 to output the input twice).

SKI combinator calculus

The encoding of lambda term S is λxλyλz.((xz)(yz)), which is written as λλλ.((3 1)(2 1)) using De Bruijn indexes instead of names, and as 00 00 00 01 01 1110 10 01 110 10 in BLC.

The K combinator is written as λxλy.x or λλ.2 in a corresponding format, so it would be 00 00 110 in BLC.

The identity function I is the same as the cat: 00 10.

Therefore, you can implement SKI combinator calculus in BLC.

BLC8

BLC operates on a stream of bits (values of 0 and 1), while BLC8 is the same, but operates on a stream of bytes (values from 0 - 255) with the most significant bit in the smallest value (big-endian). In the following programs, BLC and BLC8 programs are put into different parts.

Programs (BLC)

self-interpreter

  01010001
   10100000
    00010101
     10000000
      00011110
       00010111
        11100111
         10000101
          11001111
          000000111
         10000101101
        1011100111110
       000111110000101
      11101001 11010010
     11001110   00011011
    00001011     11100001
   11110000       11100110
  11110111         11001111
 01110110           00011001
00011010             00011010

prime number sieve

000100011001100101000110100
 000000101100000100100010101
 11110111          101001000
 11010000          111001101
 000000000010110111001110011
 11111011110000000011111001
 10111000
 00010110
0000110110

Brainfuck interpreter

0000000          01a15144 02d55584               223070b7        00f032ff
0000020          7f85f9bf        956fe15e        c0ee7d7f 006854e5
0000040          fbfd5558        fd5745e0        b6f0fbeb 07d62ff0
0000060          d7736fe1 c0bc14f1               1f2eff0b        17666fa1
0000100          2fef5be8        ff13ffcf        2034cae1 0bd0c80a
0000120          e51fee99        6a5a7fff        ff0fff1f d0049d87
0000140          db0500ab 3bb74023               b0c0cc28 10740e6c
0000160

Universal Turing Machine

0101000110100000000101011000000000011110000101111110011110 
0001011100111100000011110000101101101110011111000011111000 
0101111010011101001011001110000110110000101111100001111100 
0011100110111101111100111101110110000110010001101000011010

Programs (BLC8)

self-interpreter

 19468
  05580
   05f00
    bfe5f
     85f3f
      03c2d
     b9fc3f8
    5e9d65e5f
   0decb f0fc3
  9befe   185f7
 0b7fb     00cf6
7bb03       91a1a


There is also a universal Turing machine written in BLC8 which is slightly longer than the one in BLC.

Computational Class

Lambda calculus is Turing-complete, and because binary lambda calculus is a version of lambda calculus, it is also Turing-complete. It can also implement SKI combinator calculus as seen above, so it is Turing-complete in that way. As a final indication of Turing-completeness, Brainfuck and a Universal Turing Machine have both been represented in this language.

See Also

External Resources