Having Fun with Monoid in Scalaz Seven

It's been some times since my last blog on Scalaz Seven that talks about Functor. You may have guessed that my second post on the series would be Applicative Functor. Well, sorry, I can't write in order yet, I prefer to talk about Monoid in Scalaz Seven instead. OK Let's have fun.

Having Fun With |+|

To start with, let's have some fun with |+| operator.

Let's start

scala> 6 |+| 7

res0: Int = 13

Well, not that interesting. It's just an addition. What about

scala> 6 + "9"

res2: String = 69

scala> 6 |+| "9"

<console>:14: error: type mismatch;

 found   : java.lang.String("9")

 required: Int

       6 |+| "9"

Not bad. |+| somehow protects you from adding integer to String. OK, not bad, but, not that fun. What about this:


scala> some(6) |+| some(9)
res9: Option[Int] = Some(15)

All right, that starts to be interesting. Give me more:

scala> some(6) |+| some(9) |+| some(10)
res10: Option[Int] = Some(25)


scala> some(6) |+| some(9) |+| some(10) |+| none[Int] |+| some(6)
res11: Option[Int] = Some(31)

Not bad at all. Want something more than that. Some String ?

scala> "Hello" |+| "World"

res25: java.lang.String = HelloWorld

scala> some("Hello") |+| some("World")

res26: java.lang.String = Some(HelloWorld)


What else do you have ? List ?


scala> List(2,4) |+| List(4, 5)
res28: List[Int] = List(2, 4, 4,5)

Cool. Boolean?


scala> val b = true
b: Boolean = true


scala> val c = true
c: Boolean = true


scala> b |+| c
<console>:24: error: value |+| is not a member of Boolean
       b |+| c
         ^

Ouch. Why ? Well, because |+| can be interpreted in conjunction or disjunction (note that, actually this works in Scalaz 6, not sure if scalaz seven will make it work as in scalaz 6). To fix this, let's do the following:


scala> val a = Conjunction(true)
a: scalaz.package.@@[Boolean,scalaz.Tags.Conjunction] = true


scala> val b = Conjunction(true)
b: scalaz.package.@@[Boolean,scalaz.Tags.Conjunction] = true


scala> val c = Conjunction(false)
c: scalaz.package.@@[Boolean,scalaz.Tags.Conjunction] = false


scala> a |+| b
res34: scalaz.package.@@[Boolean,scalaz.Tags.Conjunction] = true


scala> a |+| c
res35: scalaz.package.@@[Boolean,scalaz.Tags.Conjunction] = false


scala> a |+| b |+| c
res36: scalaz.package.@@[Boolean,scalaz.Tags.Conjunction] = false

All right. That makes sense. What about Disjunction ? Well, just do the same.

scala> val e = Disjunction(true)
e: scalaz.package.@@[Boolean,scalaz.Tags.Disjunction] = true


scala> val f = Disjunction(true)
f: scalaz.package.@@[Boolean,scalaz.Tags.Disjunction] = true


scala> val g = Disjunction(false)
g: scalaz.package.@@[Boolean,scalaz.Tags.Disjunction] = false


scala> val h = Disjunction(false)
h: scalaz.package.@@[Boolean,scalaz.Tags.Disjunction] = false


scala> e |+| f
res37: scalaz.package.@@[Boolean,scalaz.Tags.Disjunction] = true


scala> e |+| h
res38: scalaz.package.@@[Boolean,scalaz.Tags.Disjunction] = true


scala> g |+| h
res39: scalaz.package.@@[Boolean,scalaz.Tags.Disjunction] = false

OK. That's cool, but it starts to be boring. Doesn't it? Give me something more spectacular.  What about Tuple?  All right, what about Tuple?

scala> (6, "Hello", List(4, 2)) |+| (7, "Hello", List(5))
res40: (Int, java.lang.String, List[Int]) = (13,HelloHello,List(4, 2, 5))

So, |+| actually "sums" each corresponding element of two tuples. That's quite cool. What if they are nested? Will it work ?

scala> (some(6), some("Hello"), (some(5), some(3))) |+| 
        (some(7), none[String], (some(6), none[Int]))

res43: (Option[Int], Option[java.lang.String], (Option[Int], Option[Int])) = 

(Some(13),Some(Hello),(Some(11), Some(3)))


Fantastic! Pretty cool.

[ I heard somebody there "you see, this Scalaz guy loves using funny operator. This time, they use |+|. OMG, That's not readable". All right, all right. You can actually change all |+| above with its alias called mappend, hope you're happier now].

Monoid and Semigroup Behind the Scene


Behind the scene, what happen is that Scalaz offers a quite simple but powerful abstraction, called Monoid. Believe me, Monoid is something quite simple: it's a type class with two functions: append and zero: 

1     
2      trait Monoid[A] { 
3        val zero: A 
4        def append(s1 : A, s2 : => A):A
5      } 

With the following contract (or a law, if you wish)


zero append x = x
x append zero = x
(x append y) append z = x append (y append z)


Scalaz provides several instances of Monoid (we have seen some of them in action above):

• Int, Short, BigInt, BigDecimal, Byte, Short ...
• Boolean conjunction and disjunction
• List and Stream
• String
• Either.LeftProjection and Either.RightProjection.
• ...

What about Option and Tuple ? Actually, Scalaz also provides some derived Monoid, like:

• Option[A] is a monoid if A is monoid 
• Tuple[A, B, C, D] is a monoid if A, B, C, and D is monoid
• Map [A,B] is a monoid if B is a monoid
• ...

Map is an interesting example. Let's try this:

scala> val m = Map("UO" -> BigDecimal(40.2),

     |              "US" -> BigDecimal(50.1),

     |              "YR" -> BigDecimal(10.1))

scala> val n = Map("UO" -> BigDecimal(10.2),

     |              "US" -> BigDecimal(40.0),

     |              "YZ" -> BigDecimal(10.5))

scala> m |+| n

res47: scala.collection.immutable.Map[java.lang.String,scala.math.BigDecimal] = Map(UO -> 50.4, US -

> 90.1, YZ -> 10.5, YR -> 10.1)

As you can see, |+| adds every corresponding element in m and n. If there's no corresponding element, for example "YR" in m and "YZ" in n, then it just puts the element in the result map.

All examples so far use append function of Monoid, but not zero. A type class with only append is called Semigroup. The function zero is useful when we want to fold a list of monoid, for example using suml function also provided by scalaz:

scala> val xs = List(some(2,4), some(1, 3), some(2, 10))

xs: List[Option[(Int, Int)]] = List(Some((2,4)), Some((1,3)), Some((2,10)))

scala> xs.suml

res48: Option[(Int, Int)] = Some((5,17))

Conclusion
Scalaz provides a cool thing called Semigroup and Monoid. With that, we can benefit the operator |+| and sum for their instances like Integer, String, List, and so on. But the main benefit is that Scalaz provides implementation of Monoid for Option, Tuple, and Map. You don't need to know what Monoid or Semigroup are to benefit all this. But, why should you avoid them ? It's a very simple stuff.

I hope you enjoy this very express introduction to Scalaz Seven Monoid. Who said Scalaz is complex ?
 I'm preparing more on this subject. So, stay tuned.

Gatling Tool at Riviera Scala Clojure

This evening, at Riviera Scala Clojure, we received Stéphane Landelle and Romain Sertelon, Gatling Tools developers.

It's been quite some times I look for stress test tool that is intended for developers, instead of testers. You know, soemething like Caliper, but for stress tests.For a simple reason, I would like to profile my application and identify the problem on the load before even going to QA testing. Profiling can be done using a tool like Yourkit. But for load test, I haven't found anything convincing.

Of course, I used JMeter in the past. But I really want to have something that can be coded, but stays simple. JMeter, well...., it's  not that.

So, Gatling caught my attention. It has already caught my attention since Stéphane mentioned it in Paris Scala User Group mailing list back in December. So, here they are,  presenting the product in front of Riviera Scala Clojure group.

Performance, DSL, and Reporting
One thing that makes Gatling different is its performance. The performance of Gatling is claimed to be superior than JMeter. This is because Gatling uses Akka and AsyncHttp that allow optimization of concurrent execution of scenarios. The argument really makes sense to me, and I would really love to see it in real. Check their wiki to see the performance benchmark compared to JMeter: https://github.com/excilys/gatling/wiki/Benchmarks

The second important point in Gatling is DSL. The DSL is intended to allow programmatic scenario to be expressed easily. DSL in Gatling,  is nothing more than a fluent API, so, no need to worry, it's Scala. Check here to see the examples of the API.

You may notice that the API is quite simple -- maybe too simple? I found the DSL too imperative, but maybe this is a pragmatic choice by Gatling developer. I would have preferred the DSL to be a little bit more functional with use of pattern matching, partial function, and function composition, and other functional programming concepts instead of sequencing, the use of doIf, and loop.

The reporting is actually an interesting part of Gatling. Unfortunately, we were not lucky enough to have a full blown presentation on it, only an after presentation discussion.

Conclusion 
Gatling is an interesting tool to see if you"re interested in having a lightweight load test tool  like me. Its performance benchmark is quite promising. I have had a look at the codes, played with it, and it looks quite promising. The wiki page contains quite extensive information. But, I give you a puzzle: please find me in the wiki a scala file that shows the scenario example. Go ahead, if you can find it in 30 minutes, you're better than I am :-)

Against SOPA.

To show my support all protest movements against SOPA, I close for today my blog. Will be back tomorrow.

On 2011 and 2012

The good things

Joining Amadeus is the best thing that happened to me this year. It was a little bit complicated, but I'm happy that it's finally done. The travel industry has a lot of  very very interesting applications of computer science. And what's better than joining the leader in the field ?


Needless to say, however, that the rest of the blog content will be all mines, not my employer.

When I started the year 2011, I had used Scala for a year, mainly for my  part-time master degree. 2012 is then my second year only with Scala. I introduced Scala two times this year, one for Amadeus and the other was for SII. In both occasions, the public showed strong interests in this language. Scala in Depth is the new book on Scala I read this year(well, the only one, actually). It's an interesting book, and can't wait to read the final version.

I started learning Clojure also in 2010 using Stuart Halloway, Programming in Clojure. But in 2011, reading The Joy of Clojure and Clojure in Action brought me to better understanding of this very interesting language. Clojure has also a very interesting community, many of them are very intelligent. Most of all, Clojure community do not seem to care on whether or not they become Java killer or Java replacements. In this regard, compared to Scala community, they are cooler.

What to say about Haskell? Simply the best mainstream language exist out there. Compared to 2010, I read a lot of papers on Haskell. And what superlative to be used to describe Monad Reader? Simply the best.

If there is only one conference I would like to attend, I would name "Strange Loop". I read almost all slides, check almost all videos that made online. Of course, I didn't miss the best presentation of the year for me, which is Rich Hickey's Simple Made Easy. It's really my dream to be able to attend the conference some day.

Participating in organization of RivieraDev conference is another interesting moment. It's a small conference with a quality comparable to bigger European conferences. I loved the high and low, non stop thinking about the contents and the corresponding speakers were very interesting experience. Would love to do it again in 2012.

This year, I also started to be interested in machine learning . I started with Mahout in Action, followed by Machine Learning in Action, two excellent books from Manning. I also read Collective Intelligence in Action and Algorithms of Intelligent Web, also from Manning. Finally, without surprise, I've also finished Standford ML-Class. That was an excellent class and surely will help me better understand the subject. If you didn't attend this class, please do for the next term.

Finally, with Nicolas Bousquet and Tobo Atchou, we manage to found the long-term project of organizing user group around Scala and e. We named it Riviera Scala Clojure, following the name pattern given by Riviera Ruby and Riviera User Group. I love this group, and am optimistic on its future.

The bad things

If I have to mention one bad thing this year, it would be a repetitive attack against Scala. Some of them were really unfounded. I really wonder why Scala had such difficult moments this year. Maybe this is because there are more and more developers use Scala and they expect to have the same supports as Java. Or maybe, because functional programming is indeed not an easy thing to understand. Well, I found that the Scala leaders (Typesafe, for example) have reacted quite positively.

Other thing that I regret is that I didn't manage to go to either Devoxx or Fosdem, two European interesting conferences. Not to mention Scala Days 2011 that was not in Europe.

I also regret the fact that I didn't manage to learn more on distributed systems like Hadoop, Spark, and two interesting projects that address BSP like Apache Giraph and Hama. I didn't really have enough time to learn those interesting things. I would say that, put aside Mahout, I didn't really add my knowledge on Hadoop (and its ecosystem) from what I have learned in 2010.

Somewhere in October, I was in nostalgic mode, and started re-learn Prolog. Unfortunately, it was very quickly abandoned due to also the lack of time.

2012
I would like to "make a comeback" to Hadoop  and Lucene  world :-). I will start my personal project around Lucene starting this year. I also hope that the project can benefit something from Spark and/or Mahout.

Indeed, I think I will do a lot of things around text processing, machine learning, and all those things. Without surprise, I will register to Standford NLP and PGM classes.

I also expect that in 2012, I'll learn a lot on building distributed system. That's why I will put some efforts on Akka's world, or Actor's world in general. This includes of course Erlang. Yes, I would like to seriously learn Erlang in 2012.

I've learned functional programming a lot from Haskell and Clojure --  in addition to Scala. I plan to learn Erlang, and to complete the figure of functional programming, I would like to learn OCaml, one of the most important language in functional programming.

That said, of course,  Scala, Clojure, Haskell, and yes: Java (I still love my aging Java) will be my main concerns in 2012.

If I manage to have everything in time, I will attend Scala Days 2012. Hopefully on or two other meetings in Scala/Clojure in Europe, and why not participating in French Scala Days organization or something similar? (If you plan to organize one and look for volunteers, you know who to contact :-)

Riviera Scala Clojure will make sure that I consume my free time.  I hope the group to become bigger and will give significant contribution to Scala or Clojure community in general.

Happy new year !

Scalaz Seven Functor Feels like Seven Samurai

Jason Zaugg and all his scalaz folks are working on scalaz seven at the moment. Although they have started quite a couple of times ago, I only had a chance to play with the library only today.

In case you don't know scalaz, it's actually a popular but often misunderstood library written in scala. It's not haskell standard library ported to scala, but it's highly inspired by the haskell standard library though. I recommend you to have a look here scalaz . One recommendation: take your time, don't be hurry to understand, otherwise you will end up associate scalaz to banana [1], to rabbit [2], or to ejb2 [3]. Of course, scalaz is not ready for production, because you know ... you cannot persist a scalaz object using Hibernate.

I start with one of the simplest scalaz type class, called Functor. It sounds scarry, right ? Don't worry, think of Functor as a way to lift a function that maps A to B to something that map "container" of A to "container" of B. If you have a function that maps, from int to int, say, a functor allows mapping from List of integer to a list of integer by mapping each element of the list.

Say, you have a function incr:

val incr:Int=>Int= x => x + 1

a Functor[List] allows you to map every element in a list using that function like this:

val xs = List(5, 6, 7)

Functor[List].map(xs, incr)   // 6, 7, 8

Well, yeah, is that all? No ! I can also have this:

val eitX:Either[String, Int] = Right(6)

val eitY:Either[String, Int] = Left("Err")

Functor[Either].map(eitX, incr) // Right(7)

Functor[Either].map(eitY, incr) // Left("Err")

It starts to be interesting right, because you don't have map for Either in Scala standard library. Fine, is it great ?  No, it sucks. Function[Either] or Function[List] suck. We don't want it. Fortunately, scalaz comes wi th some magics that simplify the thing

(wait a minute? Scalaz ? Simplifies something? You must be kidding ?)

With the super complex highly intelligent Scalaz (as it is perceived  by many), indeed life is simpler, we can directly write:

val eitX:Either[String, Int] = Right(6)

val eitY:Either[String, Int] = Left("Err")

eitX.map(incr)             // Right(7)
eitY.map(incr)             // Left("Err")

That works, because Either, List, Option are instances of Functor (you know, the container that allows you to lift a function).

Is that all ? No. There are something even more interesting. Imagine if we have a List of Option, is it a functor ? Oh yes, it turns out that the composition of functors is a functor. Let's check:

val listCompOpt = Functor[List].compose(Functor[Option])

val ys = List(Some(1), Some(3), None, Some(6))
val zs = listCompOpt.map(ys)(incr)  // List(Some(2), Some(4), None, Some(7))

Yeah! What about the product ?

val listOptProdF = Functor[List].product(Functor[Option])

val ts = (List(1,2),Some(1))

val us = (List(3,7, 2, 1),None)

listOptProdF.map(ts)(incr)   // (List(2, 3),Some(2))

listOptProdF.map(us)(incr)   // (List(4, 8, 3, 2),None)

Oh, Cool.

OK, to finish this post, scalaz-seven (at least the version I was playing with) provides a couple of interesting functions like strengthL, strengthR, and fpair.

Here they are:

val xEit:Either[String, Int] = Right(3)

val yEit:Either[String, Int] = Right(4)

println(xEit.strengthL("Help"))    // Right("Help",4)

println(yEit.strengthL("Help"))    // Right(("Help",3))

val xOpt:Option[Int] = Some(4)

val yOpt:Option[Int] = None

println(xOpt.strengthR("my godness"))   // Some(4, "my godness") println(yOpt.strengthR("My godness"))  // None

println(xOpt.fpair)     // Some(4,4)
println(xEit.fpair)     // Right(3,3)

I  hope to be able to come with other posts in this series. No promise, but stay tuned.

----------------
[1] Banana in this article context is not a scala or a java library, it is a fruit name. In case you're not familiar with it, check this article. You may wonder how could one wrongly associate scalaz with banana. Well, that may happen, who knows.

[2] Rabbit in this article context is not a scala or a java library, not even a cool javascript library, it is a name of an animal. Again, wikipedia is helpful in case you're not familiar with it. Well, again, it may happen that you associate scalaz to rabbit, who knows.

[3] EJB2 is a server side component, usually managed by the application server. It is used mainly in enterprise application, and by the way the 'E' is Enterprise. You should not wonder why you might associate scalaz to EJB2, it happened !

RivieraDev Day 2 Wrap Up - With Epilog Too

Another interesting day today. There were less participants than yesterday, although the talks are actually at least as interesting as yesterday.

Hibernate OGM by Emmanuel Bernard
We might wonder (well, I'm still wondering even after the talk) why we need JPA for NoSQL. Even worse, a JPQL for NoSQL, quite contradictory isn't it?

That was actually Emmanuel Bernard's presentation I attended this morning (in French). At the beginning, the goal of OGM is to use JPA for Infinispan. But, the Hibernate team found out that the JPA could be generalized to NoSQL in general. That's why they start to implement Hibernate OGM to No SQL databases.

Emmanuel explained four types of NoSQL databases: key value, big table (e.g. HBase), graph database (Neo4J), or document based (MongoDB) one. At the moment, OGM  supports Neo4J and MongoDB that are apparently keen to participate in OGM development.

All in all, I find the presentation not that interesting and not that convincing. A good presentation to start the morning though.

Scala by Fredrik Ekholdt
Fredrik explained a lot of things on Scala in this talk. Too many, in my opinion. For some, that might be interesting, because we can see a lot of things in once, but for some others that might be too hard to follow, hence not interesting.

The presentation started with quick introduction to Scala, before going into detail to trait and loan pattern, higher order function, duck typing, functional programming and data structure, parallel collection, implicit, and pimp my library. All in 50 minutes presentation !

I couldn't really judge the content, since nothing really new in his presentation today, after all it's a Scala introduction talk. I think it should have been better if Fredrik focused on some important features and not to go to many things.

Play! by Nicolas Leroux and Nicolas Martignoles (A little GQuery)
Well, I'm sorry not to be able to say a lot for this presentation. I had to leave the session doing some buffet lunch preparation after the first 20 minutes.

But, from the part that I saw, I really think that Play! is a good idea and helpful. I would love to see the framework more detail. Even better, Play! 2.0 core will become Scala, what can be better than that ?

Oh, yes. I could also spend some 5 minutes or so in Manolo's presentation on GQuery. It looks like to be an interesting thing to see. Also, at the end of the talk, he announced the release of GQuery 1.1 today ! Thanks to choose RivieraDev to make the announce.

Ceylon by Stephane Epardaud and Cucumber by Frederick Ros 
To be honest, the presentation on three JVM languages are not that impressive: Scala, Kotlin, and Ceylon. The presenters went too detail into the detail of languages, but less in philosophical choices (if any). But, that was not the reason I left the session after 30 minutes: it was planned that I would see the two presentations.

Ceylon as a language is quite boring, actually. Nothing specially mind-blowing in Ceylon (Scala: well, it's mind-blowing, reified generic in Kotlin is actually interesting) I have an impression Ceylon is there to reduce a little bit the frustration ones have with Java, but still keep all the rest, especially the possibility to work with famous java frameworks (yeah, yeah: hibernate). Oh, I have to say nevertheless that Union Class is insteresting.

I missed the beginning of Cucumber presentation. When I arrived in the room, Frederick was doing some demos. Then, he presented some interesting use cases of Cucumber, including the BDD, or even the use of Cucumber to monitor production (not sure to understand what this meant though).  There were only around twenty people in the room, but the discussion that followed the presentation was quite excellent (that might be the benefit of small public). One question I love much was "Is there really helpful for somebody without computer science all this specification written in natural language, but still expressed at the end in programming language? " That's exactly my doubt on BDD though. I still feel the "jump to solution, without real requirements analysis" is in the BDD approach. Is it really the best way to make "life specification?" . BDD is still programmer oriented from my point of view.

Coffee Script by Bodil Stokke
This talk is the best talk of the day. It actually saved the day that at the end relatively less interesting than Thursday.

Bodil Stokke presented the Coffee Script excellently. She showed really the essence of the coffee script: make clean solution, a lot of use of spaces, nice syntaxes, and all those things. Nothing really mind-blowing in coffee script though, it's just a better syntax than java script. There's no, for example, the concept of isolate, that quite interesting in dart.

It was not the content who made Bodil's presentation interesting though. It was the way she presented the subject. The jokes about the programming language creator were very funny. From Bodil's presentation we can see however that Coffee Script is a serious attempt to improve java script. The syntaxes are indeed very nice, like destructuring [sum, diff] = (a,b) -> [a + b, a -b].

All in all, the presentation was excellent, she succeded to show how nice coffee script was. But honestly, if you stick to use Java Script in a discipline way (see eloquent java script book), I don't think we really need Coffee Script. Dart is clearly something else -- unfortunately, it does not have nice syntaxes of Coffee Script though.


OPA by Louis Gesbert
For me, the mind-blowing approach of web development is incarnated by OPA. They really attack the fundamental problem of web development: heterogeneity of the system, starting from client, server, and the database. They are really heterogen, for example, the programming languages are different, the presentation of the data is different. For example relational database is yet another form of representation of data in the system that uses object oriented and java script in the client.

Those heterogeneity is indeed the problem that every body seems to try to solve, starting from Dart that wants to be a language that can be used in big application as well as a client one, node js, or even GWT.

So, OPA tries to provide a comprehensive solution that unifies the way to develop web application. Not surprisingly, functional programming language is used for this purpose. Indeed, with functional programming, you can define what the system is, and not how the system should be architected. For example, the automatic slicing client/server applications provided in OPA is a very cool idea.

In his presentation, however, Louis was not really able to show the concrete solution that OPA tried to propose.  I did not really get how the problem of heterogeneity  could really be solved by OPA. Maybe I should check OPA more to know better the product.

Oh, yes. It was quite ashamed to see very few attendees were in this session. Maybe it was too hard to stay in a conference on Friday evening.

Epilog
Finally, I really think that RivieraDev was a good conference, with nice programs. The programs can still be improved , but the important things might be the number of attendees , especially on the second day. But, small number of participants could also be positive as I saw in Cucumber session that I found to have really interesting discussions.

I'm quite disappointed with Ceylon, Scala, and Kotlin presentations. Not on the content, but how they were presented. I don't really care about the exact syntaxes or features, because in one hour, I could not do anything. In one hour presentation, one should attack more on philosophical point of view of the language, instead of syntax things.

Surprisingly, all Java scripts related sessions were quite interesting. I love Dart and CoffeeScript sessions, and heard a lot of nice things on JQuery. I had also a good impression on GQuery presentation. I would have been happier however if a real Java Script supporter to defend the languages. I still believe that it is possible to write Java Script cleanly (like it is the case in Eloquent Java Script book). Maybe, next year, the supporter of "clean" and plain Java Script should be invited.

See you next year.

RivieraDev Day 1 Wrap Up

It was an interesting day we had on Thursday at Riviera Dev.

The conference started with a keynote from Stephane Epardaud, Inria, and some sponsors. Nothing much interesting in the keynote content, except that now I know that Inria puts (even) more efforts on programming languages. This is very cool. 

Dart, by Florian Loitsch
Then, the talks started. At the first session, Florian Loitsch from Google presented Dart. I was sooo sceptical about Dart, but I decided to come to his session anyway. To my surprise, his presentation reduced my scepticism on Dart. Not on the infamous "optional typing" on which I still have my reserves, but on the fact that Dart is not actually that boring. The Isolate concept, interface with factory, and couple other things are very neat. Florian actually did an excellent job in his presentation to demo all these things live.

I had also some interesting discussions with him at lunch time about Dart, the role of Gilad Bracha, how Dart team works, and so on. All in all, his talk was almost my favorite talk at the conference.


Kotlin, by Dmitry Jemerov
All right. After Dart, another language, Kotlin by Dmitry Jemerov from JetBrain. His talk was actually interesting, but because his session must compete with NodeJS session, the number of participants are not that many, but still he had a lot of audiences.

Dmitry did not present many new things on Kotlin compared to the Kotlin web site or to Strange Loop presentation on the language. One thing I like in Kotlin is actually reified generics and also on String interpolation, that quite neat. I wonder how type check costs to Kotlin performance though. One other interesting thing from his presetnation was the IDEA demo on Kotlin. It was so short  unfortunately, he could have made longer and slower demo though.

GWT, by Nicolas de Loof
Nicolas de Loof was a good presenter. His presentation was fluid, and by the way, it was the only French talk I attended.

In his talk, he presented GWT from very high level point of view. Why GWT, the environments around GWT, and so on and so forth. For me, the talk was too high level though, I expected something more technical or strategic, like GWT after dart (oops, I almost said: GWT after dark). But after all, it was a quite interesting session.

Java 7 / 8, by Simon Ritter
This talk was supposed to be the talk of the day. And indeed, it was talk of the day in term of audience. The INRIA amphi was quite full.

 He started with long history about Oracle and Sun, JCP and all those things. Then, quickly re, viewed Java 7 features, and finally Java 8. There were not many things in Java 8 though ..., oops sorry, there were a lot of things new in Java 8 of course, but I heard most of them. He showed examples on "closures", which was quite nice, and he talked about the possibility to have parallel collection in Java 8 (sounds familiar, isn't it?).

How GitHub Uses GitHub to Build GitHub
The star of the day is Zach Holman. His talk (was it a rant ? ) was astonishing and inspiring.

He started with agile-bashing (I love a presenter that starts his presentation by bashing agile) and then started to explain on how GitHub work, something he called working asynchronously. Then, about the crazy practices of branching of branch of branch of branch, and how he sees the things should have been done simpler. He also explained about pull requests as a communication tool, about Hubot, and all those things.

His rant was finally quite depressing for those who work with a lot of processes and less real things. The idea of Zach is to put to maximum the possibility of doing real things instead of those process stuffs like meetings, complicated problem report, and all other things that finally counter-productive.

Speaker Dinners / Open Café
Open Café at the end of the day was also interesting. I discussed a lot with Henri Gomez (DevOps),  Nicolas Leroux (Play!), Bodil Stokke (Coffee Script), Fredrik Ekholdt (Scala, TypeSafe) and my colleague Nicolas Bousquet. We had a lot of interesting things discussed, including what differences between Norwegians and Swedish :-) (Fredrik and Bodil are Norwegians) , Scala and TypeSafe, and all other things.

Summary
That was an interesting inspiring day. I hope to have similar experience today. Hope to see another depressing presentation again :-)

Semantic Tableaux in Less than 90 Lines of Scala

This week challenge for me was to write a code that can check a propositional logic formula like
(¬(p ⋀ q) ↔ (¬p  ∨ ¬q)) ∧ ( ¬r ∧ q)  and check if the formula is valid or satisfiable. A formula is valid when it is always true under any interpretations of all its atoms. A formula is satisfiable when there is some interpretation of its atoms that can make the proposition true.

The complete code for this post is available here.

Semantic Tableaux
For example, p ⋀ q is satisfiable, since if p and q are both true, then the formula is true. (p  ∨ ¬p)  ⋀ (q ∨ ¬q) is valid, because regardless the interpretation of p and q, the formula is always true.

One way to implement the satisfiability and validity check is by creating truth table. But, the use of truth table is always exponential in number of atoms. There is fortunately a simple technique to check the validity and satisfiability a propositional logic formula. The technique is called Semantic Tableaux. I need to get my logic book I used back to the time of 2nd year of university (Ben-Ari, 1992 ) to remind me how it works. Basically, there are 9 rules, 5 α rules, and 4 β rules.

The following are the 9 rules:

α Rules

α	α1	α2
¬ ¬A	A
A1 ∧ A2	A1	A2
¬(A1 ∨ A2)	¬A1	¬A2
¬(A1 → A2)	A1	¬A2
(A1 ↔ A2)	A1 → A2	A2 → A1

β Rules

β	β1	β2
B1 ∨ B2	B1	B2
¬(B1 ∧ B2)	¬B1	¬B2
B1 → B2	¬B1	B2
¬(B1 ↔ B2)	¬(B1 → B2)	¬(B2 → B1)

I will not explain the Semantic Tableaux algorithms in detail. You can check a more detail in (Ben-Ari ) or in (Issawi, 92). Here is an example of tableau creation for ¬(p ⋀ q) ↔ (¬p  ∨ ¬q) :

Code 
Ok, let's start coding now.  The target is to have the following application working:

object Run { 
    def main(args:Array[String]):Unit = { 
      import Formulas._ 
      val formula1 = (¬('r) ∧ 'q) ∧ (¬('p ∧ 'q) ↔ (¬('p) ∨ ¬('q) )) 
      println(isSatisfiable(formula1) + "," + isValid(formula1)) // true, false 
 
      val formula2 = ¬('p ∧ 'q) ↔ (¬('p) ∨ ¬('q) ) 
      println(isSatisfiable(formula2) + "," + isValid(formula2)) // true, true 
    } 
  }

I used a sealed class Formula to represent all formulas. Atom, Conjunction, Disjunction, Implication, Equivalence, and Xor are classes that extends the trait. In addition, I introduced class  ¬ to represent the negation. Here is how it looks like.

sealed abstract class Formula  
case class Atom(symbol:Symbol) extends Formula 
case class Conjunction(p:Formula, q:Formula) extends Formula 
case class Disjunction(p:Formula, q:Formula) extends Formula 
case class Implication(p:Formula, q:Formula) extends Formula 
case class Equivalence(p:Formula, q:Formula) extends Formula 
case class Xor(p:Formula,q:Formula) extends Formula 
case class ¬(p:Formula) extends Formula

Note that Atom class takes a symbol as its property, so that it allows us to write Atom('p) for example.

I let the Formula class empty in the example above just to make the examples clear. The content of the class is actually the boolean operation to a formula, like ∧,∨, →, ↔, and ⊕. I benefit from Scala that allows special characters to be used as function name. Here is the class Formula looks like:

sealed abstract class Formula { 
  def ∧(q:Formula) = Conjunction(this, q) 
 
  def ∨(q:Formula) = Disjunction(this,q) 
 
  def →(q:Formula) = Implication(this,q) 
 
  def ↔(q:Formula) = Equivalence(this,q) 
 
  def ⊕(q:Formula) = Xor(this, q) 
}

With this, we can write(Atom('p) → Atom('q)) ∨ Atom(r). Not bad, but better to have directly ('p → 'q) ∨ r . For that purpose, implicit comes to rescue:

implicit def symbolToAtom(sym:Symbol) = Atom(sym)

We can now define how the validity and satisfiability work. This code illustrates the example of the application for testing our program:

object Run { 
    def main(args:Array[String]):Unit = { 
      import Formulas._ 
      val formula1 = (¬('r) ∧ 'q) ∧ (¬('p ∧ 'q) ↔ (¬('p) ∨ ¬('q) )) 
      println(isSatisfiable(formula1) + "," + isValid(formula1)) // true, false 
 
      val formula2 = ¬('p ∧ 'q) ↔ (¬('p) ∨ ¬('q) ) 
      println(isSatisfiable(formula2) + "," + isValid(formula2)) // true, true 
    } 
  }

Now let's see the implementation of the 9 rules (you remember 5 α rules, and 4 β rules ?). It's quite simple actually. An application of rule actually retuns a list of leaf, and a leaf is actually a list of formula. Here it is:

  type Leaf = Set[Formula] 
 
  def applyRule(f:Formula):List[Leaf] = 
    f match { 
      case f if isLiteral(f) => List(Set(f)) 
 
      case ¬(¬(a)) => List(Set(a)) 
 
      case Conjunction(a,b) => List(Set(a,b)) 
 
      case ¬(Disjunction(a,b)) => List(Set(¬(a), ¬(b))) 
 
      case ¬(Implication(a,b)) => List(Set(a, ¬(b))) 
 
      case Disjunction(a,b) => List(Set(a), Set(b)) 
 
      case ¬(Conjunction(a,b)) => List(Set(¬(a)), Set(¬(b))) 
 
      case (Implication(a,b)) => List(Set(¬(a)), Set(b)) 
 
      case Equivalence(a,b) => List( Set(a,b) , Set(¬(a), ¬(b))) 
 
      case ¬(Equivalence(a,b)) => List(Set(a,¬(b)),Set(¬(a), b)) 
  }

Nothing should be surprising except the case f if isLiteral(f) => List(Set(f)).  Just disregard this line at the moment, it's only useful in semantic tableau generation. Another surprise maybe for the equivalence rules.  The two equivalence rules in the code above are actually equivalent to the one in the rule table (leave as an exercise :-) ). Note how close the rules definition to its coding implementation. Isn't it nice ?

The most interesting part is of course the implementation of semantic tableau generation. In this naive implementation, the semantic tableau generation is embarrassingly simple, barely 10 lines of codes.

    def semanticTableau(f:Formula):List[Leaf] = { 
 
      def combine(rec:List[Leaf], f:Formula):List[Leaf] = 
               for ( a <- applyRule(f); b <- rec) yield (a ++ b) 
 
      def openLeaf(leaf:Leaf):List[Leaf] = 
        if (leaf forall isLiteral) 
          List(leaf) 
        else 
          leaf.foldLeft(List(Set.empty:Leaf))(combine) flatMap(openLeaf) 
 
      openLeaf(Set(f)) 
    }

Although short, the code is actually very dense. As you can see, the generation of semantic tableau above uses an auxiliary method openLeaf that does exactly that: opening a leaf. Opening a leaf is a recursive function that stops when all formulas in the leaf is a literal. A literal is either an atom or a negation of an atom. The else part is much more complex. But here is the idea: for each formula in a leaf, we apply one of the 9 rules defined above. The result of the application is combined using the combine function above. This will end up with a list of Leaf. For each leaf, then we recursively calls openLeaf using flatMap. This may be unclear, but try to play with the codes, hopefully it'll be clearer.

Finally, we need to implement validity and satisfiability check. A formula is f said to be valid if the semantic tableau for ¬f is closed. A semantic tableau is closed when all its leaves are closed, and finally a leaf is closed when it contains a formula in form of p and ¬p. Here is the implementation:

    def isClosedLeaf(f:Leaf):Boolean = 
      if (f.isEmpty) false 
      else { 
        (f.head match { 
           case Atom(_)    => f.tail.exists( _ == ¬(f.head)) 
           case ¬(Atom(a)) => f.tail.exists( _ == Atom(a)) 
           case _ => false 
         })  || isClosedLeaf(f.tail) 
      } 
 
    def isOpenLeaf(f:Leaf) = !isClosedLeaf(f) 
 
    def isValid(f:Formula):Boolean = semanticTableau(¬(f)) forall isClosedLeaf 
 
    def isSatisfiable(f:Formula):Boolean = semanticTableau(f) exists isOpenLeaf

We're done.

Summary
In this post, I showed my weekend hacking to implement naive satisfiability and validity checking of a propositional formula using semantic tableau. The implementation uses intensively Scala concepts like operator overriding, implicit, and fold and flatMap. All this concepts are helpful to implement the semantic tableaux techniques in relatively short Scala codes (less than 90 lines).  The use of operator helps readibility of the implementation (imagine how it looks like if I didn't use operators ∧,∨, →, ↔, and ⊕).

Reference
Ben-Ari, M (1992) Mathematical Logic for Computer Science. Prentice Hall.

Fix from Fold

My two previous posts, Fold Right from Fold Left and Folding Stream with Scala are actually my interpretation to (Hutton, 1999) paper. Now, I would like to continue with another paper (Pope, 2010 ?) that also talks about fold. Note that, Pope's work cites of  Hutton's work.

This post ends my fold trilogy. It has been an exciting and fun to play with.  I would love to continue with scalaz Fold (Foldr, Foldl, FoldMap Foldable are interesting), but I think I have to stop having fun :-)

Yet Another dropWhile Implementation

In Folding Stream with Scala , I implemented dropWhile using fold using (Hutton, 1999) paper. Pope proposes two more implementations, both work very well with infinite stream.

First, a reminder of fold implementation:

def foldr[A, B](combine:(A, =>B) => B, base:B)(xs:Stream[A]): B = { 
    if (xs.isEmpty) base 
    else combine(xs.head, foldr(combine, base)(xs.tail)) 
  } 

And here is the solution:

  def dwHo[A](pred:A=>Boolean, xs:Stream[A]):Stream[A]=>Stream[A] = { 
    val id =(s:Stream[A])=>s 
    val tail= (s:Stream[A])=>s.tail 
 
    def combine(next:A, rec: =>Stream[A]=>Stream[A]) = { 
     if (pred(next)) (rec compose tail) 
     else id 
    } 
    foldr(combine, id)(xs) 
  }

Example:

  scala> val xs = Stream.range(20, 120) 
  xs: scala.collection.immutable.Stream[Int] = Stream(20, ?) 
  scala> dwHo( (_:Int)<100, xs)(xs).toList 
  res33: List[Int] = List(100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119) 

It also works with infinite Stream:

scala> val ys = Stream.from(1) 
ys: scala.collection.immutable.Stream[Int] = Stream(1, ?) 
scala> dwHo( (_:Int)<5, ys)(ys).take(10).toList 
res38: List[Int] = List(5, 6, 7, 8, 9, 10, 11, 12, 13, 14)

Under the hood, here is what happen:

foldr combine id [1..] 
 =combine 1 (foldr combine id [2..]) = 
 =(foldr combine id [2..]) . tail 
 =(combine 2 (foldr combine id [3..]) . tail 
 =(foldr combine id [3..]) .tail . tail 
 =(combine 3 (foldr combine id [4..]) . tail . tail 
 =(foldr combine id [4..]) .tail . tail . tail 
 =(combine 4 (foldr combine id [5..]) . tail . tail . tail 
 =(foldr combine id [5..]) . tail . tail . tail . tail 
 =(combine 5 (foldr combine id [6..]) . tail . tail . tail 
 =id . tail . tail . tail . tail

And (id.tail.tail.tail.tail)[1..] = [5..].

Fix from Fold
The most interesting part of the (Pope, 2010) is not on dropWhile though, but on an implementation of a function using fold. The function is called fix, also known as Y combinator. Check this page to have an idea of what fix function is.

Basically, using fix, we can encode recursion function. The following is an example of factorial function using fix in haskell:

Prelude> :m Control.Monad.Fix 
Prelude Control.Monad.Fix> fix (\rec n -> if n == 0 then 1 else n * rec (n-1)) 5  

120
In Scala, fix function is implemented in a much trickier way. The difficulties come from the Scala strictness. Here is the implementation of fix I found after googling a little bit:

def fix[A](f: (A=>A)=>(A=>A)): A=>A = f(fix(f))(_)

Example:
scala> fix[Long](f=>x=> if (x == 0) 1 else x * f(x - 1))(5)

res5: Long = 120

One question that may arise is whether fold can be implemented using fix. Well, apparently, yes, after all, it's a recursion, but I haven't tried it yet. A more interesting question would be if fix can be implemented using fold. The answer is yes, and that's the essence of (Pope, 2010) article. Here is the implementation of fix using foldr in Scala:

def fix[A](f: (A=>A)=>(A=>A)): A=>A = { 
  def combine( a:(A=>A)=>(A=>A), b: =>A=>A):A=>A = f(b)(_) 
  foldr(combine, null)(Stream.continually(null)) 
}

Give a try:

scala> fix[Long](f=>x=> if (x == 0) 1 else x * f(x - 1))(5) 
res6: Long = 120

Youpi..., isn't it awesome? This shows how expressive fold is, since it can now be used to implement (any?) recursion functions.

References

• Hutton G (1999) A tutorial on the universality and expressiveness of fold. Available from http://www.cs.nott.ac.uk/~gmh/fold.pdf 

• Pope B (2010 ?)  Getting a Fix from the Right Fold. Available from: http://www.haskell.org/wikiupload/1/14/TMR-Issue6.pdf . There is one other dropWhile solution in this paper that I dumped here: https://gist.github.com/1195982.

Fold Again: Fold Left using Fold Right

In my previous post, I have shown how fold can be used to implement other collection methods, like filter, map, length, reverse, or even dropWhile and break.

We wonder now whether it is possible to implement fold left using fold right. The article (Hutton, 1999) shows indeed that it is possible. The objective of this post is then to show it in Scala and discuss a little bit about fold universality.

Before implementing fold left using fold right, let's implement something simpler. Let's implement suml, a function that is similar to sum we discussed in the previous post. Instead of summing from right to left, we want suml to sum from left to right.

The following illustrates the difference between sum and suml:

   1 sum(Stream(1, 2, 3, 4))= 1 + (2 + (3 + 4))
   2 suml(Stream(1, 2, 3, 4))= (((1 + 2) + 3) + 4)
   3 

As described in (Hutton, 1999), it turns out that we can't directly implement suml using fold. What possible is to define suml_ that returns a function Int=> Int. Here is the implementation:

   1 def suml_(xs:Stream[Int]) = {
   2     def combine(x:Int, g: =>Int=>Int) = (acc:Int)=>g(acc +x)
   3     foldr(combine, (x:Int)=>x)(xs)
   4 }
   5 def sum(xs:Stream[Int])=suml_(xs)(0)

When suml_(Stream(1, 3, 4, 5)) is called, it returns actually

((_:Int) + 5) compose ((_:Int) + 4) 

compose ((_:Int) + 3) compose ((_:Int)+ 1) 

compose ( (x:Int)=>x)

Note that, the returned function is actually an Int=>Int function, and when it receives 0 as its input, it returns (((1 + 3) + 4) + 5) = 13. Also note a special function, the identity function (x:Int)=>x.

OK, Great. What about foldl? Well, it is the generalization of suml above. Here is the foldl implementation:

   1 def foldl_[A,B](f: (A,B)=>B, xs:Stream[A]) = {
   2    def combine(x: A, g: =>B=>B) = (acc:B)=> g(f(x,acc)) 
   3    foldr(combine, (a:B)=>a)(xs)
   4 }
   5 def foldl[A,B](f:(A,B)=>B, base:B, xs:Stream[A]) = foldl_(f,xs)(base)
   6 

Let's give a shot:

   1 scala> foldl( (_:Int) + (_:Int), 0, Stream(1, 3, 4, 5))
   2 res1: Int = 13
   3 
   4 scala> foldl( (_:Int) * (_:Int), 1, Stream(1, 3, 4, 5))
   5 res2: Int = 60

Excellent. But, all this looks like a magic, right? Is there a systematic way to derive a implementation of a function using fold? Fortunately, yes. Here we come to the most interesting part of (Hutton, 1999).

Fold Universality and  Fusion Property of Fold

Two  important concepts explained in (Hutton, 1999) is fold universality and fusion property of fold.

The fold universality states that the two Scala code below are equivalent:
Code 1

   1 def g[A,B](xs: Stream[A], f:(A, B)=>B, v:B): B = 
   2   if (xs.isEmpty) v else 
   3   f(xs.head, g(xs.tail, f, v))

Code 2

   1 def g[A,B](xs:Stream[A], f:(A,B)=>B, v:B) = foldr(f,v)(xs)
   2 

Or more concise, in haskell symbols:

   1 g[]     = v
   2                       <=>   g = fold f v
   3 g(x:xs) = f x (g xs)    

And the fusion property of fold states the following:

1 h w = v
2                          => h . fold g w = fold f v
3 h(g x y) = f x (h y)

Let's have examples.

First, let's see how universal property of fold is useful to derive an implementation of a function using fold.

We will start with the recursive definition of foldl:

1 foldl     [] f v  = v
2 foldl (x:xs) f v  = foldl xs f (f v x) 

In scala:

1 def foldl[A,B](xs:Stream[A], f:(B,A)=>B, v:B): B = {
2    if (xs.isEmpty) v
3    else foldl(xs.tail, f, f(v, xs.head))
4 }

Unfortunately, foldl does not match directly with universal property definition. We need then an auxiliary method foldl_ :

1 def foldl_[A,B](xs:Stream[A]) = foldl[A,B](xs:Stream[A], (_:(B,A)=>B), (_:B))

That is, foldl function without the last two parameters.

We're ready to use universal property now:
foldl_ [] = v
foldl_ (x:xs) = f x (foldl_ xs)

Here, v is the identity function =id.

{Functions}
foldl_ (x:xs) g a = f x (foldl_ xs) g a
<=>
{Definition of foldl}
foldl_ xs g (g a x) = f x (foldl_ xs) g a
<=>
{Generalizing foldl_ xs = h}
h g (g a x) = f x h g a
<=>
f = (λx h -> (λa -> h(g a x)))

So, we got:
foldl xs f v = foldr((λx h -> (λa -> h(g a x)))) id xs v

When translated to Scala, we obtain the code explained at the beginning of the post.

***

Now, go for fusion property. Recall our map definition defined in the previous post (I modified a little bit):

   1 def map[A,B](f1:A=>B) = {
   2    def combine(x:A, xs:Stream[B]) = f1(x) #:: xs
   3    foldr(combine, Stream.empty)
   4 }

Note that the combine function can be represented as λx xs->f1 x : xs .

We would like to (a little bit informally) prove that map(f1) compose map(f2) =  map(f1 compose f2).
From the equation, we can substitute:
h = map(f1)
g = λx xs->f2(x):xs
w = v = Stream.empty = []
f = f1 compose f2

But,
map(f1) [] = []
map(f1) (g(x,xs)) = map(f1) ( f2(x):xs )
                  = (f1 compose f2)(x):map(f1)(xs)

So, the equation map(f1) compose map(f2) =  map(f1 compose f2)indeed holds.