Tuesday, August 21, 2007

Scala vs Lisp for GPS: Part I: Expressivity

Introduction Before I found Scala I was looking for a language with the following characteristics:

  1. Expressivity on par with Python or Lisp
  2. Performance on par with Java
  3. Has a REPL or at least an interpreter
  4. Compiled
  5. Object-oriented
  6. Large number of modern libraries and frameworks
  7. Cross platform, including think-client GUIs
  8. Open Source
Now I've found Scala and I think I have my language, but unfortunately it's hard to tell about the expressivity without doing a real project and doing a real project involves a measure of risk. Instead, I decided to port some Lisp programs from Norvig's Paradigms of Artificial Intelligance Programming to Scala and compare them to the original Lisp programs. As as second step, I'll "Scala-ize" each program to be more idiomatic Scala (mostly increasing object orientation) to see the result. Finally, I'll attempt to do some sort of performance comparison. Background - What is GPS GPS stands for "General Problem Solver." The algorithm here comes from Alan Newell and Herbet Simon way back in 1957. The original attempt was to create a computer program that could solve any problem. It fell quite short of its goal, but the algorithm is still interesting and its expression in Lisp or Scala quite concise. Those of you familiar with planning problems will recognize the basic structure and the sample problems. For more information, see Chapter 4 of PAIP. The Algorithm A problem is described using a set of initial conditions, a set of operators that can change those conditions, and a set of goal conditions. Each operator has a name, a list of preconditions (conditions that most be true for it to be invoked), an add list (conditions it will add to the state when invoked), and a delete list (conditions it will remove from the state with invoked). Note that these conditions are simple. They are not based on on propositional or predicate logic. The GPS uses a technique called means-ends analysis. A brief explanation is contained here about half way down the page. In a nutshell, the algorithm tries to achieve each goal one at a time, until it fails to a achieve a goal or it has achieved all the goals. The preconditions for each action are achieved by recusively invoking the algorithm on them. For a detailed description of the implementation of the algorithm, see PAIP or look at the comments in my Scala code. Comparison of Implementations There are some substantial differences between the Lisp implementation and the Scala implementation. They are:
  1. The Scala implementation is more explicitly structured. Some of the structure, such as the static typing, is forced by Scala. Others, such as using classes instead of conventions on list contents to distinguish between normal conditions and "executing conditions," are not forced by Scala but are simply easier and more natural.
  2. The resulting plan is a list of operators rather than a list of lists obeying a convention. This is straightforward because "executing conditions" are a special class of condition and are explicitly tied back to the operators they represent.
  3. The core algorithm in Scala is completely and explicitly devoid of mutable state. The Lisp solution makes only one small use of mutation in achieve-all, and that occurrence could easily be removed in the same was as it was from Scala. However, cons cells, and the lists they form, are mutable and therefore it is much more difficult to prove that the algorithm uses no mutable state.
  4. The Scala solution required fewer utility functions. This is due to both the richer standard library and case classes.
  5. The problem-definition DSL required significantly more code in Scala, especially in order to make it interpreter-friendly.
  6. The syntax of the problem-definition DSL in Scala is statically checked. For example, you cannot use preconditions in the place of the add list. Achieving this took a fair amount of work, and I almost just went with a looser version that was equally easy to type and read but less validated.
  7. In my subjective opinion, the Scala version is much easier to read. I find the fact that Lisp control structure like "if" implicitly return nil on failure if not "else" is provided to be quite confusing.
General observations:
  1. At least for this problem (which didn't use macros), Lisp code could be almost directly converted to Scala.
  2. Scala implicits make an effective substitute for special variables (i.e. defparameter) in Lisp.
  3. Overall LOC count is too close to matter.
  4. Lisp development is far more interactive that Scala.
  5. The Scala compiler catches a lot of "stupid" mistakes that the Lisp compiler does not (but the Lisp compiler catches some, much more than Python, Ruby, et. al.), reducing the number of edit/run cycles by a fair margin.
  6. Case classes are really useful. They allow you to add structure to your program without going to all the work of implementing all the support methods, such as equals, hashCode, toString, and unapply for pattern matching. Lisp is worse than Java et. al. because it has four different equals functions (eq, eql, equal, equalp) all with subtle (and not so subtle) differences. In Scala, if you are wise and don't have to deal with Java libraries (hah!), you pretend eq (reference equality) doesn't exist (indeed, pretending references don't exist, and null doesn't exist, seems like a good idea to me). In fact, I find case classes so useful, I think I'm going to write a Python metaclass so I can use them in Python, too.
  7. I retract previous negative statements about pattern matching on lists. It's useful. I get it now. But I still wouldn't convert a string to a list just for pattern matching.
Updated - Finished point 6. Conclusion I'm not going to conclude anything yet. So far, Scala seems to be as expressive as Lisp, and its added structure and compiler definitely reduce the number of errors made while coding. However, this comparison was on a relatively simple piece of code and the Scala implementation was mostly a port. This means that I can't say one way or another whether the added structure of Scala would be a help or a hindrance to the early stages of flushing out code. Based on my experience with Python, I think without case classes the added structure would definitely be a hindrance. Keeping all the basic functions (comparison, hash, toString) up-to-date on rapidly changing objects is a real pain.

Sphere: Related Content


Alex Boisvert said...

Hi Erik, the link to the scala code seems broken.


Erik Engbrecht said...

Thanks for the heads up! It's fixed now.

Anonymous said...

Did you forget to finish point 6 of 'General observations'?

Erik Engbrecht said...

I obviously need to read what I write more carefully. Broken links and unfinished thoughts...you'd think this was a hobby or something...

Point 6 under general observations is now complete.

Bill Pyne said...

I read this post yesterday after you published the link on TSS. Great post. I downloaded the Scala code and am looking it over. The code gives a better flavor for Scala's power than the simple examples I've seen elsewhere.

Anonymous said...

Hi Erik, great post! I didn't consider Scala until I read it. I'm starting to change my mind now.

Jon Harrop said...

Have you considered OCaml or F#? They are both much faster than any of the other languages you discuss, for example.

Erik Engbrecht said...

Jon - I've been considering taking a look at both those languages, but F# is not open source and for Linux/Unix would be dependent on Mono, which, not surprisingly, seems to always lag behind Microsoft's .NET implementation and not be completely compatible. I think what the Mono project has produced is very impressive, but I also think it will always be a behind the MS .NET runtime and libraries.

Quick perusal of the OCaml website leads me to believe that it doesn't have the breadth of libraries that I would like. One of the aspects of Lisp that frustrates me is that while there are tons of libraries out there for it, simply too many of them are in a pre-release state, neglected, or both. This seems to be common with "fringe" open source languages.

Scala gets around it by being Java compatible. I imagine F# is the same way with .NET. If .NET were as cross-platform as Java I would give F# a very close look, but as far as I can tell it is not.

Anonymous said...

One more language that I suggest you to look through is Nemerle (nemerle.org). It is .NET-based language, but I like it even more then Scala. First of all, I was very impressed with its macro system.

ignacio cases said...

Hi Erik,

thank you for this post. I am implementing GPS with Scala 2.9.1, and wanted to take a look at your solution, but the url seems to be locked.