
\blankpage

\chapter{A Clocked DNA Programming Language}
\label{ch06}

\section{Existing Programming Languages May Not Work}

In the first 10 years of their existence, automobiles resembled
horsedrawn carriages -- minus the horse hitches. 
\index{horsedrawn carriages}%
This may have comforted early customers who
enjoyed the familiarity of the vehicle, but it made no sense
once the speed capabilities  of the new technology became apparent.

While we have emphasized the familiarity of the clocked
stored program concept in the preceding chapters, 
we do not mean to imply that 
programming languages for electronic computers
should be used to control DNA computers.
Let's first look at what is different about DNA computing.

\begin{itemize}
\item
First, there is the question of scale.
A large parallel electronic computer may have 1,000 processors
or maybe even 10,000, but a clocked
DNA computer can have billions of instruction
\index{clock}%
stacks.
\item
Second, each step in an electronic computer takes under
a billionth of a second
to execute,
whereas the billions of instruction stacks may take 
several minutes to stabilize after each tick and tock is released.
So, even if the total raw computing power (instructions
emitted per unit of time)  of a DNA computer may be comparable
to that of an electronic one, we must make every parallel instruction count.
\item
Third, the instruction stacks simply release instructions into
solution. They keep no local state (there is nothing
analogous to local variables or registers). All changes
occur on the global state and on the stacks themselves.
\index{global state}%
This means that a ``call'' to a gated instruction stack 
using an unlock strand
does not pass parameters.
\item
Fourth, as we discussed in Chapter~\ref{ch04}, it is possible
to pour in a vial of tick strands, but they may not all be consumed.
When tock strands are poured in next, some stacks may release
several instructions while others release none.
So, clocking can be imprecise.

The strategy suggested in Chapter~\ref{ch04} was to 
administer strands in proper stoichiometry and then wait long enough.
Other strategies that may be more precise are possible.
For example, a vial may be administered that contains
more tick strands than instruction stacks and then some
flushing mechanism (such as coated iron balls) may remove excess ticks.
\index{flushing}%
A programmer should be able to specify whether such
a {\em flushing} mechanism is necessary.
\item
Fifth, a stack with a gate will not execute unless it receives
an unlock strand.
It is conceivable, however, that some gated stacks will receive unlocks
at a different time than other ones.
A programmer should be
able to specify whether all stacks sharing the same gate should 
begin at the same
or whether this common start time is unnecessary.
\end{itemize}

\section{ParaGAT: a minimalist language
for a clocked parallel DNA computer}


The language {\em ParaGAT} consists of instructions (which are
\index{ParaGAT}%
strands of DNA), gates (which are other strands),
and synchronization primitives.
The basic synchronization primitive is {\bf flush} which entails
\index{flush}%
ensuring that there are no clock strands (ticks or tocks) in the system.
Flushing is the primitive used to ensure that instructions are executed
one at a time. The notion that instructions must be
executed synchronously occurs so frequently, however,
that {\em ParaGAT} also includes the keywords
{\bf sync} (meaning the $i$th instruction in every stack
\index{sync}%
\index{async}%
should execute before any stack executes
instruction $i+1$)
and {\bf async}. 

The keyword  {\bf async} means that
the programmer allows  different instances of some stack
to execute different instruction numbers concurrently.
Operationally, this means that the system can flood with tick and tock
strands to allow runaway stacks.
(It might be possible to use some version
of the asynchronous Qian stacks \citep{qian}. 
Qian stacks once unlocked (if necessary)
would have a sequence of instructions each released by a complement
of an instruction and a toehold.
The complements would be pre-loaded in the system.
It is an engineering question whether Qian stacks or the hairpin
style stacks proposed here would be a better implementation
of asynchronous stacks.)

The keyword {\bf async} also implies that the stack
construction step is allowed
to construct stacks of different sizes provided the stacks differ
only in how many times a given instruction is repeated.
For example,  for 
a parallel async stack containing the nominal sequence of  
instruction strands X Y X Z could also have stack instances
having the sequence X X Y Y Y X Z Z.
This freedom may permit fast parallel construction methods like those
that caused a smear in the last chapter.

The notation is very simple.
For example, the following describes a block of
ungated synchronous parallel stacks. 
Each payload instruction is just a DNA strand.

\begin{quote}
\begin{verbatim}
begin sync
  payloadInstruction 1 
  payloadInstruction 2 
  payloadInstruction 3 
  payloadInstruction 4 
end sync
\end{verbatim}
\end{quote}


Next, {\em ParaGAT} should have a way to specify a block
of instructions
representing a collection of gated stacks.
\index{stack, gated}%
\index{gate}%
The specification should include
the gate condition required to unlock each stack.
Here the condition will be a strand or strands that together will unlock
the stack.
(It is easy to build a stack that requires the Boolean {\em and} of 
a set of strands to open. Each corresponding lock is just another gate.) 

A block of asynchronous stacks that will be unlocked
\index{asynchronous}%
if the strand $g$ appears will take the form:

\begin{quote}
\begin{verbatim}
gate g
begin async
  payloadInstruction 1 
  payloadInstruction 2 
  payloadInstruction 3 
  payloadInstruction 4 
end async
\end{verbatim}
\end{quote}

As we will see below, it is sometimes
necessary to ensure that all instances of the 
gated stacks begin executing at the same time (even when the gated
stacks themselves will execute themselves asynchronously).
One way to ensure that is to pour in part of the gate  as needed.
Admittedly, this means that, in addition to tick
and tock,  other strands
may be poured into the DNA solution. 
As long as this is done sparingly, it could be very useful.
We call this primitive {\bf external}; it takes a strand
\index{external}%
as an argument.

When the programmer wants all stacks
having this gate to begin executing
at the same time,
we make the gate external and introduce it only
after we can be sure the previous stacks have completed.

\begin{quote}
\begin{verbatim}
external gate g
begin async
  payloadInstruction 1 
  payloadInstruction 2 
  payloadInstruction 3 
  payloadInstruction 4 
end async
\end{verbatim}
\end{quote}


A program is written as a hopefully small
collection of gated and ungated blocks.
This ``dataflow'' style of programming, in which
\index{dataflow}%
strands are released when their pre-conditioning gates
are satisfied, models the DNA in solution
nicely.

\subsection{Conceptualizing Computations in  ParaGAT}

One way to view synchronous instruction stacks in {\em ParaGAT} is 
as a sequence of instructions having a strict linear dependency.
Conversely, asynchronous instruction stacks have no inter-dependencies.
Therefore, a more convenient way to model  the computation 
is as a graph where each vertex is an instruction (a single DNA strand
ultimately), a possibly non-empty gate (one or more single DNA strands),
and possible dependencies.
Edges denote dependencies. So $x \rightarrow y$ means that instruction
$x$ must precede instruction $y$.
\index{program composed of dependencies}%

This graph representation compiles to ParaGAT quite simply.
Instructions having common gates are put into the same gated stack.
Instructions having no gates are put into a single ungated stack.
The stack is synchronous if some of the instructions 
of a stack have dependencies
on other instructions in the stack. The stack is asynchronous otherwise.
A gate $g$ is external if all instructions either directly
or transitively precede or follow $g$.

\section{An Example Application in ParaGAT}

As a practical example of our approach, consider a detector
for several harmful single stranded pieces of DNA.
\index{detector}%
Let's say that we want to indicate which strand is present by using
quenched fluorescent markers.
So, a DNA instruction in a stack will not fluoresce but will do so
once released.
Now, suppose we have two colors (red and blue) to choose from, but
we want to distinguish between four different strands, which we 
will call $s1$, $s2$, $s3$, and $s4$.

We arrange our stacks so that $s1$ and $s2$ will cause red to show in 
a first time period given the external gate ``phase1.''
Then $s1$ will cause red to show in the second (following) time period,
but $s2$ will cause blue to show in the second time period.
Similarly,
$s3$ and $s4$ will cause blue to show in 
a first time period.
Then $s3$ will cause red to show in the second time period,
but $s4$ will cause blue to show in the second time period.

Here is the block for the first time period for $s1$ and $s2$.
(We have not yet
figured out how to construct a gate that embodies a 
boolean {\em or}. So, we may in fact need
different  stacks for the {\em or} condition.)
\index{external}%

\begin{quote}
\begin{verbatim}
gate (s1 or s2) 
external gate phase1 
begin async
  red fluorescent marker instruction 
  red fluorescent marker instruction 
  red fluorescent marker instruction 
  red fluorescent marker instruction 
end async
\end{verbatim}
\end{quote}

We treat $s3$ and $s4$ similarly. They cause a
blue fluorescence in the first
time period. 

\begin{quote}
\begin{verbatim}
gate (s3 or s4) 
external gate phase1 
begin async
  blue fluorescent marker instruction 
  blue fluorescent marker instruction 
  blue fluorescent marker instruction 
  blue fluorescent marker instruction 
end async
\end{verbatim}
\end{quote}

For the second time period, we use an external gate to ensure
that the second time period stacks don't start
emitting their markers while the first time
period stacks are emitting their strands.
That is, we might flush out the fluorescence from the first time period
as well as the phase1 strands
and then introduce the phase2 strand externally.
Either $s1$ or $s3$ cause red fluorescence in the second time period.

\begin{quote}
\begin{verbatim}
flush
gate (s1 or s3) 
external gate phase2
begin async
  red fluorescent marker instruction 
  red fluorescent marker instruction 
  red fluorescent marker instruction 
  red fluorescent marker instruction 
end async
\end{verbatim}
\end{quote}



Either $s2$ or $s4$ cause blue fluorescence in the second time period.

\begin{quote}
\begin{verbatim}
flush
gate (s2 or s4) 
external gate phase2 
begin async
  blue fluorescent marker instruction 
  blue fluorescent marker instruction 
  blue fluorescent marker instruction 
  blue fluorescent marker instruction 
end async
\end{verbatim}
\end{quote}

\section{Future Work}

{\em ParaGAT} is essentially a machine language.
It consists of strands to be put on stacks, strands to act as gates,
and primitives for flushing and external unlocking.
Skilled language designers will be able to build
higher level constructs 
on top of these primitives.
The challenge is to construct a language that is high level
and easy to write, but that also compiles to time- and material-efficient 
DNA programs.
At this point, we see this as a wide open problem.


\clearpage

