Trying to resist Scala...must...not...succumb...

I've frequently been engaged in discussions regarding future Java language extensions (closures, etc) on forums like Javalobby and blogs like Neal Gafter's, and my co-workers aren't as big fans of Java as I am (being more inclined to Python and C), but moving away from Java is hard because of the incredible amount of useful libraries available, mature VM, and our favorite IDE - IntelliJ IDEA.

I would like to have a language, right now, that included a better static type system, first class functions, type inferencing, etc, but also allowed me to use all of my existing Java code, and run on top of a mature VM. Having Java-like performance would be a big plus.

And Scala seems to be it. I had looked at Scala a long time ago, but I hadn't realized how much progress they had made. Recently, I took another look at it, and boy oh boy, is it tempting. There seems to be almost no downside to writing future code in Scala, as it will run in the same VM as my other code, and seamlessly interoperate with Java classes, yet offers similar performance. And don't even get me started on Scala's DSL creation capability, which exceeds even Ruby (though still not Scheme)

However, two missing wishlist features gave me the excuse to leave it alone for now. For one, I told my coworkers that I am not switching to any new language which does not have a REPL. I had assumed that Scala was compiler-only. Secondly, no IntelliJ support is a big turnoff.

To my surprise, Scala *does have* a REPL interpreter. Whoops.

Only one excuse left. Please JetBrains, do not add first-class Scala support to IDEA. Do not tempt me to switch languages, I'm begging you! :)

-Ray

Knowledge extraction with 2 dimensional regular expressions?

Some of my best and worst ideas come when I'm sitting on the toilet. I pretty much have an informal bookshelf next to it, which I use to refresh and reinforce my memories of galois theory, probability, or in this case, automata from time to time. I'm not getting any younger (almost 36) -- it's been ages since college -- so whatever time I can use to reinforce those neurons and keep those skills from slipping away is golden.

So, there I was, automata book in hand, thinking about how I could simplify and modularize, Tardis, Timepedia's web crawler, automated knowledge discovery extractor, and temporal query engine. One part of what Tardis does is look for time related information in documents, and extract timeseries and timeline information.

How it does this exactly, I won't say at this time, but it uses a large battery of heuristics and other classical algorithms. The problem is, this logic is cemented inside of Java code, a sort of implicit 'expert system' with a huge number of cases, and complex interactions. Extending this to support newly discovered rules is hard enough with the source code in hand, but impossible for the end user.

Wouldn't a DSL be better? But if so, which one? An expert system like CLIPS/JESS? Those risk alot of complexity as well as scalability issues. If this was simple text extraction, I'd give the users the ability to author custom regexp match/rewrite rules for particular documents, sort of a mini-online-SED. As you can imagine, a lot of time related information is two dimensional in nature, stored in documents in tabular form, so ordinary regexp's don't capture the problem.

Aha! What about two dimensional regular expressions? Do they even exist? By the time I had gotten off the toilet, I had already devised replacements for regular expression concatenation operators in the form of row/column concatenation operators. I knew however that I was not the first to think of this, so a quick Google Scholar search led me to this paper: Two-Dimensional Languages (1997), Dora Giammarresi, Antonio Restivo, Handbook of Formal Languages

At first glance, this looks like a fertile field, previously applied for recognizing graphical features in pictures. Could I extend it to my needs? More on that later. First, let's look at an example.

As you may recall, a classical regular expression consists of operations like concatenation, union, and Kleene star. Concatenation is usually represented by placing two symbols next to one another, such as "ab" which means "a + b" where + is the concatenation operation. Union is typically represented via the pipe character "|", so "a|b" means "a union b". Kleene star of course is the union of all possible concatenations, e.g. "(a|b)*" = e, a, b, a+b, a+a, b+b, aa+b, ab+a, etc.

The two dimensional analogues of these would row concatenation, column concatenation, and row/column Kleene star operators. Let us denote column concatenation as "+", and row concatenation as "/", so "a + b" recognizes "ab" as long as they are in the same row, and "a/b" recognizes "ab" as long as they are in the same column. Column-wise Kleene star as "+*" and row wise Kleene star as "/*".

Now let's try a problem, recognize the set of all "chessboards", encoded with the symbols 'b' for black, and 'w' for white squares. Here's an example chessboard:


b w b w b w b w
w b w b w b w b
b w b w b w b w
w b w b w b w b
...


First, we match the first row with "(b + w)+*". Next, we match the second row with "(w + b)+*", and then we concatenate these two expressions row wise, to form

"(b + w)+* / (w + b)+*"

This says match "bwbwbw..." followed on the next row by "wbwbwb...". Now all we've got to do is repeat this pattern row rise.

"( (b + w)+* / (w + b)+) )/*"

This will match the above chessboard pattern. I realize it may be confusing to represent column wise concatenation via '+' instead of the empty string as is traditional, but I wanted to make the separate row and column operators explicit and equal in importance.

Now, I was delighted that something like this could be done, and furthermore that theoretical results for NFAs, DFAs, and closure properties existed for such languages, but I still faced the problem that knowledge extraction seems to require processing values semantically, not just lexically, so I tabled it as just a nifty and cool area of research, but with no application to what we were doing.

That was, until I showed it to Mat, who came up with an additional step that would enabled 2D regexps such as those described above to be used by Tardis for time related extraction. And that story, I will leave for a future article. :) The lesson I learned however, is not to give up on an idea that may seem impractical until you've got input from other people.

In the mean time, check out the paper I linked.

-Ray

When algorithms work better than you dream...

So, Timepedia is building a time machine, right? It sounds pretentious, but for us, it's really a geeky moniker of love for our project, after all, is Google's "search engine" really an "engine"? How much horsepower does it have? :)

One part of Timepedia, readers of this blog are already familar with: Chronoscope. With Chronoscope, we are attempting to build an open platform of visualization tools for time oriented data, in much the same way that Google Maps and Google Earth deal with spatial data.

However, what good is a time machine, if you don't know where to go, or don't understand what you're looking at? Timepedia has another platform, aimed at data mining time related information, called Everett (owned and implemented by another Timepedia founder, Mat). Everett is a collection of many algorithms for both data mining, and forecasting, some of them bleeding edge academic research. When we started, we weren't sure which of them would work, or how well they would work, we only knew that they had promising features, so Everett was less of a end user product, and more of a research platform.

One of the tools of Everett is an algorithm that lets us find hidden recurring patterns in data, even in the presence of noise, or scaling. Last week, we tested the algorithm on real life data for the first time, and had one of those "holy cow!" moments, which don't occur too often for me personally, where your own code surprises you.

To give you an example, I fed Everett an 18,000 data point series of federal funds rates over the last few decades, and it identified a pattern that occured 3 times in history. Visualizing this in another tool we call Timelord (A Chronoscope married to Everett and other server-side services), I was puzzled as to the significance of these three sequences. My co-founder Shawn spent about 1 hour Googling, until he found the correlation: These sequences corresponded to international financial/currency crises (such as the Mexican currency crises), in which the Fed was forced to take action. The leadup to the crises appeared identical each time. A fluke? It sure the hell was very interesting.

I was worried it was a fluke, so I tried something more mundane. A time series of unemployment benefit expenditures in Indiana, and once again, Everett identified a series of puzzling repetitive sequences. What were they? The dates looked very familar, 1980-81, 1990-91, 2000-1...were they recessions? To check, I used Timelord to overlay a National Bureau of Economic Research official measure of economic expansions and contractions, and sure enough, these patterns intersected with NBER recessions. One other interesting property stood out, the patterns returned prefixed the recessions, that is, Everett was showing us a pattern that leads to a recession.

How cool is that? Ambition got the best of me, I went for broke: I tried a historical time series of average hurricane strength (saffir-simpson scale), as well as a yearly count. There appears to be good evidence that a 40-60 cyclical hurricane season exists, and I was hoping that Everett could find these patterns, but alas, it did not.

Still, the initial results are promising, and we hope that Everett will give average users an ability to query time in ways that have not been previously available.

So, if you're wondering why I haven't released Chronoscope yet, it's because I've been working on integrating Timelord with Everett. :)

-Ray
p.s. Timelord is another GWT application, making it our 4th major GWT application. Everett is C++ coupled via JNI a Java/GWT RPC interface, since performance is absolutely critical in Everett.

Converting to Guice, easier than I ever imagined.

I've been working the past month on revising the data layer of Timepedia, which has, shall we say, somewhat interesting storage requirements. However, the RDBMS related portions had become an enormous eyesore, with tons of handcoded hibernate DAO methods. I have been admiring Guice from afar for awhile, but delayed the pain of refactoring the RDBMS code until I had no choice.

Surprisingly, there was no pain at all!

I took a chance, and used Wideplay's warp-persist framework for Guice, deleted all of my DAO implementation classes in favor of Dynamic Finders, and wrote one Guice module (5 lines of Hibernate config code mostly), compiled, deployed, and prayed. Amazingly, it worked the first time. I was done, total conversion time: 30 minutes.

Now, it helps that I wasn't using Spring nor J2EE (I dislike bulky over designed frameworks with hideous XML configurations), but I think this is a good result for Guice. It reduced the number of lines of code (especially the Dynamic Finders) dramatically as well as the amount of configuration.

-Ray

Timepedia, Chronoscope Quick Status Update

As I mentioned in my last entry, I haven't been able to work for the last few weeks due to a family emergency, but work has now been ramping back up, and we are shooting for a preview of the full site in 2-3 weeks time.

Chronoscope in the meantime is undergoing a heavy refactoring, both to use the GWT Exporter everywhere (instead of hand-rolled bridge functions), as well as performance fixes for the renderer (should be a lot smoother on release), and inclusion of the FontBook Renderer for rotated text. The initial release still won't have a Flash canvas renderer due to the need to work on the Timepedia site.

-Ray

Sorry for the lack of updates...

I (Ray) was supposed to have started a series on modifying the GWT compiler, but I had to fly out on an emergency recently because my mother has fallen gravely ill and is intensive care and I spend most of my time at the hospital now. Everything has been delayed, the blog series, the next version of Chronoscope, the launch of Timepedia, by weeks. Sorry for the delay.

-Ray

Top 16 missing features from iPhone

Don't get me wrong, I love my iPhone, but the following annoyances, bugs, and missing features really bother me. And for a $600 device, I expect Apple to address this in future firmwares.

1. No MMS. Inexcusable really for a modern phone. MMS isn't just about trading photos, because...

2. No ability to exchange vCard or iCal either over MMS, Email, or Bluetooth, because...

3. The iPhone doesn't appear to support vCard or iCalendar. Really, try inviting yourself to a meeting with Google Calendar and the ICS invites will show up as unusable attachments. Not the end of the world, except...

4. iPhone Mail won't properly show the HTML Invite of a Google Calendar invite! You get the subject line, and unusable attachments, and that's it. Embedding a multipart/alternative inside a multipart/mixed seems to be too much for it. So for now, you're stuck with first, checking email with Mail.app, accepting an ICS invite and getting it into your phone via iSync. Hope no one invites you to important meetings on the road.

5. Again, Bluetooth profiles supported seem pretty paultry. No dialup network tethering, no print service, no OBEX exchange, and so on.


6. VPN L2TP only supports shared secret identification and doesn't allow Machine Certificate.

7. Can't use iPhone to haul files around. You know, being able to use it as a USB drive and sync some files or use Bluetooth File Exchange would be nice, which just about every other phone supports.

8. No gestures for text selection. So, you can position the cursor, but if you need to delete a sentence or word, you have to just press the delete button a few dozen times. You can't cut/copy/paste text either. Double-tap word selection and triple-tap sentence would be nice, and would not interfere with the zooming in any application except Safari text fields.

9. no iChat, no jabber, no AIM, no bonjour, well, nothing but email and SMS. And since neither Flash nor J2ME is available, pretty much no hope of third party development of these -- except for web-based hacks which are likely to chew up battery life with HTTP traffic vs idling a TCP socket.

10. Mail application does not support full range of configuration that Mail.app does (e.g. choosing between IMAPS and STARTTLS, picking SMTP/IMAP ports, etc)

11. Landscape mode available in far too few apps. I like the landscape-mode keyboard, but it is not available in Mail, or SMS, or practically anywhere else except Safari.

12. No speed dial? Wouldn't it be nice if double-taping the home button from sleep wake would take you right into the Phone app so you could hit a speed dial number, or better yet, allow double-tap-home to be configured to go to the favorite app screen of your choice (e.g. recents?) Apple talks about how great it is that the buttons are so configurable being virtual instead of plastic, but why not let the enduser have more control over screen UI layout and macros?

13. No Flash...I know, it's coming most likely. Still, very irritating.

14. No Java (J2ME). The iPhone eats up 500M of RAM for the OS, and he says Java is a hog? With J2ME today, on many phones, you can send/receive SMS from Java code, you can open sockets, you can open bluetooth connections, you can access the file system, you can control the camera, record sound, play video, access PIM databases, make accelerated 3D rendering calls, access accelerated 2D sprite/tile logic, the list goes on. I am onboard with the AJAX programming model, great, but AJAX alone can't cover all application classes, unless they massively embellish the Safari JavaScript API to attain feature parity with the various J2ME JSRs.

15. If no Java, then come up with an Objective-C secure sandboxed alternative that allows more access to native iPhone widgets. AJAX developers can't achieve a seemless native-look-and-feel by using HTML rendering, because the iPhone native widgets are relying on Core Animation as well as access to native data. A Java or Obj-C layer could. A Javascript layer cool, if, and I mean, *IF* Apple put serious work into extending the Dashcode API to encompass a hell of alot more functionality than they do today. Without Flash and without Java, even something as simply as writing a game with sound effects becomes hard. I guess the only alternative is to load up a bunch of quicktime objects into the webpage. Sheesh.

16. Last, but not least, Mobile Safari and AJAX. Yeah, it's the 'full web', right? Not exactly.

a) Safari chews up mousedown, mousemove, mouseup, and other DOM events before the browser gets them to implement scrolling and zooming. So, for example, maps.google.com scrolling doesn't work on iPhone. Great, they have a native app that deals with scrolling and zooming already on the iPhone, but what about other web pages that need these events?

b) Any element or frame with overflow: scroll is treated as overflow: clip. That is, with the exception of top level window, you cannot have scrollable regions anywhere else within a page. Safari has no concept of 'focused' scrolling. You'd expect that if you tap an embedded FRAME/IFRAME/DIV and it had scrollbars, that you could scroll them by dragging your finger. Ooopps! They obviously need a mechanism to support scrolling when there are multiple scrollable regions. And the response cannot be 'well, only browse pages designed for iPhone in the first place!' because that's the WAP "mobile Web" argument, which Steve Jobs himself has ridiculed. I want the FULL web experience on my iPhone.

c) Safari should let the browser DOM event handlers get fit dibs at the event. If they call event.preventDefault(), it should CANCEL the default finger-drag-scrolls-whole-window. Would this allow some poorly designed web pages to disable zoom and scroll? Yep.

The iPhone is a magnificent phone. But I feel it is much like the PlayStation 3 - about the same price, underdeveloped firmware, and lacking third party support. A year later, the PS3 firmware has added DLNA, background downloads, enhanced RGB, BluRay, new AVC codecs, Folding@Home, and lots of other features.

Let's hope that the iPhone's lack of features is not a conscious decision to eschew those features, but merely the result of rushed deadlines to get a stable device out before they could finish every feature in their roadmap.


-Ray