Dear lispers,
Below is a message I wrote and posted to the mathematica news group.
(comp.soft-sys.math.mathematica) (moderated) I think lispers may be
interested too. In particular, I'm interested to hear lisper's comments. (I
don't know for sure, but I think lisp languages does not rely on expression
structure as much as Mathematica, even though both language uses tree
syntax)
------
This is the 5th weekly posting of a series of expositions on Mathematica
expressions, Trees, and Indexes.
----- ----- -----
Introduction:
It's fairly easy to see how Mathematica expression are trees, and how each
atom has an index. This is so until the heads of expressions are expression
themselves. For example, the structure of the following expression is
difficult to understand:
0[0,0][][0[0,0][],0[0,0][]]
It is however a legal expression, and such forms could be exploited in
applications (one simple example is the Derivative function).
In this post, I hope to give a clear exposition of the isomorphism between
Mathematica expressions, trees, and index sets. Once we understand the
isomorphism of expressions and index set with atoms, we can explain the
behavior of any structural manipulating functions in terms of how the
function effects the indexes and atoms. The structural manipulating
functions I had in mind are those covered in The Mma Book 2.1 to 2.2. We'll
just call them tree functions for abbreviaton.
We will write functions that convert expression to index set and vice versa.
To simulate tree functions (e.g. Level, Through, Flatten), we can first
convert their main arguments to index set, manipulate the index set, then
convert it back into an expression. This approach exposes functions'
behaviors, and it shows how they can be implemented in any language. (Our
focus is not on implementation, but exploration on useful structural
transformations of trees, as exemplified in Mathematica's Outer, Distribute,
Transpose...etc.)
----- ----- -----
Trees and Index set:
What is a tree? (I don't have a formal definition handy but we don't need
one here.) Basically: A tree is an abstract idea of a structure. Starting
with a node, called root. A node may have other nodes connected to it,
called its children. Nodes that have no children are called leaves. If a
node is not a leave, then it is a nonleave, or called a branching node.
(terminology used here may differ from convention) In summary, a tree is a
set of nodes, each has a parent/child relation with some other nodes, and by
definition there is one node called root, which is the only node without
parent.
We can lable the nodes systematically. The root node will be labeled {}
(empty braces). If it has two children, then they are labeled {1} and {2}.
The children of {1} will be labeled {1,1}, {1,2} and so on. Similarly,
children of {2} are {2,1},{2,2}...etc. In general, we add a digit in every
new generation, counting children starting at 1. In this way, each node has
a name, called its index. The number of digits in an index indicates its
"generation ordinal" or Level. The root node is the generation 0, or Level
0, because its index does not contain any digits.
Now notice that we can also use alphabets instead of numbers, or, we can
start counting with 0 instead of 1. We will stick to the indexing system
that starts counting with 0. This reason for this choice will be apparant
later.
A set of indexes defines a tree. The set that contain all indexes of a given
tree minus the root index {} will be called the _complete index set_ of that
tree. _Leaves index set_ is the set of indexes of all leaves of the tree.
Similarly for _Nonleaves index set_ (minus the root {}). The union of leaves
and nonleaves is the complete index set. Their intersection is empty.
Examples:
Here's the complete index set of a tree:
{{0},{1},{2},{3},{0,0},{2,0},{2,1},{3,0},{3,1},{3,1,0}}
its LeavesIndexSet is
{{1},{0,0},{2,0},{2,1},{3,0},{3,1,0}}
its NonleavesIndexSet is
{{0},{2},{3},{3,1}}
The MinimumIndexSet is
{{0,0},{2,1},{3,1,0}}
(MinimumIndexSet is the a subset of complete index set: its elements are
indexes that can not be inferred from others. Discussed in a previous
posting)
A given list of indexes may not be a complete index set, but a complete
index set can always be inferred. For example, given {{3},{1},{2,2}}, the
{3} implies {2},{1},{0}, and {2,2} implies {2,1},{2,0},{2}. So the complete
index set is {{0},{1},{2},{3},{2,0},{2,1},{2,2}}. A list of index implies a
complete index set, which in turn defines a tree. Conversely, any tree
corresponds to a unique complete index set. Now we have the isomorphism
between trees and (complete) index sets.
----- ----- -----
Lisp Expresions:
Now let's look at how a tree shape can be defined as a string (we'll call
such string _expression_). The simplest way is using nested parenthesis.
We'll use 0 as the atomic object. Starting with root we have 0, which
correpsonds to the index set {{}}.
First, notice that there are two types of tree growth:
(1) birth of a new generation, e.g. {{0},{1}}-->{{0},{1},{1,0}}.
(2) birth of a sibling, e.g. {{0},{1}}-->{{0},{1},{2}}.
To grow a new generation, we add a pair of parenthesis. So, we have 0 -->
(0), corresponding to {{}}-->{{},{0}}. To grow a sibling, we append a 0. We
have (0)-->(0 0), corresponding to {{},{0}}-->{{},{0},{1}}. By this growing
process, all trees have a corresponding expression, and vice versa. If you
are a purest, you can use a pair of empty parenthesis as your atom, so the
whole string consists of only parenthesis.
Example: Here's a growth history of the tree
{{0},{1},{2},{3},{0,0},{2,0},{2,1},{3,0},{3,1},{3,1,0}}, represented by both
expressons and index sets.
{
0,
(0),
(0 0),
(0 0 0),
(0 0 0 0),
((0) 0 0 0),
((0) 0 (0) 0),
((0) 0 (0 0) 0),
((0) 0 (0 0) (0)),
((0) 0 (0 0) (0 0)),
((0) 0 (0 0) (0 (0)))
}
{
{},
{{0}},
{{0},{1}},
{{0},{1},{2}},
{{0},{1},{2},{3}},
{{0,0},{0},{1},{2},{3}},
{{0,0},{0},{1},{2,0},{2},{3}},
{{0,0},{0},{1},{2,0},{2,1},{2},{3}},
{{0,0},{0},{1},{2,0},{2,1},{2},{3,0},{3}},
{{0,0},{0},{1},{2,0},{2,1},{2},{3,0},{3,1},{3}},
{{0,0},{0},{1},{2,0},{2,1},{2},{3,0},{3,1,0},{3,1},{3}}
}
(the empty braces are omitted in index sets. This is so because otherwise an
index set ALWAYS contains the {}.)
We'll call the above the Lisp expression system, and it is not the only way
to represent a tree shape with strings. In the following system, we'll use
brackets instead of parenthesis for visual distinction from the lisp system,
and we'll call it the Mathematica expression system.
----- ----- -----
Mathematica Expresions:
In the Mathematica expression system:
(1) As before, we start with an atom 0.
(2) To grow a new generation, we add a pair of brackets after its parent.
So, we have 0 --> 0[], corresponding to {{}}-->{{},{0}}.
(3) To grow a sibling, we append a 0 inside the []. We have 0[]-->0[0],
corresponding to {{},{0}}-->{{},{0},{1}}.
Here is the growth history of the above tree in mma expression:
{
0,
0[],
0[0],
0[0,0],
0[0,0,0],
0[][0,0,0],
0[][0,0[],0],
0[][0,0[0],0],
0[][0,0[0],0[]],
0[][0,0[0],0[0]],
0[][0,0[0],0[0[]]]
}
Commas are used instead of spaces for separaters.
----- ----- -----
Lisp vs. Mathematica expression:
Lisp expression system and mma expression system are isomorphic, but
expression systems are not isomorphic to trees. There is a one-to-one
mapping between the set of all expressions and the set of all trees, but
there is NOT a one-to-one mapping between strings in an expression and nodes
of its corresponding tree. For example, a tree is a set but an expression is
not a set. However, there is a one-to-one mapping between the atoms in an
expression to leaves of its corresponding tree. For example, consider the
mma expression 1[][2,3[4],5[6[]]]. The atoms correpsonds to the leaves index
set {{1},{0,0},{2,0},{2,1},{3,0},{3,1,0}}. This can be seen using the
following construct
expr=1[][2,3[4],5[6[]]];
(#->Part[expr,········@@#])&·@Position[expr,_,{-1}]//Sort
returns
{{1} -> 2, {0, 0} -> 1, {2, 0} -> 3, {2, 1} -> 4,
{3, 0} -> 5, {3, 1, 0} -> 6}
In summary, an expressions (lisp or mma) corresponds to tree shapes, and the
atoms of an expresion corresponds to the leaves of its corresponding tree.
In lisp form, atoms' indexes are visually apparant. For example, in ((1) 2
(3 4) (5 (6))), 1 must be {0,0}, 2 is {1}, 3 and 4 are {2,0} and {2,1}, 5 is
{3,1}, and 6 is {3,1,0}. In the mma counterpart 1[][2,3[4],5[6[]]], it is
less obvious what is the index of 1. In general, if the first child of any
node has children (i.e. if we have non-atomic heads), then it's difficult to
"see" its structure. Here is a comparison table:
lisp mma
-------------------------
0 0 atom
(0) 0[] appending (sibling birth)
(0 0) 0[0]
(0 0 0) 0[0 0 0]
((0)) 0[][] nesting (new generation birth)
(((0))) 0[][][]
In the lisp form, any pair of matching parenthesis (...) encloses a
subexpression. (subexpression is a continuous partial string that is itself
an expression). In the mma counterpart, the form of subexpression is
atom[...][...]...[...]. For example, f[][] is a subexpression corresponding
to lisp's ((f)).
The structure of lisp expression is more visually apparent. However, mma
expression form has its advantages too. For example, sin(x) is more familiar
then (sin x). Similarly of f(f(x)) vs. (f (f x)). But I believe there is a
more important advantage which we'll discuss below.
----- ----- -----
Heads->True/False Intepretations
It is desirable to have an expression system such that atoms corresponds to
all nodes of a tree, not just the leaves. This is inherently "impossible",
but we can "fake it" by intepreting our expression differently.
Notice that all nonleaves has at least one child: its first child. (e.g.
{2,0} is the first child of {2}.) We can pretend that the first child (and
all its offspring) of every nonleave is actually the nonleave, and the first
child itself does not exist.
Example:
The complete index set for the expression List[List[f[1,1]],List[f[2,1]]] is
{{0},{1},{2},{1,0},{1,1},{2,0},{2,1},{1,1,0},{1,1,1},
{1,1,2},{2,1,0},{2,1,1},{2,1,2}}
In standard intepretation, the correspondences between leaves and atoms are:
{{0} -> List,
{1, 0} -> List,
{2, 0} -> List,
{1, 1, 0} -> f,
{1, 1, 1} -> 1,
{1, 1, 2} -> 1,
{2, 1, 0} -> f,
{2, 1, 1} -> 2,
{2, 1, 2} -> 1}
The nonleaves {{},{1},{2},{1,1},{2,1}} have no corresponding atoms.
In a "mma intepretation", we have a mapping between all nodes and atoms:
{{} -> List,
{1} -> List,
{2} -> List,
{1, 1} -> f,
{1, 1, 1} -> 1,
{1, 1, 2} -> 1,
{2, 1} -> f,
{2, 1, 1} -> 2,
{2, 1, 2} -> 1}
The following nodes are now considered "non-existant":
{{0},{1,0},{2,0},{1,1,0},{2,1,0}}, because their atoms now "belong" to their
parents.
This new intepretation is actually more natural to Mathematica programers.
When we see f[1,2...], we think of f[] as a container, and things are stored
between its brackets. We don't think of f as the first element of a
container even though it IS, as clearly shown in lisp form (f 1 2 ...). With
the "mma intepretation", things are dandy because now we have data at all
nodes, not just the leaves. This is extremely useful. The price we pay is
that when the heads are nested, things quickly become confusing. Compare:
Mma form:
1[2][3[4]][5[6][7[8]]]
Lisp form:
(((1 2)(3 4))((5 6)(7 8)))
Complete index set:
{{0},{1},{0,0},{0,1},{1,0},{1,1},{0,0,0},{0,0,1},{0,1,0},{0,1,1},
{1,0,0},{1,0,1},{1,1,0},{1,1,1}}
MinimumIndexSet:
{{0,0,1},{0,1,1},{1,0,1},{1,1,1}}
In the above, the expression's structure is clearly shown by lisp form.
However, the structure using the "mma intepretation" is better shown by mma
form: the new structure is equivalent to f[ g[ 7[8] ] ], where f is
1[2][3[4]] and g is 5[6]. The dimensions of the expression in stardard
(lisp) intepretation is {2,2,2}, but in "mma intepretation" it is {1,1,1},
with each 1 correpsonding to g, 7, and 8 respectively. (Note: This is not
what Dimensions returns. More on that later.)
The two different intepretation of expression is exactly what the
Heads->True/False option means in functions that accepts a level spec. When
Heads->True, it tell mma to inteprete the expression normally, so that atoms
corresponds to leaves only. Heads->False tells mma to regards Heads as parts
of the container, not part of the expression.
Here is an analogy: We are familiar with the concept of folders and files.
Folders are containers of files. It is extremely convenient for Folders to
have names. In the "lisp intepretation", folders have no names. A folder is
a pure basket. You MAY think of the name of a folder as the first thing in
its basket. In the "mma intepretation", a folder has a name, and its name is
the first item it contains. Consequently, each folder has one less item.
Furthermore, the first item may happen to be a folder, thus the "name" of a
folder may be another folder.
Remember that the lisp and mma expression are isomorphic. You can use either
one for whatever intepretation. It is in the mma form that makes the
Heads->True/False bi-intepretation apparant, and functions can have a Heads
option for flexibility. This is what I believe to be an advantage. The
disadvantage is that the expression form no longer clearly indicates its
structure if heads are non-atomic, and the Heads->True/False is quite
confusing. Consequently, I believe it is why we don't see much use of
multiple nested heads.
With the above understanding, one may observe some idiosyncrasies of Mma.
Here are some examples.
Depth of an expression is the max number of digits in the expression's
complete index set plus 1. Plus 1 because the root {} counts as one level.
Now ·····@f[][][] returns 2, but the index of f is {0,0,0}. Of course, if
you read the Appendix, it explains that Depth[expr] is effectively
Depth[expr,Heads->False]. I wish there is a Heads option to Depth.
Similarly, the Dimensions function is effectiely
Dimensions[expr,Heads->False]. For example, expr=0[0][0[0],0[0]], its lisp
form is ((0 0)(0 0)(0 0)), clearly of dimensions {3,2}. But Dimensions[expr]
does not return {3,2}. Since now Heads are ignored, in order for Dimensions
to be useful, it added one requirement: Dimensions requires all heads to be
the same. Observe:
··········@f[f[0,0]] --> {1,2}
··········@f[g[0,0]] --> {1}
This is unintuitive because we normally would not think of same structure as
having different dimensions. More on Dimension in later posts.
Similarly, the Array function does not grow branches on Heads... and there
are others... In general, I think that Mma discourages nested heads. I wish
the Heads option will be added to more functions in future version to give
user the flexibility.
This message is getting way long. We'll come back next week. For now,
perhaps some would enjoy writing a LispToMathematica expression (string)
converter and vice versa. Solutions will be given next week if more
primitive subjects did't turn up.
Xah, ···@best.com
http://www.best.com/~xah/SpecialPlaneCurves_dir/specialPlaneCurves.html
"morality abets evil"