What's the *right* way to handle a POST in FP?

Question

I'm just getting started with FP and I'm using Scala, which may not be the best way, since I can always fall back to an imperative style if the going gets tough. I'd just rather not. I've got a very specific question that points to a broader lacuna in my understanding of FP.

When a web application is processing a GET request, the user wants information that already exists on the web-site. The application only has to process and format the data in some way. The FB way is clear.

When a web application is processing a POST request, the user wants change the information held on the site. True, the information is not typically held in application variables, it's in a database or a flat-file, but still, I get the feeling I'm not grokking FP properly.

Is there a pattern for handling updates to static data in an FP language?

My vague picture of this is that the application is handed the request and the then-current site state. The application does its thing and returns the new site-state. If the current site-state hasn't changed since the application started, the new state becomes the current state and the reply is sent back to the browser (this is my dim image of Clojure's style); if the current state has been changed (by another thread, well, something else happens ...

Stoops

IO per definition is imperative – Ursulaursulette

See if you follow this syllogism: (a) I/O is imperative; (b) any non-trivial program requires I/O; therefore any functional program is trivial. I'm not saying I believe that, I'm just saying I don't understand why it's wrong. That's the essence of my original question. – Stoops

Functional programming means letting somebody else do the I/O. :-D – Lithesome

IO is not per definition, imperative. OP: it is incredibly important to not succumb to myths such as these. – Meir

@Malvolio: actually most sites do change what's held on a site when a GET is made too. Think about any forum or, heck, StackOverflow itself... Everytime a GET is made, what is held on the site changes because the user can see how many time the entry/post/question was viewed. So GET changes the state of the server too. – Alexanderalexandr

Answer 1

One way to deal with this kind of problem in a pure FP environment are monads like in Haskell (e.g. IO and State), but there are alternatives like "unique types" (which allow only one reference to a value) in Clean.

There is not much to grok here: If you have mutable state, then you need somehow to restrict access to it, in a way that every change of that state is perceived as a "new version" of that structure from the rest of the program. E.g. you can think of Haskell's IO as "rest of the world", but with a kind of clock attached to it. If you do something with IO, the clock ticks, and you never see the same IO again. The next time you touch it it's another IO, another world where everything you did has already happened.

In real life you can "see" how things "change" in a movie - that's the imperative view. But if you grab the film, you see just a string of small immutable pictures, without any trace of a "change" - that's the FP view. Both views are valid and "true" in their own context.

However, if you use Scala, you can have mutable state - no problem here. Scala simply don't need any special handling for this, and there is nothing wrong in using it (although it's considered "good styl"e to keep the "impure" spots as small as possible).

Engelbert

How do I translate those monads into real I/O, especially in a multithreaded environment? (Feel free just to give me a link if you have one). Yes, I realize Scala allows me to escape the FP paradigm, but I don't want out, I want to get further in. – Stoops

I'm definitely no expert for this, but it seems the most promising technique for this is FRP: en.wikipedia.org/wiki/Functional_reactive_programming – Engelbert

Answer 2

The answer is monads. Specifically, the state and io monads would handle this completely.

Here's an example of how this would work:

trait Monad[A] {
  def flatMap[B, T[X] <: Monad[X]](f: A => T[B]): T[B]
}

class State[A](st: A) extends Monad[A] {
  def flatMap[B, T[X] <: Monad[X]](f: A => T[B]): T[B] = f(st)
  def map[B](f: A => B): State[B] = new State(f(st))
}

object IO extends Monad[String] {
  def getField = scala.util.Random.nextString(5)
  def getValue = scala.util.Random.nextString(5)
  def fieldAndValue = getField + "," + getValue
  def flatMap[B, T[X] <: Monad[X]](f: String => T[B]): T[B] = f(fieldAndValue)
}

object WebServer extends Application {
    def programLoop(state: State[Map[String, String]]): State[Map[String, String]] = programLoop(
        for {
          httpRequest <- IO
          database <- state
        } yield database.updated(httpRequest split ',' apply 0, httpRequest split ',' apply 1)
    )

    programLoop(new State(Map.empty))
}

Note that there isn't a single thing that is mutable in the program, and, however, it will keep changing the "database" (represented by an immutable Map) until it runs out of memory. The IO object here is simulating hypothetical HTTP PUT requests by feeding pairs of randomly generated key and values.

So, this is the general structure of a functional program processing HTTP PUT and feeding a database. Think of a database as an immutable object -- each time you "update" it, you get a new database object.

Chu

But what happens when you have many types of requests and many types of resources and several layers of abstraction? – Footfall

@Footfall What is it that you see as a problem? In a non functional enviroment you have chaining and nesting of functions that turn a request into a response. It might be upside-down -- the code calls something to provide the response instead of returning it, but see Lift, BlueEyes, Unfiltered, Scalatra, Circumflex, etc. They all work as functions from request to response. Here we need (state, request) to (state, response). In fact, BlueEyes does that a bit, by passing in context. – Chu

Answer 3

The most idiomatic FP answer to asynchronous modifications of state over the web is continuation-passing style, I guess: the current running function is provided a continuation function as a "next action", whose calling with arguments resulting from the current computation (the analogous of the imperative return) represents state-passing.

Applied to the web, it means that when the server needs input from the user, it just saves the per-session continuation. When the user responds with some information, the saved continuation is restored, the input he provided is processed by some computation, and it is then returned as the value of the continuation.

You can find an example of continuations-based web application framework here. A detailed high-level writeup of the idea is here. See also the plethora of ressources and FP applications implementing this here.

Continutations are supported in Scala as of 2.8, and there is a 200-300 LoC example of a webserver in continuation-passing style in the distribution.

Katar

Answer 4

Note: I don't know Scala at all, so I'm just guessing at the syntax from examples.

Here's one functional way of implementing a map:

val empty           = x =>                scala.None
def insert(k, v, m) = x => if k == x then scala.Some(v) else m(k)
def delete(k, m)    = x => if k == x then scala.None    else m(k)
def get(k, m)       = m(k)

Instead of a traditional data structure, a map can be just a function. To add or remove entries from the map, a function is composed with the existing map to yield a new map.

I like thinking of webapps like this too. A webapp converts requests into transactions. A transaction mutates one state to another, but it could be applied to the current state, or some past state, or some unknown future state. Transactions alone aren't useful; something has to be sequencing them, applying them one after another. But the request handler doesn't have to think about that at all.

As an example, take a look at how the Happstack framework models state. An incoming request gets routed to a handler which runs inside a monad. Thanks in part to some TH magic, the framework serializes the resulting mote and adds it to the tail of the growing transaction log. To determine the most recent state, one can simply step through the log file, applying transactions in sequence. (Happstack can write "checkpoints" too, but they're not strictly necessary for operation.)

Lithesome