EsoPost

An EsoPost program consists of a sequence of operators. At the beginning of the program, all operators in the program are pushed to the execution stack in reverse order, so that the first operator is on the top. All operators are initially inactive, except 8 and 9 are initially active. The data stack is initially empty.

There are two stacks, the data stack (also just called "the stack") and the execution stack. There is also the dictionary, which maps keys to values. Objects on both stacks, and keys and values, come in three types:

• Operator: One of the eight predefined operators numbered 0 to 7. What happens when an operator is executed depends on the operator.

• Mark: There is only one such value of this type, and there is no distinction of whether it is active or inactive (it is always treated as inactive; trying to activate it just leaves it inactive). Marks are only in the data stack and as keys as values in the dictionary; a list cannot contain marks, and neither can the execution stack.

• List: A list contains zero or more objects in sequence, and can include other lists. The only object that can't be in a list is a mark. All empty lists are the same list (although some empty lists may be active and some may be inactive), but non-empty lists are distinct even if they contain the same contents. Non-empty lists are "by reference", so if you put multiple copies of the same non-empty list on the stack (rather than constructing multiple lists with the same data) then they are the same. Executing it results it pushing its contents to the execution stack in reverse order (so the first element is on top).

Each object, other than keys in the dictionary, can be either active or inactive, except marks.

Execution proceeds as follows: If the execution stack is empty, then the program terminates successfully; otherwise, remove the top object from the execution stack and decide what to do: If it is an active operator, execute it; otherwise (if it is an inactive operator, or if it is anything other than an operator), move it to the top of the data stack.

The operators, and what they do when they are executed, are:

• 0: Pushes a mark onto the data stack.

• 1: Finds the topmost mark on the data stack; everything starting from the item directly above that mark, up to the top, is compiled into an inactive list, which is then pushed to the data stack; those items, and the mark, are removed from the data stack. If there is no mark in the data stack then it is an error.

• 2: Pop one object from the data stack, and find a matching key in the dictionary; if there is none, then it is an error, otherwise the value that corresponds to that key is pushed to the data stack. (A mark matches another mark, an operator matches the same operator (even if one is active and one is inactive), an empty list matches an empty list (even if one is active and one isn't), and a non-empty list matches only the same list (not others with the same value, but doesn't care if active or inactive).

• 3: Pop two objects from the data stack, first a value and then a key. Associate the key and value in the dictionary. If that key is already associated then it is overridden with the new value.

• 4: Exchange the top two objects of the data stack.

• 5: Activate the top object of the data stack. If it is a mark, or if it is already active, then the object remains there and remains active.

• 6: If the top object of the data stack is active, execute it; otherwise it remains on the top of the data stack.

• 7: Pop one object from the data stack and write it to standard output in some implementation-defined way.

• 8: The initially active version of the 5 operator.

• 9: The initially active version of the 6 operator.

Variant

The "EsoPost II" variant replaces 2 and 3 with other operations:

• 2: Duplicate top object of data stack.

• 3: Discard top object of data stack.

This variant does not require to check if objects match.

The standard variant (described in most of this article) is called "EsoPost" or "EsoPost I".

Examples

This example program repeats making first a empty list, and then a list containing a empty list, and then a list containing a list containing a empty list, etc.

0089189389
1089008028183802878128681898389
12899

Implementation in PostScript

true setpacking
/Commands [256 {null cvx} repeat] def
/Define {exch 0 get exch Commands 3 1 roll put} bind def
/Input (%stdin) (r) file def

(;) {{//Input read {10 eq {exit} if} {quit} ifelse} loop} bind Define
(0) ([) load cvlit Define
(1) (]) load cvlit Define
(2) /load load cvlit Define
(3) /store load cvlit Define
(4) /exch load cvlit Define
(5) /cvx load cvlit Define
(6) /exec load cvlit Define
(7) ( == ) Define
(8) /cvx load Define
(9) /exec load Define

{//Input read {//Commands exch get exec} {quit} ifelse} bind loop

For EsoPost II, change the lines defining 2 and 3 to:

(2) /dup load cvlit Define
(3) /pop load cvlit Define

Similarity to 7

There is some similarity to 7. Some differences include:

• In 7, passive commands push the corresponding active command to the stack; in EsoPost, they remain passive when pushed to the stack, and a separate command makes them active.
• In EsoPost you can have a list encapsulated as an object itself; in 7 the only objects are the commands and bars.
• In EsoPost most commands do not manipulate an entire section at once; only the active version of 1 does this, and converts it into a single object which can then be manipulated at once with the other commands.
• In EsoPost the program does not "cycle".

Computation class

There is the correspondence of some Underload commands with EsoPost II:

(   089
)   1898
:   28
!   38
~   48
^   68
a   08481858
*
S

Also write "089" at the beginning of the program and "18989" at the end of the program.

That should be of sufficiency to be Turing-complete, since they say only :()^ is needed.