Monday, 24 December 2007

Immutable stacks in OCaml/F# and Scala

The Scala programming language diverges from the ML family of languages (including OCaml and F#) in many respects and some of these can be seen in the simple immutable stack implementation given in the book "Programming in Scala".

The following implements a simple immutable stack in Scala 2.6:

sealed abstract class Stack[+a] {
def push[b >: a](x: b): Stack[b] = new NonEmptyStack(x, this)
def isEmpty: boolean
def top: a
def pop: Stack[a]
}
object EmptyStack extends Stack[Nothing] {
def isEmpty = true
def top = throw new Error("EmptyStack.top")
def pop = throw new Error("EmptyStack.pop")
}
class NonEmptyStack[+a](elem: a, rest: Stack[a]) extends Stack[a] {
def isEmpty = false
def top = elem
def pop = rest
}

The following is an equivalent implementation in OCaml or F#:

module Stack = struct
type +'a t = Empty | NonEmpty of 'a * 'a t
let is_empty = (=) Empty
let push h t = NonEmpty(h, t)
let top = function
Empty -> raise Not_found
| NonEmpty(h, _) -> h
let pop = function
Empty -> raise Not_found
| NonEmpty(_, t) -> t
end

The idiomatic ML solution is clearly substantially more concise. There are several reasons for this:

  1. OCaml and F# infer all types in this (and most other) cases whereas the argument and return types of the functions and parameters of parent classes are all specified explicitly in the Scala.
  2. Covariance is automated by OCaml and F# but Scala requires covariance to be introduced explicitly in the definition of the abstract class and repeated in all derived classes, and then handled explicitly in the definitions of member functions such as push.
  3. OCaml and F# automate the hoisting of immutable expressions like the empty stack whereas Scala requires the distinction to be added explicitly by declaring NonEmptyStack as a derived class but EmptyStack as an individual object.
  4. The type of the empty stack must be given explicitly in Scala but the type is polymorphic so Scala introduces the identifier Nothing to denote this unknown type. This is inferred automatically by OCaml and F#.
  5. The module system allows all definitions (type and function) to be encapsulated in a single module called Stack in the OCaml and F#. In contrast, the Scala gives three different object/class definitions that redundantly contain Stack as a substring in their names.

These characteristics of Scala make it more verbose than OCaml and F# in this case. Comparisons between Scala and other modern functional programming languages are surprisingly rare: the Scala community typically compare Scala to other JVM languages. Thus we shall endeavour to describe the similarities between Scala and other languages in future posts.

5 comments:

helium said...

OK, tried it in F#, but didn't work. The Scala-version is generalized, so that you can push supertypes of "a" (and than recive a stack of supertypes). But this seems not to work in F#:



module Stack = struct
type +'a t = Empty | NonEmpty of 'a * 'a t
let is_empty () = (=) Empty
let push h t = NonEmpty(h, t)
let top = function
Empty -> raise Not_found
| NonEmpty(h, _) -> h
let pop = function
Empty -> raise Not_found
| NonEmpty(_, t) -> t
end

type baseType = class
new() = {}
end

type derivedType = class
inherit baseType
new() = {}
end

let aStack = Stack.NonEmpty(new derivedType(), Stack.Empty)

let anotherStack = Stack.NonEmpty(new baseType(), aStack);




Type mismatch. Expecting a baseType Stack.t but given a derivedType Stack.t. The type baseType does not match the type derivedType

Flying Frog Consultancy Ltd. said...

In OCaml, the +'a denotes a type covariant in the type variable 'a. So this example works in OCaml but F# does not appear to use the same notation for covariance annotations. I'll try to find out how you do this in F#...

Erik said...

Any luck on this so far?

Flying Frog Consultancy Ltd. said...

Erik, I have investigated this and it turns out that .NET and F# do not support contravariance so this is not currently possible. Microsoft are planning to add this in .NET 4.0 though.

Simon C. said...

I'm a bit late in the conversation but well :).

Regarding your last point on the module system, the same could be done in Scala. It's just that the version you posted is the idiomatic version because it makes use of inheritance polymorphism to extend what you wrote here with the pattern matching.

It's not worse nor better, but it is very practical for some designs.

Here is the Scala version written as the ML-module. Your other remarks (on type annotations and necessity to define classes and objects) stand, but they are compromise for some more powerful features. Full-inference & type generalization could not work in Scala, and as an Ocaml programmer I don't feel too much impaired by this, because it gives a contract (and in Ocaml there are always times when you need to supply the type, like when creating a Map).

class Stack[+a] {
sealed abstract class t[+a] extends Stack[a];
case class NonEmpty[+a](elem: a, rest: Stack[a]) extends t[a]
case object Empty extends t[Nothing]
def push[b >: a](x: b): Stack[b] = NonEmpty(x, this)
def isEmpty: Boolean = this == Empty
def top: a = this match {
case Empty => throw new Error()
case NonEmpty(x, _) => x
}
def pop: Stack[a] = this match {
case Empty => throw new Error()
case NonEmpty(_, t) => t
}
}

In term of expressiveness, I believe Scala classes are as "powerful" as ML modules (they were made from ML-modules with Java classes aspects). You can define abstract types, etc.