Bletchley Park

Rare non-PL post, but I figure this one is worth it.

I went to Bletchley Park last weekend, and had an absolutely fantastic time. There was a lot more there than I expected. It's an absolute bargain at £10, and it's only about 45 minutes on the train from Euston station in London. It's definitely worth doing one of the free tours, too. The guides are extremely knowledgeable and entertaining.

Also located there is the National Museum of Computing, which was fascinating. I took some pictures:


And one of me standing in front of a PDP-11 looking quizzical:

So, if you are in the UK, or are planning a visit, definitely make the effort to get to Bletchley Park.

Two features that would improve my life

If you've ever seen From the Earth to the Moon, you might remember the episode about the creation of the Lunar Lander. Tom Kelly is shown standing outside throwing a red ball against a wall repeatedly while he tries to think of solutions to hard problems. This scene has always been memorable to me because I think it is the only cinematic depiction of "problem solving" that has ever seemed familiar to me.

I cite this scene because it echoes the way I problem solve. I think a lot, and I do strange things in an undirected manner until I solve it. When I'm actually creating software, I generally know how most of it is going to work before I even start typing. Writing all the supporting code and boilerplate is not intellectually challenging - and I think this is the majority of the "programming" that a commercial programmer is called upon to do.

In the midst of this programming-as-typing though, there are often hard problems that need to be solved. These are usually the bits that I find myself actually needing to think about - they are usually hard problems to reason about, and I find that I "code around" them in many instances. It's the kind of situation where you might write a stub and then promise yourself to come back and write it later, once you understand the problem (and its solution) a little better.

A recent example for me - I was attempting to figure out how to do a novel kind of type inference over complex terms. I wrote a "infer" function that takes a piece of a program and returns a typed piece of program. And then I wrote some tests, and my implementation consists of just returning "unknown type". Not very useful.

I have a bunch of strategies I usually use when I'm trying to solve these kinds of problems. I scribble on paper a lot, trying to contrive concrete examples that I can start to generalise into an actual algorithm. That's fine at the early stages, and helps my understanding a lot.

Another strategy is to use some sort of REPL (interactive environment) and try to write bits of code that get me closer to my goal. I usually use MLton for development, so this usually means switching over to SML/NJ so that I can start to "sketch" in code.

Often these two approaches are enough to get me most of the way to a solution. If the problem is really hard, it might not be. In these cases, I generally wheel out my trusty theorem prover, Isabelle. At this point, it becomes possible to re-implement the bits of supporting code that I need in order to express the problem, and then start trying to test my assumptions by actually proving properties about the kinds of functions I'm "sketching". This forces me to make very concrete my assumptions and intentions, because a theorem prover refuses to make educated guesses.

So, having gone through that entire process, I was thinking of something that would make my life better: a language-aware prototyping environment.

Let me explain. I have very little tolerance (or desire to use) visual programming environments, or "CASE tools", or very dynamic languages that permit "rapid prototyping". I'm talking about something that will help while I'm trying to solve hard problems embedded within lots of other code during "real" software development.

Basically I want the ability to access all of the supporting code and boilerplate that I've written in order to express my problem from within a prototyping environment. Having to re-implement things inside Isabelle is a pain, particularly if I'm dealing with problems that are linked to the way things are represented. I have to re-build all of the structures in another language just to be able to re-state the problem I'm trying to solve.

So I want to be able to instantiate a prototyping environment exactly where I would currently just write a stub. I want to be able to see visualisations of data easily. I'd like to be able to do some of the things that I do with the REPL. I'd like to be able to easily save and re-run test cases. So far, so pedestrian.

And this is where it starts to get more interesting. I want to be able to write partial specifications. In this kind of "exploratory programming" - I want to be able to start to apply "fuzzy" constraints until they become clearer in my head, mixing them with valid program code. I think a good way to do this would be to employ some of the techniques from Qualitative Spatial and Temporal Reasoning. These could be quite simple things, for example: "this value gets bigger over time", "this event is going to occur before this one", and when dealing with complex data structures - "this value exists inside this other one".

None of this would be directly executable, naturally, but with a range of visualisation options and some consistency checking, it would give you an ability to interact with a partially-written program in ways that you would otherwise start to do manually in a REPL. Taking some of the QSTR statements and deriving some new facts from them would be useful too - if I have a bit of code saying that x gets bigger over time, then perhaps it could tell me that this means that y will get smaller over time. It could draw me a pretty graph! By being able to mix "real" code with these kinds of qualitative statements, I think you could start to get some interesting results. I think the trick would be to integrate it into a compiler so that it's not necessary to do this in a "dynamic" way - the stuff that is not directly executable just gets compiled into some code that implements the prototyping environment.

That's the first feature that I think would improve my life. It would serve as a (metaphorical) "red ball" to throw against the wall while you try to solve a hard problem.

The second is a fairly simple extension: generate tests, specifications and documentation based on this prototyping process. By including your compiler in the prototyping process, it seems like you are actually starting to capture a whole bunch of useful information.

If I specified that A comes before B, then surely there are some useful tests (what happens if B comes before A, for example?). If I made some statement about the depth of a tree versus the number of iterations through a piece of code, then that might be an interesting test or profiling metric.

From a documentation standpoint, it seems like you could generate some useful documentation that provides insight into how a "difficult" piece of code actually works, because hopefully it would be possible to capture some of the rationale and the intuitive problem solving process that led to the eventual solution. By keeping track of the revisions made inside the prototyping environment, you essentially have a record of the "story" of the code as it becomes more concrete.

While it would probably be a reasonable amount of work, it's certainly not impossible. I believe the minimal set of functionality that would actually make this a useful feature would be quite small. I think this could be a "killer app" for some programming language - as long as the rest of the language was sane, I think I could be convinced to make a switch.

Pigeons and Programming: Superstitious behaviour

You may be familiar with B.F. Skinner's experiments with pigeons, published in 1948. Basically, pigeons were kept in cages and fed on random schedules. This led to the pigeons developing some rather bizarre behaviour - turning in clockwise circles, attempting to "lift" an invisible bar, and various other odd actions. Skinner's conclusion was that this kind of reinforcement led to a kind of weak association between whatever the pigeon was doing when food was delivered and the "reward" of getting food. The eventual conclusion was that these pigeons were displaying a kind of "superstitious behaviour", which led them to repeat actions that resulted in reward in the past, despite there being absolutely no causal effect.

Some psychologists object to extending these results to an explanation for superstitious behaviour in humans, but I believe the link between reinforcement and repeated behaviour is relatively well-demonstrated.

What's the point of this pigeon story? I think it applies to programming.

Having a poor mental model of the semantics of a programming language leads to all sorts of bizarre superstitious behaviour. You only have to read thedailywtf for a little while to see all kinds of examples of the programming equivalent of throwing salt over your shoulder and turning around three times. Let me stretch the analogy a little further:

Certain programming structures lead to success in a task. This success leads to a kind of reinforcement of the techniques used to reach that solution. This "reinforcement" could be compiling, passing tests or running successfully. Similarly, there is a kind of negative reinforcement schedule - compile errors, failing tests or runtime failures.

It's important to form a distinction at this point between simple learning-from-experience and the kinds of superstitious behaviour that I'm arguing occur in programming. Let me give an example - having a poor knowledge of a given language, let's say that I construct a program and I apply techniques A, B, C and D. These could be anything, really - naming schemes for variables, grouping of sub-expressions with parentheses, adherence to particular patterns, or anything else. It may be that only A and C were sufficient in order to have the program compile and run. Unfortunately, I've also included B and D. Next time I come to write a program, if I continue applying B and D, these become a kind of entrenched superstition. They serve no purpose, except to make reading code more difficult for programmers who do not share your superstitions. This is still just learning from experience though - this isn't inherently "superstitious" - it's just a school of programming associated with throwing everything at a wall and seeing what sticks.

Now, here's the crux: it is inconsistent application of "reward" that leads to superstitious behaviour. This inconsistency exists in two basic forms in programming languages. The first is when there is a lot of hidden behaviour. When there are a lot of hidden assumptions, it becomes very difficult to discern why your program works. This is where the compiler or framework takes on a "magical" quality, whereby the rules governing success or failure are so complex as to seem almost random.

The second opportunity for inconsistent application of reward is late failure. I find this kind of behaviour is regularly present within the high-level, dynamically-typed, interpreted languages. Where the goals of these languages emphasise being accessible and intuitive for beginners, this actually equates in many cases to "keep running until the error is completely fatal". Where failure occurs well away from the actual source of the error, diagnosing and correcting errors can quickly become an exercise in near-random mutation of source code. When cause-and-effect become very difficult to predict, then changing one part of the system and having another piece break (or start working) becomes a kind of reinforcement schedule. This has two dangerous impacts: 1) it leads to unnecessary error handling in places there shouldn't be error handling. The hideous global "try/catch" block wrapping an entire program is a symptom of failure occurring much later than it should. 2) programmers become timid about touching certain parts of a system. This leads to more "magical thinking", whereby a piece of the system not only is difficult to understand, but should not be attempted to be understood. This makes it almost impossible to refactor or grow a system in a structured way. There will always be bits of "magical" code waiting to break unexpectedly.

So of the two sources of inconsistency, the first is the easiest to address. This basically just corresponds to "learn enough about your environment so that it no longer appears magical":

• Test your assumptions regularly - Do you really need those extra parentheses? If you're not sure, try it without.
• Be a square: read the manual - it seems incredibly dull, but it's actually worth understanding your language of choice from the ground up. You may be a good enough programmer to pick up languages just by reading a bit of source code and a few ad hoc tutorials, but there is something to be said for the systematic approach to learning a language - namely, the hidden behaviours of the environment become considerably less magical.
• Avoid magic - If you're considering web frameworks or programming languages or whatever, beware the phrase "it all just works". If you don't understand how or why it works, and you don't believe you are willing to devote the effort to understanding how or why it works, then the benefits of any whiz-bang features are going to be eaten up by the maintenance and correctness issues you'll suffer as a result of superstitious behaviour.

The late failure issue is considerably harder to address without simply suggesting switching to a language that can enforce certain properties and that will fail early. By "early" I mean, "at compile time" or "immediately after the first error case". I am always particularly suspicious of languages where things like silent type coercion and silent initialisation of never-seen-before variables occurs. These are basically just error cases waiting to happen, but they won't be revealed until much, much later in the execution of the program. When a typo at line 1 can cause an incorrect result at line 10,000, you probably have a problem.

So the only advice I can offer, aside from "fail early" is to employ self-discipline in the absence of language-enforced discipline. Attempt to build structures that will cause your program to fail early rather than deferring failure. Avoid developing superstitious behaviours around certain pieces of code - if everyone spends a little time questioning their own attitudes towards development (and particularly towards debugging), then maybe there will be a little less superstitious coding behaviour in the world.

Why programming language design is hard (and a few ways it can be made easier)

When designing a programming language and accompanying implementation, you are forced to keep thinking at three different levels - the way that the implementation works, the way that people will use it, and the requirements that influence design decisions.

On the face of it, this is no different to any other software development activity. In building a stock control system or any other common piece of software, I would be forced to think about the way it will be used (e.g. how users will enter items and how the people in the distribution centre will scan items as they leave), the implementation (e.g. what classes/functions/methods implement this functionality) and the requirements influencing the design (e.g. Mr. Big Boss of International Corporation really wants the software to be beige).

The difference with programming languages and many other types of software implementations is that it is difficult to relate your requirements and design decisions back into the real world. When designing a stock control system, a stock item is designed in such a way that it is some representation of a real item in a real warehouse. The behaviour of the system attempts to reflect real processes carried out by real people. You can go down and meet the people who dispatch the items if you want, and ask them all about their jobs. Having these two very concrete things at your disposal makes implementation correspondingly easier, because you have a "real world" system against which to validate your software system.

Programming language design lacks these analogous constructs. The "behaviour" of the programming language basically corresponds to the semantics of the language, which you're probably still trying to nail down (it's unlikely that you have a written semantics, right?). The way the users are going to make use of your programming language depends on what the semantics are. While you can contrive examples and try to implement them in the language, you lack perspective, because the semantics that you have implemented are exactly the way they are because they correspond to your understanding of the semantics. You're probably the person worst-equipped to make judgements about the usability of your own creation. This removes our two best tools for guiding an implementation; the ability to predict users' behaviour with respect to the system, and concrete things against which to verify our assumptions.

A few solutions

1) Get feedback early and often - this is important in all software development, but if you are designing a new programming language, you need to be talking to people all the time. While some people you talk to will demonstrate objections on some sort of dogmatic ideological basis ("I don't like static type systems, and you have a static type system, so the entire language is junk"), explaining the semantics to other people and gauging how much effort it requires for them to get a sense of the language will be very helpful in guiding future decisions.

2) Know why you're designing a new programming language - novelty or fun are perfectly valid reasons for doing PL design, but never lose sight of the fact that almost nobody will use a new programming language unless it does something better/easier/faster than they can already do it in one of the 10 trillion programming languages in the wild today. Think about the kinds of programs that you want the language to be able to express easily, and what kinds of programs will be more difficult to express. You might be aiming to create a general-purpose programming language, but that doesn't mean it's going to be good at absolutely everything. If you do claim to be designing a general-purpose language, here's a good thing to keep in mind at every point during your development: "How would I feel about writing this compiler in my new language?"

3) Write things down, often - Your ideas will probably change the more concrete your design gets. As you start being able to interact with your design (because you have a partial implementation of an interpreter or compiler), you will probably change your mind. Writing down a description (formal or informal) of your syntax and semantics will help keep you from completely contradicting your own stated goals. If (as in point 2) you decided that you were designing a language that would be good at expressing programs of type X, and then you subsequently make some changes that make it very difficult to express those types of programs, then what was the point of your language again? Keep referring to point 1.

4) Write tests - however sceptical or enthusiastic you may be about test-driven development in other endeavours, I can't stress enough how useful it is for programming language design. At the very least, keep a directory full of the test programs you write and automate some means of running these. If you can write tests down to the statement level, do that. You can never have too many tests. As I said in point 3, your design is likely to change. You need to be bold in refactoring and redesigning, otherwise your ability to change fundamental design decisions will suffer. You'll end up building "hacks" into your syntax or semantics just because you really aren't sure if changing some assumption or construct will break everything. This has the added benefit of providing you with a whole lot of sample code when you come to write documentation.

5) Think about the theory - Don't be afraid of theory. Theory is your friend. A lot of people have published a lot of papers on many facets of programming language design. It's worth learning enough about the theory of programming languages to enable you to read some of this published output. If you're stumbling around in the dark trying to figure out a way to statically enforce some property, or a more efficient register-allocation algorithm for code generation or just trying to figure out why your parser generator is complaining about your grammar, chances are that somebody has solved this problem before, and has expressed some solution to it in a published form. You'll find it much easier to relate the constructs in your new language to other existing languages if you don't reinvent the terminology wheel too. I can't recommend strongly enough Types and Programming Languages by Benjamin C. Pierce as an excellent starting point for all things theoretical in the programming languages world.

6) Consider using ML - I wouldn't be the first to note that ML is really good for writing compilers. Obviously, your circumstances may be different to mine, but having written compilers and interpreters in a few different languages, I haven't found anything quite as good as ML at expressing the kinds of parsing, validation and translation activities that are integral to compiler implementation. The type system helps prevent the majority of errors that you are likely to encounter while writing compilers. Recursive data types express most internal compiler structures perfectly, and the presence of mutable storage and imperative I/O means that you don't need to jump through too may "functional programming" hoops in order to achieve some of the things for which those features are useful. Also, the very existence of Modern Compiler Implementation in ML by Andrew Appel (which I consider to be the best introductory text on compilers to date) should make you at least think about having a look before you decide on an implementation language for your next compiler.

7) Don't be afraid of being the same - There is a tendency towards ensuring that your syntax and semantics are different from everything else in existence. If language X has a feature that is similar to yours, do you really need to invent new syntax and terminology? If something exists elsewhere, it's probably worth your time to figure out how it works and how it is expressed, and then re-implement it in a way that would be familiar to users of language X. If you are actually interested in having people adopt your language, then you should reduce the learning curve as much as possible by only inventing new terminology and syntax where it is appropriate to do so (i.e., because it is either a novel feature, or there is some improvement that can be made by doing it differently). If you're creating a new language, you've already established that there are things you can do differently or better, so it's not necessary to go overboard in differentiating yourself. If it were, PHP would never have become popular in the presence of Perl. Clojure and Scheme would never have survived the disadvantage of Lisp already existing, and so on.

Having laid out all of these points, I'm certainly guilty of not taking my own medicine at times. I've largely written this out because I'm currently going through a design and implementation process with Lope, and I don't want to repeat my past mistakes!

On the semantics of pseudo-code

I was reading a thread on HackerNews entitled "What language do you think in?" and I was fascinated by the responses.

Many of those commenting claimed to think "in pseudo-code". That got me thinking - what does it mean to think in pseudo-code?

By the textbook definition, pseudo-code is some sort of idealised, abstract code with an informal syntax. It serves as an aid to human understanding, making use of the abilities of humans to resolve ambiguity in a sensible way and "black box" a lot of minor details. That all sounds fine.

The catch for me comes in thinking about the semantics of this mental pseudo-code. It still has some semantics, I assume, otherwise it is likely to be entirely useless as a mental model. Perhaps we think of a statement in pseudo-code for "sum all of the values in X":

for each value k in X
a = a + x

OK, so that seems a reasonable enough translation from an English language specification into some code. We've left out some details like what the initial value of "a" is, and the syntax is pretty fluid, but it should be unambiguous to most readers.

The problem is that this is only one step of nearly-mechanical translation from just writing code in a programming language. There is a sneaky step of concretisation going on here, both in the framing of the statement, and the pseudo-code representation.

First, in the framing of the statement, we've assumed a stored list of values exists and is called "X". Even abstracting this away to "the list of input values" (referring to it by its purpose, rather than a label) is still commitment to a paradigm at this early stage. On the language side, we've basically just taken the semantics of some reasonably ubiquitous "C-style" language (think C, Python, Ruby, whatever) and abstracted away some syntax. This really doesn't seem very useful in terms of "abstract thinking".

So is this really what people mean when they say "thinking in pseudo-code"? If so, that's just really a coded way of saying "I mentally construct programs in an idealised version of language X", where 'X' is some language (or perhaps group of similar languages) that the programmer is familiar with.

I'm really not a fan of early concretisation. I can't think how many times I've been in a meeting discussing high-level requirements with a group of technical and non-technical people. The conversation goes something like:

Non-Technical Person: We're really going to need X
Me: Are you sure you need X? Y seems to do everything you want equally well, and it might fit better with the established processes of the organisation.
Non-Technical Person: The processes that are important are...
Technical Person 1: ... we should do Z! because there will just be a couple of classes to add, and using language version 2.3.7 we can just use built-in serialisers to create an object store.
Technical Person 2: No, 2.3.7 will require a kernel upgrade, we should use 2.3.6 and avoid that altogether.
(...)
Me: *head explosion*

Names and specifics (and a little dramatic effect) aside, I've really had this exact conversation more than once in more than one organisation. What I've come to realise is that there are a lot of people who refuse to engage in a conversation in the abstract, and they have to mentally compile to code or implementation details in order to even engage with the conversation. I think this is probably the result of people who genuinely do think in pseudo-code in the way that I've described.

Naturally, this is all speculative, because I'm not sure I could force myself to think in code if I tried. I'm just not wired that way. I need to have a high-level understanding of a problem (which allows me to mentally formulate a high-level solution - usually in terms of the same abstract concepts used to describe the problem), and then "programming" becomes a typing exercise, in which I mentally translate from a high-level computational model to the code I'm writing as I type it.

So, I'm interested in hearing from people who do claim to think in 'pseudo-code'. Have I completely misrepresented what you mean when you say it? Are you actually writing in a language with syntax in your head? Do you close your eyes and see functions and objects and whatever else? Similarly, if you don't think like that, have you observed others that do?