The state of the art for Arrow specs (clarifications and additions)

[Brian Rice]

Bill Tanksley wrote:
>Brian Rice wrote:
>> (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.

Well, in general, 'reifying' arrows usually means putting an arrow object
onto the heap so that a running computation can refer to it.  It's a basic
system service to be able to construct any member of any graph, so that
graphs are *the* means to defining objects constructively.

>> 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
>'reify'.
>
>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
>system.

In that case, every arrow besides the ones that the user adds are reified
arrows.  But it is true of every arrow that it has a "car" and "cdr".
That's why those graphs are part of the vm specification.

>(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
>cdr-graph?

Reification just allows you to have an object that the system rules allow.
In arrow, because the amount of objects allowed to exist by the rules is
unbounded, object allocation must be lazy.  So, 'reify' is really about
implementation, and not semantics.

>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
>something?

Yeah, that's pretty unclear.  Basically, we're talking about the agents
that manipulate system contexts.  For example, the user working through an
evaluator is an agent.  As such, the user can access system objects through
language constructs directly or indirectly via identifiers bound to them
according to a specified scheme.  Agents are those that traverse through
the graphs as described in (3).

>> (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.

Okay, this is a more regular definition.  Consider it changed.  (I had just
wanted to leverage familiarity with 'apply' from lisp in order to explain
what was being done.)

>> 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.

Okay.

>> 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.

Well, those are good examples of how to use this 'feature', but I want to
emphasize this "multiple worlds" idea because it's going to be a fairly
universal tool for working within Arrow.  Eventually, the system should be
able to give the user all sorts of new kinds of views on itself and its
parts, and very often this will (I predict) make good use of the "possible
worlds" idea, so bear with me.  However, your statement is true and
helpful, so I'll try to re-formulate it, emphasizing both aspects.

>> 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.

In retrospect, it seems to fit into what your previous suggestion described
(speculative evaluation, distributed calculation, and searching).  So, yes,
I'll try to make a section for "more advanced" users and include it there.

>> For example, if a meta-graph is treated as a function,
>
>New word alert!

Darn it, it's in the paper (just like "graph").  You just take the graph as
a set, and sketch the "is an element of" relation as another graph.  What
results locally is a central node representing the graph itself, with
arrows radiating from it to it's members.

>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
>arrows.

I hope the statement above clarifies it.  Most likely, I should include the
meta-graph generation ability as a system primitive that addresses graph
functionality, but it's not clear how it fits in with the whole design.
But yes you can consider the "meta-graph" of a graph to be the system's way
of allowing you to keep track of the arrows in a graph.

Actually, now that I think of it, the meta-graph generation construct, if
reversed so that instead of making a graph out of a collection of arrows,
could be a fairly natural "arrow-like" construct.  I will have to consider
this a little more before deciding.

>> 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?).
>
>Okay.
>
>> 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.

Yes, it'll take a while to explain why I claim this.

For now, just consider the implementation of a meta-circular interpreter
for a declarative language like Prolog or Mercury, and you'll see how
evaluation strategy can be worked with by declarative constructs themselves.

>> 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).

Yes, but I am not discussing tuples or sequences.  Tuples in the arrow
system would be represented by single nodes (arrows), just as in category
theory.  This is a different idea entirely, since I am not inherently
assuming any structure whatsoever between the results of this graph's
application.  You _can_ place the results within a tuple, but I don't have
a good construct yet for collecting the results.

>-Billy

	-Brian