Portable Minsky Machine Notation

Portable Minsky Machine Notation (PMMN) is a syntax for Minsky machines that was created by User:ais523 in 2015. Like Bitwise Cyclic Tag, it is equivalent (when seen as an esoteric programming language) to a mathematical formalization that has existed for a long time, but has the advantage that it has a concrete syntax, and thus it is possible to write compilers to and from it and interpreters for it.

Definition

Portable Minsky Machine Notation expresses Minsky machines. As such, the program's commands all refer to one of a (fixed) number of internal counters. In Portable Minsky Machine Notation, these are named using integers written in decimal: 0, 1, etc.. The counters have a minimum value, but no maximum value; they can store arbitrarily large integers. (The actual identity of the minimum value makes no difference to the language; 0 is the most common choice, although in some cases 1 will be easier to implement.) At the start of the program, each counter is at its minimum value. Note that although the counters themselves must be able to store unbounded integers, the input program may not directly mention an integer with value greater than 2 billion (thus indirectly placing a limit on the maximum number of counters that can be used); this restriction is to make it easier to construct a Portable Minsky Machine Notation parser, via removing the need for the parser to handle bignum arithmetic.

There are two commands that access memory. inc(counter) adds 1 to the value of a counter. dec(counter) subtracts 1 from the value of a counter, unless it is already at its minimum value. dec (but not inc) can also be used as the test of a control flow command, in order to read memory in addition to writing it; when used as a test, dec has its usual effect, but in addition, returns true if the decrement changed the counter's value, or false if the counter was at its minimum value already. These two commands are followed by a semicolon when used as part of a block or program.

There are also control flow commands: if and while. These are followed by a test (i.e. a dec command) in parentheses, followed by a block of code (which is just a sequence of commands enclosed by braces, { and }). An if command can additionally be followed by else and another block of code. These have the meanings that C, Java and Perl programmers would expect: if runs its first block if the test succeeds (and its second block, if it exists and if the test fails); while runs its block if the test succeeds, then when the block completes, jumps back to just before the while statement (thus causing the test to run again, and if it succeeds, causing the block to run again and another jump back, potentially infinitely many times).

Programs can also contain comments. These start with /*, end with a matching */, and cannot be nested. Whitespace is insignificant, except that it cannot appear inside a counter number, keyword, or comment marker.

Here's the complete grammar in a BNF-like format (with a program being a commandlist):

digit       ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
counter     ::= digit | counter digit
test        ::= "dec" '(' counter ')'
command     ::= "inc" '(' counter ')' ';'
             |  test ';'
             |  "if" '(' test ')' block
             |  "if" '(' test ')' block "else" block
             |  "while" '(' test ')' block
block       ::= '{' commandlist '}'
commandlist ::= command
             |  commandlist command

Extensions

These aren't part of the language itself, but are commonly provided by interpreters, and can be thought of as implementing a "larger" language along similar lines.

RLE extension

In order to avoid the need for long repetitive strings of inc command to encode increments by large numbers, an inc_by command is provided as syntactic sugar. The syntax is inc_by(counter, amount), where counter is a counter number and amount is a nonnegative integer expressed in decimal; this is exactly equivalent to a sequence of amount inc(counter) instructions. (Other repetitive sequences can be compressed via using inc_by to increment a temporary counter, and a while loop decrementing that counter in order to run them repeatedly.)

I/O extension

An extra two commands are provided that aren't part of the mathematical definition of a Minsky machine, but allow programs to do input and output. This is useful for testing, or when compiling programs from one language into another.

The input(counter) command reads one octet from standard input. If the read fails (either because of an error, or because standard input is at end-of-file), it does nothing. Otherwise, it adds 1 plus the numerical value of that octet (i.e. from 1+0 to 1+255) to the value of that counter. It cannot be used as a test.

The output(counter) command sets the value of the given counter to its minimum value. If it was already at its minimum value, nothing happens. Otherwise, 1 is subtracted from the difference between the counter's previous value and its minimum value, and the resulting number is interpreted as an octet and output to standard output. Programs should avoid trying to output octets with values outside the range 0 to 255, as this makes no sense and interpreters might not deal with the situation consistently.

On systems where newline is represented by something other than the octet with value 10, implementations should provide a command-line option to convert the platform-specific newline code to and from octet 10 on input and output respectively.

Computational class

Because Minsky machines are Turing complete, so is Portable Minsky Machine Notation.

See also

• Minsky machine
• Bitwise Cyclic Tag
• The Amnesiac From Minsk
• Your Minsky May Vary, a derivative of this language