DeBruijn
| Paradigm(s) | Functional |
|---|---|
| Designed by | User:Sλλλ1(210) |
| Appeared in | 2021 |
| Computational class | Turing complete |
| Reference implementation | Unimplemented |
| File extension(s) | .txt |
DeBruijn is an esolang created by Andrew Phillips in 2021. It is based on pure, untyped lambda calculus written with DeBruijn Indices.
Feature specification
Overview
A DeBruijn program is written as a lambda expression with DeBruijn indices, such as this:
λλλ20(10)
The indices are indexed starting at 0, so λλ1 is the K combinator, because the 1 refers to the outer lambda.
λλ1
When an expression is passed to this lambda, it will replace the 1 because 1 refers to the outermost lambda.
An alternative to typing the Greek Lambda (λ) is to use a backslash (\). This looks less pretty, but is more portable because λ is non-ASCII.
The DeBruijn expression is reduced into a normal (irreducible) form and the program is complete, yielding its reduced form. The program:
(\\\1(210))\\10
reduces to
rem: λ λ 1 (1 0)
Pure DeBruijn programs only do this reduction. For more information on how reduction works with DeBruijn indices, check out the Wikipedia article.
Caveat: DeBruijn only allows indices from 0 through 9. This should be plenty in any practical case. However, if the interpreter reduces a program into one containing an index higher than 9, it will no longer be re-typeable in DeBruijn.
Definitions
DeBruijn only understands the characters λ\0123456789()[]{}". any other character appearing in the program needs to be defined before use (whitespace ignored). On the first instance of an undefined character, the interpreter/compiler stores the rest of the group into the character. The character may then be replaced elsewhere with the stored lambda. All definitions must be placed in the program header.
(T \\1 ) (F \\0 ) (& \0(\0TF)\F ) (| \0(\T)\0TF ) ...
The rest of the program may then be written in terms of the characters TF&|.
Output
The output lambda is written just like a string in any other language. Assuming the program is run on a command line, "hello world" will print out hello world and reduce to the identity lambda λ0.
"any printer reduces to the identity,\nwhich doesn't change the next item"\\\1(210)
any printer reduces to the identity, which doesn't change the next item rem: λ λ λ 1 (2 1 0)
The output only occurs when the output lambda reaches the program head. It can, however, still reduce, and the lambda it joins with will carry its action. This now "dirty" lambda is denoted "λ.
\"this won't print because it's inside a lambda."\0
rem: λ "λ 0
Input
Input to the program is allowed through the use of curly braces ({}). The most lenient way of allowing input is to leave a trailing open-brace at the end of the program (note that this is special syntax, so parentheses are not required):
(T \\1)
(F \\0)
\0 "Yes" "No" \0 {
> debruijn example.txt T Yes rem: λ 0 > debruijn example.txt F No rem: λ 0
There are many problems with this approach. Firstly, it only works on the command line. Secondly, there is no way to specify the amount of data to allow or how to interpret it. Thirdly, it is a security risk:
> debruijn example.txt '\\"code injection"' code injection rem: λ 0
Instead it is recommended to use full brace syntax. a list of braces indicates a choice for a single input character. The revised program is much safer than above:
(T \\1)
(F \\0)
(\0 "Yes" "No" \0) {T}{F}
If the input is neither of the options, then the last option will be chosen. If the last option is empty, then the program will error, as there is no empty lambda.
... {T}{F}{}
> debruijn example.txt '"whatever I want"' ERROR
The single character braces work for characters that are defined. If you want to use an illegal character or don't want to create a definition, you can use single-quotes to demark a character label.
(\0\0) {'0' "you pressed 0"}{'T' "you pressed T"}{"you pressed something else"}
> debruijn example.txt 0 you pressed 0 > debruijn example.txt T you pressed T > debruijn example.txt hello you pressed something else
Depending on implementation, the input lambda might consume a single character or a single argument from the command line. However, when the stdin is set someplace else (i.e. a text file), then input is consumed per character. If not enough input characters are available on the command line, the program will simply await input. In a file, the input is irreducible once a EOF is found, unless there is a specific {'\x04' ...} branch that continues after EOF.
Recursion and nonreducing groups
In order to do recursion, the fixed point operator (Y \(\1(00))[\1(00)] ) is definable in DeBruijn. However, if the program tries to reduce this into a normal form, it will crash because the program grows infinitely large. The solution involves nonreducing groups, wrapped in square brackets ([]). Any group wrapped in square brackets will be treated as irreducible, so they will substitute into expressions but not allow substitution into themselves. Once the nonreducing group reaches the head of the program, it will become reducible again.
(Y \(\1(00))[\1(00)] )
\[Y"1"]{
> debruijn example.txt rem: λ [(λ (λ 1 (0 0)) [λ 1 (0 0)]) "λ 0] > debruijn example.txt "\0" 1111111111111111111111111111111111111111111111111111111111111111111111111...
For some implementations, it may feel natural to introduce this nonreduction as laziness. Note though, that lazy implementations will have to explicitly reduce the reducible groups. Otherwise, the program will not reach a normal form, which is the primary goal of the language (IO is a side-effect).
Examples
Hello world
"hello world!\n"
hello world! rem: λ 0
Truth machine
(T \\1 )
(F \\0 )
(Y \(\1(00))[\1(00)] )
(\0[Y"1"]["0"]) {'1' T}{'0' F}
Adder
Adds two input numbers and outputs the result in 0 + 1 + 1 + ... + 1 form.
(S \\\1(210) )
(z \\0)
(\\"0"1S0" + 1"\0){
Triangular number
Uses the fixed-point "Y" combinator to recursively find the sum of the first n naturals. The definition of f is used as example input.
(F \\0 ) (T \\1 ) (S \\\1(210) ) (f S(S(S(S(SF)))) ) (P \\\021 ) (- \0(\(\P(1F)(S(1F)))\0)(PFF)T ) (Z \0(\0FF)T ) (Y \(\1(00))[\1(00)] ) Y\\Z0[F][1(-0)S0]
> debruijn example.txt f rem: λ λ 1 (1 (1 (1 (1 (1 (1 (1 (1 (1 (1 (1 (1 (1 (1 0))))))))))))))
Print some numeral 0 through 9
This definition is extendable to any finite amount; however, the best approach to printing any number would of course involve recursion.
(n λ0"0"λ0"1"λ0"2"λ0"3"λ0"4"λ0"5"λ0"6"λ0"7"λ0"8"λ0"9"0) λ0(λλλ2100)(λλ1)(n)(λλ0)(λλ1)λ0
...\debruijn> debruijn example.txt "\\1(1(1(10)))" 4
Implementations
I'm working on an interpreter for DeBruijn, but other than that, it is unimplemented. Please feel free to have a go at your own implementations and add them here.
My Python-based interpreter
Note: This is currently unfinished and it does not match the spec. In particular, no input is supported except the catchall which can be used anywhere. There may be issues with the order in which things are printed. I will update it frequently.