cocoon-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Ovidiu Predescu <ovi...@cup.hp.com>
Subject Flowmaps: the wrong approach (was Re: [RT] (long) Rethinking Finite State Machine Approach to Flow Management)
Date Fri, 30 Nov 2001 22:38:46 GMT
This is very interesting, in the past few weeks I was investigating
alternative approaches to FSM too!

What I was looking at were continuations in functional languages like
Scheme. With their aid you can essentially describe a very complex Web
based interaction just like when you're writing in a procedural
language. It's amazingly simple and powerful!

For example, you can write a login sequence like this (pseudo-code,
not actual Scheme syntax):

void login()
{
  page = "login.xml"

  while (true) {
    send-response (page)
    username = getParameter ("username")
    password = getParameter ("password")
    if (username, password) in database
      break
    page = "bad-login.xml"
  }

  compose-news()
}

void compose-news ()
{
  // Display the news composing form
  page = "compose-news.xml"
  while (true) {
    send-response (page)
    subject = getParameter ("subject")
    body = getParameter ("body")
    if (subject == null)
      page = "no-subject.xml"
    else if (body == null)
      page = "no-body.xml"
    else
      break
  }

  // Do some other stuff here
}

In the above example send-response is a special procedure, which sends
the response back to the client, saves the state of the program in a
so-called continuation object, and stops the execution of the thread
serving the request, simply killing it.

When the client clicks the "Submit" button on the displayed HTML page,
the program is awaken by the system _exactly_ where it stopped, and
continues the execution as it wasn't interrupted at all!

Even more, this mechanism takes care of the situation where the user
uses the back button to view some older pages, and then decides to
continue on an alternative path. Since the continuation objects are
still maintained by the system, hitting the submit button in such a
page will resume the program in a previous point in its execution!

In some cases though, you don't want to allow such behaviors. There
are ways through which you can nullify the past continuations, and
remove them from the system. This will disallow the user to go back
and go on alternate paths.

With this mechanism you can write Web apps which are a _lot_ easier to
write, maintain, and validate as correct. All the logic is expressed
in a natural way to the programmer, as procedures. In fact some of the
more complex Web applications are very hard to write using FSM, simply
because they cannot be expressed using a regular grammar.

Unfortunately continuations are something specific to functional
languages, Java doesn't support this concept. Fortunately there is a
whole theory (Continuation Passing Style, do a search on Google for
more info) on how to take a continuation style program and transform
it into a program for a language without continuations.

Here are some very useful resources that describe in detail the
concepts I mentioned above:

The original paper describing the relationship between Web and
continuations:

  http://youpou.lip6.fr/queinnec/Papers/webcont.ps.gz

A Scheme interpreter written in Java, which implements the
abstractions in the above paper:

  http://youpou.lip6.fr/queinnec/VideoC/ps3i.html

Another paper that describes the concepts, and shows another
interesting possible implementation:

  http://www.cs.rice.edu/CS/PLT/Publications/esop2001-gkvf.ps.gz

The last paper shows some very impressive figures. Although I wasn't
quite able to obtain the same performances as described above, I still
got very good results.

And here is a paper, which while not showing any of the above,
explains why would one want to program in Lisp :-) The author wrote
together with another guy a Web app in early 1995, which sold to Yahoo
in 1997, and is currently Yahoo Store, for $50 million I'm told. The
site is written entirely in Lisp! Check it out at:

http://www.paulgraham.com/avg.html


Regards,
-- 
Ovidiu Predescu <ovidiu@cup.hp.com>
http://orion.rgv.hp.com/ (inside HP's firewall only)
http://sourceforge.net/users/ovidiu/ (my SourceForge page)
http://www.geocities.com/SiliconValley/Monitor/7464/ (GNU, Emacs, other stuff)

On Fri, 30 Nov 2001 13:38:17 -0500, Jason Foster <jafoster@uwaterloo.ca> wrote:

> <snip type="lots of interesting ideas"/>
> 
> One thing I would like to inject into the discussion is the idea of 
> switching from a (I think I've got this right) imperative to a declarative 
> approach to defining the FSM.
> 
> The example FSM given by Berin is described in what I would call a 
> classical imperative approach.  The whole FSM is defined in one step by 
> enumerating the states and the transitions.  The complexity of such beasts 
> grows extremely quickly ( O(n^2) with a small constant depending on 
> sparseness, IIRC) and they soon become a real pain for a single mind to 
> grasp.
> 
> I was looking at Prolog recently and thought that you could define 
> something a lot like an FSM using a declarative approach.  Basically 
> instead of having to define all of the states and transitions at one time,
>   you treat the problem at the level of individual states and their 
> preconditions.  The inference engine then decides if a particular 
> transition is legal.
> 
> Moving away from the FSM example, consider the example of generating a 
> reply to a URI.  Right now we declare the pipeline explicitly.  We match on 
> the URI and then process away.  An alternative would be to consider the URI 
> as a proposition and the "sitemap" as declaring a set of axioms.  When a 
> request comes in an inference engine determines if you can "prove" the URI 
> using the axioms.  Each axiom could add something to the output stream or 
> to whatever it is that actions use to store their results.  The the URI is 
> "provable" then we send the reply to the client.  If it isn't, then we send 
> a 404.
> 
> The reason I thought this approach might have some merit is that it may 
> reduce the complexity of the sitemap.  Instead of having to worry about all 
> of the states and the overall flow through the system, you only worry about 
> single states/actions and their preconditions.  The inference engine takes 
> care of actually hooking everything up.  There are a number of Open Source 
> implementations of Prolog and similar languages that we could adopt if this 
> looks to be a good idea.
> 
> I think that this approach complements, not replaces what Berin was 
> proposing.
> 
> Of course once Cocoon's "control" mechanism (Sitemap, Flowmap, etc.) is 
> made into a component controlled by cocoon.xconf we can have all sorts of 
> different mechanisms!  It's not confusion, it's choice ;)
> 
> Just a thought.
> 
> Jason Foster

---------------------------------------------------------------------
To unsubscribe, e-mail: cocoon-dev-unsubscribe@xml.apache.org
For additional commands, email: cocoon-dev-help@xml.apache.org


Mime
View raw message