Scala: A conversation starter

Yesterday was the first Scala lift off conference, and I found myself in the middle of conversations I would have never expected. The most unexpected conversation of all—during an encounter between Bayesian probabilists and category theorists—had more to do with quantum mechanics than it had to do with Scala. It was nonetheless representative of a wider phenomenon: Scala has drawn the attention of many very different people.

At the conference yesterday there were early Java adopters with a hunch that Scala might be the next "Big Thing". There were dynamic language programmers who found their web applications difficult to scale. There were enterprise Java folks who require the tried-and-true rock-solid stability of the JVM and the Java platform, but find the Java language increasingly stale. There were academic researchers who would rather be using Haskell but need to work with legacy Java code. There were startup people looking for a "secret weapon". There were visionaries dreaming of out-of-the-box "planet-scale" web applications.

Scala can't (and won't) be all things to all people. But Scala is sufficiently interesting that is has caught the attention of very different people from very different backgrounds and with very different priorities. It has succeeded in bringing these people together and gotten them to start conversations. Hopefully these conversations will outlive the conference in which they were born. Hopefully they will grow to include even those who couldn't be here. I can't begin to predict where these conversations will lead, but I can tell you that I'm excited... very excited.

Michael Galpin on Scala and XML, and some notes on xml.pull

Michael Galpin has written a nice overview of Scala and XML on developerworks.

I wish he would also have gone into the scala.xml.pull package, but then I really should write documentation for it instead of leaving this to others.

The point of pull-parsing is of course to avoid building up an in-memory representation of the XML. We might want to avoid is because

• the XML data is just too large, or


• because we know that we are going to throw most of it away (garbage) and need the performance gain implied by not even allocating the garbage.

There are alternatives, for instance implementing the SAX-like MarkupHandler. However, MarkupHandler and SAX are examples of push parsing, and sometimes dealing with the sequence of events explicitly is more lucid than having some Handler class and managing state of the handler with lots of control variables.

In absence of more elaborate documentation, here is the example from the scaladoc of XMLEventReader.scala comment and from the test, in the hope they provide some insights in what pull parsing is. I should really give a more thorough example, but then there are excellent articles on the net describing pull-parsing (e.g. check out Elliotte Rusty Harold on Stax, from just a couple of years ago). That article also shows IMHO that pulling XML events is even more useful and readable when used with pattern matching. I will let somebody else drive that point home, here now the scala doc.

A pull parser that offers to view an XML document as a series of events.

  import scala.xml._
  import scala.xml.pull._
  import scala.io.Source
 
  object reader {
    val src = Source.fromString("")
    val er = new XMLEventReader().initialize(src)
  
    def main(args: Array[String]) {
      Console.println(er.next)  // print event for start tag hello
      Console.println(er.next)  // print event for start tag world
      // ...
    }
  }

Events are described in file XMLEvent.scala.

Happy XML pulling ;)

Where is Scala heading?

This is my first post on Scala Blog, so sorry if it's too philosophical. I promise to show some substance soon :)

As I'm learning my way with Scala one analogy cannot escape from entering my thoughts. The analogy is (of course?) Haskell.

However I don't mean the way the language is built up, but rather the way it's governed. Both Haskell and Scala are designed and implemented by brilliant scientists, who are the benevolent dictators when it comes to choosing the language features. In the Haskell case it's the Simon Marlow and Simon Peyton-Jones behind the GHC compiler along with a very active community with a lot of outstanding members. In the Scala case it's Martin Odersky and the LAMP.

Such a setup means that the language leaders are highly aware of the decades of computer science research and can pick the best and innovate on top of it. This is great, because you get substance instead of the buzzwords. However this also means that they are driven by success in research community.

What is the problem with that? Well, Martin is the professor at LAMP, which today means he has to teach and produce papers. However, to publish papers one must be constantly innovative, since CS conferences do not readily publish just case studies and tech reports. Since his main focus seems to be Scala it means that the language is constantly evolving to accommodate the innovation needed to get published.

The drive for innovation by itself is wonderful. However a programming language is a relatively fragile thing, since it must fit into the imagination of potentially millions of people. But when it's constantly improving it is hard to fit it in. Just look how much trouble introducing Generics caused to Java programmers.

The reason why I started with Haskell is that situation in that community is even more extreme. While Haskell 98 report standardized a relatively conservative language almost everyone today will use the GHC extensions. And those take by now the largest part of the GHC user guide and are often underdocumented and hard for a newcomer (and sometimes an experienced Haskeller) to understand.

The Scala changes are perhaps not so extensive and we are definitely dealing with a more practical language, but still the change log in the end of Scala spec makes for quite a long read. And since I love the language itself and the people behind it I would be very interested to know what are the goals and how long will Scala continue to evolve before slowing down.

(also at dow.ngra.de)

Scala class at Stanford

I am pleased to announce that Ben Newman, Julien Wetterwald, and I will be teaching CS94SI: Cross-Paradigm Programming with Scala, a student-initiated course at Stanford University this coming Spring. As the name suggests, the course will focus on how Scala can be used to program with several programming paradigms (functional, object-oriented, concurrent, domain-specific, etc.).

If you have any experience teaching Scala, in an academic setting or otherwise, I'd love to hear about your experiences at jorge.ortiz@gmail.com.

<Lecturer Details>
Ben is pursuing a Masters degree in Computer Science at Stanford with a specialization in Software Theory. He has a passion for programming languages and has extensive teaching experience, having been a teaching assistant for CS106A, CS107, and CS156 at Stanford.

Julien is also pursuing a Masters degree in Computer Science at Stanford with a specialization in Software Theory. His main areas of interest are programming language design and compilers. As an undergraduate at EPFL, he was a teaching assistant for Martin Odersky's class Programmation IV, taught in Scala. He has used Scala to write a compiler and a domain-specific language for graphical user interfaces.

Jorge graduated from Stanford with a Bachelors in Symbolic Systems in June 2007. During his time there he helped teach CS106A, CS106X, and CS107. He is a contributor for http://scala-blogs.org/ and the lift web framework, written in Scala. He uses lift and Scala every day at work.
</Lecturer Details>

<Course Details>
No previous exposure to Scala is required, though we do ask that students have studied at least two programming languages in an academic setting (CS107 is recommended; CS 242 may increase your appreciation for the class). Students will be expected to complete a final project of their choosing. The one-unit class will meet Wednesdays from 4:15-5:45pm in Gates 260. Stanford students can register for CS94SI on Axess.
</Course Details>

lift 0.5, now with Blueprint CSS beauty, jQuery excellence, and JSON goodness

Folks,

I am pleased to announce lift version 0.5.

lift is an expressive and elegant framework for writing web applications. lift stresses the importance of security, maintainability, scalability and performance, while allowing for high levels of developer productivity.

Demo: http://demo.liftweb.net

New in version 0.5:

• jlift JavaScript utilities and associated binder helpers


• Blueprint CSS built in (version 0.6 of Blueprint CSS) so it can be served via /classpath


• XML -> JavaScript bindings so that JSON -> XHTML rendering can be defined using Scala XML literals, but the resulting JavaScript code can be sent to the browser to do mass rendering of JSON objects


• JSON support including: - S.buildJSONFunc - JSONHandler class - Lots of fancy JavaScript expression building


• Parser Combinator Helper routines


• ByList query term


• Support for serving certain common files (e.g., jQuery, Blueprint CSS) right from the JAR/WAR file


• MappedText and MapperFakeClob classes for storing very long text fields in the database

Changes include:

• Revised the example site to use Blueprint CSS for style


• When lift is running in test mode, the default form generators will insert lift:field_name attribute into the form fields to aid in testing


• Added json2.js (and minified version) Enhanced the resource serving stuff so that: - The path is defined in LiftServlet and changable (defaults to "classpath") - Moved the resource location from the root to "toserve" (can be changed) to avoid any possible way of serving up classes - The white list is a Partial Function for more flexibility - The white list by default contains jquery.js and json.js - There's a re-writer to re-write the request into an actual file (so jquery.js gets re-written to jquery-1.2.2-min.js)


• MappedField.toForm now returns a Can[NodeSeq ] so a field can be omitted from a form


• Added LocInfo and LocInfoVal to SiteMap for storing CSS and other tidbits about each menu item


• Fixed the 'Welcome to the your project' type-o


• Further abstracted the whole logging thing. There's a default log4j setup that can be override The LiftLogger trait is made concrete in Log4JLogger, but the generic LiftLogger creation is done by function that can be modified in LogBoot: var loggerByName: String => LiftLogger = _logger var loggerByClass: Class => LiftLogger = _loggerCls One can insert a new logging system into lift by replacing the loggerByName and loggerByClass functions with appropriate functions that return a LiftLogger.


• Extensive updates to the <lift:xxx /> tag mechanism that uses tag labels as snippets and support for adding arbitrary tag handling to lift.

The lift community has grown to over 400 people. There are a number of lift-based project in development including http://much4.us which makes use of lift's Comet, AJAX, and JSON support.

Thanks to the excellent, talented team of lift committers including Jorge Ortiz who was build-master for this release, Steve Jenson who keeps adding practical things to lift, and the rest of the lift team.

Please take a look at lift 0.5, join the lift community, and give us some feedback!

Thanks,

David

From Regexps to Regexp Patterns, still functional

Here now is the long overdue follow-up to "RegExp but no state machine". Remember, we were talking about regular expressions: state machines come to mind, and we hurry to the cabinet with the imperative chainsaw, but it turns out that some scalpel-like pure functions can be used to cut the problem as well.

Binding Variables

Quite often, we are not just interested in the boolean answer to the question "did this input match the regexp?". We also want to know the parts that matched parts of the regexp, as in "if the file ends in .txt, put its name without the extension into variable x". In other words, we want to bind variables to parts of the input, depending on how the input matched. Regexps that contain variables deserve to get a beautiful and original name: let us call them regexp patterns.

You want to see an example that is not buried in natural language? We can do that... I will use Scala syntax, but keep in mind that regexp patterns in Scala are
undergoing a redesign - these example are just here to explain regexp patterns.

 
def just_the_name(name:Seq[Char]) = name match {
  case Seq(filename @ _*, '.', 't', 'x', 't') => filename
}

Matching regexp patterns is a bit more involved than matching regexps. That is not apparent from the above, tame example, but what about something like this

def is_backup(name:Seq[Char]) = name match {
  case Seq(_*, bak @ (() | ('.','b','a','k'))) => !bak.isEmpty
}

There are two ways that the input name can match the regexp patterns, a fact that is cleverly used to return a boolean to the caller. When there are many or-patterns and "wildcard_star" patterns, the number of possibilities can grow very large.

Back to Business

Maybe regexp patterns will be resurrected soon in Scala, for now, let us focus on the problem and its functional solution. We will write a Scala program that matches regular expression patterns.

Here is code to represent regexp patterns. It uses the RegExp classes defined before (a complete listing that you can compile in one go is provided at the end).

abstract class Pat[A]
// v is the variable (represented as Int), w the prefix that was
//  already seen, r the remaining part we yet have to match
case class PVar[A](v:Int, word:RegExp.Word[A], re:RegExp[A]) extends Pat[A] {
  override def toString = "x"+v+"@"+re.toString
}
case class PPair[A](left:Pat[A], right:Pat[A]) extends Pat[A]
case class PChoice[A](left:Pat[A], right:Pat[A]) extends Pat[A]
case class PatNil[A] extends Pat[A]
case class PatCons[B](hd:B, tl:List[B]) extends Pat[B]

As the comment says, these pattern representation is interesting: it does not only represent regexp patterns, but also partial matches of inputs. When we write down a regexp pattern, the "word" field of PVar will be empty. During the matching, as input becomes available, the different possibilities of going through the input will correspond to different instances of Pat.

Let us try how that would look for the is_backup example. To keep things short, we turn the pattern into x@'A', y@(()|'B')). We match the input A against the pattern, and see how we would go about this. We freely add the empty sequence () where it is appropriate.

Is the first letter of A consumed by x@'A', y@(()|'B'))? Yes, and it is bound to x.
Is () consumed by y@(()|'B'))? Yes, and nothing is bound y and we are done.

Now the same with AB

Is the first letter of AB consumed by x@'A', y@(()|'B'))? Yes, and it is bound to x.
Is the first letter of B consumed by y@(()|'B'))? Yes, and B is bound y.
Is () consumed by ()? yes and we are done.

So we want to step character by character through the input, and
keep track of the bindings by rewriting our patterns -- this is were the partial derivatives come into play. A function pdPat will rewrite a pattern with a partial derivative (the partDeriv function was explained before, in "RegExp but no state machine".)

  def pdPat[A](pat:Pat[A],c:A):Pat[A] = 
    pat match {
      case PVar(x, w, r) => PVar(x, w:::List(c), partDeriv(r, c))
      case PPair(p1, p2) => 
        val pn = PPair(pdPat(p1, c), p2)
        if (acceptsEmpty(strip(p1)))
          PChoice(pn, PPair(mkEmpPat(p1), pdPat(p2, c)))
        else
          pn
      case PChoice(p1, p2) => PChoice(pdPat(p1, c), pdPat(p2, c))
    }

In short, this function takes a regexp pattern and a character. It goes through the regexp pattern and constructs the partial derivative of its underlying regexp. When it needs to keep track of a binding (case PVar), it does so by appending the character at the end. It uses the functions mkEmpPat (which means matching against empty input and makes the regexps disappear or fail in a regexp pattern, but keeps the bindings that were computed before) and strip, which just gives us the underlying regexp and ignores all variable binding stuff that might be going on.

Exercise: write a function that computes the result of accepts_empty(strip(p)) directly, without constructing a regexp first.

The Full Monty

Here now, without further ado, the full example (including stuff from the first part). As always, it might be instructive to run to try out with your own examples, execute step-wise in your IDE debugger (Eclipse and Netbeans), or, the classic, insert lots of println statements.

Note that different possibilities of feeding an input character to a choice are tracked by return a list of environments. The "longest match" and the "shortest match" policies can be recovered by selecting a special element of the list of environments that is the end result of running the patMatch function.

object RegExpPat {

  // from part 1

  type Word[A] = List[A]

  def matchRegExp[A](re:RegExp[A], w:Word[A]): Boolean =
    w match {
      case List() => acceptsEmpty(re)
      case c::w1  => matchRegExp(partDeriv(re, c), w1)
    }

  def acceptsEmpty[A](re:RegExp[A]): Boolean =
    re match {
      case Phi() => false
      case Empty() => true
      case Choice(r1,r2) => acceptsEmpty(r1) || acceptsEmpty(r2)
      case Seq(r1,r2) => acceptsEmpty(r1) && acceptsEmpty(r2)
      case Star(r) => true
      case L(_) => false
    }

  def partDeriv[A](re:RegExp[A], c:A): RegExp[A] = {
    (re, c) match {
      case (Phi(), _)                => Phi()
      case (Empty(), _)              => Phi()
      case (L(c1), c2) if (c1 == c2) => Empty()
      case (L(c1), _)                => Phi()
      case (Choice(r1,r2), c)        => Choice(partDeriv(r1,c),partDeriv(r2,c))
      case (Seq(r1,r2), c)           =>
        val rn = Seq(partDeriv(r1,c),r2)
        if (acceptsEmpty(r1)) Choice(rn, partDeriv(r2,c)) else rn
      case (rs @ Star(r), c)         => Seq(partDeriv(r,c),rs)
    }
  }

  abstract class RegExp[A]

  case class Phi[A]() extends RegExp[A]
  case class Empty[A]() extends RegExp[A]
  case class L[A](letter:A) extends RegExp[A]
  case class Choice[A](left:RegExp[A], right:RegExp[A]) extends RegExp[A]
  case class Seq[A](left:RegExp[A], right:RegExp[A]) extends RegExp[A]
  case class Star[A](exp:RegExp[A]) extends RegExp[A]

  // part 2

  abstract class Pat[A]
  // vx is the variable (represented as Int), w the prefix that was
  //  already seen, r the remaining part we yet have to match
  case class PVar[A](v:Int, word:Word[A], re:RegExp[A]) extends Pat[A] {
    override def toString = "x"+v+"@"+re.toString
  }
case class PPair[A](left:Pat[A], right:Pat[A]) extends Pat[A]
  case class PChoice[A](left:Pat[A], right:Pat[A]) extends Pat[A]
  case class PatNil[A] extends Pat[A]
  case class PatCons[B](hd:B, tl:List[B]) extends Pat[B]

  // combinator
  def pat_var[A](n: Int, r:RegExp[A]) = PVar(n,List(),r)

  // binding
  type Env[a] = List[(Int,Word[a])]

  def patMatch[A](pat:Pat[A], word:Word[A]):List[Env[A]] = {
    (pat,word) match {
      case (p, c::w) =>
        patMatch(pdPat(pat, c), w)
      case (PVar(x,w,r),List()) =>
        if (acceptsEmpty(r)) List(List((x,w))) else List()
      case (PChoice(p1,p2), List()) =>
        patMatch(p1, List()):::patMatch(p2, List())
      case (PPair(p1,p2), List()) =>
        for(xs <- patMatch(p1, List()); ys <- patMatch(p2, List())) yield xs:::ys
    }
  }

  def longPatMatch[A](pat:Pat[A], word:Word[A]):Option[Env[A]] =
    patMatch(pat,word) match {
      case env::_ => Some(env)
      case _      => None
    }

  def shortPatMatch[A](pat:Pat[A], word:Word[A]):Option[Env[A]] =
    patMatch(pat,word) match {
      case List() => None
      case xs     => Some(xs.last)
    }

  def pdPat[A](pat:Pat[A],c:A):Pat[A] =
    pat match {
      case PVar(x, w, r) => PVar(x, w:::List(c), partDeriv(r, c))
      case PPair(p1, p2) =>
        val pn = PPair(pdPat(p1, c), p2)
        if (acceptsEmpty(strip(p1)))
          PChoice(pn, PPair(mkEmpPat(p1), pdPat(p2, c)))
        else
          pn
      case PChoice(p1, p2) => PChoice(pdPat(p1, c), pdPat(p2, c))
    }

  def strip[A](pat:Pat[A]):RegExp[A] =
    pat match {
      case PVar(_,w,r) => r
      case PPair(p1,p2) => Seq(strip(p1),strip(p2))
      case PChoice(p1,p2) => Choice (strip(p1),strip(p2))
    }

  def mkEmpPat[A](pat:Pat[A]):Pat[A] =
    pat match {
      case PVar(x,w,r) =>
        if (acceptsEmpty(r))
          PVar(x, w, Empty[A]())
        else
          PVar(x, w, Phi[A]())
      case PPair(p1,p2) => PPair(mkEmpPat(p1), mkEmpPat(p2))
      case PChoice(p1,p2) => PChoice (mkEmpPat(p1), mkEmpPat(p2))
    }

  // example for testing
  val the_choice = Choice(Empty(), L('B'))

  val ex = PPair(PVar(1, List(), Star(L('A'))), PVar(2, List(), the_choice))

  def main(args:Array[String]) {
   println(longPatMatch(ex, List('A')))
   println(longPatMatch(ex, List('A','B')))
  }
}

Oh, did I mention that there is no mutable state involved?

Credit: The functional implementation described here follows Kenny Zhuo Ming Lu and Martin Sulzmann. A toast to them! Several people, including myself, found similar solutions, but they are the heroic ones that implemented and proved it all.

Guide to the Scala Community

One of the most intriguing things about Scala is the people who are working with it. I have been following Scala mailing lists over a year, and was impressed by the helpfulness and positive attitude of the people involved. Very few are the times I've seen personal attacks, if any. Also the people at EPFL who are responsible for creation of Scala have given lots of insight why things are done way they are, or why is feature X not implemented. They have even changed Scala rapidly to support other people's ideas.

This blog entry is mainly meant for a Scala beginner as a guide. I try to familiarize you with different ways of interaction with other's in Scala related things, and to get you know about user written faciliation tools and (upcoming) libraries. Any suggestions how to extend this post are appreciated, of course.

First of all, there are the mailing lists. At the moment there are many of them, and it's hard to tell sometimes to which should one post, because the ambiguity of division. But better to post somewhere than to nowhere. Here are the most important:

The main list is scala, and it's for general Scala related discussion, e.g. standard library, language changes, or implementation issues.

scala-user is mostly for newbie questions, and also for specific technology related discussion, also stories of experience of Scala programming.

scala-debate is mostly for discussion that is specific in kind, in which not many people are interested. It's also excellent place to discuss programming theory, future and ideas of improvement for Scala. The discussion seems to be there the most relaxed of all lists, and lots of 'lambda the ultimate' kind of persons are lurking there.

To see guidelines how to interact with the above mentioned and other mailing lists see this page.

The mailing lists are the best places for you to ask questions, or give suggestions, and of course help others. But if you have found a bug e.g. in the compiler, the lists are rarely the best place to announce them. You should just see if there exists a bug report in Trac, and if not, create one. It won't go unnoticed, and will most definitely be appreciated! But in special circumstances it's ok to discuss them too, or ask whether you have found a bug or not.

Please don't get offended if nobody answers your question; it's likely that the question is hard to answer, or it was sent at an unfortunate time, and was forgotten. It's not crime to ask again...

For those who like to chat, the irc channel #scala @ freenode is the place to go. There's at least couple of active guys who try to give their best in helping you. Again, please be patient with your question.

The blogs about Scala are of course not to be forgotten. Here's the most interesting ones I've come up with:

• Tony Morris, a functional programming enthusiastic, has written interesting Scala software and given nice introductions to subjects like implicits: http://blog.tmorris.net/.
• David Pollak talks about Scala webframework lift.
• James Iry knows how to give description of Monads, and their usage: One Div Zero
• David MacIver has interesting theoretical insights to Scala: Desperately Unenterprise
• My own blog Scalada, and my example site Scalad
• Rumination's of a Programmer has lots of examples how to use Scala by Debasish Ghosh.
• Alex Blewitt's introductions for beginners
• Daniel Spiewak's Scala for Java Refugees articles
• Scala Buzz contains lots of Scala related weblogs
  
• Scala wiki has examples, and answers to frequently asked questions.
• Scala Blog - 'nuff said.
  

If anyone knows other good ones, I'd be happy to hear about them.

Now you know some of the people dealing with Scala. Next I'll give you some pointers to faciliation tools:

One of the most useful tools is a simple seach facility for Scala API. Even though it could be so much more, it's already good as is: API Seach tool. And for those who need to show short samples of code to others, e.g. in IRC discussion, a pastebin is very useful, and this one can even colorize the Scala syntax: Scala Pastebin.

Moreover, even though Scala standard library is very important, there's huge amount of useful general tools a programmer needs that can't be found from the standard library. Of course there's also Java API that can be utilized, but it doesn't let use all Scala features smoothly unless wrappers are explicitly written. That's why some clever guys started a community based library, called Scalax. I emphasize it's in its early phase, and encourage you to just wait until it's in better shape, unless you're enthusiastic and want to contribute to it. Moreover, there's another non-related publicly available Open Source code project named Scalaz, which somewhat overlaps with Scalax in its functionality. The design is however different, and you can get the better of both worlds if needed.

Of course I shouldn't forget the best open source real world example Scala has to offer yet: Lift webframework. There's also Scala-tools.org where Scala Open Source projects can be added, as far as I know.

Text editing tools, including IDEs, are numerous. For lightweight editors you can find a Scala configure file in the Scala distribution in [Scala]/share/scala/support/. IDEs are at the moment in development, but some are usable, for example Eclipse plugin which will have its newest, highly improved version out soon (update: it's in public testing now, see wiki. You can also read the progress of Netbeans plugin here.

I hope these descriptions helped you to get a better understanding where to go in the Scala world. By writing articles like this I try to give my humble support to this community, which I so enjoy being part of.