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.