Technology

Reminderer Grammar Parser is Done!


I finished the grammar parser for Reminderer app. Yay!

I uploaded and made it available on the web thanks to Google App Engine. You can see it in action here:

http://grammarparser.appspot.com/parser.jsp

(Unfortunately, you can’t embed it directly in WordPress, so you’ll have to click the link.)

You can say things like:

  • buy milk tomorrow 8pm
  • Pat’s birthday May 1 repeats yearly

Go ahead and take it for a test drive. Let me know if you find bugs!

Continue reading

Advertisements
Technology

Reminderer Redux


It’s been a while! I finally have some time to work on Reminderer (a TODO Android app).

Lessons Learned

I’ve spent the past couple of days commenting and refactoring the code, and boy do your programming skills improve in a year.

The current grammar parser has interfaces with only one implementation (unnecessary) and an inconsistent and obtuse design (maintenance nightmare). I built something quickly the first time around but now I’m paying the penalty because its taking me forever to re-understand it.

I keep remembering an article I read a few months ago by a well-respected programmer…the gist of it was that sometimes you need to put away “best practices” in order to “meet the deadline.” That’s true if you code and run, or if you don’t care about maintaining your code. Otherwise, you will have to spend some time on design, documentation, and refactoring with the goal of making the code intuitive. That way you or someone else in the future will have the shortest possible learning curve.

A New Vision for a UI

I’m a hug fan of Emac’s org-mode. For those of you who don’t know what Emacs is, it’s a 30+ year old editor (so yes, I’m a retro geek). Org-mode is a recent addition created by some Google employees that is like steroids to Emac’s outline mode.

What I love about org-mode is

  1. Dynamically create TODO items. It’s a blog post, now it’s a TODO item. Wait, now it’s a finished TODO item. Wait, now the TODO has a sub-TODO. Since it’s a text editor, it’s super-easy to create/edit/manipulate TODOs.
  2. Create an infinite hierarchy of tasks. Org-mode has no limit on the number of sub-tasks, sub-sub-tasks, sub-sub-sub-tasks, etc. (Sub-tasks rock because you can’t complete a TODO until all it’s sub-tasks are done, so its uber-useful for keeping track of projects.)
  3. View upcoming, done, in-progress TODOs at the press of a button. And it’s also dead simple to move them around too.

These are the reasons why I’ve used org-mode at work for the past couple of years.

But enough about Emacs. What does it have to do with Reminderer? Well, Reminderer does Item 1 thanks to the grammar parser and with support for a “share” intent (note to self: don’t forget this uber-important feature). Item 2 and 3 will need to be features.

As of the time of this writing, I spent the weekend refactoring the grammar parser. Up next comes the database and the alarm system. Then the UI.

Technology

Reminderer: Asynchronous Database Operations (Part 2)


I’ve been reading Predictably Irrational, a book on how we tend to make stupid (irrational) decisions. In particular, we have a habit of keeping as many doors open as possible, even if doing so is to our disadvantage. So what the heck does that have to do with asynchronous database operations? Keep reading.

In the previous post, we created a grammar for parsing tasks. Now we need a database to store the tasks. In Android, this is pretty straightforward—we decided to hide the database behind a ContentProvider. (That way if we decide to open up the database to other apps in the future, we’re more than half way there.) Creating a database and a content provider in Android is  well-documented. (You can also check out the classes in the com.frankandrobot.reminderer.database package at github.)

So far so good—straightforward and simple. Then it came time to integrate the database operations (CRUD) with the UI.

The problem is that the database operations can take a relatively long time and make the app appear sluggish. The worst case scenario is that we get the dreaded ANR dialog. We need to do the CRUD in a separate thread. Android gives you several options to do this. Among them are:

Options. So many options. And I wanted more!

When I got to this point, I was worried that the AsyncQueryHandler (being a handler) would get stopped or paused when the activity is stopped or paused. Instead of creating a simple test case to prove or disprove my theory, I proceeded to devour the stock Calendar app source code. Two weeks later, I found that it uses an IntentService in conjunction with a handler to do (some) of the CRUD.

The jury is still out on this handler-intent-service combination. But I can tell you this much—an AsyncQueryHandler does not get killed or paused when the activity gets killed or paused. (I had misunderstood the handler-activity relationship. Apparently, a handler’s life cycle isn’t as dependent on the activity’s life cycle as I thought.) So an extra two weeks later, the Reminderer app now has a working database backend. On the plus side, I am now wiser 🙂

The moral of the story is that we need to find a balance between accumulating knowledge and sticking to a schedule.

Check out the progress of the Reminderer app over at github.

Technology

Reminderer: a Grammar Parser


Some friends and I are coding a Remember-the-Milk inspired Android app called (for the moment) Reminderer. If you never used Remember the Milk, it’s a todo-list app. One of its appeals is that you can enter tasks using every-day language. For example, “Buy milk at 8pm” because a task that’s due at 8pm. We wanted our app to have the same functionality. That means that we should be able to enter tasks like “Buy milk on Monday” or “Mom’s birthday next Monday” and have the app auto-magically turn them into tasks. In order to do that, our app needed a context-free grammar and a grammar parser.

As its name implies, a context-free grammar encapsulates the idea of language, minus meaning or context. A grammar parser takes a string expression and tells you whether or not its part of the grammar, processing the expression as it goes along. Check out these two notebooks to learn more about grammars and grammar parsers: Context Free Grammars and Recursive Descent Parsers.

In order to write a grammar parser by hand (easily), the grammar needs to be non-left recursive. (Basically, in a non-left recursive grammar, the recursion, if any, occurs at the end of a grammar rule.) The reason the grammar should be non-left recursive is because it makes the job of coding the parser easier—each parser function is in an almost one-to-one correspondence with each grammar rule.

After some trial-and-error, this is the non-left recursive grammar we came up with for tasks:

expr: task | task commands
commands: command commands | NULL
command: time | date | next | repeats | repeatsEvery | location 
time: timeParser | "at" timeParser
date: "today" | "tomorrow" | dateParser | "on" dateParser
next: "next" dayParser
repeats: "repeats" occurrence 
occurrence: "hourly" | "daily" | "weekly" | "monthly" | "yearly"
repeatsEvery: "repeats" "every" S
S: timeDuration | dayParser | "hour" | "day" | "week" |  "month" | "year" 
location: "at" locationString

This snippet of code shows the correspondence between the parser functions and the grammar:

Task commands() {
  // save position
  int curPos = context.getPos();
  // command commands
  if (command() != null && commands() != null)
    return task;
  // undo cursor advance if no match found
   else context.setPos(curPos);
  //...
}
Task command() {
 int curPos = context.getPos();
 if (time() != null || date() != null || next() != null
     || repeats() != null || repeatsEvery() != null
     || location() != null)
     return task;
 else {
   context.setPos(curPos);
   return null;
 }
}

The expression if (command() != null && commands() != null) in commands() and the similar line in command() mimic the corresponding grammar rules:

commands: command commands | NULL
command: time | date | next | repeats | repeatsEvery | location

So that’s the grammar that we decided to use in Reminderer. In case you haven’t noticed, the grammar doesn’t express uniqueness. For example, “Buy eggs at 8pm at 10pm” is a perfectly valid sentence. (The parser handles this by using the last time stamp.)

If you’re wondering about “timeParser”, “dateParser”, and “dayParser”, these work in conjunction with Java’s DateFormat and SimpleDateFormat classes. That is, instead of encapsulating date and time formats in the grammar, we outsource that work to preexisting Java classes built for that purpose.

The Reminderer grammar parser is more or less done. Check it out at github: https://github.com/frankandrobot/Reminderer/. Make sure to check out the “newParserStrategy” branch. I’ll make sure to upload a debug build later this week. And yes, the app is open source—it’ll use an Apache-style license. We just haven’t had time to upload the license yet.