computing : games & art : research
This is an interpreter written by me for the S Language created by Martin Davis, Ron Sigal & Elaine J. Weyuker (Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science, 2nd edition, Morgan Kaufmann Publishers, ISBN: 0-12-206382-1). It's a simple, imperative language, equally powerful to a Turing Machine but easier to program. This interpreter is open-source and released under the MIT license.
Comments in this interpreter must be preceded by the hash symbol ('
#'). For example:
Variables in S can only store natural numbers (including zero). There are three kinds of variables: input variables, temporary variables (set by default to 0) and only one output variable (also set by default to 0) called
Input variables may be called
X3, etc. In this interpreter, input variables are initialized in the Input Area, separated by commas. The syntax for initialization
variable-name: value. For example:
Temporary (or local) variables may be called
Z3, etc. These variables are set by default to 0 and need no initialization.
Instructions: S only supports three instructions: addition, subtraction and conditional jumps. In this interpreter, instructions are written in the Code Area. Each instruction must be written on a different line.
Labels: Each line of instructions may be preceded by a label. Labels may be named any letter optionally followed by a number, for example
C32, etc., surounded by
[ ]. Labels
are unique and may appear only once in each program. Labels may not be called
E, though, as this is a reserved label. Example:
A program is a finite sequence of instructions. Programs are run from the first line to the last. A program halts when there are no more instructions to execute.
As mentioned in the previous section, S programs only support three instructions, addition, subtraction and conditional jumps. Please note the spaces in the syntax of each instruction and respect them as the interpreter will not work if these are not set correctly. The interpreter is not case sensitive.
V <- V + 1
Does: increases by
1 the value of the variable
V <- V - 1
Does: if the value of
0, leaves it unchanged; otherwise decreases it by
IF V != 0 GOTO A
Does: If the value of
V is nonzero, perform the instruction with label
A next and continue from there; otherwise proceed to the next instruction in the list. If the label is
V is nonzero, the program halts, as
E is the exit label.
I would like to thank Mariana Milicich and Ignacio Losiggio for finding and helping me fix bugs in this code.