  % -*- Mode:TeX -*-


\documentstyle[11pt]{article}

\input{/jj/kt/laktex}

\setlength{\oddsidemargin}{0 in}
\setlength{\textwidth}{6.5 in}
\setlength{\topmargin}{-0.5 in}
\setlength{\textheight}{9.0 in}

%%% make the document look like Scribe output.
\def\thesection       {\arabic{section}.}
\def\thesubsection    {\thesection \arabic{subsection}.}
\def\thesubsubsection {\thesubsection \arabic{subsubsection}.}

\setcounter{page}{12}
\setcounter{section}{1}

% Allow @ in control sequence names  
\makeatletter
\def\subsubsection{\@startsection{subsubsection}{3}{\z@}{-3.25ex plus 
 -1ex minus -.2ex}{1.5ex plus .2ex}{\large\bf}}
% Restore @ to "other" status.
\makeatother


\begin{document}
\section{TTDA format}

TTDA format is a CIOBL format for Tagged-Token Dataflow Architecture object
code.  In the following description, CIOBL lists are indicated by parentheses.

TTDA object code is a sequence of {\it code blocks}.  Each code block is
represented by three CIOBL objects: the {\it property list}, followed by the
{\it instruction count}, followed by the
{\it instruction list}.  A TTDA file consists of a sequence of property list,
instruction count, instruction list, property list, instruction count,
instruction list, {\it etc}.  The final object in the TTDA file is an {\it
exsym-table}.  This contains information about all of the definitions in the
file for use in type-checking and optimization.

\subsection{The Property List}

The property list is a list of the form:
\begin{example}
    ({\it indicator-1} {\it value-1} {\it indicator-2} {\it value-2} {\it ...})
\end{example}

Any number of indicator/value pairs may be present.  Each indicator is a
keyword symbol which identifies a particular property of the code block.  Each
value is a CIOBL object which gives the value for that property.  Currently,
the following properties are defined:

\begin{description}
\item[:CODE-BLOCK-NAME] A keyword symbol which identifies the code block.
Each code block in the file will have a different {\tt :CODE-BLOCK-NAME}
property.

\item[:PROCEDURE-NAME] The code block name of the code block of which this
code block is a subsidiary.  For the top-level code block of a procedure,
this property will be the same as the {\tt :CODE-BLOCK-NAME} property.
Currently, subsidiary code blocks only occur in the case of nested loops or
more than one top-level loop.

\item[:ARITY] the arity of the procedure that this code block implements.
This property is only present for the top-level code block of a procedure.

\item[:CODE-BLOCK-SUMMARY] Present only for the top-level code block of a
procedure, this property is a nested list structure that identifies the
relationship between the code blocks that comprise the procedure.  It is a
list of the form {\tt ({\it code-block-name} {\it summary-1} {\it summary-2}
{\it ...})}, where each {\it summary} is the summary for a direct descendent
of this code block.

Suppose, for example, that procedure {\tt arvind} has two outer loops, the
first
of which also has a nested loop.  Suppose also that the compiler decides to
place each of the three loops in a separate code block, naming the code blocks
for the outer loops {\tt :ARVIND-0} and {\tt :ARVIND-1}, and naming the
nested
loop {\tt :ARVIND-0-0}.  Then the {\tt :CODE-BLOCK-SUMMARY} property of the
code block named {\tt :ARVIND} is {\tt (:ARVIND (:ARVIND-0 (:ARVIND-0-0))
(:ARVIND-1))}.

\item[:N-LOOPS] Indicates how many loops are present within the code block.
Currently, this is either zero or one.  Note that {\tt :N-LOOPS} may be
one even for the top-level code block of a procedure.

\item[:CONSTANT-AREA-SIZE] Indicates how many locations of constant area
should be allocated for invocations of the code block.  Note that this may be
non-zero even if {\tt :N-LOOPS} is zero.

\item[:PLACE] A {\tt PLACE} object which indicates where the procedure or
loop appeared in the source file.

\item[:PATHNAME] The pathname of the source file from which this code block was
compiled, represented as a string.

\item[:COMPILER-VERSION] An object which identifies what compiler was used to
compile this code block [the exact contents of this property is not yet
defined].

\item[:CONSTANTS-BOUND] A list of keywords naming the top-level constants
defined in this {\it constant-def} code-block.  

\end{description}

It is not an error if the property list contains properties not listed above.

\subsection{The Instruction List}

The instruction list is a CIOBL list containing the {\it instructions} which
comprise the code block.  For the convenience of programs which read TTDA
files, the instruction list is preceded by the instruction count, which is just
an integer indicating how many instructions are in the instruction list.  The
instructions in the instruction list are assumed to be numbered consecutively
from zero.

A TTDA instruction has an {\it opcode}, which identifies what operation the
instruction performs.  When an instruction fires, it sends results to other
instructions.  The {\it destination list} is used to build the tokens for
these results.  The destination list is a list of zero or more {\it
destinations}, each of which identifies an input of another instruction in
the code block; each destination is an arc in a dataflow graph.
Corresponding to each destination is an {\it annotation}, which carries
debugging information such as the name of the variable.  Each destination
list/annotation list pair is called an {\it output} of an instruction.  The
opcode determines how many outputs an instruction has.  Currently the {\tt
:SWITCH} opcode has two outputs, while all others have only one.  Finally, an
instruction may or may not have a {\it constant}.

An instruction appears in one of two forms, depending on whether or not it has
a constant:
\begin{example}
  (\i{opcode} NIL \i{dest-list-0} \i{ann-list-0} \i{dest-list-1} \i{ann-list-1} \i{...})
\end{example}

or

\begin{center}
\begin{example}
  (\i{opcode} \i{const-pos} \i{const-type} \i{const-val} \i{dest-list-0} \i{ann-list-0} %
\i{dest-list-1} \i{ann-list-1} \i{...}) 
\end{example}
\end{center}

{\it Opcode} is a keyword symbol.  Each {\it dest-list} is a list of
integers, where each integer encodes a destination according to the following
formula:

$$ Destination  =  8 \times Offset + 2 \times Position + Partner\mbox{-}P $$


{\it Offset} is the number of the instruction to which the destination points
(recall that instructions are numbered consecutively from zero).  {\it
Position} is 0, 1, or 2 according to whether the destination is to input
zero, one, or two of the instruction at {\it offset}.  If {\it Position} is
3, it indicates that the instruction at {\it offset} is to ignore the value.
{\it Partner-P} is 0 if the token sent for the destination does not need to
wait for a partner, 1 if it does.

Each {\it ann-list} is a list of CIOBL objects, each being an annotation for
a destination of the corresponding {\it dest-list}.  By convention, an
annotation of {\tt NIL} means that a destination has no annotation.  The
first annotation is for the first destination, {\it etc.}, and if the
annotation list is shorter than the destination list, it means that the
destinations which have no matching entry in the annotation list have no
annotation.  In other words, trailing {\tt NIL}s are dropped from the
annotation list.

If the instruction has a constant, {\it const-pos} is {\tt 0}, {\tt 1}, or
{\tt 2}, according to whether the constant is for input zero, one, or two of
the instruction.  {\it Const-val} is a CIOBL list of the form {\tt ({\it
type} {\it value})}, where {\it type} is a keyword symbol.  The various types
are explained below.

\begin{description}
\item[:INTEGER]{\it Value} is an integer to be used as a constant.

\item[:FLOAT]{\it Value} is a float to be used as a constant.

\item[:CHARACTER]{\it Value} is a character to be used as a constant.

\item[:BOOLEAN]{\it Value} is one of the two keyword symbols {\tt :TRUE} or
{\tt :FALSE}, indicating a boolean value to be used as the constant.

\item[:NIL] The constant is {\tt nil}, the end-of-list indicator.  The value
of {\it value} is ignored; typically it will be {\tt NIL}.

\item[:SYMBOL]{\it Value} is the name of a symbol.  Since Id has no package
system, the package of {\it value} is irrelevant, and for that reason
{\it value} will always be a keyword symbol.

\item[:CONSTANT-AREA]{\it Value} is an integer giving the offset into
constant area from which the constant is to be taken.

\item[:IDENTIFIER]{\it Value} is a keyword symbol naming a global identifier
whose value is to be used as a constant.  The linker or loader must replace
this type of constant with the actual value of the identifier, when it
becomes known.  The linker/loader replaces this symbolic constant with the
position where the actual value of the constant will be stored in the global
constant area.

\item[:CODE-BLOCK]{\it Value} is a keyword symbol naming a code block.  The
linker or loader must replace this type of constant with whatever is an
appropriate input to the {\tt :GET-CONTEXT} instruction.  Typically, this is
an integer code block index.
\end{description}

Note that if an Id procedure {\tt f} is defined at top level, then there is
both a code block named {\tt :F} and an implied global identifier named {\tt
:F}.  The value of the global identifier is a closure of {\tt f} over no
arguments.  Hence, if the constant {\tt (:CODE-BLOCK :F)} appears in an
instruction, the loader replaces it with the code block index of code block
{\tt :F,} while if the constant {\tt (:IDENTIFIER :F)} appears in an
instruction, the loader replaces it the location of the closure in the global
constant area.  The run time system will ensure that the closure is in fact
written to the proper location in the global constant area.  For
non-procedural constants, the {\tt constant-def} code-block will compute the
value and write it into the constant area.

\subsection{The Exsym Table}

The Exsym-table (EXternal SYMbol table) holds information about all the
definitions in the file.  An exsym-table maps names to sets of {\it
properties} and {\it assumptions}.  While compiling a definition named {\tt
foo}, the compiler will learn things such as procedure arity, type, whether
it is inlinable, {\it etc.} --- these facts are stored as properties in the
exsym for {\tt foo}.  The compiler may also {\it use} the values of
properties for other definitions --- the values of these facts are stored in
the assumptions list, and the values of these {\it assumed} properties are
checked against the {\it actual} values at invocation time, as a consistency
check.

The exsym-table, a user-defined object, is written to the output file as 
\begin{example}
    <user-defined-begin> dfcs:exsym-table
       \i{n-exsyms} \i{exsym-0} \i{exsym-1} \i{etc.} 
    <user-defined-end>
\end{example}
 {\it N-exsyms} is the number of exsyms in the exsym table.  Each exsym
consists of 
\begin{example}
    <user-defined-begin> dfcs:exsym
       \i{exsym-name} \i{exsym-property-alist} \i{exsym-assumption-alist} 
    <user-defined-end>
\end{example}
 The {\it exsym-property-alist} has the form of a LISP alist:
\begin{example}
    ((\i{property-0 value-0}) (\i{property-1 value-1}) ... )
\end{example}
and each {\it exsym-assumption-alist} consists of an alist of the following form: 
\begin{example}
    ((\i{symbol-0} (\i{property-0 assumed-value-0}) ...)
     ...
     (\i{symbol-n} (\i{property-0 assumed-value-0}) ...))
\end{example}

Here are some of the properties and the encodings for their values:
\begin{description}
\item[:ALGEBRAIC-TYPE] If this exsym denotes an algebraic type, then this
property holds a list of the names of the constructors of this type.

\item[:ARITY] The arity of a procedure.

\item[:DISJUNCT-TAG] This is the tag of the sum constructed by this
procedure.  This will either be a number, denoting which disjunct it is, or
{\tt :POINTER} or {\tt :NON-POINTER} if this constructor belongs to a type
with one non-nilary constructor and one nilary constructor, and the machine
can tell the difference at run time between an array and a non-array.

\item[:GLOBAL-CONSTANT] {\it value} will be the name of the code-block which
computes and stores the value of this constant.

\item[:INLINABLE-DEFINITION] A representation of the program graph to be
substituted instead of a call to this procedure.  The encoding of a
program dataflow graph is describe in
Section~\ref{program-dataflow-graph}.

\item[:IS-CONSTRUCTOR] If this property is non-nil, then it contains the name
of the algebraic type to which this constructor belongs.

\item[:DEFINED-TYPE] A representation of the {\it type} of the procedure or
constant.  The encoding of a type is described in
Section~\ref{type-expression}.

\item[:USES-NAMES] A list of all the global names referenced by this code
block.

\item[:RECURSIVE-SET] A list of the names included in the recursive set of
this procedure.  If this procedure is not recursive, then this should be
{\tt NIL}.

\item[:TYPE-ARITY] {\it value} is a number representing how many
parameters this {\it type-constructor} expects.

\item[:NON-GENERIC-TYPES-ENCODING] A list of numbers corresponding to
the type-variables in the type-expression stored in the {\tt
:DEFINED-TYPE} property.  This denotes that these variables are {\it
non-generic} (a magical property that attempts to make Milner style
type-checking work in the presence of side-effects).

\end{description}

\subsubsection{The Program Dataflow Graph}
\label{program-dataflow-graph}

The program graph may be stored as a value for the {\tt
Inlinable-Definition} property in the exsym-table.  Because the graph is
a circular structure, it needs a special encoding.

A dataflow graph is a {\it user defined} CIOBL object with the following contents:
 \begin{example}
    <user-defined-begin> dfcs:dataflow-graph
      \i{plist} 
      \i{n-maps} (\i{map-0 map-1 ... map-n-maps})
      \i{n-instructions}
      (\i{opcode-0 im-0 om-0 opcode-1 im-1 om-1}
         ... 
       \i{opcode-n-inst im-n-inst om-n-inst})
      (\i{origin-list-0 origin-list-1 ... origin-list-n-inst})
      \i{n-slots} :PARAMETER (\i{parameter-0 parameter-1 ... parameter-n-inst})
      \i{slot-name-1} (\i{value-0 value-1 ... value-n-inst})
         ...
      \i{slot-name-n-slots-2} (\i{value-0 value-1 ... value-n-inst})
      :OTHER-SLOTS (\i{other-slots-0 other-slots-1 ... other-slots-n-inst})
      \i{root-set}
    <user-defined-end>
\end{example}

The {\it plist} is just the plist of the dataflow graph.  Each {\it map-i} is a port
map description, as returned by {\tt PORT-MAP-DESCRIPTION}.  When writing a dataflow
graph, we avoid writing duplicate maps, both to minimize file length and to maximize
sharing when the graph is read back in.  The graph topology is described by two
lists.  The first gives the opcode and port maps for each instruction: {\it im-i}
and {\it om-i} are the indices within the port map list of instruction {\it i}'s
input map and the output map.  The second gives the connectivity:
each {\it origin-list} is of the form
\begin{center}
\begin{example}
    (\i{inst-0 port-0 ann-0 inst-1 port-1 ann-1} ... \i{inst-n-inp port-n-inp ann-n-inp}),
\end{example}
\end{center}
giving the {\it index}, {\it port}, and {\it arc} annotation of each instruction
wired to this instruction's inputs.  If an instruction has nothing wired to a
particular input then instead of three values there is the single value {\tt NIL}.
There follows {\it n-slots} pairs of a keyword symbol and a list of values; these
give the values for each instruction of the indicated slot.  The first of these is
always {\tt :PARAMETER}, and the last of these is always {\tt :OTHER-SLOTS}.  {\tt
:OTHER-SLOTS} is a bit funny since there is really no {\tt :OTHER-SLOTS} visible
outside DFCS -- its values are plists as actually used in the {\tt :OTHER-SLOTS}
slots of instructions.  The pairs between {\tt :PARAMETER} and {\tt :OTHER-SLOTS}
can be used to record slots for which most instructions have a value, which can
result in smaller files because there don't need to be so many indicators in {\tt
:OTHER-SLOTS}.  Finally, the root-set is a list of the indices of the instructions
comprising the root set.

The values for the {\tt PARAMETER} and other slots may include references to
instructions within the dataflow graph; these are represented by the {\tt
INSTRUCTION} {\it user defined} CIOBL object, which just contains the index of the
instruction pointed to.  It is an error for a slot to have a reference to an
instruction which is not part of the dataflow graph being written.  It is also an
error for a slot to contain a reference to a dataflow graph.  It is an error for the
plist to contain a reference to any instruction or dataflow graph.

The format above is a little strange at first glance, but was designed both for
compactness and for ease of reading.  It is possible to read this format without
doing any ``back patching''.

\subsubsection{Variables}

One last object which may occur in dataflow graphs are {\it Variables}.  These are
put on arc annotations to show to which variable in the program these arcs
correspond.  A variable consists of a {\it Source Name}, that is the name the
programmer typed in, a {\it Place}, denoting the column, line and character number
where the variable occured in the source file, and a {\it Unique Name}, assigned by
the Scope Analysis module so that we do not have to worry about accidently {\it
capturing} free variables when we rearrange the code.  A variable is encoded as
follows.
\begin{example}
    <user-defined-begin> id::variable
      \i{Source-Name} \i{place} \i{Unique-Name}
    <user-defined-end>
\end{example}

\subsubsection{Type Expressions}
\label{type-expression}

Representations of type expressions are stored as values for the {\tt
Defined-Type} property.  These may also be circular structures and
therefore need a non-trivial encoding.  A type expression may either be
a {\it Type-Var} or a {\it Type-Cons}.  A type variable is encoded as an
integer, for example the type expression:
        $$ *0 $$
would be encoded as:
\begin{example}
    <user-defined-begin> id::type-variable
      $0$
    <user-defined-end>
\end{example}

Most objects have more complex types, such as:
        $$ *0 \rightarrow N \rightarrow *0 $$
Which consists of three {\it type-conses} and one type-variable.
\begin{example}
    (-> \i{type-var-0} (-> (N) \i{type-var-0}))
\end{example}
This type would be encoded as:
\begin{example}        
    <user-defined-begin> id::type-var 
       ( :-> 0 ( :-> ( :N ) 0 ) )
    <user-defined-end>
\end{example}
Each unique integer in the encoding will be replaced by a distinct {\it
type-var}, and multiple references to the number in the encoding will be
replaced by pointers to the same {\it type-var}.

\subsection{The Copyright Notice}

 TTDA files may contains a copyright notice.  In the Id compiler, a
copyright notice is represented as a structure, which must be inserted
into the object code in order for the object code to be protected.
 \begin{example}
    (defstruct (copyright-notice
                 (:constructor make-copyright-notice (string)))
      string)
\end{example}

 An Id file may be copyrighted by using a copyright notice pragma, {\it e.g.},
\begin{example}
    @copyright\_notice "Copyright (c) 1986,1987,1988,1989,1990
                       Massachusetts Institute of Technology.
                               ALL RIGHTS RESERVED";
\end{example}
This is the form used in the Id World libraries.

 In a TTDA file, the copyright notice is a user-defined object, and is represented as 
\begin{example}
    <user-defined-begin> id::copyright-notice
      \i{string}
    <user-defined-end>
\end{example}

\end{document}
