  % -*- Mode:TeX -*-


\chapter{Syntax Directed Operations}
\label{attributes}
\section{Parse Trees and Grammars}
\label{grammars}

 In this section we will describe syntax-directed operations on parse-trees
and parse-tree-nodes that can be performed in DFCS.  As a running example,
we will use the simple expression grammar given below (in abstract syntax):
\begin{eqnarray*}
\mbox{expression}	& ::= & \mbox{plus-expression} \\
			&     & \\
\mbox{plus-expression}	& ::= & \mbox{plus-expression + mul-expression} \\
\mbox{plus-expression}	& ::= & \mbox{plus-expression - mul-expression} \\
			&     & \\
\mbox{mul-expression}	& ::= & \mbox{mul-expression * prim-expression} \\
\mbox{mul-expression}	& ::= & \mbox{mul-expression / prim-expression} \\
			&     & \\
\mbox{prim-expression}	& ::= & \mbox{number}
\end{eqnarray*}

\subsection{Grammars}

 A {\em grammar}\index{grammar} is a set of productions.  A grammar has a
name, and a grammarspec\index{grammarspec}, the latter used to identify the
grammar within a production specification, also called a {\em
prodspec}\index{prodspec}. For example, consider the following prodspec:

\begin{verbatim}
    (expression  -> "(" expression ")")
\end{verbatim}

The grammarspec in this example is the symbol {\tt ->}.  By having
different grammarspecs, several grammars can be in use; typical
grammarspecs might be {\tt -ID->} \etc.

All productions have a tag which identifies them; the tag is a keyword
symbol. For example, the above production may have a tag {\tt
:expression/1}.  Grammar keeps a mapping from the prodspec to the
production tag in a hash table.  Finally, a grammar may have some
attributes associated with it.

\lispdoc defgrammar grammarname grammarspec [Macro]
 Define a grammar named {\em grammarname}, which is identified by the symbol
{\em grammarspec} in production specifications.



\subsection{Productions}

 A production is a structure for recording information about a reduction in
the grammar.  In addition to prodspecs and tags, a production may also have
{\em properties} and {\em attributes}.

The tags of all productions are unique, even if they are in different
grammars.  This is for efficiency; if two productions in different grammars
could have the same tag, then to identify a ptnode you would have to do a
two-level dispatch on the tag and the grammar.

A prodspec is used to specify a production, and sometimes to associate names or other 
things with components of the production.  A prodspec takes the following form:
\begin{verbatim}
     (lhs grammarspec rhs-1 rhs-2 rhs-3 ...)
\end{verbatim}
\eg,
\begin{verbatim}
     (EXPRESSION -> LET (LET-BINDING-LIST BLIST) IN (EXPRESSION))
\end{verbatim}
 Here, the grammarspec is the symbol {\tt ->}, and names a particular grammar.
Some of the other components have associated values, such as the symbol {\tt
blist} for {\tt let-binding-list}.  The last right hand side component
explicitly has no value.  The left hand side has an implied value of the symbol
{\tt expression}; thus in a prodspec, {\em symbol} is equivalent to {\tt ({\em
symbol} {\em symbol})}.  This means that {\tt let} and {\tt in} each have an
implied value, but that will be irrelevent if they are terminals of the grammar
(\ie, have no corresponding children in ptnodes represented by this production).
When determining the production a prodspec names, only the symbol part of
prodspec components matters.

A special case of a prodspec is when some of the rhs components have values
which are integers: this is called a {\em template}\index{template}.  Each
production has a template where the integers indicate child numbers for the
rhs components.

\lispdoc defproduction tag grammar-name \clauses \optgroup{\list{{\tt :template} template}} 
                                        \repeat{\list{{\tt :properties}
                                                      \repeat{\group{indicator value}}}}
        [Macro]
 This defines a production with tag {\em tag} for grammar {\em grammar-name}.
The {\em template} will be a prodspec, as defined above.  The {\em properties}
clauses define properties associated with this ptnode tag; these properties are
accessible via {\tt ptnode-get}.

If there is already a production with the same tag, grammar, and template,
then  the properties of the existing production  are replaced,
otherwise a new production is defined, which may require removal of an
existing production with the same tag, and removing other tags pointing to
the same production.

\lispdoc tag \rest prodspec [Macro]
 The {\tt tag} macro expands into the parse tree node tag associated with the
production named by {\em prodspec}.

\lispdoc ptnode-get ptnode indicator \optional default [Macro] 
This returns the value of the property {\em indicator} for the production
associated with the tag of the given parse tree node {\em ptnode}.  If no
value is found, then {\em default} is returned.

\subsection{A Grammar for the Expression Language}
\label{grammar-example}
\begin{example}
    (defgrammar expression-language ->)

    (defproduction :expression/1
       (:template (expression -> plus-expression)))

    (defproduction :plus-expression/1 
       (:template (plus-expression -> plus-expression "+" mul-expression)))
    (defproduction :plus-expression/2 
       (:template (plus-expression -> plus-expression "-" mul-expression)))

    (defproduction :mul-expression/1 
       (:template (mul-expression -> mul-expression "*" prim-expression)))
    (defproduction :mul-expression/2 
       (:template (mul-expression -> mul-expression "/" prim-expression)))

    (defproduction :prim-expression/1 
       (:template (prim-expression -> number)))

    ;;; number is a pseudo-terminal
    (defproduction :number)
\end{example}
 Note that the names of the non-terminals in the {\tt :template} clause of
the {\tt defproduction} forms match the abstract grammar, not the
particular tags given to individual productions.



\subsection{Grammar Abbreviations}

 A grammar abbreviation is similar to a production, in that it has a unique
{\em tag} and {\em template}.  However, it may actually name several
productions.  In order for an abbreviation to make sense, the productions
it abbreviates should be related in some fashion.

\lispdoc define-grammar-abbreviation tag \clauses \optgroup{\list{{\tt :template} template}}
                                         \list{{\tt :productions} \repeat{productions}}
        [Macro]

 This defines an abbreviation for one or more productions. The {\em
template}, if present, can be used to access the children of all the
specified productions. In this case, all the productions must contain the
same number of nonterminals. Different shapes of productions can be
abbreviated together only if a template is not desired. 

\subsection{Some abbreviations for the Expression Language}
\label{abbrev}
 In many cases, we could treat the addition, subtraction,
multiplication, and division productions of the expression grammar in
a uniform fashion, and so we would like to define and abbreviation:
{\tt any-binary-expression}.
\begin{example}
(define-grammar-abbreviation any-binary-expression
   (:template (e -> (e0 0) op (e1 1)))
   (:productions
     (plus-expression -> plus-expression "+" mul-expression)
     (plus-expression -> plus-expression "-" mul-expression)
     (mul-expression -> mul-expression "*" prim-expression)
     (mul-expression -> mul-expression "*" prim-expression)))
\end{example}
 The prodspec's {\tt any-binary-expression} and {\tt (e -> e0 op e1)} will
both match against any of the {\tt :plus-expression/1}, {\tt
:plus-expression/2}, {\tt :mul-expression/1} or {\tt :mul-expression/2}
productions.  As we shall see later, the template of the abbreviation can
be very useful in these cases.

\subsection{Traversing Parse Trees}

Two mechanisms are provided to traverse a given parse tree. The first
is {\em structural} traversal which directly accesses the parse tree's
parent children links and is independent of the grammar. The second is
{\em abstract} traversal that provides an abstract means of
identifying each ptnode with its production in the associated grammar
and descends through the tree according to the production reduced at a
given parse tree node. Both methods have their own merits. It is
expected that modules that perform structural editing of the parse
tree may use the former more naturally, while the modules that
annotate the tree with properties may find the latter more useful.

\lispdoc let-ptnode-children \list{\repeat{var}} ptnode \repeat{form} [Macro]
{\tt let-ptnode-children} is used to structurally descend in the parse tree
by one level. It evaluates the given forms as an implicit {\tt progn} in a
environment where each child of the ptnode {\em ptnode} is bound to the
corresponding variable {\em var}.

Specifically, the form
\begin{example}
(let-ptnode-children (\i{var-1\/} \i{var-2\/} \ldots) \i{ptnode}
   \i{form-1}
   \i{form-2}
   \ldots)
\end{example}
is equivalent to the form
\begin{example}
(let ((\i{var-1\/} (first (ptnode-children \i{ptnode\/})))
      (\i{var-2\/} (second (ptnode-children \i{ptnode\/})))
      \ldots)
   \i{form-1}
   \i{form-2}
   \ldots)
\end{example}
except that {\tt let-ptnode-children} takes special care that {\it ptnode\/} is
evaluated only once.  It is an error for {\it ptnode\/} to be a pseudo-terminal or
to have fewer children than there are {\it var\/}s.  While is it is legal for
{\it ptnode\/} to have more children then there are {\it var\/}s, this usage is
discouraged.



The following macros can be used to perform an abstract traversal of
the parse tree.

\lispdoc grammarcase
         keyform
         \repeat{\list{\group{\list{\repeat{key}} $|$ key} \repeat{form}}}
         [Macro]
This form, which is similar to Common Lisp's {\tt case} macro, is provided for
dispatching on the {\tt tag} slot of ptnodes.  Its general form is

\begin{example}
(grammarcase \i{keyform}
  (\i{keylist-1} \i{consequent-1-1} \i{consequent-1-2} \ldots)
  (\i{keylist-2\/} \i{consequent-2-1\/} \ldots)
  (\i{keylist-3\/} \i{consequent-3-1\/} \ldots)
  \ldots)
\end{example}

{\tt grammarcase} first evaluates {\it keyform}, which must evaluate to a ptnode,
and then takes the {\tt ptnode-tag} of the result, yielding the {\it key object}.
{\tt grammarcase} then considers each clause in turn.  If the key object matches
any item in a clause's keylist, then the consequents of that clause are
executed as an implicit {\tt progn}, with the value of the last consequent being
returned as the value of the {\tt grammarcase}.  If the satisfied clause has no
consequents, or if no clause is satisfied, {\tt grammarcase} returns {\tt nil}.

Each item in a keylist must be either a keyword symbol or a list of the
form {\tt ({\it symbol\/} -> {\it symbol-or-string\/} {\it
symbol-or-string\/} {\it ..\/})}.  The latter form is provided so that a
production may be referred to by its appearance (the prodspec), rather than
its tag.  This feature may only be used when the grammar is known at
compile time and has been loaded into the Lisp world.

If there is only one item in a keylist, then the item itself may be used as the
keylist.  In addition, the symbols {\tt t} and {\tt otherwise} may be used in place
of a keylist; if used, they must appear in the last clause, which will be
executed if all of the other clauses fail.  Here is an example of {\tt grammarcase}:

\begin{verbatim}
    (grammarcase x
      (:number
       e0)
      ((plus-expression -> plus-expression "+" mul-expression)
       e1)
      (((mul-expression -> mul-expression "*" prim-expression)
        (mul-expression -> mul-expression "/" prim-expression))
       e2)
      (otherwise
       (print-error "Unknown ptnode tag")))
\end{verbatim}

This is equivalent to the following:

\begin{verbatim}
    (grammarcase (ptnode-tag x)
      (:number
       e0)
      (:plus-expression/1
       e1)
      ((:mul-expression/1 :mul-expression/2)
       e2)
      (otherwise
       (print-error "Unknown ptnode tag")))
\end{verbatim}

Note that the actual symbols used in place of {\tt :plus-expression/1},
{\tt :mul-expression/1} and {\tt :mul-expression/2} would depend on the
grammar being used at the time.

\begin{lispdocs}
\lispdoc grammarbind \list{\group{\list{\repeat{key}}} $|$ key} ptnodeform \rest body 
         [Macro]
\lispdoc ptnode symbol \optional index [Macro]
\lispdoc n-ary-n                       [Macro]
\end{lispdocs}

 {\tt Grammarbind}, like {\tt let-ptnode-children}, sets up an environment in
which one may access the children of a ptnode by name.  However, in {\tt
grammarbind} the names are derived from the keys in the key list.  Each key is a
prodspec: either the template of a production defined by {\tt defproduction} or
the template of an abbreviation defined by {\tt define-grammar-abbreviation}.

The form {\em ptnodeform} must evaluate to a ptnode.  The {\tt ptnode} macro is
used within the scope of the {\tt grammarbind} to access the children of the
ptnode.  The argument to ptnode is the name of one of the non-terminal children
of the ptnode.
 
Each item in the keylist must be a list of the form {\tt ({\it symbol\/} -> {\it
symbol-or-string\/} {\it symbol-or-string\/} {\it ..\/})}.  This form is
provided so that the children of a production may be referred to by the
production's appearance, rather than by position, as in {\tt
let-ptnode-children}.  {\tt grammarbind} may only be used when the grammar is
known at compile time and has been loaded into the Lisp world.  Unlike in {\tt
grammarcase}, the keys in the keylist must have some similarity --- each key
must have the same number of non-terminals, and the corresponding non-terminals
must have the same names.  Furthermore, the names of each non-terminal child
must be distinct --- there cannot be two children of the ptnode which have the
same name.  For instance, if two non-terminals were named {\tt expression}, it
would be ambiguous which child is referred to by {\tt (ptnode expression)}.

The macro {\tt n-ary-n} is useful when the productions named in the
keylist have a \separated-by key within them. This is a special
key that permits n-way branching in the parse tree to be represented
by a single production. As an example, a tuple expression may be
parsed using the following production:

\begin{verbatim}
    (defproduction :tuple-expression/1
       (:template (tuple-expression -> plus-expression $separated-by ",")))
\end{verbatim}

The macro {\tt n-ary-n} returns the number of iterations of the right
hand side used at a particular parse tree node corresponding to this
production. For example, the value of {\tt (n-ary-n)} inside the scope
of a {\tt grammarbind} applied to a tuple expression parse tree node
used to parse the expression {\tt 2+3,4*5,1} will be 3.

\lispdoc grammarcasebind
         keyform
         \repeat{\list{\group{\list{\repeat{key}} $|$ key} \repeat{form}}}
         [Macro]

 This is a combination of {\tt grammarcase} with a {\tt grammarbind} in each clause.

\section{Parse Tree Attributes}
\label{ptnode-attr}

\subsection{Attribute Declarations}

\lispdoc define-ptnode-attribute selector-name grammar-name-or-names
        \clauses \list{{\tt :type} type} \optgroup{\list{{\tt :storage} storage}}
        \repeat{\list{{\tt :productions} \repeat{productions}}}
        [Macro]
 {\tt define-ptnode-attribute} defines a ptnode attribute.  The attribute is
created and added to the system, and a selector macro is defined for use by the
user.  The selector name must begin with {\tt ptnode-}, for consistency with
ptnode slots.  As with user defined slots, the name is imported into and
exported from the {\tt dfcs} package.

  The same attribute may apply to several grammars, therefore {\em
grammar-names} is a list of the grammars for which it is defined.

  {\em Type} is either {\tt :synthesized}\index{synthesized} or {\tt
:inherited}\index{inherited}. Synthesized attributes are computed
bottom-up; they are initialized at the terminal nodes of the parse tree and
the attribute value for the parent node is computed from that of its
children at each intermediate parse tree node. Inherited attributes
are computed top-down. They are initialized at the root of the parse
tree and the attribute values of the children are computed using that
of the parent at each intermediate parse tree node. 

{\em Storage} is either {\tt :ephemeral}, {\tt :memoized}, or {\tt
:permanent}.  An {\tt :ephemeral} attribute is not memoized at all: every time
an ephemeral attribute of a ptnode is fetched it is recomputed.  The advantage
is that it occupies no space within ptnodes.  The value of a {\tt :memoized}
attribute is recorded within a ptnode after it is computed, and so multiple
fetches of its value will cause at most one computation.  {\tt :memoized}
attributes are invalidated if the structure of the parse tree changes, and are
therefore recomputed when fetched after a change has been made to the parse tree
topology.  {\tt :permanent} attributes are like {\tt :memoized} attributes, but
their values are retained even if the structure of the parse tree changes.  {\tt
:permanent} attributes are intended for applications where the values of the
attributes can only be computed at a particular time, but once computed continue
to have meaning even when the structure of the parse tree changes.  An example
would be unique names for identifiers.  Because new nodes can be added to a
parse tree after permanent attributes have been computed, it is allowed to {\tt
setf} the values of {\tt :permanent} attributes, for once the structure of the
parse tree changes, values of already computed {\tt :permanent} attributes will
have to be maintained manually.

 {\tt :productions} clause supplies a list of production specifiers, tags,
templates, or abbreviations, that specify all the productions on which
this attribute is defined.  There may be more than one such
clause.  If there is no {\tt :productions} clause, then the attribute is
defined for all productions in the specified grammars.

%  The {\em tags} slot contains all productions which have storage reserved for
%this attribute, and so is always {\tt nil} for {\tt :ephemeral} attributes.
%
% {\em ubiquitous} contains a list of names of grammars for which this attribute
%is ``ubiquitous'', meaning that it is defined for all productions of the grammar.
%When a production is added to a grammar, it automatically has storage reserved
%for all ubiquitous attributes in the grammar.
%
%  The {\em function-table} maps tags to functions for computing the attribute.
%For a synthesized attribute, the tag maps to a single function which is applied
%to a ptnode to compute the attribute value for that node.  For an inherited
%attribute, the tag maps to an array indexed by child number containing functions
%which are applied to the parent to compute the attribute value for the child.
%Note that for inherited attributes, the tag of the parent is looked up in the
%function table.  This means that the set of tags which might be looked up is
%different from the set of tags for which the attribute has storage reserved.  To
%simplify matters, the function table contains an entry for {\em all} tags of all
%grammars for which the attribute is defined.  If no corresponding function
%exists for some tag, then the function table entry is {\tt nil} or an array of
%{\tt nil}s of the appropriate size.  When a default function is defined for a
%grammar, an entry is made in the DEFAULT-FUNCTION-ALIST, and all NILs in the
%FUNCTION-TABLE for tags of that grammar are replaced by the default function.
%The alist exists so that if new productions are added to the grammar, they can
%receive the default function.  Recording the default functions in the
%FUNCTION-TABLE as well makes function lookup fast.  Functions are recorded in
%the FUNCTION-TABLE and the DEFAULT-FUNCTION-ALIST as symbols, not functions
%themselves.
%
% The following six functions compute an attribute for a ptnode.  They are not
%called directly by the user: DEFINE-PTNODE-ATTRIBUTE generates a macro which
%expands into a call to the appropriate function of the six.  The function names
%are of the form COMPUTE-s-t-ATTRIBUTE, where s is either PERMANENT, MEMOIZED, or
%EPHEMERAL, and t is either SYNTHESIZED or INHERITED.  The PERMANENT and MEMOIZED
%functions determine a slot for recording the value computed, and either return
%the value already present in this slot or find and invoke the applicable
%attribute function, passing along the slot number so that the function can
%record the value without recomputing the slot number.  The MEMOIZED functions
%also revalidate the ptnode if necessary.  EPHEMERAL functions just invoke the
%function, without worrying about slots or revalidation.  The ptnode passed to
%the function is either the ptnode for which the attribute is computed, for
%SYNTHESIZED attributes, or that ptnode's parent, for INHERITED attributes.  The
%latter also receive the child number of the original ptnode.  An error is
%signalled if you try to compute an inherited attribute for a parentless ptnode.
%The PERMANENT functions also have SETF methods defined, since it is legal for
%PERMANENT attributes to be manually recorded.

\begin{lispdocs}
\lispdoc defattributes \repeat{\list{\group{\list{\repeat{key}} $|$ key} \repeat{form}}}
           \repeat{\list{\list{attribute-name ptnode \optional index-variable}
                         \repeat{value-form}}}
        [Macro]
\lispdoc defattributes \repeat{\list{\group{\list{\repeat{key}} $|$ key} \repeat{form}}}
           \repeat{\list{\list{{\tt values} \repeat{\list{attribute-name ptnode \optional index-variable}}}
                         \repeat{value-form}}}
        [Macro]
\end{lispdocs}

 This macro defines the method for computing the value of attribute {\em
attribute-name} for the the productions named by the keylist. If {\tt
values} is used on the left hand side of a clause, then the {\em
value-form} must return the same number of values.  

On the right hand sideof each clause of {\tt defattributes} specification,
the non-terminals of the productions are named and accessed in the same way
as in the body of a {\tt grammarbind}, with {\tt (ptnode {\em
nonterminal-name})} or {\tt (ptnode {\em nonterminal-name} {\em index})}.
The parent ptnode of the production may also be accessed using the {\tt
ptnode} macro.

The macro {\tt n-ary-n} is also available for use when the productions
named have a \separated-by key within them.

On the left hand side, the attribute value being computed can be named by
{\tt (attribute-name {\em nonterminal-name})} or {\tt (attribute-name {\em
nonterminal-name} {\em index})}.  We also allow the syntax {\tt ({\em
attribute-name} (ptnode {\em ptnode [index-variable]}))} for consistency
with the rhs.

 The key
\begin{verbatim}
   ($lhs -> $rhs-component $separated-by)
\end{verbatim}
is used to define the default production of an attribute (for an
example grammarspec ``{\tt ->}''). The value
computed here is used for an attribute when  there is no
{\tt defattributes} specification for that production.

\subsection{Attribute Example}

As an example, we will compute a synthesized attribute that counts the
number of leaves and binary internal nodes in the parse
tree for the example grammar given in section~\ref{grammar-example}.

\begin{verbatim}
(define-ptnode-attribute ptnode-node-count expression-language
  (:type synthesized)
  (:storage :memoized))

(defattributes (e -> e0 op e1)
  ((ptnode-node-count e)
   (+ 1 (ptnode-node-count (ptnode e0)) 
        (ptnode-node-count (ptnode e1)))))

(defattributes :number 
  ((ptnode-node-count :number)
   1))

(defattributes ($lhs -> $rhs-component $separated-by)
  ((ptnode-node-count $lhs)
   (loop for i from 0 below (n-ary-n)
         sum (ptnode-node-count (ptnode $rhs-component i)))))
\end{verbatim}

The synthesized attribute {\tt ptnode-node-count} is defined to have
memoized storage. Note that we have used the grammar abbreviation
defined in section~\ref{abbrev} to collectively define the attribute
computation for all the binary productions. Also, the default
attribute definition picks up any production not covered explicitly. 

\section{Graph Attributes (Unimplemented)}
\label{graph-attr}

[Note that this section proposes an unimplemented feature of DFCS.]

In this section, we will define a framework for declaring and computing
attributes for individual input and output ports of dataflow instructions.
In spirit, it is similar to the syntax directed attribute system for parse
trees described in the last section.

A {\em graph attribute}\index{graph attribute} is affiliated with one or
more graph representations (abstractions on dataflow-graphs) in a compiler
family. A graph attribute can be specified for either all the input ports
of an instruction, or all the output ports of an instruction, or both input
and output ports of an instruction. Once defined for a graph
representation, an attribute specification applies to every instruction in that
representation. We cannot specify attributes for subsets of instructions. 

Graph attributes are essentially property slots defined for the input
and/or output ports of an instruction instance. A new attribute slot is set
aside for each relevent port whenever a new instruction instance is
generated. There are general mechanisms to control the time of actual
allocation of an attribute slot. One may choose to always pre-allocate
storage for an attribute in each instruction instance generated, or one may
allocate storage on demand only for those instructions that actually access
the attribute. There are general mechanisms to initialize the attribute
slots once they are allocated. Of course, it is possible to access and
modify the attribute values residing at each port individually. We will
describe all these mechanisms in detail shortly.

Apart from providing some control over the allocation and initialization of
the attributes, the responsibility of computing, propagating, and
maintaining the graph attributes is left to the user. There is no general
mechanism to specify the automatic semantic computation of the attribute
value of a port using the graph connectivity existing around it. The user
must explicitly traverse the graph and set the attribute values. This
situation is likely to change in the future when some attribute grammar
style mechanism may be devised to allow automatic definition of attribute
values of a port with respect to the graph it belongs to. In the very
least, such a mechanism will have to deal with cyclic graphs and fixpoint
calculations for such graphs. 

\lispdoc define-dfg-attribute selector-name \clauses
        \repeatplus{\list{{\tt :affiliation} representation family}}
        \list{{\tt :type} type}
        \list{{\tt :storage} storage}
        \optgroup{{\tt :initial-element} initial-element \optgroup{initial-element-type}}
        [Macro]

Defines a dataflow graph attribute with the name {\em selector-name}.  The
name of the attribute must be of the form {\tt
{\it{}prefix}-port-{\it{}name}}. By convention, {\em prefix} is used to
specify the kind of graphs (the representation) this attribute belongs to;
{\em name} is the name of the attribute. For example, the {\em type}
attribute for each port of a program graph instruction may be named as {\tt
pgi-port-type}.  The name of the attribute is also used as a selector macro
for that attribute with an instruction, a port type ({\tt :input} or {\tt
:output}), and a port name as parameters\footnote{We should really have
just the instruction and the port name as the parameters. We have to look
into this more carefully.}. It can also be used with {\tt setf} to modify
the attribute value stored at a given port of a given instruction.

The {\tt :affiliation} clauses record the names of the graph representation
and the compiler family that this attribute belongs to. There should be at
least one affiliation clause.

The {\tt :type} clause specifies the type of ports this attribute is
applicable to. It must be one of {\tt :input}, {\tt :output}, or {\tt
:input-output}, which mean that the given attribute is defined for the input
ports only, the output ports only, or both input and output ports of an
instruction, respectively.

The {\tt :storage} clause specifies the time of allocation of storage for
the attribute slots on the ports. It must be one of {\tt :pre-allocated} or
{\tt :on-demand}. {\tt :pre-allocated} means that an array of slots will be
allocated whenever a new instance of an instruction is generated.  {\tt
:on-demand} means that the array of slots will be allocated only when a
selection or modification operation is attempted for that attribute on some
port of the given instruction instance. This saves considerable space if
the attribute is relevent for only some instructions, but may incur a
slight additional runtime overhead in testing whether the attribute array
has already been allocated or not. 

The {\tt :initial-element} clause, if present, specifies the initialization
mechanism of the attribute when allocated. If the clause is absent, each
attribute slot is initialized to the keyword symbol {\tt :uncomputed}. When
the clause is present, its interpretation depends on the {\em
initial-element-type}. This must be one of {\tt :static} or {\tt :dynamic}
and defaults to {\tt :static}. If the initial element type is
inferred to be {\tt :static}, then {\em initial-element} must be an 
immediate constant.  It is evaluated once at the time of attribute
definition and used to initialize the port array slots whenever they are allocated.
If the initial element type is specified to be {\tt :dynamic}, then the
initial element must name a function with one argument that will be called once at
the time of allocating an instruction instance with that instance as an
argument.  That function can fill up the slot array as desired.

\lispdoc initialize-dfg-attributes instruction representation family
[Function]

This initializes all the {\tt :pre-allocated} attributes of the given
instruction. Only the attributes belonging to the given representation and
compiler family are initialized. 

\lispdoc wire-attribute-from-port-to-port
          \list{from-attribute from-instruction from-port-type from-port}
          \list{to-attribute to-instruction to-port-type to-port}
        \optional wire-function
        [Macro]
This macro wires the value of the attribute {\em from-attribute} from the
specified source instruction port to the attribute slot for {\em
to-attribute} in the destination instruction port using the given wiring
function. The wiring function, if unspecifed, defaults to {\tt setf}.

\begin{lispdocs}
\lispdoc map-on-input-port-values function instruction attribute [Function]
\lispdoc map-on-output-port-values function instruction attribute [Function]
\end{lispdocs}
These functions map the given function on all the input/output port values of
the given instruction at the given attribute. The mapping function is called with 2
arguments, the value of the port slot and the port number. The results of
the mapping are not accumulated. 


\begin{lispdocs}
\lispdoc call-on-input-port-instruction function instruction input-port [Function]
\lispdoc map-on-output-port-instructions function instruction output-port [Function]
\end{lispdocs}

These functions apply the given function on all the instruction ports
connected to a given input/output port of a given instruction. There can be
only one source instruction wired to an input port, while there may be
several sink instructions wired from an output port. Therefore, the former
results in a single call over the source instruction, while the latter maps
the supplied function over all the sink instructions. In each case, the
function is called with 2 arguments, the connected instruction and the port
to which the connection is made (this is a port number rather than a name).

\lispdoc with-all-port-values-of-dataflow-graph
        \list{var dataflow-graph attribute} \body body [Macro]
This collects all the port values on all instructions of a dataflow graph
for the given attribute into an array accessible through {\em var}. The
array is available only within the scope of this macro and should not be
passed outside it. 

%%% \section{Semantic Analysis}
%%%
%%% \lispdoc define-semantic-function function \clauses 
%%%              mode default-method default-value consistency-predicate depth-bound cycle-action
%%%      [Macro]
%%%
%%% Define a semantic function (analyzer) named {\em function}. 
%%%
%%% {\em Mode} is one of {\tt :instruction}, {\tt :forward} or {\tt
%%% :backward}.  It specifies the type of analysis to perform.   If the mode
%%% is {\tt :instruction}, the semantic function will take an instruction as
%%% input, if it is {\tt :forward}, it will take an instruction-sink as
%%% input, and if it is {\tt :backward}, it will take an instruction-source
%%% as input.
%%%
%%% The {\em default-method} is the function to call when no specific method
%%% is defined for an opcode.
%%%
%%% The {\em default} is the value returned the first time you hit a cycle
%%% (for instance we're computing the strictness for a particular output of
%%% some instruction, and in the process we need to know the strictness for
%%% that same output, the default value will be used here (the first time
%%% around --- we will then iterate until the value returned for that output
%%% is the same as the previous value (testing using the
%%% CONSISTENCY-PREDICATE)).
%%%
%%%
%%% \lispdoc define-semantic-method function \group{opcode | \list{opcode port-name}} 
%%%                              \list{object-variable \rest other-args}
%%%                              \body body
%%%      [Macro]
%%%
%%%
