How is Lisp dynamic and compiled?

Question

I don't understand how Lisp can be compiled and dynamic. For a language to be able to manipulate and modify and generate code, isn't it a requirement to be interpreted? Is it possible for a language to be completely compiled and still be dynamic? Or am I missing something? What is Lisp doing that allows it to be both compiled and dynamic?

Answer 1

Lisp is a wide family of language and implementations.

Dynamic in the context of Lisp means that the code has a certain flexibility at runtime. It can be changed or replaced for example. This is not the same as dynamically typed.

Compilation in Lisp

Often Lisp implementations have a compiler available at runtime. When this compiler is incremental, it does not need whole programs, but can compile single Lisp forms. Then we say that the compiler supports incremental compilation.

Note that most Lisp compilers are not Just In Time compilers. You as a programmer can invoke the compiler, for example in Common Lisp with the functions COMPILE and COMPILE-FILE. Then Lisp code gets compiled.

Additionally most Lisp systems with both a compiler and an interpreter allow the execution of interpreted and compiled code to be freely mixed.

In Common Lisp the compiler can also be instructed how dynamic the compiled code should be. A more advanced Lisp compiler like the compiler of SBCL (or many others) can then generate different code.

Example

(defun foo (a)
  (bar a 3))

Above function foo calls the function bar.

If we have a global function bar and redefine it, then we expect in Lisp usually that the new function bar will be called by foo. We don't have to recompile foo.

Let's look at GNU CLISP. It compiles to byte code for a virtual machine. It's not native machine code, but for our purpose here it is easier to read.

CL-USER 1 > (defun foo (a)
              (bar a 3))
FOO

CL-USER 2 > (compile 'foo)

FOO
NIL
NIL

[3]> (disassemble #'foo)

Disassembly of function FOO
(CONST 0) = 3
(CONST 1) = BAR
1 required argument
0 optional arguments
No rest parameter
No keyword parameters
4 byte-code instructions:
0     (LOAD&PUSH 1)
1     (CONST&PUSH 0)                      ; 3
2     (CALL2 1)                           ; BAR
4     (SKIP&RET 2)

Runtime lookup

So you see that the call to BARdoes a runtime lookup. It looks at the symbol BAR and then calls the symbol's function. Thus the symbol table serves as a registry for global functions.

This runtime lookup in combination with an incremental compiler - available at runtime - allows us to generate Lisp code, compile it, load it into the current Lisp system and have it modify the Lisp program piece by piece.

This is done by using an indirection. At runtime the Lisp system looks up the current function named bar. But note, this has nothing to do with compilation or interpretation. If your compiler compiles foo and the generated code uses this mechanism, then it is dynamic. So you would have the lookup overhead both in the interpreted and the compiled code.

Since the 70s the Lisp community put a lot of effort into making the semantics of compiler and interpreter as similar as possible.

A language like Common Lisp also allows the compiler to make the compiled code less dynamic. For example by not looking up functions at run time for certain parts of the code.

Answer 2

For a language to be able to manipulate and modify and generate code, isn't it a requirement to be interpreted?

No.

Is it possible for a language to be completely compiled and still be dynamic?

Yes.

Or am I missing something?

Yes.

What is Lisp doing that allows it to be both compiled and dynamic?

It is compiled on the fly, just like most implementations of java, and PyPy.

Answer 3

It can be compiled and dynamic in the same time because it's late-bound. You can run a list of functions and arguments and then add something to it and then run it again. Basically each part of the code can be run not just entire functions.