Skip to content
/ flexsym Public

An automata-based, Turing-tarpit programming language for the construction of non-deterministic Turing machines.

License

Notifications You must be signed in to change notification settings

cmaher/flexsym

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

89 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

flexsym

Flexsym is an automata-based, Turing-tarpit programming language for the construction of non-deterministic Turing machines.

Usage

$ bin/flexsym <code-file>

test with

$ rake test

##Description

Just like a Turing machine, the flexsym runtime operates on a set of states, an infinite 1-dimensional tape (with each cell initialized to 0), and a head. Each cell in the tape can hold any Integer (that your implementation of Ruby can support...)

Each state can read the value of the tape at the head and branch based on that value. Additionally, a state can give a set of actions to perform, including increasing/decreasing the value of the tape at the cell pointed to by the head, moving the head left/right, outputing the value of the cell at the head, or transition to another state. A state halts the machine if it doesn't transition anywhere.

If one state has multiple sets of actions for the same value, then machine branches nondeterminstically, once for each extra set of actions. Each extra machine gets a copy of the tape with the same head position. The runtime runs machines in 'steps', where each machine executes the actions of one state before any transitions are made. If one machine halts, the program halts.

States are declared by wrapping a string in ';' characters, and then declaring the default block of commands for that state.

    ;state; _ _ _ _

They can optionally be followed by a number of branches, each starting with a hex number, followed by a block ofcommands

    ;state; _ _ _ _ 
    4f      _ _ _ _

At runtime, the state will read the value of the tape at the head. If the value matches the value at the start of one or more branches, those branches will be executed. Otherwise, the default block will be executed.

There are eight types of commands that can be executed in a block

command effect
+ Increases the current tape cell value by 1
- Decreases the current tape cell value by 1
^ Output the ASCII character with the value of the tape cell at the head
. Output the numeric value of the tape cell pointed to by the head
< Move the tape head left
> Move the tape head right
_ Void -- doesn't do anything, takes up one command entry
;<label>; Transition to the state with the given label

No matter what order the commands are written in a block, they are executed in the following order:

  1. +/-
  2. ^/.
  3. >/<
  4. ;label;

Again, _ are not executed, they just take the place of a command

Many commands of the same type or execution level can be given in a single block, but only the last one will actually be executed.

See examples/hello.flexsym for "Hello, World!"

See examples/nd4.flexsym for nondeterministic branching

Basic Grammar:

    <program>       ::= <label> <state-list>
    <label>         ::= ";" [^;]* ";"
    <state-list>    ::= <state> | <state-list> <state>
    <state>         ::= <label> <block> <branch-list>
    <block>         ::= <cmd> <cmd> <cmd> <cmd>
    <cmd>           ::= <op> | <label>
    <op>            ::= "+" | "-" | ">" | "<" | "." | "^" | "_"
    <branch-list>   ::= <branch> | <branch-list> <branch> | ""
    <branch>        ::= <number> <block>
    <number>        ::= <hexnum> | "-" <hexnum>
    <hexnum>        ::= [0-9a-fA-F]+

Additionally, non-op, non-';', are allowed anywhere. Note that in most places, a-f will be interpreted as numbers, so be careful. A good place for comments is inbetween a state's label and its default block

This is an entry for the December 2012 competition at www.pltgames.com

License: MIT

About

An automata-based, Turing-tarpit programming language for the construction of non-deterministic Turing machines.

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages