Binary lambda calculus

From Esolang
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 x
  • 01xy = Apply function x of y
  • 1x0 = 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


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