Skim machine
Skim machine is a language invented by User:A that is a trivial substitution of the Minsky machine.
Syntax
Skim machine programs are divided into lines of operations, with each non-empty line entailing a single instruction. Such an operative unit starts with the command name, followed by an accumulator identifier, and optionally concludes utilizing a comma-separated target line number.
Accumulator identifiers comprehend at least one character, being compositions of alphanumeric constituents or the underscore (_).
The following furnishes an Extended Backus-Naur Form (EBNF) description of the language:
program := [ linebreaks ]
, [ programLine ]
, { linebreaks , programLine }
, [ linebreaks ]
;
programLine := emptyLine | commandLine ;
commandLine := optionalSpaces
, ( incInstruction | jzdecInstruction )
, optionalSpaces
;
emptyLine := optionalSpaces ;
incInstruction := "INC" , mandatorySpaces , accumulatorName ;
jzdecInstruction := "JZDEC"
, mandatorySpaces
, accumulatorName
, argumentSeparator
, integer
;
accumulatorName := nameCharacter , { nameCharacter } ;
nameCharacter := letter | digit | "_" ;
letter := "a" | ... | "z" | "A" | ... | "Z" ;
integer := [ "+" | "-" ] , digit , { digit } ;
digit := "0" | "1" | "2" | "3" | "4"
| "5" | "6" | "7" | "8" | "9"
;
linebreaks := linebreak , { linebreak } ;
linebreak := "\n" ;
argumentSeparator := optionalSpaces , "," , optionalSpaces ;
optionalSpaces := { space } ;
mandatorySpaces := space , { space } ;
space := " " | "\t" ;
Commands
Only two types of operations are employed in the language: INC, which increments an accumulator, and JZDEC, combining in it the potential for decrementing an accumulator or jumping to another line based on its value.
An aperçu shall educate about the available instructions:
| Command | Description |
|---|---|
INC a
|
Increment the accumulator a by one and proceed to the next instruction.
|
JZDEC a, b
|
If the value of the accumulator a equals zero, jump to the line indexed with the zero-based number b. Otherwise decrement a by one.
|
Computational class
It is Turing-complete with at least 3 accumulators, as a 3-accumulator Skim machine can compile to the Minsky machine. (However, a minimization of the number of accumulators is encouraged.)
- INC a, b
INC a JZDEC c, b
- JZDEC a, b, d
JZDEC a, b JZDEC c, d
Examples
Adder
The following program adds the two numbers 2 and 4 and stores the sum in the augend accumulator:
INC augend INC augend INC addend INC addend INC addend INC addend JZDEC skip, 8 INC augend JZDEC addend, 10 JZDEC return, 7
Interpreter
- Common Lisp implementation of the Skim machine programming language.