Ⅎ
Ⅎ (from “Ⅎunctional”, may be called “turned F” in ASCII contexts or when lazy to type) is undoubtedly an essence of an equational functional language. Its idea is simple, so it probably was stumbled upon by many, including User:Oerjan and User:Arseniiv [1]. Currently, the description here is as the latter of them sees fit.
Overview
The program is a series of function definitions, each as simple as a sole expression involving function’s arguments and other functions. There could be a restriction to use only names already defined at this point, including (Ⅎ′) or excluding (Ⅎ″) the one currently defined; such a restriction doesn’t matter for language expressivity.
When program is run, a function named main is evaluated. Overall evalution strategy is call-by-need, unless a modification (for example, to allow full IO) has something like Haskell’s seq or $!. When there’s nothing to evaluate, the resulting expression is printed.
The #Trivia section elaborates on things implied by the context in which this language was conceived.
Examples
Simplest unterminating program in Ⅎ/Ⅎ′:
main = main.
and in Ⅎ″:
w x = x x. main = w w.
A boolean conjunction (0 ∧ 1 in the example):
0 then else = else. 1 then else = then. and x y = x y 0. main = and 0 1.
Syntax
There we’ll go technical for a bit, to allow maximal freedom to both possible users and implementers.
Lexical
Whitespace should contain U+20 SPACE, U+09 CHARACTER TABULATION, CR and LF characters at least, and all Unicode characters with property WSpace at most. Identifier characters should contain all printable non-space ASCII characters U+21…U+7E except .=() at least, and all of Unicode general categories L, M, N, P, S except .=() at most.
High-level
The grammar in EBNF:
Program = Definition+
Definition = Identifier Arguments "=" Expression "."
Arguments = Identifier*
Expression = ClosedExpression+
ClosedExpression = Identifier | "(" Expression ")"
If an argument is eponymous with an already defined function, that function should be shadowed out in the definition’s body.
Let expressions
For purposes of being a lesser tarpit, one could, without a trace of shame, add let … in … expressions:
Expression = LetExpression | ClosedExpression+ LetExpression = "let" Definition+ "in" Expression
Now go depend on context and incapsulate all you want!
Trivia
This section can be useful for implementers not familiar with modern equational functional languages like Haskell, F# or Scala.
Expressions of form f args are well-formed even if there are less arguments given than declared for f—this is called partial application and results in a function which waits for more arguments until it can proceed to evaluate. This feature allows to define various data structures, like tuples or lists, and values like natural numbers or booleans.
Call-by-need strategy is a practical lazy evaluation strategy. Suppose we have a definition for f x1 ... xn. When evaluating f arg1 ... argn, no argument is evaluated until needed—that is, until we proceed to evaluate an application of form (xi ...) from the definition, and after argi is evaluated, we replace all occurences of xi by the result—in this regard, this strategy is different from call by name. Of course a sane implementation wouldn’t construct huge terms by multiple replacements, it can store occurrences of each xi in expression as references to the same mutable object that holds unevaluated argi at first, and then holds the result.
Lazy evaluation allows one to define things like conditionals. For example, one can first define boolean values like this:
0 then else = else. 1 then else = then.
and then write c t e for if c then t else e. Then, t will not be evaluated if c is 0, and vice versa.
As mentioned above, an implementation can have means to control evaluation order, for example a seq primitive. When evaluating seq a b, the first argument is forced first, then the second is returned. The usual idiom is to place a variable as a which needs to be fully evaluated in b. If a doesn’t have any variables in common with b, doesn’t diverge or have side effects, then seq a b is fully equivalent to b, albeit evaluated slower due to forcing of a.
Now you can’t say the article is obscure.
Power
The language is obviously as powerful as combinatorial calculus, so is Turing-complete.
Furthermore, it is TC even if only one pair of parentheses is allowed, as one can define classic combinators
K x y = x S x y z = (x z) y z
then expand main in this basis, and finally extract all parenthesized subexpressions there into separate definitions.
If parentheses are banned altogether, the language is a push-down automaton, as each function effectively turns into a pattern match on the head of a list of functions, and there's no way to group multiple list elements into a single element.
See also
Combinatory logic, the corresponding computational model.