Friday, 26 February 2010

What are the semantics of your favourite programming language?

"Focusing purely on syntax is like reading Shakespeare and then commenting on the excellent quality of the spelling" -- David Streader

I came across a recent post about the importance of semantics on the Abstract Heresies blog. While very short, it summed up well my general feelings about the attitudes of programmers to things like semantics. I get the feeling that for many, it goes something like this:
  • Learn the syntax of one language. Do some basic coding. High rate of errors.
  • Develop intuitions around semantics of that language. Rate of errors decreases.
  • Learn the syntax of another language. Do some basic coding. Rate of errors slightly less than after learning the syntax of the first language.
  • Develop intuitions around semantics of new language, relating these intuitions to the intuitions about the semantics of the first language. Rate of errors decreases.
And so on. I should take this opportunity to define what I mean by "semantics" (please excuse the self-referential nature of the last statement and this one). In the world of languages (formal or informal), there exists a distinction between the concrete representation of something, and what it actually means. In programming languages, this is essentially the difference between the program text that you feed into a compiler or interpreter, and the behaviour of the program once it is run. The typical approaches to defining semantics fall into two general categories - operational semantics, where one defines a kind of "abstract machine", specifying how its state is modified upon encountering some construct, and denotational semantics, where constructs in the language are mapped onto other structures that give them meaning (these are usually various kinds of mathematical structures). In human language, this syntax/semantics distinction could be demonstrated in the difference between the sounds that a person makes while speaking ("syntax"), and the understanding that one takes away from those words ("semantics").

Fundamentally, most errors in programs come from a disconnect between a programmer's understandings of the semantics of some system, and the actual semantics of that system. This could mean misunderstanding the effect of some statement in a programming language, or misunderstanding the effect of some statement in a specification (formal or informal).

Consequently, I really think that it is important to emphasise the semantics of programming languages. It seems like there is too much emphasis placed on syntax. Syntax is largely uninteresting - it differs in only trivial ways, even between languages that are radically different.

If I write down this definition:

function mystery 0 = 0
| mystery x = 1 / x

We can figure out what this function does based on our understanding of function application, and of division. That's not "real" syntax for any particular language. However, if we were to concretise it to a language, it would probably look similar in most languages, however we would very quickly begin to encounter semantic distinctions. Some languages will round the result, some will truncate it. Some will keep infinite precision, others will use floats or doubles. I would bet that with 5 different languages picked at random, you could get 5 different results.

These are relatively minor distinctions. How about this one?

function rec x = rec (x + 1)

It's obviously non-terminating, but what exactly does non-termination mean? Some languages will overflow the stack or exhaust some kind of memory limit within a finite number of applications of the function. Some languages may overflow their underlying numerical representation. Some might keep computing until they exhaust main memory. And some languages will never compute this function at all (because the effect is unobservable, so it'll be optimised away).

The effect starts getting even more pronounced when you start talking about objects and concurrency. Are your messages blocking or non-blocking? Is transmission guaranteed? How about ordering? Are there implied synchronisation points or locks? What does it mean for an object in one thread to hold a reference to an object in another thread, and call methods on that object?

While I'm an advocate of formal semantics, I'm a realist. I understand that that would not necessarily enrich the lives of all programmers. But c'mon guys, how about even an informal specification of the semantics of some of these languages that are in common use? Programmer experimentation gets you some of the way, but nothing really beats a rigorous treatment to shine a light in the dark corners of languages where errors hide.

Tuesday, 23 February 2010

The state of the world (and why I still think it's a bad idea)

I've been working recently on context-aware systems - i.e. systems that respond to some measurable things in the user (or computing) environment to infer a context, exhibiting some context-sensitive behaviour as a result. There are lots of things that can define a context, and many ordinary systems can probably be characterised as context-aware, particularly in the mobile computing space.

So, one obvious measured value from the environment is location, which gives rise to the most ubiquitous class of context-aware systems: location based services. In its simplest form, this might mean using a GPS built into a mobile phone or PDA to infer the location of the user, guiding him or her to relevant local points. For example, a user might want to see all the restaurants within walking distance - fire up the GPS, query the database of restaurant locations - done! So far, so pedestrian. There are plenty of services that have done this (and that have done it well).

The complication comes as we wish to integrate multiple sources of information to infer a single abstract notion of a context, or when we wish to integrate discrete information. At the IT University of Copenhagen, we have a system of BLIP (Bluetooth) nodes installed in the corners of the building on every floor. Coverage is not uniform or total, so a device (and therefore a user) may be seen in one corner of the second floor, disappear from the Bluetooth coverage, and moments later reappear on the 4th floor. It is therefore necessary to begin to abstract away from the real measured environment some more general notion of location or space. Adding more sensors measuring different values with different intervals simply compounds the problem further. The disparity between the real environment and the inferred context grows wider and wider.

This conceptual gap is where my problem with notions of global state come in. Building a system that represents state explicitly (and globally) is disingenuous in most cases. In the object oriented world, for example, one might be tempted to have a "User" object that records information about the locations of users. Except, that object is persistent, and the user really isn't. We're now in the world of confidence intervals and uncertainty. If I query the object associated with some user and ask "where are you now?" - the response will likely be a firm and reassured position in some coordinate space, or a reference to a node.

The problem exists because we've built an abstraction that is not a true abstraction of the underlying measured environment. If we base some behaviour on the response from the User object, we're likely to be acting on information that is well and truly out of date. The sensors actually don't necessarily know where a user is at any given moment, only that the user was seen in a location at some time. If we shift our abstraction to work on this basis instead (perhaps the User object returns a "last seen" timestamp and a location), then what have we gained from this abstraction? We can start to build a whole host of largely equivalent abstractions, none of which are particularly helpful, because they all rely on a notion of having total knowledge of the state of the world at all times. The kinds of stateful representations provided by most mainstream programming languages are, I argue, poor models of many measurable environments. Without building higher-order abstractions over the abstractions inherent in the language, we are forced to either build useless abstractions, or hide too much necessary detail.

If you agree with this premise, then you may wonder what the solution is. In short, it's reactiveness. In order to interact with the measured environment producing discrete values, programs must not rely on state information about the environment, rather, new facts must be computed as the measurements are made. When something changes in the real environment, programs must react to this change, and emit new events to be consumed by other programs (or parts of the program). In this way, idioms such as Functional Reactive Programming seem well suited to the task. Even outside the world of context-aware computing, it seems that persistent global state is often smoke and mirrors hiding potential data currency issues.

So the question I ask is: do you really need it?