John Fremlin's blog: Explaining meta-programming by analogy

Functional programming is easy for programmers to understand: it is, after all, a subset of imperative (normal) programming. It is also easy to understand the benefits of functional programming. But try to explain why meta-programming is great — or even what it is, and eyes glaze over and the idea does not stick. I'm going to make an attempt to explain it with the help of a tasty analogy here.

First off, by meta-programming I mean writing a program to generate (part of) another program. In the Ruby world, some people use the term for introspection or meddling with the object system. That is not what I am talking about. Programming is unambiguously specifying a process to be carried out by a computer. Meta-programming is programming where the output of the process is itself a program. For a real-world example which might be familiar, writing a parser generator like yacc is meta-programming.

Let's compare programming to having a meal. In imperative programming, you cook the meal, set the table, sit down at the table, share the meal with the other diners, and then do the washing up. Functional programming would be like everybody getting a microwave ready meal or an army MRE — no worries about washing up and no worries about sharing out the food.

This brings out the benefits and downsides of functional programming (programming without side-effects). It is much simpler to figure out who is going to eat what, and when there are many diners they don't conflict. The justification for functional programming is that it is more elegant and can scale to larger problems without an explosion of complexity. However, microwave pizza is often eaten by people who are too lazy to do the washing up. The packaging is inefficient and bad for the environment and the ingredients could equally have been used to make a fresh pizza (why not use your computing resources to their full potential?).

In cases where there are multiple implementations of a program for a similar task: for example compilers, image processors or database systems, the best are written in a non-functional style in languages like C or C++. There are plenty of programmers who can handle sharp chopping knives (pointers) without cutting themselves. If you're too clumsy to do that, then your side-effect free programs will also be incorrect (spilling the greasy pizza all over your t-shirt).

That's easy to explain, but what is meta-programming? In this analogy, I would say meta-programming is about modifying your kitchen to suit your cooking. A normal cook might install a dish-washer (a programmer switching to another language) but a meta-cook would DIY-assemble a rack and high-pressure hose arrangement for the particular plates used in the kitchen, and then perhaps end up building a machine for building these custom dish-washers.

I think this analogy of making your own dish-washer for your particular plates is quite apposite: meta-programming is rarely done except in large projects. McDonald's can design custom fryer baskets, but a small kebab shop is going to use whatever old one they can get their hands on. This means that the sort of person who might readily appreciate the convenience of functional programming (microwave pizza) is unlikely to have any experience developing the sort of serious project that uses meta-programming. Secondly, many uses of meta-programming in small projects are completely unnecessary and when a C project builds up complex macro systems they're probably doing that instead of working on whatever the project should achieve (jury rigging an awesome mop instead of actually cleaning the kitchen).

But all big projects do end up using code-generation (meta-programming). Always. For doing RPC, parsing, error reporting, generating code for calculations, etc. So it should be easy to give some examples where meta-programming is really used in practice. Unfortunately, again by analogy with the dishwasher business, these examples tend to be complex and specific to the task at hand.

As an alternative, to demonstrate that meta-programming can be easily used without necessarily being a huge undertaking, I shall give a few examples from teepeedee2 project, using Common Lisp. This comes to the heart of what I have failed to convey to my peers from my student days who use C and C++ to write first-class programs (some use python to write reasonable programs). If you have a cheap 3D printer, then maybe making your own plates isn't such a big deal, and it might be cheaper and easier than going out and buying them. But cheap meta-programming isn't science fiction.

For example, to define the XML DTD for the Atom syndication format I use this code:

(define-dtd :teepeedee2.ml.atom
    (:nicknames #:tpd2.ml.atom)
;; Arbitrary subset defined by hand
  (feed :attributes (xmlns) :children (#'identity title subtitle link author id entry updated))
  (title :children (#'identity))
  (subtitle :children (#'identity))
  (link :attributes (href rel) :children ())
  (updated  :children (#'identity))
  (author :children (name email))
  (name  :children (#'identity))
  (email :children (#'identity))
  (id  :children (#'identity))
  (summary :children (#'identity))
  (content :children (#'identity) :attributes (type))
  (entry  :children (title link id updated summary content)))

This generates macros called <feed, <title etc. so I can write (<link :href "/") to generate <link href="/"></link>. In fact, these macros will check that I spelled the attributes correctly and warn me at compile time if not, and additionally check at compile time that, for example, a <link does not occur in the middle of an <updated tag (which would be against the DTD and probably indicates a typo).

Some languages like Scala have XML built in. Lisp does not, but using meta-programming one can add it along with whatever features one wants. Here, in fact there are several layers of macros, so that constant tags can all be concatenated into a fixed string at compile time.

How about a simpler example? If someone posts the same comment twice on this blog, I only want it to show up once. But what does the same comment mean? The comment class has a time posted slot, which will probably be different, so comparing two comment instances in a simple way is not enough. I decided that two comments are the same if they are on the same blog entry, have the same text and are by the same person.

(defun comment-similar-p (a b)
  (macrolet ((cmp-fields (&rest fields)
	       `(and
		 ,@(loop for field in fields
			 for accessor = (concat-sym 'comment- field)
			 collect `(equalp (,accessor a) (,accessor b))))))
    (cmp-fields
     author
     text
     entry-index-name)))

Normally, one might have to write out the boring boilerplate (and (equalp (comment-field0 a) (comment-field0 b)) (equalp (comment-field1 a) (comment-field1 b)) (equalp (comment-field2 a) (comment-field3 b)) ...) etc. But I wrote a little program in the macrolet that generates this for me. (Spot the typo in the handwritten version?) Making the DSL to implement the body of the function wasn't hardly more trouble than writing the function.

I use cl-cont to implement userspace threading. In the games on mopoko.com, like Scissors, Paper, Stone all the players need to be asked the same question at the same time, then once they have all answered, we decide who wins. This macro creates a macrolet called spawn/cc which creates a new thread. When all the threads have returned, the continuation (k) is run.

(defmacro with-join-spawn/cc ((&optional (name (gensym "join"))) &body body)
  (with-unique-names (k)
   `(call/cc
     (lambda (,k)
       (let ((,name 1))
	 (flet ((,name ()
		  (assert (plusp ,name) (,name) "spawn/cc returned too much")
		  (decf ,name)
		  (when (zerop ,name)
		    (funcall ,k))))
	   (macrolet ((spawn/cc ((&optional (name ',name)) &body body)
			`(progn
			   (incf ,name)
			   (with-call/cc
			     ,@body
			     (,name)))))
	     ,@body)
	   (,name)))))))

So I can use it like this (a paraphrasing of part of roshambo.lisp):

(with-join-spawn/cc ()
  (loop for p in (my players) do 
  	(let ((p p))
	     (spawn/cc () 
	     	       (setf (its choice p) 
		       	     (my secret-move :select p
		       	     	 `(:one rock paper scissors)))))))

And there's no need for hand-rolled thread counting for each move in every game. All the dangerous if wrong boilerplate is moved into one place: the with-join-spawn/cc macro.

Having lightweight meta-programming available means that you can quickly automate any drudgery. It's a paradigm shift and opens up new opportunities. Meta-programming as a heavy-weight mechanism, complicating up your build-systems and so on is best used for really important tasks. There's no need to design your own dishwasher factory when you are warming something up after a hard days work. Disposable plates might be a good idea.

Imagine being able to quickly make a robot that would chop the onions, and a robot to set the table. And imagine that making such a robot was only slightly more effort than laying the table yourself — but you only have to do it once. Suddenly having a decent meal every day isn't much work, and you wonder why people are still gobbling down tasteless pizza.

It's science fact, and it's been on planet earth for decades.

UPDATE 20091001 — rephrased some ideas; thanks to everybody for the feedback.

UPDATE 20091028 — thanks to everybody who pointed out how bad my examples were. Guess I should choose some better ones and rewrite it again. . .