Thursday, September 22, 2011

Frege supports now Haskell style comments

From the feedback I received so far I learned that it would probably be a good idea to make porting Haskell code  to Frege as easy as possible. Which means, not harder than unavoidable.

One of the maybe most annoying differences on the lexical level has been the Java-ish comment syntax. This has been fixed today, and from now on Frege recognizes only Haskell style comments anymore.

Yes, this is a backward-incompatible change. I did it under the assumption that there is not much Frege code around there yet.

For those of you who have already written lots of well-documented Frege code there is a tool to convert old comments  to new ones in files specified on the command line. Conversions may be incomplete if one has identifiers with an odd number of apostrophes at the end, as I had to note during conversion of the compiler sources.

Monday, September 19, 2011

Parallelism in Frege employing the fork/join Java API

Yesterday I implemented some experimental support for the fork/join API that comes with JDK 7.

The base operation from a Frege point of view is par. An expression like

a `par` b

arranges for evaluation of a in another thread and returns b, like in Haskell.
For example, a parallel map can be implemented like this

pmap f [] = []
pmap f (x:xs) = a `par` as `par` (a:as) 
        a  = f x
        as = pmap f xs

Unlike the ordinary map, pmap works only on finite lists, because construction of the tail implies immediate construction of the tail of the tail and so forth.

There is an example program in the distribution that implements different algorithms for computing the number of solutions to the n queens puzzle. I added a parallel version of the list based solution and measured the resulting run times. The parallel version constructs n different start out positions where the first queen is placed on a different column of the first row each time, and computes the solutions for the n start out positions in parallel. Then it adds the results.

I have a computer with 2 "hyperthreaded" cores. The JVM deduced from this that the parallelism must be 4 and starts 4 worker threads. During program execution, I saw a CPU utilization of around 75%. This already saved 50% of the run time in medium sized problems (up to n=13).

I then arranged it so that 2 threads will be created for every "CPU", and noticed an overall CPU utilization of 95%. The savings in run time tend to manifest themselves better the  greater the problem is and seem to approximate  2/3. But this numbers will most likely depend on the hardware and maybe the OS.

In small problems that take less than a second in the sequential version (i.e. n=8), the run time differences are barely noticeable.

There is also the possibility to prohibit the Frege run time from actually executing anything in parallel by passing a system property -Dfrege.parallel=false in the command line. The par operator will then effectively behave like

a `par` b =  snd (a,b)

The feature is included in the frege3.17.152.jar available from the download area.

Thursday, September 15, 2011

Friendly Reception

Last weekend, a person unknown to me announced our project on reddit:::haskell. There were about 40 comments, the most of them were positive, interested or even excited.

To answer questions and, most importantly, combat the impression that the project is not active anymore, Wulf and me decided to get us a reddit account (voxfrege).

One topic discussed more extensively was that small differences between Frege and Haskell are  considered annoying for Haskell programmers. Paradoxically, those differences seem to be the more annoying the more "like Haskell" Frege is.

One key example for this is the comment syntax. I am willing to reconsider this and other topics like this as soon as possible (while there is not much code out there yet). Indeed, the opinion expressed that Frege is most interesting to "weekend/would-be Haskell programmers" who are locked with the JVM in their daily jobs, seems to be confirmed by the fact that the same announcement linked to reddit::java did not get a single comment up to now!