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.  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 one 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.
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.  And sure enough the next important program I wrote needed code walking again. I wanted out of the rewriting maze and yet there was 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 be written only 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.  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 since it's a black box that could be more programmable but isn't.
That's two open problems: code walkers are hard to program and compilers to reprogram.  I was expecting by now that the compiler would have everything I want but nope, it doesn't. It's also hard to change the compiler to make it do what I want, so I don't bother changing it at all. Either way I don't have my custom code walker. Today's programming languages don't offer code walkers.
If 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.
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.  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.  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. 
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.