void-main-args

Gatling Tool at Riviera Scala Clojure

2012-02-22T01:13:00.002+01:00

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.

2012-01-18T13:27:00.000+01:00

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

On 2011 and 2012

2011-12-31T16:30:00.001+01:00

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

2011-11-23T02:55:00.001+01:00

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

2011-10-21T22:01:00.001+02:00

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

2011-10-21T06:51:00.000+02:00

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

2011-09-26T07:24:00.010+02:00

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

2011-09-06T00:21:00.003+02:00

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

2011-08-29T13:24:00.002+02:00

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.

Folding Stream with Scala

2011-08-15T23:48:00.005+02:00

Introduction
Couple of weeks ago, I read a well known paper on expressiveness of fold (Hutton, 1999). The paper is a very interesting paper that explains how fold is a very powerful construct.

The codes in the paper are written in Haskell and therefore assumes laziness. This means that the execution of function in Haskell is delayed until it is really needed. This is not the case for Scala, where the operation is executed eagerly, or in other word, it's strict instead of lazy.

Stream is the implementation of lazy list in Scala. Using Stream, the elements are only evaluated when they are needed. So, we may expect that Stream is close to Haskell's list.

The use of scala Stream and fold right are the topic of this post.

Fold Right
Let's back to fold. The paper I mentioned above (Hutton, 1999) showed how expressive fold construct, especially foldRight. The objective of this post is to show the same things as the paper, but in Scala.

Let's see the problem we may encounter. The following Haskell code works:

   1 Prelude> foldr (||) False (repeat True)
   2 True

But not the following Scala code:

   1 Stream.continually(true).foldRight(false)(_ || _)

because the code above throws StackOverflowError.

The reason of the error is because Stream.foldRight is not actually lazy. When I read the article and wondered how the non-laziness of Stream.foldRight could be solved, I received Tony Morris' tweet telling that scalaz fixes the non-laziness. The following is the reimplementation of lazy foldRight for Stream inspired by Foldr scalaz implementation:

1 
2 def foldr[A, B]( combine: (A, =>B) => B, base: B )(xs: Stream[A]): B = {
3    if (xs.isEmpty) 
4      base
5    else 
6      combine(xs.head,  foldr(combine, base)(xs.tail))
7 }

The following code works without StackOverflowError:

   1 def combine(x: Boolean, y: =>Boolean) = x || y
   2 foldr(combine, false)(Stream.continually(true))

The key of the foldr implementation above is in thetype definition of combine parameter: (A, =>B) instead of (A,B). This makes the second parameter evaluated lazily.

Some Fold Right Uses
The following shows some familiar functions implemented using foldr.

   1 def sum(xs: Stream[Int]) = {
   2     def combine(x: Int, y: =>Int) = x + y
   3     foldr(combine, 0)(xs)
   4 }
   5 def product(xs: Stream[Int]) = {
   6     def combine(x: Int, y: =>Int) = x * y
   7     foldr(combine, 1)(xs)
   8 }
   9 def and(xs: Stream[Boolean]) = {
  10    def combine(x: Boolean, y: =>Boolean) = x && y
  11    foldr(combine, true)(xs)  
  12 }
  13 def or(xs: Stream[Boolean]) = {
  14    def combine(x: Boolean, y: =>Boolean) = x || y
  15    foldr(combine, false)(xs)  
  16 }

Using Fold Right to Implement Scala Collection Functions
As in (Hutton, 1999), the following section shows how Fold Right can be used to implement some functions. At the first time, let's see length, filter, reverse, flatten, and map implementations.

   1 def map[A,B](f:A=>B, xs:Stream[A]) = {
   2    def combine(x:A, xs: =>Stream[B]) = f(x)  #:: xs
   3    val base:Stream[B] = Stream.empty
   4    foldr(combine, base)(xs)
   5 }
   6 def length[A](xs: Stream[A]) = {
   7     def combine(x: A, len: =>Int) = len + 1
   8     foldr(combine, 0)(xs)
   9 }
  10 def reverse[A](xs: Stream[A]) = {
  11     def combine(x: A, xs: =>Stream[A]) = Stream.concat(xs, Stream(x))
  12     val base:Stream[A] = Stream.empty
  13     foldr(combine, base)(xs)
  14 }
  15 def filter[A](p:A=>Boolean, xs: Stream[A]) = {
  16    def combine(x: A, xs: =>Stream[A]) = if (p(x)) x #:: xs else xs 
  17    foldr(combine , Stream.empty)(xs)
  18 }
  19 def filterNot[A](p:A=>Boolean, xs: Stream[A]) = {
  20    def combine(x: A, xs: =>Stream[A]) = if (p(x)) xs else x #:: xs 
  21    val base:Stream[A] = Stream.empty  
  22    foldr(combine, base)(xs)
  23 }
  24 def flatten[A](xss: Stream[Stream[A]]) = {
  25    def combine(xs: Stream[A], ys: =>Stream[A]) = xs #::: ys
  26    val base: Stream[A] = Stream.empty
  27    foldr(combine, base)(xss)
  28 }
  29 def partition[A](p:A=>Boolean, xs:Stream[A]) = {
  30    (filter(p, xs), filterNot(p, xs))
  31 }
  32

Note that, the functions like flatten, filter, and map, work with infinite Streams. See the following examples:

   1 scala> map( (_:Int)+1, Stream.from(1))
   2 res2: Stream[Int] = Stream(2, ?)
   3 
   4 scala> res2.take(4).toList
   5 res3: List[Int] = List(2, 3, 4, 5)
   6 
   7 scala> filter( (_:Int) % 2 ==0, Stream.from(10)).take(5).toList
   8 res5: List[Int] = List(10, 12, 14, 16, 18)
   9 
  10 scala> partition( (_:Int) % 2 == 0, Stream.from(20))
  11 res6: (scala.collection.immutable.Stream[Int], Stream[Int]) = (Stream(20, ?),Stream(21, ?))
  12 
  13 scala>  flatten(Stream.continually(Stream(1, 3, 4))).take(10).toList
  14 res13: List[Int] = List(1, 3, 4, 1, 3, 4, 1, 3, 4, 1)

Implementing dropWhile and break
One of the most interesting part of (Hutton, 1999) is the dropWhile implementation using foldr. The implementation is shown in the following code:

   1 def dropWhile[A](pred: A => Boolean, xs: Stream[A])= {
   2    def combine(x: A, xs: =>(Stream[A], Stream[A])) = 
   3       if (pred(x)) 
   4          (xs._1, x #:: xs._2) 
   5       else 
   6          (x #:: xs._2, x #:: xs._2)
   7    val base:(Stream[A], Stream[A]) = (Stream.empty, Stream.empty)
   8    foldr(combine, base)(xs) _1
   9 }

Instead of directly producing the result, a tuple of Streams is returned. The first Stream is the result and the second one is used for bookkeeping purpose.
The following illustrates an execution of dropWhile:

   1 dropWhile( (_:Int)<5, Stream(1,2,7,3,4,5,6,7,8,9,10)) 
   2 10 => ( (10), (10))
   3 9  => ( (9,10), (9,10))
   4 8  => ( (8,9,10), (8,9,10))
   5 7  => ( (7,8,9,10), (7,8,9,10))
   6 6  => ( (6,7,8,9,10), (6,7,8,9,10))
   7 5  => ( (5,6,7,8,9,10), (5,6,7,8,9,10))
   8 4  => ( (5,6,7,8,9,10), (4,5,6,7,8,9,10))
   9 3  => ( (5,6,7,8,9,10), (3,4,5,6,7,8,9,10))
  10 7  => ( (7, 3,4,5,6,7,8,9,10), (7,3,4,5,6,7,8,9,10))
  11 2  => ( (7, 3,4,5,6,7,8,9,10), (2, 7,3,4,5,6,7,8,9,10))
  12 1  => ( (7, 3,4,5,6,7,8,9,10), (1, 2, 7,3,4,5,6,7,8,9,10))

What surprising is that the solution actually works for infinite Stream too as illustrated in the following code:

   1 scala> dropWhile( (_:Int)<5, Stream.from(1)).take(10).toList
   2 res17: List[Int] = List(5, 6, 7, 8, 9, 10, 11, 12, 13, 14)

The last interesting function implemented here is break. The equivalent of Haskell's break in Scala collection is called span (Update, Oct 24 thanks to oxbow). The break function creates a tuple of two lists separated at condition boundary. Example:

   1 scala> val (a,b) = break( (_:Int)<5, Stream.from(1))
   2 a: Stream[Int] = Stream(1, ?)
   3 b: Stream[Int] = Stream(5, ?)
   4 
   5 scala> a.toList
   6 res22: List[Int] = List(1, 2, 3, 4)
   7 
   8 scala> b.take(5).toList
   9 res23: List[Int] = List(5, 6, 7, 8, 9)
  10

The implementation of break here, of course, highly inspired from dropWhile one:

   1 def break[A](pred: A=>Boolean, xs: Stream[A]) = {
   2    def combine(x: A, xs: =>(Stream[A], Stream[A], Stream[A])) =
   3       if (pred(x)) 
   4         (xs._1, x #:: xs._2, x #:: xs._3)             
   5       else
   6         (x #:: xs._3, Stream.empty, x #:: xs._3) 
   7              
   8    val base:(Stream[A], Stream[A], Stream[A]) = (Stream.empty, Stream.empty, Stream.empty)
   9    
  10    val result = foldr(combine, base)(xs) 
  11    (result._2, result._1)
  12 }

Summary
In this blog post, I showed the result of playing around with Stream and fold right. First, I rewrote the implementation of foldRight, showed the use of foldRight, expressed some collection functions using foldRight, and finally provided dropWhile and break.

The blog post does not have intention to overcome the non-laziness of Scala language. Scala is not a lazy language, and I think it's not appropriate to use lazy evaluation as the main stream of the codes.

Pope (Pope, 2010 ?) in Monad Reader 6 discussed further the implementation of dropWhile. He presented two further solutions based on higher order function composition. He also presented the fold implementation using what is so called fix function. See http://en.wikibooks.org/wiki/Haskell/Fix_and_recursion to have an idea of what Fix function is.

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

A List containing elements with consecutive types A and B

2011-07-13T01:09:00.004+02:00

Just wondering how we can create a "heterogenous" list of two types, where an object of the first type must be inserted after the second.

Examples:
5 :: "help" :: 8 :: "ldf" to create a list with type (Int, String)
"help" :: 8 :: "ldf" :: 9 to create a list with type (String, Int)

Here is what I got:
Wondering if I can do better.

-

Implementing Bird's Make Century Pearl

2011-01-24T18:56:00.010+01:00

Book of Bird (2000) contains 30 pearls of functional programming. I haven't finished this very inspiring book yet, but I would love to share one of the pearl, the pearl number 6, making century.

The problem that the pearl solves is given a number (1, 2, 3, 4, 5, 6, 7, 8, 9) return all expressions containing + and * that make 100. In this case, the output is:

1 * 2 * 3 + 4 + 5 + 6 + 7 + 8 * 9
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 * 9
1 * 2 * 3 * 4 + 5 + 6 + 7 * 8 + 9
12 + 3 * 4 + 5 + 6 + 7 * 8 + 9
1 + 2 * 3 + 4 + 5 + 67 + 8 + 9
1 * 2 + 34 + 5 + 6 * 7 + 8 + 9
12 + 34 + 5 * 6 + 7 + 8 + 9

The following is the specification written using BDD library in Scala:

class  MakeNumberSpec extends FlatSpec with ShouldMatchers { 
 
  "Make Number" should "return all expressions that make a number" in { 
     val xs = (1 to 9).toList 
     solutions(xs, 100).map(displayE(_)) should equal( 
        List("1 * 2 * 3 + 4 + 5 + 6 + 7 + 8 * 9", 
             "1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 * 9", 
             "1 * 2 * 3 * 4 + 5 + 6 + 7 * 8 + 9", 
             "12 + 3 * 4 + 5 + 6 + 7 * 8 + 9", 
             "1 + 2 * 3 + 4 + 5 + 67 + 8 + 9", 
             "1 * 2 + 34 + 5 + 6 * 7 + 8 + 9", 
             "12 + 34 + 5 * 6 + 7 + 8 + 9")) 
  }

The complete solution described in this blog is available at my github here.

Let's first define the expression, term, and factor. A factor is a list of digit, like List(1, 2) is interpreted as 12. Then, term is a multiplication of factors, like 4 * 15, and expression is sum of terms.

It might be tempted to introduce class Expression, Term, or Factor. But I prefer to make the solution simple by using type alias instead:

   type Factor = List[Int] 
   type Term = List[Factor] 
   type Expr = List[Term]

To display factor, term, and expression, I introduced displayF, displayT, and displayE as follow:

def displayF(f: Factor) = f.reduceLeft(10 * _ + _).toString
def displayT(t: Term) = t.map(displayF(_)).mkString(" * ")
def displayE(e: Expr) = e.map(displayT(_)).mkString(" + ")

Let's test first the displayE method:

   scala> displayE(List(List(List(1), List(2), List(3)), 
          List(List(4)), List(List(5)), List(List(6)), List(List(7)), 
          List(List(8), List(9))))

   1 * 2 * 3 + 4 + 5 + 6 + 7 + 8 * 9

The book (Bird, 2010) provides an excellent theory of the solution described here. I will try to be more practical here.

The problem can be attacked by exhaustive search, which means for each two consecutive number, either we add '+', '*' or simply concatenating the numbers.
For example, for 8 and 9 we can have 89 by concatenation, 8 + 9 by summation, and 8 * 9 by multiplication. Given the description of the problem, there will be then 3ⁿ expression candidates to evaluate. For the problem of make century here, it is not that big, only 3⁸ = 6561 candidates.

To do the exhaustive search, we need the following function that expands an expression to a list of expressions when a number is introduced to the list of candidates so far. Three possibilities: concatenating, summing, and multiplying. The code is (with xs is the factor, xss is the term, and xsss is the rest of the expression).

    case (xs::xss):: xsss => 
      List( ((x::xs)::xss)::xsss,         // concatenating 
            List(x) :: xs::xss) :: xsss,  // multiplying 
           ( List(List(x)) :: (xs::xss):: xsss)) // sum

We need of course to take into account the basic case, which is inserting to an empty expression. The empty expression itself is List(List(Nil)) . The complete function becomes:

     def glue(expr: Expr, x: Int) : List[Expr]= 
       expr match { 
         case (Nil::Nil)::Nil => List(List(List(List(x)))) 
         case (xs::xss):: xsss => 
           List( ((x::xs)::xss)::xsss, 
                 (List(x) :: xs::xss) :: xsss, 
                  ( List(List(x)) :: (xs::xss):: xsss)) 
          case _ => Nil // or throw IllegalArgumentException ?
       }

Let's do some tests:

    scala> glue(List(List(Nil)), 9).map(displayE(_)) 
    res3: List[String] = List(9) 
      
    scala> glue( List(List(List(9))), 2).map(displayE(_)) 
    res4: List[String] = List(29, 2 * 9, 2 + 9) 
      
    scala> glue( List(List(List(2), List(9))), 1).map(displayE(_)) 
    res5: List[String] = List(12 * 9, 1 * 2 * 9, 1 + 2 * 9)

The exhaustive solution can then be implemented by continuously applying the glue for each insertion of new number taken into account. This is done by using foldRight of flatMap functions. Then, of course we filter only the one that makes the number to be kept. The following is the code that executes the exhaustive search:

     def valueF(f: Factor) = f.reduceLeft(10 * _ + _) 
     def valueT(t: Term) = t.foldLeft(1)( _ * valueF(_)) 
     def valueE(e: Expr) = e.foldLeft(0)(_ + valueT(_))

     val emptyExpression: Expr = List(List(Nil)) 

     def solutions(xs: List[Int], n: Int): List[Expr] = { 
         def good(exp: Expr) = valueE(exp) == n 
   
         xs.foldRight(List(emptyExpression))( 
           (x, ys) => ys.flatMap(glue(_,x))). 
         filter(good) 
     }

The code can be optimized using a simple enhancement, that is, by using an ok method that has the property good(candidate) => ok(candidate). In this case, we can use ok definition as follow:

   def ok(exp: Expr) = valueE(exp) <= n

and use it as the the filter of the glue operation. The implementation of solutions method becomes:

   def solutions(xs: List[Int], n: Int): List[Expr] = { 
    
       def ok(exp: Expr) = valueE(exp) <= n 
       def good(exp: Expr) = valueE(exp) == n 
    
       xs.foldRight(List(emptyExpression))( 
          (x, ys) => ys.flatMap(glue(_,x).filter(ok))).filter(good)

The solution above can still be optimized by observing that value method executes the same expressions several times. To avoid recalculation, we propagate the last factor, term, and expression.
The following is the improved code, a little bit obscure, I admit.

First, the factor, term, and expression is represented by Intermediate class:

    case class Intermediate(k: Int, f: Int, t: Int, e: Int) { 
      def value = f * t + e 
    }

And, finally the modified glue and solution:

    def glue(expr: Expr, x: Int, im: Intermediate): 
        List[(Expr,Intermediate)]=  { 
   
      expr match { 
        case (Nil::Nil)::Nil => 
          val exp = List(List(List(x))) 
          List( (exp, Intermediate(10, x, 1, 0)) ) 
   
        case (xs::xss):: xsss => 
          List( ( ((x::xs)::xss)::xsss, 
                  Intermediate(10*im.k, im.k * x + im.f , im.t, im.e)), 
                ( (List(x) :: xs::xss) :: xsss, 
                  Intermediate(10, x, im.f * im.t, im.e)), 
                ( (List(List(x)) :: (xs::xss):: xsss), 
                  Intermediate(10, x, 1, im.f*im.t + im.e))) 
        case _ => Nil 
   
      } 
    }

def solutions(xs: List[Int], n: Int): List[Expr] = {

   
       def ok(exp: (Expr, Intermediate)) = exp._2.value  <= n 
       def good(exp: (Expr, Intermediate)) = exp._2.value == n 
   
       xs.foldRight(List( (emptyExpression, Intermediate(0,0,0,0))))( 
          (x: Int, ys: List[(Expr, Intermediate)]) => 
            ys.flatMap( y => 
              glue(y._1, x, y._2).filter(ok))). 
          filter(good).unzip._1 
    }

Reference
Bird R(2010), Pearls of Functional Algorithm Design. Cambridge University Press.

Lazy Sieve Eratosthenes in Scala and Clojure

2010-12-29T09:54:00.008+01:00

Sieve Eratosthenes is a popular prime number generation algorithm. Start with 2 and cross out all even numbers until a limit number. Then, doing the same for 3 to cross out all factors of 3, like 3, 6, 9. The goal of the blog is to show some lazy sieve algorithms using clojure and scala and show the benchmark result of the algorithms.
The complete code is available at https://github.com/anrizal06/rizier .

It is easy to implement eager Sieve algorithms, using scala, this can be achieved as follow:
1 def sieve(limit: Int) = {

   2    
   3    val composites = new Array[Boolean](limit)
   4    
   5    (2 to math.sqrt(limit).toInt).foreach(i => {
   6        if (!composites(i)) 
   7            (i * i  until limit by i).foreach(composites(_) = true)
   8    })
   9    
  10    for { i <- 2 until limit
  11          if (!composites(i))
  12    } yield i
  13 }

On of the problem with the solution above is that the limit parameter that must be used. The parameter is OK if we want to get prime numbers below a certain limit, but it is not OK when we want, for example to get the 1000th prime.

The solution for the problem above presented here is by using lazy evaluation provided in both scala and clojure. Using lazy algorithms, we generate a prime number, only when necessary. For example, if we want to get the 26th prime number, we only generate 26 prime number, not more.

The lazy algorithms for sieve are presented in the work of Melissa ONeill (2009) and the idea are adopted by for example clojure contrib API. The paper also showed that the naive functional solution (not exposed here) is very limited. Indeed, I made some tests with the solution and reached easily StackOverflow error for relatively small number.




Not So Naive Solution




Let's start first with the still naive, but optimized somehow, lazy sieve eratosthenes. First in clojure:

   1 (defn naive-primes
   2    "Implementation of lazy but naive sieve algorithms"
   3    []
   4   (letfn [
   5           (next-prime [x xs] 
   6              (if (some #(zero? (rem x %))
   7                     (take-while #(<= (* % %) x) xs))
   8              (recur (+ x 2) xs)
   9              (cons x (lazy-seq (next-prime (+ x 2) (conj xs x))))))]
  10    (cons 2 (lazy-seq (next-prime 3 [])))))

Line 10 starts the implementation by consing 2 to the lazy sequence of prime number starting from 3. Then, starting from 3, all odd numbers are examined if they are prime or not. This is done at line 6-7 of the code. If it is a composite number, then it recursively calls next prime to examine the next odd number (line 8) . Otherwise, if it is a prime, then the prime number is returned, and the list of prime numbers discovered so far is updated.

To get the 100th prime, one can use (nth (naive-primes) 100)

The equivalent Scala program is the following:

 1   def primes(): Stream[Int] = {
 2      lazy val ps = 2 #:: sieve(3)
 3      def sieve(p: Int): Stream[Int] = {
 4          p #:: sieve(
 5             Stream.from(p + 2, 2).
 6                 find(i=> ps.takeWhile(j => j * j <= i).
 7                 forall(i % _ > 0)).get)
 8      }
 9      ps
10   }

Stream is the Scala equivalent of Clojure lazy-seq. Note the interesting use of lazy val. To get the 100th prime number, one can use primes().take(100).last

At stack overflow , I exposed another solution using mutable list as the alternative solution to the lazy stream above. It turned out that the mutable list solution was faster than the solution above.

With Wheel

The Clojure Contrib library implements Sieve algorithm using wheel. The idea of the algorithm is to discard as many as possible the composite number that is factor of first prime numbers (3, 5, 7 in addition to 2). Indeed, the first solution already discards 2. To discard the numbers, a circular list of step -- or wheel -- is usd. For (2, 3, 5, 7), the wheel is

(2 , 4 , 2 , 4 , 6 , 2 , 6 , 4 , 2 , 
       4 , 6 , 6 , 2 , 6 , 4 , 2, 6 , 4 , 6 , 
    8 , 4 , 2 , 4 , 2 , 4 , 8 , 6 , 4 , 6 , 
    2 , 4 , 6, 2 , 6 , 6 , 4 , 2 , 4 , 6 , 
    2 , 6 , 4 , 2 , 4 , 2 , 10 , 2 , 10).

To make the list circular, clojure has a very convenient method call cycle that can then be used to create the circular list:

cycle [2 4 2 4 6 2 6 4 2 4 6 6 2 6  4  2
6 4 6 8 4 2 4 2 4 8 6 4 6 2  4  6
                        2 6 6 4 2 4 6 2 6 4 2 4 2 10 2 10]


Scala does not have built-in cycle, but it is quite straight forward to implement cycle in scala:

 def cycle[A](xs: List[A]): Stream[A] = {
     lazy val result: Stream[A] = xs.toStream.append(result)
     result
   }

The complete implementation of the algorithm in Clojure is:

   1 (defn wheel-primes 
   2    "The optimization of lazy naive sieve algorithm 
   3    by discarding the number divisible by 2, 3, 5, and 7.
   4    This is done by adding the next number to be examined
   5    by the number given by the wheel."
   6    []
   7    (let [next-prime
   8          (fn next-prime [x xs [f & r]] 
   9              (if (some #(zero? (rem x %))
  10                     (take-while #(<= (* % %) x) xs))
  11              (recur (+ x f) xs r)
  12              (cons x (lazy-seq (next-prime (+ x f) (conj xs x) r)))))
  13          wheel (cycle [2 4 2 4 6 2 6 4 2 4 6 6 2 6  4  2
  14                         6 4 6 8 4 2 4 2 4 8 6 4 6 2  4  6
  15                         2 6 6 4 2 4 6 2 6 4 2 4 2 10 2 10])]
  16          (concat 
  17              [2 3 5 7]
  18              (lazy-seq (next-prime 11 [] wheel)))))

The second solution is then close to the first one, except that instead of incrementing with 2, the next number to be examined is obtained by incrementing with the number in the wheel.
The Scala version of the solution is: 

   1    def cycle[A](xs: List[A]): Stream[A] = {
   2      lazy val result: Stream[A] = xs.toStream.append(result)
   3      result
   4    }
   5    def wheel(): Stream[Int] = {
   6      cycle(List(
   7        2 , 4 , 2 , 4 , 6 , 2 , 6 , 4 , 2 , 
   8        4 , 6 , 6 , 2 , 6 , 4 , 2, 6 , 4 , 6 , 
   9        8 , 4 , 2 , 4 , 2 , 4 , 8 , 6 , 4 , 6 , 
  10        2 , 4 , 6, 2 , 6 , 6 , 4 , 2 , 4 , 6 , 
  11        2 , 6 , 4 , 2 , 4 , 2 , 10 , 2 , 10))
  12    }
  13  
  14    def from(x: Int, stepIt: Iterator[Int]): Stream[Int] = {
  15        x #:: from(x + stepIt.next, stepIt)
  16    }
  17    
  18    def primes(): Stream[Int] = {
  19        lazy val ps = 2 #:: 3 #:: 5 #:: 7 #:: sieve(11, wheel.iterator)
  20        def sieve(p: Int, it: Iterator[Int]): Stream[Int] = {
  21            p #:: sieve( from(p + it.next, it).
  22                            find(i => ps.takeWhile(j => j * j <= i).
  23                             forall(i % _ > 0)).get,
  24                          it)
  25        }
  26        ps
  27    }






Hash Map Based Solution
The problem with the first two solutions is that both solutions require the check whether a number is factor of the prime number discovered so far.  For example, when examining 121, the first two algorithms verify if 121 are factor 3, 5, and 7.  It turns out, that the check is not necessary, and this leads to the third solution of lazy sieve. 

Like the two solutions above, the algorithm receives a stream of odd number and returns a stream of prime number.  The algorithm uses a hash map that stores the last discovered composite number. Each composite number that is stored in the hash map is a factor of prime numbers discovered so far. The key of the hash map is the composite number and the value is the double of the corresponding prime number. 

When a number is under examination, it is checked against the hash map. 
If the number is in the hash map, obviously, it is a composite number. In this case, the number is removed from the hash map and replaced by new composite number that is factor of the corresponding prime. The new composite number must not be in the hash map, therefore it continues to increment the number until discovering a brand new composite number.

On the other hand, when the number is not in the hash map since the beginning, it is a prime. A new composite corresponding to the prime is then inserted to the hashmap; the number is the square of the prime. 


  1 (defn hashtable-primes 
  2    "An implementation of lazy sieve algorithm by storing in a hastable
  3    the next composite number corresponding to a prime number"
  4    []
  5   (letfn [
  6     (next-composite [x step sieve]
  7        (if (sieve x)
  8           ; the composite number has already been found previously
  9           (recur (+ x step) step sieve)
 10           ; brand new composite number
 11           (assoc sieve x step)))
 12     (next-prime [x sieve] 
 13       (let [step (sieve x)]         
 14        (if (sieve x)
 15           ; found a composite
 16           (recur (+ x 2) (next-composite (+ x step) step (dissoc sieve x)))
 17           ; found a prime
 18           (cons x 
 19             (lazy-seq 
 20                (next-prime (+ x 2) (assoc sieve (* x x) (* x 2))))))))]
 21   (cons 2 (lazy-seq (next-prime 3 {})))))

The Scala version of the solution is the following. I used mutable map to gain better performance without really sacrifying the functional nature of the code: 1     import scala.collection.mutable.Map
 2     
 3     def primes() : Stream[Int] = {
 4         2 #:: sieve(3, Map{ 9 -> 6 })
 5     }
 6     private def sieve(p: Int, pQ: Map[Int, Int]): Stream[Int] = {
 7       p #:: sieve(nextPrime(p + 2, pQ), pQ )
 8     }
 9     private def nextCompositeNumber(
10           x:Int, step: Int, pQ: Map[Int, Int]): Unit = {
11       pQ.get(x) match {
12         case Some(_) => nextCompositeNumber(x + step, step, pQ)
13         case None => pQ(x) = step
14       } 
15     }
16     private def nextPrime(candidate: Int, pQ: Map[Int, Int]): Int = {
17       pQ.get(candidate) match {
18           case Some(step) =>
19               pQ -= candidate
20               nextCompositeNumber(candidate + step, step, pQ) 
21               nextPrime(candidate + 2, pQ)
22           case None =>
23               pQ(candidate * candidate) = candidate * 2
24               candidate 
25       }
26     }
Benchmark
To complete the implementation, I did a simple benchmark, mainly with the Scala versions, but Clojure version showed also the similar results. For the implementation, I used Scala 2.8.1 and Clojure 1.2 with Oracle JVM 1.6.0_14 version. The benchmark was done in my tiny laptop with 3GB of memory, Windows, and Intel Pentium Dual Core. 
The result is shown in the following graph: 
Where x-axis shows the limit in million and the y axis is the execution time in ms. The blue line is for the naive solution, and magenta one for wheel solution, and the yellow one for the hash map one. 
The same curve, but not the same execution time, is also observed in the implementation using Clojure. However, The Clojure implementation execution time is longer than Scala.The wheel solution improves the performance of the naive one, but the implementation that uses hashmap performs much better. 
The maximum limit I could manage to have in my machine using the Scala implementation of the hash map algorithm was 150 000 000 that represented more than 8 million primes . The time of execution was around 270 s.
Reference
ONeill M (2009) The Genuine of Sieve Erathosthenes. Available at: 
http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf