Binary lambda calculus - Esolang

Binary lambda calculus

From Esolang

Jump to navigation<br>Jump to search<br>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.

Contents

1 BLC Syntax

2 Basic Program Information

3 SKI combinator calculus

4 BLC8

5 Programs (BLC)

5.1 self-interpreter

5.2 prime number sieve

5.3 Brainfuck interpreter

5.4 Universal Turing Machine

6 Programs (BLC8)

6.1 self-interpreter

7 Computational Class

8 See Also

9 External Resources

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, 1-indexed<br>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.<br>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 once, you would write 0010 = 00 10.

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 0 bit in BLC is 0000110 (True), and a 1 bit is 000010 (False), which are the normal lambda calculus representations of these values.

0000110 = 00 00 110<br>*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<br>*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<br>*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<br>10100001<br>00000001<br>10000001<br>01110011<br>00001111<br>11100001<br>01110011<br>1111100000<br>011110000001<br>01110111001101<br>1110011111111000<br>01111111 10000101<br>11101001 11010010<br>11111010 01011010<br>10011010 00011001<br>00011010 00011010

prime number sieve

000100011001100101000110100<br>000000101100000100100010101<br>11110111 101001000<br>11010000 111001101<br>000000000010110111001110011<br>11111011110000000011111001<br>10111000<br>00010110<br>0000110110

Brainfuck interpreter

0000000 01a15144 02d55584 223070b7 00f032ff<br>0000020 7f85f9bf 956fe15e c0ee7d7f 006854e5<br>0000040 fbfd5558 fd5745e0 b6f0fbeb...