Project Gilgamesh

Symbian Exposium 2003

I'm leaving to catch the train to London now for the Exposium.

Hoping to learn more about Symbian and meet some interesting people: should be good. I'll write something about it in a couple of days!

Movable Type CSS

I'm trying to get rid of the absolute positioning of the links bar and the main content, by having them both just float into the right place.

It's not working though. It's now broken (the navigation bars underneath the content). Grrrr. Any hints?

Toolset

The project is "open source", or rather will be, when I release some source-code... So, to help would-be contributors, here is the description of the toolset that I have been using and considering so far.

Gilgamesh will be coded in Java, specifically in J2ME as a 'MIDlet suite'. I'm on a steep learning curve with Wireless Java myself, so if these terms are unfamiliar, don't worry: I've given some references in the table below, and I'll be blogging links to useful Java and Symbian documentation now and then.

Why Java? C++ is another viable alternative for the platform (Symbian 7.0 with UIQ, e.g. Sony Ericsson P800), and might be considered more reasonable for the application (A complex spreadsheet could get quite computationally intense).
My personal reasons were "I don't know C++", and "I like Java, and I want to learn more of it". If you really want to know, I'd have rather coded in Perl, but that's not supported on the P800...

Tool	Version	Description	Download	Additional info
Java 2 SDK	1.4.1	The Java compiler, tools, and API documentation. Vital of course	java.sun.com/ (You will want to download the documentation too)	Lots of info at java.sun.com" including various tutorials Recommended books: O'Reilly's Java in a Nutshell. (Not a tutorial: there are plenty of good ones about, but don't even think about the awful Chris Wright 'Teach Yourself Java') In fact O'Reilly has a good Java series And Sun have a good booklist, among which I've read and can recommend Effective Java (definitiely not a tutorial though.)
Java 2 Micro Edition Wireless Toolkit	1.0.3	Contains the subsets of Java language and API specified by J2ME (Micro Edition). Includes a compiler called ktoolbar which makes sure that your code sticks to that set. It also has emulators to show you what the application will (probably) look like running on a phone or PDA.	java.sun.com/products	Lots of info at wireless.java.sun.com I've bought Jonathan Allin's Wireless Java for Symbian Devices and the Java series Programming Wireless Devices with the Java 2 Platform, Micro Edition which had good reviews. Both seem useful but I'm not yet at the stage of having used them a great deal.
UIQ SDK	1	Development Kit for the Symbian 7.0 based UIQ User Interface. This is a massive download (which I haven't yet made as I'm on a dialup connection, and I'm hoping to blag a CD at the Exposium...	http://www.symbian.com/developer/ http://www.ericsson.com/mobilityworld/ (you need to register the Ericsson Mobility World developer programme: this is free.)	Lots of information from Symbian, Sony Ericsson mobility world, UIQ. It's worth joining the developer programmes so that you can read their white papers and download tools.
Ant	1.5.3	Ant is an automated build tool, similar to make. It's Java's de facto project build tool, and very easy to use. A single command can: Compile just the source files that have changed Run the regression-test suite (see junit below) to make sure that the project still works ;-> Update the javadoc documentation Create .jar distributions of the project Archive Send e-mail notifications about the build	ant.apache.org	The Ant documentation is quite good. Worth reading the article Ant in Anger (also bundled with the download). Apparently Erik Hatcher and Steve Loughran's Java Development with Ant is worth reading, but I've not bought it yet.
junit	3.8.1	junit is a unit-testing framework, which is now pretty much standard with Java. It makes it easy to write regression tests which is A Good Thing. Project Gilgamesh will require unit tests to exist for all classes.	www.junit.org	junit comes with some excellent documentation. The Ant book site has a freely available chapter on using Ant with junit. Oreilly's Java Extreme Programming Cookbook has a free chapter on junit available for download. 12 reasons to write unit tests is a nice introduction to the benefits of unit testing.
javadoc	n/a	javadoc is a standard tool with the Java SDK. All classes submitted to Project Gilgamesh must be well documented (for the appropriate definition of 'well'. More details in due course).	n/a	javadoc -help The Java SDK has pages of information about Javadoc under "Tool Docs" - "Javadoc Tool Page" and especially under "Javadoc Tool Reference Page (~your platform~)".
CVS	1.11.5 (client)	cvs (Concurrent Versioning System) is a source control system. This means that one or more developers can look at the same Java source and make changes to any part safely (because changes can be tracked, rolled back, etc.) Source Control, like automated testing, is A Good Thing. So far, Gilgamesh is not available on a CVS server. This should be rectified over the next few weeks (but I could do with some help setting it up.)	www.cvshome.org	cvshome has plenty of documents: I'm have to admit that I find the documentation very confusing by the documentation: the concepts are fine, but it takes a leap to understand what's going on. So hand-holding on CVS for me and other CVS newbiew would be really appreciated... This introduction seems about as straight-forward as I can find. The manual is complete but opaque for the beginner.
Java Editor / IDE	n/a	I'm using gvim with ctags to edit my Java source files. But this isn't obligatory. I'm interested in learning more about Eclipse (free) and Intellij IDEA (not free).	www.vim.org ctags.sourceforge.net

Formulas

I hinted in the entry on the Grid that each cell would contain a list of cells that it refers to in formulas.

    A   
 +------+
1| 1    |
 +------+
2|A1*2  | <-- references:  A1
 +------+
3|A1+A2 | <-- references:  A1,A2
 +------+

But of course this is an oversimplification. We don't just need a list of cells that we reference: we need to know how they interact with the formula. The formula will need to be parsed into a tree of data relating

• Functions
• Cell references
• Constant data (numbers, strings, dates)

Some examples

(Don't pay too much attention to the pseudo-syntax)

A1+A2
 - function(+)
   - ref(A1)
   - ref(A2)  
if(A1==23 then "Yes" else "No)
 - function(if)
   - function(equals)
     - ref(a1)
     - constant(23)
   - constant("Yes")
   - constant("No")

The last example shows a more complicated example, demonstrating that parsing the syntax could be quite intense. Of course, even a standard, commercial product like Excel simplifies the syntax by making it more functional:

if(equals(A1, 23), "Yes", "No") // Excel syntax

As you can see, this is much more easily translated into the parse-tree above.

S-expressions

The easiest (for the implementer) way of having formulas easily parseable would be to use the Lisp syntax of S-expressions. 99% of Lisp commands are written like this

(function arg1 arg2 arg3 ...)
Converting the formulae above:
  (+ A1 A2)
  (if (equals A1 A2) "Yes" "No") 

It looks a bit odd if you're not used to it, but it's trivial to build the parser. My first design idea is this:

• If you write a formula beginning with parenthesis "(", then it will be parsed as an S-expression.
• If you write a formula beginning with an equals "=", just like Excel and co, then it will be parsed more cleverly.

    =1 + 2               // arithmetic operators come inline
    =function(arg, arg)  // functions as standard
    =A1                  // reference unchanged
  

• The S-expression parsing will get implemented first: we can worry about the syntactic sugar later

Whichever way the formula is specified, it will end up being parsed as

1. Reference to a Function object
2. Zero or more argmuents

Of course, any of the arguments may also be Formula objects in turn, thus creating the parse tree.

(if (= A1, 23), "Yes", "No)
- Formula:
  - Function:  if
  - Formula------------.
  - Constant: "Yes"     \
  - Constant: "No"       \
                    - Function:  =
                    - Reference: A1
                    - Constant:  23

The Function class will have a simple interface something like:

public abstract class Function {
  public String display;
  public boolean CheckArgs(Value[] args) {
    // ... (filled in by subclass)
  } 
  public Value execute(Value[] args) {
    // ... (filled in by subclass)
  }
}

and is extended by subclasses like so:

public class EqualsFunction extends Function {
  public EqualsFunction() {
    display = "=";
  }
  public boolean CheckArgs(Value[] args) {
    if (args.size == 2) {
      return true;
    } else {
      return false;
    }
  }
  public Value execute(Value[] args) {
    if args[0].equals(args[1]) {
      return BooleanValue.TRUE;
    } else {
      return BooleanValue.FALSE;
    }
  }
}

Common framework for data

NB: I'm assuming that all the possible data-types (Booleans, Formulas, Arguments, Strings, Cell References) inherit from a parent class (here Value). That's because we need to be able to pass them around, store them, and use them consistently.

This might well be too heavyweight for being on a J2ME constrained device. But I think it will have its advantages: we'll see as we go on and try to optimize later if we need to. More on this topic later.

Designing the Grid

One of the most important data-structures to determine for a spreadsheet application has to be the Grid. It's what gives us the concepts of "Rows" and "Columns" of cells, and gives us a nice way of formatting related items like records of data into tables.

2-d array

The naïve way of implementing this (and I mean the way that I first thought of ;->) is to use a 2-dimensional array. That is to say, if the grid is 30 x 30 we'd have a grid something like:

   1 2 3 4 5 ..30
  +-+-+-+-+-+---
 1| | | | | |
  +-+-+-+-+-+---
 2| | | | | |
  +-+-+-+-+-+---
 3| | | | | |
  +-+-+-+-+-+---
 4| | | | | |
 :+-+-+-+-+-+---
 :| | | | | |
30  : : : : :

Array of arrays

Of course, in some languages, such as Java and Perl, this is implemented internally as an array of arrays. Though it's declared and used as if it was really a grid, in fact each individual array can contain a different number of elements.

+-+  +-+-+
|1|->| | |
+-+  +-+-+
|2|->| | 
+-+  +-+-+-+-+
|3|->| | | | |
+-+  +-+-+-+-+
|4|->| | |
+-+  +-+-+-+-+-+
|5|->| | | | | |
+-+  +-+-+-+-+-+
|6|->| | |
+-+  +-+-+
 :    : : 

Already, this seems to have some advantages, in that some rows may have more data than others. We don't have to store cells that don't exist (i.e. it's a sparse data-structure). Once we start thinking about rows of data, this leads to some other considerations:

• Add more rows to the end of the grid
• Delete a row
• Insert a row in the middle of the grid

All things which one does reasonably often with a spreadsheet program. If we have a row-based model rather than a grid based one, then it's easy to just add the row using the standard List-manipulation techniques of, for example, the Vector class.

Cell references

Most of the power of spreadsheets comes from the fact that cells can reference other cells:

   A   B   C
 +---+---+-----+
1|   |   |A2+B2|
 +---+---+-----+
2|  3|  5|     |
 +---+---+-----+

If we add a row

   A   B   C
 +---+---+-----+
1|   |   |A2+B2| <--
 +---+---+-----+
2|   |   |     |
 +---+---+-----+
3|  3|  5|     |
 +---+---+-----+

I'd expect the reference in cell C1 to now point to A3+B3. Hopefully there is a more elegant way for us to do this than to go through every cell in the grid updating the formulas.

References to cells, not to addresses

The formulas shouldn't contain references to a particular address, but to the Object of the cell. (I'm assuming basic familiarity with OO, especially Java here).

public class Cell {
  /** Cell has an Array of other Cell objects which it refers to */
  Cell[] references;
}

Just because we've added or moved a row here or there doesn't change the other Cell objects, so we don't have to update the addressing at all: of course this implies that the referenced cell has a way of finding out its own address eventually:

Cells know which row and column they're in

The best way for the cell to know its own address is to keep a reference to which row and column it's in. The row and column will know which number they are.

 +-+-+-+-+-+-+-+   B 
1| | |X| | | | |  +-+
 +-+-+-+-+-+-+-+  | |
    ^             +-+
   /              |X|
  /             ->+-+
+-+            /  | |
|X|------------   +-+
+-+

e.g. Cell object maintains references to its Row (Row 1) and its Column (Column B). Both the Row and the Column also contain references to the Cell object.

public class Cell {
  Line   row;
  Line   col;
  Cell[] references;
}

If the Cell object needs to know its address, it can query the Row and the Column. All that needs to happen when Rows or Columns are inserted or moved is for them to be renumbered. This implies that the Grid contains

• A list of rows
• A list of columns

The grid will manage the renumbering of the list whenever changes happen. All the individual Line needs to do is to maintain the position that it is in the list.

Deleting a line

Of course there is some additional complexity here:

   A   B   C
 +---+---+---+
1|   |   |=A2|
 +---+---+---+
2| 33| 12|   |<-- delete this line
 +---+---+---+

1. Delete Row 2
2. For each cell in the row, delete the cell from the relevant column
   • 33 (delete from column A)
   • 12 (delete from column B)

But though we don't need to notify dependent cells when a cell's address changes, we do need to notify when the cell itself changes (or as in this case, is deleted).

   A   B   C
 +---+---+---+
1|   |   |=##|<-- error!
 +---+---+---+

Generic deletion of a line

(e.g. row OR column)

1. Delete the line
2. (renumber the list of lines)
3. For each cell in the line
   1. delete the cell from the relevant perpendicular line.
   2. Notify any dependent cells that this cell has now been deleted.

Blogging Gilgamesh

Welcome to yet another blog about Symbian, and especially about a project which I've initiated, developing an open source Spreadsheet application for the platform, in particular for the pen-based UIQ desktop used by the Sony Ericsson P800.

Though Symbian is an OS for mobile phones and PDA's, that is, for small computing devices, I'm calling the project "Gilgamesh" (as in "the Epic of ...") Writing a spreadsheets might seem complicated at first glance: I've been thinking about it more or less constantly for the last 2 months and the project still seems immense...

I'm hoping that trying something on a scale I've never attempted before will be a great learning experience. Also that the blog and discussions around it will be an interesting working document about the challenges of designing and implementing a useable and powerful application for a computer with a screen the size of a train-ticket ;->