Free Text Geocoding
September 1 2008
I think nearly everyone would agree that maps are useful things; I've only met a couple of people who labour under the illusion that they know the way from anywhere to anywhere. Personally I find maps more than interesting - they're often fascinating. Maps are one thing the British do immensely well (judging by some of the inaccurate doodles I've seen abroad). By looking at the detailed Ordnance Survey map of the area where I grew up, I can easily see layers of historical information such as: the Roman road a mile away; the long-abandoned railway lines upon which roads were later built; the now-drained marshes and the canal network later built upon them. Of course, these are fairlystandardmaps with a well-understood relationship to the real world; sites such as Strange Maps and Mark Easton's blog show how maps can present data in many other forms. My headmaster at school thought that geography as a subject had lost its way; instead of focusing on rock strata, it should focus on teaching children where places where. At the time, we all thought he was a touch eccentric; in retrospect, he was absolutely right. Huge tracts of politics, economics, and history only make sense in the context of a given place(s). I could go on, but I hope my point is clear: maps are important, and not just for finding our way around.
A big problem with traditional maps is finding things: places, areas, and so on. Even for a medium sized paper map, the size of the index is huge; and the index for a good quality London A-Z is often almost as big as the map itself. Paper map indexes have their own funny little language, trying to squeeze as much data in as possible. However paper indexes have two problems. First, how many times have you forgotten what square you were supposed to look at when you get to the proscribed page? Second, indexes can only grow to a certain size before they are unusable.
Computer geocoding
The advent of computer mapping has been a real boon, and not to just map fiends such as I. The first site I used regularly was Street Map. Having the map data for the whole UK was incredibly useful and the search facilities, while crude, were a huge improvement on a paper index. When later sites such as Google Maps became available, I was stunned. Suddenly freely viewable map data (though note I do not use the phrase free map data) for much of the world was coupled with a new way of searching. No paper index, or Streetmap's cloying need to be told what type of search was being performed (e.g. place name, street name, post code etc.). Instead is what I call (for want of a better name) free text geocoding: that is, where one types in something in the format used in real-life, and the search engine finds the right place automatically. One doesn't need to tell the search engine that the search is for a postcode or a place-name, or even which country one is searching - it magically does the right thing. Well, of course - not always the right thing. For example, at the time of writing, if I do a search for Penrith in Google Maps UK, I get taken to a suburb of Sydney in Australia. The poor residents of Penrith in the North of England don't even have their town mentioned as a possible match for the search; one must instead search for something like Penrith Cumbria or Penrith UK. There are a range of related minor infelicities in both Google Maps and Yahoo Maps. However on average, both do an adequate job.
There are several reasons why sites such as Google Maps are not as widely used as they might be. Regrettably the chief reason is legal: there are restrictions on the way that map data can be used. Fortunately an initiative - OpenStreetMap - to create much freer map data was started a few years back (and started by Brits - we are, it appears, a nation of map lovers) and is now at the stage where, despite many huge holes in its data, it is semi-usable: in central London, for example, it already has arguably the highest quality maps. Some of the uses of OpenStreetMap are already quite astonishing (the UK postcode layer is a simple, but effective, example of what can be done - click the little
icon in the top-right of the map for more fun), and its accelerating progress is impressive.
+
One part of OpenStreetMap that frustrates me a little is its search (the Name Finder). Although it does a reasonable job in many respects, the results it returns are hard to interpret (type in Penrith and then try and work out which result is the UK town - I got this wrong on my first go and I'm English!), and it's not easy to use it outside of a website (because it's written in PHP). Furthermore the version running on OpenStreetMap's front page is painfully slow (possibly because it's running on overloaded servers). [At the time of writing, I can't even work out how to get it to find Penrith in the UK automatically. Queries like Penrith, UK crash it. Penrith - please don't take the cold-shoulder from the map search engines personally!]
Free text geocoding
Since one of the huge benefits of using computer mapping is its search ability, I thought a fun little summer project would be to create my own free text geocoder. I started with only a vague idea of what a free text geocoder should (or could) do. While I don't now claim to have thought of everything, I do now have a much clearer idea of what a good free text geocoder should do. I've split these into must
and should
haves. A free text geocoder must:
- give accurate results (meaning it always, somewhere in the list of matches, gives the place the user is looking for). While this might seem obvious, some of the existing free text geocoders don't do this, as we saw earlier.
- require as little formatting from the user as practicable (e.g.
London SW1andSW1 Londonare both likely searches). - return any unmatched text (thus allowing searches like
cafes in Pimlicoto returnPimlico
as the place matched andcafes in
as unmatched text which an application can then use as it pleases). - be fast: results shouldn't take more than a second on average (and preferably should be much quicker).
- be localisable. This is both linguistic and cultural. Searching should take place disregarding the users input language, but results should be localised when possible. Results should be formatted relative to the users local cultural expectations (e.g. in the US, state names are always shown; in the UK county names are nearly always shown).
- be possible to use it do more than just find the latitude and longitude of a place.
- try and weight the results so that the
most likely
match(es) are given higher priority (e.g. an Englishman searching for Penrith should see the English town as the first match, while an Australian should see the Sydney suburb). - be usable in different contexts (e.g. in websites, or in applications).
- be amenable to (possibly quite low-level) customization.
Fetegeo
To this end I created, and have now released, Fetegeo with a BSD / MIT licence. Using Fetegeo's included client / server interface, queries can be performed on the command-line:
$ fetegeoc geo London Match #1 ID: 719913 Name: London Latitude: 51.508415 Longitude: -0.125533 Country ID: 233 Parent ID: 1262 Population: 7421209 PP: London, United Kingdom Dangling text:Of course, there are a lot of London's in the world and I haven't copied all of Fetegeo's output. Notice though that, since the preferred country of the user wasn't specified, it's chosen what most people are likely to consider to be
theLondon as the first match. If the user specifies that their country is Canada then London in Ontario is the first match:
$ fetegeoc -c ca geo london Match #1 ID: 2984878 Name: London Latitude: 42.983389283 Longitude: -81.233042387 Country ID: 39 Parent ID: 540 Population: 346765 PP: London, Ontario Dangling text:Fetegeo can be instructed to allow dangling (i.e.
unmatched) text in matches:
$ fetegeoc -d geo Museums in London Match #1 ID: 719913 Name: London Latitude: 51.508415 Longitude: -0.125533 Country ID: 233 Parent ID: 1262 Population: 7421209 PP: London, United Kingdom Dangling text: Museums in
If you're interested, there's a slightly more thorough description of the ways that Fetegeo can be used, and a simple demo which geocodes results and shows them on an OpenStreetMap map.
How Fetegeo works
Internally, Fetegeo's search is fairly simple and its approach is easily described. Strings in Fetegeo are always normalised; in particular punctuation is removed, and strings are lower-cased. String queries to the database are always on hashes of normalised words. Given a normalised string S, Fetegeo breaks it into a list of words. It then works right-to-left in the list, trying to find all possible matches. Whenever a match within S occurs, a counter is decremented meaning that subsequent matching takes place n elements from the end of the list. Matches are greedy; they always try to first match the maximum number of words possible, before gradually trying fewer words. Matches are exhaustive in the sense that all possibilities are tried; however only the longest matches are eventually returned to the user (some obvious optimisations are used here, so that some possibilities aren't tried if it's obvious they won't work). Fetegeo first of all tries to match the entirety of S as being a place within the users country; if that fails, it tries to match a country name at the right-hand side of the string. It then tries to match places and postcodes; if a place is found, it is considered to be a parent area; subsequent matches can only match places within that area or (recursively) a sub-area. Postcodes can occur at any point in the match. Of course, there's a lot more detail than this in the code, but this is the essence of Fetegeo's fast free text geocoding.
How Fetegeo compares
How does Fetegeo score on the must / should chart?
It's too early to say how accurate Fetegeo's results are. First, Fetegeo has only been relatively lightly tested so far: it's inevitable that there will be bugs and oversights. Second, any free text geocoder is subject to something I'm tentatively calling Tratt's First Law of Free Text Geocoding (though I doubt I'm the first to think of it): the upper bound for results quality is determined by your dataset. The best free text geocoder in the world can only give iffy results with an iffy dataset. Fetegeo's initial dataset is based on Geonames data (and postcode data from various other sources). While Geonames should be saluted as the first serious attempt to collate freely-available place data, the structure of the data is less than ideal, and the data itself is of variable quality, suffering from frequent inaccuracies and duplication. Because of this, Fetegeo has been designed to be relatively independent of any particular dataset; I hope one day in the not too distant future that OpenStreetMap's data will be sufficiently broad in scope to replace Geoname's (OpenStreetMap's data is already deeper in the sense that it includes roads, which Geonames doesn't).
Fetegeo is already reasonably fast, given that it's only been semi-optimised. On my 3-ish year old desktop machine, using the stock install of PostgreSQL (a few tweaks would, I suspect, make it perform much better - if only I could work out what those tweaks were amongst the mass of overlapping configuration options!), typical queries are answered in less than 0.1s. Fetegeo makes use of simple caching internally to speed things up. Someone who understands databases better than I could almost certainly make things run much faster.
Fetegeo has the beginnings of being usable for more than just longitude / latitude searches, but there is some way to go yet to prove this is feasible. In particular I would like to see it capable of being used by applications to classify things as being in particular areas. Imagine you have a website listing X's in Britain (where X could be just about anything), where each X is located at a particular latitude / longitude. This allows one to easily search for all X's near place P
. However users often want to perform area searches such as all X's in London
or all X's in Rutland
. Exposing the identifiers of places, counties, states (and so on) makes this latter type of query feasible.
Fetegeo is usable in a number of different ways. As such, Fetegeo is just a Python library which can be included and used in any application. Fetegeo also comes with a standard internet server and (command-line) client, which can receive and answer XML queries (as an aside, the XML parser used is often the slowest part of querying). This means that even a simple web-site can query a single Fetegeo server and make use of its caching facilities and so on.
Conclusion
I have no idea whether anyone will find Fetegeo useful. It seems to me that, even in its current embryonic form, it fills an unoccupied niche, at least in terms of its licence if not its functionality (yet). I hope that other people might find it interesting, and start to extend its functionality to make it more widely applicable. If you want to find out more, and contribute, please waltz on over to fetegeo.org.
Extended Backtraces
June 2 2008
I can quite distinctly remember when, as a teenager, I realised that I would spend much of my life debugging. I was programming in assembler, where loops are simply branch statements to defined labels. Because loops are so common, one would use the same label for each loop; later loops would redefine the label, meaning that no problems could occur. Being a literal person I used the labelloopfor all such loops. When one of my programs mysteriously failed, I could not work out why. Eventually I realised that one of my label definitions had spelt
looop(three O's instead of two) instead of
loop, so my loop had branched back to the previous loop in the file. Spotting that took me a couple of days.
Later, I realised that most programming errors fit into two broad categories: the obvious and the subtle. Obvious errors are those whose source can be easily pinpointed (even if fixing the problem takes a while). The subtle are typically those where cause and effect are separated, making identification of the root of the problem difficult (often, when eventually located, such problems are easily fixed). The looop
problem above was, to a relative novice programmer, a very subtle problem (years of experience have taught me that looking for daft spellings and in my own programs is a good initial target when debugging).
There are, to my mind, two tricks to debugging. The first is to try and turn subtle problems into obvious problems; however subtle problems are typically inherently subtle and unamenable to such treatment. The second is to try and speed up the solving of obvious problems. For me, the main tool for solving obvious problems is the humble backtrace which, when an exception occurs, shows one (in some manner or another) the call stack and, hopefully, what file and line number each entry therein is associated with. Given the following trivial program:
func head(l):
return [l[0], l[1 : ]]
func main():
head([1])
head([])
a standard looking backtrace would be:
Traceback (most recent call at bottom): 1: File "/tmp/head.cv", line 6 2: File "/tmp/head.cv", line 2 3: (internal), in List.get Bounds_Exception: 0 exceeds upper bound 0Using this we can fairly quickly see that the cause of our error is passing an empty list to a function which assumes that there is at least one element in the list. [As a side note, this example is in one way unrepresentative: in the vast majority of cases, it's typically the bottom one or two lines of the backtrace that pinpoint the real source of the error.]
Backtraces like the above can be found in most modern programming languages like Java. They are immensely useful and form precisely half of my debugging toolkit, the other half being printf - in my view of the world, these two tools obviate the need for debuggers. The power of backtraces is most obviously felt in those languages that don't have them. C programs typically need to be run through a debugger to get a backtrace, meaning that errors in programs running in production can be extremely difficult to diagnose. The first Haskell program I wrote had the head
error in it. The resulting message just said Prelude.head: empty list
with nothing else to help me - no line numbers or even file names. Needless to say, it took me a long while to work out what this meant, and how it happened (if I remember correctly, I passed an empty list to a library function which, in turn, called head). Unsurprisingly that was also pretty much the last program I wrote in Haskell - languages that turn should-be-obvious errors into subtle errors are of no use to me. [Apparently Haskell now has some in-built, though hardly easy to use, support for backtraces. The implications relating to Haskell's prioritisation of features are, to my mind, highly amusing.]
Python was the first language I saw that took backtraces a little bit further, printing (when possible) the line of source code associated with each part of the backtrace. A Python-esque backtrace looks roughly as follows:
Traceback (most recent call at bottom):
1: File "/tmp/head.cv", line 6
head([])
2: File "/tmp/head.cv", line 2
return [l[0], l[1 : ]]
3: (internal), in List.get
Bounds_Exception: 0 exceeds upper bound 0
This simple innovation is a real boon: as in this case, one often doen't even need to open a source file in a text editor to see the error made. Python-esque backtraces help make obvious errors quicker to solve than traditional backtraces.
I realised early on in Converge's development that knowing merely the line number of an error was only part of the problem. Often a specific sub-expression within a certain line is the relevant part of the backtrace, and the rest of the line is noise. Converge therefore recorded the column (i.e. offset within a line) where each error is associated with, meaning that backtraces looked like the following:
Traceback (most recent call at bottom): 1: File "/tmp/head.cv", line 6, column 4 2: File "/tmp/head.cv", line 2, column 13 3: (internal), in List.get Bounds_Exception: 0 exceeds upper bound 0This extra information is very helpful: it means that I can accurately pinpoint which of the two list lookups in line 2 is responsible for calling
List.get incorrectly. As a useful advantage, Converge's approach also means that errors that happen within multi-line statements (i.e. logicallines of source split over multiple physical lines in a source file to aid presentation) work properly.
Converge's backtraces stayed like the above for quite some time, until recently when I realised that knowing the start column associated with an error is only part of the story. What one really wants to know is the start and end of the associated expression. A small tweak to the parser, and a huge (but mechanical) change to the compiler, and Converge backtraces could tell one how many characters in the line an error was associated with:
Traceback (most recent call at bottom):
1: File "/tmp/head.cv", line 6, column 4, length 8
head([])
2: File "/tmp/head.cv", line 2, column 12, length 4
return [l[0], l[1 : ]]
3: (internal), in List.get
Bounds_Exception: 0 exceeds upper bound 0
This is almost helpful, but in practice I find it surprisingly hard to count n characters within a line on screen, which hinders interpretation of the above data.
A short while later, the answer hit me: what the backtraces need to do is to highlight the relevant sub-expression within the line. Here's a screenshot of the above error running in an xterm with the latest version of Converge:
As you might notice, the tiny little difference here is that the part of each line pertinent to the error is in bold and underlined. Knowing that, one can instantly see that the first of the two list lookups on line 2 is responsible for calling List.get incorrectly. Interestingly, my first attempt at this put the offending fragments only in bold, but since whitespace can sometimes be a significant part of an error, underlining can be a useful aid. In the case where the associated source code is split over multiple lines, the first relevant line of source code is printed with
added to the end of the line to inform the user that the printed line is not the end of the story.
...
As I explained in a previous entry, when Converge DSLs are translated into Converge ASTs, individual call stack entries can be associated with more than one source location. This means that backtraces tend to be rather long, which previously made tracking down the cause of an error tedious - loading multiple files into text editors and continually flipping back and forth to xterms is not fun. Extended
backtraces become a real life saver in this regard. Here's an example where a DSL incorrectly tries to subtract a string from an integer:
Looking at this backtrace, an experienced programmer will be able to quickly surmise that, given the exception message, the most likely candidate for this error is in the ex4.cv file (which, as the eagle-eyed may notice, is code written in the DSL - Converge's errors work with both the base language and with embedded DSLs). Imagine trying to debug this with a traditional backtrace: there's a lot of information in the backtrace, and there would be no indication as to which part of it is more likely to be responsible for the error.
From a practical point of view, Converge's extended backtraces have no run-time penalty for correct code, and users don't have to do anything to enable them - they're a standard part of the system. Extended backtraces can be found in -current versions of Converge (at the time of writing, Converge's support for Curses under Windows is weak, so underlining doesn't work there - it's a quick, fun little project for someone who's interested).
So, going back to the start of this entry, how do Converge's extended backtraces help with debugging? Well, they might help turn the odd subtle error into an obvious error, but that's an incidental benefit. What I think they do is make solving obvious errors much quicker than previously. In the sort time since I've had extended backtraces, I've noticed that I've often been able to almost instantly fix errors that before might have taken me a couple of minutes. Given the number of programming errors I make, the cumulative time saving is most welcome.
In summary, I think that Converge's extended backtraces are a real boon to programming. To the best of my knowledge, Converge is the first language with such backtraces in - I hope it won't be the last!
Designing Sane Scoping Rules
March 3 2008
If there's one thing which unites pretty much every post-assembly programming language it is the use of the humble variable. Variables are such a common feature that we tend to take them for granted; perhaps I show my background in assembly by being explicitly aware of them. However where programming languages often differ is in the way that they allow one to reference variables: the dreadedscopingrules. In this article I'm going to outline why Converge has the scoping rules it does.
The first thing I need to do is to outline the problem. Although all my examples are framed in terms of a typical
imperative programming language, the underlying concepts all translate fairly directly to functional languages too. Here's the simplest example possible:
x := 2 ... y := xIn every language I know this says
assign. So after this code is run both2toxand the assign the value ofxtoy
x and y will have the value 2.
The first major issue with regards to variables is global vs. local variables. Take the following code which is intended to represent the top-level of a source file:
x := 2
func f():
x := 3
f()
In a lot of BASIC-type languages there is only one underlying x variable in this program, so after this code is run the outer x will have the value 3. In essence we have a flat variable scope: all variables belong to the same, single, namespace. This not only makes writing programs error-prone (e.g. one function accidentally corrupts another's x), but makes certain styles of programming largely impractical (e.g. recursive functions). It's probably no coincidence that the first mainstream programming language to make a virtue out of recursion - Algol 60 - also was among the first to get its scoping rules in reasonable order.
Retro-fitting sane scoping rules is not easy if the first version of your language used the above scoping rule (note the deliberate use of the singular) - any change of scoping rule(s) has a high chance of breaking programs in nasty ways. Some of the BASIC-type languages I first used solved the backwards compatibility problem by making variables global
by default but allowing variables in functions to be declared as local. This allows one to rewrite the above example as follows:
x := 2
func f():
local x
x := 3
f()
This code now has two distinct x variables: one at the top-level and one in the f function. Every time f is called - even recursively - it will be given space for a new, fresh x. This feature makes programming a lot easier, even if it defaults to the insane globalscoping rule by default. As an aside, surprisingly (to me at least), you can still see the
global by defaultscoping rule in the modern language Lua. This goes to show how fundamental scoping rules are: once they're in a language, users will resist nearly all meaningful change to them.
Most programming languages adopt a slight variant of the above rules which are fairly easy to understand in practice. Essentially variables with the same name as a top-level variable reference that top-level variable directly, while all other variables are local. So in a C-type language the following code contains two variables: a top-level x and a y local to f:
x := 2
func f():
x := 3
y := 4
f()
Running the above code means that the top-level x is set to 3, while the y variable is local to f. Variations on this set of scoping rules underly many programming languages in use today.
The next major design challenge for scoping rules is much more subtle and confuses many of us to this day. Knowing that the global keyword in Python declares that assignment to a specified variable doesn't make it local to that scope, consider the following Python code:
x = 2
def f():
x = 3
def g():
global x
print x
x = 4
print x
g()
f()
print x
What do you think this will print out? Let's try it out with Python 2.5:
$ python scope.py 3 2 4 $In other words, we get a result which is a long way from what we might have expected: the
print statement in g prints 2 instead of the expected 3 and the final print statement prints 4 instead of the expected 2. What is it doing? What's happening is that most languages don't have nested scopes (as one might expect) but two scopes: a top-level (a.k.a. global or module) scope and a function scope. What this means is that the assignment to x in g references the top-level x, not the x in f; you might want to read that twice to check that you've really understood it.
It might at first seem that Python's scoping rules are simply silly; actually, they're not unreasonable and they're shared by most programming languages (e.g. Java). Why? The problem is that the function g might outlive
f. Here's a simple example:
func f():
x := 2
func g():
return x
return g
f()()
In other words, f returns a reference to g; when g is executed, the value of x known to f will have disappeared as, in most programming languages, variables are stored on the stack. This means that variables only exist for the duration of a function call. Since f's variables will have disappeared when g is executed, all sorts of bad things could happen.
Scheme was the first language that presented a practical solution to this problem of nested scopes in the form of closures. The standard way that closures are defined is guaranteed to confuse and I'm not going to repeat it. They're actually very simple: essentially each function allocates heap memory to store variables on. Thus if an inner function outlives an outer function there is no problem in referencing variables in the outer function even if the stack space has long since disappeared, since a function calls variables can outlive the function call itself.
[As an aside, the fact that closures need to allocate heap memory (although it's often possible to statically analyse such allocations away) has been used as an argument against them in languages such as Java. That's the chief reason that Java has all sorts of complications like inner classes, final variables and so on: Java resisted closures, and then had to resort to hacks to get a poor facsimile of its functionality. It's hard to imagine any decent programming language being built now that doesn't implement closures (Converge certainly does), so closures are gradually losing their exotic
tag (which, I suspect, is based on their definition and not their utility, which is far from exotic).]
When I was designing Converge, I put some effort into deciding what its scoping rules were going to be. I wanted to make things safe by default (e.g. no global by default
-type nonsense), and to make closures easy to deal with. Converge's scoping rules are (or, at least, were), I believe, the simplest of any imperative programming language. They boil down to this: assigning to a variable makes it local to a function; unless a variable is declared nonlocal, in which case scopes are searched from inner to outer to find the matching variable. That's it. Rewriting the Python example into Converge yields the following:
x := 2
func f():
x := 3
func g():
nonlocal x
Sys::println(x)
x := 4
Sys::println(x)
g()
func main():
f()
Sys::println(x)
Which when run does the expected:
$ converge s.cv 3 3 2 $The interesting thing here, in my mind at least, is the
nonlocal keyword. Although it's a tad awkward sounding, it was the best combination of brevity and accuracy that I could think of. Unlike Python it would be incorrect to declare a variable as global since there are more than 2 scopes: in fact, there are an arbitrary number. What nonlocal is saying is when you see an x search each successive outer scope in order to find where it was originally defined. It's not a commonly used feature, but when you need it is priceless.
I said above that Converge has - or had - the simplest of any imperative programming language (at least as far as I'm aware). Some time after the first publications and release of Converge, the Python team decided to fix their scoping rules for their backwards-compatibility-breaking Python 3000 release. PEP 3104 contains the eventual proposal they came up with. Interestingly it is identical to Converge's scoping rules even down to using the nonlocal keyword. Please note that I'm not suggesting that the Python team copied Converge uncredited (and even if they did, I wouldn't mind - I actively encourage people to take the good ideas from Converge and put them in other languages). However I think it shows that these are good scoping rules and that eventually imperative programming languages will evolve towards something like them.
The open question is this: why has it taken us, as a community, 50 years or more to define two simple scoping rules (assignment is local; nonlocal successively searches outer scopes) and one simple implementation technique (closures), and why have we taken so many wrong turns (in this article I haven't enumerated the silliest, such as dynamic scoping)? I suspect the answer, if it could be definitively uncovered, would give one a very interesting insight to the subject of computing in general.
Some Lessons Learned from Icon
December 3 2007
Updated: December 10 2007
One of Converge's lesser known influences is Icon. Although it's a relatively obscure language itself, a surprising number of people have heard of Icon's direct predecessor SNOBOL. I first heard of Icon through Tim Peters and Python, where Icon was the inspiration for Python's generator feature (basically procedures that whose execution can be resumed to produce multiple values). However Icon has a much richer, and definitely unique, approach to expression evaluation than any other imperative programming language. When I started working on Converge, I decided to go back to the source
, and see how much of Icon's unique approach I could incorporate into Converge.
This article is a personal look back at Icon's influence on Converge, and the successes and failures resulting from that influence. It's quite probable that much of it reflects my slightly superficial understanding of Icon - apart from its innovative approach to expression evaluation, much of the language has an old fashioned feel to it, sometimes appearing like a dynamically typed version of Pascal, and this prevented me from ever wanting to write anything large in it. This isn't a criticism of Icon as such - it was ahead of its time in many ways - but is merely an observation that modern programmers expect something slightly different from their programming languages. Hopefully, even with the above caveat, this article contains something of value to those interested in programming languages.
Why is Icon interesting
In a nutshell, Icon is interesting due to what it calls goal-directed evaluation. This is an evaluation mechanism which gives to an imperative programming language some of the flexibility more often associated with languages like Prolog, such as a limited form of backtracking. It is built around the concepts of success and failure, and generators (see the Converge documentation for more details). Expressions can succeed or fail; if they succeed, they produce a value; if they fail, they do not produce a value and transmit failure to their containing scope. Generators are functions which can produce more than one value.Icon's syntax is derived from Algol, so the following complete program prints 1 to 9 inclusive:
procedure upto(x)
i := 0
while i < x do {
suspend i
i := i + 1
}
end
procedure main()
every x := upto(10) do write(x)
end
Most of this is probably reasonably intuitive, apart from the every and suspend keywords. every can be considered to be equivalent to the typical understanding of a for statement (indeed, in Converge, the same construct is called for). suspend is equivalent to yield in Python or Converge, returning a value, but allowing the procedure calls execution to be resumed directly after the suspend statement.
Failure and if: a beautiful combination
If I had to pick one thing from Icon that I would not be without in Converge, it would be the concept of failure in if statements. There is something beautiful about saying if this function succeeded, assign the value to this variable and then do xyz. This idiom is used to build a very useful convention that is present throughout Converge's libraries. As in most languages, container items such as dictionaries have a
get function which returns the value associated with a certain key; geting a key which doesn't exist generates an error. There is a very a common variation on this use case, which is to check whether a dictionary has a certain key, and if it does to do something with its value; otherwise a different code path is taken. In most languages this idiom is expressed roughly as follows:
d := Dict{"a" : 2, "b" : 8}
if d.has_key("a"):
Sys::println(d["a"])
Not only is the double lookup of a an eyesore, and a maintenance accident waiting to happen, but it can be a significant overhead in tight loops. In Python (and probably other languages), it's common to see the following idiom:
d := {"a" : 2, "b" : 8}
try:
v = d.has_key("a")
print v
except KeyError:
pass
This idiom makes use of the fact that it's nearly always quicker to catch an exception if a key isn't found than to perform two lookups. In my opinion, this idiom is far from pleasant, for reasons that I'm sure most readers will intuitively understand.
In Converge one can express this common idiom thus:
x := Dict{"a" : 2, "b" : 8}
if v := x.find("a"):
Sys::println(v)
In this example, v only gets assigned a value if find succeeds.
There are some other advantages to this approach (e.g. there's no fiddling around checking for null), but the symmetry between get and find, and the consistency of this convention across libraries has proved a real success in Converge. For me, this feature alone justifies the Icon experimentin Converge.
Variables should not spring into existence with a default value
The idiom mentioned in the previous section is, unfortunately, somewhat dangerous in Icon itself, as all variables have a default value of sorts. What this means is that the following Icon code runs without error:procedure main() if 1 < 0 then x := 0 write(x) endTo me, this is odd, because
x never has a value assigned to it (as the expression in the if statement is clearly false); any errors resulting from such a mistake turn out to be very difficult to debug. In Converge I therefore made it so that reading from a currently unassigned variable raises an error, which protects against programming slips such as the following:
x := Dict{"a" : 2, "b" : 8}
if v := x.find("c"):
...
else:
Sys::println(v)
As the lookup of cfails,
v doesn't have a value assigned to it, so reading from v in the else branch of the if statement raises an Unassigned_Var_Exception, pinpointing the offending code.
Procedures shouldn't fail by default
In Icon, the defaultreturn valueof a procedure is failure. This makes quite a lot of sense for generators such as the following:
procedure upto(x)
i := 0
while i < x do {
suspend i
i := i + 1
}
end
As this suggests, the typical action for a generator is (via a loop) to generate several values; once that loop is finished, the generator fails. Thus each Icon procedure effectively has return &fail at its end. Very early versions of Converge inherited this behaviour.
What became quickly apparent is that while this is reasonable behaviour for generators, it can be a disaster for normal procedures. Look at this code and see if you can work out what will happen when it's executed:
procedure f(x) if x > 0 then return 1 end procedure main() write(f(-1)) endIf you guessed that nothing would be printed to screen, congratulations. If you didn't, then don't worry, because this frequently surprised me. This happens since the failure of the
if's condition in means that the procedure executes its default return action, which is to fail. Thus the procedure doesn't return a value, and the call to write is never even evaluated.
Although this might seem trivial, the problem becomes significantly worse when it's embedded in a large body of code. f is an example of what I informally think of as the dangling
- in other words, it's quite easy to write a procedure where different values should be returned, but where one branch of an if return problemif incorrectly neglects to actually return anything. I find this occurs quite often during the early stages of development when one is fleshing out functions. On several occasions I spent several hours tracking down instances of this problem.
The question I asked myself was whether this feature was worth the pain. A quick analysis of real world code quickly showed that the vast majority of functions aren't generators, and indeed only ever return a single value. Therefore optimising for the exceptional case (generators) is an odd design choice.
I considered two solutions to the problem. First, one could syntactically differentiate generators and procedures, with the former failing by default and the latter not. Second, one can make all procedures not fail by default. Adding new syntax is a decision that should never be taken lightly, and since generators aren't that common, I couldn't justify the added conceptual complexity. Therefore Converge functions became similar to Python functions, with their default return action being to return the null object.
Generators are useful, but easily hidden
Generators are an integral part of Icon and Converge, but as well as having no specific syntax to define them, there is no specific syntax to call them. Assuming thatg is a generator, I have grown quite fond of the following idiom:
l := [] ... for l.append(g())which appends every element generated by
g to l. However the problem in such cases is that it can be difficult to work out what part of the expression is the generator. Converge now tries to solve this problem by prefixing generator function names, whenever it makes sense, with iter_ which highlights that the function in question is a generator. This makes it easier to look at a piece of code and work out what it does without having to understand every function called.
Backtracking is rarely useful
One of the major features of goal-directed evaluation is that backtracking can be performed. The most common way for this to be achieved is by linking expressions together with&. The resulting conjunction of these expressions only succeeds if all of its component expressions succeed. The expressions are evaluated in order. If one of them fails, and a previous expression is a generator, then backtracking occurs. The previous generator is resumed to produce a new value, and the conjunction then resumes execution from that point.
Combining conjunction with for allows compact expressions such as the following to be expressed:
x := "abcabaacvcabcbab" for Sys::println(i := 0.iter_to(x.len()) & i % 2 == 0 & x[i] == "a" & i)This prints out every index position in
a which is a multiple of two, and which contains the character a (0 6 10 14 for those who are interested).
There are two problems with the above. Most obviously, it is incredibly difficult to read from a human perspective; indeed, it would be far better written as a couple of if statements within a for body. The second problem is that the form of backtracking used is often too weak to be useful. Icon allows variables in conjunctions to have assignments undone during backtracking, but even this isn't really enough (I didn't even bother implementing such functionality in Converge, because I couldn't really see its use). Full backtracking often involves undoing assignments within objects and so on, and no imperative language can ever hope to do this automatically.
Out of all the systems I've written in Converge, only one has made any practical use of the built-in backtracking, and even then it needed some manual help to be truly useful.
The fail variable causes bizarre behaviour
One way in which Icon shows its age is its differentiation between values and references. In keeping with most object orientated languages, Converge makes no such distinction to the user (although within the VM it does so for efficiencies sake). One of Icon's main oddities is that fail is a synonym for return &fail, while &fail is a sort-of reference to an invisible object.
Converge simplified this, so that fail was a variable pointing to a semi-special object (in similar fashion to the null object). However the fail variable proved, in admittedly rare cases, to be conceptually troubling. It's troubling in Icon too, although in slightly different ways. What do you think happens in Icon if I define l as the following and then iterate over each of its elements and print them out?
l := [1, &fail, 3]If you guessed that an error is raised because
l didn't get assigned a value (because evaluating &fail cause the whole thing to fail), pat yourself on the back. Now try this:
l := [] put(l, 1) put(l, &fail) put(l, 3)If you guessed that
1, then 2 get printed out, you're doing very well. And finally consider this:
l := [] put(l, 1) t := &fail put(l, t) put(l, 3)If you guessed that
1, then a blank line, and then 2 get printed out, you're doing much better than I ever managed to.
Converge's attempts to simplify thus were somewhat successful, but left one hole. While one could successfully evaluate the following list in Converge:
l := [1, fail, 2]the following mysteriously printed nothing:
Sys::println(l[1])since
l[1] is a synonym for l.get(1), which of course tried to evaluate return fail, which then caused get to fail. While this might seem a contrived example, it unavoidably cropped up when getting a module to return the value of a specific definition, since one of those definitions was fail.
fail was edged out of Converge in stages. A while ago, the recommendation became that the only safe idiom involving fail was return fail. Perhaps surprisingly, this was not an onerous restriction. Nevertheless it still failed to prevent the problem of fail being a definition in a module. Therefore the fail variable was finally banished entirely from Converge recently (although it lives on internally in the VM). fail is now an expression in Converge's grammar, and is equivalent to return &fail in Icon. Thus finally, all of the bizarre behaviour associated with the fail variable is forgotten, and I now sleep easier at night.
Do something different
When I was looking for information in Icon, I stumbled across a few interviews with Ralph Griswold (Icon's main designer), and a paper on its history. One thing that became clear to me was that a major design goal of Icon was not to be just another (boring) synthesis of a few existing language features - like the vast majority of programming languages - but to try out genuinely new things. Have a look at e.g. p38 of this interview or p6 and 13 of this paper looking back at Icon's history. Whatever you might think of Icon, it undoubtedly fulfilled this aim: its expression evaluation system alone has no precedent in contemporary programming languages (and there are other interesting parts of the language).When I was starting Converge, I agreed whole heartedly with this aim, but had no idea how to achieve it. Indeed, when Converge started, I only had the vague intention of chucking a few seemingly useful influences into the melting pot (initially Python, Icon, ObjVLisp, and ultimately Template Haskell when I'd got the mix of the former three languages about right). I had that vague feeling that either everything interesting had been done before, or that the remaining interesting things were outside of my grasp. To be honest, I sort of gave up on the aim of being innovative, and just concentrated on trying to mix Converge's influences together in a coherent way. What has been interesting is that as Converge has developed, new challenges have presented themselves, and I've had to find answers (some better than others) to such challenges. And in so doing, I think Converge has grown some genuinely innovative features, such as DSL blocks, and its approach to error information for macros amongst others. And in Converge's case - unlike Icon, as I understand it - the journey isn't over. Indeed, since I think Converge is currently nearing the end of the beginning, there's bound to be new challenges ahead, some of which will lead to new innovations of one sort or another, some ultimately successful, some ultimately not.
When I read about Icon's aim, and looked at the end result, I assumed that the innovative ideas in Icon had sprung out of nowhere. I, on the other hand, had no idea how to bring such ideas, fully formed, into the world. What's become clear to me is a restating of Edison's famous rule. Innovation is often a matter of perspiration over inspiration. Now my advice to those who wish to do innovative work is simple: if you put the miles in, you'll raise your head one day and discover that you're in a place where no-one else has ever found themselves in before. It's a good feeling, and one that benefits us all, as collectively we gradually discover what works and what doesn't.
Updated (December 10 2007): Used a clearer example in the Failure and if: a beautiful combination
section.
IEEE Software Special Issue on Dynamically Typed Languages
September 13 2007
Roel Wuyts and I were lucky enough to guest edit the current issue of IEEE Software magazine on dynamically typed languages. We had some very good submissions, and narrowing down the selection was quite a challenge!
The IEEE have helpfully put a few of the articles from the special issue online for free. Get them while you can! The full issue is available in paper form (obviously), or online, although you need IEEE membership to access the other articles.
| Earlier articles |