Binary lambda calculus
Jump to navigation
Jump to search
Binary lambda calculus (BLC) is a version of lambda calculus with provisions for binary I/O, a standard binary encoding of lambda terms, and a designated universal machine.
The program is as a sequence of bits. The following commands are defined:
00x
= Lambda function with body x01xy
= Apply function x of y1x0
= Where x is zero or more "1" bits, make the de Bruijn index of the lambda, for example 10 is the innermost argument, 110 the second most, 1110 the third most, etc
I/O
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 is 0000110 (True), and an unset bit is 000010 (False). 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.
See also
External resources
- Binary lambda calculus at Wikipedia (from the Wayback Machine; retrieved on 19 October 2016)
- Wikipedia:Binary combinatory logic
- John's Lambda Calculus and Combinatory Logic Playground