The state of the art for Arrow specs

Brian Rice water@tscnet.com
Thu, 28 Oct 1999 18:46:20 -0700


At 04:14 PM 10/28/99 +0200, Laurent Martelli wrote:
>>>>>> "Brian" == Brian Rice <water@tscnet.com> writes:
>
>  Brian> Comments are, of course, highly welcome.
>
>Thanks for the clarification. I now understand better what Arrow is
>all about. 
>
>Tell me if I'm wrong : a graph is a set of arrow, whose car is a
>possible input value for a function, and whose cdr is the output value
>for that input. 
>
>Right ?

[Note in retrospect to writing this material.  I misread your question, so
the information below answers the wrong question, though it is still valid
information for those interested.  The real answer is further below.]

Well, a graph is indeed a set of arrows, and in general nothing more than
that.  I use the term 'degenerate graphs' for those where arrows referenced
by other arrows in the graph are also in the graph.  I've considered the
term 'horizontal graph' to refer to ordinary graphs where the arrows
referred to may be thought of as nodes from within the graph context.  In
contrast, 'vertical graphs' would essentially contain recursive List
cons-structures (singular or multiple ones).
 
Now, the car and cdr of a graph exist because the graph's meta-graph
contains a representation of the graph as an arrow, linked to its member
arrows by the "is an element of" relation.  The meaning of the car and cdr
is something that I haven't looked into at all, so I consider it a 'node':
that is, an arrow whose references I disregard.  My policy with this is to
create a 'ground' arrow for the system and to 'root' all nodes' references
to the ground, which makes the arrow essentially meaningless.  (Note: if
anyone here is familiar with lattice theory, they would be highly
interested to find out some of my more recent results on this model of
graphs and their meta-graphs.  I will explain these results soon.)

[The following is not my idea of the ideal arrow picture, but instead
merely an ad hoc idea.]
Now, when I say that I want to use an arrow, I mean that I want to refer to
it within computational and declarative contexts to specify information
about it.  So, I link the graph's head arrow to other arrows for
declarations and (as in the example) function applications, which allow the
system to use the graph as both a construct and a subject matter.

So, applying a graph G to an arrow X would (according to this incomplete
model) consist of an arrow {G, X} within our special function -application
construct.  This could be used a la higher-order functional programming as
an argument to a further function-application.

Oops!

Darn it, I misread your question.  What you want to know is basically how a
graph can be read as a function.  Well, the answer is indeed as you
suggest: a function (as represented by a graph) consists of arrows linking
input value as car with output value as cdr of the arrow.  A function's
graph would only have one arrow per unique input value.  However, a
generalization to all graphs yields the state-machine notion where the
arrows denote possible information transitions.  The usual horizontal graph
corresponds to the usual state-machine notion, while degenerate and
vertical graphs are horses of a different color.

For those familiar with mathematical graph theory, multi-graphs (graphs
where multiple arrows may have the same endpoints) are equivalent to graphs
for the purposes described here.  I could go into the theory of all of this
for many pages, so I have a lot of intellectual resources from which to
develop the theory now.

>Laurent Martelli
>martelli@iie.cnam.fr

I hope this helps.
	-Brian