From Esolang
Jump to: navigation, search

(from “Ⅎunctional”) 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.

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.

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.

References