Kolmogorov

From Esolang
Jump to navigation Jump to search

Kolmogorov is an esoteric language based on the Kolmogorov machine.

Data Structure

As every school child knows, a Kolmogorov machine differs from a Turing machine in that the Kolmogorov machine uses a graph rather than a tape. To express this graph, the Kolmogorov language uses nodes and edges which have each a value of one byte. The byte value of each edge can be thought of as the "address" of neighbouring nodes.

Syntax

The Kolmogorov language has three different constructs: statements, expressions and loops. Commands, with the exception of the byte literal and loops, are composed of a single letter followed by zero or more arguments. The language is case-sensitive, but permissive in regard of whitespaces, which encompasses spaces, tabs, as well as linebreaks. The homologation of these separators is as liberal as their omission, meaning that constructs are not obliged to be set apart by aid of these characters. In the same manner as with the visual divisions, comments may be interspersed according to one's own will. Whitespaces and comments may not, however, intrude basic tokens, for instance, a byte value \147 may not be divided by a space into \1 47.

Expressions

Byte: \n where n is a number between 0 and 255

Examples: 

\46  "the word with value 46"
\98  "the word with value 98"
\255 "the word with value 255"


Peek: p

Peek receives another expression as input. It returns the value of the node at the edge with this value.

Examples: 

p\45  "Returns the value of the node at edge 45"
pp\23 "Returns the value of the node at the edge which has the value of the node at the edge with value 23"


Input: i

Input receives an ASCII character from the user, and returns a byte value.


ActiveNode: *

The active node is used as an address. If you use it where the statement expects a byte value, you will get an error.

Examples: 

p* "The value of the current node"
*  "A pointer to the current node"

Statements

Assign: a

The assign statement creates a new node joined to the present node with the value given in the first expression, and with an edge which has the value of the second expression. Examples 

a\45\89 "Assign a node with value 45, which is joined to the current node with an edge of value 89"
ap*\0   "Assign a node with the value stored at the current node, which is joined to the current node with an edge value of 0"


Join: j

The join statement creates an edge between two existing nodes. The first expression is the address of the "from node", the second value is the address of the "to node". The third expression, a ByteExpr is the value of the new edge.

Examples: 

j\12\3\9      "Join the node at address 12 to the node at address 3 with a new edge with the value 9"
jp\34\255\255 "Join the node at the address with the value of the node at address 34 to the node at address 255 with an edge with value 255"


Seek: s

The seek statement takes an address, and makes the node at this address the new active node.

Examples: 

s\2 "Seek to the node with address 2"
sp* "Seek to the node with the address of the value of the active node"


Output: o

The output statement takes an address and prints the ASCII character corresponding to the referenced node's byte value.

Examples: 

o\5          "Output the value at the node with address 5"
o*           "Outputs the ASCII character mapping to the value in the active node"
oppppppppp\9 "This is a pretty silly example but shows the 'awesome' power of the Kolmogorov language"


Add: +

The add statement takes an address and a ByteExpr and adds the ByteExpr to the node at this address.

Examples: 

+\1\5 "Add 5 to the node at address 1"
+*\1  "Add one to the active node – BrainFuck programmers will be delighted to note the semantic equivalence of this command and BF's +"


Minus: -

The minus statement takes an Address and ByteExpr and subtracts the byte from the node at the address.

Examples: 

-\1\5 "Subtract 5 from the node at address 1"
-*\1  "Subtract one from the active node – like BF -"


RemoveNode: R

Remove node is a statement which takes a ByteExpr, uses it as an address and removes it from the graph. It does not accept an address, as then it would be possible to R* which is ridiculous.

Examples: 

R\34 "Remove the node at address 34"
Rp*  "Remove the node at the address of the value of the active node"


RemoveEdge: r

Remove edge is a statement which takes a ByteExpr, and removes the corrosponding edge from the graph.

Examples: 

r\23 "Remove the edge which has value of 23"
rp\2 "Remove the edge which has the value held by the node at address 2"

Loops

NodeLoop: [Address Statements]

If the value of the node at the address is greater than 0, then this will loop. Similar to Brainfuck's loop, except it runs until the value of the node at the given address is 0.

Example program: 

"This program prints out the numbers 9 - 1"
+*\9     "Add 9 to the active node"
[*
   +*\48 "Add 48 to the active node"
   o*
   -*\49 "Subtract 49 from the active node"
]


EdgeLoop: {ByteExpr Statements}

If there is an edge which has the value of this ByteExpression, then this will loop.

Example program: 

"This program constructs an array, printing the values as it goes"
a\5\1         "This node counts the number of nodes forming the array"
a\60\0        "This is the start node in the array"
j\0\1\1       "Join the counter node to the first node with an edge with value 1"
s\0           "Seek to the first node in the array"
[\1           "while the counter node > 0"
   o*
   {\0        "while theres an edge with value 0"
      s\0
   }
   ap\1\2     "create another counter node with the value of the first counter node"
      [\2     "if the node with address 1 > 0"
      a\60\0  "create the next node in the array"
      j\0\1\1 "join the new node to the counter node"
      a\0\2   "exit the loop"
      ]
   -\1\1      "subtract one from the counter node"
]

Comments

Comments are any text enclosed within double quotes. As with whitespaces, their occurrence inside of the source code is not encumbered by any restrictions apart from being excluding from within tokens.

Example: 

"This is a program about a whale!"

Example programs

Multiplication

This program will multiply two numbers and display the result, assuming the result is between 0 and 9. 

ai\0      "The first number"
ai\1      "The second number"
a\0\2     "An accumulator for the result"
[\0       "While the first number > 0"
   +\2p\1 "add the second number to the accumulator"
   -\0\1  "take one from the second number"
]
+\2\48    "add 48 to the accumulator, turning it into the appropriate ASCII value"
o\2       "output the result"

Cat program

The following cat program queries the user for an input character and prints this character to the standard output. 

a\1\1   "Create a dummy node at edge address 1 with a non-zero value for infinite repetitions."
[\1     "Ensure an infinite loop by referring to the constant non-zero dummy node at edge 1."
  -*p*  "Set the active node to zero by deducing from it its own value."
  +*i   "Read a character from the user and store its ASCII code in the active node."
  o*    "Output the active node's byte value, which contains the input ASCII character code."
]

Truth-machine

"Create a node with the edge address 1, used for contingent printing of '1'."
a\49\1
"Store the user input into the current node."
+*i
"Print the current node."
o*
"Convert the user input character into its numeric value."
-*\48
"If the user has entered '1', print the value of the node at edge 1, which is '1', infinitely."
[*
  o\1
]

Computational class

There is a reduction from Brainfuck to Kolmogorov.

This assumes that there is a graph of Kolmogorov nodes, each joined to predecessor with an edge value of 1, and each joined to its successor with edge value 0. I make this assumption because it seems trivial (consider the array example given above). 

Brainfuck  "Kolmogorov"
>           s\0
< 	    s\1
+ 	    +*\1
- 	    -*\1
. 	    o*
, 	    [* -*\1] "first zero the value" +*i
[ 	    [*
] 	    ]

See also

External resources

Retrieved from "https://esolangs.org/w/index.php?title=Kolmogorov&oldid=99036"