Are there Lisp native code compilers?

Question

Are there native code compilers for Lisp? To which extent can it even be compiled, with all it's dynamic nature, garbage collection, macros and what else?

Answer 1

You bet. Chez Scheme (a commercial compiler) is one of the better ones. Gambit and Larceny are research compilers that also generate native code.

Answer 2

There are huge numbers of Lisp compilers to native code, see http://www.thefreecountry.com/compilers/commonlisp.shtml and e.g. the CMU Common Lisp Compiler.

Answer 3

Yes. See http://en.wikipedia.org/wiki/Common_Lisp . It mentions that Steel Bank Common Lisp (a fairly popular implementation) compiles everything to native by default. The fact that garbage collections and such are used is not an obstacle to native code. That just means some kind of runtime is needed. But so what? Even C has a runtime.

Answer 4

There a many Lisp compilers that compile to native code. CMUCL, SBCL, ClozureCL are known among the open-source Lisp compilers.

Garbage collection is not an obstacle to compilation to native code. Also, in some cases Lisp can use stack allocation that does not need GC and may greatly improve performance (using dynamic-extent declaration; at least SBCL supports this).

Macros (and any code that is run at read-time (read macros and read-eval), compile-time (macros, compiler macros, code in eval-when)) require incremental compilation (first macro-function has to be compiled, and then code that uses macro can be compiled). This somewhat complicates compilation, but it is not too much a problem. Also, macros and compiler macros even help the compilation process because they allow programmer to write code generators and code optimizers, essentially customizing the compiler.

So the compiler is more complicated than some simpler languages (like C), but complexity is manageable (see Design of CMU Common Lisp).

Dynamic nature of Common Lisp is controllable and designed to be effeciently compilable. In contrast to some other dynamic languages (e.g., Python), dynamism is restricted (e.g., you can not take the current lexical environment at run-time) which give compilers some freedom to optimize.

Answer 5

Many Lisp compilers compile to 'native' code. 'Native' means here 'machine code' (x86 in 32bit or 64bit mode, PowerPC, SPARC, ...).

Other questions:

• can 'non-native code' compilers generate single file executables? -> Yes.

• can 'native code' compilers generate single file executables? -> Yes.

• how 'native' is 'native'? -> Lisp system will most of the time have their own internal data structure layout (CLOS classes), their own error handling ('conditions'), their own memory management (garbage collection), their own libraries, ...

• can Lisp run without a GC? -> Usually not. There are exceptions.

• what about the application size? -> By default simple ways to generate a Lisp application often lead to large executables. The executables include the whole Lisp including its library, names of all symbols, information about argument lists to functions, the compiler, the debugger, source code location information, and more. Some compilers generate also largish code (SBCL is an example).

• are there ways to shrink application sizes? -> That depends on the Lisp system. Commercial Lisp systems like LispWorks and Allegro CL can. For application delivery, they can remove unused code, remove debugging information, remove parts of the Lisp (libraries, compiler, ...) and more.

• can Common Lisp systems generate small executables. I mean really small. -> Not really. The executables are either large (CCL) or very large (SBCL). Some Common Lisp systems can generate medium sized executables. But none can really generate small executables.

• is there really no way to generate really small executables? -> Years ago compilers were written which generate relatively compact C code without large libraries. But these compilers are not maintained.

• are there other ways to shrink executables? -> If you want to run more than one Lisp application, it makes sense to reuse runtime, compiler, libraries in one or more shared libraries. That way the code to deliver will be smaller, when a runtime is already installed as a shared library (or similar).

• how do I find out what the Lisp I'm using supports as application delivery? -> read the manual and ask other users.

• okay, so most Common Lisp systems can't generate tiny applications. Are there other Lisp dialects who can generate smaller executables. -> Yes, some Scheme compilers can.

• how does Common Lisp handle runtime errors? -> depends on the way you generate the application. By default you get a Lisp debugger (unless you have removed it). But you can use your own error handling routines in your application and can prevent the debugger from appearing.

• what are Common Lisp particular strengths, when generating really small executables isn't one? -> you can include a REPL to interact with the application, you can use an included compiler to compile new (or changed code) at runtime, you can use the FASL (compiled Lisp code) loader to LOAD additional native code at runtime (think plugins, patches, extensions, ...), sophisticated error handling including error recovery is possible, ...

• but Lisp is dynamic? -> Yes, dynamic means that it can change lots of things during runtime. For example in Common Lisp you can change a CLOS class at runtime and the class' instances will adopt to the changes. But the various Lisp systems have different ways to remove some of the dynamic features. Structures are less dynamic than CLOS classes. You can declare types and compile with different optimization settings (speed, safety, debug, ...). You can inline functions. And more.

A simple way to see the compiled code for functions is to use the Common Lisp function DISASSEMBLE. Example in Clozure CL on an x86-64 Mac

? (defun foo (x y) (if (= x y) (sin x) (* y (cos x))))
FOO
? (disassemble 'foo)
L0
  [0]     (leaq (@ (:^ L0) (% rip)) (% fn))
  [7]     (cmpl ($ 16) (% nargs))
  [10]    (jne L209)
  [16]    (pushq (% rbp))
  [17]    (movq (% rsp) (% rbp))

...

  [172]   (pushq (@ 77752))
  [179]   (jmpq (@ 10 (% temp0)))
L189
  [189]   (leaq (@ (:^ L0) (% rip)) (% fn))
  [196]   (jmpq (@ .SPNVALRET))
L209
  [209]   (uuo-error-wrong-number-of-args)
NIL

The output of DISASSEMBLE obviously depends on the processor architecture, the OS, the used Lisp compiler and the current optimization settings.

Answer 6

Don't forget Chicken Scheme.