Skip to content
A scene from Ireland

2013

Parsing a two-dimensional language.

Many programming languages are essentially one dimensional. The parser treats them simply as a linear sequence of tokens. A program could all be written on a single line, or with each token on a separate line and the parser or compiler wouldn't notice the difference This set of languages includes Algol, Pascal, C, Rust and many others.

Some languages are 2-dimensional in a bad way. FORTRAN is probably the best example, though BASIC is similar. These (at least in their early forms) had strict requirements as to what can go on one line and what needs to go on a separate line.

A few languages are exploring the middle ground. Go will treat Newlines like semi-colons in certain cases which can result in a 2-dimensional feel, but brings with it some rather ad-hoc rules. Python probably makes the best attempt at 2-dimensional parsing of the languages that I have looked at. It allows newlines to terminate statements and also uses indents to indicate the grouping of some language elements, particularly statement groups.

While I find a lot to like in Python, it seems imperfect. I particularly dislike using a backslash to indicate line continuation. You can avoid this in Python by putting brackets around things as a newline inside brackets is ignored. But this feels like a weakness to me.

As I wrote in a recent article for lwn.net:

The recognition of a line-break as being distinct from other kinds of white space seems to be a clear recognition that the two dimensional appearance of the code has relevance for parsing it. It is therefore a little surprising that we don't see the line indent playing a bigger role in interpretation of code.

This note is the first part of a report on my attempt to translate my intuition about parsing the two dimensional layout into some clear rules and concrete code. This note deals with indents. A subsequent note will look at non-indenting line breaks.

  • in Tools
  • 3 min read

Wiggle 1.0

About 11 years ago I started writing "wiggle". I have finally released version 1.0.

Wiggle is a tool for applying patches with conflicts. I do quite a bit of applying patches to a release different to the one they were created for. This often works, and often fails completely so that the task must be done completely by hand.

Parsing LR grammars

It is time for another diversion, but it is leading towards the language design - honest.

LR grammars are a tool for specifying the grammar for a language, and it is fairly easy to automatically generate a parsing tool from a grammar. So they have often been used for this purpose.

There seems to be some suggestion that LR is no longer to tool of choice (see wikipedia - since redacted), apparently because it is hard to do good error reporting. The gcc compilers converted from an LR grammar to a recursive descent LL grammar, apparently for this reason.

However I like LR grammars and I don't see the problem. So I plan to start out with an LR grammar approach. Either it will work well, or I will start the see the problem, and either outcome in positive in my view. So I cannot lose.

Lexical Structure

It is traditional to divide the parsing of a program into two conceptually separate stages - the lexical analysis which extracts a stream of tokens from a stream of characters, and the grammar matching stage which gathers those tokens into grammatical units such a declarations, statements, and expressions. Recognising the value of tradition, Ocean will similarly have separate lexical and grammatical stages. This note will focus on the lexical stage.

Future language design decisions will refine may details of the lexical structure of the language, however there is a lot of commonality among current languages and we can build on that commonality to establish a base approach to lexical analysis which can then be fine tuned when the details of the language are known.

Literate programming?

I was going to start out by describing the lexical structure of Ocean, but as I thought more about it, I realised there was something that needed to come first. And that something is literate programming.

Literate programming is the idea - popularised by Donald Knuth - of writing programs like pieces of literature. They can be structured as a story or an exposition, and presented in a way that makes sense to the human rather than just to a computer.

The naming of a language

"The naming of cats is a difficult matter, It isn't just one of your holiday games." The naming of programming languages is also important. As with any project a name is needed to be able to refer to, and it inevitably will set expectations and flavour to some degree.

I've had a few different thoughts about names. My first idea was "plato". Plato was a philosopher and is particularly known for drawing a distinction between the real and the ideal. All things in the real world, circles and squares and so forth, are just poor shadows of the perfect circles and the perfect squares that exist in the ideal, or "Platonic" plane.

An exercise in Language Design

When I was doing my honours year in Computer Science (UNSW, 1986) I wanted to design a new programming language. That would be a rather large project for an honours year and naturally it didn't happen. I have remained interested in languages, though for most of the time that interest has been idle.

I recently wrote some articles about languages for LWN and that has re-awoken my interest in language design. While I had scribbled down (or typed out) various notes about different ideas in the past, this time I seem have have progressed much further than ever before. It probably won't ever amount to much but I've decided to try to continue with the project this time and create as concrete a design and implementation as I can ... in my spare time.

  • 1 min read

RAID - not just smoke and mirrors

My final talk at Linux.conf.au 2013 was about "md" software RAID.

Slides are here and video is here (mp4).

One take away, mainly from conversations afterwards, is that - there is a perception that - it is not that uncommon for drives to fail in a way that causes them to return the wrong data without error. Thus using checksum per block, or 3-drive RAID1 with voting, or RAID6 with P/Q checks on every read might actually be a good idea. It is sad that such drives are not extremely uncommon, but it seems that it might be a reality.

What does one do when one finds such a drive? Fixing the "error" and continuing quietly seems like a mistake. Kicking the drive from the array is probably right, but might be too harsh. Stopping all IO and waiting for operator assistance is tempting.... but crazy.

I wonder...

  • in Tools
  • 1 min read

Wiggles and Diffs at LCA

My second talk at LCA2013 - the first one accepted - was on "wiggle", my tool for applying patches that don't apply. In the presentation I wanted to explain how "diff" works - as I then wanted to explain why one of the things that wiggle does is more complex that a simple "diff". For this I came up with a simple animation that I presented as a series of "impress" slides. Some suggested I make them into an animated "gif", so I did. And here it is (click for a higher-res version):

Animation of Diff algorithm

Among the useful feedback I got about wiggle:

  • UTF-8 support would be good. This only applies to the way it breaks strings into words. Currently it only understand ASCII
  • Detecting patterns of "replace A with B" and looking for unreplaced copies of "A" in the original might be useful.

The slides in LibreOffice format are here and the recording of the talk is here

  • 2 min read

Linux.conf.au - one down, two to go.

At linux.conf.au this week and as always it is proving to be a great conference. Bdale's keynote on Monday was a really good opening keynote: very wide-ranging, very high level, very interesting and relevant, very pragmatic and sensible.

One of this key points was that we should all just keep building the tools we want to use and making it easy for others to contribute. The long tail of developers who submit just one patch to the Linux kernel make a significant contribution but wouldn't be there if it was hard to contribute, hard to get the source, or hard to build the source. With Linux all of these are relatively easy and other projects could learn from that ... particularly the "easy to build" bit.

So let's not worry about beating MS or Apple, or about claiming the year of the Linux anything. Let's just do stuff we enjoy and make stuff we use and share our enthusiasm with others. If that doesn't lead to world domination, nothing will.

For myself, I managed to get 3 speaking slots this year ... makes up for not speaking for some years I guess. My first was yesterday about the OpenPhoenux project - follow-on from OpenMoko. It was very well attended, I got really good responses and positive feedback. I even managed to finish very very nearly on time. So overall, quite a success. I hope the next two (both tomorrow, Wednesday) go as well.

You can view the slides if you like, but they aren't as good without all the talking. Hopefully the LCA organisers will upload the video at some stage.