Imapl

ImAPL is a programming language created by the user Lemon enthusiast in 2015.

ImAPL is based on the idea of completely immutable data structures. The "variables" in ImAPL can't be changed during a program's execution, but are required to be equal to certain values at some points.

Etymology

ImAPL stands for Immutable Array Programming Language.

Semantics

Commands

Consider any two expressions, a and b:

a=b.     When this command is executed, a is already equal to b.
a=b!     Same as above.
a=b?     If a is not equal to b, skips to right after the next command that ends with a dot.

All non-printable characters in the source code are ignored. This includes, for example, tabulations and newlines, but not spaces.

Constants

Instead of variables, ImAPL has named constants.

The basic types are scalars, which are just natural numbers, and arrays, which can contain elements of any types.

Some ways to define a scalar in ImAPL:

N=50.
N=50!
N+N+N=100+N.

Arrays can be constructed with elements preceded by spaces:

a= 1 2 3 4.

The space is actually the append operator, which enlongates a array by adding the second argument as a new element. The first space (before the "1") has two arguments, the empty array and the number one.

This shows that empty arrays are representable by the empty string:

empty=.

Using parenthesization, we can change the usual application order and make nested lists:

Nested= ( 1 2 3) ( 4 5 6) ( 7 8 9)!

We can also easily create arrays with the ascii values of printable characters (excluding quotation marks):

b="Hello!".

Which is equivalent to:

b= 72 101 108 108 111 33.

Other characters can be written as numbers and concatenated:

2Lines="The following is written on the second line:"& 10&"The previous is written on the first line".

Constant names:

Constants can be named basically anything, as long as their names don't include non-printable characters and characters reserved for commands or operators. Constant names also can't be interpretable as arrays or number, but those are practically the only restrictions:

A number:
123

An array:
"abcdef"

A valid constant name:
7'$%"ab("12)31"2312""de11f"'12

Operators (Ordered by precedence):

Binary operators are left-associative.

Operator      Type                Effect
a b        Arr,Any->Arr      Appends b as an element after a.
a*b        Num,Arr->Arr      Creates array with b elements, all equal to a.
a+b        Num,Num->Num      Adds two natural numbers.
a&b        Arr,Arr->Arr      Concatenates two arrays.
X¨         Opr->Opr          Returns an array where the nth element is obtained by applying the operation X with the nth element(s)
                             of the argument(s). Gives error if the arguments are not arrays of same length. X can also contain ¨.

Operators can also give errors if passed arguments of the wrong type.

Execution:

When the program is executed, the constant % is set to the one-time input for the program. The other constants are set in a way that makes the program run without any errors. It may be impossible, then the program may exit without producing output.

If there is more than one such possibility, one of the (possibly infinitely many) sets of acceptable values is chosen at random.

The other special constant, $, represents the output's bytes, and also produces an error unless it is equal to an array of numbers in the range [0,255].

Computational class

The author of the language is trying to show that ImAPL is turing-complete, by implementing a string-rewriting language similar to Thue, but with an extra halting symbol.

A single array should contain every state of the machine until the halting point. The program therefore results in an error for any machine that does not halt, but that's still sufficient for turing completeness. By removing either its first or last element, it can be compared to itself and made to satisfty one of the acceptable transition functions between states.