Unlambda
From Esolang
Unlambda, designed by David Madore, is a minimal functional esoteric programming language based on combinatory logic. It is Turing-complete thanks to its built-in s and k combinators and the apply operator, ` (backquote). Furthermore, some input/output functions are available. Unlambda is a functional Turing tarpit.
Unlambda is essentially a version of combinatory logic. It is written in prefix notation, so parentheses are neither necessary nor allowed. The apply (prefix) operator ` takes exactly two arguments and otherwise works the same as parentheses in combinatory logic or lambda calculus. This is the only operator; every other element of the language is essentially a combinator, denoting a function taking exactly one other function as argument and returning another. A combinator does not automatically take its argument, instead the ` operator is used to apply one combinator to another. However, the d and c combinators complicate this somewhat.
The following combinators are defined:
s takes three arguments (via currying) and applies each of the first two to the third and applies those to each other and returns the result, that is, ```sxyz evaluates to ``xz`yz.
k takes two arguments (via currying) and returns the first.
i takes one argument and returns it.
v takes one argument and returns v.
.x (where x is any character) takes one argument and returns it, with the "side effect" of printing x.
r is an abbreviation for .newline.
d as a function simply takes two arguments and applies the first to the second, but in an expression it has a special effect: the second argument must be evaluated before the first. While d has only one argument, that argument is not evaluated. (For example, ``d`.xi`.yi evaluates `.yi first, outputting y and returning i. Now since the second argument has been evaluated, d acts like the identity function i, so we have ``i`.xii, which evaluates to i and outputs x: the whole program outputs yx rather than xy due to d's special order-of-evaluation rules.)
c takes one argument. When applied, c creates a continuation out of the program's current state and applies the argument to this continuation.
A continuation is a special function that, when applied to an argument, "goes back in time" to when the continuation was created and makes the c function that created it return the continuation's argument instead of what it normally would. An example:
``cii (This function creates a continuation (`*i). See meta-notation below.)
``i(`*i)i (Now the function i is being applied to the continuation.)
`(`*i)i (i returns (`*i) as normal.)
(Applying (`*i) takes us "back in time"...)
`ii (...and changes the original `ci to the argument that (`*i) was applied to, which is i.)
i (`ii is evaluated, returning i as normal.)
The following combinators were added in Unlambda version 2:
e takes one argument. When applied, e exits the program, possibly providing its argument as the program's result. Put another way, e is an abbreviation for a continuation, the one in which the whole program is run.
@ takes one argument. When applied, it tries to read a character of input, making it the current character. It then applies its argument to i if successful or to v if not (for example on EOF).
?x takes one argument. When applied, it compares the current character to x, and then applies its argument to i if equal and to v if not (or if no character has been read, or EOF has been reached).
| takes one argument. When applied, it applies its argument to .x, where x is the current character, or to v if no character has been read, or EOF has been reached.
[edit] Meta-notation
For reasoning about Unlambda programs, or for displaying partially evaluated expressions, it is useful to have a notation for ongoing computations and continuations. These suggestions are not part of the language proper, but can be added to debugging implementations.
- To denote a continuation, write an expression in parentheses, with a * character at the spot where a value may be returned.
If the continuation is applied to an argument, that argument is substituted for the *, and the resulting expression in parentheses replaces the whole program.
Using the e combinator and considering * as a variable, this notation may be taken as an abbreviation for a lambda expression: (expression) = ^*`e expression. Alternatively, it may be considered an "inside-out" printing of the actual continuation structure used by some implementations.
In order for a continuation to have the intended meaning, the * should be at a spot in the expression where the next evaluation may take place, that is, everything before it should have been already evaluated, and it should not be inside a promise ('d expression). There might be more than one * in a continuation, but only one is not nested in further parentheses (representing embedded continuations).
- To distinguish between expressions and already evaluated functions, use a different notation for the latter, replacing the ` character by ' (a forward quote).
An evaluated function will then not contain ` except after a 'd (because d "freezes" unevaluated expressions) or inside an embedded continuation.
- To shorten notation or to make structure sharing explicit, define names for common subexpressions.
We borrow the $v notation from the unlambdaifier tool, and let $v=expression or function. The assignment may be listed separately or for example embedded in the expression at the first spot where the subexpression is used. To embed continuation variables in this way we may use an inside-out notation such as (=$x:...) for definition and ($x:...) for referencing.
A shorter notation for inside-out continuation variables is to use other types of brackets, such as [...] or <...>.
- Using these notations it is possible to evaluate Unlambda programs in an equational style. If you wish to substitute such equations into expressions, note that instances of the (...) notation in the equation also need to be substituted by the continuation of the subexpression.
For example, the equation `cc = (*) is valid. When substituting this into `c`cc, we must also substitute (`c*) for (*), giving `c`cc = `c(`c*). Note that we can only do this for subexpressions that are next in order for evaluation, at a spot where a * would be allowed. This restriction does not apply for equations that do not contain the (...) notation.
[edit] See also
[edit] External resources
- Unlambda website
- The Comprehensive Unlambda Archive Network, a collection of Unlambda programs
- Combinator calculator and partial unlambda interpreter (see also: Combinator birds)
- Unlambda in K
- Slow Unlambda PHP
