\documentstyle[epsf]{article}

\title{{\sc Grip}---Michael's sections}
\author{Mark C.~Torrance\\
Michael P.~Frank\\
Department of Computer Science\\
Massachusetts Institute of Technology\\
Cambridge, Massachusetts  02139}
\date{\today}

\begin{document}

\maketitle

\begin{abstract}
  We describe {\sc Grip}.
\end{abstract}

\section{Introduction}

{\sc Grip} stands for Grid Processing, in analogy with LISP. {\sc Grip} is a
graphical programming language based on 2-dimensional Turing machines,
as discussed in \cite{Dewdney89}.  I like {\sc Grip}.

Imagine a large grid of square cells.  In analogy with the standard
Turing machine, one can imagine a 2-dimensional form of Turing
machine, which was actually the kind that Turing thought of first.
Instead of examing one cell on a tape, the head of the 2-D Turing
machine examines one cell on a grid.

We call a 2-D Turing machine tape head a ``husk'' in reference to its
appearance on our display as a square outline around a grid cell.  The
name ``husk'' also refers to the fact that the tape head iself is only
the the physical enbodiment, the outer shell, of the complicated and
hidden Turing machine that may be controlling its behavior.

What if this Turing machine were not hidden?  What if the invisible
state-transition table for the machine was replaced by some sort of
program physically present within the grid?  In fact, what if the
interpretation of this program to control the Turing machine was
performed by yet another Turing machine scanning the program?  That
would be interesting.  The behavior of that interpreter Turing machine
could be controlled, in turn, by the actions of yet another Turing
machine that interprets a controlling program.  On a real computer, of
course, there must be some level at which the Turing machines are
controlled by a program that is not present on the grid.  That is the
role of our {\sc Grip} interpreter; it embodies the state-transition
table for a Turing machine whose function is to interpret programs on
the grid written in the {\sc Grip} language, which specify the
behavior of other Turing machines on the grid.

Of course, normal Turing machines are not capable of directly
controlling others, so we augment our machines' capabilities to
include the creation of a ``child'' Turing machine, and a facility for
controlling the child; for everything that a Turing machine can do, it
can also cause its child to do that thing.  This includes causing its
child to create a child of its own, and control it in a certain way.
Thus, for each Turing machine, there is really an infinite chain of
descendant machines that it can create and control.  In the {\em Grip}
language, a top-level Turing machine can be told to make its
descendants do something using a {\sc Grip} command of the form,
``Tell your child to tell its child to ... tell its child to do {\em
this}.'' 

Our {sc Grip} programming system supports simultaneous execution
of multiple top-level turing machines, or ``roots'' as we call them;
thus one can write concurrent programs that cooperate or compete or
attempt to destroy each other in a fashion reminiscent of ``Core
Wars.''

\section{Inspirations/History}

\section{Motivating Principles}

\section{Language Features}

Every command in the {\sc Grip} language occupies a single grid cell,
although the command may have immediate data values located in
adjacent cells.  The simplest commands are the flow-control
instructions.  These control the direction of motion of the root husk
while it is executing the {\sc Grip} program.  Figure~1 gives some
examples.

\begin{figure}
  \vspace{0.5in}
  \begin{center}
    \leavevmode
    \epsfxsize 4in
    \epsfbox{examples.ps} 
  \end{center}
  \caption{Some examples of {\sc Grip} commands.}
\end{figure}

In the examples above, the light squares represent the husks that are
moving over the grid.  In example 1, there are only directional
flow-control instructions.  The root husk will continue around the
loop indefinitely.

The second example illustrates the fundamental ``\{`` (BEGIN)
command that tells the root husk to send a command to its child.  If
the child does not exist, it is created in the same position as its
parent, namely, on the BEGIN instruction.  The command sent is ``L''
(turn left), so the child rotates left from its current orientation
(east) and the moves forward, or north.  The ``\}'', or END, is needed
to stop controlling the child; this allows commands to the child to be
strung together, as demonstrated in example 3.

Also in example 3 is an illustration of the ``write'' instruction,
which takes a single argument.

Here is an example of a table.

\begin{table}
  \begin{tabular}{||l||}
    \hline \hline
    {\bf Husk Control Primitives} \\ \hline
    \hline
    Go forward 1 square \\ \hline
    Turn left and go 1 square \\ \hline
    Turn right and go 1 square \\ \hline
    Turn around and go 1 square \\ \hline
    Read symbol in current square \\ \hline
    Write a symbol to current square \\ \hline
    Create a child husk at current location \\ \hline
    Apply a control primitive to the child husk \\ \hline
    Destroy the child husk \\ \hline
    \hline
  \end{tabular}
  \caption{Husk Control Primitives.}
\end{table}

\begin{table}
  \begin{tabular}{||l|l|l|l||} \hline \hline
                & Command Format  &                                    & Depends \\
    Command     & (for Eastward-  &                                    & on      \\
    Name        & moving root)    & Description                        & child?  \\ \hline
    \hline
    \multicolumn{4}{c}{Root husk (program counter) direction control}      \\ \hline
    east        & {\tt >}         & Go east                            &   \\ \hline
    south       & {\tt V}         & Go south                           &   \\ \hline
    west        & {\tt <}         & Go west                            &   \\ \hline
    north       & \verb|^|        & Go north                           &   \\ \hline
    port        & {\tt P}         & Turn left and go                   &   \\ \hline
    starboard   & {\tt S}         & Turn right and go                  &   \\ \hline
    slash       & {\tt /}         & Bounce E<->S, W<->N                &   \\ \hline
    backslash   & \verb|\|        & Bounce E<->N, W<->S                &   \\ \hline
    bounce      & {\tt \#}        & Bounce back                        &   \\ \hline
    \multicolumn{4}{c}{Interface to husk control primitives}               \\ \hline
    go          & {\tt G}         & Go forward                         & Y \\ \hline
    left        & {\tt L}         & Turn left and go                   & Y \\ \hline
    right       & {\tt R}         & Turn right and go                  & Y \\ \hline
    around      & {\tt A}         & Turn around and go                 & Y \\ \hline
    read        & {\tt r} $s$     & Replace $s$ with symbol being read & Y \\ \hline
    write       & {\tt w} $s$     & Write $s$                          & Y \\ \hline
    begin       & {\tt \{}        & Start controlling child, create if needed & Y \\ \hline
    end         & {\tt \}}        & Stop controlling child             & Y \\ \hline
    destroy     & {\tt )}         & Stop controlling child and destroy it & Y \\ \hline
    \multicolumn{4}{c}{Branching}                                          \\
    if          & {\tt ?} $s$ $x$ & Do $x$ only if reading $s$         & Y \\ \hline
    if-not      & {\tt N} $s$ $x$ & Do $x$ only if not reading $s$     & Y \\ \hline
    random      & \verb|~| $x$    & Do $x$ with probability $0.5$      &   \\ \hline
    case        & {\tt C} $v_1$ $x_1$ \ldots $v_n$ $x_n$ $\Box$ {\tt C} & If reading $v_i$, do $x_i$ & Y \\ \hline
    \multicolumn{4}{c}{Miscellaneous}                                      \\
    define      & {\tt D} $s$     & Define function for symbol $x$     &   \\ \hline
    end-define  & {\tt E}         & Return from function               &   \\ \hline
    cross       & {\tt X}         & No-op (allows paths to cross)      &   \\ \hline
    skip        & {\tt \$} $x$    & Do not do $x$ (skip over $x$)      &   \\ \hline
    fork        & {\tt Y} $x$     & Create new root starting at $x$    &   \\ \hline
    suicide     & {\tt @}         & Destroy root                       &   \\ \hline
  \end{tabular}
  \caption{Commands of the {\sc Grip} language.}
\end{table}

\section{Ease of Debugging}

\section{Implementation}

\bibliography{grip}
\bibliographystyle{plain}

\end{document}


