|Computational class||Turing complete|
In this language, everything is either a structure, or a function. Each of them has a name and arguments.
A structure is a passive entity. It has a name and zero or more arguments. It is like a named array.
A function is an active entity. It takes one or more arguments (so at least one argument must be provided) and returns a boolean value (bit), which is either
(1) are names of structures and they take zero arguments.
There are two ways to call a function. If you pass the same number of arguments that appear in the function definition, then the function definition will be expanded until the call returns a bool. However, if you call a function with one argument less, the function will return any structure such that when that structure is appended to the previous arguments, the function returns
The main function is named
main and it takes two arguments: input and output.
Both input and output contain a single structure (with arbitrary deep nested structures). The output is any structure such that when
main is called with the input and the output it returns
(1). If there is no such structure, the program does not halt.
Interpreter inspects all possible return values of all function calls and if it can find an output structure such that there is at least one combination of function call and return value pairs such that the main function terminates and returns
(1), then that output structure is the output of the program.
Source code consists of function definitions. Each function definition consists of two parts: formal arguments and return value. As said, return value must be a bool. Each function and structure consist of function/structure name and space-separated arguments, all of that encapsulated in a pair of parentheses. Structure is everything that is not a function. Functions cannot appear in formal arguments. Formal argument variables are represented by identifiers. Example:
(main x y) (1)
In the example above, there is a single function
main and of course it takes two arguments, which are named
y (they can be any structures). The function returns
(1), which is a truthy value, so any input-output pair is valid. In other words, this program prints random output for all inputs. Interpreter can even introduce new structures that do not appear in the input.
All function calls whose parameters cannot be matched by any overloaded definition implicitly return
Warning: Examples are not tested on a real interpreter. There may be mistakes in the snippets.
(main x x) (1)
Explanation: the function returns
(1) if the input is equal to the output, and we achieved that by naming both parameters
x. Note: if we named the parameters using distinct identifiers, that would not imply that the actual parameters must be distinct. The
main function returns
(0) for all cases that are not specified, so therefore it returns
(1) iff the input is equal to the output.
(main x (output (H) (e) (l) (l) (o) (,) (space) (W) (o) (r) (l) (d) (!))) (1)
Explanation: we implicitly defined structs for each letter from the output and we also defined
space for the space character and we defined struct
output which contains all the output characters. Input is ignored (output does not depend on the input
(main x y) (= y (palindrome x)) (= x x) (1) (palindrome x) (= x (reverse x)) (reverse x y) (= y (rev x (nil))) (rev (nil) x r) (= r x) (rev (pair x y) z r) (= r (rev y (pair x z)))
(1) if the input is a palindrome, and outputs
(0) otherwise. Format of the string is the following: empty string is
(nil) and prepending a bit
b before string
s is represented as
(pair b s), where
b is either
(main x x) (= x (0)) (= x x) (1)
Explanation: we assert that the input is equal to the output and that the input (and the output) is
(0). In other words, if the input is
(1) for output
(0), so the output is
(0). However, if the input is anything that is not
(0), then we cannot match the main function, so the program does not halt. One may argue that the program does not keep outputting
(1) if the input is
(1), but actually, the output cannot be examined until the program halts, so if the program does not halt, the output is undefined.
Random number generator
(main x (5)) (1) (main x (7)) (1)
(7) with implementation-dependent probability.