Compiling Lisp code

Introduction

This section deals with compiling Lisp code to a form that runs more efficient on a real computer.

The overheads of executing Lisp are:

The first concern will be to convert the Lisp code to source code for the target platform; when the Lisp interpreter is written in Java we want the Lisp code compiled to Java, etcetera.

The disadvantage is the compiler then needs to be around for compilation to be able to take place. Programs thus get compiled once, and then run. The compiler is not available at run time. As compiled code can interact with interpreted code, the user is still free to write his own functions, but they will have to run interpreted.

The advantage of directly compiling to source code as input for another compiler is that it is less work. However, a little compiler could be written that takes the resulting output source code and compiles it further to some other target, dynamically at run time. Theoretically, even a byte code interpreter could be written, and a compiler for it, and this could be plugged into the system.

Steps for converting to source code

When compiling to source code, the first step is parsing in the code to be compiled. The compiler will have to look very similar to an interpreter; code needs to be read in, and part of it needs to be executed at compile time (macros will be expanded during compilation), global variables are set, functions defined, and possibly other things done while loading a file. Compilation will be taken to mean creating a class that gets loaded, and a method in this class called to perform what would usually be performed when loading the file.

The fact that compilation is reminiscent of interpretation suggests that the strategy pattern could be used, when the compiler is written in the target environment. For this, the default evaluation routine or object needs to be replaced by another, one that compiles in stead of interpreting. Compiling would then reduce to loading a file, but using a different 'interpreter' for it. This abstraction is further warranted by the fact that a debugging environment is needed, one where a programmer can step through code.

Defining a function will reduce to defining a class (in an object-oriented system) with an eval or apply method. The method gets called with a list of arguments to perform its tasks. In addition, routines can be created that directly perform the task with the arguments given in directly in the target programming language. This is made easier with the Lisp dialect described earlier because of the constraint of a fixed number of arguments.

Parsing the expressions into an internal format

The first possible step is to skip parsing at runtime, by doing it at compile time. Even though this does not give a much greater speed at runtime, it is a requirement if the code is to be compiled.

A form (foo a b) could be compiled to 

LispObject object = 
   cons(recSymbol("foo"),
      cons(recSymbol("a"),
         cons(recSymbol("b"),nil)));
This expression could be assigned at construction of the object, and thus built only once like the interpreter would do.

Equivalently, a symbol bar would be defined as: 

LispObject object = recSymbol("bar");

If nothing is known about the function foo, no further simplifications can be made, as it could be a macro or a function, and thus nothing is known about whether the arguments need to be evaluated or not.

When foo is a macro, it can be dealt with easily by directly expanding the code in place. When foo is defined as 

In> (defmacro foo (a) a)
Out> foo

Evaluation of (foo (+ 2 3)), 

In> (foo (+ 2 3))
Out> (+ 2 3 )

is the same as inlining the code with a let statement: 

In> (let ((a (quote (+ 2 3)))) a)
Out> (+ 2 3 )

Macros have to be expanded before an expression is evaluated, but other than that, the compiler can read in all the code before inlining macros, to be able to inline macros that are defined later on. Alternatively, the actual evaluation could be cast in code that looks at runtime to discover whether a function call is actually a macro expansion, but this is less efficient at run time.

In the following examples, it is assumed that there are objects of type LispObject, which can hold a general Lisp expression, LispNumber which can hold a number, and functions eval, cons, and recSymbol. The last, recSymbol, takes some native argument like a string, and converts it to a LispObject. nil is taken to be an empty list.

Optimizing an expression can then continue in various steps. Suppose we take the definition of the call (foo a b) above, and that we know that foo is a function that will be compiled. Then we can rewrite 

LispObject object = 
   eval(
      cons(recSymbol("foo"),
         cons(recSymbol("a"),
            cons(recSymbol("b"),nil))));
return object;

as 

LispObject object = 
   Foo.eval(
         cons(eval(recSymbol("a")),
            cons(eval(recSymbol("b")),nil)));
return object;

Here the arguments are evaluated explicitly before being passed to foo, and foo is hard-linked, called directly with the appropriate arguments.

A next step is to optimize the eval inside these expressions, eg. optimizing evaluation of a and b. If a and b were local variables from within a let statement, or arguments to a function call in its environment, this could be optimized further. Each declaration of a local variable can be made a real local variable in the target source code. 

(let ((a 2) (b 3)) (foo a b))
could become 

LispObject a = recSymbol("2");
LispObject b = recSymbol("3");
LispObject object = 
   Foo.eval(cons(a,cons(b,nil)));
return object;

This skips lookup of local variables in an environment, as the compiler will be able to directly take the appropriate value.

In the dialect described here, we only accept a fixed number of arguments, and thus we could add a method to the Foo object which accepts two arguments, and the code would change to: 

LispObject a = recSymbol("2");
LispObject b = recSymbol("3");
LispObject object = Foo.eval(a,b);
return object;

If foo is guaranteed to only work with numeric values for input, we could add another method to the foo evaluator object Foo, one which takes two numeric arguments: 

LispNumber a = 2;
LispNumber b = 3;
LispNumber number = Foo.evalTyped(a,b);
return recSymbol(number);

The interesting option for the last optimization is that all the intermediate values are now numbers, not lisp atoms. The advantage to this is that if an expression is more complex than the above example, the input arguments can be converted to numbers at the beginning, and then the arithmetic operations performed, and only at the end are these numbers converted back to atoms (through the recSymbol function explained above). So in this case, 

(let ((a 2) (b 3)) (+ (foo a b) 5))

Could be converted to: 

LispNumber a = 2;
LispNumber b = 3;
return recSymbol(Foo.evalTyped(a,b)+5);

A lot of conversions to and from formats can be avoided if the compiler can recognize that it is appropriate. Code of this form would not be much slower than code written natively in the target language (actually not quite true, if you have the full language at your disposal you might be able to do optimizations by hand).

If functions are defined as macros, of course the compiler can inline them and perform additional optimizations, removing the need for the overhead of a call.

A further optimization could be a conversion to native numeric types. If the compiler knows that the result of some computation is an integer, and it fits in a native integer (for instance a 32-bit integer), tha above code could become: 

return recSymbol(Foo.evalTypedNative(2,3)+5);

Some general rules for optimization

Optimization generally entails doing as much work doing compilation, and as little as possible during runtime. Looking up the location where a local variable is stored, looking up a function, and in a macro that gets inlined determining if an if statement or some clause to a cond statement will always return true are things the compiler can find out and 'evaluate' at compile time, so it doesn't have to be done at runtime.

The compiler can optimize code based on assumptions about the input. This is why compiled languages usually have typed variables. This can also be solved, for specific cases, by using macros. Suppose one wants to multiply two matrices, (mat-mult a b). The elements of the matrices a and b can be anything, univariate polynomials, multivariate polynomials, analytic functions of one variable, complex, real. But when the compiler knows the elements of the matrices are real-valued, some optimizations can be made in the body of a macro. Alternatively, if a function call required for multiplying matrix elements is defined as a function, that function can be treated as a macro, and a separate function compiled from it and called from within mat-mult, to take into account the fact that it is going to be passed real-valued matrix elements. Having more information about the input gives options for optimizing the code more. This allows algorithms to be stated at a high-level, with the compiler taking care of the optimizations for a specific case.

With optimization by hand, often a situation is encountered where a loop performs a task a few million times, and thus every clock cycle that can be saved in the inner loop saves a few million clock cycles. Inlining macros allows the compiler to discover that an if or cond statement always executes the same clause, and thus the if or cond statement (which has to be independent of the loop index) can be taken outside of the loop.

Dealing with function calls and macro expansions when compiling Lisp expressions to syntax from other languages

Since we are using a strongly typed Lisp dialect with no implicit type conversions, Lisp expressions can be readily converted to other syntax quite easily. Most procedural or object-oriented languages require a notation of the form function(arg1,arg2,...) where in Lisp that would be (function arg1 arg2 ...).

One slight problem arises due to the fact that every expression in Lisp returns a result, including macro's. Consider the following piece of code: 

(while (< i n)
  (progn
    (print i)
    (setf i (+ i 1))
) )

This is easy to convert to for instance c++ syntax as: 

while (i<n)
{
  printf("%d\n",i);
  i=i+1;
}

Now a slightly more advanced example shows the problem: 

(while (progn (print i) (< i n))
  (progn
    (setf i (+ i 1))
) )

This is valid Lisp code. progn returns the result of evaluating the last expression. A naive translation to c++ would yield: 

while ({printf("%d\n",i); i<n;})
{
  i=i+1;
}

which is obviously invalid c++ code. One way around this in this case could be: 

{
  printf("%d\n",i);
  pred = i<n;
}
while (pred)
{
  i=i+1;
  {
    printf("%d\n",i);
    pred = i<n;
  }
}

However, in this case, if the progn statement is large, it could result in a doubling of a large bit of code. It would however be efficient.

The other alternative would be to encapsulate the progn in a separate function that can be inlined by the compiler, as: 

inline int pred(int i, int n)
{
  printf("%d\n",i);
  return (i<n);
}

...

while (pred(i,n))
{
  i=i+1;
}

One more sophisticated example: 

(f a (progn b c))

would at first erroneously yield: 

f(a,{b; c;});

Also here the choice can be to either call the progn statement beforehand: 

  aarg=a;
  {
    b;
    barg = b;
  }
  f(aarg,barg);

This can become expansive when there are nested macro-like calls. Or, encapsulation can be performed, leading (again) to a slightly less efficient version due to function call overhead: 

inline int ftemp()
{
  b;
  return c;
}
f(a,ftemp());

In the compiler, the choice has to be made to either inline the code directly, or to allow the c++/Java compiler to inline the code. The above suggests that when generating code for a function body, the algorithm should first try to expand macro bodies, until it encounters a function call, and then expand the function calls as arguments to function calls. When it cannot expand a function argument because it is actually a macro expansion, it can either inline it itself, or generate an inlined method for it to allow the c++/Java compiler to inline the code at hand.

The concept of bootstrapping

To support a compuer algebra system like Yacas, it suffices to implement the small interpreter discussed in the beginning of this section. The interpreter will however be slow, as a lot of the functions required will have to e written in Lisp code and interpreted.

Bootstrapping can solve this problem. One starts with a small interpreter which can run the code, albeit slowly, and a (possibly poor) compiler is written and used to compile some base components of the system. At the second iteration, in stead of loading the files that were loaded the first time, the compiled versions can be loaded, which run a lot faster. This can be repeated many times, compiling a small sub-system, and loading the compiled version the next time the interpeter starts up, thus making the system faster at each iteration.

All that is then needed for a Yacas system is to have a little Lisp interpreter in place, plus a compiler to compile to the native platform, and 'bootstrap' the rest of the code into the system using the compiler. The system effectively 'ports' itself to the new platform, by generating efficient code for that platform.

For example, one could first start with compiling some utility functions, then compile support for parsing Yacas expressions and pattern matching, and then compile more powerful script code.

As a first step, a simple but fast compiler can be invoked, invoking more powerful compilers each time the system has faster components, resulting in faster and faster code.

Strong typing as an option for generating optimized code

Until now we have only discussed an untyped Lisp system, one where the system doesn't know the types of arguments passed or variables. An untyped Lisp is in principle enough for implementing a CAS. However, a small addition, declaration of types for parameters and variables, has a lot of advantages.

Take a function fact 

(defun fact (n)
   (if (equal n 0)
      1
      (* n (fact (+ n -1)))
)  )

Now, if we write this as 

(defun (fact INTEGER) ( (n INTEGER) )
   (if (equal n 0)
      1
      (* n (fact (+ n -1)))
)  )

Note that this just adds extra information, about types that should be passed in or returned. But the addition of type information greatly aids in translating (compiling) to other targets. For example, in c++ this bit of code could look like 

BigInteger fact(BigInteger n)
{
   if (n==0)
      return 1;
   else
      return n*fact(n-1);
}

Strong typing has the advantages of adding extra information the compiler can use to optimize code further, and strong typing also allows the compiler to give appropriate error messages when a function is called with incompatible arguments.

The step back to untyped Lisp can of course always be made, with a simple translation step removing typing information from expressions. We can keep a simple low-level Lisp untyped interpreter, write code in a typed version of the Lisp dialect, and in a translation phase remove the typing information so the untyped interpreter can understand it.

For the typed Lisp, the following functions are changed:

In addition, global variables will have to be declared explicitly, with global:

declare is not needed for the untyped interpreter, just for the typed Lisp code that will be used for conversion to c++/Java or other targets.

The typing system is very simple; no automatic type conversion is performed. In stead, the user is expected to call conversion routines. For instance, when a function sin expects a float, but an integer n is passed in, the calling sequence should ne something like (sin (int-to-float n)), and not (sin n). Some functions, like setf, will accept different types of arguments (the second argument to setf should be of the type of the variable the value is assigned to).

This is a very simple typing system, but this Lisp dialect is not meant to be really used for programming, just a basic minimum set. Overloading of functions and variable number of arguments are also not supported.

The following native types are supported in the basic Lisp dialect:

This list will be extended.

The compiler can also be made to accept non-typed variables, arguments and functions. The type of these objects should then default to OBJECT. However, this does not save the user from converting to appropriate type. For instance, if the type of some expression is not explicitly set to INTEGER, and it is used in addition, then a call to object-to-int is required every time the object is treated as an integer. Next to it being a nuissance for the programmer, it also makes the code less efficient.

The compiler is of course free to ignore types when it comes to translation. All objects should be able to pass as type OBJECT. The typing system is there to ensure efficiency of the generated code. The untyped interpreter described in the beginning of this book disregards all typing information whatsoever. The compiler does however have to check that arguments passed in have a valid type.

By the same token, the interpreter could be modified to handle the typed expressions, and just ignore the typing information. The interpreter could easily be extended to ignore the typing information given: 

In> (defun foo-untyped (n) (+ n 2))
Out> foo-untyped
In> (defun (foo-typed INTEGER) ( (n INTEGER) ) (+ n 2) )
Out> (foo-typed INTEGER )
In> (foo-untyped 3)
Out> 5
In> (foo-typed 3)
Out> 5

The change from <name> to (<name> <type>) is a trivial one. But this extra information can easily be mapped to strong typed compiled languages, which is why it is a useful step.

Indeed, 100 lines of Yacas (Yacas already had an interpreter at the time of writing of this document, version 1.0.53 had an interpreter written in c++) code can render the following: 

(defun foo 
    (n )
    (IntegerToObject 
      (+ 
        (ObjectToInteger n )2 )))

to 

LispObject foo(LispObject n)
{
   LispObject result ;
   {
      result  = IntegerToObject(ObjectToInteger(n)+2);
   }
   return result;
}

and 

(defun 
    (foo INTEGER )
    ((n INTEGER ))
    (+ n 2 ))

to 

BigInteger foo(BigInteger n)
{
   BigInteger result ;
   {
      result  = n+2;
   }
   return result;
}

The typing information in effect gives the compiler enough information to directly convert expressions to another syntax. The compiler thus just becomes a simple expression transformer.