Suneido Exception Handling part 2

It actually didn't take that long to implement the ideas I talked about in my last post.

I ran into some problems with circular dependencies when I made my exceptions derive from SuString, but by splitting the header I got around these.

The hardest part was remembering how C++ exceptions work. A year of programming mostly in Java and already the C++ details are fading!

I remembered something in Effective C++ but it turned out to be in More Effective C++.

The recommended style is:

throw MyException(...)

...

catch (const MyException& e)

At first glance this seems wrong because you're throwing a temporary value, but C++ copies thrown exceptions. And catching by reference avoids a second copy that's done if you catch by value.

Of course, this recommendation assumes no garbage collection. With garbage collection, like in Suneido, it's reasonable to just throw and catch pointers, which is what I ended up doing. (Before changing to pointers I ran into problems because I passed the caught exception to the Suneido catch code, forgetting that the caught value is a temporary on the stack.)

It was a good reminder of the extra complexity in C++. In Java you don't have to worry about whether you have a value or a pointer or a reference and whether it's on the stack or the heap. You do have the difference between primitive types and reference types, but especially with auto-boxing and un-boxing it's pretty transparent. And in any case, it doesn't lead to crashes like forgetting a C++ value is on the stack.

Since exceptions are a sub-class of strings, all the existing code that assumes strings works fine.

I added two methods: exception.As(newString) to re-throw an exception with a different string. And exception.Callstack() to retrieve the call stack from an exception (e.g. to log it).

Next, I'll have to go through our libraries and make sure that any re-throws are done properly to preserve the original source of the exception, and that any logging uses the callstack from the exception.

Suneido Exception Handling

One annoying part of exceptions in Suneido is that there's no way to "properly" re-throw an exception.

You can catch (e.g. to perform some cleanup or logging), and then re-throw but then the debugger shows the source of the error as being your re-throw, not the original. This makes it hard to figure out the original source of the problem.

This was an area that caused me some confusion moving from C++ to Java. In C++ you re-throw by saying just "throw;" without any exception value. Java doesn't have this. At first, I thought that meant you couldn't re-throw in Java, but you can.

I had also wondered why Java code always constructed new exception objects to throw. Why not just have some static exception objects you could re-use?

The reason is that it is the exception constructor that captures information about the location of the error, and the call stack, etc. So obviously, re-using exception objects wouldn't work too well!

So to re-throw in Java, you simply throw the exception you caught. It will have the correct information since it was constructed at the site of the original error. (Unless you want to disregard that information, in which case you can always just construct a new exception.)

It seemed like this approach might be a possible way to improve Suneido's exception handling. But Suneido exceptions are thrown and caught as strings, not exception objects, which makes it a little tougher to include exception information.

But it should be feasible. The value given to catch could be an object that inherits from SuString, but adds exception information. throw could allow either a simple string, in which case you'd construct an exception string with information about the current call stack. Or you could re-throw an exception string from catch, in which case you'd preserve the original information.

And the string-like exception object could also have methods for getting the call stack information, which would be useful for things like logging.

Actually, cSuneido already does part of this. Internally, a throw creates an exception object that records the current frame and stack pointers. But catch is only given the thrown string part of the exception. And it's only recording pointers, so if any code runs (e.g. exception handling code) then the call stack is lost (overwritten).

To preserve the information, you'd have to actually copy it before it was overwritten. Currently, that's only done for uncaught exceptions which end up in the debugger. To allow catch and re-throw you'd have to copy the information before you executed any exception handling code, which would probably be simplest to do at the throw. This could slow down exception handling, but exceptions shouldn't be getting used anywhere that would be a problem. (Note: On Java with jSuneido the Java exception object already captures the information for us.)

finally
Currently, Suneido doesn't have support for "finally" like Java. I thought it would be easy to add this to jSuneido since Java supports it. But unfortunately, finally is implemented by the Java compiler, rather than the JVM. TANSTAAFL

jSuneido Progress

I've been making steady progress on the Java version of Suneido. I've been working on compiling to Java byte code and have functions with expressions and control statements pretty much finished. That leaves exceptions, blocks, and classes.

But yesterday I went back and made a fairly radical change to how jSuneido is implemented. I started at 7:30 am, started making changes, broke almost every test, and finally got the tests running again at 9:30 pm. (with breaks for lunch and supper)

cSuneido's data types all inherit from SuValue. Everything is done in terms of virtual calls on SuValue. I followed the same pattern in jSuneido and it was working ok.

The problem is that in Java this means everything being "double wrapped". e.g. a Java string is wrapped in a Suneido SuString. This isn't twice as much memory, since the wrappers are small, but it is twice as many memory objects. And it means every operation, (e.g. string concatenation) has to create both a result object and a wrapper.

Integers aren't as bad since the wrapper can contain the primitive type. But even integers are "worse" than cSuneido because it encoded them directly in the pointer. Needless to say, the JVM doesn't allow this sort of trick.

The other problem is that using wrappers like this makes the code a lot more "awkward". Instead of 123 or "hello" you have to write SuInteger.valueOf(123) or SuString.valueOf("hello").

Another area that I was thinking about was integration with Java code. With Suneido having its own types, you'd have to wrap and unwrap values in the interface, which seems ugly.

One thing that got me thinking about this was Scala's use of implicit conversions to extend existing classes (like String or Integer) without actually storing them in a wrapper. (Although I wonder about the performance impact of wrapping on the fly.)

I started wondering whether I could drop the idea of an SuValue base class and the derived wrapper classes, and just use Java Object instead. That way I could directly use native Java types like Integer, String, and BigDecimal.

The downside of this approach is that you can't do everything with virtual calls on SuValue. Since there's no common base class (other than Object, which obviously doesn't have the methods I need) you have to resort to instanceof and getClass. The object-oriented purists would frown on this. But again, Scala (and other functional languages) opened my eyes on this a bit, since matching on "type" is quite common and accepted.

So operations like "add" have to check the types of values and handle any conversions. This is a little ugly, but it's isolated in a small amount of core code that doesn't change much. And I can't say I was sorry to drop the double dispatch I was using. It's a good technique, but I still find it confusing.

Ideally, you'd test both approaches and measure speed and memory usage. Maybe if I had a team of programmers (or grad students) to assign to it. But with just me, part time, I can't see spending the time to do this. So I have to take my best guess at what the best approach is.

I decided it was the way to go and so I made the switch. Better now, when I could do it in a day, and not worry too much if I introduce bugs, versus later when I'd have more code, and less tolerance for bugs.

So far, I'm happy with the results. There are a few isolated ugly parts, but other than that it seems cleaner. Time will tell, although there's no way to know how the other approach would have worked out, so I'll never know for sure.

Testing Techniques

I've written quite a few tests that look like:

String[][] cases = new String[][] {
    { "something", "expected result" },
    ...
};
for (String[] c : cases)
    assertEquals(c[0], c[1], process(c[0]));

This works well enough, but one drawback is that when one case fails, there's no easy way to "go" to that case to edit it.

The testing people would probably say each case should be a separate test method, but that's a lot of extra declarations of methods.

So lately I've been writing tests like:

    test("something", "expected result");
    ...

void test(String input, String expected) {
    assertEquals(input, expected, process(input));
}

Written this way, when there's a failure Eclipse will take me straight to the failing case.

Another Technique

Sometimes it's useful to do some manual "exploratory" testing. (I know you should program test first, but I'm afraid I don't always manage it.)

For example, working on jSuneido's expression code generation I wrote a simple read-eval-print-loop so I could type in expressions and have them compile and run and print out the result.

One of the dangers is that you don't write so many automated tests because you're doing manual testing. To get around this I had my program write the cases to a text file in the correct format to paste straight into my tests.

For example, this session:

> 123 + 456
 => 579
> f = function (x, y) { x + y}; f(123, 456)
 => 579
> "hello world".Size()
 => 11
> q
bye

Added this to the log file:

test("123 + 456", "579");
test("f = function (x, y) { x + y}; f(123, 456)", "579");
test("'hello world'.Size()", "11");

Scala Attractions

Here are some of the things I find attractive about Scala. I still haven't written a line of code, though, so don't take it too seriously. Just first impressions of a language connoisseur :-)

user defined operators
In C++ you'd call this operator overloading, but Scala doesn't have a reserved set of operators. Even "+" is just a method. Obviously, this has potential to be abused, like any other feature. But it's a lot nicer to be able to say x + y for a new type of numbers, rather than x.plus(y)

traits
Scala traits are like Java interfaces, but they can include method implementations. They're similar to mix-ins. I struggled to do similar things in C++ so I can see the value.

implicit conversions
Ruby and other dynamic languages have "open classes" where you can modify existing classes at any time. They call it "monkey patching". It can be really useful, but I also find it really scary. Maybe I'm just a wimp, but I don't want standard classes changing under me. If I use some third party library or plug-in, I'm not sure I want the standard string or list class to change as a result.

Scala takes a different approach - you define implicit conversions to your own class. So instead of adding methods to String, you define an implicit conversion to MyString, which then has the extra methods you want. Scala provides a number of "rich wrappers" with implicit conversions for things like RichString and RichInt.

This is a good example of why you need to focus on the end, not the means. If what you want is to be able to write str.myOperation() there's more than one way to do that, and it doesn't necessarily require a dynamic language.

Of course, implicit conversions can cause problems as I know well from C++. But Scala's approach looks like it avoids most of the problems.

everything's an object
In other words, no more "primitive types", like in Java, that have to be handled specially. And no more boxing and unboxing. It's too bad Java didn't take this approach. There are performance issues, but with todays compiler technology they can be overcome.

first class functions
Meaning you can have unnamed function literals and pass functions around as values. To me, this is huge. Sure, you don't need this all the time, but to write higher level code it's invaluable.

lazy
This is a little thing, but I think it's cool that Scala provides a built-in way to do lazy initialization. As opposed to Java, where Effective Java has a whole section on how to do (and not do) lazy initialization.

type inference
Scala seems to combine the best of both worlds - the benefits of static typing, with almost the brevity of dynamic languages. Would you rather write:

val a = Array("one", "two", "three")
val b = new Map[String,String]

or:

String[] a = new String[] { "one", "two", "three" };
Map<int,string> b = new HashMap<string,string>();

I've talked about this before. C++ is just as bad as Java, although they are proposing an improvement in C++0X.

== is equals
I think Java made the wrong choice in making == compare pointers and equals compare values. I've talked about this before. It's great to see Scala break with Java and normally make == the same as equals.

actor model for concurrency
This is actually a Scala library rather than part of the Scala language. But it's a standard library. The actor model is what has made Erlang known for writing concurrent applications. I'm not sure how Scala's implementation compares to Erlang's, but it's nice to see tools for concurrency. Especially coming from C and C++ that basically said "not our problem". I wonder if I can make use of this when I get to making jSuneido's database concurrent?

lists and tuples
These are classic functional data structures. Although I wouldn't say I "know" functional programming, I'm certainly not ignorant of the benefits of imutable data structures and the dangers of side effects. My programmers will tell you I've been know to harp on the evils of side effects. cSuneido makes good use of lists and other imutable data structures.

class parameters
This looks like a great shortcut for writing simple classes. Would you rather write:

class Data(count: Int, name: String)

or:

class Data {
    final public int count;
    final public String name;
    Data(int count, String name) {
        this.count = count;
        this.name = name;
    }
}

optional semicolons
If nothing else, this will save me from the annoyance of typing semicolons in Suneido where I don't need them, and then turning around and omitting them from Java where I do! The joys of switching languages every other day!

Mozilla Labs - Bespin

Here's another interesting Mozilla Labs project - a web based programmer code editor, with some interesting UI innovations.

Mozilla Labs - Bespin

Introducing Bespin from Dion Almaer on Vimeo.

Mozilla Labs - Ubiquity

This isn't new, but I just came across a reference and looked it up. Sounds pretty interesting.

Mozilla Labs - Ubiquity


Ubiquity for Firefox from Aza Raskin on Vimeo.

Not Your Father's Spreadsheet

Google Spreadsheets has some interesting features like Google Lookup and Auto-Fill.

Scala Gets My Vote

Of all the languages I've read about recently, Scala strikes me as the one I'd most like to use.

I've always been interested in (computer) languages. I haven't actually seriously used many different languages - mainly C, C++, and recently Java. But I've avidly read about many.

I have books on Scheme, Smalltalk, Perl, Python, Icon, Dylan, C, C++, C#, Tcl, Ruby, Java, Lua, JavaScript, Erlang, Groovy, Scala, and probably more that I've forgotten.

I'm just finishing reading Programming in Scala by Martin Odersky (the creator of the language), Lex Spoon, and Bill Venners. Part of what prompted me to read it was a podcast with Bill Venners talking about why he likes Scala.

I liked C++. People criticize it because it was too complex, but I liked it's powerful features.

I can't get excited about Java. It's ok, and it has great IDE support, but it's a little boring. I like the garbage collection and the safety of no pointers, but I miss C++'s tricks with things like templates and operator overloading.

For some reason I haven't got too excited about Ruby either. I haven't written much code in it, but I've read a fair bit, gone to conferences, and managed a project written with Rails.

Ironically, Java compared to C++ is a bit like Suneido compared to Ruby. Both Java and Suneido try to avoid features that, although powerful, allow you to "shoot yourself in the foot" (if not in the head!)

Scala feels more like C++, lots of power and flexibility and tricks, enough to probably make your head hurt.

Both Scala and C++ try to support writing powerful, natural libraries and extensions, which I like.

For "system" programming (as opposed to "application" programming) I still lean towards static typing. But I do get tired of the verbosity of type declarations in C++ and Java. Scala is statically typed, but it also does type inference which greatly reduces the verbosity.

And it's a plus for me that Scala runs on the JVM and can be easily integrated with Java. (There's a .Net version as well, although not as well supported.) It seems like I could write parts of jSuneido in Scala if I wanted. I suspect you still might want to implement performance bottlenecks in Java, though. Or at least be careful which Scala features you used, since power often comes at a price.

Scala supports functional programming, but in combination with more conventional object-oriented programming. I haven't spent the time to wrap my head around "pure" functional languages like Haskell or (O(Ca))ML. But I could see using some functional programming in Scala.

I thought the Programming Scala book itself was good. It's not small - 2.6 lbs and 776 pages, but I had no trouble getting through it. I see it won a Jolt Award. Apress also has a Scala book, and both Pragmatic and O'Reilly have Scala books coming.

Tech Social Skills

Our internet access quit working the other night. I tried the usual things, restarting computers, routers, cable boxes, etc. But no luck.

So I called tech support. After working my way through the voice menus I finally reached a recording - which said more or less:

"We are currently experiencing problems in the City Park area.
We are working on it.
If you are calling from this area, hang up now."

Perfectly logical, but it sounds like Spock from Star Trek. No apology, no explanation, no asking for patience. Basically just "get lost, don't bug us".

Update: The next day (yesterday) the internet was working during the day but sometime around 4 or 5 pm it died. I would speculate that everyone got home from work and rushed to see if it was working and the load crashed their system and it stayed off all evening.

Side Note: Why do you have to work through Shaw Cable's entire voice menu system to get to internet support? I got the number from a sticker on the cable modem. Couldn't they have a separate phone number? I guess that wouldn't be as convenient for them.

"Getting" Git

The Git version control system, originally developed by Linus Torvalds for the Linux kernel, has been getting pretty popular lately, especially in the Ruby on Rails crowd.

There's a preliminary Eclipse plugin and even a TortoiseGit project. SourceForge is even offering it already, whereas it took them forever to get Subversion.

At RailsConf last year I went to a session on Git Internals by Scott Chacon and was quite intrigued. You can see the slides with voice over.

Suneido has it's own version control system that has served us well, but it's pretty basic. Git's distributed style and easy branching would be nice to have.

At OSCON 2006 I had gone to a tutorial on Subversion API's with the idea that maybe we could replace Suneido's version control with an interface to Subversion. I was disappointed to find that the API's are all file oriented. I even talked to the presenter after the session to see if there was any way around this, but he couldn't suggest anything. As far as I can tell, Git is similarly file based. Probably a big reason for this is that these types of systems usually evolve from shell scripts that, understandably, work with files.

My interest in Git was raised by reading Pragmatic Version Control Using Git. On top of that, we've recently had some problems with Suneido's version control. Nothing major but still impetus to think about something better. I started to think about what it would take to implement Git like version control in Suneido. Having enjoyed his talk, I also bought Scott Chacon's PeepCode pdf book on Git Internals which expands on the same material.

The basic ideas behind Git are pretty straightforward, although quite different from most other version control systems. The way it works is attractively elegant and simple. Yet it supports powerful uses.

One area where Suneido's version control has problems (as do other version control systems) is with moving and renaming. Git supposedly handled this, but I couldn't figure out how. There didn't seem to be anything in the data structures to track this. Strangely, neither the Pragmatic book or the Git Internals pdf talked much about this.

But it didn't take long on the internet to find the answer. The Wikipedia article was surprisingly useful. It turned out to be an issue that had seen some discussion. For example this mailing list message and this one.

I was right, the data structures don't record any information about moves or renames. Instead, that information is heuristically determined after the fact, by looking at file contents.

One of the common uses of Suneido's version control is to check the history of a record. (Although we haven't gone as far as to implement a "blame" utility yet.) But the way Git works, this is not a simple task. You have to work back through each version of the source tree looking for changes to the record. But no doubt there are ways to speed this up, maybe by caching which records were involved in each commit.

I worked up enough interest and understanding to take a stab at implementing something this weekend. I have a prototype (a few hundred lines of code) that can save a source tree in a repository and retrieve it again.

Performance is a bit of an issue. Git works by comparing source trees. We have about 15,000 records (think source files) in our main application. Building a Git style tree of the working copy takes some time. But it turns out most of the time is not reading the records, it's calculating the hashes. It shouldn't be too hard to make a cache to speed that up. (You could store the hashes in the libraries but that would be dangerous since something might update content without updating the hash.)

There's obviously still a ways to go before it would be able to replace Suneido's existing version control, but it's enough to convince me that it would be feasible. Just what I needed, another project :-)

Leaky Abstractions

Originally, Suneido memory mapped the whole database file at once. This is a simple, fast way to access a file. (Note: This doesn't load the whole file into memory. It uses the virtual memory system to load pages of the file on demand.)

Unfortunately, 32 bit cpu's have a limited amount of address space. Windows only allows a maximum of 2 gb and often you have to share that space with other things.

To allow databases bigger than the address space, I changed Suneido to memory map the database file in sections. Once you've filled up the address space, if you want to map another section, you have to unmap one of the previous ones.

This is a lot like how virtual memory works, and you have the same question of which section to unmap. What you really want is to unmap the section that you're not going to need for the longest time into the future. Unfortunately, there's no way to predict the future. Instead, various heuristics are used, a common one is to unmap the least recently used (LRU) section. In other words, the mapped sections form an LRU cache into the database file.

I used an efficient approximation of LRU called the clock algorithm. We've been using this for a long time and it seemed to work reasonably well.

But recently, we started to get occasional errors from loading large databases. Often this kind of thing is caused by memory or disk errors or corrupted data. But the strange thing was that the error was consistently reproducible. We could bring the dump file back to our office and try to load it and get the same error. And the database wasn't corrupt as far as we could tell - later dumps would load fine.

I started to suspect something to do with the memory mapping. One clue was that we only had this problem on large databases.

Eventually, I discovered the problem. The rest of the database doesn't do anything to "lock" sections in memory while it works on them. Instead, it simply relies on LRU not unmapping anything that's been recently used.

But I was using an approximation of LRU. In certain rare cases the clock algorithm can end up unmapping a recently used page. (That's why it's only an approximation of LRU.) Normally that's not a problem. But because I was depending on LRU, when this rare case happened, it resulted in the error we were getting.

To fix it, I simply implemented a "true" LRU algorithm. It'll be a little slower than the clock algorithm, but given how it's used I don't think this will have a noticeable affect. And the code is actually simpler, which is always nice.

The moral of the story is I got burnt by what Joel Spolsky calls a leaky abstraction.

PS. With jSuneido, I'm considering going back to the old system of mapping the whole database file at once. This would limit the size of the database on 32 bit systems, but it's probably not unreasonable, especially in the future, to require a 64 bit system if you want a big database. This would simplify the code and eliminate bugs like the one above.

String Concatenation

Working on jSuneido, I noticed that I hadn't implemented Suneido's optimizations for concatenating strings.

In most languages this kind of code is grossly inefficient:

s = ""
for each line
  s = s + line // concatenate on the end

That's because each concatenation is allocating a new string, a little bit longer each time. The normal solution is to use a different mechanism, e.g. a StringBuffer in Java.

Suneido optimizes this case by constructing a linked list instead of allocating a new string each time. Later operations then "flatten" the list into a simple string.

The downside is that if you concatenate a lot of little strings the linked list representation uses a lot more memory than a simple string. i.e. we've traded memory for speed

Reading the 2nd edition of Programming Lua, I came across the usual discussion of why it's bad to concatenate like this. But they recommend a different solution - to keep a stack/list of pieces with the invariant that you can't put a bigger piece on top of a smaller piece. Instead you combine them, and if the newly combined piece is bigger than the one below it, you combine them, and so on.

It took me a minute to think this through. If you're adding random sized pieces, then 50% of the time you'll be adding one bigger than the last one, and therefore combining them. The end result, if I'm thinking this through properly, is that, on the average, each piece in the stack/list will be half as big as the one before. So a list of N entries will hold roughly 2 ^ N characters. i.e. you can build a big string with a short stack/list.

The Lua book is suggesting doing this in your application code, but my thought is to replace Suneido's current algorithm with this one. I'd be interested to see how it compares. It will do more concatenation and allocation, but will use less memory when dealing with a lot of pieces. It also does the concatenation more "incrementally" rather than one big concatenation to flatten the list like cSuneido currently does.

High-Tech Storytelling

This is a cool video. It's about 10 min and best viewed full screen (button just left of the "vimeo" at the bottom).


World Builder from Bruce Branit on Vimeo.

Digital Photography

One of the interesting trends in digital photography is combining multiple images to overcome limitations of sensors and lenses. This is primarily a software trend, that seems to be gradually moving from desktop software to in-camera features. Of course, the desktop software isn't standing still either - the latest Photoshop has some amazing features, and special purpose software does even more.

One of the first uses of multiple shots was for simple panoramas. But people are also using this to get high resolution images from lower resolution cameras. For a while, cameras have had modes to help with this, showing you the previous shot while you line up the next one (and keeping the exposure the same). Now the new Sony HX1 has a "sweep" mode where you just hold down the shutter button and "wave" the camera. It decides what individual shots to take. Cool. (It also has a 20x zoom lens and shoots 1080p hi-definition video!)

Multi-shot techniques are also being used for high dynamic range (HDR), where you take multiple shots at different exposures and blend them together. (examples) You can do this with software like Photoshop, but it's also moving into cameras like the Ricoh CX1.

And multiple shots can be used to overcome limited depth of focus. (You can also go the other direction and simulate a smaller depth of focus.)

The Sony HX1 will even take multiple shots and keep the one where the person's eyes are open.

None of this would be practical without a variety of technological advances - faster image capture, bigger/cheaper memory, more processing power in camera and in computer.

These techniques are sometimes called "computational photography".

There are so many cameras out these days that it's impossible to keep track. A couple that have caught my eye lately are the Canon PowerShot SX200 IS which is a descendant of the S3 I have but much smaller and with 12 mp and 720p video. It looks perfect for travel. And the Olympus Stylus Tough-8000 which is waterproof (to 10m/33ft), shockproof, freezeproof, and crushproof. Can't beat that for adventure sports.

I used to shake my head at my father's collection of cameras, but if I'm not careful I'll end up with my own. The sad difference is that his film cameras stayed relevant a lot longer than any camera you'll buy today, which will be out of date before you get it home.

jSuneido Language Implementation

As the saying goes, "be careful what you wish for".

I was getting tired of the somewhat mechanical porting of code from C to Java, and I was looking forward to the language implementation because I knew it would involve some thinking.

Of course, now that I'm in the middle of thrashing around trying to figure out the best way to implement things, I'm thinking maybe there's something to be said for having a clear path!

"Mapping" one complex object (Suneido's language) onto another (the JVM) is complicated. There are a lot of choices, each of them with their pro's and con's. And you never have complete information either about how things work, or what their performance characteristics are.

Some of the choices won't be easy to reverse if they turn out to be wrong. Often, you're not even sure they were "wrong". They might turn out to have awkward parts, but then again, any design choice is likely to have awkward aspects.

One of the things to remember is that the Java language and the Java Virtual Machine (JVM) are different. Some features are implemented at the Java compiler level, and so they're not directly available at the JVM level. You have to implement them in your own compiler if you want them.

I'm also having trouble fighting premature optimization. On one hand, I want a fast implementation. On the other hand, it's better to get something simple working and then optimize it.

For example, I'd like to map Suneido local variables to Java local variables. But to implement Suneido's blocks (think closures/lexical scoping) you need a way to "share" local variables between functions. The easiest way to do that is to use an array to store local variables. But that's slower and bigger code. One option is to only use an array when you've got blocks, and use Java local variables the rest of the time. Or even more fine grained, put variables referenced by blocks in an array, and the rest in Java local variables. While faster and smaller, this is also more complicated to implement. To make it worse, when the compiler first sees a variable, it doesn't know if later it will be used in a block. So you either have to parse twice, or parse to an abstract syntax tree first. (Rather than the single pass code generation during parse that cSuneido does.)

One of the things that complicates the language implementation is that Suneido allows you to Eval (call) a method or function in the "context" of another object, "as if" it were a method of that object. This is relatively easy if you're explicitly managing "this", but it's trickier if you're trying to use the Java "this".

I'd prefer to map "directly" to JVM features like local variables and inheritance because the resulting code will be smaller and presumably faster (since JVM features will have had a lot of optimization). And presumably the closer the match, the easier it will be to interface Suneido code with Java code.

Despite the initial thrashing, I think I'm settling into a set of decisions that should work out. I already have code that will compile a minimal Suneido function and output java bytecode (in a .class file).

So far, ASM has been working well. Another useful tool has been the Java Decompiler so I can turn my generated bytecode back to Java to check it.

Computer Vision

Knowing in theory that things are possible is a far cry from actually seeing them.

I'm not sure what the practical applications of this technology are, but it's sure cool!

jSuneido Progress

Yesterday I worked on re-implementing the database request and query parsers.

I got the request one done and a good portion of the query one. I'd hoped to finish it in one day, but I didn't quite make it. Probably another half day or so.

It slowed me down a bit trying to share code with the language lexer and parser, yet keep the code independent.

The only difference in the lexers is in the keywords. Unfortunately, there's no way (that I know of) to extend enums. Separate Token classes would have meant duplicating the common stuff - yuck!

Instead, I decided to make the lexer include both sets of keywords. The extra coupling is unfortunate, but I figure it's better than duplication.

Luckily, the way the parsers work, keywords are not "reserved". So it doesn't hurt either parser to have extra keywords. (It wouldn't have been hard to "enable" only ones needed in a particular case, but it would have been one more complication.)

I also ran into complications with generics. The parsers take a type parameter so they can be reused with different "generators" e.g. to generate code, or execute directly, or build a syntax tree. There's a lot of actions shared between the different parsers (e.g. for expressions). The parsers also call each other (e.g. queries call the expression parser) so the generators have to be type compatible. I ended up with code like:

But compared to some of the twisted C++ template code, it doesn't seem too bad.

(I ended up having to use an image for that line of code because Blogger kept getting messed up by the angle brackets, even if I entered them as & lt ; in Edit Html mode.)

Java Enums

When Java (1.)5 came out with the new enum facilities, I thought it was cool, but I wasn't sure how practical it was. Allowing members and methods on enums? It seemed weird. Of course, this was coming from a C(++) background where an enum is just a thinly disguised integer.

But now that I'm programming in Java I'm actually finding these facilities quite useful. For example, in the lexical scanner Token class I attach various information to the tokens:

• the string "name" in the case of keywords
• the "matching" token for parenthesis, braces, and brackets
  
• whether it's an infix or assignment operator

I use a separate TokenFeature enum for the infix and assignment features, and store them using an EnumSet, which represents them as bits in an integer (for small sets).

The only awkward part is having to define a bunch of different constructors.

Having this information attached to the tokens simplifies the code quite a bit, avoids duplicating the information in several places, and makes it easy to maintain.

PS. Looking back at the code, I think it could be simplified. All assignment operators are infix (at least for my purposes) so I don't really need a set of features, the infix method could just check for INFIX or ASSIGN. Sigh ... sometimes it seems like the refactoring never ends!

Robots

Check out these photographs:

http://www.boston.com/bigpicture/2009/03/robots.html

How FriendFeed uses MySQL to store schema-less data

Here's an interesting database approach that deliberately does not use conventional database indexes.

How FriendFeed uses MySQL to store schema-less data

cSuneido Query Improvement

Recently we've been working on fixing some of the "slow" queries in our applications. Usually this means adding appropriate composite (multi-field) indexes.

But in one case, that didn't completely fix the problem. We added the index necessary to select the right data but then we summarizing by different fields and that was requiring a temporary index.

Thinking about this, I realized that it doesn't make much sense to create a temporary index so summarize can read the data in the right order to process it sequentially. Better to just read the data in any order and accumulate the results. That means you have to process all the data before you can produce any output, but that's no different than having to create the temporary index first. And (in most cases) the accumulated results will be smaller that the temporary index, since you're summarizing.

It didn't seem like this should be too hard to add. (typical programmer optimism)

But then I started looking at the code and I realized that although the query operations choose strategies, they weren't actually using the strategy pattern. Instead they just have a bunch of if's to alter their behavior based on the chosen strategy.

It's funny that hasn't struck me before. It seems so obvious. And it's not like I just learned about the strategy pattern. I read Design Patterns when it first came out in 1994, 15 years ago. I'd made each query operation a separate class, but for some reason I'd stopped there.

So I decided to refactor the summarize code to use separate strategy classes. Which again turned out to be a bigger job than I thought.

I started out with just using my text editor (Scite) but I've been spoilt with all my IDE usage. So I tried using NetBeans (6.5). But that didn't work too well. I could build from NetBeans but I couldn't double click on the errors to go to the offending source. (Even with Scite I can do that.) And I couldn't seem to configure it to my indenting style (Whitesmith's).

So I switched to Eclipse. It's not as easy to import a project into Eclipse as it is in NetBeans, but after a few false starts I get it going. It does support Whitesmith's style. And you can double click on the errors. But C++ support in NetBeans or Eclipse isn't anywhere close to as nice as Java support.

One problem with splitting things up after the fact is that the code tends to have developed interconnections. Luckily it wasn't too hard to pass the necessary information.

Shortcomings of Test Coverage

It didn't surprise me, but some people might wonder how I could have a bunch of bugs left in the parsing code, when I had pretty complete test coverage.

It wasn't because the bugs were in the few lines that weren't executed by the tests.

The problem is that just executing every line doesn't means you've tested all the possible "paths" through the code. And it certainly doesn't mean you've tested every possible input.

For something like the parser with many branches (if's and loop's) and deeply recursive, it's pretty much impossible to test every possible "path".

I still think it's worthwhile aiming for good test coverage. If you don't have good coverage that means there are parts of your code that haven't ever been run by your tests. And we all hate the bugs that seem so blatant that people say "didn't you run this?".

So just don't let good test coverage give you a false sense of security. There can still be lots of bugs hiding in those untested execution paths.

Another jSuneido Milestone

jSuneido now parses Suneido code, at least the 11 mb of source code that I threw at it.

Note: I'm only checking that it parse successfully - I'm not checking the results of the parse so there could still be problems. For example, in ambiguous cases it might be picking the wrong choice. But I don't think it's too likely because the wrong choices almost always lead to later syntax errors.

It didn't take long to set up the framework to read cSuneido dump files since I already had done this for loading stdlib into the database.

I initially expected a lot of failures but I was still a little surprised when it failed to parse a single record from stdlib! But I was still fresh and the sun was shining (although it was -30!) so I could laugh.

I soon found it was because all the stdlib records start with a copyright comment. Of course, none of my tests had an initial comment. This was easy to fix.

After that it was just slogging, fixing errors one by one. Sometimes programming seems like mountain climbing. Finishing a project and getting to the top are great, but you'd better enjoy the process as well, since that's where you spend most of your time.

I was really hoping to get the parsing working by the end of the day, but by late afternoon it seemed like I might not make it. Then I fixed one more bug and ... no more errors! It threw me off for a minute. I'd grown so accustomed to the error output that it took me a minute to realize it had succeeded.

I wish I could say I was done with parsing, but I still have to go back and rewrite the query parsing to not use Antlr. Oh well, that shouldn't take too long.

Then on to actually generating Java byte code! I'm going to try using ASM to start. It looks promising and even has an Eclipse plugin, but if it doesn't work out, there are other alternatives.

jSuneido Progress

I pretty much have the parsing port finished. I think of Suneido as a "small" language, but it's big enough when you're trying to parse it! I have over 90% test coverage (as reported by EclEmma). The only parts that aren't well tested are the error handling. I should probably add a few more tests for that.

The tests are more "functional" than "unit" tests. If something broke they wouldn't be much help locating the exact source of the problem. But I think it would be hard to write true unit tests for something like a recursive descent parser. I'm happy enough with the functional tests.

There are probably a few things I've missed, especially to do with optional semicolons. Next I plan to try parsing all our Suneido source code. That should flush out any remaining issues.

I also want to go back and rewrite the query parsing so I can eliminate the remaining dependencies on Antlr. This shouldn't be too hard. The lexical scanning is the same as the language, just with a different set of keywords, so I don't have to write that.

Then I'll be on to the fun challenge of actually generating Java byte code.

In the long run I'd prefer not to support two implementations of Suneido. Assuming jSuneido works out for the server, I'd like to move on to figuring out how to implement the client side. The hard part here is the UI. Currently, Suneido's UI calls the Win32 API directly.

One short term solution might be to look at whether Java can call the Win32 API. If so, this would allow a quick port, although it would limit the client to Windows.

Another obvious, but longer term, approach would be to rewrite the UI in Swing or SWT.

A less obvious, but interesting approach would be to go with a browser type approach using HTML, CSS, Javascript. This is a really messy, ugly approach, but it has some interesting properties. For example, it's the approach being taken by the new Palm webOS.

In any case, this is all speculation. I've still got plenty to do to get the server part of jSuneido working.

Eclipse Tip for Windows and Mac Users

Switching back and forth between Windows and Mac, my fingers find it hard to remember whether copy/cut/paste/undo/redo are with the control key or the command key.

In Eclipse you can configure the keyboard so you can add the control versions of these (as well as the command versions).

I also added home and end (Line Start/End).

One nice feature of Windows under Parallels on the Mac is that it lets you use either command or control.

There's Always a Better Way

I'm working on the parser for jSuneido and it's going well.

In a few places the parser needs to "look ahead" at future tokens.

In cSuneido I did this by looking ahead directly in the source string.

When I was porting this code it seemed a little ugly. For example, it handled skipping whitespace but not comments. (Meaning you couldn't put a comment in certain places in the code.)

My next thought was to save the state, scan ahead, then restore the state. Easy enough, especially since it didn't have to be nested.

But it still seemed a little ugly.

Then I realized, I could just clone the lexer, and read ahead in the clone without disturbing the original. (I didn't use the Java clone stuff since it's a little twisted. I just made a "copy" constructor that takes another lexer.)

I'm a lot happier with this solution. I bet there's an even better solution out there, but this one will do for now.

I think one of the big weaknesses in beginning programmers is that they tend to settle for the first thing that works. But there are always other solutions and the first one you come up with is unlikely to be the best.

Of course, this is also what refactoring is about - improving your code, not settling for the first draft.

The hard part in this porting is having to read all the old C++ code and see all kinds of ways it could be improved. But I have to resist refactoring the C++ code or I'll never make any progress on jSuneido. One thing at a time. It's enough of a challenge to make the Java code as clean as I can.

PS. I'm back to using Eclipse. I could be happy with NetBeans but I find Eclipse a little better. Of course, part of that is just that I've spent more time with Eclipse.

NetBeans

In a totally unwarranted diversion from the job at hand I decided to have a "quick" look at NetBeans.

Download and install were easy and quick.

A minor quibble was that it asked me to register and I would have, but it just took me to a web site to create an account. No thanks, I've got better things to spend my time on than creating yet another account.

NetBeans can import Eclipse projects so I had my project open in no time.

I ran all my tests and ... one failed! It complained that I was using the wrong assertEquals to compare floating point numbers. I didn't actually want to compare floating point numbers - I had used Math.signum instead of Integer.signum. Easily fixed. Strange that Eclipse didn't catch that. Maybe a newer version of JUnit.

This was a good opportunity to use NetBeans' out-of-the-box Subversion. Or not. It told me my Subversion client was too old and refused to do anything. So much for out-of-the-box.

As with Eclipse, there appear to be different ways to connect to Subversion. One of them is with JavaHL - part of Subclipse. Another is through the command line client.

I updated my plugins but that didn't help.

I tested the command line client and it was indeed old. (Apple seems to like to stick to old versions.) One recommendation was to install a newer version from Collabnet. Which meant I had to sign up for a Collabnet account.

Then I had to give NetBeans the path to it. Now my Subversion appears to work. But again, like with Subclipse, it was definitely not as easy as it should be. Presumably every Mac + NetBeans + Subversion user (that hasn't manually upgraded their SVN client) is going to have the same problem.

Another minor quibble is that I didn't like the font in NetBeans (Monospaced) as much as the one in Eclipse (Monaco) but that's easily adjusted in the Preferences. Probably just a matter of what I'm used to.

So I start programming in NetBeans. I add a class, oops, meant to add a Junit test. Try to delete the class (that I just created) and it won't let me. The error message is ultra helpful "cannot delete file". But I can delete it fine from the Finder, and then it disapppears from NetBeans. Very strange but I'm not going to worry about it. (until the next time!)

One feature that I'm missing already is that NetBeans doesn't seem to offer to create missing methods like Eclipse does. This is great for "programming by intention" where you just write your code, calling functions that you haven't written yet, and then go back and create them. (NetBeans will automatically create unimplemented methods from interfaces.)

I do like how Find is a bar at the bottom of the editor, like Firefox, and what I recently added to Suneido. But Replace is still a dialog :-( as it is currently in Suneido (but I am planning to change Suneido's Replace to a bar as well)

Wow! I just realized that the HOME and END keys are working "properly" (i.e. beginning and end of line like Windows) in NetBeans! To get these working in Eclipse I had to customize the keyboard mapping. On the Mac HOME and END normally scroll to the top and bottom, but for programming or even just writing, I more often want to go to the beginning or end of the line.

Despite the messing around I managed to get a fair bit of the parser ported. I'm glad I'm separating the parsing from the code generation so I can work on (and test) one thing at a time. It's also turned out to be quite easy to split the parser into several parts (constants, expressions, statements). This should let me re-use the expression parser in queries. (Suneido's query expression have always been a subset of the language expressions because I never got around to doing everything in two places.)

I looked for a metrics plugin for NetBeans so I could see how many lines of code I'd written today (roughly 300 plus tests) but the only one I found needed to be built from source and I couldn't be bothered right now. There do seem to be more plugins for Eclipse than for NetBeans.

Eclipse + Subversion

One of the problems with third party add-on/plug-in architectures, like Eclipse or Firefox is that installing the software isn't enough, you also have to reinstall all your add-on's.

You would think that since this is such a common issue that there would be tools to ease this process but I haven't encountered any. You should at least be able to export a list of add-on's from one installation and import them into another. You can sync your bookmarks and passwords in Firefox (with add-ons) but you can't sync your add-on's.

After reinstalling Eclipse (eclipse-java-ganymede-SR1-macosx-carbon.tar), one of the first things I needed was access to Subversion. Eclipse comes with support for CVS but not Subversion, even though most people moved from CVS to SVN long ago, and are now moving from SVN to Git.

I've been using Subclipse but I thought I'd check if that was still the best option. I found there was also Subversive. It's came from Polarion but it's now a part of the Eclipse project so at first I thought that would be better. But a little research gave mixed results. There's obviously some squabbling between the two projects. Apparently Subclipse didn't join the Eclipse project due to license issuings. Subversive got around the licensing issues by not providing all the components, requiring you to separately install some parts.

The overall feeling I got from my quick research was that both plug-ins provide much the same functionality, but people seemed to have fewer problems with Subclipse. There are enough problems with both that some people recommend just using TortoiseSVN outside Eclipse. But TortoiseSVN is only available on Windows (where I do use it).

So I tried to install Subclipse. And got errors about dependencies. Sometimes I just have to shake my head at the state of our technology. This is a fresh install of Eclipse and a fresh install of Subclipse. You can't get much simpler than that. Wouldn't that be the first, most obvious test case? To be fair, maybe it's something to do with being on Mac OS X or something specific to my setup. You never know. But more research (what did we do before the internet and search engines?) showed that I wasn't the only one with this problem.

One suggested fix was to uncheck some of the optional components - that got rid of the errors.

When I had added Subclipse, it had automatically added SVNkit (from Eclipse itself). One of the optional components in Subclipse is the SVNkit adaptor. When you uncheck this, it unchecks the whole SVNkit plug-in. It appears that it's the SVNkit that "causes" the errors, not the optional Subclipse components.

The "best" part, is that when you proceed to the install, it appears that it is installing SVNkit after all - despite it being unchecked. I'm not sure what's going on, but it seems to work so I'm not going to waste any more time on it.

Here's a screen shot to illustrate:


Maybe I should be trying NetBeans. It doesn't have Antlr support, but now that I'm not using Antlr, that's not an issue. And it does have official support for Subversion!

Computer Frustrations

Sometimes computers really piss me off.

I thought I was finally figuring out Antlr. Then my grammar worked in AntlrWorks, but not in Eclipse. AntlrWorks is using Antlr 3.1 but Eclipse was using Antlr 3.0. In the Eclipse preferences I see I can choose 3.1 but when I do, Antlr quits working. Ok, I guess I need to upgrade. But I expected this would be a problem because I haven't been able to update in Eclipse for quite a while. I try to update anyway, but it just tells me I can't, for some cryptic reason that doesn't help me at all.

This roadblock makes me think about whether I should be using Antlr. I've already spent quite a few days struggling with it and progress is very slow. I'm pretty sure I could have ported the C++ code to Java by now. One of the big reasons to use a tool like Antlr is to work at a higher level that's easier to modify. But the more I add to my grammar, the more brittle it seems to get. Small changes tend to break the whole thing with a cascade of vague messages.

In a way, it's understandable. I'm trying to port a grammar from a hand written recursive descent parser. In a hand written parser you can do all kinds of things that aren't possible in a more structured system like Antlr. And things like optional semicolons are not the easiest to handle with tools like Antlr.

The ironic part is that Antlr works great to do simple stuff (like Suneido's query language) but for more complex stuff it becomes increasingly difficult, at least if you're not an expert with it. Of course, that makes it almost useless - complex stuff is where you need it. If you were developing a little language from scratch it would be fine because you could just tailor the language to what Antlr handled easily.

I hate to give up, especially on an interesting challenge like this, but I have to remind myself that the goal is to port Suneido, not to spend endless hours struggling to learn and use some tool. And even if I got it to work, I'm then stuck with a dependency on Antlr. Which is already causing me problems and will just make it harder for anyone else who might want to build or modify jSuneido. And heaven forbid if they want to change the grammar - if they touch it, they're more than likely to break it, with no idea how to fix it.

To make a long story short, I'm giving up on Antlr and I'm going to have to start over with a fresh install of Eclipse in order to be able to update.

But that's just the beginning of my current computer frustrations. My irritation level is already quite high because of way too much obligatory family stuff this weekend. But before I started back on jSuneido I figured I'd better fulfil one last duty and download the photos Shelley took during the family stuff. Easy, just fire up Lightroom, import the photos, and copy them over to the file server so Shelley can look at them.

Wrong. Lightroom hangs up part way through the import. And not only hangs up Lightroom, but the whole of OS X. I end up having to force the power off and reboot. I thought it was because I was messing around while I was waiting for the import to finish. So I try again, this time not touching anything while it's working. It gets a little farther, but again it locks up the whole computer. WTF! I force the power off again and reboot. But this time it corrupted the Lightroom catalog and it can't repair it. Grrrrrr.

I have backups, but they don't include my last session in Lightroom because Lightroom backs up at the beginning of a session. That seems totally backwards to me. First, I want to backup what I do in a session. I may go weeks before I use it again, during which time my last session hasn't been backed up. Second, checking the catalog and backing up takes quite a while. Having to wait for that when I go to do something with Lightroom is really annoying, which means half the time I skip it, meaning my backups are liable to be even more out of date. I'd much rather it did the backup when I quit, since it wouldn't be holding me up and I wouldn't be so tempted to skip it.

And there's yet another frustration in this. My first instinct was to recover the file with Time Machine, since it's saved me a few times. I don't use it very often so I thought I was doing something wrong when I couldn't get it to work. Then I realized the Lightroom folder is inside the Pictures folder, and I don't back up the Pictures folder since it's so big. And I keep a mirror of it on the file server anyway so Shelley can access it from her Windows machine.

There also used to be problems with Time Machine having trouble backing up the Lightroom catalog when it was open, but I think/hope that's fixed. (???)

I start a Time Machine backup to get the Lightroom folder backed up. It takes forever to "prepare the backup" and then it says it's backing 16 gb. WTF again. There's no friggin way I have added / modified 16 gb of stuff since the last Time Machine backup. Then I realize that the Lightroom folder also contains the preview cache, which I see has grown to be 13 gb! Ok, stop the backup (which also takes forever, for some reason), exclude the previews, restart the backup, wait for it to "prepare",

So I move my Lightroom folder out of the Pictures folder so it will get backed up. I start up Lightroom, point it at the new catalog location, and ... it crashes. Now I'm getting really pissed off. I mess around with various ways of starting Lightroom, with various catalogs and eventually I get it running.

Meanwhile, half my morning is gone and I haven't accomplished a damn thing other than to raise my blood pressure. Sometimes you have to wonder about these "time saving" machines.

I still need to import the photos but I'm a little gun shy - I don't really want to crash my whole computer again. I was trying to import directly from the memory cards (the way I always do). Maybe something in the low level memory card reader drivers was the problem, so I copy the files on to the hard drive and try importing from there. Success!

Then I notice that a bunch of the file names have "-1" on the end. Argh! That's because I already imported a bunch of them. They weren't in the Lightroom catalog because I restored to an old version, but the actual files were still there. So now I have a bunch of duplicate files. (Lightroom normally prevents this, but only if they're in the catalog.)

Lightroom has a function to synchronize the catalog with a folder, so I use that. And ... it hangs. This is not my day. Lightroom normally runs very smoothly. Of course, I'm off the "happy path", and I'm thrashing around, which is always dangerous.

Maybe the Time Machine backup I've got running is interfering with Lightroom. It still hasn't finshed "preparing" but at least it stops fairly promptly when I tell it to.

I go to force quit Lightroom and a dialog shows up. ARGH! again. It wasn't hung up, it was just asking what I wanted to do with the file differences. Being reminded of my own stupidity doesn't help my mood. Besides, I need to synch after I clean up the duplicate files, not before.

I use a shell to rm *-1*. No easy way to do that from the Finder or from Lightroom. If you didn't know how to use the shell you'd be stuck with dragging files to the trash can one by one. GUI's aren't always so great.

I synch again, this time waiting for the dialog to pop up. Finally, I have the photos imported.

I start up ChronoSync and update the mirror of my photos on the file server. (I don't use its scheduler to do this automatically because it always seemed to want to run at the worst possible times and most of the runs did nothing because I hadn't imported anything new.)

Time for coffee. Then maybe I can actually do something productive. If you can call it "productive" to abandon multiple days of work with a sophisticated tool and go back to implementing by hand.

New Add-On System for Suneido

I just added an article on the Suneido web site about a new add-on system.

I'm currently reading Clean Code (recommended) so I was pleased with the small methods in the add-on code. However, I was half way through writing the code before I realized I wasn't writing tests, let alone tests first. Oops.

When the methods get so small I start to resent all the lines with just curly braces and start to wonder if a Python indentation based style might not be better suited.

jSuneido Antlr Parsing

More Antlr grammar fun.

I'm still struggling with optional semicolons. I thought I had it figured out but I had overlooked some cases. You can "view" semicolons three ways:

separators, as in "x ; y ; z"

terminators, as in "x; y; z;"

empty statements, as in "while (x) ;"

I had them working as separators, but that didn't handle "x;".

That was easy enough to fix, but then it didn't handle "while (x) ;" And it treated "x;" as two statements "x" followed by an empty statement, which isn't what I want. (Although it might not matter for code generation.)

Taking the terminator approach, I want statements to end with either a newline or a semicolon, unless they are followed by a "}" or an else, or several other cases. Yuck.

Also, reading the Antlr book more, it seems that just turning on backtracking globally may not be the best approach since you no longer get any warnings and it can potentially make the parser very slow. The alternative is to rewrite the grammar to avoid the ambiguities, turn on backtracking selectively on certain rules, or add your own syntactic predicates (instead of letting backtracking add them automatically).

To further confuse things, the book recommends ignoring some warnings (such as the classic if-then-else ambiguity) rather than fixing them with syntactic predicates since the default resolution is the correct one and the fix is less efficient. But that goes against the normal recommendation to eliminate all warnings, otherwise you may miss valid warnings mixed in with the ones you're supposed to be ignoring. The other problem is that I'm not sure I know how to figure out whether the Antlr default is what I want.

I removed the backtrack option and got rid of all but one ambiguity by tweaking the grammar. It was complaining that conditional expressions were ambiguous. At first I thought it was the if-then-else problem, but because the ":" part isn't optional like "else", that's not the problem. I found if I removed my assignment rule it solved the problem. Aha, the ambiguity is probably between "(x = y) ? ..." and "x = (y ? ...". You wouldn't have this problem if assignments were statements rather than expressions.

But it still seems a little odd, because that seems like a precedence issue, which in top-down grammars is handled by the order of nesting of rules. Wait a minute, assignment has the lowest precedence, so it should be first. But I had it last because that's how cSuneido had it. Now my grammar compiles cleanly with no warnings.

[I hadn't used the AntlrWorks IDE for a while, but I started using it again to experiment.]

It appears I have an approach that will handle the optional semicolon issue. [source] Before I complete the grammar, there are a few other questions I'd like to answer.

cSuneido emits byte code directly during the parse; it doesn't build a tree first. I think I should be able to do the same thing with the Antlr parser. The advantage of this approach is performance. The disadvantage is that you don't have a tree to use for other purposes. It's also hard to test since the only output is byte code which isn't human readable. You have to translate it to a form of assembly language to get something readable.

I'd like to decouple the parser from the code generator in a way that would allow me to attach a tree builder instead of the code generator. That will keep the performance advantages of direct code generation but still let me get a tree. For testing I could write something that will just produce strings.

This sounds simple, but it's somewhat complicated because generating code requires actions at intermediate points within the rules. e.g. "if" requires outputting a conditional branch between the expression and the statement. On the other hand, building a tree requires returning partial tree results from rules.

Antlr has a built in system for building abstract syntax trees. It would be great if I could use this since it would simplify the code a lot. But when I'm generating byte code I don't want to actually generate a tree. I wonder if I could write my own Tree class that would generate byte code but not actually build a tree. I'd then have to augment this with the extra intermediate actions. Unfortunately, the Tree interface is somewhat complicated. The BaseTree that is described as having no "payload" still keeps a list of its children, which I want to avoid when generating byte code.

Despite the extra work, I think it may be simpler to roll my own rather than try to make the tree stuff work in ways it wasn't intended to.

I modified Language.g to call a Builder interface and then implemented a StringBuilder used for ParseTest. So far so good. I still have to add the intermediate actions but then shouldn't be too hard. Then I can start to implement a Builder that does code generation.

ARGH! Rereading what I had written, I realize I didn't solve the empty statement issue. For example, it can't parse "if (x) ;" I guess that's what I'll have to work on next!

jSuneido, Java, and Antlr

Back to working on jSuneido. I'm writing the Antlr lexer/parser for the Suneido language. In the process I'm discovering a few issues.

The return value from my language parser was wrapped in another class (constant_return). But that's not the case in my query parser - it returns the result value directly. Obviously the grammars are different but I can't see what would cause this difference. I dug around trying to find an answer but I gave up. If I wanted to spend the time on it I could start cutting down the grammars until I found what was doing it by a process of elimination. But it's easier to just extract the value out of the class. [Later: the problem went away when I added more rules.]

I wasn't handling explicit signs on numeric constants properly. I had an optional minus sign on the lexical rule for numbers, but that only worked if there was appropriate whitespace. "a - 5" was ok, but "a-5" got interpreted as "a -5" (no operator) and gave an error.

The fix led to ambiguities between whether "-5" was a numeric constant or an expression with a unary minus operator. I wanted it to be a numeric constant so I had to change my expression rules a bit.

I notice I don't seem to allow a plus sign on numeric constants in cSuneido. It's redundant, but still seems to be an oversight.

I wasn't handling errors in the lexers. I'd put in the recommended code to abort parsing on the first error, but I didn't realize I had to do something similar for the lexer. Eventually I found How can I make the lexer exit upon first lexical error? which seems overly twisted, but does the trick. I needed this in the query grammar as well.

SuDecimal.toString wasn't behaving like cSuneido. e.g. 1000 would come out as 1e3. BigDecimal.toPlainString works better in this case, giving "1000", but it doesn't switch to exponential notation for big exponents like cSuneido does. cSuneido switches to exponential notation for exponents bigger than 19. It's probably not critical to match this exactly but it should still switch to exponential notation for big exponents.

The parsers were accepting "extra" stuff on the end. You have to explicitly match EOF. You would think that would be the default. Or at least mentioned prominently. Yet EOF isn't even in the Antlr book index, and it's not in the examples.

One of the big issues with converting Suneido's language parser to Antlr is optional semicolons. I figure I'd better tackle this early in case it's a show stopper. Or if not a show stopper, something that will require a specific approach to writing the grammar.

Thankfully JavaScript (ECMAScript) also has optional semicolons so I could look at examples for it.

You can use Antlr's automatic backtracking, as in one example. But this example works by treating newlines as significant and optionally matching them everywhere applicable - a lot of places!

Backtracking is not used in another example. Instead it uses some tricky code to "promote" applicable newlines to be significant.

The first approach seems simpler, albeit more verbose.

One ambiguity is the return statement. "return 123" can be either "return; 123" or "return 123;". Strangely, Antlr doesn't complain about this issue. It takes "return \n 123" as a single statement, whereas cSuneido would take it as "return ; 123".

Of course, Suneido's handling of optional semicolons is not exactly the same as JavaScript. That would be too easy :-) I'm not even sure cSuneido is totally "correct". For example, cSuneido takes "5 \n -4" as "(5 - 4)" because it looks ahead to see if following lines start with a binary operator. But to me it seems like it "looks" more like "5; -4"

In certain contexts, newlines are not significant. For example, if you're inside a parenthesized expression. And "f() g()" should be legal i.e. two statements. But "(f() g()) should be illegal. This seems to be handled by Antlr with backtracking.

I've always felt a little guilty that I wrote some of the tests for cSuneido in stdlib rather than in C++ code. But it was a lot easier to write certain tests that way. Now that I'm writing jSuneido I find there is an advantage to that approach. To keep the C++ tests I have to rewrite them in Java. But the ones that are in stdlib work as is. It's making me think that it would be nice to have a "complete" set of tests for the executable in stdlib, much like Rubinius initiated an Rspec test suite that "defines" Ruby.

Of course, the reason I'm thinking of this now is that I don't have a clear definition of how optional semicolons are supposed to work in Suneido, other than the cSuneido implementation. A set of tests would be nice! The downside of tests in stdlib is that Suneido has to be fairly complete to run them. And my language implementation is barely started right now.

I had to temporarily kluge some string results from my rules in order to test the parsing, but with not too much messing around it seems to be working. There are some subtle parts: "return expr?" is different than "return | return expr". The first seems to be what I want in order to interpret "return expr" as one statement instead of two.

So far so good. It looks like it may not be too hard to get Antlr to do what I want.

Drag and Drop Files into Gmail with Firefox

A post by Tim Bray led me to a post by Mrgan whose main complaint is that you can't drag and drop files onto Gmail attachments.

I agree this is a shortcoming. But if you use Firefox you can fix it with the dragdropupload add-on.

And the advantage is that this add-on works with any web site/app, not just Gmail. Whereas, if one desktop app implemented drag and drop, that wouldn't help any other desktop app.

Mrgan's other main comment is that off-line already works with desktop mail apps. That's true, but I still think Gmail's new offline mode is better - you can use it on multiple machines, and it has a flaky connection mode. And unlike POP (IMAP is better), it keeps your email on the server so you don't have to worry about backing it up.

Even Tim Bray seems to think that email is better as a desktop app. Maybe that's because he uses a single machine (a laptop) for work, home, and travelling. For me, using multiple computers (and operating systems), I think Gmail is a lot better. I think I'd prefer it even if I used a single computer, but the advantage might not be as clear.

And, unlike Tim, I do think that Gmail's "conversations" are a big improvement. They take a little getting used to, so anyone who doesn't use Gmail won't necessarily see the advantage. But I find I really miss Gmail's conversations when I use other email apps.

Another thing I think Gmail should be applauded for is that it doesn't add any "junk" to my messages. I think it's pretty ugly when I get professional business communications with Microsoft or Yahoo ads (spam!) on the end of their emails.

Forking Ruby

Dave Thomas gives an interesting keynote at RubyConf on why it might make sense to fork Ruby.

It's interesting how the new Ruby syntax for hashes is much closer to Suneido's, as is Dave's proposed syntax for blocks/closures.

More Antlr Fun

When I started on the Antlr grammar for the Suneido language I realized I hadn't handled escape sequences in string literals in queries.

I thought this would be easy, but I thrashed around for quite a while on it.

There are lots of examples like:

STRING_LITERAL
   :    '"' (EscapeSequence | ~('"'))* '"'
   ;
fragment EscapeSequence
   :     '\\' ('b'|'t'|'n'|'f'|'r'|'v'|'\"'|'\''|'\\')
   |    '\\' 'x' HexDigit+
   |   OctalEscape
   ;
fragment OctalEscape  
   :    '\\' ('0'..'3') ('0'..'7') ('0'..'7')
   |    '\\' ('0'..'7') ('0'..'7')
   |    '\\' ('0'..'7')
   ;

Looks straightforward. But ... there aren't many examples that show how to convert those escape sequences to the proper characters. There are a few like:

EscapeSequence
   :'\\'!
   ( 'n' {$setText("\n");}
   | 'r' {$setText("\r");}
   | 't' {$setText("\t");}

Maybe that worked in Antlr 2, but it doesn't work in Antlr 3. The nearest thing to an explanation I could find was a cryptic response to a mailing list question. It seems to imply there is a way to do it, but if so, I couldn't figure it out. (I hope my responses to Suneido questions aren't as cryptic!)

I found a few references to this being an area where Antlr is weak. The book has very little material on lexical analysis.

I tried various combinations and permutations but I couldn't find any way to make it work. In the end I just handled it outside Antlr by writing a function that would convert the escape sequences in a string. So my grammar just has:

STRING
   : '"' ( ESCAPE | ~('"'|'\\') )* '"'
   | '\'' ( ESCAPE | ~('\''|'\\') )* '\''
   ;
fragment
ESCAPE : '\\' . ;

I guess I should have taken this approach from the start, but the examples seem to show handling more in the lexer. And like my last Antlr issue, it seems a little ugly to be able to recognize things in the grammar, but then have to reprocess them again yourself later.

jSuneido Milestone

I just fixed the last two failing stdlib tests. Now all the tests pass except, of course, for the ones that requires the language (rules and triggers).

One of the bugs was a couple of lines of code I'd somehow omitted during porting.

The other was using 0x2f as a bit mask instead of 0x3f. Oops. The "funny" part was that this was in the code for handling minutes and seconds in date/times so it would cause intermittent failures depending on the exact time when you ran the test. It got down to the point where I was getting 7 and I should have been getting 23. The difference is 16, one bit. Aha! The C++ code was correct so I could have found it by comparison, but for some reason my eyes didn't pick up on the one character difference.

I guess this is a pretty big milestone for this project. For some reason it doesn't feel like it. Too gradual, too much more to do.

I hadn't done any speed benchmarks up till now. For a quick comparison, it took 11 seconds to run the stdlib tests with jSuneido and 5 seconds with cSuneido. That's not a scientific or fair test, but I'm happy enough with the result. Considering I haven't done any optimization, or even worried about speed at all, it doesn't seem too bad. And this is just running jSuneido from within Eclipse. Presumably the server Java VM would be better since it does more optimization. And it's also crossing from Windows to OS X through Parallels which may add some overhead.

I've always been ready to accept a speed penalty for the Java version, as long as it was more than made up for by multi-threading on multiple cpus/cores. e.g. If it's 25% slower, but you can use 4 cores, you still end up 3.5 times faster overall. Of course, you don't achieve an N times speedup from N cpus because of locking etc.

It would have been nice if there was an in-house app that I could switch to jSuneido. But our main apps require rules and triggers. Maybe our version control server - I don't think it uses any rules or triggers. That's a little scary, though. It's a pretty critical component. Especially since we generate the automatic nightly updates for our clients directly from version control. Might be wise to do a bit more testing first :-) I'm sure my staff would agree!

jSuneido Hung up on Antlr

Views were one of the last things to implement in the straight database server part of jSuneido.

This meant extending the Antlr grammars for requests (to define views) and queries (to expand views). I thought defining views would be easy and expanding them would be tricky. It turned out to be the opposite.

The trick with defining views is that I didn't want to parse the view definition, especially since the view definition follows the query grammar, not the request grammar. I just wanted to slurp up the remainder of the input as the definition. This sounds simple, but I thrashed for 3 or 4 hours on it.

I had something like:

request : VIEW id '=' VIEWDEF ;

VIEWDEF : .* ;

But you can't do that. What makes it trickier is that although this looks like a single grammar it actually produces separate lexer and parser classes. (lower case rules are for parsing, upper case for lexing.) The lexer operates independently so you can't define VIEWDEF as .* since that'll match anything/everything.

I tried predicates based on some example I found for implementing C macros:

request : VIEW id '=' {viewdef = true; } VIEWDEF ;

VIEWDEF : {viewdef}? .* ;

But this doesn't work either, probably for a variety of reasons, but one main one is that the parser and lexer are separate so the parser can't control the lexer (at least not easily).

So I decided to do the work all in the lexer:

request : VIEWDEF ;

VIEWDEF : VIEW ID '=' .* ;

But then I got "alternatives are unreachable". Eventually I found an explanation that .* is not greedy. That works well for something like '/*' .* '*/' but not so well for what I wanted. The suggested solution was to use ('\u0000'..'\uFFFE')* instead. Here's the end result:

request : VIEWDEF
   {
   String s = $VIEWDEF.text;
   int i = s.indexOf('=');
   iRequest.view(s.substring(0, i), s.substring(i + 1).trim());
   }

VIEWDEF : VIEW WHITE+ NAME WHITE* '=' ANY EOF
   { setText($NAME.text + "=" + $ANY.text); };

fragment
ANY : ('\u0000'..'\uFFFE')+ ;

This seems a little ugly, but appears to work. It's a little roundabout to lexically split the view definition, then concatenate it back together, only to split it apart in the parser.

There could be a better way to do this but I couldn't find it. This will do for now.

I did find a bug in the standard library code while I was working on the views. The QueryCount function was trying to optimize the case where the query was just a table name. But something that looks like just a table name could actually be a view, in which case the optimization wouldn't work. I removed the optimization. It should really have been in the database anyway.

I thought this would fix the last of the test failures, but when I ran them all I found there were still a couple more failing. Hopefully one more day will clean them up.

As powerful as Antlr is, it's not the easiest system to work with. One of the next things I want to work on is compiling the Suneido language. I have a feeling I'll be putting in many more hours getting Antlr to do what I want. I could always go back to porting the hand written C++ recursive descent parser, but I think Antlr is better if it's not too painful to get working.

Trace Based JIT Compiling

Mozilla recently announced their new TraceMonkey Javascript implementation using trace based JIT compiling.

It's pretty cool stuff. For more information you can download Andreas Gal's thesis, or read HotpathVM: An Effective JIT Compiler for Resource-constrained Devices or Incremental Dynamic Code Generation with Trace Trees

I almost wish I was still working on Suneido's virtual machine :-)

TDM MinGW GCC 4

For some reason the MinGW project has been very slow to release a GCC 4 version. At first they said they were waiting for 4.1 but that arrived and still nothing. They eventually did release an experimental build but there hasn't been much action on this.

Checking the status recently, I searched for MinGW 4 and discovered the TDM versions of MinGW, including 4.3, and they seem to be active with it.

In a way this is a "fork" of the MinGW project - one of the benefits of open source. But it's not a fork in terms of going in a different direction, only in terms of releasing sooner. I really wonder why the main MinGW project does not want to release version 4, maybe they have a good reason, but if so they don't seem to be communicating it very well. Obviously they could still maintain version 3 if they feel that is a better choice for some things.

I built Suneido with the latest TDM version. GCC 4 has a lot of improvements to optimization, but sadly it's still slower than Visual C++ (about 10% slower than VC9, which in turn is about 10% slower than VC7)