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?

Flittermouse

Just the same way as, say, tcc is "dynamic". You only need a compiler available in runtime. – Quartered

@Quartered and a smart linker and loader. – Beeler

@WillNess, tcc does not need any linkers, it can emit binary code straight into memory. – Quartered

@Quartered great! so TCC is all-in-one. :) – Beeler

Might want to see this too: Which languages are dynamically typed and compiled (and which are statically typed and interpreted)? – Wingback

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.

Crissum

Isn't this an incredibly long-winded way of saying that Common Lisp is late-bound? – Orchestrion

@Marcin: now even more long-winded. – Crissum

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.

Orchestrion

Not necessarily JIT. Lisp code can be compiled at arbitrary points during program execution, not necessarily "just in time" when it is executed. – Cogwheel

SBCL compiles immediately. I am not sure whether this counts as 'on the fly'. – Phonometer

@ThomasBartscher Compiled immediately to native code when you have it generate a fasl? – Orchestrion

I don't know but I think that's the case. Don't know any reason why it wouldn't when it's always compiling immediately in the REPL either way. – Phonometer

@ThomasBartscher Fair enough. – Orchestrion

It's more like "compile on command" or as I like to call it, COCO. – Orontes

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.

Chancelor