Specs2 2.0 - Interpolated

The latest release of specs2 (2.0) deserves a little bit more than just release notes. It needs explanations, apologies and a bit of celebration!

Explanations

• why is there another (actually several!) new style(s) of writing acceptance specifications
• what are Scripts and ScriptTemplates
• what has been done for compilation times
• what you can do with Snippets
• what is an ExampleFactory

Apologies

• the >> / in problem
• API breaks
• Traversable matchers
• AroundOutside and Fixture
• the never-ending quest for Given/When/Then specifications

Celebration

• compiler-checked documentation!
• "operator-less" specifications!
• more consistent Traversable matchers!

Explanations

Scala 2.10 is a game changer for specs2, thanks to 2 features: String interpolation and Macros.

String interpolation

Specs2 has been designed from the start with the idea that it should be immutable by default. This has led to the definition of Acceptance specifications with lots of operators, or, as someone put it elegantly, "code on the left, brainfuck on the right":

class HelloWorldSpec extends Specification { def is =

  "This is a specification to check the 'Hello world' string"            ^
                                                                         p^
    "The 'Hello world' string should"                                    ^
    "contain 11 characters"                                              ! e1^
    "start with 'Hello'"                                                 ! e2^
    "end with 'world'"                                                   ! e3^
                                                                         end
  def e1 = "Hello world" must have size(11)
  def e2 = "Hello world" must startWith("Hello")
  def e3 = "Hello world" must endWith("world")
}

Fortunately Scala 2.10 now offers a great alternative with String interpolation. In itself, String interpolation is not revolutionary. A string starting with s can have interpolated variables:

val name = "Eric"
s"Hello $name!"

Hello Eric!

But the great powers behind Scala realized that they could both provide standard String interpolation and give you the ability to make your own. Exactly what I needed to make these pesky operators disappear!

class HelloWorldSpec extends Specification { def is =         s2"""

 This is a specification to check the 'Hello world' string

 The 'Hello world' string should
   contain 11 characters                                      $e1
   start with 'Hello'                                         $e2
   end with 'world'                                           $e3
                                                              """

   def e1 = "Hello world" must have size(11)
   def e2 = "Hello world" must startWith("Hello")
   def e3 = "Hello world" must endWith("world")
}

What has changed in the specification above is that text Fragments are now regular strings in the multiline s2 string and the examples are now inserted as interpolated variables. Let's explore in more details some aspects of this new feature:

• layout
• examples descriptions
• other fragments
• implicit conversions
• auto-examples

Layout

If you run the HelloWorldSpec you will see that the indentation of each example is respected in the output:

This is a specification to check the 'Hello world' string

The 'Hello world' string should
  + contain 11 characters
  + start with 'Hello'
  + end with 'world'

This means that you don't have to worry anymore about the layout of text and use the p, t, bt, end, endp formatting fragments as before.

Examples descriptions

On the other hand, the string which is taken as the example description is not as well delimited anymore, so it is now choosen by convention to be everything that is on the same line. For example this is what you get with the new interpolated string:

s2"""
My software should
  do something that it pretty long to explain,
  so long that it needs 2 lines" ${ 1 must_== 1 }
"""

My software should
  do something that it pretty long to explain,
  + so long that it needs 2 lines"

If you want the 2 lines to be included in the example description you will need to use the "old" form of creating an example:

s2"""
My software should
${ """do something that it pretty long to explain,
    so long that it needs 2 lines""" ! { 1 must_== 1 } }
"""

My software should+ do something that it pretty long to explain,
    so long that it needs 2 lines

But I suspect that there will be very few times when you will want to do that.

Other fragments and variables

Inside the s2 string you can interpolate all the usual specs2 fragments: Steps, Actions, included specifications, Forms... However you will quickly realize that you can not interpolate arbitrary objects. Indeed, excepted specs2 objects, the only other 2 types which you can use as variables are Snippets (see below) and Strings.

The restriction is there to remind you that, in general, interpolated expressions are "unsafe". If the expression you're interpolating is throwing an Exception, as it is commonly the case with tested code, there is no way to catch that exception. If that exception is uncaught, the whole specification will fail to be built. Why is that?

Implicit conversions

When I first started to experiment with interpolated strings I thought that they could even be used to write Unit Specifications:

s2"""
This is an example of conversion using integers ${
  val (a, b) = ("1".toInt, "2".toInt)
  (a + b) must_== 3
}
"""

Unfortunately such specifications will horribly break if there is an error in one of the examples. For instance if the example was:

This is an example of conversion using integers ${
  // oops, this is going to throw a NumberFormatException!
  val (a, b) = ("!".toInt, "2".toInt) 
  (a + b) must_== 3
}

Then the whole string and the whole specification will fail to be instantiated!

The reason is that everything you interpolate is converted, through an implicit conversion, to a "SpecPart" which will be interpreted differently depending on its type. If it is a Result then we will interpret this as the body of an Example and use the preceding text as the description. If it is just a simple string then it is just inserted in the specification as a piece of text. But implicit conversions of a block of code, as above, are not converting the whole block. They are merely converting the last value! So if anything before the last value throws an Exception you will have absolutely no way to catch it and it will bubble up to the top.

That means that you need to be very prudent when interpolating arbitrary blocks. One work-around is to do something like that

import execute.{AsResult => >>}
s2"""

This is an example of conversion using integers ${>>{
  val (a, b) = ("!".toInt, "2".toInt)
  (a + b) must_== 3
}}
  """

But you have to admit that the whole ${>>{...}} is not exactly gorgeous.

Auto-examples

One clear win of Scala 2.10 for specs2 is the use of macros to capture code expressions. This particularly interesting with so-called "auto-examples". This feature is really useful when your examples are so self-descriptive that a textual description feels redundant. For example if you want to specify the String.capitalize method:

s2"""
 The `capitalize` method verifies
 ${ "hello".capitalize       === "Hello" }
 ${ "Hello".capitalize       === "Hello" }
 ${ "hello world".capitalize === "Hello world" }
"""

 The `capitalize` method verifies
 + "hello".capitalize       === "Hello"
 + "Hello".capitalize       === "Hello"
 + "hello world".capitalize === "Hello world"
 

It turns out that the method interpolating the s2 extractor is using a macro to extract the text for each interpolated expression and so, if on a given line there is no preceding text, we take the captured expression as the example description. It is important to note that this will only properly work if you enable the -Yrangepos scalac option (in sbt: scalacOptions in Test := Seq("-Yrangepos")).

However the drawback of using that option is the compilation speed cost which you can incur (around 10% in my own measurements). If you don't want (or you forget :-)) to use that option there is a default implementation which should do the trick in most cases but which might not capture all the text in some edge cases.

Scripts

The work on Given/When/Then specifications has led to a nice generalisation. Since the new GWT trait decouples the specification text from the steps and examples to create, we can push this idea a bit further and create "classical" specifications where the text is not annotated at all and examples are described somewhere else.

Let's see what we can do with the org.specs2.specification.script.Specification class:

import org.specs2._
import specification._

class StringSpecification extends script.Specification with Grouped { def is = s2"""

Addition
========

 It is possible to add strings with the + operator
  + one string and an empty string
  + 2 non-empty strings

Multiplication
==============

 It is also possible to duplicate a string with the * operator
  + using a positive integer duplicates the string
  + using a negative integer returns an empty string
                                                                                """

  "addition" - new group {
    eg := ("hello" + "") === "hello"
    eg := ("hello" + " world") === "hello world"
  }
  "multiplication" - new group {
    eg := ("hello" * 2) === "hellohello"
    eg := ("hello" * -1) must beEmpty
  }
}

With script.Specifications you just provide a piece of text where examples are starting with a + sign and you specify examples groups. Example groups were introduced in a previous version of specs2 with the idea of providing standard names for examples in Acceptance specifications.

When the specification is executed, the first 2 example lines are mapped to the examples of the first group, and the examples lines from the next block (as delimited with a Markdown title) are used to build examples by taking expectations in the second group (those group are automatically given names, g1 and g2, but you can specify them yourself: "addition" - new g1 {...).

This seems to be a lot of "convention over configuration" but this is actually all configurable! The script.Specification class is an example of a Script and it is associated with a ScriptTemplate which defines how to parse text to create fragments based on the information contained in the Script (we will see another example of this in action below with the GWT trait which proposes another type of Script named Scenario to define Given/When/Then steps).

There are lots of advantages in adopting this new script.Specification class:

• it is "operator-free", there's no need to annotate your specification on the right with strange symbols

• tags are automatically inserted for you so that it's easy to re-run a specific example or group of examples by name: test-only StringSpecification -- include g2.e1

• examples are marked as pending if you haven't yet implemented them

• it is configurable to accomodate for other templates (you could even create Cucumber-like specifications if that's your thing!)

The obvious drawback is the decoupling between the text and the examples code. If you restructure the text you will have to restructure the examples accordingly and knowing which example is described by which piece of text is not obvious. This, or operators on the right-hand side, choose your poison :-)

Compilation times

Scala's typechecking and JVM interoperability comes with a big price in terms of compilation times. Moderately-sized projects can take minutes to compile which is very annoying for someone coming from Java or Haskell.

Bill Venners has tried to do a systematic study of which features in testing libraries seems to have the biggest impact. It turns out that implicits, traits and byname parameters have a significant impact on compilation times. Since specs2 is using those features more than any other test library, I tried to do something about it.

The easiest thing to do was to make Specification an abstract class, not a trait (and provide the SpecificationLike trait in its place). My unscientific estimation is that this single change removed 0.5 seconds per compiled file (from 313s to 237s for the specs2 build, and a memory reduction of 55Mb, from 225Mb to 170Mb).

Then, the next very significant improvement was to use interpolated specifications instead of the previous style of Acceptance specifications. The result is impressive: from 237 seconds to 150 seconds and a memory reduction of more than 120Mb, from 170Mb to 47Mb!

On the other hand, when I tried to remove some of the byname parameters (the left part of a must_== b) I didn't observe a real impact on compilation times (only 15% less memory).

The last thing I did was to remove some of the default matchers (and to add a few others). Those matchers are the "content" matchers: XmlMatchers, JsonMatchers, FileMatchers, ContentMatchers (and I added instead the TryMatchers). I did this to remove some implicits from the scope when compiling code but also to reduce the namespace footprint everytime you extend the Specification class. However I couldn't see a major improvement to compile-time performances with this change.

Snippets

One frustration of software documentation writers is that it is very common to have stale or incorrect code because the API has moved on. What if it was possible to write some code, in the documentation, that will be checked by the compiler? And automatically refactored when you change a method name?

This is exactly what Snippets will do for you. When you want to capture and display a piece of code in a Specification you create a Snippet:

s2"""
This is an example of addition: ${snippet{

// who knew?
1 + 1 == 2
}}
"""

This renders as:

This is an example of addition

// who knew?
1 + 1 == 2

And yes, you guessed it right, the Snippet above was extracted by using another Snippet! I encourage you to read the documentation on Snippets to see what you can do with them, the main features are:

• code evaluation: the last value can be displayed as a result

• checks: the last value can be checked and reported as a failure in the Specification

• code hiding: it is possible to hide parts of the code (initialisations, results) by enclosing them in "scissors" comments of the form // 8<--

Example factory

Every now and then I get a question from users who want to intercept the creation of examples and use the example description to do interesting things before or after the example execution. It is now possible to do so by providing another ExampleFactory rather than the default one:

import specification._

class PrintBeforeAfterSpec extends Specification { def is =
  "test" ! ok

  case class BeforeAfterExample(e: Example) extends BeforeAfter {
    def before = println("before "+e.desc)
    def after  = println("after "+e.desc)
  }

  override def exampleFactory = new ExampleFactory {
    def newExample(e: Example) = {
      val context = BeforeAfterExample(e)
      e.copy(body = () => context(e.body()))
    }
  }
}

The PrintBeforeAfterSpec will print the name of each example before and after executing it.

Apologies

the >> / in problem

This issue has come up at different times and one lesson is: Unit means "anything" so don't try to be too smart about it. So I owe an apology to the users for this poor API design choice and for the breaking API change that is now ensuing. Please read the thread in the Github issue to learn how to fix compile errors that would result from this change.

API breaks

While we're on the subject of API breaks, let's make a list:

• Unit values in >> / in: now you need to explicitly declare if you mean "a list of examples created with foreach" or "a list of expectations created with foreach"

• Specification is not a trait anymore so you should use the SpecificationLike trait instead if that's what you need (see the Compilation times section)

• Some matchers traits have been removed from the default matchers (XML, JSON, File, Content) so you need to explicitly mix them in (see the Compilation times section)

• The Given/When/Then functionality has been extracted as a deprecated trait specification.GivenWhenThen (see the Given/When/Then? section)

• the negation of the Map matchers has changed (this can be considered as a fix but this might be a run-time break for some of you)

• many of the Traversable matchers have been deprecated (see the next section)

Traversable matchers

I've had this nagging thought in my mind for some time now but it only reached my conscience recently. I always felt that specs2 matchers for collections were a bit ad-hoc, with not-so-obvious ways to do simple things. After lots of fighting with implicit classes, overloading and subclassing, I think that I have something better to propose.

With the new API we generalize the type of checks you can perform on elements:

• Seq(1, 2, 3) must contain(2) just checks for the presence of one element in the sequence

• this is equivalent to writing Seq(1, 2, 3) must contain(equalTo(2)) which means that you can pass a matcher to the contain method. For example containAnyOf(1, 2, 3) is contain(anyOf(1, 2, 3)) where anyOf is just another matcher

• and more generally, you can pass any function returning a result! Seq(1, 2, 3) must contain((i: Int) => i must beEqualTo(2)) or Seq(1, 2, 3) must contain((i: Int) => i == 2) (you can even return a ScalaCheck Prop if you want)

Then we can use combinators to specify how many times we want the check to be performed:

• Seq(1, 2, 3) must contain(2) is equivalent to Seq(1, 2, 3) must contain(2).atLeastOnce

• Seq(1, 2, 3) must contain(2).atMostOnce

• Seq(1, 2, 3) must contain(be_>=(2)).atLeast(2.times)

• Seq(1, 2, 3) must contain(be_>=(2)).between(1.times, 2.times)

This covers lots of cases where you would previously use must have oneElementLike(partialFunction) or must containMatch(...). This also can be used instead of the forall, atLeastOnce methods. For example forall(Seq(1, 2, 3)) { (i: Int) => i must be_>=(0) } is Seq(1, 2, 3) must contain((i: Int) => i must be_>=(0)).forall.

The other type of matching which you want to perform on collections is with several checks at the time. For example:

• Seq(1, 2, 3) must contain(allOf(2, 3))

This seems similar to the previous case but the combinators you might want to use with several checks are different. exactly is one of them:

• Seq(1, 2, 3) must contain(exactly(3, 1, 2)) // we don't expect ordered elements by default

Or inOrder

• Seq(1, 2, 3) must contain(exactly(be_>(0), be_>(1), be_>(2)).inOrder) // with matchers here

One important thing to note though is that, when you are not using inOrder, the comparison is done greedily, we don't try all the possible combinations of input elements and checks to see if there would be a possibility for the whole expression to match.

Please explore this new API and report any issue (bug, compilation error) you will find. Most certainly the failure reporting can be improved. The description of failures is much more centralized with this new implementation but also a bit more generic. For now, the failure messages are just listing which elements were not passing the checks but they do not output something nice like: The sequence 'Seq(1, 2, 3) does not contain exactly the elements 4 and 3 in order: 4 is not found'.

AroundOutside vs Fixture

My approach to context management in specs2 has been very progressive. First I provided the ability to insert code (and more precisely effects) before or after an Example, reproducing here standard JUnit capabilities. Then I've introduced Around to place things "in" a context, and Outside to pass data to an example. And finally AroundOutside as the ultimate combination of both capabilities.

I thought that with AroundOutside you could do whatever you needed to do, end of story. It turns out that it's not so simple. AroundOutside is not general enough because the generation of Outside data cannot be controled by the Around context. This proved to be very problematic for me on a specific use case where I needed to re-run the same example, based on different parameters, with slightly different input data each time. AroundOutside was just not doing it. The solution? A good old Fixture. Very simple, a Fixture[T], is a trait like that:

trait Fixture[T] {
  def apply[R : AsResult](f: T => R): Result
}

You can define an implicit fixture for all the examples:

class s extends Specification { def is = s2"""
  first example using the magic number $e1
  second example using the magic number $e1
"""

  implicit def magicNumber = new specification.Fixture[Int] {
    def apply[R : AsResult](f: Int => R) = AsResult(f(10))
  }

  def e1 = (i: Int) => i must be_>(0)
  def e2 = (i: Int) => i must be_<(100)
}

I'm not particularly happy to add this to the API because it adds to the overall API footprint and learning curve, but in some scenarios this is just indispensable.

Given/When/Then?

With the new "interpolated" style I had to find another way to write Given/When/Then (GWT) steps. But this is tricky. The trouble with GWT steps is that they are intrisically dependent. You cannot have a Then step being defined before a When step for example.

The "classic" style of acceptance specification is enforcing this at compile time because, in that style, you explicitly chain calls and the types have to "align":

class GivenWhenThenSpec extends Specification with GivenWhenThen { def is =

  "A given-when-then example for a calculator"                 ^ br^
    "Given the following number: ${1}"                         ^ aNumber^
    "And a second number: ${2}"                                ^ aNumber^
    "And a third number: ${6}"                                 ^ aNumber^
    "When I use this operator: ${+}"                           ^ operator^
    "Then I should get: ${9}"                                  ^ result^
                                                               end

  val aNumber: Given[Int]                 = (_:String).toInt
  val operator: When[Seq[Int], Operation] = (numbers: Seq[Int]) => (s: String) => Operation(numbers, s)
  val result: Then[Operation]             = (operation: Operation) => (s: String) => { operation.calculate  must_== s.toInt }

  case class Operation(numbers: Seq[Int], operator: String) {
    def calculate: Int = if (operator == "+") numbers.sum else numbers.product
  }
}

We can probably do better than this. What is required?

• to extract strings from text and transform them to well-typed values
• to define functions using those values so that types are respected
• to restrict the composition of functions so that a proper order of Given/When/Then is respected
• to transform all of this into Steps and Examples

So, with apologies for coming up with yet-another-way of doing the same thing, let me introduce you to the GWT trait:

import org.specs2._                                                                                      
import specification.script.{GWT, StandardRegexStepParsers}                                                                                                         
                                                                                                         
class GWTSpec extends Specification with GWT with StandardRegexStepParsers { def is = s2"""              
                                                                                                         
 A given-when-then example for a calculator                       ${calculator.start}                   
   Given the following number: 1                                                                         
   And a second number: 2                                                                                
   And a third number: 6                                                                                 
   When I use this operator: +                                                                           
   Then I should get: 9                                                                                  
   And it should be >: 0                                          ${calculator.end}
                                                                  """

  val anOperator = readAs(".*: (.)$").and((s: String) => s)

  val calculator =
    Scenario("calculator").
      given(anInt).
      given(anInt).
      given(anInt).
      when(anOperator) { case op :: i :: j :: k :: _ => if (op == "+") (i+j+k) else (i*j*k) }.
      andThen(anInt)   { case expected :: sum :: _   => sum === expected }.
      andThen(anInt)   { case expected :: sum :: _   => sum must be_>(expected) }

}

In the specification above, calculator is a Scenario object which declares some steps through the given/when/andThen methods. The Scenario class provides a fluent interface in order to restrict the order of calls. For example, if you try to call a given step after a when step you will get a compilation error. Furthermore steps which are using extracted values from previous steps must use the proper types, what you pass to the when step has to be a partial function taking in a Shapeless HList of the right type.

You will also notice that the calculator is using anInt, anOperator. Those are StepParsers, which are simple objects extracting values from a line of text and returning Either[Exception, T] depending on the correct conversion of text to a type T. By default you have access to 2 types of parsers. The first one is DelimitedStepParser which expects that values to extract are enclosed in {} delimiters (this is configurable). The other one is RegexStepParser which uses a regular expression with groups in order to know what to extract. For example anOperator defines that the operator to extract will be just after the column at the end of the line.

Finally the calculator scenario is inserted into the s2 interpolated string to delimitate the text it applies to. Scenario being a specific kind of Script it has an associated ScriptTemplate which defines that the last lines of the text should be paired with the corresponding given/when/then method declarations. This is configurable and we can imagine other ways of pairing text to steps (see the org.specs2.specification.script.GWT.BulletTemplate class for example).

For reasons which are too long to expose here I've never been a big fan of Given/When/Then specifications and I guess that the multitude of ways to do that in specs2 shows it. I hope however that the GWT fans will find this approach satisfying and customisable to their taste.

Celebration!

I think there are some really exciting things in this upcoming specs2 release for "Executable Software Specifications" lovers.

Compiler-checked documentation

Having compiler-checked snippets is incredibly useful. I've fixed quite a few bugs in boths specs2 and Scoobi user guides and I hope that I made them more resistant to future changes that will happen through refactoring (when just renaming things for example). I'm also very happy that, thanks to macros, the ability to capture code was extended to "auto-examples". In previous specs2 versions, this is implemented by looking at stack traces and doing horrendous calculations on where a piece of code would be. This gives me the shivers everytime I have to look at that code!

No operators

The second thing is Scripts and ScriptTemplates. There is a trade-off when writing specifications. On one hand we would like to read pure text, without the encumbrance of implementation code, on the other hand, when we read specification code, it's nice to have a short sentence explaining what it does. With this new release there is a continuum of solutions on this trade-off axis:

1. you can have pure text, with no annotations but no navigation is possible to the code (with org.specs2.specification.script.Specification)
2. you can have annotated text, with some annotations to access the code (with org.specs2.Specification)
3. you can have text interspersed with the code (with org.specs2.mutable.Specification)

New matchers

I'm pretty happy to have new Traversable matchers covering a lot more use cases than before in a straight-forward manner. I hope this will reduce the thinking time between "I need to check that" and "Ok, this is how I do it".

---

Please try out the new Release Candidate, report bugs, propose enhancements and have fun!

Strong functional programming

Programming in a statically typed functional language (think Haskell) gives quite a few safety guarantees as well as a lot of expressivity thanks to the use of higher-order functions. However the type system lets you write some problematic functions like:

loop :: Int -> Int
loop n = 1 + loop n

Why is that problematic? For one, this function never terminates, that can't be good. But also, and this is very annoying, we can not anymore use equational reasoning:

loop 0 = 1 + loop 0

// substract (loop 0) from both sides, and use `x - x = 0`
0 = 1

0 = 1 can then allow you to prove anything => #fail.

In this post I'm going to present the ideas of "Strong functional programming" (or "Total functional programming") and show how they can help avoid this situation above where unrestricted recursion goes wrong.

Note: most of this post is a transliteration of an article of David Turner, "Total Functional Programming", 2004. I'm also using pieces of "Ensuring stream flows" and this blog article by @sigfpe.

Life without ⊥ (bottom)

The type Int which is used for the definition of the loop function is not as simple as it looks. It is actually Int (⊥) where ⊥ (called "bottom") a value denoting run-time errors and non-terminating programs. "Total functional programming" doesn't allow this type of values and this why it is called "Total": functions are always defined on their domain (their "input values"), they cannot return an undefined value.

Not having to deal with ⊥ has a lot of advantages:

Simpler proofs

As we've seen in the introduction, we can't really assume that (e - e = 0) when (e: Nat) without having to worry about the ⊥ case. When ⊥ is present, proof by induction can not be easily used as read in math textbooks. To refresh your memory, this proof principle states that for any property P:

if P(0)
and for all n, P(n) => P(n + 1)
then for all n, P(n)

However if you allow ⊥ to sneak in, this principle becomes a tad more complex.

Simpler language design

Arguments evaluation

With no bottom value, one divide between programming languages just disappears. We don't really care anymore about strict evaluation (as in Scheme, Scala) vs lazy evaluation (as in Haskell), the evaluation of a function doesn't depend on the evaluation of its arguments:

-- a function returning the first argument
first a b = a

-- with strict evaluation
first 1 ⊥ = ⊥

-- with lazy evaluation
first 1 ⊥ = 1

Pattern matching

But that's not the only difference, another one is pattern matching. In Haskell, when you expect a pair of values, you won't be able to match that against ⊥:

-- will not match if (a, b) is ⊥
first (a, b) = a

You can argue that this is a reasonable language decision to make but that's not the only possible one. In Miranda for instance, the match will always succeed:

-- a bottom value can be "lifted" to a pair of bottom values
(⊥a, ⊥b) = ⊥

& operator

Same thing goes with the evaluation of operators like & (logical AND). It is defined on Booleans by:

True  & True  = True
True  & False = False
False & True  = False
False & False = False

If you introduce ⊥ you have to define:

⊥ & y = ?
x & ⊥ = ?

Most of the programming languages decide to be "left-strict", i.e they evaluate the first argument before trying to evaluate the whole expression:

⊥ & y = ⊥
x & ⊥ = False if x = False
x & ⊥ = ⊥ otherwise

Again, that might seem completely obvious to us after years of using this convention, but we can imagine other alternatives (doubly-strict, right-strict, doubly-non-strict), and this breaks the classical symmetry of the & operator in mathematics.

More flexibility in language implementation

Reduction

Let's introduce a bit of programming languages theory. When you define a programming language, you need to specify:

• how to build language expressions from "atomic" blocks. For example, how to build an if expression from a boolean expression and 2 other expressions

  if booleanExpression then expression1 else expression2

• how to "execute" the language expressions, usually by specifying how to replace values in expressions with other values. For example using a specific boolean value in an if expression:

  a = true
if a then b else c => c

As you can see, executing a program means "reducing" large expressions to smaller ones, using specific rules. This raises some immediate questions:

1. can we reach a final, irreducible, expression (a normal form)?

2. if several "reduction paths" are possible (by using the reduction rules in different ways), do they converge on the same normal form?

If you can show that your programming language satisfies 2. when 1. is true, then you can say that it has the "Church-Rosser" property or it is confluent. Another version of this property, the "strong" form says that every reduction leads to a normal form and it is unique whatever reduction path you took.

Total functional programming can be called "Strong" because it has this property. The consequence is that the language implementation is free to select various evaluation strategies, for example to get better memory consumption or parallelism, without any fear for changing the program meaning.

Not all green

If Strong Functional Programming is so easy don't we all use it right now? What are the disadvantages then?

Not Turing complete

The first issue with Strong Functional Programming is that it is not Turing complete. It computes programs which always terminate but cannot compute all the programs that always terminate. In particular it can not compute its own interpreter. Why is that?

Let's say the interpreter is a function eval taking as arguments, a program P and its input I (this example comes from here). Any program is a big sequence of symbol and can be coded into a number, so our eval interpreter can be seen as a function :: (Nat, Nat) -> Nat. Based on that I can build an evil function in my total language:

evil :: Nat -> Nat
evil code = 1 + eval code code

But there is also a number corresponding to the evil program. Let's call that number 666:

-- this means "apply the evil program aka '666' to the value 666"
-- by definition of the eval interpreter
eval 666 666 = evil 666

-- but if we go back to the definition of evil
evil 666 = 1 + (eval 666 666)

-- we can't get a value for 'evil 666', because it's equivalent to the equation 0 = 1
evil 666 = 1 + evil 666

So evil is a non-terminating program of my language, which is however supposed to terminate because built from 1 and eval (a terminating program by our hypothesis) => fail.

This is a troubling conclusion. One way out is to create a hierarchy of languages where each language above has enough power to write an interpreter for the language below. And, at the top of the hierarchy, we use a Turing-complete language. This is not unsimilar to isolating a typed, functional world from a non-typed, side-effecting one (aka "the real world").

Non terminating!

Yes, by definition. But non-terminating programs are super useful, you wouldn't want your operating system stop after a few keystrokes saying "I'm done, buddy".

The good news is that we can actually deal with this situation by using codata. But before we look at codata in detail, we're going to enumerate some of the rules of an "elementary" Strong Programming Functional language (or ESFPL).

The rules for non-termination

Let's adopt a Haskell-like syntax for our ESPFL. One thing we must be able to do is to define the "usual" datatypes:

data Bool    = True | False
data Nat     = Zero | Suc Nat
data List a  = Nil  | Cons a (List a)
data Tree a  = Nilt | Node a (Tree a) (Tree a)

and some functions on those types:

-- size of a Tree
size a :: Tree a -> Nat
size Nilt = 0
size (Node a l r) = 1 + size l + size r

-- filter a List with a function
filter f Nil = Nil
filter f (Cons a rest) if (f a)  = Cons a (filter f rest)
                       otherwise = filter f rest

Rule n.1: all case analysis must be complete

This one should feel obvious to anyone having used data types and pattern matching before. If you forget a case in your pattern matching analysis, you face the risk of a runtime exception: NoMatchError.

But this rule has a larger impact. You will also have to change your "standard" library. For example you can't define the function taking the first element of a list, head, as before. You need to provide a value to use when the list is empty:

-- taking the first element of a list
head a :: List a a -> a
head Nil default           = default
head (Cons a rest) default = a

The other alternative is to program with a data type where things can't go wrong:

data NonEmptyList a = NCons a (NonEmptyList a)

-- taking the first element of a non-empty list
head a :: NonEmptyList a -> a
head (NCons a rest) = a

This kind of discipline doesn't seem so harsh, but other difficulties arise with the use of built-in arithmetic operators, starting with divide. What do you do about divide 1 0?

There are propositions to build data types where "1 / 0" is defined and equal to "1"! It looks so weird to me that I'd certainly try to go with a NonZeroNat data type before anything else.

Rule n.2: type recursion must be covariant

I like this rule because it was not obvious to me at all when I first read it. What does it mean?

1. You can define data types recursively
2. You can use functions as values

3. So you can build the following data type

   data Silly a = Very (Silly -> a)

With the Silly data type I can recurse indefinitely:

bad a :: Silly a -> a
bad (Very f) = f (Very f)

ouch :: a
ouch = bad (Very bad)

The ouch value is a non-terminating one, because the evaluation of bad will use bad itself with no case for termination. Rule n.2 is here to prohibit this. You can't define a data type with a function that use this data type as an input value. The fact that this rule was not obvious raises questions:

• how do we know that we have found all the rules for ESFP?
• is there a "minimal" set of rules?

I have no answer to those questions unfortunately :-(.

Rule n.3: recursion must be structural

The previous rule was about data type recursion, this one is about function recursion. More precisely the rule says that: "each recursive function call must be on a syntactic sub-component of its formal parameter". This means that if you make a recursive call with the function being defined, it has to be on only a part of the input data, like with the ubiquitous factorial function:

factorial :: Nat -> Nat
factorial Zero = 0
factorial (Suc Zero) = 1

-- we recurse with a sub-component of (Suc n)
factorial (Suc n)    = (Suc n) * (factorial n)

This rule is not too hard to understand. If you always recurse on data that is provably "smaller" than your input data, you can prove that your function will terminate. This rule can also accomodate the Ackermann function, which has 2 Nat parameters:

ack :: Nat Nat -> Nat
ack 0 n = n + 1

-- m + 1 is a shortcut for (Suc m)
ack (m + 1) 0       = ack m 1
ack (m + 1) (n + 1) = ack m (ack (m + 1) n)

By the way, if you don't know the Ackermann function, look it up! It has an amazing growth, with very small numbers. Try to evaluate ack 4 3 for fun :-)

How restrictive is this rule? Not so much. This rule authorizes to program:

1. "primitive recursive" functions. Those are the functions, like factorial, which are defined using only simple recursion (think how addition (Suc n) m can be defined in terms of addition n m) and by composing other primitive functions

2. other "total recursive" functions, like ack ("total" meaning "terminating" here). Indeed ack is not "primitive recursive". It was actually especially created to show that not all "total recursive" functions were "primitive recursive"

It turns out that all the functions which we can be proven to terminate by using first-order logic (without forall and exists) can be programmed with structural recursion. That's a lot of functions, but we have to change or programming practices in order to use only structural recursion. Let's look at an example.

Coding fast exponentiation

We want to code the "power" function. Here's a naive version:

pow :: Nat -> Nat ->
pow x n = 1,                   if n == 0
        = x * (pow x (n - 1)), otherwise

It is primitive recursive but not very efficient because we need n calls to get the result. We can do better than this:

pow :: Nat -> Nat -> Nat
pow x n = 1,                       if n == 0
        = x * pow (x * x) (n / 2), if odd n
        = pow (x * x) (n / 2),     otherwise

Unfortunately this version is not primitive recursive, because when we call pow we're not going from n + 1 to n. It is however obvious that we're "descending" and that this algorithm will terminate. How can we re-code this algorithm with primitive recursion?

The trick is to encode the "descent" in a data type:

-- representation of a binary digit
data Bit  = On | Off

-- we assume a built-in bits function
bits :: Nat -> List Bit

-- then the definition of pow is primitive recursive, because we descend on the Bit data type
pow :: Nat -> Nat -> Nat
pow x n = pow1 x (bits n)

pow1 :: Nat -> List Bit -> Nat
pow1 x n = 1
pow1 x (Cons On rest)  = x * (pow1 (x * x) rest)
pow1 x (Cons Off rest) = pow1 (x * x) rest

David Turner conjectures that many of our algorithms can be coded this way and for cases where it get a bit hairier (like for Euclid's gcd) we could authorize another type of recursion called "Walther's recursion". With this kind of recursion we can recognize a larger class of programs where recursion is guaranteed to terminate because we only use operations effectively "reducing" the data types (acknowledging that n / 2 is necessarily lower than n). Using "Walther's recursion" with a language having functions as first-class values is still an unsolved problem though.

Codata for "infinite" computations

After having looked at the rules for bounding recursion and avoiding non-termination, we would still like to be able to program an operating system. The key insight here is that our functions need to terminate but our data doesn't need to. For example, the Stream data type is infinite:

data Stream a = Cons a (Stream a)

In this perspective, an operating system is a bunch of functions acting on an infinite stream of input values. Let's call this type of infinite data, "codata", and see how we can keep things under control.

Here's our first definition, Colist (similar to the Stream type above):

-- "a <> Colist a" stands for "Cocons a (Colist a)"
codata Colist a = Conil | a <> Colist a

Does it breach the "Strong normalization" property that we described earlier? It doesn't if we say that every expression starting with a coconstructor is not reducable (or is in "normal form"), there is nothing which can be substituted. Whereas with a regular List you can evaluate:

Cons (1 + 2) rest = Cons 3 rest

This is why we need to have a new keyword codata to explicitly define this type of data. In a way, this is making a strong distinction between "lazy" and "strict" data, instead of using lazy evaluation to implement infinite data types.

Primitive corecursion

The equivalent of Rule n.3 for codata is that all recursion on codata must be "primitive corecursive". You have any idea of what it is? It is kind of the opposite / dual of the structural recursion for data types. Instead of proving that we always reduce the input value when making a recursive call we need to prove that we "augment" the result, by always using a "coconstructor" to create the result:

-- functions on codata must always use a coconstructor for their result
function a :: Colist a -> Colist a
function a <> rest = 'something' <> (function 'something else')

Then we can define functions like:

ones :: Colist Nat
ones = 1 <> ones

fibonacci :: Colist Nat
fibonacci = f 0 1
            where f a b = a <> (fibonacci b (a + b))

Another way of looking at the difference between data/recursion and codata/corecursion is that:

• recursion on data is safe if we break-up the data in smaller pieces then recurse on those pieces
• corecursion on codata is safe if we apply the recursion first then put that in a coconstructor which declares that we have infinite data

Codata is data which is (potentially) infinite, but observable. There are methods to safely extract results, one at the time, in a terminating way. That's exactly what the fibonacci function does. It builds a sequence of results, so that you can safely extract the first one, then you have a way to build the rest of the values.

This is why people also talk about the duality between data and codata as a duality between constructors and destructors. Or a duality between accessing the internals of a data type and observing the behavior of a codata type.

Coinductive proofs

When we try to reason about codata and corecursion, we can use coinduction (you saw that one coming didn't you :-)?). The principle of coinduction is the following:

2 pieces of codata are the same, "bisimilar" in the literature, if:

• their finite part are equal (the "a" in "a <> rest")
• their infinite part are the same

In other words, if the 2 sequences always produce the same values. Using that principle we can show the following theorem on infinite structures:

-- iterate a function: x, f x, f (f x), f (f (f x)),...
iterate f x = x <> iterate f (f x)

-- map a function on a colist
comap f Conil =  Conil
comap f a <> rest = (f a) <> (comap f rest)

Now, we'd like to show that iterate f (f x) = comap f (iterate f x):

iterate f (f x) = (f x) <> iterate f (f (f x))       -- 1. by definition of iterate
                = (f x) <> comap f (iterate f (f x)) -- 2. by hypothesis
                = comap f (x <> iterate f (f x))     -- 3. by definition of comap
                = comap f (iterate f x)              -- 4. by definition of iterate

The coinduction principle is used exactly in step 2. If "iterate f (f (f x))" and "comap f (iterate f (f x))" are the same, then adding a new value "(f x)" will preserve equality.

Limitations

The definition of "primitive corecursive" is a bit restrictive. It prevents useful, and well-founded, definitions like:

-- "evens" would need to come first after <> for this definition to be corecursive
evens = 2 <> (comap (+2) evens)

Note that we can't allow any kind of construction with "<>". For example the bad function below is not terminating:

-- infinite lists
data Colist a = a <> Colist a

-- the tail of an infinite list
cotail a :: Colist a -> Colist a
cotail a <> rest = rest

-- don't do this at home
bad = 1 <> (cotail bad)

In "Ensuring streams flow", David Turner shows that it is possible to develop an algorithm which will check where the corecursion is safe and where it isn't. The formal argument takes a few pages of explanation but the idea is simple. We need to count the "levels of guardedness":

• having evens recursing inside comap is not a problem, because comap will add a new coconstructor

• having bad recursing inside cotail is a problem, because cotail "removes" a coconstructor

So the idea of the algorithm is to count the number of times where we "add" or "remove" coconstructors to determine if the corecursion will be safe or not.

Comadness

To conclude with the presentation of codata, I want to briefly introduce comonads and give a short example to give an intuition of what it is.

If you look at the definition in the books and listen to the category theory people, you will read or hear something like: "get the monad definition, change the arrows direction and you have a comonad":

-- the comonad operations

-- the dual of return or unit for monads
extract :: W a -> a

-- the dual of bind or flatMap for monads
cobind :: W a -> b -> W a -> W b

Intuitively you can think of a comonad as:

• "I can extract things from a Context" (to contrast with the "I can put things in a context" of monads)

• If I have a function which "computes values from inputs values which might change depending on the context": W a -> b, then I can use "values in context", W a, to return other "values in context", W b

This is still not quite clear, so let's give a simple example based on Colist. Colist is a comonad which we can use like that:

-- a Colist of Nats where each new value is the previous value + 1
nats = 0 <> comap (+1) nats

-- a function taking the first 2 elements of a Colist
firstTwo a :: Colist a -> (a, a)
firstTwo a <> b <> rest = (a, b)

-- now, let's cobind firstTwo to nats
cobind firstTwo nats = (0, 1) <> (1, 2) <> (2, 3) <> ...

Sometimes you can read that List is a monad representing the fact that a function can produce non-deterministic results ("zero or many"). By analogy with the List monad, we can say that Colist is a comonad that represents the function can have non-deterministic inputs.

Conclusion

I touched on a lot of subjects with this post, for which there would be a lot to say (and certainly with less approximation that I did). In the first part we saw that, when dealing with finite data, the notions of termination, computation and recursivity and intimately related. In the second part we saw that it can be beneficial to give a special status to infinite data and to provide for it the same kind of tools (proofs with corecursion, comonads) that we usually have for data.

I hope that the subject of codata will become more and more popular (this recent proposal for a codo notation in Haskell might be a good sign). We can see a lot of architectures these days turning to "Event Sourcing". I suspect that Codata, Comonads, Costate and all the Cotypeclassopedia will prove very useful in dealing with these torrents of data.

Coming full circle

In this post I want to show a few of the upcoming features in specs2-1.9 and also take a step back on how specs2 features and implementation unfolded since I started the project one year ago.

Why would you want to rewrite from scratch?

Good question, that seems to be very masochistic :-). Not only because of the sheer amount of features to re-implement but more importantly because of the difficulty to move users to a new version.

I explained in details the reasons why I thought the rewrite was necessary, how it would benefit users and how to migrate in a previous blog post. What I want to emphasize here is the compromise I decided to make at that time:

• more concurrency and reliability
• less practicality

The main reason for this compromise was immutability. Forcing myself to immutability had opened the gates of robust and concurrent software but at the same time I had to cut back on the syntax I had proposed for the original specs1 project. For example it wasn't possible anymore to write:

    // this example can only be "registered" if there are side-effects
    "hello must have 5 letters" in {
      "hello" must have size(5)
    }
    "world must have 5 letters" in {
      "world" must have size(5)
    }

Instead, I proposed to write:

    // examples are "linked" together with the ^ operator
    "hello must have 5 letters" ! e1 ^
    "world must have 5 letters" ! e2

    def e1 = "hello" must have size(5)
    def e2 = "world" must have size(5)

The feed-back was immediate. Some developers who were sent a preview liked it but others told me: "NEVER I would use this horrible syntax". Ok, fair enough, I can't blame you, it's a bit ugly on the right.

I decided then that I would relax my constraints a little bit and add one, just one, var. It would only be used to accumulate examples when building the specification, to enable the good old specs1 style. This was also, at least partially, solving the migration problem since a full rewrite of the specifications was not necessary.

Not everything was as cool as in the original specs1 tough. In particular the super-easy "isolated" execution model was missing. Until...

Lightbulb

... Until it struck me, just one month ago, that reintroducing this mode of execution was less than 10 lines of code!

Because I had chosen the functional paradigm of "executing a Specification" <=> "interpreting a data structure" it was really easy to change the interpretation to something declaring: "for each example, execute the code in a clone of the Specification so that all local variables are seen as fresh variables".

In terms of product management, it was a "magic" feature almost for free! To me, this is the illustration of a principle of Software: "if code is a liability, maximise your return on investment".

Maximize the ROI

I'm sure you've already read something like: "features are an asset, code is a liability". But I haven't yet read the logical consequence of it: "Maximize the ROI: extract as many features as you can from your existing code". Indeed every time we write a piece of code, it's worth wondering:

• how can this be put to a better use?
• can I add something slightly different to provide a new useful feature?
• can I generalize it a bit to make sense of it in another context?
• can I make it composable with an existing feature to get a new one?

That's exactly what happened with the "isolated" feature above. Here's another example of this principle in action.

IO and serialization are not cheap

A few months ago, I developed a feature to create an index page. On this index page I had to show the status of specifications which had been executed as part of the previous run. This meant that I had to store somewhere, on the file system, the results of each specification execution.

In terms of feature price, this is not a particularly cheap one. Everytime there is some IO interaction and some kind of serialization, the number of possible issues to consider is not so small. In a way that was really an "iceberg" feature: not a lot of functionality on the surface, but a lot of machinery under the water. So I wondered how I could improve my ROI on this. Hmm... since I'm writing status information to the disk there might be a way to reuse it!

Indeed, I can use this information to selectively re-run only the failed examples, or the skipped ones, or... And so on. From there, a new "feature space" opens, and the initial investment starts making sense.

It is also possible to maximize the ROI on existing features. A feature is an "asset". Perhaps, but it's not completely free either. You have to explain it, to promote it, to show when and how it interacts with the rest of the software. This is why maximizing the ROI of features makes sense as well.

That's exactly what happened with the brand-new "isolated" feature.

All expectations

Year after year I'm looking at the specifications that people are writing with specs/specs2. Kind of my hallway usability test for open-source libraries... I usually see several "styles" of specifications and one style is pretty frequent:

    "This is an example of building/getting/processing a datastructure" >> {
       // do stuff
       val data = processBigData

       // check expectations
       data must doThis
       data must haveThat
       data.parts must beLikeThis
       // and so on...
    }

In that style of specification, there is usually one action and lots of things to check. It is very unfortunate that most of the testing libraries out there will stop at the first failure. Because it really makes sense to collect all of them at once instead of having to execute the specification multiple times to get to all the issues.

Is there a way to "collect" all the failures in specs2-1.8.2? Not really. You can try use "or" with the expectations:

       (data must doThis) or
       (data must haveThat) or
       (data.parts must beLikeThis)

And that will collect all the failures up to the first success, and then it will stop executing the rest. Besides, the "or" syntax with all the parenthesis is not so nice.

After a while I realized that the only way to make this work was to use yet another mutable variable to silently register each result. But then I'd be back to the old specs1 problem. What about concurrency? How can I prevent each concurrent example to step on another example results?

Well, that's easy, I have the "isolated" feature now! Each example can run in its own copy of the specification and the mutable variable will only collect the results from that example safely. The result is a feature that's easy to implement but also easy to use because it's just a matter of mixing a trait to the specification!

Coming full circle

Can I go further with the same thinking? Why not?!

From the beginning of specs2, I liked the fact that the so-called "Acceptance specification" style allowed me to write a lot of text about what my system behavior and then annotate it with the actual code. The price to pay was all the symbols on the right of the screen which appeared utterly cryptic to some people (to say it nicely).

Then, last week, I realized that I could rely on something which exists in most code editors: code folding! In a classical JUnit TestCase, specs1 specification or specs2 mutable specification if you fold the code, you're left with only the text, forming a narrative for your system. If you see it like that, any specs2 mutable specification can be turned into an acceptance specification, just a few features are missing:

• the ability to add an arbitrary piece of text (instead of should/in blocks) and formatting fragments (for example to give an overview of the system, before going into the details)
• given/when/then specifications
• auto-examples

Not a lot to implement really. Most of the machinery is already provided by the org.specs2.Specification trait. This means that, for a very reasonable "price", you can now use "mutable" specifications in specs2 with a great deal of expressivity (nothing's perfect though, there are small issues due to semi-column inference for example, see here for variations around the "Stack" theme).

Full circle and blurred lines

To me, it really feels that I've come full circle:

1. I rebuilt from scratch the "Specification" concept from specs1, throwing away the syntax
2. I reintroduced some mutability very carefully to get some of that syntax back
3. I built upon all the immutable code to finally end up with exactly what I would have liked to have in specs1!

My only concern now is that newcomers might feel lost because the library is not really prescribing a specific style: "should I use a 'unit' style or an 'acceptance' style? And what are the differences between the 2 anyway?". I hope that they'll realize that this is actually an opportunity. An opportunity to try out different ways of communicating and then choosing the most efficient or pleasing.

Pragmatic IO - part 3

A follow-up to my previous posts about IO.

Why types and laws matter

It's embarrassing to write post after post only to find out I keep being wrong :-). While the technique I described in my last post (using StreamT) works ok, I actually don't have to use it. The traverse technique explained in EIP works perfectly, provided that:

• we write a proper Traverse instance using foldLeft (as explained in the first part of this post)

• we trampoline the State to avoid Stack overflows due to a long chain of flatMaps during the traversal

• we use the right types!

Get the types right

That's the point I want to insist on today. Last evening I read the revisited WordCount example in Scalaz-seven which is like the canonical example of using the EIP ideas. Two words in the comments struck my mind: "compose" and "fuse". Indeed, one very important thing about EIP is the ability to compose Applicatives so that their actions should "fuse" during a traversal. As if they were executed in the same "for" loop!

So, when I wrote in my previous post that I needed to traverse the stream of lines several times to get the results, something had to be wrong somewhere. The types were wrong!

1. instead of traversing with State[S, *] where * =:= IO[B], I should traverse with State[S, IO[*]]
2. what I get back is a State[S, IO[Seq[B]]], instead of a State[S, Seq[IO[B]]
3. this matters because passing in an initial state then returns IO[Seq[B]] instead of Seq[IO[B]]

Exactly what I want, without having to sequence anything.

Use the laws

Not only I get what I want, but also it is conceptually right as the result of an important traverse law:

  traverse(f compose g) == traverse(f) compose traverse(g)

That "fusion" law guarantees that composing 2 effects can be fused, and executed in only one traversal. It's worth instantiating f and g to make that more concrete:

  // what to do with the line and line number
  def importLine(i: Int, l: String): (Int, IO[Unit]) =
    (i, storeLine(l) >>= println("imported line "+i))

  // `g` keeps track of the line number
  val g : String => State[Int, String] =
    (s: String) => state((i: Int) => (i+1, s))

  // `f` takes the current line/line number and do the import/reporting
  val f : State[Int, String] => State[Int, IO[Unit]] =
    st => state((i: Int) => importLine(st(i)))

  // `f compose g` fuses both actions
  val f_g: String => State[Int, IO[Unit]] = f compose g

I'm really glad that I was able to converge on established principles. Why couldn't I see this earlier?

Scala and Scalaz-seven might help

In retrospect, I remember what led me astray. When I realized that I had to use a State transformer with a Trampoline, I just got scared by the Applicative instance I had to provide. Its type is:

  /**
   * Here we want M1 to `Trampoline` and M2 to be `IO`
   */
  implicit def StateTMApplicative[M1[_]: Monad, S, M2[_] : Applicative] =
    Applicative.applicative[({type l[a] = StateT[M1, S, M2[a]]})#l]

I also need some Pure and Apply instances in scope:

  implicit def StateTMApply[M1[_]: Monad, S, M2[_] : Applicative] =
    new Apply[({type l[a]=StateT[M1, S, M2[a]]})#l] {
      def apply[A, B](f: StateT[M1, S, M2[A => B]], a: StateT[M1, S, M2[A]]) =
        f.flatMap(ff => a.map(aa => aa <*> ff))
    }

  implicit def StateTMPure[M1[_] : Pure, S, M2[_] : Pure] =
    new Pure[({type l[a]=StateT[M1, S, M2[a]]})#l] {
      def pure[A](a: => A) = stateT((s: S) => (s, a.pure[M2]).pure[M1])
    }

Once it's written, it may not seem so hard but I got very confused trying to get there. How can it be made easier? First, we could have better type annotations for partial type application, like:

  // notice the * instead of the "type l" trick
  implicit def StateTMApplicative[M1[_]: Monad, S, M2[_] : Applicative] =
    Applicative.applicative[StateT[M1, S, M2[*]]]

  implicit def StateTMApply[M1[_]: Monad, S, M2[_] : Applicative] =
    new Apply[StateT[M1, S, M2[*]]] {
      def apply[A, B](f: StateT[M1, S, M2[A => B]], a: StateT[M1, S, M2[A]]) =
        f.flatMap(ff => a.map(aa => aa <*> ff))
    }

  implicit def StateTMPure[M1[_] : Pure, S, M2[_] : Pure] =
    new Pure[StateT[M1, S, M2[*]]] {
      def pure[A](a: => A) = stateT((s: S) => (s, a.pure[M2]).pure[M1])
    }

And with a better type inference, the first definition could be even be (we can always dream :-)):

  implicit def StateTMApplicative[M1[_]: Monad, S, M2[_] : Applicative]:
    Applicative[StateT[M1, S, M2[*]]] = Applicative.applicative

Which means that it may even be removed, just import Applicative.applicative!

Actually Scalaz-seven might help by:

• providing those instances out-of-the box

• even better, provide combinators to create those instances easily. That's what the compose method does

• give even better type inference. Look at the traverseU method here, no type annotations Ma!

Now that the fundamentals are working ok for my application, I can go back to adding features, yay!

Pragmatic IO - part 2

A follow-up to my previous post about IO.

Learning by being wrong, very wrong

I didn't think that diving into the functional IO world would have me think so hard about how to use some FP concepts.

Mind the law

The technique I described at the end of my previous post didn't really work. It was wrong on many accounts. First of all, my
Traverse instance was buggy because I was reversing the traversed Stream. This is why I had inverted messages in the console. During the traversal, starting from the left, I needed to append each traversed element to the result, not prepend it:

  /**
   * WRONG: because each new element `b` must be appended to the result.
   * it should be bs :+ b instead
   */
  def SeqLeftTraverse: Traverse[Seq] = new Traverse[Seq] {
    def traverse[F[_]: Applicative, A, B](f: A => F[B], as: Seq[A]): F[Seq[B]] =
      as.foldl[F[Seq[B]]](Seq[B]().pure) { (ys, x) =>
        implicitly[Apply[F]].apply(f(x) map ((b: B) => (bs: Seq[B]) => b +: bs), ys)
      }
  }

It is important to mention here that proper testing should have caught this. There are some laws that applicative traversals must satisfy (see EIP, section 5. One of them is that seq.traverse(identity) == seq. This is obviously not the case when I returned a reverted sequence.

Not at the right time

Then I realized something also which was also worrying. On big files, my application would do a lot, then, report its activity to the console. This would definitely not have happened in a simple for loop with unrestricted effects!

So I set out to find a better implementation for my file reading / records saving. The solution I'm going to present here is just one way of doing it, given my way of constraining the problem. There are others, specifically the use of Iteratees.

My goal

This is what I want to do: I want to read lines from a file, transform them into "records" and store them in a database. Along the way, I want to inform the user of the progress of the task, based on the number of lines already imported.

More precisely, I want 2 classes with the following interfaces:

• the Source class is capable of reading lines and do something on each line, possibly based on some state, like the number of lines already read.
  The Source class should also be responsible for closing all the opened resources whether things go wrong or not

• the Extractor class should provide a function declaring what to do with the current line and state. Ideally it should be possible to create that function by composing independent actions: storing records in the db and / or printing messages on the console

• and, by the way, I don't want this to go out-of-memory or stack overflow at run-time just because I'm importing a big file :-)

Mind you, it took me quite a while to arrive there. In retrospect, I could have noticed that:

• all the processing has to take place inside the Source.readLines method. Otherwise there's no way to close the resources properly (well unless you're using Iteratees, what Paul Chiusano refers to as "Consumer" processing)

• the signature of the function passed to Source.readLines has to be String => State[IO[A]], meaning that for each line, we're doing an IO action (like saving it to the database) but based on a State

• the end result of readLines has to be IO[Seq[A]] which is an action returning the sequence of all the return values when all the IO actions have been performed

Considering all that, I ended up with the following signatures:

  /**
   * @param  filePath the file to read from
   * @f      a function doing an IO action for each line, based on a State
   * @init   the initial value of the State
   * @return an IO action reading all the lines and returning the sequence of computed values
   */
   def readLinesIO[S, A](filePath: String)(f: String => State[S, IO[A]])(init: S): IO[Seq[A]]

and the Extractor code goes:

  // the initial state
  val counter = new LogarithmicCounter(level = 100, scale = 10)

  // a function to notify the user when we've reached a given level
  val onLevel            = (i: Int) => printTime("imported from "+filePath+": "+i+" lines")
  // a function to create and store each line
  def onCount(l: String) = (i: Int) => createAndStoreRecord(Line(file, l), creator)

  // for each line, apply the actions described as a State[LogarithmicCounter, IO[A]] object
  readLinesIO(file.getPath)(l => counter.asState(onLevel, onCount(l)))(counter)

I like that interface because it keeps things separated and generic enough:

• reading the lines and opening/closing the resources goes to one class: Source
• defining how the state evolves when an action is done goes to the LogarithmicCounter class
• defining what to do exactly with each line goes in one class, the Extractor class

Now, the tricky implementation question is: how do you implement readLinesIO?

What not to do

Definitely the wrong way to do it is to use a "regular" traverse on the stream of input lines. Even with the trampolining trick described in my previous post.

Indeed traverse is going to fold everything once to go from Stream[String] to State[S, Seq[IO[B]]] then, with the initial State value, to Seq[IO[B]] which then has to be sequenced into IO[Seq[B]]. This is guaranteed to do more work than necessary. More than what a single for loop would do.

The other thing not to do is so silly that I'm ashamed to write it here. Ok, I'll write it. At least to avoid someone else the same idea. I had an implicit conversion from A to IO[A],...

That's a very tempting thing to do and very convenient at first glance. Whenever a function was expecting an IO[A], I could just pass a without having to write a.pure[IO]. The trouble is, some actions were never executed! I don't have a specific example to show, but I'm pretty sure that, at some point, I had values of type IO[IO[A]]. In that case, doing unsafePerformIO, i.e. "executing" the IO action only returns another action to execute and doesn't do anything really!

Learn your FP classes

I must admit I've been reluctant to go into what was advised on the Scalaz mailing-list: "go with StreamT", "use Iteratees". Really? I just want to do IO! Can I learn all that stuff later? I finally decided to go with the first option and describe it here in detail.

StreamT is a "Stream transformer". It is the Scala version of the ListT done right in Haskell. That looks a bit scary at first but it is not so hard. It is an infinite list of elements which are not values but computations. So it more or less has the type Seq[M[A]] where M is some kind of effect, like changing a State or doing IO.

My first practical question was: "how do I even build that thing from a Stream of elements?"

Unfolding a data structure

Unfolding is the way. In the Scala world we are used to "folding" data structures into elements: get the sum of the elements of a list, get the maximum element in a tree. We less often do the opposite: generate a data structure from one element and a function. One example of this is generating the list of Fibonacci numbers out of an initial pair (0, 1) and a function computing the next "Fibonacci step".

With the StreamT class in Scalaz, you do this:

  /** our record-creation function */
  def f[B]: String => M[B]

  /**
   * unfolding the initial Stream to a StreamT where we apply
   * a `State` function `f` to each element
   */
  StreamT.unfoldM[M, B, Seq[A]](seq: Seq[A]) { (ss: Seq[A]) =>
    if (ss.isEmpty)  (None: Option[(B, Seq[A])]).pure[M]
    else              f(ss.head).map((b: B) => Some((b, ss.tail)))
  }

The code above takes an initial sequence seq (the Stream of lines to read) and:

• if there are no more elements, you return None.pure[M], there's nothing left to do. In my specific use case that'll be State[LogarithmicCounter, None]

• if there is an element in the Stream, f is applied to that element, that is, we create a record from the line and store it in the database (that's the b:B parameter, which is going to be an IO action)

• because M is the State monad, when we apply f, this also computes the next state to keep track of how many rows we've imported so far

• then the rest of the stream of lines to process, ss.tail, is also returned and unfoldM will use that to compute the next "unfolding" step

One very important thing to notice here is that we haven't consumed any element at that stage. We've only declared what we plan to do with each element of the input stream.

Running the StreamT

In the StreamT object in Scalaz there is this method call runStreamT taking in:

• a StreamT[State[S, *], A], so that's a StreamT where the state may change with each element of the Stream
• an initial state s0
• and returning a StreamT[Id, A]

Note: State[S, *] is a non-existing notation for ({type l[a]=State[S, a]})#l

That doesn't see to be game-changing, but this does a useful thing for us. runStreamT "threads" the State through all elements, starting with the initial value. In our case that means that we're going to create IO actions, where each created action depends on the current state (the number of lines read so far).

The cool thing is that so far we've described transformations to apply: Stream[String] to StreamT[State, IO[B]] to StreamT[Id, IO[B]] but we still haven't executed anything!

UnsafePerformIO at last

Then, I coded an unsafePerformIO method specialized for Stream[Id, IO[A]] to execute all the IO actions. The method itself is not difficult to write but we need to make sure it's tail-recursive:

  /** execute all the IO actions on a StreamT when it only contains IO actions */
  def unsafePerformIO: Seq[A] = toSeq(streamT, Seq[A]())

  /**
   * execute a StreamT containing `IO` actions.
   *
   * Each IO action is executed and the result goes into a list of results
   */
  @tailrec
  private def toSeq[A](streamT: StreamT[Id, IO[A]], result: Seq[A]): Seq[A] =
    streamT.uncons match {
      case Some((head, tail)) => toSeq(tail, result :+ head.unsafePerformIO)
      case None               => result
    }

Hidding everything under the rug

Let's assemble the pieces of the puzzle now. With an implicit conversion, it is possible to transform any Seq to a StreamT performing some action on its elements:

   /**
    * for this to work, M[_] has to be a "PointedFunctor", i.e. have "pure" and
    * "fmap" methods. It is implemented using the `unfoldM` method code seen above
    */
   seq.toStreamT(f: A => M[B]): StreamT[M, B]

Then, we can traverse a whole sequence with a composition of a State and IO actions:

   seq.traverseStateIO(f)

Where traverseStateIO is using the toStreamT transformation and is defined as:

  /**
   * traverse a stream with a State and IO actions by using a Stream transformer
   */
  def traverseStateIO[S, B](f: A => State[S, IO[B]])(init: S): Seq[B] =
    StreamT.runStreamT(seq.toStreamT[State[S, *], IO[B]](f), init).unsafePerformIO

[you'll get bonus points for anyone providing a Traverse[Stream] instance based on StreamT - if that exists]

Finally the Source.readLines method is implemented as:

  /**
   * this method reads the lines of a file and apply stateful actions.
   * @return an IO action doing all the reading and return a value for each processed line
   */
  def readLinesIO[S, A](path: String)(f: String => State[S, IO[A]])(init: S): IO[Seq[A]] =
    readLines(path)(f)(init).pure[IO]

  private
  def readLines[S, A](path: String)(f: String => State[S, IO[A]])(init: S): Seq[A] = {
    // store the opened resource
    var source: Option[scala.io.Source] = None
    def getSourceLines(src: scala.io.Source) = { source = Some(src); getLines(src) }

    try {
      // read the lines and execute the actions
      getSourceLines(fromFile(path)).toSeq.traverseStateIO(f)(init)
    } finally { sources.map(_.close()) }
  }

And the client code, the Extractor class does:

  val counter = new LogarithmicCounter(level = 100, scale = 10)

  // notify the user when we've reached a given level
  val onLevel            = (i: Int) => printTime("imported from "+filePath+": "+i+" lines")
  // create and store a record for each new line
  def onCount(l: String) = (i: Int) => createAndStoreRecord(Line(file, l), creator)

  // an `IO` action doing the extraction
  readLinesIO(file.getPath)(l => counter.asState(onLevel, onCount(l)))(counter)

Conclusion

I've had more than one WTF moment when trying to mix-in State, IO and resources management together. I've been very tempted to go back to vars and unrestricted effects :-).

Yet, I got to learn useful abstractions like StreamT and I've seen that it was indeed possible to define generic, composable and functional interfaces between components. I also got the impression that there lots of different situations where we are manually passing state around which is error-prone and which can be done generically by traverse-like methods.

Pragmatic IO

This post is my exploration of the use of the IO type in a small Scala application.

A short IO introduction

Scala is a pragmatic language when you start learning Functional Programming (FP). Indeed there are some times when you can't apply the proper FP techniques just because you don't know them yet. In those cases you can still resort to variables and side-effects to your heart's content. One of these situations is IO (input/output).

Let's take an example: you need to save data in a database (not a rare thing :-)). The signature of your method will certainly look like that:

  /** @return the unique database id of the saved user */
  def save(user: User): Int

This method is not referentially transparent since it changes the state of the "outside world": if you call it twice, you'll get a different result. This kind of thing is very troubling for a Functional Programmer, that doesn't make him sleep well at night. And anyway, in a language like Haskell, where each function is pure you can't implement it. So how do you do?

The neat trick is to return an action saying "I'm going to save the user" instead of actually saving it:

  def save(user: User): IO[Int]

At first, it seems difficult to do anything from there because we just have an IO[Int], not a real Int. If we want to display the result on the screen, what do we do?

We use IO as a Monad, with the flatMap operation, to sequence the 2 actions, into a new one:

  /** create an IO action to print a line on the screen */
  def printLine(line: Any): IO[Unit] = println(line).pure[IO]

  /** save a user and print the new id on the screen */
                                           // or save(user) >>= printLine
  def saveAndPrint(user: User): IO[Unit] = save(user).flatMap(id => printLine(id))

Then finally when we want to execute the actions for real, we call unsafePerformIO in the main method:

  def main(args: Array[String]) {
    saveAndPrint(User("Eric")).unsafePerformIO
  }

That's more or less the Haskell way to do IO in Scala but nothing forces us to do so. The natural question which arises is: what should we do?

IO or not IO

Before starting this experiment, I fully re-read this thread on the Scala mailing-list, and the answer is not clear for many people apparently. Martin Odersky doesn't seemed convinced that this is the way to go. He thinks that there should be a more lightweight and polymorphic way to get effect checking and Bob Harper doesn't see the point.

Surely the best way to form my own judgement was to try it out by myself (as encouraged by Runar). One thing I know for sure is that, the moment I started printing out files in specs2, I got an uneasy feeling that something could/would go wrong. Since then,
IO has been on my radar of things to try out.

Luckily, these days, I'm developing an application which is just the perfect candidate for that. This application:

• reads log files
• stores the records in a MongoDB database
• creates graphs to analyze the data (maximums, average, distribution of some variables)

Perfect but,... where do I start :-)?

Theory => Practice

That was indeed my first question. Even in a small Swing application like mine the effects were interleaved in many places:

• when I opened the MongoDB connection, I was printing some messages on the application console to inform the user about the db name, the MongoDB version,...
• the class responsible for creating the reports was fetching its own data, effectively doing IO
• datastore queries are cached, and getting some records (an IO action) required to get other data (the date of the latest import, another IO action) to decide if we could reuse the cached ones instead

The other obvious question was: "where do I call unsafePerformIO?". This in an interactive application, I can't put just one
unsafePerformIO in the main method!

The last question was: "OMG, I started to put IO in a few places, now it's eating all of my application, what can I do?" :-))

Segregating the effects

Here's what I ended up doing. First of all let's draw a diagram of the main components of my application before refactoring:

   +-------+    extract/getReport       +------ IO +   store      +------ IO +
   + Gui   + <------------------------> + Process  + -----------> + Store    +
   +-------+     Query/LogReport        +----------+              +----------+
                                             | getReport               ^
                                             v                         |
                                        +------ IO +     getRecords    |
                                        + Reports  + ------------------+
                                        +----------+

Simple app, I told you.

The first issue was that the Reports class (actually a bit more than just one class) was fetching records and building reports at the same time. So if I decided to put IO types on the store I would drag them in any subsequent transformation (marked as IO on the diagram).

The next issue was that the Process class was also doing too much: reading files and storing records.

Those 2 things led me to this refactoring and "architectural" decision, IO annotations would only happen on the middle layer:

                                        +------- IO +            store
                               read     + Extractor + -----------------------------+
                               files    +-----------+          |                   |
                                             ^                 |                   |
                                             | extract         v                   v
   +-------+    extract/getReport       +----------+      +------ IO +        +----------+
   + Gui   + <------------------------> + Process  +      + Status   +        + Store    +
   +-------+     Query/LogReport        +----------+      +----------+        +----------+
                                             | getReport       ^                   ^
                                             v                 |                   |
                                        +------ IO +           |    getRecords     |
                                        + Reporter + ------------------------------+
                                        +----------+
                                             | createReport
                                             v
                                        +----------+
                                        + Reports  +
                                        +----------+

• all the IO actions are being segregrated to special classes. For example extracting lines for log files creates a big composite IO action to read the lines, to store the lines as a record and to report the status of the extraction. This is handled by the Extractor class

• the Status class handles all the printing on the the console. It provides methods like:

    /**
     * print a message with a timestamp, execute an action,
     * and print an end message with a timestamp also.
     *
     * This method used by the `Extractor`, `Reporter` and `Process` classes.
     */
     def statusIO[T](before: String, action: IO[T], after: String): IO[T]`
  

• the Reports class only deals with the aggregation of data from records coming from the Store. However it is completely ignorant of this fact, so testing becomes easier (true story, that really helped!)

• the Store does not have any IO type. In that sense my approach is not very pure, since nothing prevents "someone" from directly calling the store from the middle layer without encapsulating the call in an IO action. I might argue that this is pragmatic. Instead of sprinkling IO everywhere I started by defining a layer isolating the IO world (the data store, the file system) from the non-IO world (the reports, the GUI. Then, if I want, I can extend the IO marking the rest of the application if I want to. That being said I didn't do it because I didn't really see the added-value at that stage. A name for this approach could be "gradual effecting" (the equivalent of "gradual typing")

• the Process class is not marked as IO because all the methods provided by that class are actually calling
  unsafePerformIO to really execute the actions. This is the only place in the application where this kind of call occurs and the GUI layer could be left unchanged

All of that was not too hard, but was not a walk in the park either. Some details of the implementation were hard to come up with.

Under the bonnet: syntactic tricks

First of all, what was easy?

"Monadic" sequencing

Sequencing IO actions is indeed easy. I've used the for comprehension:

  def statusIO[T](before: String, action: IO[T], after: String): IO[T] = {
    for {
      _      <- printTime(before)
      result <- action
      _      <- printTime(after)
    } yield result
  }

"Semi-column" sequencing

But also the >>=| operator in Scalaz to just sequence 2 actions when you don't care about the first one:

  def statusIO[T](before: String)(action: IO[T]): IO[T] = printTime(before) >>=| action

"Conditional" sequencing

And, for the fun of it, I implemented a "conditional flatMap operator", >>=?:

  action1 >>=? (condition, action2)

In the code above the action1 is executed and, if the condition is true, we execute action2 and forget about the result of action1, otherwise we keep the result of action1.

"if else" with a twist

Not completely related to IO I also liked the ?? operator. Say I want to execute an action only if a file exists:

   if (file.exists) createRecords(file)
   else             ()

The else line really feels ugly. This kind of "default value" should be inferred from somewhere. Indeed! This "default value" is the Zero of a given type in Scalaz, so it is possible to write:

   file.exists ?? createRecords(file)

It just works (tm) but it's worth knowing where that zero values really comes from:

1. createRecords(file) returns IO[Int] (the last created id - that's a simplification of the real program)

2. there is a way to create a Monoid from another Monoid + an Applicative:

   // from scalaz.Monoid
   /** A monoid for sequencing Applicative effects. */
   def liftMonoid[F[_], M](implicit m: Monoid[M], a: Applicative[F]): Monoid[F[M]] =
     new Monoid[F[M]] {
       val zero: F[M] = a.pure(m.zero)
       def append(x: F[M], y: => F[M]): F[M] =
         a.liftA2(x, y, (m1: M, m2: M) => m.append(m1, m2))
     }
   

3. in this case IO has an Applicative, M is Int so it has a Monoid hence IO[Int] defines a Monoid where the zero is IO(0). I had to open up the debugger to check that precisely :-)

Under the bonnet: it just works,... not

The next piece of implementation I was really happy with was the "logarithmic reporting". This is a feature I implemented using vars at first, which I wanted to make pure in my quest for IO.

What I want is to extract log lines and notify the user when a bunch of lines have been imported (so that he doesn't get too bored). But I don't know how many lines there are in a given file. It could be 100 but it could be 30.000 or 100.000. So I thought that a "logarithmic" counter would be nice. With that counter, I notify the user every 100, 1000, 10.000, 100.000 lines.

The LogarithmicCounter works by creating a State object encapsulating 2 actions to do, one on each tick, one when a
level is reached:

    // create and store a line on each `tick`
    def onCount(line: String) = (i: Int) => createAndStoreRecord(line, creator)

    // and notify the user when we've reached a given level
    val onLevel = (i: Int) => printTime("imported from "+filePath+": "+i+" lines")

    /** @return a State[LogarithmicCounter, IO[Unit]] */
    val readLine = (line: String) => counter.asState(onLevel, onCount(line))

The readLine method is used in a traversal of the lines returned by a FileReader:

    (lines traverseState readLine): State[LogarithmicCounter, Stream[IO[Unit]]]

Pass it an initial counter and you get back a Stream of IO actions which you can then sequence to get an IO[Stream[Unit]]:

    // initial traversal with a function returning a `State`
    val traversed: State[LogarithmicCounter, Stream[IO[Unit]]] = lines traverseState readLine

    // feed in the initial values: count = 1, level = 100 to get the end `State`
    val traversedEndState: Stream[IO[Unit]] = traversed ! new LogarithmicCounter

    // finally get a global action which will execute a stream of
    // record-storing actions and printing actions
    val toStore: IO[Stream[Unit]] = traversedEndState.sequence

Some readers of this blog may recognize one usage of the Essence of the Iterator Pattern - EIP and that's indeed what it is (my first real use case, yes!). traverseState is just a way to use the more traditional traverse method but hiding the ugly type annotations.

This kind of type-directed development is nice. You add some type here and there and you let the compiler guide you to which method to apply in order to get the desired results:

1. after the traversal I get back a State
2. if I want to get the final state, the Stream of IO, I need to feed in some initial values, that's the '!' method
3. if I want to get an action equivalent to the stream of actions, I need the sequence method which has exactly the type signature doing what I want

I was about to call it a day when I actually tried my application,... StackOverflow! What?!?

Trampolining to the rescue

It turns out that traversing a "big" sequence with a State is not so easy. First of all, State is an Applicative because it is also a Monad (please read the earlier EIP post for the details). So basically this amounts to chaining a lot of flatMap operations which blows up the stack.

Fortunately for me, Runar has implemented a generic solution for this kind of issue, like, less than 2 months ago! I leave you to his excellent post for a detailed explanation but the gist of it is to use continuations to describe computations and store them on the heap instead of letting calls happen on the stack. So instead of using State[S, A] I use StateT[Trampoline, S, A] where each computation (S, A) returned by the State monad is actually encapsulated in a Trampoline to be executed on the heap.

The application of this idea was not too easy at first and Runar helped me with a code snippet (thanks!). Eventually I managed to keep everything well hidden behind the traverseState function. The first thing I did was to "trampoline" the function passed to traverseState:

  /**
   * transform a function into its "trampolined" version
   * val f:             T => State[S, A]              = (t: T) => State[S, A]
   * val f_trampolined: T => StateT[Trampoline, S, A] = f.trampolined
   */
  implicit def liftToTrampoline[T, S, A](f: T => State[S, A]) = new LiftToTrampoline(f)

  class LiftToTrampoline[T, S, A](f: T => State[S, A]) {
    def trampolined = (t: T) => stateT((s: S) => suspend(st.apply(s)))
  }

So the traverseState function definition becomes:

  // with the full ugly type annotation
  def traverseState(f: T => State[S, B]) =
    seq.traverse[({type l[a]=StateT[Trampoline, S, a]})#l, B](f.trampolined)

However I can't leave things that like that because traverseState then returns a StateT[Trampoline, S, B] when the client of the function expects a State[S, B]. So I added an untrampolined method to recover a State from a "trampolined" one:

  /** @return a normal State from a "trampolined" one */
  implicit def fromTrampoline[S, A](st: StateT[Trampoline, S, A]) = new FromTrampoline(st)

  class FromTrampoline[S, A](st: StateT[Trampoline, S, A]) {
    def untrampolined: State[S, A] = state((s: S) => st(s).run)
  }

The end result is not so bad. The "trampoline" trick is hidden as an implementation detail and I don't get StackOverflows anymore. Really? Not really,...

The subtleties of foldRight and foldLeft

I was still getting a StackOverflow error but not in the same place as before (#&$^@!!!). It was in the traversal function itself, not in the chaining of flatMaps. The reason for that one was that the Traverse instance for a Stream in Scalaz is using foldRight (or foldr):

  implicit def StreamTraverse: Traverse[Stream] = new Traverse[Stream] {
    def traverse[F[_]: Applicative, A, B](f: A => F[B], as: Stream[A]): F[Stream[B]] =
      as.foldr[F[Stream[B]]](Stream.empty.pure) { (x, ys) =>
        implicitly[Apply[F]].apply(f(x) map ((a: B) => (b: Stream[B]) => a #:: b), ys)
      }
  }

and foldr is recursively intensive. It basically says: foldRight(n) = f(n, foldRight(n-1)) whereas foldl is implemented with a for loop and a variable to accumulate the result.

The workaround for this situation is simple: just provide a Traverse instance using foldLeft. But then you can wonder: "why is traverse even using foldRight in the first place?". The answer is in my next bug! After doing the modifications above I didn't get a SOE anymore but the output in the console was like:

  imported from test.log: 10000 lines [12:33:30]
  imported from test.log: 1000 lines  [12:33:30]
  imported from test.log: 100 lines   [12:33:30]

Cool, I have invented a Time Machine, Marty! That one left me puzzled for a while but I found the solution if not the explanation. The "left-folding" Traverse instance I had left in scope was being used by the sequence method to transform a Stream[IO] into an IO[Stream]. Changing that to the standard "right-folding" behaviour for a Stream traversal was ok. So there is a difference (meaning that something is not associative somewhere,...)

Conclusion

The main conclusion from this experiment is that tagging methods with IO made me really think about where are the effects of my application. It also encouraged functional programming techniques such as traverse, sequence and al.

I must however say that I was surprised on more than one account:

• I stumbled upon a whole new class of bugs: non-execution. My effects were not executed improperly, they were not executed at all because I forgot to call unsafePerformIO!

• I was not expecting to be needing an optimisation which had just been added to Scalaz, for something which I thought was a casual traversal

• there are still some FP mysteries to me. For example I don't know yet how to traverse a full Stream

• I also don't get why my messages were inverted on the console. I tried different experiments, with a Seq instead of a Stream, with Identity or Option as an Applicative instead of IO and I could only reproduce this specific behavior with Stream and IO

Anyway, I would say that it was overall worth using the IO type, at least for the architectural clarification and the better testing. It also brought back the warm, fuzzy feeling that things are under control. On the other hand refactoring to IO took me longer than expected and required more knowledge than just using vars and regular I/O. But that should really be accounted for in the 'investment for the future' column.

PS

There are certainly many stones left unturned in that post for programmers new to Functional Programming and Scalaz. I do apologize for that (this post is certainly long enough :-)) and I encourage those readers to ask questions on the Scalaz mailing-list.