Mathematica's
Programming Language

Roman E. Maeder
Swiss Federal Institute of Technology (ETH)

Abstract

Mathematica includes a rich and powerful programming language. It combines the
procedural, functional, and rule-based programming styles in a single coherent
system. We describe the design decisions taken in implementing Mathematica's
programming language, and compare the different programming styles in the way
they present themselves in Mathematica.

The language is well suited to handle the major programming paradigms,
including procedural and functional programming, modularization, abstract data
types, term rewriting, logic programming, and object-oriented programming. We
show typical uses of these paradigms, and discuss implementation issues for
those that are not already part of the language.

The material presented here is adapted from Chapter 1 of The Mathematica
Programmer, AP Professional, 1994. Most of the topics mentioned here are covered in detail
in the other chapters of this book. Earlier versions of this material were
published in The Mathematica Journal, in a column entitled "The Mathematica
Programmer".

The Programming Language

Procedures in Mathematica

Strictly speaking, there are no procedures, functions, or subroutines in
Mathematica. Any definition of the form f[args]:=body is a rewrite rule.
Whenever the evaluator sees an expression that matches the left side, the
expression is replaced by the right side with the values of the pattern
variables substituted. This mechanism corresponds closely to a procedure call
of a traditional language, a similarity that is intended.

A Typical Procedure

SplitLine[vl_] :=
        Module[{vll, pos, linelist = {}, low, high},
                vll = If[NumberQ[#], #, Indeterminate]& /@ vl;
                pos = Flatten[ Position[vll, Indeterminate] ];
                pos = Union[ pos, {0, Length[vll]+1} ];
                Do[ low = pos[[i]]+1;
                    high = pos[[i+1]]-1;
                    If[ low < high,
                        AppendTo[linelist, Take[vll, {low, high}]] ],
                   {i, 1, Length[pos]-1}];
                linelist
        ]

(Taken from Programming in Mathematica, Chapter 1.)

A Typical Function

RandomPoly[x_, n_] :=
        Sum[ Random[Integer, {-10, 10}] x^i, {i, 0, n} ]

A Typical Rewrite Rule

log[a_ b_] := log[a] + log[b]

Formal Parameters

The pattern variables in a procedure declaration are not local variables in
the procedure (as they are in Pascal or C)! To get this behavior you can use
the following:

f[x0_, y0_, z0_] :=
        Module[{x=x0, y=y0, z=z0}, (* initialized local variables *)
                .
                .
                x = ...                (* use of local variable *)
        ]

On the other hand, parameter passing by reference (var parameters in Pascal,
pointers in C) is also possible

SetAttributes[f, HoldAll]

f[xref_Symbol] :=
        Module[{locals...},
                .
                .
                xref = val     (* assignment to global parameter *)
        ]

Pattern Matching and Term Rewriting

Pattern matching and term rewriting is the fundamental operating principle of
Mathematica's evaluator. All other programming constructs are implemented by
way of term rewriting.

It is especially useful for implementing rules corresponding to
transformations from a handbook of formulas. Equations in a handbook are
usually meant to be used as rewrite rules, transforming the left-hand side
into the right-hand side. By looking up an expression, we perform essentially
pattern matching in our head.

Example: Laplace Transforms

Definitions taken almost verbatim from a handbook of mathematics follow:

Laplace[c_, t_, s_] := c/s /; FreeQ[c, t]

Laplace[a_ + b_, t_, s_] :=
        Laplace[a, t, s] + Laplace[b, t, s]

Laplace[c_ a_, t_, s_] :=
        c Laplace[a, t, s] /; FreeQ[c, t]

Laplace[t_^n_., t_, s_] :=
        n!/s^(n+1) /; (FreeQ[n, t] && n > 0)

Laplace[a_ t_^n_., t_, s_] :=
        (-1)^n D[Laplace[a, t, s], {s, n}] /; (FreeQ[n, t] && n > 0)

Laplace[a_. Exp[b_. + c_. t_], t_, s_] :=
        Laplace[a Exp[b], t, s-c] /; FreeQ[{b, c}, t]

Usage:

Laplace[ Exp[omega t + phi] t^2, t, s]

Programming Paradigms

Functional Programming

Structured Iteration and Reduction

Given the problem of adding the square roots of the first 500  integers, the
solution in most programming languages is to use an auxiliary variable that is
incremented by the square root of a loop index iterating from 1 to 500.

sum = 0.0;
Do[ sum = sum + N[Sqrt[i]], {i, 1, 500} ];
sum

In Mathematica, this loop reduces to a single statement that corresponds
directly to the mathematical formula.

Sum[ N[Sqrt[i]], {i, 1, 500} ]

Mathematica does not force you to think about how to implement a summation,
but lets you focus instead on the concept itself. Product[] works in the same
way, multiplying its terms together instead of adding them up.

Think of the loop body as a function applied to a list/sum/product of values.

l = {1, 2, 3, 4, 5};

Table[l[[i]]^2, {i, 1, Length[l]}]

#^2& /@ l

Consider this programming style whenever you see loops that iterate over a
structure (list, matrix, ...).

Folding

What does Fold[] do? One easy way to see how such a function works is to apply
it to purely symbolic (undefined) functions.

Fold[f, e0, {e1, e2, e3}]

One use of Fold[] is for recursion-removal. The body of a recursively defined
function (with one recursive call) can be thought of as a function f of two
arguments, the result of the recursive call and the value of the recursion
parameter (the value that changes from one call to the next). We then generate
a list of all values of the recursion parameter and use Fold[] with the
initial value equal to the value of the boundary case. Here is the standard
example, factorial numbers. This is the recursive definition:

factorial1[0] = 1;
factorial1[n_] := n factorial1[n-1]

The body function is simply multiplication, the recursion parameter ranges
from 1 to n. This gives the following definition:

factorial2[n_] := Fold[ Times, 1, Range[1, n] ]

Note that it works also for n = 0.

FoldList[] shows the intermediate steps.

FoldList[ Times, 1, Range[1, 10] ]

Nesting and Fixed Points

Loops that compute a value iteratively are examples of nested function
application.

r = 2.0;

x = 1.0;
Do[ x = (x +r/x)/2, {10}];
x

Nest[Function[x, (x +r/x)/2], 1.0, 10]

FixedPoint[Function[x, (x +r/x)/2], 1.0]

Logic Programming

Reversing a list in typical Prolog style.

reverse[l_] := rev[ l, {} ]
rev[ {}, r_ ] := r
rev[ {h_, t___}, {r___} ] := rev[ {t}, {h, r} ]

reverse[ {a, b, c} ]

Backtracking can be implemented with side conditions.

sort[ {alpha___, x_, y_, omega___} ] :=
        sort[ {alpha, y, x, omega} ] /; x > y

sort[ l_ ] := l

sort[ {5, 1, 3, 2} ]

Prolog

Here is a Prolog interpreter written in Mathematica.

Needs["LogicProgramming`"]

This is the game of NIM.

<<NIM.m

Now generate/perform moves.

LogicValues[play]

The strategy of NIM follows:

LogicValues[win]

All moves from position (1 2 1) are given.

QueryAll[play[list[1,2,1], t_, _]]

Find the winning move.

Query[win[list[1,2,1], t_]]

Perform this move.

Query[play[list[1,2,1], t /. %, newpos_]]

See The Mathematica Journal, Vol. 4, issues 1 and 2.

Modularization

Good programming style suggests separating definition and implementation. The
exported functions are declared and documented. Any needed functions are
declared and imported. The package mechanism in Mathematica provides for these
features. It is explained in detail in Programming in Mathematica
(Addison-Wesley, 1991).

A Demonstration Package

Create a clean state for a new package and declare any imports.

BeginPackage["Demo`", "Needed1`"]

Create the public symbols. This is best done with a usage message.

SampleFunction::usage = "SampleFunction[n] does nothing"

Start the implementation part.

Begin["`Private`"]

All new symbols in this part will not be exported.

SampleFunction[n_] := n^3 + 2n^2 + 3n + 4

AuxFunction[m_] := something

End[]

End the package and add its context to $ContextPath.

EndPackage[]

Reading it in.

This is a machine-independent way of reading in packages.

<< Demo`

The exported function can be used outside.

?SampleFunction

The private symbols are not found.

?AuxFunction

Import of Packages: Details

Transitivity: if A` needs B` and B` needs C`, can A` use C`?

BeginPackage["A`", "B`"];

a::usage = "a in A";

Print[$Context, $ContextPath];

EndPackage[];

BeginPackage["B`", "C`"]

b::usage = "b in B"

EndPackage[]

BeginPackage["C`"]

c::usage = "c in C"

EndPackage[]

In Version 2.2, C` is not available inside the package A`. This will be fixed in the next
version.

Hidden import

BeginPackage["D1`"];

Needs["E`"]; (* hidden import *)

Print[$Context, $ContextPath];

EndPackage[];

BeginPackage["D2`"];

Needs["E`"]; (* hidden import *)

Print[$Context, $ContextPath];

EndPackage[];

$Packages

$ContextPath

In Version 2.2.0, a second attempt at hidden import fails, since the package is not
read again, and it is not put on $ContextPath. This is now fixed.

Abstract Data Types

Abstract data types are both a theoretically well-defined concept and a useful
tool for program development. Following the principles of abstract data type
design, one arrives at a clear separation of specification and implementation.

Abstract data types are defined in terms of type names, function names, and
equations. These can be realized in Mathematica very easily. The equations
become rewrite rules. The interactive nature of Mathematica makes it well
suited for rapid prototyping and testing of designs.

A detailed discussion of abstract data types in Mathematica can be found in
The Mathematica Programmer, and in Vol. 2, No. 3 of The Mathematica
Journal. Here is a short excerpt and an example.

How to Define a Data Type

Define the names of the sorts to be used.

Define the constants to be used.

Define constructors and selectors.

Write down the equations that should hold.

How to implement a Data Type

Choose a representation for elements of the sorts defined.
Usually you can use a normal expression having the name of the sort as head.
This corresponds roughly to a record in many programming languages.

Derive rules for normal forms for the data elements.
This ensures that elements are stored in a unique way. The rules are derived
from the equations and can normally be put into the constructors.

Define constructors and selectors.
These are the only operations that are allowed access to the details of the
internal representations.

Define the other operations.
An operation for which exactly one equation exists can usually be turned into
a simple rewrite rule. (Such an operation is called a derived operation.) The
variables in the left side of the rules are in the form n_type, restricting
the arguments to the correct types. Use only selectors to access parts of the
data elements on the right side of the rules.

Use overloading where appropriate.
Overloading built-in functions is most easily done by defining up-values,
rules of the form

g/: f[n_g, ...] := ...

Choose a suitable output representation of data elements.

Define automatic type conversions where useful.

An Example

This is a data type for modular numbers.

Design

Sorts:                  mod, Integer

Constants:              p

Constructors:           makemod

Selectors:              rep

Derived Operations:     Plus, Times

Equations:              Mod[ rep[ mod[n] ] - n, p ] == 0

Implementation

makemod[n_Integer] := mod[ Mod[n, p] ]

rep[ mod[n_] ] := n

mod/: m1_mod + m2_mod := makemod[ rep[m1] + rep[m2] ]
mod/: m1_mod * m2_mod := makemod[ rep[m1] * rep[m2] ]

Note that we have overloaded the built-in addition and subtraction functions.
This corresponds directly to the use of the same names in the specification.

Usage

This sets the modulus to 5 for the computations that follow.

p = 5;

This makes two modular numbers and assigns them to the variables m2 and m3.

m2 = makemod[2]; m3 = makemod[3];

Their sum is 0 (modulo 5).

m2 + m3

Their product is 1 (modulo 5).

m2 m3

Lazy Evaluation: Infinity

With lazy evaluation, arguments of functions are only evaluated when they are
needed, not when the function is called. It can be implemented with the
attributes HoldFirst and HoldRest. Among other things, this idea allows us to
implement infinite lists.

It is, of course, impossible to deal with an infinite set explicitly on a
finite computer. But a set whose elements can be generated one at a time, each in a finite
number of steps---such a set is called recursively enumerable---can be
considered in some sense as entirely "known," because any element can be
produced upon demand. The set of all perfect squares, for example, is
recursively enumerable, for each element can be computed by the formula n^2,
where n = 1, 2,.... Such a formula describes a function of the integers; we
can therefore define a recursively enumerable set as the range of a computable
(or recursive) function.

We will call our infinite lists streams (not to be confused with input and
output streams in Mathematica).
Good software design principles suggest that we do not work on stream objects
directly, but only through an interface that hides the implementation details.
Here the interface consists of a constructor MakeStream[first, rest]
and two selectors First[stream] and Rest[stream].

The data-structure built in this way is the same as lists in Lisp. The rest,
however, is now a function that produces the rest of the stream (usually
another stream) when called. Until then it is held in unevaluated form.

<< Streams.m

First Example

Our first example is a stream of zeroes.

zeroes = MakeStream[0, zeroes]

First[zeroes]

Rest[zeroes]

We can take the rest several times.

Nest[ Rest, zeroes, 1000 ]

The Set of Integers

The definition below produces a stream of integers starting from n.

IntegersFrom[n_Integer] := MakeStream[n, IntegersFrom[n+1]]

The first element of the stream of integers from n is, of course, n itself,
and the rest is the stream of integers from n+1.

integers = IntegersFrom[1]

If we take the rest of integers 99 times and then take the first element, we
should get the 100th element. We can overload Part[] to perform this operation
on streams.

integers[[100]]

Streams like Lists

We can overload most functions on lists to work also with streams.

Listable functions thread over streams as they do over lists.

integers^2

Take[%, 10]

Most functional constructs work on streams.

Select[ integers, PrimeQ ]

%[[1000]]

Nest[] without its third argument produces a stream.

goldenstream = Nest[ Function[x, 1 + 1/x], 1 ]

Take[ goldenstream, 15 ]

N[%, 10]

Object-oriented Programming

Object-oriented programming is a programming style that is becoming more and
more popular. It promises code-reuse and easier maintenance of larger projects
than is possible with traditional procedural languages. Its use of methods and message passing
instead of procedure calls shifts the programmer's view towards close
integration of data and operations.

An interactive object-oriented language can easily be implemented in
Mathematica. The implementation is in the package Classes.m, available from
MathSource.

Objects and Classes

The first important aspect of object-oriented languages is that functions are
considered part of data. A data object "knows" which operations can be
performed on it. The functions defined for a certain type of object are part
of that object.

Thus an object is a collection of data elements and operations that act on these data elements. The operations are called methods.

Methods are usually not defined for each object separately but are collected
in a class. Objects then belong to a class from which they take their methods.

Message Passing

A uniform mechanism, called message passing, is provided for invoking the
correct piece of code, if a function is called or, as we now prefer to say, if
a message is passed to an object to execute a certain method. This viewpoint
emphasizes that it is the object's responsibility to react to a message.

Inheritance

Often a number of related data types have some common characteristics. Some
operations on them can be written in a way that does not depend on which of
the data types the operations are applied to.  Common characteristics of related data types
can then be isolated and encapsulated in a new data type. The other data types
are then made subtypes of the new type. They inherit the characteristics of
the common type, and need only implement those aspects in which they differ
from their supertype.

Thus, much of the code needs to be written only once. This saves development
time and--perhaps more important--ensures consistency, since a change needs
to be made only once, instead of being applied to several almost identical
pieces of code.

An Example

The implementation of the object-oriented system in the package Classes.m is
described in detail in Vol. 3, No. 1 of The Mathematica Journal. An updated
version of the package is available from MathSource.

Needs["Classes`"]

A class is declared with

Class[ name, superclass, instance variables, methods ]

An account has one instance variable, the balance, and methods to initialize
it and to deposit and withdraw money and to ask what the balance is.

Class[ Account, Object,
    {bal},
    {{new,      (new[super]; bal = #1)&},
     {balance,  bal&},
     {deposit,  Function[bal += #1]},
     {withdraw, Function[bal -= #1]},
     {delete,   (If[ bal != 0, Print["Remaining balance:", bal]];
                 delete[super])&}
    } ];

a1 = new[Account, 100]

Message passing is made to look like ordinary function calls. The object that
receives the message is the first argument.

deposit[ a1, 200 ]

withdraw[ a1, 500 ]

Here is a subclass of Account. It inherits most behavior. The method for
withdrawing money is overridden to check whether the balance is sufficient for
the withdrawal. If it is, we invoke the method in the superclass Account to
perform an ordinary withdrawal.

Class[ NoCreditAccount, Account,
    {},
    {{withdraw, Function[ If[ balance[self] < #1,
                              Print["cannot withdraw ", #1],
                              withdraw[super, #1] ] ]}
    } ];

a2 = new[NoCreditAccount, 1000]

withdraw[ a2, 900 ]

withdraw[ a2, 110 ]

balance[ a2]