12,080
edits
Changes
Directory:Jon Awbrey/Papers/Inquiry Driven Systems (view source)
Revision as of 19:31, 20 January 2009
, 19:31, 20 January 2009→1.3.11. The Cactus Patch: + next segment
There is a measure of ambiguity that remains in this formulation, but it is the best that I can do in the present informal context.
There is a measure of ambiguity that remains in this formulation, but it is the best that I can do in the present informal context.
=====1.3.11.4. The Cactus Language : Mechanics=====
{| align="center" cellpadding="0" cellspacing="0" width="90%"
|
<p>We are only now beginning to see how this works. Clearly one of the mechanisms for picking a reality is the sociohistorical sense of what is important — which research program, with all its particularity of knowledge, seems most fundamental, most productive, most penetrating. The very judgments which make us push narrowly forward simultaneously make us forget how little we know. And when we look back at history, where the lesson is plain to find, we often fail to imagine ourselves in a parallel situation. We ascribe the differences in world view to error, rather than to unexamined but consistent and internally justified choice.</p>
|-
| align="right" | — Herbert J. Bernstein, "Idols of Modern Science", [HJB, 38]
|}
In this Subsection, I discuss the ''mechanics'' of parsing the cactus language into the corresponding class of computational data structures. This provides each sentence of the language with a translation into a computational form that articulates its syntactic structure and prepares it for automated modes of processing and evaluation. For this purpose, it is necessary to describe the target data structures at a fairly high level of abstraction only, ignoring the details of address pointers and record structures and leaving the more operational aspects of implementation to the imagination of prospective programmers. In this way, I can put off to another stage of elaboration and refinement the description of the program that constructs these pointers and operates on these graph-theoretic data structures.
The structure of a ''painted cactus'', insofar as it presents itself to the visual imagination, can be described as follows. The overall structure, as given by its underlying graph, falls within the species of graph that is commonly known as a ''rooted cactus'', and the only novel feature that it adds to this is that each of its nodes can be ''painted'' with a finite sequence of ''paints'', chosen from a ''palette'' that is given by the parametric set <math>\{ \, ^{\backprime\backprime} \operatorname{~} ^{\prime\prime} \, \} \cup \mathfrak{P} = \{ m_1 \} \cup \{ p_1, \ldots, p_k \}.</math>
It is conceivable, from a purely graph-theoretical point of view, to have a class of cacti that are painted but not rooted, and so it is frequently necessary, for the sake of precision, to more exactly pinpoint the target species of graphical structure as a ''painted and rooted cactus'' (PARC).
A painted cactus, as a rooted graph, has a distinguished node that is called its ''root''. By starting from the root and working recursively, the rest of its structure can be described in the following fashion.
Each ''node'' of a PARC consists of a graphical ''point'' or ''vertex'' plus a finite sequence of ''attachments'', described in relative terms as the attachments ''at'' or ''to'' that node. An empty sequence of attachments defines the ''empty node''. Otherwise, each attachment is one of three kinds: a blank, a paint, or a type of PARC that is called a ''lobe''.
Each ''lobe'' of a PARC consists of a directed graphical ''cycle'' plus a finite sequence of ''accoutrements'', described in relative terms as the accoutrements ''of'' or ''on'' that lobe. Recalling the circumstance that every lobe that comes under consideration comes already attached to a particular node, exactly one vertex of the corresponding cycle is the vertex that comes from that very node. The remaining vertices of the cycle have their definitions filled out according to the accoutrements of the lobe in question. An empty sequence of accoutrements is taken to be tantamount to a sequence that contains a single empty node as its unique accoutrement, and either one of these ways of approaching it can be regarded as defining a graphical structure that is called a ''needle'' or a ''terminal edge''. Otherwise, each accoutrement of a lobe is itself an arbitrary PARC.
Although this definition of a lobe in terms of its intrinsic structural components is logically sufficient, it is also useful to characterize the structure of a lobe in comparative terms, that is, to view the structure that typifies a lobe in relation to the structures of other PARC's and to mark the inclusion of this special type within the general run of PARC's. This approach to the question of types results in a form of description that appears to be a bit more analytic, at least, in mnemonic or prima facie terms, if not ultimately more revealing. Working in this vein, a ''lobe'' can be characterized as a special type of PARC that is called an ''unpainted root plant'' (UR-plant).
An ''UR-plant'' is a PARC of a simpler sort, at least, with respect to the recursive ordering of structures that is being followed here. As a type, it is defined by the presence of two properties, that of being ''planted'' and that of having an ''unpainted root''. These are defined as follows:
# A PARC is ''planted'' if its list of attachments has just one PARC.
# A PARC is ''UR'' if its list of attachments has no blanks or paints.
In short, an UR-planted PARC has a single PARC as its only attachment, and since this attachment is prevented from being a blank or a paint, the single attachment at its root has to be another sort of structure, that which we call a ''lobe''.
To express the description of a PARC in terms of its nodes, each node can be specified in the fashion of a functional expression, letting a citation of the generic function name "<math>\operatorname{Node}</math>" be followed by a list of arguments that enumerates the attachments of the node in question, and letting a citation of the generic function name "<math>\operatorname{Lobe}</math>" be followed by a list of arguments that details the accoutrements of the lobe in question. Thus, one can write expressions of the following forms:
{| align="center" cellpadding="4" width="90%"
| <math>1.\!</math>
| <math>\operatorname{Node}^0</math>
| <math>=\!</math>
| <math>\operatorname{Node}()</math>
|-
|
|
| <math>=\!</math>
| a node with no attachments.
|-
|
| <math>\operatorname{Node}_{j=1}^k C_j</math>
| <math>=\!</math>
| <math>\operatorname{Node} (C_1, \ldots, C_k)</math>
|-
|
|
| <math>=\!</math>
| a node with the attachments <math>C_1, \ldots, C_k.</math>
|-
| <math>2.\!</math>
| <math>\operatorname{Lobe}^0</math>
| <math>=\!</math>
| <math>\operatorname{Lobe}()</math>
|-
|
|
| <math>=\!</math>
| a lobe with no accoutrements.
|-
|
| <math>\operatorname{Lobe}_{j=1}^k C_j</math>
| <math>=\!</math>
| <math>\operatorname{Lobe} (C_1, \ldots, C_k)</math>
|-
|
|
| <math>=\!</math>
| a lobe with the accoutrements <math>C_1, \ldots, C_k.</math>
|}
Working from a structural description of the cactus language, or any suitable formal grammar for <math>\mathfrak{C} (\mathfrak{P}),</math> it is possible to give a recursive definition of the function called <math>\operatorname{Parse}</math> that maps each sentence in <math>\operatorname{PARCE} (\mathfrak{P})</math> to the corresponding graph in <math>\operatorname{PARC} (\mathfrak{P}).</math> One way to do this proceeds as follows:
<ol style="list-style-type:decimal">
<li>The parse of the concatenation <math>\operatorname{Conc}_{j=1}^k</math> of the <math>k\!</math> sentences <math>(s_j)_{j=1}^k</math> is defined recursively as follows:</li>
<ol style="list-style-type:lower-alpha">
<li><math>\operatorname{Parse} (\operatorname{Conc}^0) ~=~ \operatorname{Node}^0.</math>
<li>
<p>For <math>k > 0,\!</math></p>
<p><math>\operatorname{Parse} (\operatorname{Conc}_{j=1}^k s_j) ~=~ \operatorname{Node}_{j=1}^k \operatorname{Parse} (s_j).</math></p></li>
</ol>
<li>The parse of the surcatenation <math>\operatorname{Surc}_{j=1}^k</math> of the <math>k\!</math> sentences <math>(s_j)_{j=1}^k</math> is defined recursively as follows:</li>
<ol style="list-style-type:lower-alpha">
<li><math>\operatorname{Parse} (\operatorname{Surc}^0) ~=~ \operatorname{Lobe}^0.</math>
<li>
<p>For <math>k > 0,\!</math></p>
<p><math>\operatorname{Parse} (\operatorname{Surc}_{j=1}^k s_j) ~=~ \operatorname{Lobe}_{j=1}^k \operatorname{Parse} (s_j).</math></p></li>
</ol></ol>
For ease of reference, Table 13 summarizes the mechanics of these parsing rules.
<br>
{| align="center" border="1" cellpadding="8" cellspacing="0" style="text-align:center; width:90%"
|+ '''Table 13. Algorithmic Translation Rules'''
|- style="background:whitesmoke"
|
{| align="center" border="0" cellpadding="8" cellspacing="0" style="background:whitesmoke; width:100%"
| width="33%" | <math>\text{Sentence in PARCE}\!</math>
| align="center" | <math>\xrightarrow{\operatorname{Parse}}</math>
| width="33%" | <math>\text{Graph in PARC}\!</math>
|}
|-
|
{| align="center" border="0" cellpadding="8" cellspacing="0" width="100%"
| width="33%" | <math>\operatorname{Conc}^0</math>
| align="center" | <math>\xrightarrow{\operatorname{Parse}}</math>
| width="33%" | <math>\operatorname{Node}^0</math>
|-
| width="33%" | <math>\operatorname{Conc}_{j=1}^k s_j</math>
| align="center" | <math>\xrightarrow{\operatorname{Parse}}</math>
| width="33%" | <math>\operatorname{Node}_{j=1}^k \operatorname{Parse} (s_j)</math>
|}
|-
|
{| align="center" border="0" cellpadding="8" cellspacing="0" width="100%"
| width="33%" | <math>\operatorname{Surc}^0</math>
| align="center" | <math>\xrightarrow{\operatorname{Parse}}</math>
| width="33%" | <math>\operatorname{Lobe}^0</math>
|-
| width="33%" | <math>\operatorname{Surc}_{j=1}^k s_j</math>
| align="center" | <math>\xrightarrow{\operatorname{Parse}}</math>
| width="33%" | <math>\operatorname{Lobe}_{j=1}^k \operatorname{Parse} (s_j)</math>
|}
|}
<br>
A ''substructure'' of a PARC is defined recursively as follows. Starting at the root node of the cactus <math>C,\!</math> any attachment is a substructure of <math>C.\!</math> If a substructure is a blank or a paint, then it constitutes a minimal substructure, meaning that no further substructures of <math>C\!</math> arise from it. If a substructure is a lobe, then each one of its accoutrements is also a substructure of <math>C,\!</math> and has to be examined for further substructures.
The concept of substructure can be used to define varieties of deletion and erasure operations that respect the structure of the abstract graph. For the purposes of this depiction, a blank symbol <math>^{\backprime\backprime} ~ ^{\prime\prime}</math> is treated as a ''primer'', in other words, as a ''clear paint'' or a ''neutral tint''. In effect, one is letting <math>m_1 = p_0.\!</math> In this frame of discussion, it is useful to make the following distinction:
# To ''delete'' a substructure is to replace it with an empty node, in effect, to reduce the whole structure to a trivial point.
# To ''erase'' a substructure is to replace it with a blank symbol, in effect, to paint it out of the picture or to overwrite it.
A ''bare PARC'', loosely referred to as a ''bare cactus'', is a PARC on the empty palette <math>\mathfrak{P} = \varnothing.</math> In other veins, a bare cactus can be described in several different ways, depending on how the form arises in practice.
<ol style="list-style-type:decimal">
<li>Leaning on the definition of a bare PARCE, a bare PARC can be described as the kind of a parse graph that results from parsing a bare cactus expression, in other words, as the kind of a graph that issues from the requirements of processing a sentence of the bare cactus language <math>\mathfrak{C}^0 = \operatorname{PARCE}^0.</math></li>
<li>To express it more in its own terms, a bare PARC can be defined by tracing the recursive definition of a generic PARC, but then by detaching an independent form of description from the source of that analogy. The method is sufficiently sketched as follows:</li>
<ol style="list-style-type:lower-latin">
<li>A ''bare PARC'' is a PARC whose attachments are limited to blanks and ''bare lobes''.</li>
<li>A ''bare lobe'' is a lobe whose accoutrements are limited to bare PARC's.</li>
</ol>
<li>In practice, a bare cactus is usually encountered in the process of analyzing or handling an arbitrary PARC, the circumstances of which frequently call for deleting or erasing all of its paints. In particular, this generally makes it easier to observe the various properties of its underlying graphical structure.</li>
</ol>
==References==
==References==