Graph Theory

I'm not sure what happened. I don't remember finding graph theory particularly interesting in university but over the past month I've had two occasions of simple pleasure while figuring out (pretty basic) directed graph algorithms.

The first was at our last Seaside sprint, where Lukas and I were working out how to modify his Package Dependency tool to mark cycles on Seaside 2.9's dependency graph in red, so we could immediately spot problems. It's not like there aren't already algorithms for this but it was fun just trying to work one out for ourselves.

The other was this Tuesday. I woke up wondering whether I couldn't make the graph a little easier to look at by removing direct edges when we have another indirect path to the same node. In other words, if package A depends on B and package B depends on C, we could omit a dependency from package A to package C because that dependency is already implied through transitivity anyway. I pictured this as the opposite of a Transitive Closure.

It turns out that this operation is called a Transitive Reduction and there are algorithms for it but they don't seem to be very well documented online. I ended up just working something out myself using depth-first searching and path-length tracking to prune shorter paths to objects. I don't know if there's a faster way but it doesn't really need to be that fast in this context anyway. I currently abort if the graph is cyclic but I'm pretty sure you could do something like pick an arbitrary root for the cycle, treat everything within the cycle as being distance zero from each other, and you would get a reasonable (albeit non-deterministic) answer. In our case, we don't want cycles in our graph so, realistically, you would fix the cycle and rerun the dependency checker anyway. Here's the result.

This got me thinking... is there a good implementation of graph theory algorithms in Smalltalk? I would love to be able to create a Graph of my model objects (maybe implement #edges on each one or something) and then call: "graph isCyclic", "graph transitiveReduction", or "graph topologicalSortFrom: aNode". So many things can map to directed graphs and, if you could work out domain-specific solutions by really easily layering generic graphing algorithms, that would be really cool.

Sometimes solving simple problems with definable right answers is so satisfying.

Gartner on Seaside

Well... praise for Seaside from a Gartner analyst:

If you are BIG fan of dynamics languages (closures, meta programming, and all that cool stuff) then consider giving Smalltalk a look. You might like what you see. Its like Ruby but with bigger muscles. You think Rails is cool? Check out seaside.

His general comments about Smalltalk are in line with Gartner's changing position but the specific reference to Seaside adds another touch of legitimacy when selling a Seaside project to those who hold the purse strings. Very nice.

Seaside History

There are a lot of questions around the origins and evolution of Seaside, particularly after Avi and I gave up our old domain and the old Seaside and Seaside 2 websites with it.

A couple of months ago, I began (but never finished) a history page for the Seaside website to provide some background information for those who are interested. I had to dust off some of those notes to prepare my ESUG presentation on the past and future evolution of the framework and figured I might as well dust off the history page as well. So here's the story as best as I can recall it (and by "recall", I mean "find in Google" because Google seems to hold the majority of my memories these days).

[Update: now posted at seaside.st/about/History]

Introduction

Seaside made its public debut (version 0.9) in an announcement to the squeak-dev list on February 21, 2002. Avi Bryant and I developed Seaside to support our web application development consulting, specifically the development of a web-based theatre boxoffice sales system.

Seaside took heavy inspiration from Avi's Iowa framework (now here), which was written in Ruby and was itself inspired by NeXT's (and then Apple's) WebObjects. This first release of Seaside provided action callbacks for links and forms, session state management with support for call/return and the back button, and a component system with templates.

Experimentation

Almost immediately after the release of 0.9, we began work on Seaside 2.x (codenamed Borges, a reference to Jorge Luis Borges' short story The Garden of Forking Paths and an allusion to Seaside's support for forking session states). Seaside 2.0 was essentially a complete rewrite with a layered architecture: a Kernel layer providing a continuation-based HTTP request/response response loop and state (back-)tracking; a Views layer providing action callbacks and a rendering API for generating HTML; and a Component layer providing call/return semantics, embedding, and development tools.

Seaside 2.0 was released in October, 2003 with the templating system conspicuously absent. This was an experiment to see whether the development of the HTML rendering API and the wider acceptance of CSS had reduced or eliminated the need for templates. The new layered architecture made it easy for others to experiment with developing their own template engines. Seaside was also ported by Eric Hodel to Ruby, where it kept the name Borges.

Several versions followed in quick succession with major refactorings to the session state tracking and backtracking mechanisms. Seaside 2.3 (mid-2003) also introduced an even more layered architecture that tried to make some of the internals clearer and more accessibly to the project's growing number of users and contributors. It also confirmed that Seaside would not have built-in templates in the near future. Seaside became increasingly well-known around this time with a presentation at ESUG 2002 by Lukas Renggli and Adrian Lienhard and a hands-on development workshop at Smalltalk Solutions in 2003 by myself and Avi.

Stabilization

Seaside 2.4 and 2.5 addressed some growing pains in some of the core parts of the system: the Renderer API, collapsing under the weight of combinatorial explosion, was replaced by the now-familiar Canvas API; and some of the internal workings of the Session object were reified to make its application main-loop metaphor more obvious. Version 2.5 also saw the introduction of Component Decorations, Halos, and response streaming.

As first I and then Avi began to work full time developing applications using Seaside, the community began to carry more of the development load, with the release of Seaside 2.7 being  entirely (and very successfully) managed by the community, with Lukas, Philippe Marschall, and Michel Bany leading the effort. This release focused heavily on cleaning up the code base by fixing, deprecating, refactoring, and removing code.

ESUG 2008 Presentation

I'm in Amsterdam and just finished my ESUG 2008 presentation on the evolution of Seaside this morning. The gist of the talk was that Seaside has evolved through Experimentation, Stabilization, and Optimization and is enjoying a bit of an Adoption phase which should be encouraged. Sort of a call to arms.

I also took the opportunity to try to communicate the architecture and key metaphor of Seaside through illustrations. Finally, I rounded it all out with a few examples of less obvious (read badly documented) places people might consider extending the framework.

I think it went pretty well overall. I had a few people come up afterwards saying either that it had helped them understand some part of Seaside, that the historical perspective was interesting, or that they agreed with the need for documentation and advocacy.

I imagine James Robertson will post video on his blog at some point as he was filming all the talks. In the meantime he's posted a quick summary (wrong title and name spelled wrong, though! :) ). I'm guessing the slides will be available on the ESUG website sometime soon but I'll post them if not.

Update: Slides are available here.