My team and I are developing an enterprise-level application and I have devised an architecture for it that's best described as an "Expression Tree". The basic idea is that the leaf nodes of the tree are very simple expressions (perhaps simple values or strings). Nodes closer to the trunk will get more and more complex, taking the simpler nodes as their inputs and returning more complex results for their parents.

Looking at it the other way, the application performs some task, and for this it creates a root expression. The root expression divides its input into smaller units and creates child expressions, which when evaluated it can use to build it's own result. The subdividing process continues until the simplest leaf nodes.

There are two very important aspects of this architecture:

  • It must be possible to manipulate nodes of the tree after it is built. The nodes may be given new input values to work with and any change in result for that node needs to be propagated back up the tree to the root node.

  • The application must make best use of available processors and ultimately be scalable to other computers in a grid or in the cloud. Nodes in the tree will often be updating concurrently and notifying other interested nodes in the tree when they get a new value.

Unfortunately, I'm not at liberty to discuss my actual application, but to aid understanding a little bit, you might imagine a kind of spreadsheet application being implemented with a similar architecture, where changes to cells in the table are propagated all over the place to other cells that need the result. The spreadsheet could get so massive that applying multi-core multi-computer distributed system to solve it would be of benefit.

I've got my prototype "Expression Engine" working nicely on a single multi-core PC but I've started to run into a few concurrency issues (as expected because I haven't been taking too much care so far) so it's now time to start thinking about migrating the Engine to a more robust library, and that leads to a number of related questions:

  1. Is there any precedent for my "Expression Tree" architecture that I could research?

  2. What programming concepts should I consider. I realise this approach has many similarities to a functional programming style, and I'm already aware of the concepts of using futures and actors. Are there any others?

  3. Are there any languages or libraries that I should study? This question is inspired by my accidental discovery of Scala and the Akka library (which has good support for Actors, Futures, Distributed workloads etc.) and I'm wondering if there is anything else I should be looking at as well?


It sounds to me like you've reinvented Lisp. It has trees of operators and data that get combined into larger and larger expressions. I would suggest you take a look at Clojure. Clojure is a Lisp for the JVM purpose built to tackle functional programming with heavy concurrency from the start.

  • I'll add to this that you'll want to look at technologies like Hadoop for scaling out beyond a single VM. I'd also really make sure that you prototype some possible technologies - you've got a complex problem domain and going down the wrong pat early could hurt you. – Martijn Verburg Oct 26 '11 at 7:16
  • I had come across Lisp (and Clojure) before, but not in this 'Expression Tree' context. I've done some more research with the links you've provided and I think I'll need to try some practical examples to really understand what's possible. My only reservation is that I find Lisp to be a write-only (almost unreadable) language. I think I'd hate trying to maintain production code in Lisp. Anyway, I may gain enough from experimenting with it to influence my thought processes so thanks for the input. – Dave Hartnoll Nov 3 '11 at 17:29

This sounds like a very good use-case for Clojure. Quick bullets:

  • Functional language (lazy, impure) - the dominant idiom for creating programs is by composing functions in a very similar manner to your expression trees.
  • Lisp - as a homoiconic languages it's perfect for code generation and DSLs
  • JVM language with very easy access to all Java libraries and tools
  • Amazing concurrency features - see this video
  • Interactive developemnt (ability to interact with running program via REPL, redefining objects on the fly etc).
  • Dynamically typed

Furthermore, you seem to be descibing a Dataflow Architecture. There has been quite a lot of study on such approaches and they are indeed well suited to many domains. If you wanted to implement a distributed dataflow architecture using such "Expression Trees" you might be able to build upon the following:

  • Clojure for defining the core expression tree language
  • Storm library for distributed processing
  • Incanter for statistics, data processing and visualisation
  • Thanks for that extremely useful answer. You've strengthened the previous suggestion for Clojure and given me a lot to think about. The video was particularly enlightening because it addresses so many of the problems I'm already encountering. – Dave Hartnoll Nov 30 '11 at 16:04

Not the answer you're looking for? Browse other questions tagged or ask your own question.