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

[Brian Rice]

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.



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

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).  The problem arises
that you haven't obtained the actual arrows referenced, but arrows
representing the references.

(3) Treating any graph as a function and applying it to an arrow.  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.  This results in
information transitions which can be independent of each other, as an
exploration of possible worlds.  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.

For example, if a meta-graph is treated as a function, 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.

The informal description amounts to:
	For each arrow X and graph G, return all arrows Y for which there is an
arrow in G whose car is X and whose cdr is Y.

The word "return" in the axiom is hardly precise from within our current
idea of the system.  This suggests that the arrow system must have a far
different model of functions than we now employ for computational systems.
There is another bone of contention that this statement treats the graph
"is an element of" relation as defined system-wide in a consistent way,
which seems too stringent a requirement.  This suggests taking another
approach (which I am currently working on).

The idea that a function can return multiple values is of course
inconsistent with the notion of a function.  Perhaps the best thing to do
in this situation is to have the system diverge into "possible worlds"
where in each of the worlds the function has returned a particular value,
and can proceed to analyze it as planned.  This suggests that the
multiply-defined function actually produces a search space or a space of
concurrent computations.  This notion needs much refining, since we have no
idea how to gather the information from those worlds into a collection.
Perhaps modelling the world-formation as a particular kind restriction on
the graph that was called as a function would allow access to the results.

Hmm.  It's a good time for an example:
	Let's say that we have the graph of natural numbers as a plain old set.
We would invoke the meta-graph in order to get those numbers.  For
instance, to find the successor of 0 from a logical perspective, we would
have to say something like: "for all natural numbers, x is the successor of
0 iff x=succ(0)."  (Yes, this example is purposefully trivial).  Anyway, we
have to proceed by applying the set-membership graph to the arrow at the
head of the natural numbers graph, which results in an infinite number of
contexts.  To these contexts, we apply the succ-graph and compare the
result(s) to x.  Ideally, the implementation would be able to determine the
execution strategy that avoids the inherently impossible task of actually
searching for the number whose successor is x.  The *point* is that we can
express such an action in arrow-level abstract terms, and leave all the
implementation details elsewhere.

A text form of the query just performed would read something like this
(using Lisp notation):
	(return-identity 0
	             (apply (apply invert-graph succ-graph)
	                    (apply set-membership natural-numbers-graph)))

(Note that invert-graph reverses a graph's arrows and we are comparing all
of the results of the inverse successor function with 0.  Return-identity
is an ill-defined idea for returning its argument if it is an identity
arrow (i.e. it has equal references), but it's unclear what behavior it
should have for negative results.  Also, the process of dealing with these
results is unspecified.  For now, consider this to return a graph of the
results which just happens in this case to contain only one arrow.)

	Note1: In combination with the car and cdr graphs, this can be used to
obtain the arrows referred to by a given arrow indirectly, which is what
using formal languages is all about: transforming expressions into values.
Now, we have made the car- and cdr-graphs into fundamental system functions
which are simple to implement computationally.  These tools allow us to
obtain the arrows that argument arrows actually refer to.

	Note2: All of this says nothing overtly about how to obtain arrows that
refer to the target arrow, which means that meta-information is so far
inaccessible.  Perhaps a graph which relates graphs to their meta-graphs
would help in this regard (Sounds like a good construct, perhaps?).  This
would, given the previous constructs, access to the basic meta-information
of the arrow.  However, it doesn't give the system a way to get at the
other meta-arrows which are of much greater interest, since they are the
ones which distinguish the semantic content of arrow.

	Note3: Now, something important that remains to construct is the system
for specifying graphs, which seems to me to naturally be a system for
taking certain graph constructs (ones that I've already specified plus a
number of ones yet to be specified) and modifying them incrementally using
cleanly-defined arrow functions to produce graphs of all sorts.

Also, the appropriate analogue of quantification is still missing, although
a simple solution seems to be to predicate a graph that specifies a type,
and infering from an arrow's membership in the graph that other statements
apply to it, a la formal logic.  This could be accomplished by annotating
the inferences over the function that generates the type.

An analogue of existential quantification relates to a method for making a
graph-as-function more determinate.  The basic action of creating a new
graph from the old via adding more constraints to the specification of the
graph would provide behavior which would tend toward deterministic
functions rather than the odd behavior of general-purpose graphs when
treated as functions.  Basically, this amounts to 'paring down' the arrow
population of a graph until it is equivalent to the graph of a function.
Performing a _random_ restriction of the graph to a function's graph would
provide a type of 'random introduction' of information that seems a lot
like existential quantification.  However, it's still not a definite answer.

I will post updates to this spec incrementally.

Comments are, of course, highly welcome.
	-Brian