How can Lisp be both dynamic and compiled?

Question

Okay, so first to get this out of the way: I have read the following answer:

How is Lisp dynamic and compiled?

but I don't really understand its answer.

In a language like Python, the expression:

x = a + b

Cannot really be compiled, as for the "compiler" it would be impossible to know the types of a and b (as the types are known only at run-time), and therefore how to add them.

This is what makes a language like Python impossible to compile without type declarations, correct? With declarations, the compiler knows that e.g. a and b are integers, and therefore knows how to add them, and translate that into native code.

So how does:

(setq x 60)
(setq y 40)
(+ x y)

work?

Compiled being defined as native ahead-of-time compilation.

EDIT

In reality, this question is more about whether dynamic languages without type declarations can be compiled, and if so, how?

EDIT 2

After much research (i.e. avid Wikipedia browsing) I think I understand the following:

• dynamic typed languages are languages where the types are checked at run-time
• static typed languages are languages where the types are checked when the program is compiled
• type declarations allow the compiler to make the code more efficient because instead of making API calls all the time it can use more native 'functions' (that is why you can add type declarations to Cython code to speed it up, but don't have to, because it can still just call the Python libraries in the C code)
• there are no datatypes in Lisp; therefore no types to be checked (the type is the data itself)
• Obj-C has both static and dynamic declarations; the former are type-checked at compile time, the latter at run-time

Correct me if I am wrong on any of the above points.

Answer 1

Example Code:

(setq x 60)
(setq y 40)
(+ x y)

Execution with a Lisp interpreter

In an Interpreter based Lisp above would be Lisp data and the interpreter looks at each form and runs the evaluator. Since it is running of the Lisp data structures, it will do this every time when it sees above code

• get the first form
• we have an expression
• it is a SETQ special form
• evaluate 60, the result is 60
• look up the place for the variable x
• set the variable x to 60
• get the next form... ...
• we have a function call to +
• evaluate x -> 60
• evaluate y -> 40
• call the function + with 60 and 40 -> 100 ...

Now + is some piece of code which actually finds out what to do. Lisp typically has different number types and (almost) no processor has support for all those: fixnums, bignums, ratios, complex, float, ... So the + function needs to find out what types the arguments have and what it can do to add them.

Execution with a Lisp compiler

A compiler will simply emit machine code, which will do the operations. The machine code will do everything the interpreter does: checking the variables, checking the types, checking the number of arguments, calling functions, ...

If you run the machine code, it is much faster, since the Lisp expressions don't need to be looked at and interpreted. The interpreter would need to decode each expression. The compiler has that done already.

It is still slower than some C code, since the compiler does not necessarily know the types and just emits the fully safe and flexible code.

So this compiled Lisp code is much faster than the interpreter running the original Lisp code.

Using an optimizing Lisp compiler

Sometimes it is not fast enough. Then you need a better compiler and tell the Lisp compiler that it should put more work into the compilation and create optimized code.

The Lisp compiler might know the types of the arguments and variables. You can then tell the compiler to omit runtime checks. The compiler can also assume that + is always the same operation. So it may inline the necessary code. Since it knows the types, it may only generate the code for those types: integer addition.

But still the semantics of Lisp are different from C or machine operations. A + not only deals with various number types, it will also automatically switch from small integers (fixnums) to large integers (bignums) or signal errors on overflows for some types. You can also tell the compiler to omit this and just use a native integer addition. Then your code will be faster - but not as safe and flexible as normal code.

This is an example for the fully optimized code, using the 64Bit LispWorks implementation. It uses type declarations, inline declarations and optimization directives. You see that we have to tell the compiler a bit:

(defun foo-opt (x y)
  (declare (optimize (speed 3) (safety 0) (debug 0) (fixnum-safety 0))
           (inline +))
  (declare (fixnum x y))
  (the fixnum (+ x y)))

The code (64bit Intel machine code) then is very small and optimized for what we told the compiler:

       0:      4157             push  r15
       2:      55               push  rbp
       3:      4889E5           moveq rbp, rsp
       6:      4989DF           moveq r15, rbx
       9:      4803FE           addq  rdi, rsi
      12:      B901000000       move  ecx, 1
      17:      4889EC           moveq rsp, rbp
      20:      5D               pop   rbp
      21:      415F             pop   r15
      23:      C3               ret   
      24:      90               nop   
      25:      90               nop   
      26:      90               nop   
      27:      90               nop   

But keep in mind above code does something different from what the interpreter or safe code would do:

• it only calculates fixnums
• it does silently overflow
• the result is also a fixnum
• it does no error checking
• it does not work for other numeric datatypes

Now the unoptimized code:

       0:      49396275         cmpq  [r10+75], rsp
       4:      7741             ja    L2
       6:      4883F902         cmpq  rcx, 2
      10:      753B             jne   L2
      12:      4157             push  r15
      14:      55               push  rbp
      15:      4889E5           moveq rbp, rsp
      18:      4989DF           moveq r15, rbx
      21:      4989F9           moveq r9, rdi
      24:      4C0BCE           orq   r9, rsi
      27:      41F6C107         testb r9b, 7
      31:      7517             jne   L1
      33:      4989F9           moveq r9, rdi
      36:      4C03CE           addq  r9, rsi
      39:      700F             jo    L1
      41:      B901000000       move  ecx, 1
      46:      4C89CF           moveq rdi, r9
      49:      4889EC           moveq rsp, rbp
      52:      5D               pop   rbp
      53:      415F             pop   r15
      55:      C3               ret   
L1:   56:      4889EC           moveq rsp, rbp
      59:      5D               pop   rbp
      60:      415F             pop   r15
      62:      498B9E070E0000   moveq rbx, [r14+E07]   ; SYSTEM::*%+$ANY-CODE
      69:      FFE3             jmp   rbx
L2:   71:      41FFA6E7020000   jmp   [r14+2E7]        ; SYSTEM::*%WRONG-NUMBER-OF-ARGUMENTS-STUB
  ...

You can see that it calls a library routine to do the addition. This code does all the Interpreter would do. But it does not need to interpret Lisp source code. It's already compiled to the corresponding machine instructions.

Why is compiled Lisp code fast(er)?

So, why is compiled Lisp code fast? Two situations:

• unoptimized Lisp code: the Lisp runtime system is optimized for dynamic data structures and code does not need to be interpreted

• optimized Lisp code: the Lisp compiler needs information or infers it and does a lot of work to emit optimized machine code.

As a Lisp programmer you would want to work with unoptimized, but compiled, Lisp code most of the time. It is fast enough and offers a lot comfort.

Different execution modes offer choice

As a Lisp programmer we have the choice:

• interpreted code: slow, but easiest to debug
• compiled code: fast at runtime, fast compilation, lots of compiler checks, slightly more difficult to debug, fully dynamic
• optimized code: very fast at runtime, possibly unsafe at runtime, lots of compilation noise about various optimizations, slow compilation

Typically we only optimize those portions of code which need the speed.

Keep in mind that there are a lot of situations where even a good Lisp compiler can't do wonders. A fully generic object-oriented program (using the Common Lisp Object System) will almost always have some overhead (dispatching based on runtime classes, ...).

Dynamically typed and Dynamic are not the same

Note also that dynamically typed and dynamic are different properties of a programming language:

• Lisp is dynamically typed because type checks are done at runtime and variables by default can be set to all kinds of objects. For this Lisp also needs types attached to the data objects themselves.

• Lisp is dynamic because both the programming language Lisp and the program itself can be changed at runtime: we can add, change and remove functions, we can add, change or remove syntactic constructs, we can add, change or remove data types (records, classes, ...), we can change the surface syntax of Lisp in various ways, etc. It helps that Lisp is also dynamically typed to provide some of these features.

User interface: compiling and disassembling

ANSI Common Lisp provides

• two standard functions to compile code: compile and compile file
• one standard function to load source or compiled code: load
• one standard function to disassemble code: disassemble