Wolfram Computation Meets Knowledge

Symbolic Programming: Computationally Active Language

In this blog and elsewhere, you’ll often see the statement that some advanced Mathematica feature is just another application of symbolic programming. It’s the kind of idea that seems too powerful to explain in a single blog post, yet simple enough that I am tempted to try. So, here goes.

Symbolic programming is based on the concept of recasting core features of human language into a computationally active form.

What does it mean to have a human-language-oriented programming language?

Our cognitive model of computation is typically a three-stage process: 1) describing the computation; 2) executing that description; and 3) outputting the results.

The “language” part of most programming languages begins and ends with stage one. Linguistic structures are erected to describe the program. But the execution of the program is typically oriented around an entirely different system of types and objects; and likewise, the program’s output structure tends to resemble nothing particularly language-like.

Symbolic programming uses linguistic structures as the foundation of all aspects of computation. From a computation’s description, to how the computation executes, to how humans interface with the results, the exact same basic tree structure is used throughout.

This is a powerful unification, making possible many useful computations that in other systems range from cumbersome to practically impossible. We’ll see examples along the way, but let me first describe what these linguistic structures actually are.

Symbols: The Atoms of Language

Symbols are the basic atoms of language and also of symbolic programming. The point of symbols is to have distinct pieces of notation—be they words or mathematical functions or musical notes—which are then assigned an interpretation within the overall system.

In programming, the defining feature of symbols is that they can stand for themselves. This is in contrast to variables, which must stand for some other value or be considered an error. For instance, JavaScript cannot perform the operation x + x unless x has a value:

>>> x | x is not defined | >>> x+x | x is not defined

while Mathematica has no trouble:

In[1]:= x + x | Out[1]= 2 x

By existing simply as distinct entities, symbols serve as lightweight carriers of meaning. They are inert, but can acquire meaning through combination with other symbols. For example the symbol for Pi is generically just another symbol, but when it appears “within” the symbol N, it takes on its special numerical meaning:

In[2]:= Pi + Pi | Out[2]= 2 \[Pi] | In[3]:= N[2 \[Pi], 17] | Out[3]= 6.2831853071795865

Because Mathematica manipulates things abstractly, it is able to do more-precise computation than some other systems. As the above example makes clear, symbols are only the building blocks: the real action is with the arrangements of symbols.

Symbolic Expressions: Combining Symbols into Meaning

An English phrase is built of subphrases. A mathematical formula is built of subformulas. A musical score is built of bars, which contain notes. A web page layout is built from sublayouts. When humans want to communicate nontrivial structures, they use hierarchical nesting.

Across different languages and domains, these structures, or trees, take many syntactic forms. However, they can always be reduced to very simple data structures known as symbolic expressions. Symbolic expressions simply capture the concept of arranging symbols into trees. Here are a few trees built from the symbol “e”:

e | e[e] | e[e,e] | e[e[e]] | e[e[e], e]

Like the symbols themselves, trees of symbols may simply exist, without a need to correspond to something else:

In[4]:= e[e] | Out[4]= e[e]

Symbolic expressions are the fabric from which we construct meaning. Different tree structures correspond to different meanings.

A tree with symbols like Plus and Power may represent an arithmetic expression, while the symbol SetterBar can be combined with a subtree indicating the current selection and a list of possible alternatives:

In[5]:= Row[{TreeForm[a + b^2 + c^3 + d], TreeForm[a b c]}] | Out[5]= (list of trees)

Everything in Mathematica is ultimately represented using this uniform simple structure. At the formal level, it ensures a degree of structural compatibility across all parts of the far-flung system. It also provides a system for introducing your own lightweight yet sophisticated structures.

Pure functions, for example, are the original killer apps for lightweight structures of this vein. In Mathematica, they can be represented with Function, but let’s roll our own using other generic primitives:

MyPureFunction[var_, expr_][arg_] := expr /. var -> arg

Let’s describe a function that adds 1 to its argument, and attach it to the symbol f. Notice the structure stays inert, and therefore can be passed around as data:

In[6]:= f = MyPureFunction[x, x + 1] | Out[6]= MyPureFunction[x, 1 + x]

When brought into contact with an argument, the definition fires.

In[7]:= f[a] | Out[7]= 1 + a

In symbolic programming, it is commonplace for a programmer to create abstractions that in another language would have required a modification of the core specification. This is the beauty of language: that creating new concepts does not require inventing new atomic “types” of things—only new arrangements of structure.

Computation: The Transformation of Meaning

The most important and unique aspect of symbolic programming is that these tree structures can be made computationally active. They don’t just describe things—they actually execute.

The basic idea is that because meaning is encoded by structure, computation—the transformation of one meaning into another—corresponds to the transformation of one structure into another.

For instance, position 1 in the SetterBar expression represents the current selection. By modifying the tree at that position, we modify the meaning of the expression as a whole:

In[8]:= ReplacePart[a b  c, 1->b] | Out[8]= a b c | In[9]:= a b c // InputForm | Out[9]/InputForm= SetterBar[b, {a, b, c}]

A computation begins and ends with unique, domain-specific structures. The process of computation, however, is executed using extremely general methods that are exactly the same across domains:

In[10]:= a + b /. Plus -> Subtract | Out[10]= a - b | In[11]:= {Graphics[Circle[]], Graphics[Circle[]]} /. Circle->Rectangle | Out[11]= {Graphics[Rectangle[]], Graphics[Rectangle[]]}

So, computation proceeds by very generic tree transformations. Rather conveniently, trees are also how we specify the computations themselves.

This reduces the process of computation into a linguistic puzzle: using trees to describe how other trees should transform and intersect. Not only does this allow computational primitives to have an immediate and clear meaning, it also allows the process of language design to proceed organically as regularities in these tree structures are discovered and abstracted.

Representing and Interacting with Meaning

Symbolic programming’s comprehensive emphasis on meaning allows a unique perspective on input, output and the whole interaction cycle between human and machine computation.

The basic idea is that symbolic expressions are the canonical, abstract containers of meaning. Given a symbolic expression, its meaning can then be embodied in a number of useful ways.

For example, the expression Plus[2,2] is rendered as 2+2. And Graphics[Rectangle[]] renders as:

Rectangle

And it works similarly for all sorts of domain-specific mathematics notation, documents and even sound and music primitives.

On their own, these are useful representations. But the fact that they are still really the same underlying expression leads to a powerful consequence: human computation and programmatic computation become structurally equivalent.

If I interactively create a Disk using a drawing palette:

Disk with drawing palette

its underlying data structure is the same as it would be if I had typed in the code, or if it had been generated by a program:

InputForm for disk

Graphics[Disk[{0.49, 0.49}, {0.35, 0.35}],
ImageSize -> {36.335, Automatic},
PlotRange -> {{0, 1}, {0, 1}}]

Completely different representations—in this case text and graphics—are immediately and transparently compatible, because in the end they are all just expressions. Here we have some “zero-overhead” code to color just the disks of a graphic:

ColorDisks[x_] := x /. {y_Disk -> {Blue, y}}

ColorDisks function using graphics of Rectangle and Disk

The equivalence between these representations, and between human and programmatically generated structures, opens the door to exceptionally powerful ways of interacting with computation. It is the basis of Mathematica’s dynamic interactivity framework.

The implications, however, go much further than that. Symbolic programming is the first abstraction that can uniformly span all three stages of computation, from specification to execution to output, and as a result it can leverage each aspect against the others.

Programs can be created by traditional programming, by the programs themselves or by interaction with what is considered output. The process of computation can be equivalently executed by the user or by the machine. Output is simply exposing a window into a piece of a (possibly running) program.

It’s pretty impressive that so many useful consequences can flow from the simple idea of symbolic programming: fitting computation to language, rather than the other way around.