StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>It depends on what you mean by minimal. </p> <p>To start with, the ancestor of functional languages is, first and foremost, <strong>mathematical logic</strong>. The computational use of certain logics came after the fact. In a sense, many mathematical systems (the cores of which are usually quite minimal) could be called functional languages. But I doubt that's what you're after!</p> <p>Best known is <a href="http://en.wikipedia.org/wiki/Alonzo_Church" rel="noreferrer">Alonzo Church</a>'s <a href="http://en.wikipedia.org/wiki/Lambda_calculus" rel="noreferrer">lambda calculus</a>, of which there are variants and descendants:</p> <ul> <li><p>The simplest form is what's called the <strong>untyped lambda calculus</strong>; this contains nothing but lambda abstractions, with no restrictions on their use. The creation of data structures using only anonymous functions is done with what's called <strong>Church encoding</strong> and represents data by fundamental operations on it; the number 5 becomes "repeat something 5 times", and so on.</p></li> <li><p>Lisp-family languages are little more than untyped lambda calculus, augmented with atomic values, cons cells, and a handful of other things. I'd suspect Scheme is the most minimalist here, as if memory serves me it was created first as a teaching language.</p></li> <li><p>The original purpose of the lambda calculus, that of describing logical proofs, failed when the untyped form was shown to be inconsistent, which is a polite term for "lets you prove that false is true". (<em>Historical trivia: the paper proving this, which was a significant thing at the time, did so by writing a logical proof that, in computational terms, went into an infinite loop.</em>) Anyway, the use as a logic was recovered by introducing <strong>typed lambda calculus</strong>. These tend not to be directly useful as programming languages, however, particularly since being logically sound makes the language not Turing-complete.</p></li> <li><p>However, similarly to how Lisps derive from untyped lambda calculus, a typed lambda calculus extended with built-in recursion, algebraic data types, and a few other things gets you the extended ML-family of languages. These tend to be pretty minimal at heart, with syntactic constructs having straightforward translations to lambda terms in many cases. Besides the obvious ML dialects, this also includes Haskell and a few other languages. I'm not aware of any especially minimalist typed functional languages, however; such a language would likely suffer from poor usability far worse than a minimalist untyped language.</p></li> </ul> <p>So as far as lambda calculus variants go, the pure untyped lambda calculus with no extra features is Turing-complete and about as minimal as you can get!</p> <p>However, arguably more minimal is to eliminate the concept of "variables" entirely--in fact, this was originally done to simplify meta-mathematical proofs about logical systems, if memory serves me--and use only higher-order functions called <strong>combinators</strong>. Here we have:</p> <ul> <li><p><a href="http://en.wikipedia.org/wiki/Combinatory_logic" rel="noreferrer">Combinatory logic</a> itself, as originally invented by <a href="http://en.wikipedia.org/wiki/Moses_Sch%C3%B6nfinkel" rel="noreferrer">Moses Schönfinkel</a> and developed extensively by <a href="http://en.wikipedia.org/wiki/Haskell_Curry" rel="noreferrer">Haskell Curry</a>. Each combinator is defined by a simple substitution rule, for instance <code>Sxyz = xz(yz)</code>. The lowercase letters are used like variables in this definition, but keep in mind that combinatory logic itself doesn't use variables, or assign names to anything at all. Combinatory logic is minimal, to be sure, but not too friendly as a programming language. Best-known is the <strong>SK</strong> combinator base. S is defined as in the example above; K is <code>Kxy = x</code>. Those two combinators alone suffice to make it Turing-complete! This is almost frighteningly minimal.</p></li> <li><p><a href="http://www.madore.org/~david/programs/unlambda/" rel="noreferrer">Unlambda</a> is a language based on SK combinators, extending it with a few extra combinators with special properties. Less minimal, but lets you write "Hello World".</p></li> <li><p>Even two combinators is more than you need, though. Various one-combinator bases exist; perhaps the best known is the <strong>iota Combinator</strong>, defined as <code>ιx = xSK</code>, which is used in a minimalist language also called <a href="http://en.wikipedia.org/wiki/Iota_and_Jot" rel="noreferrer">Iota</a></p></li> <li><p>Also of some note is <a href="http://homepages.cwi.nl/~tromp/cl/lazy-k.html" rel="noreferrer">Lazy K</a>, which is distinguished from Unlambda by not introducing additional combinators, having no side effects, and using lazy evaluation. Basically, it's the Haskell of the combinator-based-esoteric-language world. It supports both the SK base, as well as the iota combinator.</p></li> </ul> <p>Which of those strikes you as most "minimal" is probably a matter of taste.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload