Functional Programming in Scala

Here I go, congratulating myself for finishing Functional Programming Principles in Scala, an online class taught by Martin Odersky, creator of the Scala programming language, professor at EPFL in Lausanne, Switzerland and co-founder of Typesafe.

Scala is a well engineered modern successor to Java. It's a statically-typed functional/OO language with curly-brace syntax, pattern matching and type inference that runs on the JVM. Scala's libraries are well-thought-out and consistent. And, it's type system is some serious rocket-science.

The course took some material and examples from the classic Structure and Interpretation of Computer Programs (SICP), which is a great way to learn functional concepts in a new language. Topics included:

• higher-order functions
• pattern matching
• immutability and immutable collections
• laziness
• touched on inductive proofs of correctness

Boatload of Scala resources

Class staff and students compiled a great list of resources for learning Scala.

• Scala resources
• Scala cheat sheet
• Scala style guide

• Scala API Docs
• Scalacheat
• Twitter's Scala school and Effective Scala
• About Scala on StackOverflow
• Learning Scala in small bites
• CheatSheet

While we're on the topic, Twitter has invested big in Scala, open-sourcing some of the results. The presentation Systems Programming at Twitter gives a peek into how Twitter uses Scala for "programming the datacenter". Kestrel is a distributed message queue.

Books

• Programming in Scala
• Scala for the Impatient
• Scala in Depth

Principles for Good Design

The class was a great introduction to the language and some ideas that will come in handy in any language. I had a lot of fun with it. Odersky wrapped up the course with some principles for good program design.

• Name everything you can
• Put operations into natural scopes
• Keep degrees of freedom for future refinements

Hipster programming languages

If you look at the programming languages that are popular these days, a few patterns emerge. I'm not talking about languages that have the most hits on the job sites. I'm talking about what the cool kids are coding in - the folks that hang out on hacker-news or at Strange Loop. Languages like Clojure, Scala and CoffeeScript. What do these diverse languages have in common other than an aura of geek-chic?

• Functional programming is emphasized over object-oriented programming.
• Common patterns for manipulating lists: map, filter, reduce.
• Modern syntax in which everything is an expression and syntactic noise like semicolons is reduced.
• CoffeeScript compiles to JavaScript, while both Clojure and Scala target the JVM. Targeting legacy platforms seems to be getting easier and more popular.
• Innovative approaches to concurrency.

This last point deserves some elaboration. It might be a stretch to compare the event-driven nature of node.js with immutable data structures with actor model and software transactional memory, but, at heart, these are all strategies for dealing with concurrency. One place where Java was ahead of its peers was concurrency, so it's cool that Clojure and Scala are taking the next steps in concurrent programming on the JVM.

CoffeeScript

CoffeeScript is javascript, redesigned. It cleans up the syntax adding many of the niceties familiar from Ruby and Python. Curly braces and semicolons are out. String interpolation, list-comprehensions, default arguments, and more tasty sugar are in. Its creator, Jeremy Ashkenas, believes in code as literature and it shows all the way through the project. Take a look at the annotated source code for the CoffeeScript grammar and see if it doesn't make you weep for the ugliness of your own code.

Don't forget, CoffeeScript gets about 10 times hipper when combined with node.js, the event-driven app-server based on google's V8 javascript engine.

Clojure

Clojure is a dialect of lisp targeting the JVM. One of Clojure's key features is a set of immutable functional data structures, with efficiency comparable to Java's mutable collection classes. The beauty of a Lisp dialect is that the syntax of the language is also it's data representation. Code is data, data is code. There are lots of Clojure resources floating around, including a famous talk by Rich Hickey on state, identity, value and time and a project to port SICP to Clojure. Extra points if your client-side code is written in ClojureScript.

Several hip people have recommended reading The Joy of Clojure. Also on Rich Hickey's bookshelf is Chris Okazaki's book Purely Functional Data Structures.

Scala

Scala is a strongly typed object-functional hybrid. It's targets include the JVM and Microsoft's CLR. It's an academic language derived from the ML family, but meant to be a pragmatic replacement for Java. It has a C++ like reputation for being fully understood only by guru level developers. One of it's key features is a type system that is Turing complete in itself. I guess I'm not completely convinced that a rocket-science type system is the answer, but it's there's cool stuff in there - generics done properly, higher-kinded types, which as near as I can tell takes parametric types to a level of meta beyond generics. One nice thing is that Scala has a tighter mapping to Java than Clojure so the interop between the two is a little more reasonable.

The Akka project is a Scala platform for concurrent applications, providing both the actor model and software transactional memory. Those wanting to learn more can track down some interesting talks by language designer Martin Odersky available, plus the Scala Types podcast.

A couple more

Not enough languages for you? I'll throw in a couple more hip languages, R and Haskell. Truly cool kids know Haskell. What can I say, except that I am not yet that cool. I need to go out to a shed in the woods with a couple of books and learn me some Haskell.

R may have a bastardized syntax, but, eventually, it's functional core shines through. R is seeing a surge in popularity based on the highly hip and trendy field of data science, where it's powerful statistical methods and graphing come in handy. Aside from mclapply, R is a bit lacking in support for concurrency. [See correction below in comments!] Rhipe and Revolution Analytics's RHadoop are trying to change that by enabling distributed data analysis with R and Hadoop.

Fashion

You might be tempted to say it's all fashion. What goes around comes around. To some extent that's true, but, in each of these languages, there's something new and worthwhile to be learned. We have a ways to go before code is as expressive as we want it to be. Someone smart said that you'll like a programming language in proportion to what it teaches you. Mostly, I want to remind myself to set aside some time to play with these languages and see what new tricks they have to teach this old dog.

PS: When this post grows up, it wants to be Programming language development: the past 5 years by the very hip Michael Fogus.

Scala tutorial

On a cold gray sunday afternoon, I went through the tutorial for the Scala programming language (by a group in Switzerland called LAMP). There was an exercise straight out of SICP about evaluating simple algebraic expressions. Here's what I came up with. It may be far from optimal, but seems to work for at least the one test case.

abstract class Tree
case class Sum(l: Tree, r: Tree) extends Tree
case class Var(n: String) extends Tree
case class Const(v: int) extends Tree

object Expressions {
type Environment = String => int

def eval(t: Tree, env: Environment): int = t match {
  case Sum(l, r) => eval(l, env) + eval(r, env)
  case Var(n) => env(n)
  case Const(v) => v
}

def derive(t: Tree, v: String): Tree = t match {
  case Sum(l, r) => Sum(derive(l, v), derive(r, v))
  case Var(n) if (v == n) => Const(1)
  case _ => Const(0)
}

// there's probably a more functional way to do this
def simplify(t: Tree): Tree = t match {
  case Sum(l, r) =>
    val sl: Tree = simplify(l)
    val sr: Tree = simplify(r)
    sl match {
      case Const(lv) => sr match {
        case Const(rv) => Const(lv + rv)
        case _ =>
          if (lv==0) sr
        else Sum(sl,sr)
      }
      case _ => sr match {
        case Const(rv) if (rv==0) => sl
        case _ => Sum(sl,sr)
      }
    }
  case Var(n) => Var(n)
  case Const(v) => Const(v)
}

def toString(t: Tree): String = t match {
  case Sum(l, r) => "(" + toString(l) + " + " + 
                    toString(r) + ")"
  case Var(n) => n
  case Const(v) => v.toString()
}

def main(args: Array[String]) {
  val exp: Tree = Sum(
                    Sum(Var("x"),Var("x")),
                    Sum(Const(7),Var("y")))
  val env: Environment = { case "x" => 5 case "y" => 7 }
  println("Expression: " + toString(exp))
  println("Evaluation with x=5, y=7: " + eval(exp, env))
  println("Derivative relative to x: " + 
          toString(derive(exp, "x")) + " = " +
          toString(simplify(derive(exp, "x"))))
  println("Derivative relative to y: " +
          toString(derive(exp, "y")) + " = " +  
          toString(simplify(derive(exp, "y"))))

}

The subclasses of Tree define the nodes of a parse tree for simple expressions like:

((x + x) + (7 + y))

The program demonstrates Scala's pattern matching capabilities, defining methods that perform operations on trees: evaluate, take derivatives, and print. Pattern matching is a feature borrowed from the ML family of languages. You might think of them as case statements on steroids. Sometimes they can concisely replace polymorphism. Here, they play the role of the visitor pattern.

The visitor pattern makes it easy to add new operations on all members of an inheritance hierarchy in a modular way. (Modular meaning the operation is encapsulated). The cost is that adding a new member to the inheritance hierarchy requires modification of all existing operations. The cost and benefit of pattern matching statements is the same.

More Scala Resources:

• Scala website
• The busy Java developer's guide to Scala
• Scala talk by Martin Odersky
• Scala for Java Refugees at Code Commit
• Alex Blewitt's tutorial
• First Steps to Scala at Artima