\usepackage{bytefield}
\usepackage[colorlinks=true, pdfstartview=FitV, linkcolor=blue, citecolor=blue, urlcolor=blue]{hyperref}
\renewcommand{\ttdefault}{cmtt}
-\title{The FleetTwo Toolchain Manual\\{\normalsize A Compiler Writer's View of Fleet}}
+\title{The FleetTwo Toolchain Manual\\{\normalsize A Compiler Writer's View of FleetTwo}}
+\author{Adam Megacz}
\begin{document}
\maketitle
\begin{thebibliography}{[GDG01]}
\bibitem[ArchMan]{ArchMan}
{\it The FleetTwo Architecture Manual}
+\bibitem[Meg06]{SBP}
+ Megacz, Adam, {\it Scannerless Boolean Parsing}. Electronic Notes in
+ Theoretical Computer Science 1368, (Volume 164, Issue 2):
+ Proceedings of the Sixth Workshop on Language Descriptions, Tools,
+ and Applications (LDTA 2006)
\end{thebibliography}
\vspace{3cm}
\begin{abstract}
-Fleet compilers and tools work primarily with representations of two
-entities: Ships, Instructions, and Test Cases. In order to promote
-greater interoperability, the FleetTwo Toolchain defines both a Java
-API and a textual file format for each of these.
+Fleet compilers and tools work primarily with three entities: Ships,
+Instructions, and Test Cases. In order to promote greater
+interoperability, the FleetTwo Toolchain defines both a Java API and a
+text file format for each of these.
\end{abstract}
\vfill
\pagebreak
\section{Introduction}
-Fleet compilers and tools work primarily with representations of two
-entities: Ships, Instructions, and Test Cases. In order to promote
-greater interoperability, the FleetTwo Toolchain defines both a Java
-API and a textual file format for each of these.
+Fleet compilers and tools work primarily with three entities: Ships,
+Instructions, and Test Cases. In order to promote greater
+interoperability, the FleetTwo Toolchain defines both a Java API and a
+textual file format for each of these.
In the case of ships, this takes the form of the {\tt .ship} file
format for describing ships and the {\tt ShipDescription} Java class
-which an implementation of Fleet uses to inform the toolchain (such as
-the assembler and compiler) of what ships it contains and how they may
-be used. A library is provided for parsing the textual file format
-into the Java representation.
+which an implementation of Fleet uses to inform the toolchain of what
+ships it contains and how they may be used. The toolchain includes a
+library for parsing the textual file format into the Java
+representation.
In the case of instructions, and more generally programs, this takes
the form of the {\tt .fleet} assembly language file format for
programs into {\tt CodeBag}s of {\tt Instruction}s, and for writing
those objects back out as text.
-Finally, the FleetTwo Toolchain defines a very simple debugging
-interface, {\tt Device}, which lets a program dispatch a codebag to a
-running Fleet chip and read back the words which arrive at its {\tt
- Debug} port. A test harness has been written which makes no
-assumptions about the device under test other than that it supports
-this debugging interface and that it is capable of describing itself
-via the {\tt ShipDescription} API. By meeting these relatively minor
-requirements, a new Fleet implementation can immediately take
-advantage of a great deal of prebuilt testing infrastructure. This
-API has been implemented and is fully functional for both the software
-interpreter implementation of Fleet and the FPGA simulation of Fleet.
+In the case of Test Cases, the FleetTwo Toolchain defines a very
+simple debugging interface, {\tt Device}, which lets a program
+dispatch a codebag to a running Fleet implementation or emulator and
+read back the words which arrive at its {\tt Debug} port. A test
+harness has been written which makes no assumptions about the device
+under test other than that it supports this debugging interface and
+that it is capable of describing itself via the {\tt ShipDescription}
+API. By meeting these relatively modest requirements, a new Fleet
+implementation can immediately take advantage of a great deal of
+prebuilt testing infrastructure. This API has been implemented and is
+fully functional for both the software interpreter implementation of
+Fleet and the FPGA simulation of Fleet.
\pagebreak
-\section{Representing Ships}
+\section{Ships}
\subsection{Ship Description Files (FleetDoc)}
Inspired by JavaDoc, the Fleet software toolchain includes a tool
\item Java source code for a software simulation of the ship
\item Verilog source code for an FPGA simulation of the ship
\item A test case for the ship
-\item A list of the contributors to all of the above
+\item A list of the people who contributed to all of the above
\end{itemize}
Keeping all of this information in a single file ensures that changes
Keeping this information in {\it machine-readable} format makes it
possible to automatically generate tools which depend on the precise
-details of ship ports (such as the Fleet assembler) without the risk
+details of ship ports without the risk
inherent in manual synchronization.
The latter half of the architecture manual \cite{ArchMan} -- including
\pagebreak
\subsection{Java API for Ship Descriptions}
+The FleetTwo toolchain includes a utility for parsing a {\tt .ship}
+file into a {\tt ShipDescription}. There is one {\tt ShipDescription}
+for each {\it kind} of ship. This distinction will become important
+later, when we introduce classes to represent {\it instances} of ship
+types.
+
+\begin{verbatim}
+/** a description of a ship */
+public class ShipDescription implements Iterable<DockDescription> {
+ public String getName();
+ public Iterable<ConstantDescription> getConstantDescriptions();
+ public Iterable<DockDescription> getDockDescriptions();
+}
+
+/** a description of a valve */
+public class DockDescription {
+ public String getName();
+ public boolean isInbox();
+ public boolean isOutbox();
+ public DockDescription getShortcut();
+}
+
+/** a constant declared by a ship */
+public class ConstantDescription {
+ public final long setbits;
+ public final long clearbits;
+ public final boolean signExtend;
+ public final int numberOffset;
+ public final int numberWidth;
+}
+\end{verbatim}
+
+
\pagebreak
-\section{Representing Machine Code}
+\section{Instructions}
\subsection{Fleet Assembly Language}
The Fleet Assembly language is designed to be a human-readable
depiction of the bits which comprise a Fleet program.
\subsubsection{Formal Grammar}
-The formal syntax is given below:
+
+The formal syntax is given below. The metagrammar used is that of the
+Scannerless Boolean Parser \cite{sbp}.
\verbatiminput{fleet.g}
CodeBagDef}.
A {\tt Fiber} is a set of {\tt Instruction}s which all share a common
-execution point ({\tt Pump}). Each instruction can be a {\tt unclog},
+execution point ({\tt Pump}). Each instruction can be {\tt unclog},
{\tt clog}, {\tt kill}, {\tt literal}, or a set of {\tt Command}s. It
should be fairly clear how to translate all but the last sort of
instruction into machine code, based on the encodings in
notify}, or {\tt notifyLast}. These are compiled as shown below:
\begin{itemize}
-\item[\tt wait] is valid only on an inbox, and sets {\tt Ti=1}
\item[\tt nop] is not valid in combination with any other command; it sets all control bits to {\tt 0}
+\item[\tt wait] is valid only on an output port, and sets {\tt Ti=1}
\item[\tt discard] sets {\tt Di=1,Dc=0}
\item[\tt recieve] is valid only on an input port, and sets {\tt Di=1,Dc=1}
\item[\tt take] is valid only on an output port, and sets {\tt Di=1,Dc=1}
\item[\tt deliver] is valid only on an input port, and sets {\tt Do=1}
-\item[\tt send] is valid only on an output port, and sets {\tt Do=1,To=1}
\item[\tt sendto] is valid only on an output port, and sets {\tt Do=1}
+\item[\tt send] is valid only on an output port, and sets {\tt Do=1,To=1}\footnote{see \cite{ArchMan} for the special meaning this bit combination has}
\item[\tt notify] sets {\tt To=1} and is not valid in combination with {\tt send} or {\tt sendto}
\item[\tt notifyLast] sets {\tt To=1,Ig=1} and is not valid in combination with {\tt send} or {\tt sendto}
\end{itemize}
It is an error to specify two commands within a single instruction if
-both of the commands attempt to set the same bit (even if they attempt
-to set it to the same value).
+both of the commands attempt to set the same bit, even if they attempt
+to set it to the same value.
-Note that un-named (``anonymous'') codebags may appear as literals.
+Note that un-named ``anonymous'' codebags may appear as literals.
This means that it is possible to write interesting programs such as
the one below:
\begin{verbatim}
-#expect 3
-
#ship debug : Debug
#ship memory : Memory
\pagebreak
\subsection{Java API for Fleet Machine Code}
+\subsection{Ships}
+\begin{verbatim}
+public abstract class Ship {
+
+ /** return the description for this ship */
+ public ShipDescription getShipDescription();
+
+ /** return all pumps which feed this ship; order is NOT significant */
+ public Iterable<Dock> getDocks();
+ public Dock getDock(String s);
+
+ /** if this is the 4th fifo ship, this method returns 4 */
+ public int getOrdinal();
+
+ /** return the Fleet that this Ship belongs to, if any */
+ public Device getDevice();
+}
+\end{verbatim}
+
+\subsection{Dock}
+\begin{verbatim}
+public class Dock {
+
+ /** the descriptive name of this pump (relative to its ship) */
+ public abstract String getName();
+
+ /** return the Ship to which this Dock belongs */
+ public abstract Ship getShip();
+
+ /** the maximum number of instructions we can put in the Dock instruction fifo,
+ * or Integer.MAX_VALUE if unbounded */
+ public abstract int getInstructionFifoLength();
+
+ /** returns true if this is an inbox */
+ public abstract boolean isInbox();
+
+ /** returns true if this is an outbox */
+ public abstract boolean isOutbox();
+
+ /** return the Dock which is the destination of this Box's shortcut (if any) */
+ public Destination getShortcut() { return null; }
+}
+\end{verbatim}
+
+\subsection{Instructions}
+\begin{verbatim}
+public abstract class Instruction {
+ public final Pump pump;
+
+ public static class UnClog extends Instruction {
+ }
+
+ public static class Clog extends Instruction {
+ }
+
+ public static abstract class CountingInstruction extends Instruction {
+ public final int count;
+ public CountingInstruction decrementCount();
+ }
+
+ public static class Kill extends CountingInstruction {
+ }
+
+ public static class Executable extends CountingInstruction {
+
+ public final Destination dest;
+
+ public final boolean tokenIn;
+ public final boolean dataIn;
+ public final boolean latch;
+ public final boolean send;
+ public final boolean sendTo;
+ public final boolean tokenOut;
+ public final boolean requeue;
+ public final boolean ignoreUntilLast;
+
+ public boolean isStanding();
+ }
+
+ public static class Literal extends CountingInstruction {
+ public final long literal;
+ }
+}
+\end{verbatim}
+
\pagebreak
\section{Test Cases}
+
\subsection{Test Case File Format}
+
+The test case file format is quite simple -- it is nothing more than a
+regular Fleet assembly language program with {\tt \#expect} statements
+to indicate the values which should arrive at the {\tt Debug.in} port
+if the test runs correctly.
+
\subsection{Java API for Controlling Device Under Test}
+\subsection{The Device}
+\begin{verbatim}
+public abstract class Device implements Iterable<Ship> {
+
+ /** read a machine-formatted instruction from a file (into a Java object) */
+ public abstract Instruction
+ readInstruction(DataInputStream is) throws IOException;
+
+ /** write a machine-formatted instruction to a file (from a Java object) */
+ public abstract void
+ writeInstruction(DataOutputStream os, Instruction instr) throws IOException;
+
+ public abstract Iterator<Ship> iterator();
+
+ /** if possible, run the given code and create a FleetProcess */
+ public FleetProcess run(byte[] code);
+}
+\end{verbatim}
+
+\subsection{A Running Test}
+
+\begin{verbatim}
+/** represents a <i>running</i> "slave" fleet with a debug connection */
+public abstract class FleetProcess {
+
+ /** dumps an instruction into the fetch unit */
+ public abstract void invokeInstruction(Instruction i);
+
+ /** reads a word back from the debug port */
+ public abstract long readWord();
+
+ public final synchronized void terminate();
+
+ public final boolean isTerminated();
+}
+\end{verbatim}
+
\end{document}
projects / fleet.git / blobdiff