World Library  
Flag as Inappropriate
Email this Article

Unlambda

Article Id: WHEBN0000146927
Reproduction Date:

Title: Unlambda  
Author: World Heritage Encyclopedia
Language: English
Subject: Quine (computing), Joy (programming language), Combinatory logic, Code golf, Parrot virtual machine
Collection:
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Unlambda

Unlambda is a minimal, "nearly pure"[1] 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.

Basic principles

As an esoteric programming 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:[1]

`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 sugar 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 calculus. 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, there is a lazy evaluation 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``s``s`kskk`k``s``s`kskk, but it is supplied as a convenience. (This expression above is simply `Yk, where Y denotes a fixed point combinator.)

Unlambda 2 built-in functions

Additional built-ins were introduced in version 2 of the Unlambda language. Input 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

References

  1. ^ a b
  • Felix-Hernandez Campos (1 April 2002), Lecture 28: More on functional programming, University of North Carolina COMP144

External links

  • Unlambda homepage
  • Online Unlambda REPL
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.