Back in April, Robert Smith of Symbo1ics Ideas wrote an excellent post on solving the m-of-n Boolean Circuit problem. The problem is nominally about building a boolean circuit having n inputs that returns TRUE if at least m of the inputs are TRUE. Most of us aren’t electrical engineers, of course, so Smith quickly recasts the problem as building a function that does the same thing.
That’s a pretty easy problem with some obvious solutions but Smith asks how we might go about finding an optimal solution. Optimal in the sense that each input is examined at most once and that a solution is returned as soon as the answer can be definitely determined. That leaves out solutions that just spin through the inputs counting those with a value of TRUE. Smith finds a general formula for the solution and uses that to write a function to make the check.
Then things get interesting. Next, instead of writing a function to make the check he writes a function to generate Lisp code to make the check. With just a little cleverness—you’ll think, “Oh, I would have thought of that”—he has the function generating optimal code. The next step is to take that code and turn it into a compiler macro. Now when the function is called to check if m of the n inputs are TRUE the function will generate direct code if it can and call the iterative function if it can’t.
This is the best description of compiler macros that I’ve come across. I was going to blog about them myself but I couldn’t do better without just copying his post so you should definitely go take a look if you’re a Lisper.