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 => 0 => (!()) 1 => () 2 => (:*) 3 => (::**) 4 => (:::***) 5 => (::::****) 6 => (:::::*****) 7 => (::::::******) 8 => (:::::::*******) 9 => (::::::::********) 10 => (:::::::::*********) 11 => (::::::::::**********) (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 "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) '(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 '.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)