Unlambda
Encyclopedia
Unlambda is a minimal, "nearly pure
" functional programming language
invented by David Madore. It is based on combinatory logic
, a version of the lambda calculus
that omits the lambda operator. It relies mainly on two built-in functions (s and k) and an "apply" operator (written `, the backquote character). These alone make it Turing-complete, but there are also some I/O functions to make it possible to interact with the user, some shortcut functions and a function for lazy evaluation. There are no variables in the language.
, Unlambda is meant as a demonstration of very pure functional programming rather than for practical use. Its main feature is the lack of conventional operators and data types — the only kind of data in the program are one-parameter functions. Data can nevertheless be simulated with appropriate functions as in the lambda calculus
. Multi-parameter functions can be represented with the technique of currying
.
Unlambda is based around the principle of abstraction elimination, or the elimination of all saved variables, including functions. As a purely-functional language, not only are Unlambda's functions first-class objects, they are the only first-class objects.
An implementation of the hello world program
in Unlambda follows:
`r```````````.H.e.l.l.o. .w.o.r.l.di
for the function that prints a newline character.
Other important features provided by Unlambda include the
. As a brief example, note that the identity function
Unlambda's one flow control construction is call with current continuation, denoted
Although Unlambda's execution semantics are normally eager
, there is a lazy evaluation
option, indicated by the use of the
Unlambda's next built-in operator is
.)
in Unlambda is facilitated by operators
There is also a "reprint" operator
Finally, there is an exit operator
Computational system on which Unlambda is based:
Purely functional
Purely functional is a term in computing used to describe algorithms, data structures or programming languages that exclude destructive modifications...
" functional programming language
Programming language
A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....
invented by David Madore. It is based on combinatory logic
Combinatory logic
Combinatory logic is a notation introduced by Moses Schönfinkel and Haskell Curry to eliminate the need for variables in mathematical logic. It has more recently been used in computer science as a theoretical model of computation and also as a basis for the design of functional programming...
, a version of the lambda calculus
Lambda calculus
In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...
that omits the lambda operator. It relies mainly on two built-in functions (s and k) and an "apply" operator (written `, the backquote character). These alone make it Turing-complete, but there are also some I/O functions to make it possible to interact with the user, some shortcut functions and a function for lazy evaluation. There are no variables in the language.
Basic principles
As an esoteric programming languageEsoteric programming language
An esoteric programming language is a programming language designed as a test of the boundaries of computer programming language design, as a proof of concept, or as a joke...
, Unlambda is meant as a demonstration of very pure functional programming rather than for practical use. Its main feature is the lack of conventional operators and data types — the only kind of data in the program are one-parameter functions. Data can nevertheless be simulated with appropriate functions as in the lambda calculus
Lambda calculus
In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...
. Multi-parameter functions can be represented with the technique of currying
Currying
In mathematics and computer science, currying is the technique of transforming a function that takes multiple arguments in such a way that it can be called as a chain of functions each with a single argument...
.
Unlambda is based around the principle of abstraction elimination, or the elimination of all saved variables, including functions. As a purely-functional language, not only are Unlambda's functions first-class objects, they are the only first-class objects.
An implementation of the hello world program
Hello world program
A "Hello world" program is a computer program that outputs "Hello world" on a display device. Because it is typically one of the simplest programs possible in most programming languages, it is by tradition often used to illustrate to beginners the most basic syntax of a programming language, or to...
in Unlambda follows:
`r```````````.H.e.l.l.o. .w.o.r.l.di
Original built-in functions
The notation.x denotes a function which takes one argument and returns it unchanged, printing the single character x as a side effect when it is invoked. i represents the version of the identity function that has no such side effect; it is used here as a dummy argument. The program `.di applies the d-printing function to a dummy argument of i, returning i and printing the letter d as a side effect. Similarly, ``.l.di first applies .l to .d, printing the letter l and returning .d; this result of .d is then applied to i as in the previous example. The function r is syntactic sugarSyntactic sugar
Syntactic sugar is a computer science term that refers to syntax within a programming language that is designed to make things easier to read or to express....
for the function that prints a newline character.
Other important features provided by Unlambda include the
k and s functions. k manufactures constant functions: the result of `kx is a function which, when invoked, returns x. Thus the value of ``kxy is x for any x and y.s is a generalized evaluation operator. ```sxyz evaluates to ``xz`yz for any x, y, and z. It is a remarkable fact that s and k are sufficient to perform any calculation, as described in SKI combinator calculusSKI combinator calculus
SKI combinator calculus is a computational system that may be perceived as a reduced version of untyped lambda calculus. It can be thought of as a computer programming language, though it is not useful for writing software...
. As a brief example, note that the identity function
i can be implemented as ``skk, since ```skkx yields x for all x.Unlambda's one flow control construction is call with current continuation, denoted
c. When an expression of the form `cx is evaluated, a special "continuation" object is constructed, representing the state of the interpreter at that moment. Then x is evaluated, and then the result is given the continuation object as an argument. If the continuation is never applied to an argument, the value of the `cx expression is the same as the value of x. But if the continuation object is applied to a value y, execution of x is immediately aborted, and the value of the entire `cx expression is y.Although Unlambda's execution semantics are normally eager
Eager evaluation
In computer programming, eager evaluation or greedy evaluation is the evaluation strategy in most traditional programming languages. In eager evaluation an expression is evaluated as soon as it gets bound to a variable. The term is typically used to contrast lazy evaluation, where expressions are...
, there is a lazy evaluation
Lazy evaluation
In programming language theory, lazy evaluation or call-by-need is an evaluation strategy which delays the evaluation of an expression until the value of this is actually required and which also avoids repeated evaluations...
option, indicated by the use of the
d operator. Usually, to evaluate an expression of the form `xy, unlambda first evaluates x, then y, and then applies x to y. However, if x evaluates to the special value d, then y is not evaluated; instead, the value of the expression `dy is a special "delayed computation" object, which, when applied to an argument z, evaluates y, and then applies its value to z. Note that in the absence of side effects, this is exactly the same as `iy. The difference is that `iy executes any side effects in y immediately, whereas `dy defers the side effects until the result is applied to another argument.Unlambda's next built-in operator is
v, which ignores its argument and returns v. This feature is not strictly necessary, since v could be implemented as ```s``k``sii``s``s`ksk`k``siik, but it is supplied as a convenience. (This expression above is simply `Yk, where Y denotes a fixed point combinatorFixed point combinator
In computer science, a fixed-point combinator is a higher-order function that computes a fixed point of other functions. A fixed point of a function f is a value x such that x = f. For example, 0 and 1 are fixed points of the function f = x2, because 0 = 02 and 1 = 12...
.)
Unlambda 2 built-in functions
Additional built-ins were introduced in version 2 of the Unlambda language. InputInput/output
In computing, input/output, or I/O, refers to the communication between an information processing system , and the outside world, possibly a human, or another information processing system. Inputs are the signals or data received by the system, and outputs are the signals or data sent from it...
in Unlambda is facilitated by operators
@ and ?u. When @ is applied to a function x, a character is read from input, and stored as the "current character"; then x is applied to i. However, if no more characters were available on input, the "current character" is left undefined, and x is applied to v instead. When a function ?u is applied to a function x, the result is the evaluation of `xi if the current character is u, otherwise `xv is evaluated.There is also a "reprint" operator
|. When `|x is evaluated, the function x is applied to .u if u is the current character, or to v if there is no current character.Finally, there is an exit operator
e. When e is applied to x, the execution of the program is terminated, and x is taken as the result of the program (most of the currently existing interpreters ignore the result anyway).See also
Similar languages:- Iota and JotIota and JotIota and its successor Jot are Turing tarpits, esoteric programming languages that are designed to be as small as possible but still Turing-complete. Each uses two symbols and involves two operations, with simple denotational semantics defined in terms of lambda calculus...
- Lazy K
Computational system on which Unlambda is based:
- SKI combinator calculusSKI combinator calculusSKI combinator calculus is a computational system that may be perceived as a reduced version of untyped lambda calculus. It can be thought of as a computer programming language, though it is not useful for writing software...