Sunday, November 16, 2008

The Downward Spiral: from Scala to Haskell to Clojure

Warning
I'm afraid this entry is going to be more rambling than substance. There are two points on which I do would like to have feedback though. I'll put them in red so you can skip my fool's babbling and get directly to them.

Scala
About a year ago I got interested in Scala. I bought the Programming in Scala book and begun reading it selectively, concentrating on the functional programming part, something I want to learn. I got to like the idea of passing functions around as a way to customize functionality and I appreciated the use of case to deconstruct lists in small recursive functions. Of the three languages, Scala is the one I fiddled with the most although I did not even do a hobby sized project. I only worked on toy examples.

Haskell
One thing led to another, I got introduced to Haskell when I stumbled upon Tony Morris Haskell exercises for beginners. Since Scala has some roots in Haskell, I thought it'd be nice to learn a bit about Haskell. I begun by reading Haskell-Tutorial by Damir Medak & Gerhard Navratil. It was a bit dry for me since my mathematical notions are more than a 15 years away. I followed that up with part of "A Gentle Introduction to Haskell". I had to read and reread parts of it several times. It's not any failure of the text, it's really trying to hammer in these new (for me) notions in my head and again, the dusty maths. It's been very interesting to me and I liked the infinite data structures. Later though, my mind almost entered a infinite recursive loop itself trying to understand the client-server example in the lazy pattern section. I read a lot about Haskell but almost did nothing in it. I was puzzled while pondering the interactive environment prompt: "But how do I test anything without side effects?" I was unsure even how to assign the result of a function to a variable. I read a bit about monads but in the end, I decided to pre-order the book Real World Haskell and give it a rest meanwhile. As an aside, I was unsure if infinite lists were possible in Scala until I saw Infinite Lists for the Finitely Patient by Daniel Spiewak.

After that, I decided to have a quick look at F#. Now I hadn't written any Haskell, but I had read about it intensively for a few weeks. I was following along nicely until I saw a function example with a call to print something and I actually gasped. "Sacrilege!", I thought, and then remembered I was not in Haskell anymore and that F# is more like of a mix language like Scala.

Clojure
Things got quiet for a while until Clojure was mentioned in some article. I had a really quick look and thought: "Eek! Lisp!" It got mentioned again one too many time for me to ignore and decided to have a look at it. I went to the official website and was really surprised to see such clean layout and a beautiful logo for the language. I saw the introduction screen cast for java programmer. It turned out the the language designer is a good speaker, with strong opinions but not fanatic at all. Clojure has been designed with specific goals in mind and is the result of practical experience. Nothing seems whimsical about it; every compromise carefully weighted in.

Lisp
This is my fourth brushing with Lisp. The first one was at the university. We were learning Scheme and the professor was brilliant, but unfortunately I prematurely shut down my mind to it without giving it a shot. We were explained Scheme was a functional language and as such, a function would always return the same result when called with the same parameters. Also mutability of variables was presented as something of a trick since variables should not change. I then thought something about the lines of "How can we do anything without changing variable values? What kind of language would need something so essential to be done as a hack!?" I wanted nothing to do with Scheme anymore. It's also a shameful anecdote that being young, arrogant and hot-blooded, I went as far as personally insulting Lisp and John McCarthy on a Usenet forum.

I encountered Lisp for the second time about 10 years later on Paul Grahams website. I found The Roots of Lisp to be very interesting and I tried to give Lisp a shot and read partway through Teach Yourself Scheme in Fixnum Days by Dorai Sitaram. I was intrigued and baffled by practical applications of nondeterminism! Still, I was also busy learning C# and ASP.NET at the time to earn a living, and thus put Lisp aside.

My third encounter with Lisp was when I went to see this excellent text Functional Programming For The Rest of Us by Slava Akhmechet (I love reading about computer science history) and then found The Nature of Lisp by the same author. Fascinating stuff, but I still put Lisp aside.

Give & Take
Scala & Haskell have a lot of syntax. Clojure has little syntax. I just haven't done enough Lisp or Clojure to get used to it and so for now, I prefer at least a little syntax to be able to parse the flow control of a program. So in that regards, I prefer the former family of language. On the other hand, sometimes things can get complicated to grasp with so much syntax. As Scala & Haskell can't modify themselves like Clojure, new syntax must be injected as best as possible but this gives rises to small differences or context differences having a big impact on the meaning of the program and human parsing ain't so easy anymore. Again, lack of experience prevents me from comparing with Clojure. I suppose trying to understand a function using several layers of macros must be difficult too.

As an aside, I'm wondering something about closures, doesn't it defeat a little the purpose of functional programming to have a function which can modify a value outside the function itself? Isn't it a bit like programming with global variables? This is not a critique, just thinking out loud.

JVM & Java API
Both Scala (JVM mostly and .NET) and Clojure (JVM) have chosen to target a virtual machine and it's a great decision with a lot of advantages. But on the downside, I feel it is forcing newcomers to learn Java on top of the Java API. I feel that in that regards, the .NET framework is more agnostic. The documentation does not presuppose a particular language and usually propose code examples in many languages, granted only the Microsoft ones. What I mean is you can use the .NET framework and it's documentation with, let's say, vb.NET, and it does not feel like you have to know C# in order to use it well. It'd be nice to have something more like that when you're learning Scala or Clojure. Of course, the comparison is a bit unfair because if you are using the .NET framework with a non-Microsoft language, you'd be in exactly the same situation.

(Somewhat of a) Conclusion
Things have gone full circle now that I'll soon be getting the printed edition of Programming in Scala. I'll get back into it and hopefully get a good grasp of it. Real World Haskell will be waiting just around the corner (of the book shelve.) I still haven't made up my mind yet about preordering Programming Clojure by Stuart Halloway, but it's more than likely.

I don't know if one of these three languages will become my new favorite, but hopefully I'll have a pretty good understanding of functional programming after all that. If nothing else, I'll be ready for the addition of closures in the Java language if it ever happens, or be able to start using the functional Java or Jedi library when I finally get to use a jdk > 1.4 at work!

Monday, July 21, 2008

Cédric Beust's Coding Challenge

I finally got around finishing Cédric Beust's coding challenge in Scala.

It didn't help that I got sidetracked by Tony Morris Scala and Haskell exercises for beginners.
Scala exercises for beginners
Haskell exercises for beginners

But back to the coding challenge!

From Cédric's website: Coding Challenge

Here is an interesting coding challenge: write a counter function that counts from 1 to max but only returns numbers whose digits don't repeat.

For example, part of the output would be:

* 8, 9, 10, 12 (11 is not valid)
* 98, 102, 103 (99, 100 and 101 are not valid)
* 5432, 5436, 5437 (5433, 5434 and 5435 are not valid)

Also:

* Display the biggest jump (in the sequences above, it's 4: 98 -> 102)
* Display the total count of numbers
* Give these two values for max=1000

Since my solution is in Scala, I tried to make it as functional as I could instead of doing a standard imperative exercise.

It has been an worthwhile exploration of Scala for me.

So here it is.

First, the necessary functions to determine if a number has repeated digits or not:

def getDigits(number: int): Array[int] = number.toString.toArray.map(_.toInt - 48)

def hasRepeatedDigits(number: int): boolean = {
    val digits = getDigits(number)
    val digitPresent = Array.make[int](10, 0)
    digits.foreach(digit => digitPresent(digit) += 1)
    digitPresent.exists(_ > 1)
}

Now, to generate the list itself. That is the part I feel the most imperative. I tried different ways, including a recursive function, but this seemed the simplest way in the end:

def getNonRepeatedDigitNumbers(max:Int): List[Int] = List.range(1,max+1).filter(!hasRepeatedDigits(_))

Next has been the most interesting part for me. I started with the idea that I would use a list of the gaps and simply get the maximum from it.
Here is the idea:

def maximum(x: List[Int]): Int = (x.head /: x.tail)((a:Int, b:Int)=>(if (a>b) a else b))

But how to get the gap list? I needed something similar to a fold operation, but I wanted to operate always with the current and previous element instead of accumulating a result to operate with the current element.

Maybe I am just reinventing the wheel here, but here is my "pair" map function:

def pairMap(previous:Int, serie:List[int], f: (Int, Int) => Int): List[Int] = serie match {
    case Nil => Nil
    case head :: tail => f(
previous, head)::pairMap(head, tail, f)
}

An here is how I get the gap list:

def getGapList(serie: List[int]) = serie match {
    case Nil => Nil
    case head :: tail => pairMap(head, tail, (a:Int, b:Int)=>(b - a))
}

As an aside, I realized from Tony Morris exercises that I tended to include a superfluous match in my recursive list functions.
For example, here is how I first wrote the preceding function:

def getGapList(serie: List[int]) = serie match {
    case Nil => Nil
    case head :: Nil => Nil
    case head :: tail => pairMap(head, tail, (a:Int, b:Int)=>(b - a))
}


At last, here is how I used the functions to solve the code challenge:

val serie = getNonRepeatedDigitNumbers(1000)
val totalCount = serie.size

println("Biggest jump: " + maximum(getGapList(serie)))
println("Total count of numbers: " + totalCount)

Tuesday, June 17, 2008

Scala Light... A Java successor?

Upon reading on a few forums in Artima, I detected a desire for both a fuller Java and a simpler Scala. A fuller Java to have things like type inference and more functional style constructs. A simpler Scala to be have an easier specification, both for the mind and for the IDE.

What do you think would be more appropriate to help Java developers get a better language?
  • Continue to selectively better the Java Language
  • Define a subset of Scala, a Scala Light if you will. Or would a subset of Scala defeat the purpose of its synergy of features?
  • Another choice

Tuesday, June 10, 2008

A simple Java FP list map

Following on the comments I received on my previous entry about doing a bit of Java functional programming style, I made a very simple class to map a list. I'm following the style of what I have seen in the apache collections utilities. See previous post.

First note that I am doing it without generics (I'm stuck with jdk1.4.2 at work), so for some this would be old style Java programming.

Here's the utility class.
ListUtils.java

package fp;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class ListUtils {
static public List map(List elements, Applier applier) {
List result = new ArrayList();
for (Iterator it = elements.iterator(); it.hasNext();) {
Object element = it.next();
result.add(applier.apply(element));
}
return result;
}
}


And the interface used by the utility class.
Applier.java

package fp;

public interface Applier {
public Object apply(Object element);
}


Here's a client code example.

WithPoints.java

package domino;

public interface WithPoints {
public Integer getPoints();
}


Domino.java

package domino;

public class Domino implements WithPoints {
private Integer points;

public Domino(int points) {
this.points = new Integer(points);
}

public Integer getPoints() {
return points;
}
}


And finally!

package domino;

import fp.Applier;
import fp.ListUtils;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class Main {

public static void main(String[] args) {
List dominoes = new ArrayList();
dominoes.add(new Domino(1));
dominoes.add(new Domino(2));
dominoes.add(new Domino(3));

List points = ListUtils.map(dominoes, new Applier() {
public Object apply(Object domino) {
return ((WithPoints) domino).getPoints();
}
});

System.out.println(points); // [1, 2, 3]
}
}


So this time around, I did get a new list instead of transforming a list but I still think the simple iterator style is clearer and it avoids using a "utility class" for doing something really simple.

Iterator style

List points;
for (Iterator iter = Dominoes.iterator(); iter.hasNext();) {
points.add((WithPoints) iter.next().getPoints());
}


And of course, Scala still is neater for me 8)

val points = dominoes map (x => x.points)

Monday, June 9, 2008

The Scala Influence

A while ago, Frank Sommers asked the following:
How Has Functional Programming Influenced Your Coding Style?

If wish I could have replied something then, but I was just starting to learn Scala, and I couldn't.

Now, I'm still just at the beginning of grokking FP, but I can write about how it almost influenced a bit of Java code I had to write the other day at work.

Post update: "I have to use jdk 1.4.2 at work. That's why I am not using generics and all."

I had a list of instances of a certain class, and I wanted to get a list made from the result of invoking a certain method on each instance.

We'll pretend I had a Domino class, and I wanted to invoke the method getPoints() on each instances

Here's how I would have done it in Scala:

class Domino(p: int) {
val points=p
}

val dominoes = List(new Domino(1), new Domino(2), new Domino(3))

val points = dominoes map (_.points)

Let's say it's a bit cryptic in Scala and make it a bit more explicit:
val points = dominoes map (x => x.points)

I'll skip the Java class definition, but it implements the interface WithPoints, which declares the "Integer getPoints()" method .

Now, just look at what I had to code in Java to get the point list:

List points;
for (Iterator iter = Dominoes.iterator(); iter.hasNext();) {
points.add((WithPoints) iter.next().getPoints());
}

Simple really, but I couldn't get over how much neater (to me) it was in Scala.

Now comes the functional programming influence part. It so happens that I had a transformation library at my disposal in my Java project: org.apache.commons.collections

It's not what I really wanted, but I could use some kind of functional programming style with it. And here's the end result:

List dominoes;
CollectionUtils.transform(dominoes, new Transformer() {
public Object transform(Object domino) {
return ((WithPoints) domino).getPoints();
}
});


So there, it's not so bad, except that:
1) It transforms my list instead of returning a new list, which is what I wanted.
2) The imperative version is, in my opinion, clearer.

And so this is how functional programming has (almost, but not quite) influenced my coding style so far.

Wednesday, April 16, 2008

Instance read-only access modifier

Be it in C++, Java, or Scala, I have always been bothered by the fact that an instance of a class has access to the private members of another instance.

Sure, it's mighty useful for copy constructors and other functionalities like adding, but I always felt there should also be a "private read-only" access modifier.

Of course, there is no problem in the case of immutable objects. Here's a Scala example (using Scala version 2.6.1).

class Domino(p: int) {
private val points=p

def add(that: Domino) = new Domino(p + that.points)

override def toString() = "Domino: points=[" + points +"]"
}

scala> val d1 = new Domino(1)
d1: Domino = Domino: points=[1]

scala> val d3 = new Domino(3)
d3: Domino = Domino: points=[3]

scala> d1.add(d3)
res2: Domino = Domino: points=[4]


But what if, for whatever reason, I am using mutable objects?

In the following code, I have no quarrel with the function addToMe, but I am bothered by the function addToOther. I wish I could specify my special "private read-only" access modifier there, so this function would not compile.

Normal Scala code:

class MutableDomino(p: int) {
private var points=p

def addToMe(that: MutableDomino) = { points = points + that.points }

def addToOther(that: MutableDomino) { that.points = that.points + points }

override def toString() = "MutableDomino: points=[" + points +"]"
}


I would like to be able to write the class like the following (the exact name of the access modifier is not important)

Crazy Scala code:

class MutableDomino(p: int) {
private[this] var points=p

def addToMe(that: MutableDomino) = { points = points + that.points }

def addToOther(that: MutableDomino) { that.points = that.points + points }

override def toString() = "MutableDomino: points=[" + points +"]"
}


What do you think about an instance read-only access modifier?

Is it useful, or is it over the edge?

Post update!

Thanks to Eric's heads up below, I learned about the access modifier.

I can actually go even further than prevent write-access to a private member of another instance: I can block read and write access to it altogether using the "this" qualifier.
E.g. : private[this]

Here is a new version of the MutableDomino class with it that will be, rightly so, rejected by the Scala interpreter:

class MutableDomino(p: int) {
private var points=p

def addToMe(that: MutableDomino) = { points = points + that.points }

def addToOther(that: MutableDomino) { that.points = that.points + points }

override def toString() = "MutableDomino: points=[" + points +"]"
}

error: value points is not a member of MutableDomino
def addToMe(that: MutableDomino) = { points = points + that.points }
^
error: value points is not a member of MutableDomino
def addToOther(that: MutableDomino) { that.points = that.points + points }