On Saturday 06 December 2008 01:00, Meikel Brandmeyer wrote:
> Hi Randall,
>
> Am 05.12.2008 um 23:54 schrieb Randall R Schulz:
> > However, I would like to be able to examine the tree in the
> > locality of the current traversal point through path or position
> > specifications. This approach is commonly used in describing
> > algorithms about logical formulas (which are inherently
> > tree-structured). If you're not familiar with the notion, these
> > paths / positions are directly analogous to file system path names,
> > except that one uses integers to label the arcs, said integers being
> > ordinals in the child sequence of a given node.
>
> I had the same problem some weeks ago and posted a half-baked
> solution to the list.
>
> http://groups.google.com/group/clojure/browse_thread/thread/bfd6539ec
>367a95b/51e28ee607790496?lnk=gst&q=goto-by#51e28ee607790496
OK. I reviewed that thread. It seems to me you had another posting, more
recent, in which you talked about some other aspect of tree processing.
I'll have to find and read that one, too.
> However the interest was very low. So I worked on the issue and
> the attached patch is what I came up with. For my purposes it works
> pretty well. Although I'm not sure it does what you need.
One thing I noticed from the discussion in mid October was an apparent
failure to distinguish arc labels from node labels. People don't often
think of it, but in the Unix file system, each element of a path name
is an _arc_ label, not a node label. Node labels are uninteresting
low-level identifiers (technically referred to as inode numbers).
Now the file system example is just one of many that arise in computing,
obviously, but you did use a file system example and it's something
concrete that everyone recognizes. But those details are not critical,
only the general fact that you must always remain clear about when you
care about node labels and when you care about arc labels.
So my recent question related to arc labels specifically in the form of
ordinals of child elements. In my logical formula case using this as an
example:
(forall ?X (and (P ?X) (Q ?X)))
there are these distinct paths / positions:
- epsilon (empty path, always refers to the root / entire formula)
- 0 => forall ?X
(the quantifier and the variable it binds are a single entity)
- 1 => (and ...)
- 1.0 => and
- 1.1 => (P ?X)
- 1.1.0 => P
- 1.1.1 => ?X
- 1.2 => (Q ?X)
- 1.2.0 => Q
- 1.2.1 => ?X
Now if I want to process an arbitrary formula looking for, say, either
conjunctions or disjunctions of atoms (in the terminology of
mathematical logic, (P ?X) is an "atomic formula" or "atom"), I need to
ensure, using traversal-point-relative path names, that all these are
true (assume for this example that "and" is strictly binary):
- epsilon => AND or OR
- 1 => instanceof ATOM
- 2 => instanceof ATOM
When all those obtain, I have the pattern I seek, wherever it may lie
within an arbitrary formula. In practice, there are often
non-structural criteria that require further examination of the
elements of the formula, but that's not a big deal in a functional
language where once can easily specify arbitrary functions to serve as
predicates.
I'll also suggest that navigation within a tree based solely on up /
down and left / right steps is probably going to make programming
tedious if its the only way one has to move about the target tree or to
access its contents. It's vaguely like having to use successor notation
for integers instead of radix-encoded (decimal, e.g.) numerals.
> Hope this helps.
>
> Sincerely
> Meikel
Randall Schulz
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Clojure" group.
To post to this group, send email to clojure@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
-~----------~----~----~----~------~----~------~--~---
