The state of the art for Arrow specs (clarifications and addi tions)
Sat, 30 Oct 1999 12:21:00 -0700

> From: Brian Rice []
> Subject: Re: The state of the art for Arrow specs (clarifications and
> additions)

> Well, the following should help clear up some natural 
> confusion which I did
> not anticipate (flaming is welcome).  Notice that the terms should be
> clearer to read, and the explanations more literally spelled out.

I like this.  Thank you.  I have a few more q's.  Sorry about the lousy
formatting, Outlook does that to you :(.

> (1,2) car-graph and cdr-graph: these are two graphs which 
> contain all of
> the reified references that all arrows in the system contain. 
>  Note that
> this is a recursive definition, since arrows in car-graph and 
> cdr-graph can
> have their references reified as well.  This allows arbitrary 
> reification
> of references.

Okay, this makes sense.  May I assume that 'reified' means 'having a car and
cdr which was inserted into the appropriate graphs'?  Or does it have a
definition which is external to this little essay?  If so, it might reduce
confusion to link to that definition, or at least mention the fact.

> The statements formalizing car-graph and cdr-graph amount to:
> 	For each arrow X, (1) there is an arrow in the 
> car-graph whose car is X
> and whose cdr is the arrow referred to by X's car slot, and 
> (2) there is an
> arrow in the cdr-graph whose car is X and whose cdr is the 
> arrow referred
> to by X's cdr slot.

> So, reifying the references of X produces {X, car X} (an element of
> car-graph) and {X, cdr X} (an element of cdr-graph).

Ah, excellent.  This answers my question above re: the definition of

May I attempt to rephrase your initial paragraph?  Please warn me if I've
simply misunderstood, and if I do well feel free to take my words.

(0) reified arrow: this type of arrow can be manipulated in several ways by
the system.  In particular, it has a "car" and "cdr" defined in terms of the

(1,2) car-graph and cdr-graph: these two graphs manage all of the "car"s and
"cdr"s for reified arrows.  car-graph points from each reified arrow to all
cars belonging to it; cdr-graph does the same for cdrs.  Note that since
both are graphs, both are composed of arrows; therefore, either or both may
contain reified arrows, producing a recursive structure.

Oh, a question: is there any special reason why an arrow may only be reified
or unreified?  What if it was added to the car-graph but not to the

Back to the essay:

> So, reifying the references of X produces {X, car X} (an element of
> car-graph) and {X, cdr X} (an element of cdr-graph).

> The 
> problem arises
> that you haven't obtained the actual arrows referenced, but arrows
> representing the references.

I'm not clear about this.  Who has obtained what?  I see that one subgraph
was added to each of the reification graphs, and those subgraphs point from
X (the original arrow) to X's referents as appropriate.  So who has obtained

> (3) Treating any graph as a function and applying it to an 
> arrow.

Both of the previous terms were nouns.  This one is a sentance, and I
honestly couldn't understand the list the first time I read through it
simply because of this irregularity.  Permit me again to rephrase:

(3) Function:  Any graph can be treated as a function which accepts an arrow
as input and possibly produces arrows as output.

> This
> relates to the representation of a function as a graph, which involves
> drawing arrows from domain-value to range-value.  For an 
> actual function,
> there is only one arrow in the graph representation whose 
> input (car) is
> unique to that arrow, ensuring that a function returns at 
> most one value.
> Generalizing function-application to relations and even full 
> graphs allows
> a much more general system of obtaining information.

Clear.  I like it.

> This results in
> information transitions which can be independent of each other, as an
> exploration of possible worlds.

This is interesting in and of itself, but doesn't bear any direct,
recognizable relation to what you've said before.  It's useful information,
but it gets in the way of learning.  May I again attempt a rephrase:

This generalization allows simple access to many interesting abilities and
descriptions of abilities, such as speculative evaluation, distributed
calculation, or searches.

> Such an idea relates to performing
> concurrent independent calculations, even ones which are 
> distributed, or
> describing the abstract semantics of a search without the procedural
> quality which only quallifies the implementation.

Sorry, I jumped ahead.  This might have some useful information, but if I
were writing this (a task for which I'm clearly unqualified, so take with a
grain of salt) I would just link to the other interesting info, or just hold
it back for an advanced user.

> For example, if a meta-graph is treated as a function,

New word alert!

Are the car-graph and cdr-graphs meta-graphs?  If so, then please use that
word in their definition.  Are any other graphs considered 'meta'?  If so,
what makes them 'meta'?  It better not be because they point to subgraphs,
because every graph points to subgraphs.

I suspect that when you say "meta-graph" you mean "system graph", that is,
one of the graphs which is used by the system itself to keep track of the

> then 
> evaluating the
> graph node results in as many concurrent computations as 
> there are arrows
> in the graph.  This suggests a function which returns a set 
> of multiple
> values, or alternately a system for providing paths of 
> independent travel
> for the system's contexts (which are perhaps agents?).


> Note that this
> mechanism for modelling multiple computations is 
> implementation-independent
> in a way that no current non-declarative programming language 
> can cleanly
> handle.  But then, even the declarative languages usually 
> have a limited
> implementation mechanism for this concurrent evaluation style.

I'm not sure that I see this.  But keep iit in there anyhow; you have to
make some claims for your system, or the person tyring to learn it will have
no motivation to keep reading.

> The idea that a function can return multiple values is of course
> inconsistent with the notion of a function.  

Not really.  Functions can formally return tuples, or even infinite
sequences (an infinite sequence can formally model a function which changes
over time).

...lots of okay stuff clipped for lack of time...

> Comments are, of course, highly welcome.

Okay.  :)

> 	-Brian