The Marriage of Mr. Mathematica and Ms. Scheme

Chongkai Zhu

MzScheme is an implementation of the Scheme programming language for Windows (95 and up), Mac OS, and Unix. The name is pronounced “miz scheme”, as in “Ms. Scheme”. MrMathematica is a connection between Mathematica and Scheme, especially MzScheme. It provides the ability to call Mathematica from Scheme. The two languages share much common ground while are complementary to each other. With MrMathematica, user can choose whatever feature he like either from Scheme or from Mathematica, for example, to do mathematical (both symbolic and numerical) computation in Mathematica and deal with (general) programming in Scheme. The combination of Mathematica and the neat language Scheme makes programming great fun! MrMathematica enhances Mathematica and is helping to introduce Mathematica to more people (those Schemers, i.e. Scheme Users).

Programming languages vary in power. Since the 1950s, thousands of programming languages have been designed. Among these, Mathematica and Lisp are no doubt two powerful ones. MrMathematica is attempts to combine the two.

Among all the available Lisp implementations, MrMathematica targets only MzScheme, while the design of MrMathematica remains portable to any Lisp implementation that can be extended using C.

The Scheme Dialect of Lisp

Programming languages should be designed not by piling feature on top of feature, but by removing the weaknesses and restrictions that make additional features appear necessarily [1]. The Scheme dialect of Lisp demonstrates that a very small number of rules for forming expressions, with no restrictions on how they are composed, suffice to form a practical and efficient programming language that is flexible enough to support most of the major programming paradigms in use today.

People who first learn about Lisp often want to know for what particular programming problems Lisp is “the right language”. The truth is that Lisp is not the right language for any particular problem. Rather, Lisp encourages one to attack a new problem by implementing new languages tailored to that problem. A linguistic approach to design is an essential aspect not only of programming but of engineering design in general. Perhaps that is why Lisp, although the second-oldest computer language in widespread use today (only FORTRAN is older), still seems new and adaptable, and continues to accommodate current ideas about programming methodology.

To keep the length of this paper reasonable, here I only give an overview of the language. Details can be found in the references.

A Scheme expression is either a symbol, a boolean (Scheme use #t and #f as boolean), or a list of zero or more expressions separated by whites pace and enclosed by parentheses. If an expression is a list, we call the first element the operator and the remaining elements the arguments. Scheme expression (f foo #t) corresponds to Mathematica expression f[foo,True].

Scheme is an expression-oriented language. That is, legal expressions have values. We are going to define several primitive operators:

> '(foo bar #f)
(foo bar #f)

> (eq? '() '())
#t

Now that we have an operator whose argument is evaluated we can show what the quote is for. By quoting a list we protect it from evaluation. An unquoted list given as an argument to an operator like eq? is treated as code:

> (eq? (eq? 'a 'a) #t)
#t

Whereas a quoted list is treated as mere list, in this case a list of three elements:

> (eq? '(eq? 'a 'a) #t)
#f

This corresponds to the way we use quotes in natural language. MrMathematica is the topic of this paper; “MrMathematica” is a word that contains 13 letters.

Quote may seem a foreign concept because few other languages have anything like it. It is closely tied to one of the most distinctive features of Lisp: code and data are made out of the same data structures, and the quote operator is the way we distinguish between them. (Compare this with Mathematica!)

> (cons 'a 'b)
(a . b)

> (car '(a . b))
a

With cons, car and cdr, we can now understand what list is. A list is either an empty list, the '(), or a pair, and the cdr of the pair should also be a list. If a list is not an empty list, then it’s first element is the car of the pair, while the other elements of the list (another list) is the cdr of the pair.

> (cons 'b (cons 'a '()))
(b a)
> (cdr '(a b c))
(b c)
> (cons 'c (cons 'b 'a))
(c b . a)

> (cond ((eq? 'a 'b) 'first)
        ((eq? 'a 'a) 'second))
second

Next we define a notation for describing functions. A function is expressed as (lambda ((Subscript[p, 1]) ... (Subscript[p, n])) e), where (Subscript[p, 1]) ... (Subscript[p, n]) are symbols (called parameters) and e is an expression. An expression whose first element is such an expression, ((lambda ((Subscript[p, 1]) ... (Subscript[p, n])) e) (Subscript[a, 1]) ... (Subscript[a, n])), is called a function call and its value is computed as follows: Each expression (Subscript[a, i]) is evaluated. Then e is evaluated. During the evaluation of e, the value of any occurrence of one of the (Subscript[p, i]) is the value of the corresponding (Subscript[a, i]) in the most recent function call.

> ((lambda (x y) (cons x (cdr y)))
    'z
    '(a b c))
(z b c)
> ((lambda (f) (f '(b c)))
   (lambda (x) (cons 'a x)))
(a b c)

Now that we have a way of expressing functions, we can define some new ones in terms of our primitive operators. First it will be convenient to introduce some abbreviations for common patterns. We will use cXr, where X is a sequence of as or ds, as an abbreviation for the corresponding composition of car and cdr. So for example (cadr e) is an abbreviation for (car (cdr e)), which returns the second element of list e.

> (cddar '((a b) (c d) e))
()

Also, we will use (list (Subscript[e, 1]) ... (Subscript[e, n])) for (cons (Subscript[e, 1])... (cons (Subscript[e, n]) '()) ...).

> (list 'a 'b 'c)
(a b c)

By the means of “define some new functions”, we have to use a special procedure define. (define var exp) requires var to be a symbol, evaluates exp and assigns the result to the variable var.

> (define null?
    (lambda (x)
      (eq? x '())))

> (define not
    (lambda (x)
      (cond (x #f)
            (#t #t))))

> (define append
    (lambda (x y)
      (cond ((null? x) y)
            (#t (cons (car x) (append (cdr x) y))))))

> (define map
    (lambda (f lst)
      (cond ((null? lst) '())
            (#t (cons (f (car lst))
                      (map f (cdr lst)))))))

> (define lookup
    (lambda (var env)
      (cond
        ((eq? var (caar env)) (caadr env))
        (#t (lookup var (list (cdar env) (cdadr env)))))))
> (lookup 'y '((x y) (a b)))
b

So we can define functions that process lists. An elegant notation, perhaps, but so what? Now comes the surprise: we can also, it turns out, write a function that acts as an interpreter for our language: a function that takes as an argument any Scheme expression, and returns its value. Here it is:

(define eval
  (lambda (exp env)
    (cond
      ((null? exp) '())
      ((boolean? exp) exp)
      ((symbol? exp) (lookup exp env))
      ((eq? (car exp) 'quote) (cadr exp))
      ((eq? (car exp) 'pair?) (pair? (eval (cadr exp) env)))
      ((eq? (car exp) 'boolean?) (boolean? (eval (cadr exp) env)))
      ((eq? (car exp) 'symbol?) (symbol? (eval (cadr exp) env)))
      ((eq? (car exp) 'eq?) (eq? (eval (cadr exp) env)
                                 (eval (caddr exp) env)))
      ((eq? (car exp) 'car) (car (eval (cadr exp) env)))
      ((eq? (car exp) 'cdr) (cdr (eval (cadr exp) env)))
      ((eq? (car exp) 'cons) (cons (eval (cadr exp) env)
                                   (eval (caddr exp) env)))
      ((eq? (car exp) 'cond)
       (evcond (cdr exp) env))
      ((eq? (car exp) 'lambda)
       (list 'closure (cdr exp) env))
      (#t (apply (eval (car exp) env)
                 (evlist (cdr exp) env))))))
(define apply
  (lambda (proc args)
    (eval (cadadr proc)
          (list (append (caadr proc) (car (caddr proc)))
                (append args (cadr (caddr proc)))))))
(define evcond
  (lambda (clause env)
    (cond ((eval (caar clause) env)
           (eval (cadar clause) env))
          (#t (evcond (cdr clause) env)))))
(define evlist
  (lambda (exp env)
    (map (lambda (e) (eval e env)) exp)))

The definition of eval is longer than any of the others we’ve seen before. Let’s consider how each part works.

The function takes two arguments: exp, the expression to be evaluated, and env, a list representing the values of variables. This list is called the environment, and we use lookup to search it.

The spine of eval is a cond expression. How we evaluate an expression depends on what kind it is. The first two clauses deal with self evaluating values. The third clause copes with variables. If exp is a symbol, we look up its value in the environment:

> (eval 'y '((x y z) (a b c)))
b

The next nine clauses handle the primitive operators. All of these, except quote, call eval to find the value of the arguments. The last clause is more complicated. To evaluate a cond expression we call a subsidiary function called evcond, which works its way through the clauses recursively, looking for one in which the first element returns #t. When it finds such a clause it returns the value of the second element.

> (eval '(cond ((pair? x) 'pair)
               (#t 'atom))
        '((x) ((a b))))
pair

The last two clauses manipulate function and function call. A function with the form (lambda (x) y) is evaluated to a closure, which saves the environment in the function:

> (eval '(lambda (x) (cons y x)) '((y) ('a)))
(closure ((x) (cons y x)) ((y) ('a)))

A function call has the form (f x) in which f should be a lambda expression, or a variable. Apply eval to the car of exp (i.e., f) should get a closure; apply evlist will get the value of all the arguments. Next step eval will call apply. The apply will build a new environment, in which all the arguments are bound to their values, and the evaluation will continue under the new environment. For example,

(eval '((lambda (x y) (cons x (cdr y)))
        'a
        '(b c d))
      '(() ()))

evaluates to

(apply '(closure ((x y) (cons x (cdr y))) (() ()))
       '(a (b c d)))

then

(eval '(cons x (cdr y))
      '((x y) (a (b c d))))

and finally we get

(a c d)

To fully understand this evaluation model, please run and step the code here in DrScheme (choice “Intermediate Student with lambda” and then Step).

Now that we understand how eval works, let’s step back and consider what it means. What we have here is a remarkably elegant model of computation. Using just quote, eq?, car, cdr, cons, pair?, boolean?, symbol?, and cond, we can define a function eval that actually implements our language, and then using that we can define any additional function we want.

There were already models of computation, of course, most notably the Turing Machine. But Turing Machine programs are not very edifying to read. If you want a language for describing algorithms, you might want something more abstract, and that was one of McCarthy’s aims in defining Lisp: It’s what you get (or one thing you get) when you try to axiomatize computation.

For a more comprehensive eval that contains side effects, numbers, sequential execution, and indefinite number of arguments, please refer to [3]. More advanced topics about Scheme include hygienic macros and continuation as first class value. [4] [5] [6] and [7] are good textbooks on these topics. Macros are programs that write program, a special property of the Lisp family language. To fully understand the power of Lisp, you MUST know something about Lisp macros. For a good example about what Scheme Macro is, please refer to [12].

Structure and Interpretation of MrMathematica

It is recognized that Mathematica is a domain specific language instead of general purpose one. It can’t do all the things, thus a Foreign Language Interface to a GPL (general purpose language) is needed. So there exist MathLink, J/Link, .Net/Link, and PYML (Python Link). Here comes the question: What is the “best” GPL? What GPL is the right one for Mathematica to link to? The answer to the first question is the Lisp family of languages.

There is a myth that Lisp is a “special-purpose” language, while languages such as Pascal and C are “general purpose”. Actually, just the reverse is true. Pascal and C are special-purpose languages for manipulating the registers and memory of a von Neumann-style computer. The majority of their syntax is devoted to arithmetic and Boolean expressions, and while they provide some facilities for forming data structures, they have poor mechanisms for procedural abstraction or control abstraction. In addition, they are designed for the state-oriented style of programming: computing a result by changing the value of variable through assignment statements. Lisp, on the other hand, has no special syntax for arithmetic. Addition and multiplication are no more or less basic than list operations like appending, or string operations like converting to upper case. But Lisp provides all you will need for programming in general: defining data structures, functions, and the means for combining them.

It’s difficult to convey the essence of a programming language in one sentence, but John Foderaro has come close: Lisp is a programmable programming language. One of the most distinctive qualities of Lisp is the way it can be tailored to suit the program being written in it. Lisp itself is a Lisp program, and Lisp programs can be expressed as lists, which are Lisp data structures. Together, these two principles mean that any user can add operators to Lisp which are indistinguishable from the ones that come built-in. The aforementioned eval is not only elegance but also gives you great power. For more reasoning why Lisp is the right language, please search “why Lisp” and “Lisp is slow” on the net (some results will be about Common Lisp, another major dialect of Lisp).

So Lisp is not only the axiomatization of computation, but also the most powerful programming language.

Now the answer to the second question is obvious: Lisp again. Not only because Lisp is the right GPL, but Lisp and Mathematica share many features as well. Actually, Mathematica was influenced greatly by Lisp (and a big Lisp program, MACSYMA). But there was no link between Lisp and Mathematica before. So I wrote MrMathematica. MzScheme was chosen because it is the best free Lisp implementation [13], and because Scheme has a more clear semantics than Common Lisp.

Scheme is a meta-language and MzScheme is actually an operation system [10], while Mathematica regards itself primarily as a scientific computation tool. This determines the architecture of MrMathematica: It works as an extension to MzScheme, which calls Mathematica. Mathematica and MzScheme are both implemented in C, so it is natural for MrMathematica to use C as transmitter. All needed MathLink functions are lifted into Scheme in a bottom layer. Thanks to the common ground of Lisp and Mathematica, the connection is seamless and the code of MrMathematica is compact.

The phenotype of MrMathematica is a Scheme function, MathEval, which uses Mathematica to do computation on S-exp (symbolic expressions). It translates Scheme expressions into Mathematica’s FullForm, and then sends it to MathLink. After MathLink has called MathKernel to do the computation, MrMathematica will receive the return value and translate it back into Scheme. In a nutshell, MathEval encapsulates most of the details of MathLink and gives the user a perfect interface to Mathematica.

From the example we could see that MrMathematica can communicate between Mathematica and Scheme in a much better way than links for C, Java, Python or Perl. That’s not the full story. MzScheme provides many decent features. To list some: built-in data structures such as hash table, vector (array), record (structure); a module system for managing the scope of variable and syntax definitions; exceptions and threads; i/o ports. Even if you want some different feature, choosing Lisp to implement it will always be a good choice (after making sure the feature has not already been programmed).

The design of MrMathematica does not try to provide too many features, but instead insists on not making any weaknesses or restrictions. For example, calling multiple or remote Mathematica Kernel(s) is supported; parallel computation can be obtained with the help of PLT’s thread utility; variables could all be put in Scheme and the quasi-quote will help transfer their values into Mathematica. Last but not least, both PLT Scheme and MrMathematica is under GNU LGPL, i.e., so no legal issues arise.

Somebody will think that MrMathematica forces users to use FullForm instead of InputForm. Actually, when Lisp was first designed, there are also two “Forms”, M-exp and S-exp. M-exp is close to mathematical notation and used for user input and output; S-exp is the internal representation. But finally Lispers find that only S-exp is enough and greatly helps writing programs that write programs. Although there is never ending attempt to re-invent M-exp in Lisp, none succeed [11].

Let’s see an example of MrMathematica. Supposing we need to do a design job using a Genetic Algorithm. The computation of Genetic Algorithm can be divided into two parts: generating genotypes and evaluating them. The latter part is an engineering problem and should be best attacked by Mathematica. When running Genetic Algorithm, there are many individuals to be evaluated, which will cost most of the computation power, so we would like to use multiple computers to do it in parallel, i.e., run many Mathematica Kernels. If programming entirely in Mathematica, we will have to “use MathLink to communicate between Mathematica sessions”, which is nontrivial and error-prone. Using C as a host-language doesn’t help because the API provided by MathLink is nearly the same as that between C and Mathematica. With MrMathematica, things are greatly simplified: PLT Scheme supports multiple threads of control within a program. The main thread of Scheme program generates many genotypes, and it creates multiple child-threads (as many as the number of processors). Each child-thread calls one Mathematica Kernel (on a processor) and evaluates one genotype at a time. There are built in semaphores and channels that help synchronizing Scheme threads.

Conclusion and Future Work

The MrMathematica project is still in progress. The next step is to add GridMathematica and Plot support.

Despite these omissions, MrMathematica works well. Schemers can view it as a Computer Algebra library, or a built in term-rewriting engine; Mathematica users can view it as a better FFI than that of Java or Python, or a programmable FrontEnd. After all, the two languages are somewhat isogenous, thus making the “marriage” neat.

However, this is only a start of the project. To be really successful, MrMathematica needs more applications. That’s the reason for this paper. Enjoy hacking with MrMathematica.

For more information about MrMathematica, please visit www.neilvandyke.org/mrmathematica.

References

[]  Harold Abelson and Gerald Jay Sussman, LISP: A Language for Stratified Design, MIT AI Memo, 1987.

[]  Paul Graham, Roots of Lisp, www.paulgraham.com/rootsoflisp.html, 2001.

[]  Harold Abelson and Gerald Jay Sussman with Julie Sussman, Structure and Interpretation of Computer Programs, 2nd ed., The MIT Press, 1996.

[]  Daniel P. Friedman, Mitchell Wand, and Christopher T. Haynes, Essentials of Programming Languages, 1st ed., The MIT Press, 1992.

[]  R. Kent Dybvig, The Scheme Programming Language, 3rd ed., The MIT Press, 2003.

[]  R. Kent Dybvig, Writing Hygienic Macros in Scheme with Syntax-Case, August 1992.

[]  Dorai Sitaram, Teach Yourself Scheme in Fixnum Days, www.ccs.neu.edu/home/dorai/t-y-scheme/t-y-scheme.html, 1998–2003.

[]  PLT Scheme, www.plt-scheme.org.

[]  S. Wolfram, The Mathematica Book, 5th ed., Champaign/Cambridge: Wolfram Media, Inc./Cambridge University Press, 2003.

[]  Matthew Flatt, Robert Bruce Findler, Shriram Krishnamurthi, and Matthias Felleisen, Programming Languages as Operating Systems, ICFP 1999.

[11]  Guy L. Steele Jr., Richard P. Gabriel. The Evolution of Lisp, section 3.5.1. www.dreamsongs.com/NewFiles/Hopl2.pdf

[12]  Shriram Krishnamurthi, Automata as Macros, www.cs.brown.edu/~sk/Publications/Papers/Published/sk-automata-macros/paper.pdf, 2005.

[13]  bc.tech.coop/blog/040109.html and bc.tech.coop/blog/040111.html