back




August 2016

For a while I was convinced the most powerful programming abstraction was the macro: a long instruction that generates a pattern of code. Now I'm not so sure. I saw something more powerful. The code walker: a program that changes a program.

The main difference between a macro and a code walker is coverage. A macro can change only the parts of the program that call the macro. [1] Whereas a code walker can change the whole program.

There's also a difference in impact. A code walker can generate code that a macro simply can't. Since it makes a pass over the whole program, a code walker learns more about the program than a macro, and as a result generates code that a macro wouldn't know how.

Plus you have to manually edit the program to call the macro. A code walker saves this manual step by editing the program automatically.

Code walkers don't seem very useful if we go by how common it is to write them. Most programmers never write one. Just as macros don't seem very useful if one programs only with functions. So what if code walking can save a manual step and change a program completely and in ways macros can't, if it's something I rarely need to do?

Because in the cases where you need it there is no other option.

And they are more common than you think. What's subtle about code walking is how often you could use it, yet be unaware of its existence.

I had no other option and had to use a code walker for four separate projects without realizing it at the time. I wrote a binary rewriter that changes the body of functions, a source-to-source transformer that makes programs updateable, and a code verifier that makes sure a server can't steal private data from the browser. None of this was possible without a code walker, and the programming language didn't provide one. So I had to find a way to put one together, all while not knowing that what I was doing each time was code walking.

I wanted out of the rewriting maze. Each time I thought this was a one off project that for some strange reason had to be this difficult, parsing and rewriting code, and which I'd never have to do again. [2] And sure enough the next important program I wrote needed code walking again. It's as if there's no escape.

Why is code walking inescapable? I think it's because of how powerful it is. Writing powerful programs implies making programs short. I think programs can be written to be as short as possible only if they can then be processed with a code walker. Put the two together and we have the answer.

The most powerful programs can only be written with a code walker.

So what makes a code walker useful isn't just that when you need one there's no other option. It's also that when you need one you're writing one of the most powerful programs.

It took me four tries to learn this painful lesson but I finally did. In the end you need a code walker. It's where writing powerful programs converges. I hope it doesn't take you as long to learn from my mistake.

Don't be surprised one day to learn you need code walking too. Because you do. Compilers are code walkers. A compiler goes over and changes a whole program, transforming it from code read by humans (source code) into code read by machines (binary code). If you've ever compiled a program you used a code walker.

A compiler is a collection of code walkers. [3] A code walker is one internal pass in a compiler.

The biggest difference between a compiler and a code walker is that a compiler doesn't let you change code in any way you want. You're not in full control with today's compiler. The compiler has more of a say about what can happen to the output. The programmer writing the insides of the compiler, who uses several code walkers that check, transform, and generate code, has plenty of room to be inventive. But the programmer calling the compiler from the outside has his hands tied behind his back. To him the compiler is restrictive as a code walker; it's a black box that could be more programmable but isn't.

This is one of the open problems with code walkers: they're hard to program (and compilers are hard to reprogram). [4] You'd hope that by now the compiler we have has everything we need. But it doesn't. It's also hard to change the compiler to make it do what we want. So we don't try to change it at all. Either way we don't have a custom code walker. Today's programming languages don't offer code walkers.

If our hypothesis is true that the most powerful programs can only be written with code walkers, and code walkers stay hard to write, the most powerful programs will also stay hard to write.

Example

Let's see an example of a source code change that is complex but possible with a code walker and simply impossible with macros. It's also impossible with functions.

To get a feel for how powerful a code walker is I'll measure code size in number of lines and compare the code savings. This is the same way I measured code size when comparing macros to functions. The higher the code savings the more powerful a feature is.

It's an example in C for a real world FTP server called vsFTPd v2.0.5. The code walker used for this change was written months before the vsFTPd source code used as input was. It was also written by someone other than the person who wrote vsFTPd.

The source code was read by the code walker, automatically changed to add new features like the ability to be updateable, and output in source code form. [5] The code walker made 18 passes over the code, some to gather state and some to transform the code.

Every function had to be changed. This can't be done with a macro. It was attempted with one and it didn't work. When time came to gather state, like prepare all function and local parameters in custom datatypes, the macro didn't have all the information it needed. A macro applied in one function knows nothing about other functions.

A similar problem occurs within functions, not just across them. When time came to change code in the beginning of functions to jump to other parts of the body of the function, once again the macro couldn't do it. It didn't know about the parts of the function that didn't call the macro.

In both cases the root cause was the same. The macro needed to know about parts of the code that didn't call the macro, but couldn't go over them because macros aren't code walkers.

The original source code in the example is small, only 14,437 lines of code. When processed by the code walker it expands to 780,677 lines of code in preprocessed form and 7,113,312 lines of code after it's changed automatically. [6] That's a 9.1x code increase automatically added by the code walker.

I had showed code savings from macros can be 2.7x-5.3x. Code savings from this code walker are higher at 9.1x. This supports the intuition that code walkers are more powerful than macros.

Is there a limit to the code savings? I don't think so, because there's an additional compounding factor. Code savings don't depend only on the nature of the solution inside the code walker. They also depend on the nature of the problem: the number of places the code walker changes code. A program that gets rewritten in several thousand places increases its final code size a lot more than a program that has the same change applied in only a handful of places. [7]

I wouldn't say 9.1x is a reliable upper bound to the code savings of a code walker, because a code walker can be sloppy and in this example it is, generating more code than necessary. But I also can't ignore the possibility of 9.1x code savings and go back to programming without one. No programmer would go through 14,437 lines of code and make a source code change like this by hand. Without a code walker a program like this doesn't get written at all.

And that's the most uncomfortable consequence of this example and more generally of not having code walkers that are easy to program. There are programs we'll never write unless we use code walkers.









Notes:

[1]  One reason macros can't walk over a whole program is the runtime system doesn't let them. The runtime doesn't store the source code in the symbol table. Macros would be more powerful if the runtime did that.

But even if a runtime system let macros access everything, it would still be a lot of work for a macro to walk over the code. There's no workaround for this if the code is big and complicated. The macro would need to call a code walker.

[2]  The strangest part was how wrong it felt. I remember I sat down one day in the lab, downloaded gcc-2.95, and dug through the source determined to add a transformation I wanted. Within the hour I gave up. I downloaded a source code walker for C and felt a bit embarassed about it.

This isn't a real compiler I kept telling myself as I was trying out the code walker. It took me a couple of years to see code walking let me do things a compiler didn't.

With the binary rewriter I wanted to modify assembly instructions inside functions and the compiler wouldn't let me. I had to use a disassembler to do it. I also wanted to generate plain assembly without issuing a function call and once again the compiler wouldn't let me. I had to write an assembly template, clone it myself, and backpatch it.

With the source-to-source transformer I wanted to change source code but it was hard to modify gcc to do it. It wasn't enough to just write C macros. I had to use CIL, a framework for analyzing and transforming C programs, to read the source code in, change it, and write it out. It was like writing the middle part of a compiler without having to write the frontend and backend.

With the code verifier I wanted to intercept all set and get operations to textbox and input controls and Javascript couldn't do it. I used a small Lisp to access values and code walked over it. Unlike the other two times, here there was no code walking framework I could use so I had to also write the framework from scratch.

Eventually the light bulb went on.

[3]  Which goes to explain why good programmers like to write compilers. A compiler or runtime is one of the most powerful programs one could write.

If there could be a single pass/fail test to identify good programmers, writing a compiler might be it.

[4]  It's also one of the advantages of macros over code walkers. Macros are mini compilers that are accessible and easy to write.

[5]  Ironically the change added the ability to change the program while it's running live. This ability has nothing to do with our comparison of code walkers to either macros or functions.

[6]  The reason I'm not comparing 14,437 to 780,677 is that this first transformation is applied by CIL to decompose the original code. The program does nothing different up to this point.

I generated the original source code with an hcucc.pl that enabled only the features --doCommonUpdate --doInitializeRuntime to add the header files needed by this feature. I generated the changed source code enabling all hcucc.pl features. In both cases I ran indent for formatting and `wc -l` to count the lines of code.

[7]  The same compounding factor applies to macros.