prograMing: trees: lisp <--> Mathematica
- To: mathgroup@smc.vnet.net
- Subject: [mg11565] prograMing: trees: lisp <--> Mathematica
- From: "Xah" <xah@best.com>
- Date: Sat, 14 Mar 1998 13:56:18 -0500
- Organization: Venus & Xah Love Factory
This is the 6th weekly posting of a series of expositions on Mathematica
expressions, trees, and index sets. I plan to continue this series
untill all Mathematica tree functions are covered (i.e. Mathematica
book, 2.1 - 2.2). So far it's all preliminary work. Today's topic is on
a pair of functions that convert lisp to and from Mathematica
expressions.
Last week we discussed how Mathematica and lisp expressions correspond
to trees and index sets. When Mathematica expression contains
non-atomic heads, it is often helpful to see the expression in lisp
form, which reveals the expression's structure visually. Thus, we'll
write a LispForm function that serves similar purpose as TreeForm.
We'll also write a LispToMathematica function so we can convert
expressions in both directions.
Here's the code for LispForm:
--
Clear[lispFormInternal,LispForm];
LispForm::"usage"=
"LispForm[expr] returns boxes that represents expr in the Lisp
language form. Related: LispToMathematicaExpression. Example:
ToString@LispForm@Array[f,{2,2}]";
lispFormInternal[expr_?AtomQ]:=ToString@expr;
lispFormInternal[expr_]:=
RowBox[{"(",Sequence@@(lispFormInternal/@Level[expr,{1},Heads->True]),
")"}];
LispForm[expr_]:=
Module[{rational,complex},
DisplayForm@
StyleBox[lispFormInternal[
expr//.{Rational[a_,b_]:>rational[a,b],
Complex[a_,b_]:>complex[a,b]}]/.{
ToString@rational->"Rational",ToString@complex->"Complex"},
AutoSpacing->False]];
--
The algorithm for LispForm is very simple. The two rules of
lispFormInternal are the main code. The rule of LispForm[expr_] is an
interface, serving as a gate. It first replaces symbols Complex and
Rational in expr to two temporary symbols, then passes the result to
lispFormInternal, and finally replaces back the Complex and Rational
heads in the result. The reason for this extra trip is because objects
like Complex[1,2] is actually an atom in the sense AtomQ@Complex[1,2]
returns True. Similarly for Rational. If this step is not taken, then
expresions containing Complex or Rational objects will not be converted
correctly because the line
lispFormInternal[expr_?AtomQ]:=ToString@expr; stops the conversion
prematurely. For example,
lispFormInternal[Rational[1,2]] will return the argument unchanged, but
the correct result should be (Rational 1 2).
Here's the code for LispToMathematicaExpression: --
Clear[LispToMathematicaExpression];
LispToMathematicaExpression::"usage"=
"LispToMathematicaExpression[LispExpressionString] returns the
Mathematica form of the lisp expression. All symbols in lisp expr are
turned into string. '() and () are turned into nil. The lisp expression
is not expected to contain strings. Note: LispToMathematicaExpression
returns a Mathematica structured expression, not a string. Related:
LispForm. Example: LispToMathematicaExpression[\"(define fact (lambda
(n) (if (eq? n 1) 1 (* n (fact (- n 1))))))\"]";
LispToMathematicaExpression[expr_String]:=
Module[{tempSymb},(ReplaceRepeated[#,tempSymb[hh_,rest___]->hh[rest]]&)@
ToExpression@(
StringReplace[#,{"["->StringJoin[ToString@tempSymb,"["]}]&)@
Function[{sexp},
With[{atomPositionsInString=(DeleteCases[#,"delete
me",{1}]&)@
Map[If[First@#+1>Last@#-1,"delete me",#+{1,-1}]&,(
Partition[#,2,1]&)@
First@Transpose@
StringPosition[sexp,{"[","]",","}]]},(
StringReplacePart[
sexp,(StringJoin["\"",StringTake[sexp,#],"\""]&)/@
atomPositionsInString,atomPositionsInString])]]@(
StringReplace[#,{"( "->"("," )"->")","("->"[",")"->"]",
" "->","}]&)@(
FixedPoint[StringReplace[#,{" "->" "}]&,#]&)@(
StringReplace[#,{"\t"->" ","\n"->" ","'()"->"nil",
"()"->"nil"}]&)@expr];
Description of algorithm used:
We are given a lisp expression in string form. e.g. "(define fact
(lambda (n) (if (eq? n 1) 1 (* n (fact (- n 1))))))"
1. Replace all white spaces to a singe space, replace spaces to comma,
replace parenthesis to brackets, replace spaces around parenthesis.
e.g. ( +
1 2) becomes [+,1,2]. (string quotes are omitted in this description
for clarity.)
2. Turn all atoms to string. e.g. [+,1,2] become ["+","1","2"]. This is
done so that all atoms in the eventual expression does not contain
atoms foreign to Mathematica. For example, +[1,2] is not a legal
expression, but "+"[1,2] is.
3. To convert the whole string to a Mathematica expression, add a
temporary head. e.g. ["+","1","2"] becomes tempHead["+","1","2"]. The
latter is converted to an expression, no longer a string.
4. Delete the tempHead and use the first element as head. i.e.
tempHead["+","1","2"] becomes "+"["1","2"].
5. Done.
Coding explained:
The coding correspondes to its algorithm fairly well. tempSymb is a
unique temporary symbol used for temporary head. The code is a one
liner of the form a@b@c@...@arg. The steps corresponds to the functions
from right to left.
--
Here are some examples of using these functions. In the following, expr1
is an array of dimensions {2,2,2}, in the sense that each node has two
children at every generation for 3 generations. It is generated by
FullArrayExpressionGenerator[{1,1,1},Heads->True]. We passed argument
{1,1,1} because recall that we count branches starting at 0.
expr2 is the same array but using Head->False (Mathematica)
intepretation to grow the tree. That is, Heads do not give birth. The
following printout reveals much of their difference. (Out labels are
removed for clarity.)
In[160]:=
expr1=FullArrayExpressionGenerator[{1,1,1},Heads->True]
expr2=FullArrayExpressionGenerator[{1,1,1},Heads->False]
0[0][0[0]][0[0][0[0]]]
0[0[0[0]]]
In[162]:=
ToString@LispForm@expr1
ToString@LispForm@expr2
"(((0 0) (0 0)) ((0 0) (0 0)))"
"(0 (0 (0 0)))"
In[164]:=
expr1CompleteIndexSet=
Sort@CompleteIndexSet@(First/@ExpressionToIndexSet@expr1)
expr2CompleteIndexSet=
Sort@CompleteIndexSet@(First/@ExpressionToIndexSet@expr2)
{{},{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}}
{{},{0},{1},{1,0},{1,1},{1,1,0},{1,1,1}}
In[166]:=
LeavesIndexSet@expr1CompleteIndexSet
LeavesIndexSet@expr2CompleteIndexSet
{{0,0,0},{0,0,1},{0,1,0},{0,1,1},{1,0,0},{1,0,1},{1,1,0},{1,1,1}}
{{0},{1,0},{1,1,0},{1,1,1}}
In[168]:=
MinimumIndexSet@expr1CompleteIndexSet
MinimumIndexSet@expr2CompleteIndexSet
{{0,0,1},{0,1,1},{1,0,1},{1,1,1}}
{{1,1,1}}
Some of the functions used above have not been posted here yet. I'll
probably write about them later, or put up a notebook on WWW.
Here a test for LispToMathematicaExpression.
In[171]:=
LispToMathematicaExpression[
"(define fact (lambda (n) (if (eq? n 1) 1 (* n (fact (- n 1))))))"]
Out[171]=
"define"["fact",
"lambda"["n"[],"if"["eq?"["n","1"],"1","*"["n","fact"["-"["n","1"]]]]]]
Finally,
ToString@LispToMathematicaExpression@ToString@LispForm@expr===
ToString@expr
and
ToString@LispForm@LispToMathematicaExpression@sexpString===
sexpString
should always be true. Please let me know bugs. Thanks.
Note:
LispForm is written using v.3 functions such as StyleForm and RowBox. I
havn't considered how should it be written in v.2. The definition given
is more or less a temporary hack, because I do not have a thorough
understanding of Mathematica's formating engine and conventions. Also,
I havn't considered evalutation issues. That is, the argument are
evaluated before they're passed to LispForm. This may not be desirable.
Considering evalutation issue will probably complicate the code. The
current definition is good in the sene that it works. Mathematica gurus
please feel free to correct or expound.
Question: Are there other objects like Complex and Rational? i.e. AtomQ
returns True but LeafCount returns more than 1. (looks like we can
write the code and see)
Xah, xah[Dot[best,com]]
http://www.best.com/~xah/
Department of philosophy
Bovine University