Meta-II: An Early Meta-Compiler

What is a meta-compiler? Before answering that question we need to take two steps back. First, what's a compiler? A compiler reads a program written in some source language and transforms it into a (more-or-less) equivalent version expressed in a target language. For example, a C compiler takes the usual textual representation of a C program and generates object code in some target language such as assembler code or virtual machine instructions. The resulting object code is equivalent (in some sense) to the source code, but it can be run directly on a physical machine or in an interpreter.

A compiler-compiler reads a "program" which specifies the grammar of a source language and some transformation rules. The object code it generates is a compiler for that source language. (So a compiler-compiler is also compiler, it's just that its source code is your grammar-plus-transformation-rules and its output is object code which directly executes those rules and transformations.) The idea is that writing a grammar and some transformation rules is a lot less work than writing a whole compiler. Instead you write a more declarative description of what you want to happen and the compiler-compiler generates the code that deals with the fiddly details of pattern-matching and code-generation.

So now we can answer the question: "What's a meta-compiler?" A meta-compiler is a compiler-compiler written in its own source language. So when the meta-compiler reads its own description, it generates exactly its own object code, a fixed-point if you want to think of it that way. It's a neat trick, and clearly an easier way to build a compiler-compiler — provided you already have a compiler-compiler to start with.

I first came across Meta-II when I read Experimenting with Programming Languages by Alessandro Warth. In this PhD thesis Warth explains some interesting implementation details of the meta-compiler OMeta. (This meta-compiler has been used to implement many different languages at the Viewpoints Research Institute and elsewhere. These languages and the systems written with them are key evidence to support Alan Kay's assertion that we can build systems with orders of magnitude less source code than is customary today.)

Now, OMeta started out as an experiment based on the much earlier Meta-II, so when I wanted to play with a meta-compiler, this earlier, simpler program seemed like a good place to start out. (I figured that by playing with this program I would come to understand what was wrong with it, what needed changing to make the more advanced OMeta. That's certainly been the case, but I'm not entirely sure it was worth the effort.)

Meta-II is described in Meta II: A Syntax-Oriented Compiler Writing Language by Val Schorre (1964), and although this paper is a nice read, I found that the best place to start playing is James Neighbors' Tutorial: Metacompilers Part 1 and the accompanying Metacompiler Workshop. This "workshop" is a web-page with an extended version of Meta-II implemented in Javascript, so you can put your grammar description in one window, and get the code for a compiler in another window, and then use that compiler in turn to compile a program. If you want to do what I did, you can work your way through Neighbors' tutorial and then port a version of Meta-II off the web-page and into a self-contained program. (You can find the results of my slightly-too-clever-for-its-own-good port to Python here on github.)

I had decided that I wanted a version very close to Schorre's original Meta-II, rather than the extended version constructed by Neighbors. This choice in turn forced me to implement a virtual machine in my Python runtime, rather than generating native Python control constructs. That's because the original Meta-II's output operations are tuned to generating assembler code line-by-line, with only two levels of indentation. Obviously that's not going to fit well with Python, where indentation indicates block structure. So instead my code reads the generated "assembler code" and effectively assembles, loads and links it into a form where it can be interpreted directly. Quite a lot of extra work to stay with the original version of Meta-II, and in the end not worth the effort, other than for the learning experience.

So, what did I learn? And what would I change about Meta-II so that it was more useful but still simple, without going all the way to the complexity of OMeta? (Which adds a full programming language to do the output transformations.)

• It would be better to have a somewhat more expressive language in which to write the transformation rules, and that way avoid having to put so much work into a virtual machine to interpret the meta-compiler's output code. (Since Neighbors and Warth both came to the same conclusion, this does seem blindingly obvious in retrospect.) Probably the first step would be to follow Neigbors' example and introduce a mechanism for more general indentation of output, so it would then be possible to output nicely formatted representations of a program — for example S-expressions.
  
  
• Both the original Meta-II and Neighbors' extension only have access, in their output operations, to the last token matched. OMeta is a lot more flexible here, since you can give names to the values of any matching rules and then use the values later in a different order. This facility would also remove the need for a special-purpose token-recognition sub-language which Neighbors introduces in his implementation.
  
  
• OMeta uses backtracking when a rule doesn't match, but Meta-II has to make its decisions based only on the next token. In practice, you can still parse lots of languages, but it's an annoying restriction, best removed. Fortunately this is relatively straightforward. Neighbors explains how to do it, though he doesn't give an implementation. OMeta's implementation also improves backtracking performance using a caching technique: it's a "packrat parser". (See for example Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking by Bryan Ford.)
  
  
• Lastly, Meta-II cannot handle left-recursive rule definitions, because they would not terminate. If you have a grammar that is naturally left-recursive, you therefore have to rewrite it without the left-recursion, which you can always do, but this isn't really very satisfactory. How confident can you be that the subsequent parse tree and your interpretation of it really is equivalent to the intent of the original grammar? It's a problem waiting to bite you later. So a further useful improvement would be to use Warth's neat technique that makes left-recursion work in a packrat parser.

You can only really understand things properly by making them yourself, so my next step will be to implement some of these ideas, and I'll report on how that went in some future post. In the mean time I would encourage you to look at the original Meta II paper and to have a play with Neighbors' Metacompiler Workshop. It's great fun!

Recipe: Flemish Beef

This recipe is based on a dish cooked for me a long time ago by Mary Sheeran. It is supposed to be Irish — hence the Guiness — but that doesn't really explain why it is called "Flemish" Beef.

Ingredients

1	Large onion
4T	Oil
225g	Unsmoked bacon
450g	Beef
1T	Black treacle
3T	Vinegar (preferably cider vinegar)
300ml	Guiness
(1T = one tablespoon = 15ml)

Method

Slice the onion into slices about 5mm thick and fry in the oil for 5 minutes on a medium heat.

Slice the bacon rashers cross-wise into pieces about 1cm wide. Add to the pan and fry for another 3 minutes.

Slice the beef into pieces about the same size as the bacon. Fry for another 3 minutes or so. (The onion should be slightly browned and the bacon and beef should have a cooked-colour.)

Add the black treacle, vinegar and guiness. Bring to a boil then turn the heat right down so that the sauce is just simmering. You want the sauce to slowly boil down and thicken. This should take about 30 minutes.

And also ...

You might also enjoy reading Functional and dynamic programming in the design of parallel prefix networks by Mary Sheeran (Journal of Functional Programming 21(1), 2010, pp59-114).

The Clean Slate Movement

It would be nice, wouldn't it, if our programs were shorter. They would be quicker to write, easier to understand, easier to maintain. The way this is supposed to work is that we take code made by other people and build on it, so that the small part we write draws together and coordinates the code from libraries and other self-contained programs. But in practice this has not worked out quite as well as we hoped. As James Hague points out in We Who Value Simplicity Have Built Incomprehensible Machines, the code that we try to re-use has become encrusted with layer after layer of cruft. How did that happen?

"... all the little bits of complexity, all those cases where indecision caused one option that probably wasn't even needed in the first place to be replaced by two options, all those bad choices that were never remedied for fear of someone somewhere having to change a line of code...they slowly accreted until it all got out of control, and we got comfortable with systems that were impossible to understand."

Impossible? We all know what it's like. Maybe the power of search-engines and communal help over the Internet has mitigated the problem, but it's still a problem. We can get stuff done, but it gets more and more like black magic. (In another post, A Complete Understanding is No Longer Possible, Hague points out that for a reasonably thorough understanding of a MacBook Air, you would have to digest around 11,000 pages of documentation. It's not going to happen is it?)

So what can we do? The short answer to that question is: "Start again, with a clean slate". It's a daunting prospect, and one that until recently no-one would have taken seriously. But over the last few years something that we might call "The Clean Slate Movement" has started to gain credibility.

For some in this movement, like Peter Neumann or Robert Watson the central issue is security. Our systems have become so complex that it's impossible to make credible guarantees about security. Only by building new systems, re-thought from the hardware up, can we really make any progress. (If we try to do the right thing on current hardware, our systems usually end up being far too slow. If you want to understand how processor designs will be different in 10 years time, you might take a look at The Cambridge CAP Computer. It's 30 years old, but it's actually from the future.)

Other people in the movement, notably Alan Kay and his colleagues at Viewpoints Research Institute have a slightly different aim. They envision building systems which are dramatically simpler because they are dramatically smaller — with maybe 100 times or even 1000 times less code for the same functionality. They talk about writing code for a whole system, from applications down to the "bare metal" in perhaps 20,000 lines. Now if that were possible, we could certainly imagine understanding that whole system. If we printed it out 20 lines to a page, surrounded by commentary like the Talmud, it would only be 1000 pages long. Something like the size of the Oxford Users' Guide to Mathematics. Something you would expect a professional to be intimately familiar with, though they might have to go look up the odd detail.

You might reasonably ask "Is all that really possible?" It does seem rather ambitious, even unlikely. But Alan Kay obviously has a formidable reputation and his associates have already had considerable success. A central part of their strategy is to use meta-compilers to define different, powerful languages in which to implement the different parts of their system. This does seem to lead to a substantial reduction in code size. (Meta-compilers are another old technology brought up-to-date, and one that I'll return to in a future post.)

Overall, can we really afford to throw away old systems and rebuild from scratch? The marginal cost of patching-up a system is always less than the cost of starting from scratch. But if we only pay attention to short-term costs, then each repair will only barely do what's needed today, and afterwards the system as a whole will be a little worse. Unless we spend extra effort today and keep refactoring a system so that it continues to be maintainable, over time it tends to degenerate into a ghastly mess: fragile and dangerous.

Too see where this ends, you only have to look at the notoriously crufty and fragile systems employed by the financial services industry. Take for example the market maker Knight Capital, which on one day in August 2012 suffered a 440 million dollar loss due to a "technology issue". (Their software offered to trade shares at stupid prices, an offer which other people were only too happy to accept.) In the long run, it's worth paying for craftsmanship. In the long run, crufty software is never the cheapest option.

Recipe: Red Braised Chinese Leaf

This is a variation on a Kenneth Lo recipe "Hung Shao Pai Ts'ai" that we have been cooking for decades. As he says, "Unlike a meat dish, which one tires of continual eating, this vegetable dish can be eaten day after day." It's really nice.

Ingredients

1	Chinese leaf (1 to 1.5 kg)
2T	Soy sauce
1T	Dry sherry / rice wine
3T	Chicken stock
4	Chinese dried mushrooms, soaked (at least 1 hour)
5T	Oil (preferably groundnut)
2	Dried chillies
2	Spring onions, coarsely chopped
(1T = one tablespoon = 15ml)

Method

(Note that you need to cook this in a wok, and it needs to have a tight fitting lid. It doesn't really work otherwise.)

Cut the Chinese leaf in half length-ways and then cut the halves into 1-cm slices. Discard the base. Wash, drain and dry.

Combine the soy sauce, sherry and stock in a bowl.

Drain the soaked Chinese dried mushrooms and slice finely, around 1-2mm thick. (The dried mushrooms are best soaked for several hours in cold water, but if you're in a hurry you can get away with soaking them for less time in hot water, but 1 hour is about the minimum.)

Heat the oil in a wok over medium heat and cook the chillies and spring onions for between 1 and 2 minutes. (The longer, the more spicy the resulting dish. You know you have gone too far when the air is so full of chilli vapour that you stagger out into the garden like the victim of a world-war one gas attack ...) Discard the chilli and spring onion. Keep the flavoured oil in the pan.

Add the Chinese leaf and stir fry over a high heat for 4 minutes. (The Chinese leaf has to wilt before the next step. It's ok if it scorches slightly in places, but as with all stir-frying, you have to keep it moving all the time.)

Turn the heat down to medium and add the mushrooms and the soy sauce mixture. Mix well.

Turn the heat down to low and put a tight fitting lid on the wok. Leave to cook for 10 minutes.

(The original recipe thickens the sauce with cornflour at the end, but I think it's better without.)

And also ...

Those of you who remember Giles Murchiston will probably be as surprised as I was when I recently came across a submission by him, buried in the massive collection of written evidence gathered last year by the Parliamentary Joint Committee on the Draft Communications Data Bill. See pages 418-422 (or 420-424 of the PDF).