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.

http://huttuh.blogspot.com/

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

Named arguments

edit at 3rd of March, 2010: Scala will have named arguments in 2.8. Great! http://www.scala-lang.org/sid/1#

Scala unfortunately doesn't have named arguments. I would really like to have them, because they make code much clearer in some cases, and it's harder to make mistakes with them. That's why I'll show one way to simulate them.

First, let's create the function that can handle homemade named arguments:

    def f(x: {val name: String; val age: Int}) = {

f takes one argument, that contains the actual parameters we want. The type is shorthand for Any{ ... }.

Next we have imported the contents of x to be visible inside method f. This is possible due to Scala's handling of objects as first class modules.

    import x._

And now we can use the attributes as if they were f's real parameters:

    println(name + " is " + age + " years old")

How about from client's perspective? Well, client can just create a structural type that contains the needed attributes (actual arguments).

    f(new {val name = "Anthony"; val age = 5})

As you see, it's not really possible to make mistakes this way. But the calling has too much boilerplate, namely vals. So let's make it a bit better:

We create a case class for each actual parameter.

    case class Name(name : String)
   case class Age (age : Int)

Now we can make very clear function signature:

    def g(x: Name, y: Age) = {

Unfortunately we have to import all parameters one by one.

    import x._, y._
   println(name + " is " + age + " years old")

The client can call the method in the following way:

    g(Name("Tim"), Age(2))

That's it. It's annoying that we have to create case classes, but it's tolerable in important cases.

Here's the full code:

object Test extends Application{
 def f(x: {val name: String; val age: Int}) = {
   import x._
   println(name + " is " + age + " years old")
 }
 f(new {val name = "Anthony"; val age = 5})

 case class Name(name : String)
 case class Age (age : Int)

 def g(x: Name, y: Age) = {
   import x._, y._
   println(name + " is " + age + " years old")
 }
 g(Name("Tim"), Age(2))
}

Run the code and you get as output:
Anthony is 5 years old
Tim is 2 years old

edit:

On the client side, often one passes some constant values. If you call just like f(value1, value2, ... valueN), it's hard to know later when you see the code what the meaning for each value was; so you have to go see the API (if there's no tool help). Instead you have to define vals before the call:

val age = 8
val name = "Jim"
f(age, name)

But now there's the issue that you have to write the variables twice, and it would be nice to see immeaditely on the call what the value was.

Then:

f(new {val age = 8; val name = "Jim"})

isn't that bad at all. Neither the case class equivalent. If you have many arguments to pass, calling with single argument per line looks nice:

f(new { val age = 8
       val name = "Jim"
       val hobby = "blogging" })

Named arguments are especially useful when constructing objects, because it's then when you have to pass lots of vaguely related arguments.

On defence of implicit arguments and the lack of type inference power

I found two quite recent comments by Martin Odersky (main developer of Scala) that give insight to two commonly arised questions. They are 1) why implicit arguments exists, and aren't they too dangerous? And 2) Why on earth is this so cool type inference system behaving like an idiot, and isn't inferring some obvious cases.

Here are the quotes and links to the original source.

1)

"In practice, of course, you want to find the right mixture between expressiveness and safety. -- -- and you'll accept some implicit parameters at places where they are really useful. And they are amazingly useful when used as a tool in the right hands.

For instance ScalaCheck lets you write properties of your programs and then constructs unit tests for these properties automatically. Several bugs in the standard Scala library have been found this way. Without implicit parameters, the plumbing you'd have to do to set up the properties would make them much uglier, so people most likely would not write any. So that's an example where implicits are really useful. Expect to see many more libraries that do amazing things like ScalaCheck in the future.

-- --

P.S. I think this discussion highlights a bit the design philosophies behind Java and Scala. They are not the same. Scala puts more trust in its users that they will do the right thing. Maybe this assumption is wrong, and users will make a mess of it, but that's what Scala is."

Martin Odersky, posted on March 9, 2008 at 6:16 am

Original post

2)

"The reason Scala does not have Hindley/Milner type inference is that it is very difficult to combine with features such as overloading (the ad-hoc variant, not type classes), record selection, and subtyping. I’m not saying impossible — there exist a number of extensions that incorporate these features; in fact I have been guitly of some of them myself. I’m just saying it’s very difficult to make this work well in practice, where one needs to have small type expressions, and good error messages. It’s not a shut case either — many researchers are working on pushing the boundaries here (look for instance at Remy’s MLF). But right now it is a tradeoff of better type inferencing vs better support for these features. You can make the tradeoff both ways. The fact that we wanted to integrate with Java tipped the scales in favor of subtyping and away from Hindley/Milner."

Martin Odersky, posted on April 9, 2008 at 2:08 am

Original post

I hope this is not violation of any copyright ;)

Another news regarding Scala are that the contractiviness requirement for implicits was removed by David MacIver's suggestion. Moreover in one month Scala is likely to have some kind of version of virtual classes, so it's possible to extend class hierarchies in one more powerful way. I hope there will be a good documentation available when it's out *cough* existential types *cough*. :)

WhenDone - a todo application

I have now published my first open source Scala application, WhenDone. It's a todo application primarily for a single user. Goals are that it's easy to add a task, and easy to find a task do to. It's in its early phase, but is usable. I mainly develop this for my own needs, but it's a general app, so others might find it useful too. The most interesting thing might be that it is command based, even though it uses Swing! How perverted is that :).

Here's two screen captures from an example session:
Example session, part 1
Example session, part 2

WhenDone is under the MIT lisence. More information and downloadable content can be found at Google Code: WhenDone's project page.

Implicit conversions - magical and demonic

Implicit conversion is a useful mechanism, because it lets you extend libraries retroactively, without actually changing them. Let's take a common example.

We would like to repeat some String, say "nice" three times. We could write it as:

def *(times: Int, original: String) = {
def multiply(times: Int): String = {
 if(times > 1) original + multiply(times - 1)
 else original
}
multiply(times)
}

As a bit of a sidenote, multiply is not tail-recursive, because its recursive call is not the last thing it does. So it will blow up the stack space. Here's how we can make it tail recursive:

def *(times: Int, original: String) = {
def multiply(times: Int, accumulated: String): String = {
 if(times > 1) multiply(times - 1, accumulated + original)
 else original + accumulated
}
multiply(times, "")
}

This technique is called accumulation. We use additional parameter 'accumulated' to pile up the result incrementally. Now the compiler can optimize the recursive calls, and stack won't grow every call.

With '*' method defined in some object, and imported in use-site, we could now multiply strings with *("nice", 3). However, it's not as nice as we would like it to be, e.g. "nice" * 3. But how can we get there, because obviously we can't go and put the '*' method to String class. Well, the first thing to do is to create a class StringRepeated that has that method.

class StringRepeated(original: String){
def *(times: Int) = {
 def multiply(times: Int, accumulated: String): String = {
   if(times > 1) multiply(times - 1, accumulated + original)
   else original + accumulated
 }
 multiply(times, "")
}
}

Now if we create a StringRepeated, we can use the '*' like this:

val repeated = (new StringRepeated("nice")) * 3
// == "nicenicenice"

But we can't do this on normal Strings directly. The implicit conversion is what comes to rescue; it makes the conversion from String to StringRepeated.

implicit def string2repeated(x: String) = new StringRepeated(x)

That's it. Now when compiler sees a "nice" * 3, it first concludes that there is no '*' method defined in String. Then it looks for implicit conversion that would give a new object that has a '*' with correct parameter type. If there is no ambiguouty in choosing what implicit conversion to apply, the compiler will insert the conversion.

So "nice" * 3 will be statically translated to something like (new StringRepeated("nice")) * 3.

Now as this small example shows, implicit conversion can be somewhat handy. For additional example, I have an application that prints text that is partly colorized or otherwise styled. I have taken advantage of implicit conversion so that I can write printWith("Hi," | "this" * Bold | " is " * Fore(RED) | "cool."). It will print sequentially "Hi, this is cool."

Now I like this feature, but I think it's a bit dangerous. It's not always easy to see what conversions are happening, because they are automatically inserted. Good news is that you can control their use scope by importing the implicit conversions only to places where you really want them. Next I give you an example that combined with another unfortunate feature makes my head steam.

In Scala == is structural equality test method, unlike in Java, where it is reference equality test. It takes one argument type of Any, which means you can compare your object against any object. I mean any, and compiler will allow you that. Doesn't sound too bad, you say? Well, if you have lots of inheritance, you might really want that ability, so that you can reveal whether two objects are the same even if their static type is not the same. But usually I just want to know two statically equivalently typed objects to be tested against each other, not arbitrary objects.

I have had problems with this simply, because you don't always compare things you should. Humans do mistakes (I sometimes wonder, am I ever doing something *right*). For example, I might have a tuple of Ints, which has name 'boom'. And i have another tuple 'doom', and I'd like to compare their first elements, i.e. boom._1 == doom._1. But I might be a bit sleepy, and write "boom == doom._1", i.e. comparing a tuple against an Int. Compiler won't say that you are comparing completely different objects. It just sings logically incorrect bytecode. It might be very hard to notice that the comparison isn't ever going to give a true value just by testing it few times.

Ok, that's bad enough as it is, but when we mix implicit conversions with this magical soup, we are really doomed. An example: String has no reverse method. Therefore it has been extended with RichString in the same kind of way I described earlier for RepeatedString. When you say "yay" reverse, you get a RichString, not String. Guess what, "yay".reverse == "yay" won't give you true. Happy debugging times ahead, my friend. It isn't helping that with type inference in use, even with intermediate variables (val x = "yay" reverse) you might think you're dealing with a normal String. That might happen if you just forgot that there ever was a RichString class, and thought that reverse was defined in String.

My conclusion (temporary, as they always are) is that when you need concise syntax for some operations, give a thought about implicit conversions. But be sure to think carefully how it interacts with other types, and especially if you are dealing with multiple conversions.

True wizards use their magic sparingly.

Importing all classes but explicitly excluded

Importing is more powerful in Scala than in Java, because it's possible to use import inside functions i.e. you can locally bind the libraries you need. But there's also some syntactic sugar, f.ex. you can import more than one class from one path:

  object Top{
    object A
    class B
    trait C
  }

  import Top.{A, C} // imports A and C from Top package

It's possible to import all in one go with underscore '_'.

  import Top._ // imports A, B, C

What if we have a clash of names, e.g. 'A' is used in two paths.

  object Top2{ object A }

We can import and rename the other one (the new name is alias for the long name in that scope):

  import Top.A
  import Top2.{A => OtherA}

What if we need to import all but, say two classes. We could have lots of classes to explicitly type if we do it importing class by class; just using underscore would import also unwanted classes so it is not an option.

We can rename the unwanted to _, which in practice means that the naming is ignored, so effectively it's not imported at all. Let's pretend we have lots of classes in Top1, and we don't need just B and C.

  import Top.{B => _, C => _, _}

The last '_' tells to compiler to import all the others.

this.type for chaining method calls

Scala has powerful mechanisms borrowed from other languages, but often one small unique feature is not discussed: this.type. In this article I'll explain it shortly and show you a demonstration.

this.type is a singleton type, which means the type represents a certain object, not class of objects. It helps to solve the problem when you need to chain method calls of a class hierarchy, i.e. "value.method1.method2", where method1 is in super class A and method2 is in deriving class B.

  class A {def method1: A = this }
  class B extends A (def method2: B = this}
  val b = new B

Now we have defined the hierarchy, and created an instance of B named 'b'. Let's see about the chaining of method calls: The following works fine, because method2 returns type B which has method1:

  b.method2.method1

However, this won't

  b.method1.method2

because method1's result type is A, and so compiler thinks that the object hasn't got the method2.

We could solve this by overriding the method1 in B, which calls the super classes' method1 to do whatever work it does. The result type is covariantly set as B:

  class B extends A{
    override def method1: B = {super.method1; this };
    ...
  }

But this is extra work for every subclass of A that needs method chaining!

Here's the other way we can do it in Scala: Using this.type we can tell compiler that the resulting object from method1 is exactly the same as b, so compiler can infer that 'yeah, the resulting object from method1 has method2 too'.

  class A { def method1: this.type = this }
  class B extends A { def method2: this.type = this }
  // in method2 this.type is not a necessity
  // unless there's subclass of B.

Now

  val b = new B
  b.method1.method2

works with both alternatives.

For more specific information you can see: Scalable Component Abstractions which is a very good read otherwise, too.

Scala has also linear mixin composition of which you can read also on the same link. I'm not going into details, but idea is to have partial implementations as traits which we mixin together. We use them in this article, because we want to create a library, but we are not sure how we'd like to extend it later and want to take only the parts we need. Additionally we want the chaining work with all the upcoming traits uniformly, not just with the methods in the superclass. This is achieved with traits and this.type.

The heart is CommandCenter, which queues up given computations, which are just normal Scala functions, of type Unit => Any.

  trait CommandCenter{
    protected var queue = List[Unit => Any]()
    def <+(computation: => Any): this.type = {
      queue :::= List[Unit=>Any]({x => computation})
      this
    }
  }

Now we can make objects of CommandCenter that can chain adding of computations, e.g.

  val cmd = new CommandCenter{}
  cmd <+ Console.println("hi") <+ {network.send("bye")}

Certainly we'd like to execute those computations later, but we don't want to pollute the same trait, because it's different responsibility. Here's first a helper class, which just forces the evalution of computations that are in the list.

  def executeAll(list: List[Unit => Any]) 
  = list foreach {_()}

Here's the trait for actual execution:

  trait ExecuteCommands extends CommandCenter{
    def execute: Unit = executeAll(queue)
  }

Now we'd like to extend this thing so that we can make a group of computations and give them names by which we can later ask them to be evaluated.

  trait GroupedCommands extends CommandCenter {
    import scala.collection.mutable.HashMap
    protected val groups = HashMap[String, List[Unit=>Any]]()
    def >>(name: String) = {
      groups += ((name, queue))
     queue = List()
    }
  }

'>>' method ends the construction of computations; it takes all the computations in the queue and names it as a group, and clears the original queue so that new computations can be binded together.

We have also different trait for execution group computations, but we skip that (you can see it in the complete source code).

Now we can create a test case. First we have a construct method that only creates the computations. We restrict ourself from knowing more than grouping build operations i.e. GroupedCommands trait.

  def construct(command: GroupedCommands) = {
    var (x, y) = (1.0, 1.0)
    def printx = Console.println("x: " + x)
    command <+ printx <+ { x *= 2 } <+ printx >> "doubleX"
    command <+ printx <+ { x /= 2 } <+ printx >> "halfX"
  } 

Of course <+ is kinda useless, we could just make a one big computation with {comp1; comp2; ... compN}, but this is only an example, though by partioning them to be differentiable, one could use for example time delay between evaluations. Here's the execute part:

  def execute(command: GroupExecution) = {
    command execute("doubleX")
    command execute("doubleX")
    command execute("halfX")
  }

And finally the test that gives observable results:

  val command = new CommandCenter 
                with GroupedCommands with GroupExecution
  construct(command)
  execute(command)

It prints:

  x: 1.0, x: 2.0, x: 2.0, 4.0, x: 4.0, x: 2.0

Here's the complete source code.

So now you know of this.type. Spread the word, for rarely anyone mentions it.