A gentle introduction to Compile-Time Computing — Part 2

So what do you use compile-time computing for?

Over time this blog will cover these examples:

1. you want to have a structure with multiple fields. There will be member functions for arithmetic (+, -, *, /) which should be applied to all fields. How do you make sure that all the fields are covered for all operators? Do you want to write all these methods by hand, hoping you never forget a field, and neither do the people who subclass later?
2. code literals, let’s say string-based regular expressions. Do you want to compile them at runtime, at startup? Why? This will take unnecessary extra time, if they are known at compile time. But they might not be known at compile time. In Lisp you write a macro that compile-time compiles a regexp if it is a literal, and defers to runtime if not. As an additional benefit, not only do you save run time here, you also enable warnings about broken regexp literals at compile time. Many languages do that, say Perl. But they build it into the language and the compiler. In Lisp you can do it without modifying the compiler.
3. Same for e.g. printf format string checking (wrt the type and number of object arguments). In Common Lisp you can implement that kind of compile-time checking without modifying the compiler. Now, what you really want is that you write your own warning-emitters such as those printf format string warnings and regex checks, and you can supply them to the users of your library without having to ship them a hacked up compiler. With real compile-time computing you can do that.
4. let’s look at the effort that it took to turn non-OO languages into object-oriented languages. How much compiler support was needed? Looks pretty ugly to me. Is C++ even finished? Well, C++ kind of gave up on OO instead, didn’t they? With compile-time computing as implemented in Common Lisp you can turn a structs-n-functions language into an object-oriented one without modifying the compiler. In fact that is what Common Lisp did to get OO. You can add compiler support for speed optimizations later, but you don’t have to. The OO language that the CL community implemented was pure macros at first. Or let’s say you hate OO programming and have an idea for something better. Would you like to hack up a compiler for a new top-level meta-language (such as templates) or do you want to do it in the same base language? This example will mostly cover existing CLOS packages. Oh, and other Common Lisp OO packages that you can use alternatively, even mixed into the same program.
5. numerical source code literals that carry units, and where conversion from the written down number-with-unit to the internally used unit is done at compile time if known at compile time (and at runtime otherwise). Checking of unit compatibility is skipped if it can be proven at compile time. You don’t have to slow down code by dragging around the unit information if unit compatibility was proven at compile time. Don’t underestimate the significance of this. We (humanity) blew up lots of stuff including spaceships and water ships because of the scientific units mess. Let’s make it safe.
6. you wrote down (in code) a mathematical formula, solved by one variable. Your program also needs the same formula solved by another variable. Why would you solve this on a piece of paper and then write down a second function into the source code? The computer should be smart enough that you can pass it the function once and request that it generates code for the variants, solved by different variables of that one definition. One source code definition, several compiled functions to call. It keeps you from making human errors, and it is a great help if you find that your formula needs adjusting later (otherwise known as “not again…”). Instead of multiple places to edit, you have one place to control this one formula and all its variants. Compile-time computing in Common Lisp is powerful enough to do this. Now having said that… we are pushing the envelope of what I actually implemented so far. This is fairly advanced and not quick to write. I hope that I can use Maxima for this. We’ll see by the time I get to this part and you get to have a look at what tackling a problem like this is like.
7. Avoiding Reflection at runtime. This won’t be a Common Lisp example. I’ll just rant a bit about how bad it is to replace compile time computing with reflection at runtime. Apart from dropping all the speed on the floor, you are also opening your previously statically typed and compiled program to runtime errors. For added spice, imagine that those structs reflected on at runtime represent database schemas, and now something got out of sync and throws runtime error messages in production, instead of using reflection at compile time, with checking. Yes, your syntax-correct CL source code can do (checkagainst (read (/bin/sh “./gimmetheschema”)) at compile time. Runtime reflection is a really bad substitute here and it wouldn’t be required for most uses if you had compile time computing (this is a more general case of example #1 above).
8. Let’s hope I make it to the more esoteric items. One such thing is that Common Lisp is so powerful that if your compiler was too dumb to have inline functions you can fix that yourself. You write a macro that translates your function definition. It walks it statement by statement and re-writes the function as a macro. Then it puts the macro version into the to-be-compiled code and there you are. Now it’s inline, machine code wise. This is of course crazy in multiple ways, and I don’t think I can show you the ITA code we had that did this. Oh. Nonono, this isn’t theory, as much as I wish. We had that. It illustrates the raw expressive power of the language. In milder climates I use this capability to change functions from being inline or not-inline on the fly, during compilation, based on any random criteria I choose (compiled code size, local exits close to the beginning, number of times called in benchmarks), without having to use any external tools (and without having to move those functions between source code files).

Error handling

Throughout this series you will also gradually realize one of the major advantages of having the same language at compile and at run time. It is error handling. All these macros that you use to achieve the above, they are regular Common Lisp code. The entire language is available, including all libraries you ever wrote for it. And all the error handling capabilities are available at compile time. This isn’t some crazy C++ template thing giving you an error message^H^H^Hnovel that needs a web app to translate into something readable. With real compile-time computing the compile time error messages come out of your code written in your primary language, and the compile time error messages are as clear or unclear as your runtime ones. And yes, you have, at compile time, backtraces, debuggers, step-by-step evaluation, inspection, and regular data structures. You can even use your regular profiler to fix performance bugs that slow down compilation too much.

You use the regular Lisp debugger on that compile time Lisp code. Ever tried to use gdb on C++ template expansion?

Objectives

Overall you’ll see how the examples implement our primary goals:

• avoid repetition in human-written/to-be-changed-by-humans/diffed source code.
• do as much work as you can at compile time (not run time) because it is safer (warnings from the compiler, and warnings from your own code running at compile time) and makes the program run faster(*).

While also going for secondary goals:

• make source code with complicated items (say complex literals) as easy to read as possible, without having to write custom lexers and parsers. In case it isn’t obvious by now, in Common Lisp you can express any data structure that is possible at runtime as a source code literal. That includes graphs and trees.
• keep source code diffs over the change history small and readable. No boilerplate and huge cascading diffs from originally small changes drowning out the real change with noise. Always remember that you might want to read this (much) later with 15 years worth of changes piled on. The worst of this are languages that require so much change-noise boilerplate that people have their IDE do the boilerplate changes for you. That’s nice for next week’s deadline, but it doesn’t address the follow-changes-in-15-years perspective.
• don’t be forced into object-oriented programming when it doesn’t suit the project at hand - just because your compiler happens to only have support for OO paradigms (kudos to C++ to open up the language to other approaches, BTW).

Stand by while I polish, re-think, and explain all this “real quick.” If you want deeper introductions to these topics in the meantime, there are two books I particularly recommend:

Paul Graham’s “On Lisp”. This is the Lisp book with the most emphasis on Macros. It is now freely available (there also is a paper book): http://www.paulgraham.com/onlisp.html

Peter Norvig’s “Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp”. This book is much lighter on complicated Lisp macros than “On Lisp” is. The beauty here is that Peter Norvig show you the power of this in an element way, expressing ideas and assumptions the way that you want and that keeps things changeable. Paper book only: https://www.amazon.com/Paradigms-Artificial-Intelligence-Programming-Studies

Footnotes:

(*) to go to extremes, compile-time computing done right might eliminate runtime altogether, if no unknown data that actually influences output flows in. That isn’t theory either, check out Jeffrey Mark Siskind’s “Stalin” compiler for Scheme. https://engineering.purdue.edu/~qobi/software.html

Thank you again to dcooper8@ for editing and general help.

This is part 2 of a series. Part 1 is here: https://medium.com/@MartinCracauer/a-gentle-introduction-to-compile-time-computing-part-1-d4d96099cea0

Part 3 is upcoming.