# 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:

- Parsing expressions when loading in a file. This is not a big performance penalty, as it only happens at startup, and might even be slower after compilation if more needs to be loaded from disk to run a compiled version of a program.
- When evaluating a variable, the interpreter needs to dynamically look in a list for the value of the variable. Compiled code can be written such that it can immediately access the value.
- When evaluating a function, looking up the function to call can be expensive. The function needs to be found in some container of functions, like a hashtable, which would run in O(log n) time, worst-case (best case O(1), when only a few functions are added).
- The overhead of building lists to be passed to a function, which then needs to decompose the arguments.
- Needless operations, like conversions from string representation to internal number representation and back.
- Inefficient execution of code that could be done more efficiently in native code. An `if` or `while` statement can be expected to run a lot more efficient when not interpreted.

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`, etc.

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), the 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 computer 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:

- `defun` and `defmacro`
- `let`

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

- `(global <var> <type>)` - declares a global variable.

`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:

- `OBJECT` - any Lisp expression
- `INTEGER` - Big (arbitrary precision) integer
- `FLOAT` - Big (arbitrary precision) float
- `STRING` - text string (should be encapsulated by double quotes when entered by the user)
- `STRINGBUFFER` - String, but not stored in any caches or hash tables. Stringbuffer is meant to be used to build up strings.
- `CHAR` - Array element of a string or string buffer. This is made a base type so that parsers and tokenizers can be written in the Lisp dialect itself, and efficiently compiled to native code. Char is represented as a string with one character.
- `HASHTABLE` - fast association of one object with another.

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 nuisance 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.