11

There are some programming languages, like the many dialects of Lisp, that allow for macro-metaprogramming: rewriting and altering sections of code before the code is run.

It is relatively trivial to write a simple interpreter for Lisp (mostly because there is only very little special syntax). However, I cannot understand how it would be possible to write a compiler for a language that allows you to rewrite code at-runtime (and then execute that code).

How is this done? Is the compiler itself basically included in the generated compiled program, such that it can compile new sections of code? Or is there another way?

1
  • 2
    Search for the documentation of Apple's JavaScript implementation, which consists of one interpreter and three compilers. That will give you some ideas.
    – gnasher729
    Commented Sep 30, 2016 at 8:58

7 Answers 7

12

Macros have the advantage to be expanded at compile time

The idea of Lisp macros is to be able to fully expand them at compile time. Then no compiler is needed at runtime. Most Lisp systems allow you to fully compile code. The compilation step includes the macro expansion phase. There is no expansion needed at runtime.

Often Lisp systems include a compiler, but this is needed when code is generated at runtime and this code would need to be compiled. But this is independent of macro expansion.

You will even find Lisp systems which don't include a compiler and even no full interpreter at runtime. All code will be compiled before runtime.

FEXPRs were code modifying functions, but were mostly replaced by Macros

In earlier times in the 60s/70s many Lisp systems included so-called FEXPR functions, which could translate code at runtime. But they could not be compiled before runtime. Macros replaced them mostly, since they enable full compilation.

An example of a macro interpreted and compiled

Let's look at LispWorks, which has both an interpreter and a compiler. It allows to mix interpreted and compiled code freely. The Read-Eval-Print-Loop uses the Interpreter to execute code.

Let's define a trivial macro. But the macro prints the code it gets called with, every time the macro runs.

CL-USER 45 > (defmacro my-if (test yes no)
               (format t "~%Expanding (my-if ~a ~a ~a)" test yes no)
               `(if ,test ,yes ,no))
MY-IF

Let's define a function which uses the macro from above. Remember: here in LispWorks the function will be interpreted.

CL-USER 46 > (defun test (x y)
               (my-if (> x y) 'larger 'not-larger))
TEST

If you look above, the Lisp system only printed the function name. The macro did not run - otherwise the macro would have printed something. So the code is not expanded.

Let's run the TEST function using the Interpreter:

CL-USER 47 > (loop for i below 5 collect (test i 3))

Expanding (my-if (> X Y) (QUOTE LARGER) (QUOTE NOT-LARGER))
Expanding (my-if (> X Y) (QUOTE LARGER) (QUOTE NOT-LARGER))
Expanding (my-if (> X Y) (QUOTE LARGER) (QUOTE NOT-LARGER))
Expanding (my-if (> X Y) (QUOTE LARGER) (QUOTE NOT-LARGER))
Expanding (my-if (> X Y) (QUOTE LARGER) (QUOTE NOT-LARGER))
Expanding (my-if (> X Y) (QUOTE LARGER) (QUOTE NOT-LARGER))
Expanding (my-if (> X Y) (QUOTE LARGER) (QUOTE NOT-LARGER))
Expanding (my-if (> X Y) (QUOTE LARGER) (QUOTE NOT-LARGER))
Expanding (my-if (> X Y) (QUOTE LARGER) (QUOTE NOT-LARGER))
Expanding (my-if (> X Y) (QUOTE LARGER) (QUOTE NOT-LARGER))
(NOT-LARGER NOT-LARGER NOT-LARGER NOT-LARGER LARGER)

So you see that for some reason the macro expansion is run twice for each of the five calls to test. The macro is expanded by the interpreter every time the function TEST is called.

Now let's compile the function TEST:

CL-USER 48 > (compile 'test)

Expanding (my-if (> X Y) (QUOTE LARGER) (QUOTE NOT-LARGER))
TEST
NIL
NIL

You can see above that the compiler runs the macro once.

If we now run the function TEST, no macro expansion will happen. The macro form (MY-IF ...) has already been expanded by the compiler:

CL-USER 49 > (loop for i below 5 collect (test i 3))
(NOT-LARGER NOT-LARGER NOT-LARGER NOT-LARGER LARGER)

If you used some other Lisps like SBCL or CCL, they will compile everything by default. SBCL has in new versions also an interpreter. Let's do the example from above in a recent SBCL:

Let's use the new SBCL interpreter:

CL-USER> (setf sb-ext:*evaluator-mode* :interpret)
:INTERPRET

CL-USER> (defmacro my-if (test yes no)
           (format t "~%Expanding (my-if ~a ~a ~a)" test yes no)
           `(if ,test ,yes ,no))
MY-IF
CL-USER> (defun test (x y)
           (my-if (> x y) 'larger 'not-larger))
TEST
CL-USER> (loop for i below 5 collect (test i 3))

Expanding (my-if (> X Y) 'LARGER 'NOT-LARGER)
Expanding (my-if (> X Y) 'LARGER 'NOT-LARGER)
Expanding (my-if (> X Y) 'LARGER 'NOT-LARGER)
Expanding (my-if (> X Y) 'LARGER 'NOT-LARGER)
Expanding (my-if (> X Y) 'LARGER 'NOT-LARGER)
(NOT-LARGER NOT-LARGER NOT-LARGER NOT-LARGER LARGER)
CL-USER> (compile 'test)

Expanding (my-if (> X Y) 'LARGER 'NOT-LARGER)
TEST
NIL
NIL
CL-USER> (loop for i below 5 collect (test i 3))
(NOT-LARGER NOT-LARGER NOT-LARGER NOT-LARGER LARGER)
CL-USER> 
15

You are confusing two different concepts in your question. Macros are not about compiling code at runtime. They are the exact opposite: they are about running code at compile time.

So, in this case, the problem is the opposite one: it's not about making the compiler part of the program, rather it is about making the macro-program part of the compiler. You can do that by embedding an interpreter in the compiler, or use staged compilation, where you compile the macros first, then link them into the compiler, then compile the code.

In your second paragraph, you ask about a different thing, basically eval:

How is this done? Is the compiler itself basically included in the generated compiled program, such that it can compile new sections of code?

Yes, that is one possibility.

Or is there another way?

There are other ways:

  • instead of making the compiler a part of the program, you can include it in the runtime system
  • you don't have to use the same compiler, you could use a different one (e.g. have one compiler which is very big, very complex, very slow and uses a large amount of memory, but generates very small, efficient, fast, high-performance, aggressively optimized code, and a second one that you ship either in the runtime system or as part of the compiled program, that is small, simple, fast, lightweight, so that it doesn't "steal away" too many resources (CPU time and memory) from the user program, however it may generate less efficient code
  • or you could use an interpreter, and again, ship it as part of the program or as part of the runtime system
9

A typical "compiling lisp" will include the compiler in a bundled image. Furthermore, most (although not all) function calls are done through symbol indirections (basically, when the compiler sees (+ a b), it emits code to "find symbol +", then "call the function it points to").

This means that function re-definition during program execution is possible by generating executable code, somewhere in memory, then update the function pointer in the symbol that refers to your function.

This is one reason why "small free-standing binaries" generated from a Common Lisp compiler tend to be large. However, there's a technique usually called "tree-shaking" that can analyse the resulting compiled program and remove any bits of the standard image that are never referenced and in such a binary there would be no compiler included, with no ability to compile code run-time. You may still be able to have run-time code modification, by loading another (compiled) file, since that can be implemented simply in terms of "put bytes in RAM, update pointers in symbols".

4

Yes. The runtime have to include an interpreter or compiler. This is why eval is traditionally is a feature of interpreted languages, since the runtime of these languages (by definition) contains an interpreter anyway. Now if the language actually interprets the source or just-in-time compiles it and then executes it (use use various intermediate steps like a bytecode format) - this is basically implementation details. The bottom line is the runtime have to able to take source code and execute it.

10
  • 3
    What is an "interpreted language"? Languages aren't interpreted or compiled. They just are. Interpretation and compilation are traits of the, well, interpreter or compiler, not the language. Every language can be compiled and every language can be interpreted. For example: ECMAScript has eval, yet, V8 is purely compiled, there is no interpretation going on, ever. Commented Sep 30, 2016 at 14:47
  • 1
    @JörgWMittag: Er yes, this is exactly what I say - whether the code is actually interpreted or just-in-time compiled or any combination thereof is an implementation detail, as long as the runtime is able to take source code and execute it in the fly. But historically eval() originated with interpreted languages, because you basically get it for free, while it would be a major task to add eval() to say C. JavaScript (like Lisp) also originated as an interpreted language, even though multiple implementations with various compilation strategies exist for either language today.
    – JacquesB
    Commented Sep 30, 2016 at 16:48
  • 1
    @JörgWMittag: I get your point that a language may have multiple implementations and therefore is not in itself compiled or interpreted. But while this is a technically correct viewpoint, in reality languages are typically designed with a specific execution strategy in mind, and this explains many design choices. Ignoring this only makes programming languages more confusing.
    – JacquesB
    Commented Sep 30, 2016 at 17:00
  • 3
    @JörgWMittag The phrase "interpreted language" is a common, long standing and widely understood phrase. It doesn't matter if some languages can be either, "interpreted language" is a common term to indicate languages that are usually intepreted. See en.m.wikipedia.org/wiki/Interpreted_language for more info. If you're concerned for some reason about the lack of 100℅ pedantic accuracy in an old and widely used term, I dunno, go write an influential book about it or something to try and change general CS vocabulary. Folks with a modest CS background will understand that phrase.
    – Jason C
    Commented Oct 1, 2016 at 16:55
  • 1
    @RainerJoswig: "Interpreted language" is a perfectly fine term to describe a language which is only interpreted. I don't see the problem unless you are being deliberately obtuse. Eval is not tied to an interpreter which was precisely my point in the original answer, but as far as I know it originated with an interpreter, since the first Lisp implementation with eval was an interpreter. If this is factually incorrect please point out how and I will have learnt something new!
    – JacquesB
    Commented Oct 8, 2016 at 13:57
4

Clearly, runtime code generation is incompatible with ahead-of-time compilation. Therefore, the language runtime environment must include some mechanism to dynamically execute code: either an interpreter or a just-in-time compiler. Since an interpreter would duplicate effort, many compiled implementations of such languages prefer JIT compilation.

In any case, incremental compilation requires that compiled code retains enough meta-information so that new code can be executed in this context. For example, variables may not be optimized away when their scope includes an eval. However, this can be easily checked with static analysis during compilation of the surrounding code. An eval can then be implemented as a late-bound call to a separate function that is going to be compiled at run time. This avoids having to actually change already-compiled code.

This is not just an issue with Lisp. Modern high-performance JITting JavaScript implementations such as V8 also have to deal with evals.

Note that eval, macros, and incremental compilation all pose the same problem for the purpose of this discussion.

1
  • There is no need for a JIT. The runtime just needs to include an AOT compiler. Lisp systems often include both an Interpreter (better debugging) and one or more AOT compilers (better speed). OTOH JIT compilers are rarely used in Lisp. In many/most Lisp implementations EVAL will call an incremental AOT compiler. Commented Oct 5, 2016 at 16:43
1

I cannot understand how it would be possible to write a compiler for a language that allows you to rewrite code at-runtime (and then execute that code). How is this done? Is the compiler itself basically included in the generated compiled program, such that it can compile new sections of code? Or is there another way?

You say you cannot understand how it is done and then clearly describe how it is done; I think your statement that you cannot understand it is simply false. You understand it just fine.

This is exactly what I and my colleagues did when implementing expression trees in C# 3. You can say:

var p = Expression.Parameter(typeof (string), "p");
var len = Expression.Property(p, "Length");
var ten = Expression.Constant(10);
var lt = Expression.LessThan(len, ten);
var expr = Expression.Lambda<Func<string, bool>>(lt, p);

and hey presto, we have an object at runtime that represents

(string p) => p.Length < 10

and when we compile it:

var f = expr.Compile();
Console.WriteLine(f("hello")); // true

How does expr.Compile work? I wrote a compiler that spits out new IL at runtime and jits it, on the basis of the contents of the expression tree. expr.Compile runs a compiler; this should not be too surprising!

We had the distinct benefit of not having to write another parser, as the expression tree is already an abstract syntax tree. But if had wanted to be able to take the string "(string p) => p.Length < 10" and turn it into that expression tree, I assure you we would have simply written a parser that produced the expression tree, and then run that through the expression tree compiler.

It's just a lot of work; it took me the better part of a year to get lambdas all working right. There's no magic to it. And of course we all stand on the shoulders of giants; already having a runtime, with a mechanism for spitting out new IL at runtime and jitting it, was of vital importance to this feature.

0

However, I cannot understand how it would be possible to write a compiler for a language that allows you to rewrite code at-runtime (and then execute that code).

In fact, Lisp macros come out of solving this problem.

In a Lisp interpreter (not compiler) all evaluation can be handled by dispatching functions. The special operators like cond are implemented as functions which receive the unevaluated syntax. In ancient Lisp terminology, these are "fexprs". Regular functions that don't do anything meta-syntactic like cons or + are "fsubrs"; these are called with expressions reduced to values.

Meta-programming was possible by allowing the Lisp program to define its own fexprs.

However, this flexibility was found to interfere with compilation.

A compiler walks the code and recognizes the special operators that occur; instead of calling their fexprs, it calls alternative versions of these functions (built into the compiler) which translate those expressions to code. The compiler knows how to handle cond and let and whatnot because these symbols have bindings to subroutines in the compiler that implement their respective translation strategies.

If a program defines new fexprs for interpretation, and these are used in that program, then that leaves the compiler unable to compile that program. The program has only done half the job; it has provided code for interpreting some new kinds of operators, but not for compiling them.

If we have taught the interpreter some new operators via fexprs, how can we teach the compiler to handle those same operators? The answer is macros! Macros are the compiler's analog of fexprs; they extend the compiler into recognizing program-defined operators. They do that by providing a translation of their respective constructs into code that no longer contains any of the macro-defined operators. After being processed by macros, the code consists only of the built-in special operators, and function calls. The compiler then walks this and translates it, completely ignorant of the existence of user-defined operators.

It then turns out that fexprs are not needed because macros can just be run for interpreted code also. (At least not those fexprs for which macros can be written; fexprs can do some exotic, dynamic things that do not easily convert into macros.)

When macros are introduced, code has to be processed in an additional pass: expansion. This expansion is performed prior to compilation. Expansion is just another compiler pass. All compilers have passes that convert a program from one shape to another; macro expansion is just a thing of that sort. It has nothing to do with self modification (changing the code at run-time).

Lisp macros in dialects like ANSI Lisp or Emacs can perpetrate self-modification of the source code, because they have access to their own syntax as a data structure, and that data structure happens to be made of mutable cons cells. Macros which mutate their syntax will likely behave badly; such a situation is not well-defined by ANSI Lisp. It is of these kinds of programs that we ask the question "How can this be compiled? What does it mean to compile this?" Mutation of syntax is not the basis for the macro paradigm; the paradigm is that macros compute a new object (new piece of syntax) from their inputs, without mutating those inputs.

So in summary, if a language allows meta programming (introspection over its syntax and behaviors dependent on that) we need that meta-programming to be done with macros if we want it to be easily compilable. So, quite the opposite, macros do not hinder compiling, but support it.

Lisp programs do allow code to be changed at run-time, but not via self-modifying code. How a Lisp program can upgrade itself without stopping and re-starting the world is by loading new versions of functions (and other definitions). A function is just an object associated with a symbol. We can replace that object with a new one, and then calls to that symbol call the new function. If the old function is still in use (being executed), that's okay; we can let that execution finish. When the old function is no longer being executed or referenced in any way, it turns into garbage. In other words "self-modifying environment/image" not "self-modifying code". A self-modifying image provides the possibility of a disciplined approach to in-service upgrades.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.