ELEMENTARY
ELEMENTARY is both a computational class, and an informal category of programming languages that are each able to implement all programs in that computational class. These programming languages are generally "naturally occurring" languages / weird machines rather than being intentionally created, and tend to occur as a subset of practical programming languages. This article primarily discusses the view of ELEMENTARY as a programming language.
Syntax
An ELEMENTARY program is written as an expression in one or more variables, using the standard grammar for writing expressions in practical programming languages:
expression ::= constant | variable | (expression op expression)
Constants are non-negative integers, written in decimal, and variables are strings of letters/digits/underscores that start with a letter. For example, (a + 4) % (b % a) is a valid expression (and thus a valid complete ELEMENTARY program). Some ELEMENTARY interpreters support operator precedence as an extension, but it is always possible to avoid the need for operator precedence by fully parenthesizing the expressions.
The set of operators supported varies from implementation to implementation. The most important operators (that all implementations must support) are addition, modulus, and either or both of two exponentiation-like operations:
| Name | Operator | Description |
|---|---|---|
| Addition | + |
Returns the sum of the two operands. |
| Modulus | % |
Returns the remainder upon dividing the first operand by the second (producing a result in the range from 0 inclusive to the second operand exclusive). If the second operand is 0, exits the program with an error (programs can always be written to avoid this case, so some interpreters may choose not to implement it). |
| Exponentiation | ** |
Returns the first operand raised to the power of the second operand. If both operands are 0, returns 1. |
| Left-shift | << |
Returns the first operand times 2 to the power of the second operand. |
Implementations may choose to restrict their exponentiation-like operator to make it a "2 to the power of" operation (by requiring it to be used only in the contexts (2** expression) or (1<< expression)), without reducing the computational power of the language. ELEMENTARY is thus usually defined by the set of the three basic operations "addition, modulus, 2 to the power of".
It is common for ELEMENTARY interpreters to also provide support for other operators, but all of these are optional. Some which can be expressed directly in terms of the other operators include:
| Name | Operator | Description |
|---|---|---|
| Multiplication | * |
Returns the product of the two operands. |
| Floor-division | / |
Divides the first operand by the second operand, and returns the integer part of the result. Division by 0 has the same effect as modulus by 0. |
| Monus | ∸ |
If the first operand is larger than the second, returns the result of subtracting the second operand from the first. Otherwise, returns 0. (This is a modified subtraction operation that is adapted for use with ELEMENTARY.) |
| Bitwise AND | & |
Returns a number for which each binary digit is 1 if and only if both operands have a 1 in the same location (i.e. with the same place-value) when written in binary. |
| Bitwise OR | | |
Returns a number for which each binary digit is 1 if and only if at least one operand has a 1 in the same location (i.e. with the same place-value) when written in binary. |
| Bitwise XOR | ^ |
Returns a number for which each binary digit is 1 if and only if exactly one operand has a 1 in the same location (i.e. with the same place-value) when written in binary. |
| Right-shift | >> |
Divides the first operand by 2 to the power of the second operand, and returns the integer part of the result. |
Interpreters might also support comparison operators (<, >=, etc.), which return 1 (or a value that acts like 1 when used as a number) for true or 0 for false.
Subtraction cannot be directly expressed in terms of the three basic operators (because it can produce negative values, which can't be produced by any of ELEMENTARY's basic operators, and could then indirectly produce non-integer values by using a negative number as an exponent), but does not increase the computational power of the language (it is possible to compile an ELEMENTARY-plus-subtraction program into an ELEMENTARY program that performs the same calculations, but it might not be able to return the same result due to the language having no way to output anything other than non-negative integers). Likewise, adding operators that do floating-point calculations does not increase the computational power of the language.
Semantics
An ELEMENTARY interpreter is provided with the program to run, together with a value for each variable in it. The interpreter then evaluates the expression (using unbounded integers) and outputs the result – there is no control flow and any program must necessarily halt.
Computational class
As mentioned in the introduction, ELEMENTARY has its own computational class, which is documented at wikipedia:ELEMENTARY. This class is surprisingly powerful, being able to implement any polynomial-time algorithm and solve every NP-complete problem, although it is less powerful than the primitive recursive functions.
Most operators that practical programming languages support are technically unnecessary in ELEMENTARY because they could be defined in terms of the three basic operators (Wikpedia has some examples). Likewise, if the basic exponentiation-like operation is exponentiation or "2 to the power of", constants are also unnecessary: given a variable x it is possible to produce an expression that can never have the value 0 as (x ** x) or (2** x) / (1<< x); call such an expression E, then 0 can be expressed as E % E, 1 can be expressed as (0 ** 0) or (2** 0), and other constants can be produced by addition.
Programming in ELEMENTARY is normally done by creating a large number for which you can divide the digits of that number (in some base) into groups, with each group representing a partial computation that is being done in parallel. Some good examples of the technique (including both the programs themselves and explanations of how they work) can be found in this Code Golf Stack Exchange question.
As a subset
ELEMENTARY is trivially able to compile into most practical programming languages that support unbounded integers (because it is very common for such languages to support addition, modulus, and at least one of exponentiation or left-shift), often with the same syntax. Notably, both Python 2 and Python 3 contain the three basic operators with the same syntax (and many of the others, too), meaning that programs like ipython3 can be used directly as ELEMENTARY interpreters. However, ELEMENTARY tends to make very heavy use of nested exponentations to perform even simple calculations, meaning that for practical use, you would want an interpreter that optimizes these.