Unlambda

From Esolang
Jump to navigation Jump to search

Unlambda, designed by David Madore in 1999, is a minimal functional esoteric programming language based on combinatory logic. Notably, it was the first functional paradigm Turing tarpit.

Syntax

Unlambda is written in a parenthesis-free prefix notation; parentheses are neither necessary nor allowed. Instead, the ` prefix operator is used to apply a function to an argument; if f and x are expressions, then `fx is an expression that applies f to the argument x. Other than this operator, every other element of the language is essentially a combinator, denoting a function taking exactly one other function as argument and returning another.

Combinators

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.

Examples

Several more examples are included in the Unlambda distribution.

Palindromes

This program is a palindromic Hello, World program inspired by this Stack Overflow thread (from the Wayback Machine; retrieved on 11 October 2014): 

`.d`.c`.d`.c`.d`.c`.d``e
`````````````.H.e.l.l.o.,. .W.o.r.l.dii```````````````iid.l.r.o.W. .,.o.l.l.e.H.`````````````
e``d.`c.`d.`c.`d.`c.`d.`

Note that this program triggers a bug in at least the C interpreter (e doesn't actually exit as it should), so use another interpreter.

Instead of using e to avoid applying the padding functions, we can use d plus the fact that applying a ?x function to v has no effect: 

`?d`?c`?d`?c`?d`?c`?d``v````````````.H.e.l.l.o.,. .W.o.r.l.di`d
```````````````
d`id.l.r.o.W. .,.o.l.l.e.H.````````````v``d?`c?`d?`c?`d?`c?`d?`

The above also works in the C interpreter. Both of these methods can be used with a general program, as long as you avoid reverse syntax errors. The substitution of [?.]x with ``k[?.]x.i can be used for this.

Hello, world!

`.!`.d`.l`.r`.o`.w`. `.,`.o`.l`.l`.e`.Hi

Cat program

A cat program similar to the infamous counter2 example from the distribution: 

``cd``d`@|`cd

That program is a bit inefficient, as it builds up some growing continuations and may need to test eof several times before actually halting. The following shouldn't have that problem: 

```s`d`@|i`ci

Deadfish interpreter

See Deadfish#Unlambda.

Number I/O

The following parses a space-terminated input of decimal digits as a Church numeral. 

``
 ````sii                                                      # Actual parser
  ``s`k `s`kc
   ``s``s`ks ``s`k `s`ks ``s`k `s`kk
    ``s`k `s`kd ``s`k `s`kk ``s``s`ks ``s``s`ks k k `k
     `d ``s `k `s``s`ks ``s`kk                               # Add next digit
      ` `?0`?1`?2`?3`?4`?5`?6`?7`?8`?9                      # Parse one digit
       ```sii                       # Calculate number from i and v arguments
        ``s`k `s`kc
         ``s``s`ks ``s`kk ``s`ks ``s`kk  ``s`kd ``s`kk ``sii  `k ``s s `k`k `
          ```sii                                  # Count v arguments until i
           ``s`k `s`k `s`k c
            ``s``s`ks ``s`k `s`ks ``s`k `s`kk ``s`k `s`ks ``s`k `s`kk
             ``s`k `s`kd ``s`k `s`kk  ``s``s`ks ``s``s`ks k k  `k `s``s`ks k
            `k ``s`k `s s ``s`kk k
          `ki                                               # Initial count 0
       i                                  # Final i argument to stop counting
      `s`k                                                   # Multiply by 10
       ``s``s`ksk ` ``s``s`kski ``s``s`ksk ``s``s`kski
    `k ``s`d`k `s `@ ?  k                                     # Stop on space
  `ki                                                      # Initial number 0
 .*i                                             # Test by printing asterisks

The following (taken from the Deadfish interpreter) prints out a Church numeral in decimal. 

`
 ``s`k                                    # Actual printing function
  ```sii ``s `k `s``s``si
   `k ``s``s``si`kk
       ``s`k`s``si`k
        `k``si`k `k``si`k `k``si`k `k``si`k `k``si`k
         `k``si`k `k``si`k `k``si`k `k``si`k k
        ``s`kk ``s``s`ks``s`k`s`ks ``s`k`s`kk ``si`k`ki `ki
       ``s`k`s``s`ks``s`k`sik ``s`kk``s`kk``si`k`ki
   `ki ``s`kk
    ``s``s`ks ``s`k`s`ks ``s`k`s`kk
     `k ``s``si`k.9 `k ``s``si`k.8 `k ``s``si`k.7 `k ``s``si`k.6 `k
         ``s``si`k.5 `k ``s``si`k.4 `k ``s``si`k.3 `k ``s``si`k.2 `k
         ``s``si`k.1 `k `k.0
     ``s`kk
      ``s``s`ks``s``s`ks
       `k ``s`kc ``s`k`s`k`k`ki ``s``s`ks``s``s`ksk `k`k``si`ki `kk
       ``s``s`kskk `ki
  ``s `k`s``s`ks k i
 ``s``s`ksk ` ``s``s`kski ``s``s`ksk ``s``s`kski   # Testing with 10

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.

See also

External resources

Retrieved from "https://esolangs.org/w/index.php?title=Unlambda&oldid=147426"