A Progression of Languages Alternative Quantifications of Computation Expressed Using the "Exhaust" Algorithm

The Exhaust Algorithm

The "exhaust" algorithm takes three arguments:

The purpose of the exhaust algorithm is to shift elements, one by one, off of the cell's work stack, transforming each into some action defined by the jtof function and ceasing execution once the work array is exhausted. The metaphor of the work stack is something akin to a "todo" list, in that it contains ordered, symbollic representations of "what needs to be done". This metaphor is ergonomic to a very simple notion of algorithm expression (i.e. "do this" then "do that").

The actions performed by the exhaust algorithm are:

  1. validate arguments
  2. construct a context to thread state and execution through our JSON encoding
  3. kick off an execution chain by invoking next

The actions performed by the next subroutine are:

  1. trace mutable state
  2. if work is exhausted, terminate execution
  3. otherwise, have jtof convert the left-most work item into an action

JavaScript Implementation of exhaust

The TALLY Language

The TALLY Language is written as a JSON array of integers. The result of evaluating an algorithm encoded in TALLY is the sum of the integers in the TALLY encoding. For example, if TALLY were used to evaluate the array: [1,2,3], the result would be 6.

The TALLY language is simple to the point of triviality, as its entire functionality could be replaced with a basic for loop or reducing function. This simplicity is intended to highlight some of the key points of using the 'exhaust' algorithm, without the distractions of a more sophisticated language. The key points in question are:

Try typing some different integers into the array below, and observe the output of the TALLY evaluator.

The ASM Language

The ASM (Addition, Subtraction, Multiplication) Language introduces operator tokens on top of the basic TALLY mechanism. Specifically, if the token "+" is encountered at the left edge of the work stack, the top two elements of the data stack are popped, and their sum is pushed. Similary, "-" and "*" perform subtraction and multiplication against the data stack.

ASM is implemented here:

You can experiment with the programming of ASM here:

The ASMD Language

The ASMD Language adds a division operator onto the previously defined ASM language. In order to avoid introducing floating point numbers into our otherwise integer-centric process, ASMD will perform operations on rational numbers (represented here as integer pairs).

For the sake of simplicity, all operations in ASMD will be converted to expect the presence of rational numbers on the data stack. Correspondingly, an integer pair on the left edge of the work stack is pushed onto data "as is" while an integer at the left of work is converted to a ratio before being stored as data.

Program the ASMD machine using integers, operators, and ratios, for example:

Note that the result is always given in the form of a ratio.

The OBJ Language

If we change our algorithm encoding from an Array to an Object, we can begin adding abstraction and mutability to our model of computation. The OBJECT language supports an operator for referencing predefined sequences of code, and while rudimentary, this already hints at the power of an Object based notation.

The Ref Operator

The "ref" operator allows us to fetch named arrays of code defined in our cell and precat them to the cell's work stack. This functionality gives us the ability to begin to modularize our algorithm notation, storing reusable sections of code in named locations. For example, rather than include 1,"+",2,"*" in our code in multiple places, we could give that series of commands a name, and use the ref operator to put it on the work stack as needed.

The Set Operator

In compliment to ref, the "set" operator takes a key and value from the data stack and associates that value (wrapped in an array) with that key (in the cell). This provides the ability to mutate named state during the course of execution.

The Simplify Operator

Fraction simplification is not performed automatically after each mathematical operation. By invoking "simplify", we can explicitly specify when and where fraction simplification is performed.


It should be noted that cycles are possible (and very easy) to create. If one were to refernce a piece of named state that, in turn, referenced itself (either directly or indirectly), an infinite loop would be created.


SNOBAN is a refinement of the "object as program" concept. The language includes operators for Strings, Numbers, Objects, Booleans, Arrays, and Null. SNOBAN also assumes the presence of an "implementation", that can be messaged with the "IMP" operator. The implementation provides a means for SNOBAN programs to exchange data with the environment in which they run.

The "." Operator

A string containing a single period character is used to invoke operations. For example, "+","." instructs SNOBAN to invoke the numeric summing operation, while "imp","." causes the implementation operation to run.


SNOBAN programs can define a "macro" field. This field contains an object in which keys represent "macro prefixes", and values represent sequences of code to be run on the macro prefixed value. The macro algorithm does the following:

The following macro definition makes use of the "." operator a bit more ergonomic:

This macro allows the following two segments of code to have equivalent effect:

The following macro provides similar functionality for setting and getting local variables:

The "IMP" Operator

Programs can invoke the "IMP" operator on an integer representing how many elements should be piped from the data stack to the implementation and a string representing an operation that the implementation should perform. The implementation operation may push some number of elements onto the data stack upon its completion.

The SNOBAN Function

When invoked on a program, the SNOBAN evaluator returns a function intended to be applied to an implementation object and passed an ouput function as its sole argument.