/*
 * The Braktif Cellular Automaton
 * June 2005, Chris Pressey
 * BSD License added May 3 2007
 */

/*
 * Copyright (c)2007 Chris Pressey, Cat's Eye Technologies.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 *   1. Redistributions of source code must retain the above copyright
 *      notices, this list of conditions and the following disclaimer.
 *   2. Redistributions in binary form must reproduce the above copyright
 *      notices, this list of conditions, and the following disclaimer in
 *      the documentation and/or other materials provided with the
 *      distribution.
 *   3. Neither the names of the copyright holders nor the names of their
 *      contributors may be used to endorse or promote products derived
 *      from this software without specific prior written permission. 
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */
 
/*
 * Braktif is an esoteric programming language very similar to
 * 'Brainfuck F' and 'Archway', with a small but significant
 * difference: Braktif is formulated as a 28-state cellular automaton.
 *
 * Braktif playfields are divided into a program on the right and
 * a data storage area on the left.  (The data storage area can be
 * considered to extend indefinately to the left.)  The program
 * and data area are connected by a 'bus'.  On the bus sit the
 * instruction pointer, which rests underneath the part of the
 * program which is currently executing, and the data pointer, which
 * rests underneath the part of the storage which is currently being
 * addressed.  The instruction pointer and data pointer communicate
 * by means of signals (from the IP to the DP) and replies (from the
 * DP to the IP) sent along the bus.
 *
 * The instructions of a Braktif program resemble those of Smallfuck
 * or Brainfuck F:
 *
 *   *   flip current data bit
 *   >   advance DP one cell to the right
 *   <   advance DP one cell to the left
 *   [   if current data bit == 0, skip to matching ]
 *   ]   skip back to matching [
 *
 * The structure of Braktif programs resembles that of Archway.  Each
 * nested loop must be raised up one level.  In addition, extra space
 * must be left after [ instructions, and at least one non-[]
 * instruction must occur after a ] instruction, so that signals have
 * sufficient space in which to propagate.
 *
 * The data storage area of a Braktif playfield resembles the tape of
 * a Brainfuck F program (or a Smallfuck program, if an arbitrary limit
 * is imposed on it) except that it is bounded on the *right*, not the
 * left.
 *
 * The final result of all this is that the following Brainfuck F
 * program translates to the following Braktif program (the '...'
 * indicates the quiescent repeating pattern extending off to infinity):
 *
 * Brainfuck F:           +[>+]
 *
 * Braktif:
 *                           <*
 *     ... 00000000000000 *[---]
 *     ... -------------d-i-   --
 *
 * So... why Braktif?
 *
 * - eliminates 'spooky action at a distance' from the Brainfuck model:
 *   the communication between the code and the tape is made explicit
 *   (and explicitly planar, FWIW WRT the wire-crossing problem.)
 * - horribly inefficient because of this.  Flipping the n'th data cell
 *   from the m'th instruction of the program is now an O(n+m) operation.
 *   What fun!
 * - makes a passable "poor man's visual debugger" for Brainfuck F.
 * - makes experimenting with concurrent models easily.  For example it
 *   might be feasible to add a few states what would act as a simple
 *   mutex so that two different programs could share one data store.
 *
 * Finally, I do not claim that this is the most efficient formulation
 * imaginable... there is certainly room for optimization.  For
 * example, half of the 'Tool' states could probably be done away with
 * entirely if the signals were to transition themselves directly into
 * responses.  But a minimum of states is not the real goal (otherwise
 * one could just settle for John Conway's Game of Life and be done
 * with it,) and the 'Tool' states lend a certain straightforwardness.
 */

/* -------------------- Transmission Media --------------------- */

state Space	" "
    to SkipBack when (^ WakeMark and ^> WendCmd) or (> SkipBack),
    to SkipStart when ^< SkipReply and ^ InstrMark,
    to SkipFore when v< SkipStart or < SkipFore;

state Bus	"-"
    to > when > is Signal,
    to ^> when ^> is Signal,
    to v> when v> is Signal,
    to < when < is Reply,
    to ^< when ^< is Reply,
    to v< when v< is Reply,
    to ContTool when > LeftTool or < RightTool,
    to ContReply when < ContTool,
    to SkipReply when < SkipTool,
    to LeftSig when > InstrPtr and ^> LeftCmd,
    to RightSig when > InstrPtr and ^> RightCmd,
    to FlipSig when > InstrPtr and ^> FlipCmd,
    to QuerySig when > InstrPtr and ^> WhileCmd,
    to InstrPtr when < WakeMark or v< WakeMark or ^< Wakemark,
    to InstrPtr when < InstrPtr and ^< Space,
    to InstrPtr when > SkipBack,
    to SkipStop when < SkipFore,
    to InstrPtr when < SkipStop;

/* -------------------- Signals and Replies -------------------- */

class Signal
    to Bus;

class Reply
    to Bus;

state LeftSig	"L" is Signal;
state RightSig	"R" is Signal;
state FlipSig	"F" is Signal;
state QuerySig	"Q" is Signal;

state ContReply	"C" is Reply;
state SkipReply	"S" is Reply;

/* ------------------- Data Store: Data Pointer ---------------- */

state DataPtr	"d"
    to FlipTool when > FlipSig,
    to LeftTool when > LeftSig,
    to RightTool when > RightSig,
    to SkipTool when > QuerySig and ^ OffBit,
    to ContTool when > QuerySig and ^ OnBit;

state FlipTool	"f"
    to ContTool;
state LeftTool	"l"
    to Bus;
state RightTool	"r"
    to Bus;
state ContTool  "c"
    to DataPtr;
state SkipTool	"s"
    to DataPtr;

/* ----------------- Data Store: Tape Contents ----------------- */

state OnBit	"1"
    to OffBit when v FlipTool;
state OffBit	"0"
    to OnBit when v FlipTool;

/* ----------------- Program: Instruction Pointer -------------- */

state InstrPtr	"i"
    to Bus when ^ Space,
    to InstrMark;

state InstrMark	"I"
    to WakeMark when < ContReply,
    to Bus when < SkipReply;

state WakeMark	"W"
    to Bus;

/* ----------------- Program: Instruction Skipper -------------- */

state SkipStart	"!"
    to Space;
state SkipStop	"%"
    to Bus;
state SkipFore	"}"
    to Space;
state SkipBack	"{"
    to Space;

/* -------------------- Program: Instructions ------------------- */

state FlipCmd	"*";
state LeftCmd	"<";
state RightCmd	">";
state WhileCmd	"[";
state WendCmd	"]".