Wednesday, March 10, 2010

Constructing list by functionally threading state between user inputs

Ah, feels good to hack a bit of Scala after a while. A friend of mine was thinking about getting more lightweight syntax for list creation and I had urge to try something out. A simple way would be to create an implicit def that would lift a value to list:

    implicit def valueToList[a](value: a) = List(value)

Now you could have expressions like

    5 :: 3 (of type List[Int])

But just for fun I tried different approach that uses functions as intermediate values. After playing with it a while I ended up with a couple of cute trait/classes. They deal with order of evaluation so that one can for example ask user for some input, and decide should input be accepted or just ask for another. Here's what one toy use case looks like:

  val result =
    Builder.create[String] $
 ask ("Favourite number?", _ != "42") $
    ask ("The favorite president?", _ == "Bush") $
 ask ("Is Java important?", _ == "") ;

In ask method we show user a question, wait for input, and decide whether we accept it, or if user want's to exit, it will. The above predicates mean: first value must be "42", second: president can't be "Bush", and third value must not be empty.

 def ask(message: String, predicate: String => Boolean) = {
        println (message)
   val value = readLine
   if(value == "quit") throw End
   else if(predicate(value)) throw Again
   else value
 }

Ask method takes a message that is shown to user and a predicate which will test whether user's input was valid. Depending on the choice we construct the rest of the input list differently.

The control flow interrupts are handled with exceptions. The user won't ever see those exceptions, though. It's all hidden under the cover. So how does the result be different when user has quitted? Here's how we inspect how the interaction went and get the values

 if(result success) {
    println (result !)
 } else {
   println ("quitted")
}

We can ask from the result, whether it succeeded or not, and if it did, we can retrieve the result list with "!". For fail case, it would give empty list (we don't store partially constructed list, which we could).

Let's see how this is achieved. 

 trait Builder[a] extends Function1[a, Builder[a]] {
    def get: List[a]
    def `!`: List[a] = get
    def `$`(x: =>a): Builder[a]
    def success: Boolean
}
  
We have trait for incremental building (Builder), which is a Function1.  One gives it a new value with apply or $ method and it will give back a new Builder with the given value applied to  it. Notice that the parameter is call-by-value, so it won't be evaluated immediately. The method ! is for retrieving the actual result.

class EndBuilding[a] extends Builder[a] {
   def apply(x: a) = this
   override def get = List()
   def `$`(x: =>a): Builder[a] = this
   override def success = false
  }

We have two subclasses of Builder, one for building the list (ListBuilder) and one for termination (EndOfBuilding). The latter is simple: it doesn't do much, just return itself or tells that the construction failed (success = false).
  
class ListBuilder[a](init : List[a]) extends Builder[a] {
 override def success = true
 def apply(x: a): Builder[a] = new ListBuilder(x :: init)
  override def `$`(x: =>a): Builder[a] = {
    lazy val copy = x;
 
    try {
  apply(x)
   } catch {
      case Again => `$`(copy)
     case End => new EndBuilding[a]
   }
}
override def get = init reverse
def this(init: a) = this(List(init))
def this() = this(List())
}
  object End extends Throwable
  object Again extends Throwable

The ListBuilder is more interesting. $ method takes a call-by-name parameter x, essentially a thunk for later evaluation. We have a copy of it in lazy val for repeated use of x . After this we try to create a new ListBuilder with given value and at this point the x will be evaluated. This is important for the flow of the user interaction: at this point user is shown a message and input is waited to be given.

If the evaluated thunk throws either Again, or End, we catch them and change the flow of the interaction from linear to a bit more complex, repetitive even. If the user says "quit", we get End object thrown, and decide that it's time to end the construction. So we give back EndBuilding object. This way the thunks later in the flow are not evaluated at all (because they are call-by-name and evaluation is not forced inside EndBuilding).

In case user says something that we have specifically constrained out of the valid values (in ask method), we want to evaluate the question again. Again object is thrown inside thunk and catched in $. Because we had a copy of the thunk in reserve, we can just call the $ method recursively, and get the same question/input again.

In conclusion, I had a simple way to construct list, e.g. 5 $ 29 !; but it turned out to be a cool way to create a small interactive application. Whether this has any real user is up to you. Here is the whole program in one file: http://personal.inet.fi/koti/egaga/ohjelmointi/listcons.scala

Btw. I also noticed that the scaladoc distributed with 2.8 is quite unresponsive for filtering. So I made some dirty quick hacks and got it faster. Take a backup of your index.js in [scala]/bin/doc/scala-devel-docs/api/lib and put a copy of the following file there if you want to try it out: http://personal.inet.fi/koti/egaga/ohjelmointi/index.js

Also, I've created a new blog that might interest you if you are a passionate programmer, and would like to hear my opinions about Factor, Haskell, Clojure, or programming in general.


If you still haven't had enough, see what references I recommended for programmers (articles, books, videos) general or advanced/misc

1 comment:

Anonymous said...

nice article for beginners.thank you.
web programming tutorial
welookups