computing : games & art : research

S Language Interpreter

Input Area

Code Area

Output Area

Output will be printed here...


About this Interpreter

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.

xHow to Use this Interpreter

Comments in this interpreter must be preceded by the hash symbol ('#'). For example:

# This is a comment!

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 Y.

Input variables may be called X, X1, X2, X3, etc. In this interpreter, input variables are initialized in the Input Area, separated by commas. The syntax for initialization is variable-name: value. For example:

X: 1, X2: 45, X3: 992, X4: 56

Temporary (or local) variables may be called Z, Z1, Z2, 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 A, M1, 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] X <- X + 1

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.

Syntax: V <- V + 1
Does: increases by 1 the value of the variable V.

Syntax: V <- V - 1
Does: if the value of V is 0, leaves it unchanged; otherwise decreases it by 1.

Conditional Jump:
Syntax: 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 E and V is nonzero, the program halts, as E is the exit label.

Special Thanks

I would like to thank Mariana Milicich and Ignacio Losiggio for finding and helping me fix bugs in this code.

Lartu © 2015 - 2021 — Released under the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License.