Notes

Chapter 3: The World of Simple Programs

Section 10: Symbolic Systems


Representations [for symbolic expressions]

Among the representations that can be used for expressions are:

Typical transformation rules are non-local in all these representations. Polish representation (whose reverse form has been used in HP calculators) for an expression can be obtained using (see also page 1173)

Flatten[expr //. x_[y_] -> {\[EmptySmallCircle], x, y}]

The original expression can be recovered using

First[Reverse[list] //. {w___, x_, y_, \[EmptySmallCircle], z___} - > {w, y[x], z}]

(Pictures of symbolic system evolution made with Polish notation differ in detail but look qualitatively similar to those made as in the main text with functional notation.)

The tree representation of an expression can be obtained using expr//.x_[y_]->{x, y}, and when each object has just one argument, the tree is binary, as in Lisp.

If only a single symbol ever appears, then all that matters is the overall structure of an expression, which can be captured as in the main text by the sequence of opening and closing brackets, given by

Flatten[Characters[ToString[expr]]/.{"["->1,"]"->0, "e" -> {}}]

From Stephen Wolfram: A New Kind of Science [citation]