This is a definition of Underlambda in terms of rewrite rules. They
can be run in any order, Thue-style, but Underlambda cannot be
trivially expressed in Thue due to the need to match arbitrary strings
with balanced parentheses, which Thue does not have. (That is, the
rules can be run in any order except for those in tiers 5 and 5a,
which take precedence over all other rules; the precedences are
mentioned in those tiers.)
Note that all Underlambda programs must start with a magic line, which
starts like this:
#! /usr/bin/env underlambda
Other things may appear on the magic line after this, and specify
command-line parameters to the interpreter or compiler; but putting
anything there other than either nothing or a single carriage return
is not portable. (All Underlambda implementations must use newline =
10; however, implementations that implement tier 4 will disregard
carriage returns in most contexts, so it is reasonably easy to write
an Underlambda program which is portable to both ^J and ^M^J line
endings.) The very last character of an Underlambda program must be |
(anything after that is not part of the program; interpreters may but
need not interpret it as input to the program). The characters # and
| are not allowed in any other context in an Underlambda program, and
the characters { and } are not allowed anywhere at all. In addition,
parentheses and square brackets must be matched.
In what is shown below:
w, x, y and z are (possibly null) strings with balanced parentheses
X refers to any number of consecutive strings with balanced
parentheses (including 0), each of which is itself enclosed in
parentheses
# refers to the start of the program
| refers to the end of the program
(Any number includes 0).
Notes about tier 1a
iochar is an integer. It must be able to take any value in the range
0 to 128 inclusive; if a program would change it out of that range,
undefined behaviour results. However, interpreters should preferably
be able to increase the iochar up to at least 0x110000 (the maximum
code point a Unicode character can have, plus one); failing that, to
256, so that extended-ASCII and 8-bit binary characters can be read or
written. Underlambda character codes are equal to ordinary ASCII7 or
Unicode character codes (which are the same for ASCII7 characters, and
ASCII7 character codes obviously don't exist for non-ASCII7
characters), but with 1 added to each character code (and EOF is 0).
All operations in tiers 2a, 3a, 4a, etc., can clobber iochar, which is
only used by the tier 1a commands.
Notes about tier 2a
The Underload requirement - that S outputs the source code of the
function in question - has been relaxed. Underlambda is designed such
that an Underlambda interpreter needn't manipulate the literal source
code strings at all, but can instead manipulate functions (an
Underlambda function maps a stack of functions onto another stack of
functions, and sometimes has side effects). The S command outputs a
function as text (an operation known as serialisation of the
function), but the form that the output takes is
implementation-defined. The only restriction is that an invocation of
D by the same program can read the function back in and end up with an
indistinguishable function from the one written out by S. Possible
forms that the output could take include, but are not limited to, the
function's literal Underlambda source code (which is what Underload
always did), optimised Underlambda source code, source code in some
other language, and a binary dump of an interpreter or compiler's
internal data structure. It should be possible to write serialised
data in one invocation of an interpreter or compiled program and read
it in another, as long as the source code for the programs was
identical; however, compiled programs need not be able to deserialise
data that was serialised before the program was last recompiled, even
if their source code didn't change.
Notes about tier 3
The 'storage stack' is a stack of Underlambda functions. Although
these rewrite rules do not imply it, almost all the Underlambda
commands can be seen as operating on a 'main stack' (which in many of
the rewrite rules below corresponds to X); the storage stack is a
different stack from the main stack.
Notes about tier 4
Certain operations in tier 4 are allowed to have undefined behaviour
if (x) isn't a Church numeral. A parenthesised string (x) is defined
to be a Church numeral iff the Underlambda program
#! /usr/bin/underlambda
X(y)(x)^z|
is equivalent to
#! /usr/bin/underlambda
X(yyyyyy)z|
for some number of repetitions of y (not necessarily 6) for all X, y,
and z that contain only characters in Tier 1; the 'value' of the
Church numeral is the number of repetitions of y that are needed for
the equivalence to hold. Note that in general, it is an uncomputable
problem to determine whether a particular function is a Church numeral
or not. The rewrite rules below specify one implementation that works
the correct way for all Church numerals; but for the
undefined-behaviour-if-not-a-Church-numeral commands, it is permitted
to give a result different to that which the rewrite rule suggests if
the relevant string happens to not be a Church numeral (but the same
result, or an 'as-if' equivalent result, must be obtained in all cases
where the relevant string was a Church numeral).
Tier 1: Minimal Turing-completeness
(x)! =>
(x)^ => x
(x)(y)* => (xy)
(x)(y)~ => (y)(x)
(x)a => ((x))
#X(x): => X(x)(x)
Tier 1a: iochar-based character I/O
#Xo => X (side effect: iochar = 0)
#Xh => X (side effect: increment iochar)
#Xi => X (side effect: iochar = read one character)
#XO => X (side effect: output iochar as a char)
#XH => X (side effect: decrement iochar)
#X(x)I => X() (if iochar is 0)
#X(x)I => X(x) (if iochar is not 0)
Tier 2: Metaprogramming
#XQy| =>
#XCx| => X(X(x))x
Tier 2a: Serialisation of codeblocks
#X(x)S => X (side effect: serialise (x) to output)
#XD => X(x) (side effect: deserialise (x) from input)
Tier 3: Stack and storage stack manipulation
#X(x)> => X (side effect: push (x) on storage stack)
#> => (side effect: push () on storage stack)
#X< => x (side effect: pop (x) from storage stack)
#XA =>
#(x)n => ()
#X(x)(y)n => X(x)(y)
Tier 4: Church numerals
<whitespace> =>
0 => (!())
1 => ()
2 => (:*)
3 => (::**)
4 => (:::***)
5 => (::::****)
6 => (:::::*****)
7 => (::::::******)
8 => (:::::::*******)
9 => (::::::::********)
10 => (:::::::::*********)
11 => (::::::::::**********)
<and so on; two consecutive integers must be separated by whitespace
so that they don't look like one larger integer>
(x)+ => (:x*) (may be UB if x isn't a Church numeral)
(x)- => ((:)x(!!()())*(*)x*)(!(!()))(!())x^^
(may be UB if x isn't a Church numeral)
(x)p => (+)x^ (may be UB if x isn't a Church numeral)
(x)m => (-)x^ (may be UB if x isn't a Church numeral)
Tier 4a: Character I/O by character code
(x); => o(h)x^O (may clobber iochar in a different way)
? => i(!())(I(H~(:)~*(*)*~^)I^^):^
(may clobber iochar in a different way)
Tier 5: Syntax that needs preprocessing
<has a higher priority than any other rule>
"x" => ((y)(z)...) (y is the char code of the first character in
x, z of the second character, and so on until
there are the same number of () groups as
characters in the ""-quoted string; x may not
contain the " character)
<each rule here has a higher priority than all rules following in the
tier, and a higher priority than all rules not in tier 5 or 5a>
'(x) => ((x))
'x => (x) (x must be one char which is not #|[](){}')
(x)\y\z => ((x)\y)\z^ (y and z are each a literal w, x, y or z)
(x)\y^\z => ((x)\y^)\z^ (y and z are each a literal w, x, y or z)
(w(x)y)\z => ::(x)\za~(y)\z*~(w)\z~*
(z is a literal w, x, y or z,
w, x, and y don't contain \)
(xzy)\z => ::(y)\z*~(x)\z~*
(z is a literal w, x, y or z,
x and y don't contain \)
(x)\z => !(x) (z is a literal w, x, y or z,
x doesn't contain \)
Tier 5a: I/O syntax that needs preprocessing
<these rules have higher priorities than any other except the first rule in
tier 5, the first has a higher priority than the second>
'.x => ((y);) (in both rules, x must be one character which
.x => (y); is not #|[](){} and y is its char code as a
Church numeral)