Alchemist

Alchemist

Paradigm(s)	non-deterministic
Designed by	BMO
Appeared in	2018
Computational class	Turing complete
Major implementations	alchemist, Alchemist.py
File extension(s)	.crn

Syntax

Alchemist is a non-deterministic programming language based on chemical reaction networks. A program is a (multi-)set of rules of the form LHS -> RHS, where the LHS consists of simple atoms separated by + and the RHS consists of atoms separated by +. The atoms on the right hand-side can be any atoms, but there are two additional special types for Input/Output:

Atom	Description
In_{atom_name}	Reads an integer from stdin and adds that many atoms of type {atom_name}
Out_{atom_name}	Prints the number of {atom_name} atoms to stdout
Out_"{string}"	Prints the {string} to stdout

The simple atoms can contain any characters [0-9A-Za-z_], but they must start with a non-digit. The program will consist of any number of rules separated by newlines, the syntax of a rule is as follows:

  Rule = LHS? '->' RHS?

  LHS  = Number? SimpleAtom ('+' Number? SimpleAtom)*
  RHS  = Number? Atom ('+' Number? Atom)*

  Atom = SimpleAtom | 'In_' SimpleAtom | 'Out_"' StringLiteral '"' | 'Out_' SimpleAtom

  SimpleAtom = [A-Za-z_] [0-9A-Za-z_]*

  Number = [0-9]+

The exact grammar of StringLiteral may depend on the implementation, it is however expected that Hello, World! is legal. A program may optionally contain constant inputs, so a full program has the form:

  Program = Rules? ('!' Inputs)?

  Rules  = Rule ('\n' Rule)*

  Inputs = LHS

Semantics

An alchemist program contains of the rules and a universe containing simple atoms. Initially the number of atoms of each type is determined by the user inputs and the constant inputs that might be provided in the source code. The program will continually pick rules at random from the set of applicable rules, until there are no such rules.

A rule is called applicable if there are enough atoms in the universe of all the atoms on the left hand-side of that rule. When such a rule is applied, all the atoms mentioned on the left hand-side are removed and the simple ones on the right hand-side will be added. If there are In_ or Out_ atoms, these will be processed from left to right.

0-Rules

There is a special type of rules, if the coefficient of an atom is 0 then this rule will only be applicable if there are exactly zero atoms of that type.

Implicit _-Atom

The universe will (if not overridden by -o) always start off with one atom _.

Examples

If we have the rule 2H + O -> H2O and the universe consists of 3 H and 2 O atoms, then the rule is applicable. After applying the rule our universe will contain 1 H2O, 1 H and 1 O atoms. At this point the rule would not be applicable anymore.

If we have the rule Alice + Bob + 0Eve -> AliceBob and the universe contains 1 atom of each Alice, Bob and Eve. Then that rule is not applicable because it requires the universe to contain no atom of type Eve.

Evaluation order

The original implementation allows multiple Out_ and In_ rules, the evaluation of these happens as follows:

1. the atoms of the left hand-side are removed from the universe
2. each atom on the right hand-side is evaluated from left to right

A simple example shall illustrate this:

_ -> go + 2x
go + x -> Out_x + In_x + Out_x + x + Out_x

After matching the first rule there will be one go-atom and two x-atom, then the next rule will be applied:

1. the atoms on the left hand-side are removed, leaving: 0 go-atom and one x-atom
2. the first Out_x is evaluated, printing 1
3. In_x is evaluated (suppose the user inputs 28), leaving us with 29 x-atoms
4. Out_x is evaluated, printing 29
5. an x-atom is added, leaving 30 x-atoms
6. the final Out_x is evaluated, printing 30

So the above program will output 12930

Example Programs

Hello, World!

The following code will output Hello, World! to stdout:

x->Out_"Hello, World!"!x

Using the implicit _-atom, we can rewrite the above program as:

_->Out_"Hello, World!"

Truth-Machine

The following is a truth-machine:

x->z+In_y
0y+z->Out_"0"
y+z->y+z+Out_"1"!x

Josephus Problem

The following program illustrates how more complicated control-flow with 0-rules can be achieved. It reads two integers, n (number of soldiers) and k (number of people to skip) from stdin and outputs the survivor:

_ -> readk + In_n
readk -> init0 + In_k
init0 + k -> r + t + init0
init0 + 0k -> init1
init1 + t -> k + init1
init1 + 0t + r + n -> i + loop0
loop0 + 0n -> Out_r
loop0 + n -> i + loop1
loop1 + k -> r + t + loop1
loop1 + 0k -> loop2
loop2 + t -> k + loop2
loop2 + 0t -> loop3
loop3 + 0i -> loop4
loop3 + i -> loop5
loop4 + t -> i + loop4
loop4 + 0t -> loop3
loop5 + r -> t + loop3
loop5 + 0r -> loop6
loop6 + t -> i + r + loop6
loop6 + 0t -> i + loop0