Algorithmically challenged

String Interpolation on Scala 2.10

2012-01-23T18:18:00.000-02:00

One of the Scala Improvement Proposals for Scala 2.10 is String Interpolation. It has recently been added to trunk, behind the -Xexperimental flag, and I have started playing with it. At first, I stumbled upon bugs and limitations of its current implementation relative to the proposal, but I finally got something working.

To be clear: the interpolation works fine, in both of the provided forms (with and without formatting). As usual with Scala, it's the possibility of replicating the functionality for my own purposes that gets me excited. I usually explain the whys and the hows of my code, but in this case a simple paste says it all, imho.

dcs@ayanami:~/github/scala (master)$ scala -Xexperimental
Welcome to Scala version 2.10.0.rdev-4232-2012-01-23-g9a20086 (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_26).
Type in expressions to have them evaluated.
Type :help for more information.

scala> case class StringContext(parts: String*) {
     |   object matching {
     |     def unapplySeq(s: String): Option[Seq[String]] = {
     |       val re = (parts map ("\\Q" + _ + "\\E") mkString ("^", "(.*?)", "$")).r
     |       re findFirstMatchIn s map (_.subgroups)
     |     }
     |   }
     |   def s(args: Any*) = scala.StringContext(parts: _*).s(args: _*)
     | }
defined class StringContext

scala> "23/01/2012" match { case matching"$day/$month/$year" => s"$month-$day-$year" }
res0: String = 01-23-2012

Adding methods to Scala Collections

2012-01-09T21:50:00.001-02:00

I don't like getting much involved in these Scala flame wars, but this recent article left me a bit irked. At some point, the following statement is made:

"it is impossible to insert a new method that behaves like a normal collection method. "

So, for the record, that is just not true. Here's an implementation for the filterMap method:

import scala.collection._
import generic.CanBuildFrom
import mutable.Builder
 
class FilterMap[A, C <: Seq[A]](xs: C with SeqLike[A, C]) {
     def filterMap[B, That](f: A => Option[B])
                     (implicit cbf: CanBuildFrom[C, B, That]): That = {
       val builder: Builder[B, That] = cbf()
       xs foreach { x => val y = f(x); if (y.nonEmpty) builder += y.get }
       builder.result()
     }
 }
 
implicit def toFilterMap[A, C <: Seq[A]](xs: C with SeqLike[A, C]): FilterMap[A, C] = new FilterMap[A, C](xs)

Is this what the author wanted? No. He wanted too add a method that behaved like a normal collection method to something that isn't a collection. This is so crazy that, not surprisingly, people are misunderstanding him.

Now, one may come up and say that Scala does do that (add methods to stuff that are not collection), with String and Array. Yes, it does, and it does so by creating a completely new class with all these methods for each of them. Rest assured that if I create a completely new class for each one, I can add filterMap to String and Array too.

Using Scala API Documentation

2011-12-27T16:27:00.005-02:00

One link that was missing from my post about Scala on the Web was the link to the Scala API documentation, often called "scaladoc" for short, after the tool that generates it. I tried to put it in, but it kind of broke the narrative and, to be honest, I have a lot to talk about the subject. So I decided to do a whole blog just about it.

First of all, there are two main links that you can use to access it:

Most of the time, I prefer the second link: it contains improvements to the Scaladoc tool, and the documentation often contains improvements. On the other hand, being a nightly release, it is subject to regresssions in the Scaladoc tool, and the documentation contains information that is not correct for the latest release. For that reason, I keep both links in my bookmarks.

So, what else is there to say? Well, if you are new to Scala, a lot. Those familiar with the Java equivalent probably find it both familiar and strange: the screen is divided into left and right sections, the right section having description of classes and packages, while the left contains a list of them. Whereas Java splits package and class lists, however, Scala does not. And, of course, the look is completely different. These, however, are skin-deep differences, and I want to get to the bones of the matter.

One Doc, Two Frames

The first thing I want you to notice are the two search boxes: one on the left, at the very top of the page, and one on the right, a bit lower. Scaladoc is search-oriented! That means you usually don't browse it, looking for stuff, but just type what you want. You can still browse, of course, which is useful when you don't know what you are looking for.

On the left side you have the package hierarchy and classes, traits and objects belonging to the packages. Note that classes, traits and objects can be members of other classes traits and objects, in which case they won't appear on the left.

The right side contains information about a selected package, trait, class or object. The URL will change to match what is being displayed on the right side of the screen, so that you can easily bookmark or share links to specific class or object. At the present, there's no way to further refer to a member of a class, such as a specific method. This improvement will be added at some point in the future.

Typically, you'll search or browse for a class on the left side of the screen, and then browse its contents on the left, or further search for a particular member of that class.

The Left Frame

Let's drill down the left side, then, to get a better understanding of what's there and how to use it. At the top of the left frame, you'll see this:

Topmost is the search box, with a little "x" icon on the right hand to clear the search. Searching for something will hide any traits, objects and classes that don't match, as well as any packages that don't have any matching members.

Right below that is an index of all existing methods. Click on a letter and you'll get all methods starting with that letter, and the places they are defined at. Click on the hash symbol (#), and you'll get a page with all methods starting with a symbol instead of a letter. For example:

Finally, you have a small caption saying "display packages only". Surprisingly, that's a clickable option. In fact, ScalaDoc is full of clickable parts, so if you are getting familiar with it, my advice is to try to click stuff, just to see what happens. Back to that caption, though, it switches the package hierarchy from displaying all entities to displaying packages only. Clicking it will give you something like this:

If you click on "show" on one of these packages, it will open up that particular package. If you click on "display all entities", it will revert to the initial mode of display.

Speaking of "show", let's now look at the various parts of the entities list:

The darker background indicates package or package objects, and the entities on the lighter background right below it are the classes, objects and traits belonging to that package, as indicated by the icons on their left. Note that, though package objects have other members such as methods, they do not appear on the left frame of Scaladoc.

The icons for "o", "c" and "t", in dark blue, green and light blue respectively, indicate objects, classes and traits. A name can be shared between an object and a trait or class, as seen for Regex above. Traits and classes cannot share the same name, however, so each name will have at most two icons beside it.

If you are not familiar with Scala, an object is a singleton, containing what, in Java, would be represented as static.

One thing to realize here is that everything in that image is clickable, except whitespace. You can click on "scala.util.matching" and "scala.util.parsing.combinator", on "hide" and "focus", on "Regex" and "RegexParsers", and on the icons.

Clicking on a package name will show its traits, classes and objects on the right frame, unless the package is a package object, in which case the right frame will show the other members it might have. This is important because many package objects contain implicit definitions used as helpers with that package. Check, for instance, scala.sys.process.

Clicking on "hide" will hide the entities belonging to that particular package, but not any subpackage that might exist. The text will then change to "show", which will revert this action upon being clicked.

Clicking on "focus" will hide all other packages from view, like this:

Clicking on the "x" icon that appears will revert this action.

Clicking on an icon for object, class or trait will show information for it on the right frame, as will clicking on the text itself. If an object shares a name with a trait or class, however, clicking on the text will show not the object, but the class or trait, following the assumption that this is what people want most of the time.

On recent ScalaDoc versions, clicking on an entity will also move the focus to the search box on the right frame, so that you can instantly type

The Right Frame

To begin the discussion of the right, I picked GenSeq, which is rich enough in ScalaDoc UI components, but (relatively) poor enough in actual content to fit in here.

You may have wondered why the search box is not at the top on the right frame, like it is on the left. The reason for it is our starting point in explaining the right frame.

The right frame is divided in three parts, the topmost two being shown above. The first part contains general information about the selected entity, and it comprises everything from the top until right before the search box. The second part starts with the search box, and is comprised of everything in that gray background. This part contains display options that affect the third part of the right frame. The third part contains all members of the selected entity, with individual information for each one.

From the top, then, we have a green or blue background (the former for traits and classes, the latter for objects, packages and package objects) on which the name of the entity is prominently displayed. A big icon beside it indicates what kind of entity it is: t for traits, c for classes, o for objects and p for packages and package objects alike.

If the icon is slightly folded on the bottom, like the one in the example, clicking on it (or the entity name) will switch the right frame to the companion of that entity. If you are not familiar with Scala, objects, traits and classes that share a name are said to be companions to each other. Clicking on the GenSeq trait above, then, will display the GenSeq object.

In a smaller font above the entity name is the full path to that entity. Clicking on a path component will display that component.

After that, in a gray background, comes a description of all classes, traits and type parameters used in the definition of that entity. It does not list classes or traits that are inherited -- that is available further below. Not to sound too repetitive, but clicking on any of the classes and traits will display it... Also, moving the mouse over one of these names will show the full path for that name.

What follows is the full description and attributes associated with that entity. I deliberately choose one extremely poor in those, so that I could concentrate on what ScalaDoc provides. One of those things is the link to the source code in which that entity is defined. Not all Scala projects provide that attribute, but Scala API itself does. The link currently points to the web interface to the old Subversion repository -- I presume this will be switched to the new repository on Github in the near future. At any rate, all niceties of source version control systems are available on that link. For the Scala API, anyway.

"Linear Supertypes" and "Known Subclasses" at the bottom of this part can be expanded upon click, to display the exact linearization of an entity's supertypes -- the inheritance precedence -- and all known subclasses. For example, for List it will show this:

Also shown above is the tool tip indicating the full path of one of the supertypes being pointed at, just like mentioned above for entity declaration.

Let's now look at the second part of the right frame:

The search box works pretty much like the one on the left frame, hiding anything that isn't a match, but it includes descriptions on the search as well. Search for a verb, therefore, will often yield good results, unless the verb is too general.

One particularly nice feature, available on recent versions, is that typing multiple words will search for matches of any one of the words, which makes it easy to display two methods close together on the screen.

All other options below the search box also change the way things are shown in the third part. The default Ordering mode, Alphabetic, will display all non-private members of an entity, separated in categories which we'll shown below, in alphabetical order. This is different than Java, which only shows full information for members defined or overridden on that class/interface.

Clicking "By inheritance" will change the display mode to separate the members according to where it was last defined/overridden. Full information will still be displayed, and the members will still be shown in alphabetical order in their own section.

The Inherited options let you easily filter out inherited methods. Clicking on "Hide All" will toggle off all supertypes, leaving only the entity itself selected. This will hide methods that are not abstract, defined or overridden on the entity. For GenSeq, for example only two methods will be displayed: seq and companion.

Note that clicking on "Show all" will not select AnyVal, AnyRef or Any. Because the methods defined on these are available on pretty much everything, one rarely needs to see these methods.

Because many times you might be interested in a particular aspect of an entity, you can also toggle each supertype individually. You can do so to display the methods on Any, for example, or you could look into what Function1 has to offer to List.

The last option, Visibility, will toggle between displaying only public members and everything except private members.

The last part of the right frame, as mentioned, contains all members of that entity. These are divided into type members and value members. A type member is a trait, a class or a type, and value members are everything else. For example, the object Regex contains this:

Note that anything that shows up as a type member of anything but a package will not be displayed on the left frame, even though you can display it on the right frame by clicking on a link to it.

Value members are actually divided in three separate sections: abstract value members, concrete value members and deprecated value members. These are shown in that precise order, so that one can easily see all members that must be implemented to make a concrete class, and don't get the screen polluted by methods they shouldn't be using -- deprecated methods -- when browsing.

Let's look at some important points of value member definitions. The snapshot below was taken from a List with members filtered by "map":

By default, only a member's definition and the first sentence of its description are shown, like method groupBy above. Clicking on either the small arrow on the left or on the definition itself will show the full information for that member, as seen in the two definitions for map.

Since Scala supports method overload, methods can have multiple definitions. In this particular case, however, the first definition is not a real one -- this is indicated by the [use case] tag. It is important to understand what use cases are, for two reasons: first, they represent the most common way to use the method, and, second, they are lies. Well-meaning lies, but lies.

Compare the definition of the two map methods shown. Clearly, the second definition has a lot going on, whereas the first definition is pretty clear: on a List[A] (see definition for List), the map method takes a function that converts an A into a B, and returns a List[B].

Though that definition works very fine for List, the map method is not defined on List, but much higher on the hierarchy. And what works for List won't work for a BitSet, for example: since a BitSet is a Set[Int], if you map those Int into String, you won't be able to return a BitSet! After all, a BitSet cannot be a Set[String]. The same thing happens in other cases: a WrappedString is a Seq[Char], a Map[A, B] is a Iterable[Tuple2[A, B]] (aka Iterable[(A, B)]), etc. In any of these cases, a map definition like in the use case won't work.

So the actual definition of map is the second one, which can handle all of these cases. If you need precise information about map -- for example, if you are extended Scala collections -- you can look it up. On the other hand, if you just want to know how a method is used, the use case should be much easier to understand.

Most of the remaining information is pretty obvious: a description follows, and then various attributes describing how parameters are supposed to be used, what the return type is, etc.

The final interesting thing here is the Definition Classes shown below each method. This only appears when a method has been inherited from elsewhere, and it indicates both where it was originally declared (which might have been as abstract), and all places where it was overridden, ie, the implementation has been changed.

And this concludes the tutorial on using the Scala API documentation, as well as the docs for any other library written in Scala. Looking back, it is much longer (and took much more time to write) than I first thought. Yet, rest assured that using ScalaDoc becomes second nature very fast!

Scala on the Web

2011-12-23T16:26:00.001-02:00

I was wondering how to approach Scala on a dojo about it, and I kept returning to the idea that I should first introduce Scala on the Web. So, how would I go about it? What sites would I mention? Scala has grown such a rich ecosystem around it since I first started using it that I'm actually feeling a bit lost nowadays. And, let me tell you, that's a nice change! :-)

Nevertheless, the problem remains. As I started compiling the sites in my head, I quickly realized I'd have to write it down somewhere, and where better than in my own, dusty blog? So, here it is: the DCS guide to Scala on the Web!

For a long time, the starting point and central hub to Scala resources has been the Scala-Lang site. From there you can download Scala, find documentation, guides, support information, news... and it has become dated. Mind you, it still is a great resource, but some alternatives -- some official alternatives! -- have emerged since then.

One of them is Typesafe. Typesafe is a startup created around supporting Scala and related technologies. While this might not sound like a starter resource, they provide the Typesafe Stack, a set of tools including not only the language, but also Eclipse support, a build tool, a distributed system framework and a web framework. I think they plan to add more elements to it, but, anyway, go to their DOWNLOAD link and you'll have Scala up-and-running in no time.

Another important resource is the Documentation Site. A newly designed site to replace the old one on scala-lang. Scala-lang even has a link to it, though it still keeps the old one as well. Here you'll find guides, tutorials, cheatsheets, FAQ, and even a glossary of Scala terms and a Scala Style Guide. Oh, and a link to the Scala Wiki as well.

While on the wiki, please pay close attention to the Tools and Libraries page. You might not find everything there, and you might find things that have not been kept up-to-date, but even so it is an invaluable resource.

And speaking of FAQs, some brave souls took the time to compile Stack Overflow Scala Tutorial! The thing is nothing short of amazing: dozens, maybe more than a hundred of the most important questions categorized in 31 different topics, from "Introduction to Scala" to "Functional Scala", with a side dish of five additional topics for further learning.

By the way, if you don't know Stack Overflow, it is a question&answer site about programming questions -- only it actually works and is enjoyable to use, as opposed to their competition. More importantly, the Scala community is well represented on Stack Overflow, and you can use it to get questions about Scala answered in no time. In fact, it has probably been asked and answered already. :-)

The only problem with Stack Overflow is that it doesn't search for symbols, and Scala has a fair share of them. If you have a question about a symbol, use the Symbol Hound site to search for it.

What else? Well, there's Planet Scala, a blog feed aggregator, and Implicit.ly, a feed of Scala projects that is automatically fed by a plugin on the build system. It doesn't contain all Scala projects, of course, but it goes a long way.

And if you want to try Scala without ever installing it, there's Simply Scala, a Scala tutorial that let you execute the sample code, as well as try out code of your own.

If you want to get more dee involved with Scala itself, look at its github account. Scala, compiler and library, is there, as well as the documentation site I mentioned earlier.

Ok, I'm sure I left a bunch of sites out (like some news aggregators -- I don't follow them, but if you do, send me the link and I'll put them up), but let's address now some of the basic tools most people will be searching for.

I spoke earlier about a build tool, so let's discuss it a bit. The build tool of preference for Scala is SBT. If you search for it on the Internet, you might come up on the link to the old version (up to 0.7.7), which is hosted on Google Code. The newer versions (0.10.0+) are hosted on Github, and are incompatible with the older ones. Make sure you get the new version.

Alternatively, you may opt to install the SBT Extras script instead. It's the same SBT, but with a starter script that provides a richer set of options. There's also a couple of alternate starter scripts on the SBT site, called "screpl" and "scalas", which uses SBT to load dependencies while starting Scala's REPL (that's an "interpreter" console, so to speak) or starting Scala shell scripts.

You don't actually need to download Scala at all if you install SBT: SBT will download whatever version of Scala you tell it your project uses, requiring only that you have a JVM installed.

What about testing, what should you use? Scala is in the unfortunate position of having two excellent testing frameworks: ScalaTest and Specs2. They are both mature, fully-featured, actively developed and supported, and with big communities. There's no way to recommend one over the other: it really comes down to personal preference.

Both of them also support ScalaCheck, a testing framework that test stuff by automatically generating input and verifying if the specified conditions hold true. ScalaCheck is great to find boundary conditions, and, as mentioned, you can use its checker under both ScalaTest and Specs2.

You can use existing Java mocking frameworks (Specs2 has special support for Mockito, though Specs, the older version, supported JMock and EasyMock as well), but there's a Scala mocking framework available as well: ScalaMock. ScalaMock has advanced features, such as mocking Scala objects (equivalent to Java static members) and even constructors! That means you can actually mock the behavior of a "new" statement without replacing it with factories or dependency injection.

To wrap it up, web frameworks and database access.

Scala has many web frameworks available, and there's even a healthy reuse of components between these frameworks. For instance, Scalate, a templating engine that can even serve as web server on a stretch, seems to be used by pretty much everyone nowadays. But let's look into the main alternatives.

Lift is the oldest one (at least among the more serious frameworks), and has a strong community. David Pollack, It's author looked into a number of successful frameworks and decided to pick the best of the best, add a few twists of his own, and use Scala's power to provide an incredible piece of software. Among Lift's strengths, there's a strong separation of concerns (web page design and code are strictly separated), a seamless AJAX/Comet integration, powerful wizards for common concerns, and a design that took security considerations into account right from the beginning. If you do go with Lift, however, please make use of their mailing list as support -- that is their main support channel, and they prefer to concentrate their help there.

To those who are familiar with Sinatra, there's Scalatra and Bowler, that latter being built on top of the former. And I might well be mistaken, but Circumflex seems to go the same way as well.

If providing a web service is just a small part of your application, you might want to opt for Unfiltered instead. With Unfiltered, the web server is a library in your application, instead of your application being a servlet inside a framework.

And if what you really need are web services to interconnect systems, try Blue Eyes.

Now, there are a lot of other web frameworks, I'll mention just one other. Typesafe has decided to integrate the Play! Framework into its stack. Play! offers the ease of web development that PHP has, but with all the advantages Scala has to offer.

Which leaves us, at last, with databases. Again, there are many options to choose from. If you are doing web development, the framework of your choice probably already has some recommended libraries to deal with it -- their own or others (did I mention that there's a healthy reuse of components? :). I suggest you go with that.

If not, I can make some suggestions. I don't have personal experience with this, so I'm mostly recommending based on what I perceive to be preferred choices with active communities. There's ScalaQuery, which has always been a favorite of mine (just waiting for a project where I can put it to use :). Querulous and Squeryl also get a lot of traffic, but once you get to NoSQL, the main choice seems to be MongoDB's Casbah driver. I have played a little bit with it, and it is certainly quite easy to get up and running for small projects or experiments.

Do look into the existing choices, however, as there might be something better suited to your needs.

And if you haven't payed attention the first time I linked to it, the Wiki of Tools and Libraries is a very good resource to get started on specialized, well, tools and libraries. :-)

If you are new to Scala, I hope this can get you going. If you are experienced, I hope you can use this when helping others. Of course, this post will get old, the links will get outdated, and new cool stuff will come up.

For now, enjoy!

String Interpolation on 2.10?

2011-10-12T15:13:00.000-03:00

Happiness is made of small things...

Welcome to Scala version 2.10.0.r25815-b20111010230908 (Java HotSpot(TM) 64-Bit Server VM, Java 1.6.0_23).
Type in expressions to have them evaluated.
Type :help for more information.

scala> val x = 1
x: Int = 1

scala> "\{x}"
res0: String = 1

Requires the -Xexperimental flag. This test case reveals even more interesting things:

scala> val x = 1.1
x: Double = 1.1

scala> println("We have a \{ x ;2.2f}% chance of success")
We have a 1,10% chance of success

Mind you, there's a lot of things that have been hidden behind -Xexperimental, some of them for a long time now, and some of them ended up canned.
Edit: The proposal for this extension can be found here.

A quick detour through Grub and choosing default operating system

2011-08-30T10:26:00.001-03:00

I'm going to do a quick detour to talk about grub.

Grub is the boot manager of choice for Linux systems, and the one installed by default by Ubuntu, among others. My desktop at home dual boots between Ubuntu and Windows (I have gaming needs, after all), and Windows is the default operating system, so my wife doesn't have to do anything.

Setting that default was not exactly trivial. The web abounds with instructions on how to choose the default, most of which refer to the previous version of grub. About the newer version, not so much information.

So, in the end I used Ubuntu's Startup Manager to set this up. By the way, can anyone explain to me why you use Startup Manager to choose which OS to boot, and Bootup Manager to choose which processes will start? Sorry, I digress...

That worked nicely until the day I upgraded the system, at which point a new entry was created, changing the relative position of the Windows boot. That was disagreeable, so I decided to take a closer look.

The configuration used by grub during boot is located at /boot/grub, in particular /boot/grub/grub.cfg. But you shouldn't edit this file directly -- it is generated from the scripts located at /etc/grub, plus configuration on /etc/default/grub. Usually, it is this latter file you should edit.

To change the default operating system, you edit /etc/default/grub, change the setting GRUB_DEFAULT, and then run update-grub. Alas, the Startup Manager will do all this for you, but there is one thing the Startup Manager doesn't do...

So, here's the trick. The GRUB_DEFAULT is usually set to a number, indicating the relative position of the entry you want, but it can also be set to a name! To see what the entry names are, you can do a "grep menuentry /boot/grub/grub.cfg" -- the names are the strings between single or double-quotes right after "menuentry". For example:

$ grep menuentry /boot/grub/grub.cfg

menuentry 'Ubuntu, with Linux 2.6.38-11-generic' --class ubuntu --class gnu-linux --class gnu --class os {

menuentry 'Ubuntu, with Linux 2.6.38-11-generic (recovery mode)' --class ubuntu --class gnu-linux --class gnu --class os {

menuentry 'Ubuntu, with Linux 2.6.38-10-generic' --class ubuntu --class gnu-linux --class gnu --class os {

menuentry 'Ubuntu, with Linux 2.6.38-10-generic (recovery mode)' --class ubuntu --class gnu-linux --class gnu --class os {

menuentry 'Ubuntu, with Linux 2.6.38-8-generic' --class ubuntu --class gnu-linux --class gnu --class os {

menuentry 'Ubuntu, with Linux 2.6.38-8-generic (recovery mode)' --class ubuntu --class gnu-linux --class gnu --class os {

menuentry "Memory test (memtest86+)" {

menuentry "Memory test (memtest86+, serial console 115200)" {

This also shows why Startup Manager uses numbers instead of names: so that the latest Linux is always chosen. This seems a poor choice for me, for anything except the first entry, but there you go.

Anyway, once you got the name, all you have to do is edit /etc/default/grub, change the setting GRUB_DEFAULT, so that it is set to the name of the entry you want (don't forget the quotes), and then run update-grub.

Build a binary tree from pre-order traversal and in-order traversal

2011-07-05T13:55:00.000-03:00

This post comes from i has 1337 code by way of An Algorithm a Day. I'm really just posting this to show the power of Scala collections.

The idea is that you have two sequential representations of a tree: one for in-order traversal, and the order for pre-order traversal. Just one of these representations are not enough to reconstruct the tree, but the two of them, in the absence of duplicate elements, is. See the links above for an example.

The problem lends itself to recursive solutions, but there's some list manipulation required to build the input for the recursive steps. The key point of the algorithm is the realization that the first element of pre-order is the root, and every element to the left of said root in the in-order belongs to the left of the tree, and every element to the right belongs to the right of the tree. The rest is pretty trivial.

Even so, Scala makes the trivial, well, trivial. Here's the full code:

case class Tree[T](el: T, left: Option[Tree[T]], right: Option[Tree[T]])

def mkTree[T](preorder: List[T], inorder: List[T]): Option[Tree[T]] = preorder.headOption map { head =>
    val (left, _ :: right) = inorder span (head !=)
    Tree(head, 
         mkTree(preorder filter (left contains), left), 
         mkTree(preorder filter (right contains), right))
}

Note: I'm using List instead of Seq so that I can use the :: extractor.

A very quick guide to project creation on SBT 0.10.0

2011-06-27T16:14:00.000-03:00

SBT 0.10.0 is out, and it is a very different beast at first. Aside from the need for retooling and relearning, it is a very big improvement.

However, these minor differences can slow down things a bit. For one thing, previous versions of SBT asked if you wanted to create a project if run on an empty directory, and that does not happen anymore. Now it creates some stuff automatically, but other stuff -- project name, version, scala version, directory layout -- it doesn't. So, let's take a quick look on how to accomplish (roughly) the same tasks.

In the example below, I named my SBT 0.10.0 script xsbt, so that I could use the older 0.7.7 with projects that are not yet migrated.


dcs@ayanami:~/github$ mkdir TestProject
dcs@ayanami:~/github$ cd TestProject
dcs@ayanami:~/github/TestProject$ xsbt
Getting net.java.dev.jna jna 3.2.3 ...
:: retrieving :: org.scala-tools.sbt#boot-app
 confs: [default]
 1 artifacts copied, 0 already retrieved (838kB/35ms)
Getting Scala 2.8.1 (for sbt)...
:: retrieving :: org.scala-tools.sbt#boot-scala
 confs: [default]
 4 artifacts copied, 0 already retrieved (15296kB/232ms)
Getting org.scala-tools.sbt sbt_2.8.1 0.10.0 ...
:: retrieving :: org.scala-tools.sbt#boot-app
 confs: [default]
 34 artifacts copied, 0 already retrieved (6012kB/215ms)
[info] Set current project to root (in build file:/home/dcs/.sbt/plugins/)
[info] Set current project to default (in build file:/home/dcs/github/TestProject/)
> set name := "TestProject"
[info] Reapplying settings...
[info] Set current project to default (in build file:/home/dcs/github/TestProject/)
> set version := "1.0"
[info] Reapplying settings...
[info] Set current project to default (in build file:/home/dcs/github/TestProject/)
> set scalaVersion := "2.9.0-1"
[info] Reapplying settings...
Getting Scala 2.9.0-1 ...
:: retrieving :: org.scala-tools.sbt#boot-scala
 confs: [default]
 4 artifacts copied, 0 already retrieved (20447kB/186ms)
[info] Set current project to default (in build file:/home/dcs/github/TestProject/)
> session save
[info] Reapplying settings...
[info] Set current project to default (in build file:/home/dcs/github/TestProject/)
> exit
dcs@ayanami:~/github/TestProject$ find . -type d
.
./project
./project/target
./project/target/config-classes
./project/target/scala_2.8.1
./project/boot
./project/boot/other
./project/boot/other/net.java.dev.jna
./project/boot/other/net.java.dev.jna/jna
./project/boot/other/net.java.dev.jna/jna/3.2.3
./project/boot/scala-2.9.0-1
./project/boot/scala-2.9.0-1/lib
./project/boot/scala-2.8.1
./project/boot/scala-2.8.1/lib
./project/boot/scala-2.8.1/org.scala-tools.sbt
./project/boot/scala-2.8.1/org.scala-tools.sbt/sbt
./project/boot/scala-2.8.1/org.scala-tools.sbt/sbt/0.10.0
./project/boot/scala-2.8.1/org.scala-tools.sbt/sbt/0.10.0/compiler-interface-bin_2.7.7.final
./project/boot/scala-2.8.1/org.scala-tools.sbt/sbt/0.10.0/compiler-interface-src
./project/boot/scala-2.8.1/org.scala-tools.sbt/sbt/0.10.0/compiler-interface-bin_2.9.0.final
./project/boot/scala-2.8.1/org.scala-tools.sbt/sbt/0.10.0/compiler-interface-bin_2.8.1.final
./project/boot/scala-2.8.1/org.scala-tools.sbt/sbt/0.10.0/xsbti
./target
./target/streams
./target/streams/$global
./target/streams/$global/$global
./target/streams/$global/$global/streams
./target/streams/$global/$global/streams/$global
dcs@ayanami:~/github/TestProject$ ls
build.sbt  project  target
dcs@ayanami:~/github/TestProject$ cat build.sbt


name := "TestProject"

version := "1.0"

scalaVersion := "2.9.0-1"

So far so good, but note that the directories for source are not created. The new version of SBT expects your IDE to do that (which is rather annoying for us vim users), or so it seems. However, the eclipse plugin can do that at the same time it creates the eclipse project. Here's an example:

dcs@ayanami:~/github/TestProject$ cat ~/.sbt/plugins/build.sbt 
resolvers += {
  val typesafeRepoUrl = new java.net.URL("http://repo.typesafe.com/typesafe/releases")
  val pattern = Patterns(false, "[organisation]/[module]/[sbtversion]/[revision]/[type]s/[module](-[classifier])-[revision].[ext]")
  Resolver.url("Typesafe Repository", typesafeRepoUrl)(pattern)
}

libraryDependencies <<= (libraryDependencies, sbtVersion) { (deps, version) => 
  deps :+ ("com.typesafe.sbteclipse" %% "sbteclipse" % "1.1" extra("sbtversion" -> version))
}
dcs@ayanami:~/github/TestProject$ xsbt
[info] Compiling 1 Scala source to /home/dcs/.sbt/plugins/project/target/scala_2.8.1/classes...
[info] Set current project to root (in build file:/home/dcs/.sbt/plugins/)
[info] Compiling 8 Scala sources to /home/dcs/.sbt/staging/a69240767cc8e721757e/target/scala-2.8.1.final/classes...
[info] Set current project to default (in build file:/home/dcs/github/TestProject/)
> eclipse create-src   
[info] Updating...
[info] Done updating.
[info] Successfully created Eclipse project files. Please select the appropriate Eclipse plugin for Scala 2.9.0-1!
> exit
dcs@ayanami:~/github/TestProject$ find . -type d
.
./project
./project/target
./project/target/config-classes
./project/target/scala_2.8.1
./project/boot
./project/boot/other
./project/boot/other/net.java.dev.jna
./project/boot/other/net.java.dev.jna/jna
./project/boot/other/net.java.dev.jna/jna/3.2.3
./project/boot/scala-2.9.0-1
./project/boot/scala-2.9.0-1/lib
./project/boot/scala-2.8.1
./project/boot/scala-2.8.1/lib
./project/boot/scala-2.8.1/org.scala-tools.sbt
./project/boot/scala-2.8.1/org.scala-tools.sbt/sbt
./project/boot/scala-2.8.1/org.scala-tools.sbt/sbt/0.10.0
./project/boot/scala-2.8.1/org.scala-tools.sbt/sbt/0.10.0/compiler-interface-bin_2.7.7.final
./project/boot/scala-2.8.1/org.scala-tools.sbt/sbt/0.10.0/compiler-interface-src
./project/boot/scala-2.8.1/org.scala-tools.sbt/sbt/0.10.0/compiler-interface-bin_2.9.0.final
./project/boot/scala-2.8.1/org.scala-tools.sbt/sbt/0.10.0/compiler-interface-bin_2.8.1.final
./project/boot/scala-2.8.1/org.scala-tools.sbt/sbt/0.10.0/xsbti
./target
./target/streams
./target/streams/$global
./target/streams/$global/ivy-sbt
./target/streams/$global/ivy-sbt/$global
./target/streams/$global/ivy-configuration
./target/streams/$global/ivy-configuration/$global
./target/streams/$global/update
./target/streams/$global/update/$global
./target/streams/$global/project-descriptors
./target/streams/$global/project-descriptors/$global
./target/streams/$global/$global
./target/streams/$global/$global/streams
./target/streams/$global/$global/streams/$global
./target/scala-2.9.0.1
./target/scala-2.9.0.1/cache
./target/scala-2.9.0.1/cache/update
./src
./src/main
./src/main/resources
./src/main/java
./src/main/scala
./src/test
./src/test/resources
./src/test/java
./src/test/scala

That's it! I strongly recommend reading the wiki linked at the beginning of this post, but this will get you going for small stuff.

Scala 2.9 optimizes for comprehensions way better!

2011-05-21T12:49:00.000-03:00

Ok, I completely missed this. For comprehensions in Scala 2.9 was way better optimized with the parameter -optimize than they were before! Take this code:

class OptEx {
    def sum(l: Array[Int]) = {
        var acc = 0
        for (i <- 0 until l.length) acc += l(i)
        acc
    }
}

This is the java bytecode generated with Scala 2.8.1 for the method sum:

public int sum(int[]);
  Code:
   0:   new     #7; //class scala/runtime/IntRef
   3:   dup
   4:   iconst_0
   5:   invokespecial   #12; //Method scala/runtime/IntRef."":(I)V
   8:   astore_2
   9:   new     #14; //class scala/runtime/RichInt
   12:  dup
   13:  iconst_0
   14:  invokespecial   #15; //Method scala/runtime/RichInt."":(I)V
   17:  aload_1
   18:  arraylength
   19:  invokevirtual   #19; //Method scala/runtime/RichInt.until:(I)Lscala/collection/immutable/Range$ByOne;
   22:  new     #21; //class OptEx$$anonfun$sum$1
   25:  dup
   26:  aload_0
   27:  aload_1
   28:  aload_2
   29:  invokespecial   #24; //Method OptEx$$anonfun$sum$1."":(LOptEx;[ILscala/runtime/IntRef;)V
   32:  invokeinterface #30,  2; //InterfaceMethod scala/collection/immutable/Range$ByOne.foreach$mVc$sp:(Lscala/Functio
n1;)V
   37:  aload_2
   38:  getfield        #34; //Field scala/runtime/IntRef.elem:I
   41:  ireturn

And this is what Scala 2.9.0 does:

public int sum(int[]);
  Code:
   0:   new     #7; //class scala/runtime/IntRef
   3:   dup
   4:   iconst_0
   5:   invokespecial   #12; //Method scala/runtime/IntRef."":(I)V
   8:   astore  6
   10:  new     #14; //class scala/runtime/RichInt
   13:  dup
   14:  iconst_0
   15:  invokespecial   #15; //Method scala/runtime/RichInt."":(I)V
   18:  aload_1
   19:  arraylength
   20:  istore_3
   21:  astore_2
   22:  getstatic       #21; //Field scala/collection/immutable/Range$.MODULE$:Lscala/collection/immutable/Range$;
   25:  aload_2
   26:  invokevirtual   #25; //Method scala/runtime/RichInt.self:()I
   29:  iload_3
   30:  invokevirtual   #29; //Method scala/collection/immutable/Range$.apply:(II)Lscala/collection/immutable/Range;
   33:  dup
   34:  astore  8
   36:  invokevirtual   #34; //Method scala/collection/immutable/Range.length:()I
   39:  iconst_0
   40:  if_icmple       83
   43:  aload   8
   45:  invokevirtual   #37; //Method scala/collection/immutable/Range.last:()I
   48:  istore  4
   50:  aload   8
   52:  invokevirtual   #40; //Method scala/collection/immutable/Range.start:()I
   55:  istore  9
   57:  iload   9
   59:  iload   4
   61:  if_icmpne       89
   64:  iload   9
   66:  istore  5
   68:  aload   6
   70:  aload   6
   72:  getfield        #44; //Field scala/runtime/IntRef.elem:I
   75:  aload_1
   76:  iload   5
   78:  iaload
   79:  iadd
   80:  putfield        #44; //Field scala/runtime/IntRef.elem:I
   83:  aload   6
   85:  getfield        #44; //Field scala/runtime/IntRef.elem:I
   88:  ireturn
   89:  iload   9
   91:  istore  7
   93:  aload   6
   95:  aload   6
   97:  getfield        #44; //Field scala/runtime/IntRef.elem:I
   100: aload_1
   101: iload   7
   103: iaload
   104: iadd
   105: putfield        #44; //Field scala/runtime/IntRef.elem:I
   108: iload   9
   110: aload   8
   112: invokevirtual   #47; //Method scala/collection/immutable/Range.step:()I
   115: iadd
   116: istore  9
   118: goto    57

Time to take your old benchmarks out of the closet, people!

Regex Again

2011-05-19T12:46:00.000-03:00

I have been thinking about regex lately. I have never felt comfortable with how Scala regex works, but I could never settle on what should be done about. Recently, I have started more and more of thinking of regex like this:

class RegexF(pattern: String) extends String => Option[Seq[String]]

or, perhaps,

class RegexPF(pattern: String) extends PartialFunction[String, Seq[String]]

In fact, RegexPF.lift would (could) yield a RegexF. It then caught my attention that RegexF.apply has the same signature as Regex.unapplySeq, which is the standard way of handling regex in Scala!

Might this be what has been bugging me about Scala's regex all along? Should we translate

val YYYYMMDD = """(\d{4})-(\d{2})-(\d{2})""".r
val MMDDYYYY = """(\d{2})/(\d{2})/(\d{4})""".r

def getYear(s: String) = s match {
    case YYYYMMDD(year, _, _) => year
    case MMDDYYYY(_, _, year) => year
}

into

val YYYYMMDD = """(\d{4})-(\d{2})-(\d{2})""".r
val MMDDYYYY = """(\d{2})/(\d{2})/(\d{4})""".r andThen (fields => fields.last +: fields.init)

def getYear(s: String) = ((YYYYMMDD orElse MMDDYYYY) andThen (_.head))(s)

I can certainly see the advantages of pattern matching, but... it doesn't compose very well. And it has some performance issues, which is a big deal for most regex usages. And being a PartialFunction would not prevent a Regex from having extractors as well.

A Cute Algorithm

2011-05-14T23:30:00.000-03:00

These days I read about an algorithm challenge: given two sorted arrays, find the k-th minimum element from their merge.

Well, if you do merge them, you can just get the element at index k, and the merge can be done in O(n + m), where n and m are the respective size of each array.

The solution given is O(k) and pretty simple: keep an index into each array, and increase one or other until you reach k. It can be done in O(log k), though, and, fortunately for me, my first idea on how to solve it in O(k) is more easily adaptable.

My own O(k) version is like this: point an index at the k-th element on the first array, and another at the first element of the second array. If the element on the first array is smaller than the element on the first array, return that. Otherwise, as long as the element on the first array is bigger than the element on the second array, decrease the first index and increase the second. After doing that, you'll have the elements on each array that make up the k smallest elements, the k-th being the bigger between the top one in each array.

In code, something like this:

def kMin(a1: Array[Int], a2: Array[Int], k: Int) = {
    def recurse(k2: Int): Int =
        if (a1(k - k2 - 1) < a2(k2)) recurse(k2 + 1)
        else k2

    if (a1(k - 1) < a2(0)) a1(k - 1)
    else {
      val k2 = recurse(1)
      a1(k - k2 - 1) max a2(k2 - 1)
    }
}

Now, that code isn't particularly good, as there are some conditions that can break it. For instance, if the first array's size is smaller than k, you'll get an array index out of bounds exception. However, it gives the basis for explaining the O(k) algorithm.

Here we search linearly for the k smallest elements of both arrays together, but we know these arrays are sorted. So, instead of going one by one, we can use binary search instead, and turn it into O(log k)!

The concept is simple. We are looking into the k smallest elements of the two array together, so we know beforehand that the maximum number of elements we need to look into either array is k.

We'll search one array for the biggest element that is smaller than or equal to the k-th minimum, with the upper bound being the k-th element of that array, and the lower bound being 0 (meaning the k smallest elements are all in the other array).

To check if the number x-th is among the k-smallest ones, we see if that number is smaller than the (k - x)-th element on the other array. If it is, then x is among the k smallest. The intuitive explanation for that is that, if you take (k - x) elements from the one array and x elements from the other, you get exactly k elements. No element y > x in x's array will be smaller than x, since the array is sorted. And since the (k - x)-th element in the other array is also bigger than it, then no other element in the other array can be smaller either.

So, as long as we find an element that belongs in the k-th smallest, we move the lower bound. If we find an element that does not belong in the k-th smallest, we move the upper bound below it.

Once we find how many elements in one array belong in the k-smallest, we also know how many elements we must take from the other array. Pick the biggest among the biggest in each array, and you have the k-th smallest.

Here's the code below, which is much more concise than the above explanation. It finds the k-th smallest element, with k=1 being the smallest element of all. It assumes there are at least k elements overall on the arrays, though k may be bigger than the number of elements on one array. In fact, either array may be empty (but not both). One can find this code at my github repository, along with an sbt project and a Scalacheck test case.

    def kMin(a1: Array[Int], a2: Array[Int], k: Int): Int = {
      def select(k2: Int) = k2 match {
        case `k` => a2(k - 1)
        case 0   => a1(k - 1)
        case _   => a1(k - k2 - 1) max a2(k2 - 1)
      }
      
      def recurse(top: Int, bottom: Int): Int = {
        if (top == bottom) select(top)
        else {
          val x = (bottom + top) / 2 max bottom + 1
          if (a1(k - x) <= a2(x - 1)) recurse (x - 1, bottom)
          else recurse(top, x)
        }
      }
      
      recurse(k min a2.size, 0 max k - a1.size)
    }

Scala 2.9 and Parallel collections

2011-05-12T14:52:00.000-03:00

So, Scala 2.9.0 is out. Also, the Typesafe Stack is also out, which brings together Scala, Akka, and a few other things to get one up-and-running quickly. Much fun.

On the collection side of things, one of the first questions I saw was: do parallel collections share a common interface with standard collections. The answer is yes, they do, but not one that existed in 2.8.1.

You see, a trouble with parallel collections is that, now that they are available, people will probably be passing them around. If they could be passed to old code -- as it was briefly contemplated -- that old code could crash in mysterious ways. In fact, it happens with REPL itself.

For that reason, ALL of your code comes with a guarantee that it will only accept sequential collections. In other words, Iterable, Seq, Set, etc, they all now share a guarantee to be sequential, which means you cannot pass a parallel sequence to a method expecting Seq.

The parallel collections start with Par: ParIterable, ParSeq, ParSet and ParMap. No ParTraversable for now. These are guaranteed to be parallel. They can be found inside scala.collection.parallel, scala.collection.parallel.immutable, etc.

You can also get a parallel collection just by calling the ".par" method on it, and, similarly, the ".seq" method will return a sequential collection.

Now, if you want your code to not care whether it receives a parallel or sequential collection, you should prefix it with Gen: GenTraversable, GenIterable, GenSeq, etc. These can be either parallel or sequential.

And, now, something fun to try out:

def p[T](coll: collection.GenIterable[T]) = coll foreach println; p(1 to 20); p((1 to 20).par)

Expressive Code and the Alternative Vote

2011-04-30T23:02:00.000-03:00

One of the joys of writing code in Scala is how expressive it looks. Instead of dealing with the minutia of handling data, I can concentrate on what the code is actually doing. With experienced Scala programmers, that goes without saying. Newcomers have a harder time, because they are still a bit confused by grammar and vocabulary to pay proper attention to what is being said, so to speak.

The most striking example of that comes from the use of Scala's collection. There are many powerful collection libraries out there, but you are usually made very aware that you are handling a collection -- code to be hidden inside a class, to avoid contaminating business logic with it. Scala's collections, on the other hand, can easily fit in the highest abstraction levels of the code.

Let me take an example from the upcoming British referendum about the adoption (or not) of Alternative Vote. In this voting system, each voter ranks the candidates in order of preference. Depending on the specifics of its implementation, it may be possible or not to leave candidates unranked. The winner is the candidate that manages to get 50% of the votes, with the the candidate with the least votes being removed and his or her votes being reassigned according to the voter's preferences until some candidate gets elected.

So, let's consider how one could implement the algorithm that decides who the winner is. Let's say we have a set of candidates, identified by their names, and a list of votes. Each vote is a list of candidates ranked by preference. From that, we have to produce the name of the winner. In other words:

def elect(candidates: Set[String], votes: Seq[Seq[String]]): String = {

So, where do we begin? There are three essential tasks: we need to tally the votes for every candidate, we need to see if the candidate with most votes has at least 50% of all votes, and we need to discover who's the candidate the the least amount of votes.

Let's say we did these tasks, and now we know who the candidate with least and most votes are, and we have a tally of votes for all candidates. In this case, we can return the winner very easily, if there's one:

    if (votesByCandidate(mostVotesCandidate) >= votes.size / 2) mostVotesCandidate

Which still leave us the problem of how to handle the (expected) usual case of no candidate reaching 50% on first tally. There's an easy solution for that, though: just remove the candidate with least votes from the pool of candidates, and try to get a winner out of that. It's easy, because we already have a function that does that:

    else elect(candidates - leastVotesCandidate, votes)

Of the three tasks posed earlier, two are pretty simple as well: deciding who's the candidate with least and most votes. We could sort all candidates by vote and take the first and last candidate, but we don't actually need to sort anything: just knowing top and bottom is enough. We can do that like this:

    val mostVotesCandidate = candidates maxBy votesByCandidate
    val leastVotesCandidate = candidates minBy votesByCandidate

Now all that's left is finding how many votes each candidate has. We could pick the first preference in each vote and do a tally on that, but some candidates may have been removed from the pool. Instead let's say the valid candidates of a vote are the ranked list of candidates for a vote that are still in the running. We can compute that for a vote by doing:

    def validCandidates(vote: Seq[String]): Seq[String] = vote filter candidates

This doesn't read right, actually. A minor complain some people have about collection methods is that filter seems to do exactly the opposite of what's wanted: if you say filter X (those for which X is true), then it will keep X instead of discarding it. So, when we say "filter candidates", it will keep these candidates in the vote, and discard the rest.

The other non-obvious thing about this line is "candidates" itself. What does it mean to say "filter candidates"? Well, "filter" takes a function which, given a value of the collection, will return true or false depending on whether that value must be kept or discarded. That means "candidates" must be a function which, given the name of a candidate, returns true or false.

However, "candidates" is a set! We declared it so in the very first line of code presented, didn't we? Well, in Scala a set is also a function that tests whether a value is present in the set or not, returning true or false accordingly. In fact, sequences and maps are also functions in Scala, the former from indices to values, and the latter from keys to values.

Well, enough about that. We can now just take the first candidate in the list of valid candidates and tally the votes... as long as all candidates are ranked in each vote. If that is not the case, then a vote may well not contain any candidates still in the running, in which case the list of valid candidates will be empty.

Since this example comes from the British referendum, and the AV proposed in that referendum does not require votes to rank all candidates, we'll deal with that. Let's say the first valid candidate of a vote may be some candidate or no one. That is,

    def firstValidCandidate(vote: Seq[String]): Option[String] = validCandidates(vote) headOption

We can then use this to get a list of first choices for all votes with a valid first candidate:

    val firstChoices = votes flatMap firstValidCandidate

The votes for a candidate are the number of first choices for that candidate. We'll make a map out of it to avoid recounting that every time.

    def votesFor(candidate: String) = firstChoices count (candidate ==)
    val votesByCandidate = candidates map (candidate => candidate -> votesFor(candidate)) toMap;

Finally, we have to do something about the possibility of no candidate reaching 50%, which is possible in a system where not all candidates are ranked. I don't know how the proposed system will do in that case, but I'll just choose the most voted candidate if there aren't more than two.

With that fix in, this is what the whole code looks like:

def elect(candidates: Set[String], votes: Seq[Seq[String]]): String = {
    def validCandidates(vote: Seq[String]): Seq[String] = vote filter candidates
    def firstValidCandidate(vote: Seq[String]): Option[String] = validCandidates(vote) headOption
    val firstChoices = votes flatMap firstValidCandidate
    def votesFor(candidate: String) = firstChoices count (candidate ==)
    val votesByCandidate = candidates map (candidate => candidate -> votesFor(candidate)) toMap;

    val mostVotesCandidate = candidates maxBy votesByCandidate
    val leastVotesCandidate = candidates minBy votesByCandidate

    if (votesByCandidate(mostVotesCandidate) >= votes.size / 2 || candidates.size <= 2) mostVotesCandidate
    else elect(candidates - leastVotesCandidate, votes)
}

While there's a Scala oddity here and there, the code is pretty clear for all that it is doing.

Scala popularity

2011-03-22T13:09:00.000-03:00

I had 5 posts in this blog throughout 2010 -- two in January, two in June. One post January of this year. Given that, I'm pretty sure no one follows my blog except, perhaps, as a forgotten automatic tracker of some sort.

Well... I decided to blog about something back on Sunday, which is a terrible day to blog something if you want hits. Late Sunday. Looking at statistics for Monday, though, I see that I have hit three times more hits than my previous record in a single day.

It is a heartening indication of how much interest Scala is attracting nowadays.

On Scala 2.9's road...

2011-03-20T19:54:00.002-03:00

I suspect a lot of people are eagerly waiting for the parallel collections on Scala 2.9. The thing is... it's just not my thing. I like that it is being made available, but it's just not a pervasive feature for my small daily needs.

So, while I was somewhat bored by Scala 2.9, after the huge jump 2.8 was, there has been some nice improvements. For one thing, the jLine library used by REPL was replaced with one based on this (the canonical repository to the jLine actually used in Scala is here) giving a much superior experience. Now one can edit input that spans multiple lines (longer than the number of columns in the screen) without trouble, search the history, etc. There's even something to show its key-bindings: just type :keybindings.

And speaking of REPL, it doesn't stop there, by a long margin! There's :javap, which will happily decompile a class or file, :type which will show an expression's type without evaluating it, and :implicits to show what implicits are in scope. Add -v to that last one, and it will show those that come with Predef by default.

Those of you pasting code into REPL, or wanting to define companion objects, or pretty much any other feature that depends on the content of the next line, you'll be happy to know there's now :paste. Instead of instantly evaluating each line, it will wait until you hit ^D.

More recently, a few features came up that will help those that like to do Scala scripting. The -absolute-cp parameter will ensure relative paths on classpaths will be made absolute based on where the script is being run from, not where the compilation daemon was started at. If you don't even know what I'm talking about, then trust me: that will save you a lot of pain.

Another option, -max-idle, will let you specify how long the compilation daemon will stay up when idle, and even disable its auto-shutdown.

And just to make scripting even nicer, SBT's Process library is now available in Scala, as sys.process! Now we can do stuff like this:

import sys.process._

Process cat new URL("http://databinder.net/dispatch/About") !

"find src -name *.scala -exec grep null {} ;"  #|  "xargs test -z"  #&&  "echo null-free"  #||  "echo null detected"  !

Another interesting scripting feature is that not only will files containing a single object with a main method be runnable as if it were a script, but jar files produced by scala when it compiles scripts will be runnable like programs. For example:

% cat script.scala
object FiddleDeeMain {
  def main(args: Array[String]): Unit = {
    println(args mkString " ")
  }
}
% scala -nocompdaemon script.scala a b c
a b c

And, conversely,

% cat script2.scala
println(args mkString " ")

% scala -save script2.scala arg1 arg2
arg1 arg2

% scala script2.jar arg1 arg2
arg1 arg2

On the library side, a few things have happened too. Some changes where made to view, which made it much faster than it used to be. Arguably, its previous lack of performance resulted from a bug, so if you had performances issues with it, you might want to check it out again. Also on the performance front, another change with lots of potential is the introduction of a new hash code algorithm -- murmur3.

To those of you who like writing methods and classes with Numeric and Ordering, you'll probably like to know that you can now add "import Numeric.Implicits._" and "import Ordering.Implicits._" and avoid all that messy implicit parameter handling. For example:

import Numeric.Implicits._

def sum[N: Numeric](lst: List[N]) = lst reduceLeft (_ + _)

It might not seem much for a single method like that, but if you use this stuff often, I'm sure you see the advantages.

There are plenty of small changes that will make life easier, or more intuitive. For example, -5.abs will now work. Scaladoc is much faster. Many bugs have been fixed, even on places you'd never guess there were bugs (scary thought).

An interesting improvement is the introduction of DelayedInit. While most people won't ever hear of it -- unless it starts getting used in DSLs --, it enabled the rehabilitation of a much criticized feature: the Application trait. It is not that Application was a bad idea, but it was badly implemented. Given all that has been written about staying away from it, its new implementation was also given a new name, which we can now start using in our blogs everywhere: App.

On the realm of experimental stuff that may never make 2.9 at all, I'm pretty fond of -Yrich-exceptions. It adds some capabilities to exceptions on REPL. One example is lastException.show, which will display the source code location of the exception, if available (to use it, point SOURCEPATH to the source code).

There are plenty of other improvements, way too many to talk about: better docs, better error messages, better performance, bug fixes, more methods, new traits and classes, not to mention improvements made for people creating compiler plugins or working on Scala itself. If you want to get more dibs into Scala 2.9, there's a japanese site tracking the changes, though only looking through the commit log one can truly feel the scope of what Scala 2.9 is. Kudos to Scala's development team!

Testing with Scala for Fun and Profit

2011-01-24T17:21:00.000-02:00

Sometimes I like Scala, and sometimes I really like Scala.

So, I was writing some algorithms to compute the median of a sequence of values, just for the fun of it, adapting from pseudo-code description of an algorithm. The problem with pseudo-code is that it is pseudo-precise, meaning my algorithm was pseudo-correct, so I wanted to test it to ensure it really worked.

As it happens, the median of values has a trivial implementation that could be used to test against. So, one import and one one-liner afterwards, I had a quick way to test it from the REPL, where I could then experiment with the failing test case to understand what went wrong:

import org.scalacheck.Prop._
forAll((lst: List[Double]) => lst.nonEmpty ==> (myAlgorithm(lst) == lst.sorted.apply((lst.size - 1) / 2))).check

That uses the Scalacheck library, the best way to test algorithms in my opinion. What I'm doing with forAll is saying that for all inputs (List[Double]) of that function, the conditions must hold true. Specifically, if the input is not empty, then the result of my algorithm must be equal to the result of the trivial implementation of median. That will result in a property (class Prop).

I then tell it to check that property, which will be done by automatically generating input, with some heuristics to improve the chance of catching boundary cases, and testing the condition for each such input. If 100 tests pass, it finishes by saying:

+ OK, passed 100 tests.

Or, if it fail at some point, it will say something like this:

! Falsified after 0 passed tests.                                             
> ARG_0: List("-1.0") (orig arg: List("-1.0", "8.988465674311579E307"))

To be honest, my one-liner was slightly longer, because I was using arrays and arrays in Java do not have a useful toString method, so I had to tell Scalacheck how to print the array. Both Scalatest and Specs support integration with Scalacheck too, so this can be easily turned into part of a test suite.

Now this helped me achieve correctness, but I was also interested in how fast the code could run. I had three different algorithms (including the trivial implementation), and two of them could be further refined by abstracting over the selection of a pivot (quicksort-style). At that point, I decided to build a small framework which would help me test everything automatically.

I wanted to test each algorithm three times for different input sizes. The basic measurement algorithm was done by one of the methods in my toolkit:

import java.lang.System.currentTimeMillis

def bench[A](n: Int)(body: => A): Long = {
  val start = currentTimeMillis()
  1 to n foreach { _ => body }
  currentTimeMillis() - start
}

This should be familiar to anyone who ever did microbenchmarking with Scala. With that in hand, another one liner got the results I wanted:

println(bench(50000)(myAlgorithm(Array.fill(500)(nextDouble))))

Which worked well enough for a while, but really didn't scale as I got more algorithm variations and tested them with different settings. So, to get the results for each algorithm, I wrote this:

import scala.util.Random.nextDouble

def benchmark(algorithm: Array[Double] => Double,
              arraySizes: List[Int]): List[Iterable[Long]] = 
    for (size <- arraySizes)
    yield for (iteration <- 1 to 3)
        yield bench(50000)(algorithm(Array.fill(size)(nextDouble)))

Which let me pass a list of sizes I wanted to test the stuff at, and run each benchmark three times, to give me a feel for the variation in the results. Next, I made a list of the algorithms I wanted tested:

val algorithms = sortingAlgorithm :: immutableAlgorithms

That's the list I started with, but it grew as I added other algorithms. As for the immutable algorithms, they were all the same method call, but passing different pivot selection as parameters. As it got a bit verbose, I decided to apply a bit of DRY. First, I made a list of my pivot selection algorithms:

val immutablePivotSelection: List[(String, Array[Double] => Double)] = List(
    "Random Pivot"      -> chooseRandomPivot,
    "Median of Medians" -> medianOfMedians,
    "Midpoint"          -> ((arr: Array[Double]) => arr((arr.size - 1) / 2))
)

Next, I used that list to produce a list of median algorithms using each of these pivot selections:

val immutableAlgorithms = for ((name, pivotSelection) <- immutablePivotSelection)
        yield name -> (findMedian(_: Array[Double])(pivotSelection))

With the list of algorithms in hand, it was a simple for comprehension to produce a list of results:

val benchmarkResults: List[String] = for {
    (name, algorithm) <- algorithms
    results <- benchmark(algorithm, arraySizes).transpose
} yield formattingString format (name, formatResults(results))

The transposition let me see each size on a different column, making it easier to compare the algorithms when displayed together. Anyway, once I had that ready, I could also easily use the list of algorithms to test them:

def test(algorithm: Array[Double] => Double, 
         reference: Array[Double] => Double): String = {
    def prettyPrintArray(arr: Array[Double]) = arr mkString ("Array(", ", ", ")")
    val resultEqualsReference = forAll { (arr: Array[Double]) => 
        arr.nonEmpty ==> (algorithm(arr) == reference(arr)) :| prettyPrintArray(arr)
    }
    Test.check(Test.Params(), resultEqualsReference)(Pretty.Params(verbosity = 0))
}

val testResults = for ((name, algorithm) <- algorithms)
    yield formattingString format (name, test(algorithm, sortingAlgorithm._2))

I could even make the test method more general, but parameterizing the type of the algorithm, and adding a parameter for a no-parameter function generating the input. This could be easily done, but it was not needed by the time I was finished.

I find the final result of a certain elegance (then again, I'm obviously biased), that's not the reason I really like Scala. What I really, really like about it, is how I could start very small, with a few easy commands on the REPL, and then use that as the basis for an increasingly more flexible framework to do the tests I wanted.

If anyone is interested in seeing the full code, it can be found here.

Sieve of Eratosthenes (the real one) Scala One-Liner

2010-12-23T23:25:00.002-02:00

Here's a cute Sieve of Eratosthenes one liner (which I'm posting mostly so I won't loose it again):

(n: Int) => (2 to n) |> (r => r.foldLeft(r.toSet)((ps, x) => if (ps(x)) ps -- (x * x to n by x) else ps))

It requires the forward pipe operator, such as the one provided by Scalaz or the one defined here.

Type Class pattern example

2010-06-18T14:41:00.004-03:00

I was pleasantly suprised by the popularity of my last article, but some people expressed the wish to see a more practical example, outside Scala library. It is always difficult to use practical examples in blog articles, as they often require a lot of context to be properly understood and introduce a lot of unnecessary complexity.

So I'm going to compromise here. The example below discuss a common task in many systems, but which I'm going to present in a very simplistic manner. Specifically, how to format stuff for output.

There is much discussion about the proper place to handle output formatting. On one hand, for instance, we have the toString method available on every Java object. It is not uncommon to have serializer, toXML, or similar stuff either. On the other hand, such approach is not scalable and mixes business rules with presentation concerns, and architectures such as Model-View-Controller try to avoid it.

So let's try to solve this problem using the type class pattern. First, let's create or type class for a formatter which produces XML output (NodeSeq class), just as described in the last article. This time, there is one method we want this type class to have, though. Here it is:

import scala.xml.NodeSeq

abstract class FormatterXML[T] {
  def format(input: T): NodeSeq
}

To test it, we'll create a very simple method that takes this type class and use it to print stuff to the console.

def output[T](what: T)(implicit formatter: FormatterXML[T]) = println(formatter.format(what))

And, to finish the initial example, we'll create a simple class, good old Person, to test it. We'll put the implicit type class object inside the companion object of Person, so that it can be found automatically. Already, the class Person has become free of concerns about formatting, though companion object might be too close for some. This, however, is not necessary, as we'll see later.

In the code below, as in other examples later on, I'm declaring the case class and the companion object in the same line, so that it can be easily pasted on REPL (which won't recognize the companion object as a companion object otherwise). I added a test line too at the end.

case class Person(name: String, age: Int); object Person {
  implicit object Formatter extends FormatterXML[Person] {
    def format(input: Person): NodeSeq = <Person><Name>{input.name}</Name><Age>{input.age}</Age></Person>
  }
}

output(Person("John", 32))

So far, this can be trivially done in other ways, so we are gaining nothing. We'll gradually increase the complexity so that benefits of this approach start to show up. First, we'll create a Song class which has a Person member, so that we show off composition of the formatter.

case class Song(title: String, author: Person); object Song {
  implicit object Formatter extends FormatterXML[Song] {
    def format(input: Song): NodeSeq = <Song>
      <Title>{input.title}</Title>
      <Author>{implicitly[FormatterXML[Person]].format(input.author)}</Author>
    </Song>
  }
}

output(Song("War Pigs", Person("Ozzy Osbourne", 61)))

Now, I'm sure all of you must be up in arms right now, because, as everyone knows, Ozzy Osbourne wasn't the sole author of War Pigs. We need to change the Song class to accomodate more authors, but that will make the formatter more complex. To help us here, let's create a formatter for generic lists, that we can use to simplify the Song formatter:

def ListFormatterXML[T](implicit formatter: FormatterXML[T]) = new FormatterXML[Traversable[T]] {
  def format(input: Traversable[T]): NodeSeq = <List>{input map formatter.format}</List>
}

Here we start to see an advantage to this approach. This method will work for any list (any traversable, in fact!), as long as there is a formatter for its members. Anyway, let's see the Song again:

case class Song(title: String, authors: Person*); object Song {
  implicit object Formatter extends FormatterXML[Song] {
    def format(input: Song): NodeSeq = <Song>
      <Title>{input.title}</Title>
      <Authors>{ListFormatterXML[Person].format(input.authors)}</Authors>
    </Song>
  }
}

output(Song("War Pigs", 
            Person("Tony Iommi", 62), 
            Person("Ozzy Osbourne", 61), 
            Person("Geezer Butler", 60),
            Person("Bill Ward", 62)))

This works, but having as the sole child of looks a bit weird. Let's do away with this:

def ListFormatterXML[T](kind: String)(implicit formatter: FormatterXML[T]) = new FormatterXML[Traversable[T]] {
  def format(input: Traversable[T]): NodeSeq = <List>{input map formatter.format}</List>.copy(label = kind)
}

case class Song(title: String, authors: Person*); object Song {
  implicit object Formatter extends FormatterXML[Song] {
    def format(input: Song): NodeSeq = <Song>
      <Title>{input.title}</Title>
      {ListFormatterXML[Person]("Authors").format(input.authors)}
    </Song>
  }
}

output(Song("War Pigs", 
            Person("Tony Iommi", 62), 
            Person("Ozzy Osbourne", 61), 
            Person("Geezer Butler", 60),
            Person("Bill Ward", 62)))

Personally, I like this better, but your milleage may vary. Anyway, let's increase complexity a bit. If we want scalability, we'd better make the formatter more flexible, able to handle many different formats. Let's redefine our type class, in a way that avoids changes to the code we have written so far:

abstract class Formatter[T, Format] {
  def format(input: T): Format
} 

abstract class FormatterXML[T] extends Formatter[T, NodeSeq] {
  def format(input: T): NodeSeq
}

We also need a new output, but here we have a problem. How do we specify the format type explicitly while, at the same time, inferring the input type? I'll confess not having given much thought to this problem, but the following code will work:

def as[F] = new {
  def output[T](what: T)(implicit formatter: Formatter[T, F]) = println(formatter.format(what))
}

With this new definition in place, we can recompile Person, Song and ListFormatterXML above, and try it out like this:

as[NodeSeq].output(Song("War Pigs", 
            Person("Tony Iommi", 62), 
            Person("Ozzy Osbourne", 61), 
            Person("Geezer Butler", 60),
            Person("Bill Ward", 62)))

And, without changing any of that code, let's add a new output format to conclude this article:

implicit object PersonFormatterString extends Formatter[Person, String] {
  def format(input: Person): String = "%s, age %d" format (input.name, input.age)
}

def ListFormatterString[T](kind: String)(implicit formatter: Formatter[T, String]) = new Formatter[Traversable[T], String] {
  def format(input: Traversable[T]): String = input map formatter.format mkString (kind+" ", ", ", "; ")
}

implicit object SongFormatterString extends Formatter[Song, String] {
  def format(input: Song): String = input.title+" "+ListFormatterString[Person]("by").format(input.authors)
}

as[String].output(Song("War Pigs", 
            Person("Tony Iommi", 62), 
            Person("Ozzy Osbourne", 61), 
            Person("Geezer Butler", 60),
            Person("Bill Ward", 62)))

Implicit tricks -- the Type Class pattern

2010-06-17T20:19:00.009-03:00

Some people have been recently discovering the Scala equivalent of Haskell's Type Classes. I was a bit suprised because I thought everyone with enough Scala experience already knew about them, but, apparently, I was wrong.

A type class is basically a way to classify types based on the methods they offer. It offers an alternative to inheritance, in that you can group many different classes (types) that share a common set of methods, just like a superclass can be used to group its subclasses.

While Scala does not support type classes directly, the same patterns that hold true for Haskell can be simulated by using implicits in Scala. Perhaps a bit improperly, Scala programmers have been calling this pattern "type classes" as well.

It will feature proeminently in Scala 2.8, where examples can be found with Numeric, Ordering and even, I think, CanBuildFrom. In fact, one can find many questions on Stack Overflow related to Numeric being used precisely as a type class.

So, let me give a simple example of the kind of usage this can be put to. This is something someone just asked me on the #Scala channel on IRC, and I decided it makes for a nice example.

The problem put to me was restricting the options of a type parameter T without resorting to inheritance. For instance, if I want a method to work for Long and Int, but not any other type, there is no way to express that through a superclass. But the type class pattern can be used to solve it!

Here is the idea: I'll create an abstract class that will represent my type class. I'll then create elements representing the classes belonging to that type class. Finally, I'll use an implicit parameter to restrict my type parameter to that type class.

First, my abstract class:

abstract class Acceptable[T]

Yes, that's it. Not much to it, is there? Well, most often I would add to that class the methods I wish that type class to have. For instance, Numeric have all the normal operators you'd expect from classes that represent numbers. In this case, however, that won't be necessary, so I'm keeping it simple.

Next, let me create the members of my type class. I wish to create two of them: one for Int, and another for Long. To make them available without need for any import statements, I'll put them inside the companion class to Acceptable. Also, note that they are implicits.

object Acceptable {
  implicit object IntOk extends Acceptable[Int]
  implicit object LongOk extends Acceptable[Long]
}

Little to it, right? So, how do I get to use it? Well, let's create a simple method that will only accept Int and Long, as we wanted:

def f[T: Acceptable](t: T) = t

That weird declaration of T is called a context bound in Scala lingo. It's new to Scala 2.8, precisely to make this stuff easier. What it actually does is automatically define an implicit parameter -- and, for that very reason, it cannot be combined with other implicit parameters, though you can always use the full syntax to get the same result. Here's the full syntax:

def f[T](t: T)(implicit ev: Acceptable[T]) = t

So, does it work? Well, here is a small session using it:

scala> f(1)
res0: Int = 1

scala> f(1L)
res1: Long = 1

scala> f(1.0)
<console>:8: error: could not find implicit value for parameter ev: Acceptable[Double]
       f(1.0)
        ^

scala> f(1: Byte)
<console>:8: error: could not find implicit value for parameter ev: Acceptable[Byte]
       f(1: Byte)
        ^

Now, to those of you who may think this is neat but of little use, I'll point you to two examples of its usage in the new collections: the methods sum and max. If you try to call sum on a list of things that are not Numeric, it won't work -- at compile time. Likewise, if you try max on a list of things for which there are no Ordering available, it won't compile either. This way, these methods could be safely added to the collections without resorting to throwing exceptions at run-time!

This is just little window into what is possible -- enough to get a hang on the pattern without risking information overload. But look around, as there is much more to it!

String interpolation in Scala with Regex

2010-01-26T01:05:00.006-02:00

Some new stuff I was waiting for has arrived on Scala. We can now have a limited form of string interpolation very easily:


def interpolate(text: String, vars: Map[String, String]) =
  """\$\{([^}]+)\}""".r.replaceAllIn(text, (_: scala.util.matching.Regex.Match) match { 
    case Regex.Groups(v) => vars.getOrElse(v, "") 
  })

Which can then be used like this:


scala> "The ${name} of the ${game}"
res0: java.lang.String = The ${name} of the ${game}

scala> Map("name" -> "X", "game" -> "Y")
res1: scala.collection.immutable.Map[java.lang.String,java.lang.String] = Map(name -> X, game -> Y)

scala> interpolate(res0, res1)
res2: String = The X of the Y

Why do I love APL?

2010-01-08T20:38:00.005-02:00

I love the strangest languages for various reasons. Some of them have immense power, but can easily produce unmaintainable messes. Some have the elegant simplicity of zen, but never attracted the people who build kitchen sinks. Some are perfect matches for certain applications, and quickly degenerate for other usages.

In Scala I have found for the first time a positive combination of these attributes. Immense power, kitchen sinks, check. Simplicity? Perhaps not, but more so than the more popular alternatives. Some code has definitely a zen-like quality to it. And, yet, it is of general use, and has good enough resilience against unmaintainable messes. Not perfect, but better than anything else I know of, for now.

That doesn't mean I do not appreciate other languages. There is much to learn and admire in many, many languages, and I would not mind using quite a few of them if chance favors it.

So I'll leave you with the answer that came to my mind as I explained to a bewildered person why I loved APL -- a language I could spend a whole afternoon producing half a line of code:

There's joy to be found in writing code which is solely about what you want, and not about how to get there. Of expressing the fulness of your intent as a single expression. It's like the ultimate perfect katana cut.

Of course, in a real fight I'd rather have a gun.

99 Beers!

2009-10-30T22:27:00.006-02:00

I was perusing Lau Jensen's excellent Best In Class blog. Now, Lau Jensen is a Clojure-person, and that's one of the best languages out there in my opinion. So, when he compares it to other languages, that's never a nice experience to those being compared.

Personally, I think OO and infix methods (dot-style or operator notation) are essential for a well-rounded, popular language, which makes something of an uncrossable chasm between Clojure and me for "serious" stuff.

At any rate, his recent second take at Python got me curious about the Rosetta Code project. First, I got curious about his discussion of the Counting Programming Example problem, and the Python and Clojure implementations shown. I took my own shot at it, going the parallel way like the Clojure version, but I'm unsatisfied with the result. Sure, it is short, but it lacks... sense of cohesion, I guess. In fact, I just changed it from what I submitted to Rosetta. Here:

import java.net.{URL, URLEncoder}

val URLs = Map(
  'allTasks -> "http://www.rosettacode.org/w/api.php?action=query&list=categorymembers&cmtitle=Category:Programming_Tasks&cmlimit=500&format=xml",
  'oneTask -> "http://www.rosettacode.org/w/index.php?title=%s&action=raw"
  )
def oneTaskURL(title: String) = URLs('oneTask) format URLEncoder.encode(title.replace(' ', '_'), "UTF-8")

def getPage(url: String) = scala.io.Source.fromURL(new URL(url))(scala.io.Codec.UTF8)

val pattern = "(?i)==\\{\\{header\\|".r
def countPattern(title: String) =
  pattern findAllIn (getPage(oneTaskURL(title)) mkString) length

val allTasks = scala.xml.parsing.XhtmlParser(getPage(URLs('allTasks)))
val counts = 
  for (task <- allTasks \\ "cm" \\ "@title" map (_.text)) 
  yield actors.Futures.future((task, countPattern(task)))

counts map (_.apply) map Function.tupled("%s: %d examples." format (_, _)) foreach println
println("\nTotal: %d examples." format (counts map (_.apply._2) sum))

I won't bother explaining it, because I think it is self-explanatory, if a bit arcane. Scala's partial XPath support is put to good use, and future just works here. In case you aren't familiar with Future, it just detaches a thread to handle some computation you passed, and then, when you call "apply", it joins that thread and get the result. Sort of. If anyone wants to take a go at making this better, I'd like to see the results.

At any rate, while perusing the Rosetta site, I noticed that 99 Bottles of Beer problem allowed for creativity in reaching a solution. Most examples went for conciseness. My own concise Scala looks like this:

99 to 1 by -1 foreach {n =>
  println("""|%d bottles of beer on the wall
             |%d bottles of beer
             |Take one down, pass it around
             |%d bottles of beer on the wall\n""".stripMargin format (n, n, n -1))}

However, as I thought about the problem and how to make it interesting, I decided to model it with Actors. Sure, it is an absolute overkill for this problem, but I think the modelling itself shows off Actors pretty nice.

Here it is:

object Song {
  import scala.actors._
  import scala.actors.Actor._
  
  abstract class Beverage { def name = this.toString.toLowerCase }
  case object Beer extends Beverage
  
  object Wall {
    private var contents: List[Beverage] = Nil
    
    def count(what: Beverage) = contents count (_ == what)
    def isEmpty = contents isEmpty
    def stock(n: Int, what: Beverage) = contents :::= List.fill(n)(what)
    def get(what: Beverage) {
      def takeOneFrom(contents: List[Beverage]): List[Beverage] = contents match {
        case `what` :: rest => rest
        case other :: rest => other :: takeOneFrom(rest)
        case Nil => println("Sorry, we are out of "+what.name); Nil
      }
      contents = takeOneFrom(contents)
    }
  }

  sealed abstract class Messages
  case class SingSong(what: Beverage) extends Messages
  case class HowManyMore(what: Beverage) extends Messages
  case class HowManyNow(what: Beverage) extends Messages
  case class ThereAreStill(n: Int, what: Beverage) extends Messages
  case class ThereAreNow(n: Int, what: Beverage) extends Messages
  case class Gimme(what: Beverage) extends Messages
  case class HereIs(what: Beverage) extends Messages
  case object ClosingTime extends Messages
  
  def plural(count: Int, noun: String, nouns: String) = if (count == 1) noun else nouns
  def countIt(n: Int, what: Beverage) = "%d %s of %s" format (n, plural(n, "bottle", "bottles"), what.name) 
  
  object Waitress extends Actor {
    def tellThem(what: String) = println("%s on the wall" format what)
    def act = loop {
      react {
        case HowManyMore(it) =>
          val total = Wall count it
          tellThem(countIt(total, it))
          reply (ThereAreStill(total, it))
        case Gimme(it) =>
          print("Take one down, ")
          Wall get it
          reply (HereIs(it))
        case HowManyNow(it) =>
          val total = Wall count it
          tellThem(countIt(total, it))
          if (Wall isEmpty) {
              reply (ClosingTime) // You don't have to go home, but you can't stay here
              exit
          } else
          reply (ThereAreNow(total, it))
        case _ =>
          println("You wish, honey!")
      }
    }
  }
  
  object Patrons extends Actor {
    def act = loop {
      react {
        case SingSong(what: Beverage) =>
          Waitress ! HowManyMore(what)
        case ThereAreStill(n, it) =>
          println(countIt(n, it))
          Waitress ! Gimme(it)
        case HereIs(it) =>
          println("pass it around")
          Waitress ! HowManyNow(it)
        case ThereAreNow(n, it) =>
          println()
          Waitress ! HowManyMore(it)
        case ClosingTime =>
          exit
        case _ =>
          println("Say what???")
      }
    }
  }
  
  def Sing99Beers = {
    Wall stock (99, Beer)
    Waitress.start
    Patrons.start
    
    Patrons ! SingSong(Beer)
  }
}

Now, this code has a structure to it. To begin with, there are two concerns. First, there is the "wall", where the beverages are kept, and the beverages themselves. The beverages are modeled as case objects derived from a sealed class, which is an alternative to enumerations, as I have discussed in my Matrix series.

I suppose the wall ought to be synchronized, but I'm working with an assumption here. Only one agent can get things from the wall, and the wall can only be restocked while that agent is not working. It would be nice to have this enforced by the compiler, and a paper from the EPFL guys gives me hope of being able to in the future.

The second concern is the interaction between the patrons and the waitress. Again, it is further divided into two: the messages they exchange between themselves, and the actors themselves and their behavior.

Defining the messages as a subclass from an abstract class doesn't really give me anything. The Actors in the standard library are untyped, so they can receive anything as message. There is one typed Actor library for Scala, though, which is a model much more to my liking. If used, I'd not have to provide for handling of unknown messages.

The song gets sang as the patrons ask how many beers there are, the waitress answers, the patrons order one beer, get it, and then ask again how many beers there are. No actor ever waits for the answer. Instead, they finish their present reaction, and wait for another message -- which might be the answer they were waiting for, or not. What the actor do is solely defined by what message they received.

To get the song started, the wall is first stocked, patrons and waitress started, and, then, the patrons are asked to begin the song. I'm pretty sure bar owners everywhere hope it would be this easy to get people drinking until the stock is sold-out. :-)

I hope you enjoyed this post half as much as I enjoyed writing that code! If you are feeling the need to write some code right now, try modifying the program so that, when the stock of whatever is being consumed is finished, the patrons ask what else there is, and start a new song on a new beverage.

Or, better yet, why don't you find a fun problem on Rosetta Code, for which no solution exists in a language you like, and submit a solution to it? It's as easy as editting a wiki article, so go for it!

Strict Ranges?

2009-10-28T12:00:00.008-02:00

Note: This article was created before Scala 2.8.0 was out, and is mostly related to a problem that is no longer present as of that version. The code in here is supposed to be run on Scala 2.7.x unless otherwise noted, and the output of Scala 2.8.0 usually refers to some work-in-progress version of it, not the final version.

A common mistake newcomers to Scala usually make is to treat Scala ranges as strict. It's easy to see why they make such mistake, because the very expression "strict", though relatively easy to find in the Scala API documentation, is unfamiliar to them.

So, before getting into the problem, I'll make a brief detour. In functional languages, there is a concept of "strict functions" and "non-strict functions". Informally, a "strict function" is one which always evaluates its argument. For programmers from a non-functional background, that's most of the functions they ever saw, but not all. For instance, the trinary operator, "test ? f1 : f2", does not evaluate all its arguments, f1 and f2, even though it always evaluate at least one of them.

Now, to see where that can lead to trouble, let's first see an example of non-strictness in action, with Scala 2.7:

scala> object X {
| val x = -10 to 10 map (2 / _)
| }
defined module X

scala> object Y {
| val y = List.range(-10, 10) map (2 / _)
| }
defined module Y

scala> Y.y(0)
java.lang.ArithmeticException: / by zero
at Y$$anonfun$1.apply(<console>:5)
at Y$$anonfun$1.apply(<console>:5)
at scala.List.map(List.scala:812)
at Y$.<init>(<console>:5)
at Y$.<clinit>(<console>)
at .<init>(<console>:6)
at .<clinit>(<console>)
at RequestResult$.<init>(<console>:3)
at RequestResult$.<clinit>(<console>)
at RequestResult$result(<console>)
at sun.reflect.Nativ...
scala> X.x(0)
res2: Int = 0

We see an error happens when the map on the list is applied, but not when the map on the range is applied. That's because the function "map" for Range (the result of "x to y" or "x until y" expressions) is non-strict. I can get the value for any part of that Range, except the eleventh element, without throwing an exception.

But let say we have a function expensiveComputation, which takes quite a while to process. What happens, then, if I do this:

scala> import scala.actors.Futures._
import scala.actors.Futures._

scala> val m = 1 to 1000 map (i => future(expensiveComputation(i)))
m: RandomAccessSeq.Projection[scala.actors.Future[Int]] = RangeM(<function>, <function>, <function>,
<function>, <function>, <function>, <function>, <function>, <function>, <function>, <function>, <fu
nction>, <function>, <function>, <function>, <function>, <function>, <function>, <function>, <functi
on>, <function>, <function>, <function>, <function>, <function>, <function>, <function>...

If you haven't seen it before, the "future" function uses threads to compute the function you passed to it. Your program can go on to do other stuff, while all that work is being done concurrently.

Except, of course, that's not what's happening. No computation is being done, because Range's non-strict map hasn't evaluated its arguments. In fact, each time I call "apply" to get the result of the computation, the function I passed to map (the future) will be computed again! For example:

scala> def expensiveComputation(n: Int) = {
|   println("Starting expensive computation")
|   val x = n * 2
|   println("Finished expensive computation")
|   x
| }
expensiveComputation: (Int)Int

scala> val m = 1 to 10 map (i => future(expensiveComputation(i)))
(output from "m.toString" skipped)

scala> m(0).apply
Starting expensive computation
Finished expensive computation
res12: Int = 2

scala> m(0).apply
Starting expensive computation
Finished expensive computation
res13: Int = 2

To see where that can be a problem to beginners, take a look at the code in this question at Stack Overflow:

def ttest() = {
val threads =
for (i <- 1 to 5)
yield new Thread() {
override def run() {
println("going to sleep")
Thread.sleep(1000)
println("awake now")
}
}

threads.foreach(t => t.start())
threads.foreach(t => t.join())
println("all done")
}

Can you imagine what happens?

Well, gladly, Scala 2.8 should have a strict Range, so newcomers will be spared the trouble and lost debugging time. Here's what this will look like with Scala 2.8:

scala> val m = 1 to 10 map (i => future(expensiveComputation(i)))
Starting expensive computation
Finished expensive computation
Starting expensive computation
Starting expensive computation
Finished expensive computation
Starting expensive computation
Finished expensive computation
Starting expensive computation
Finished expensive computation
Starting expensive computation
Finished expensive computation
Starting expensive computation
Finished expensive computation
Starting expensive computation
Finished expensive computation
Starting expensive computation
m: scala.collection.immutable.Vector[scala.actors.Future[Int]] = NewVectorImpl(<function0>, <function0>, <function0>, <f
unction0>, <function0>, <function0>, <function0>, <function0>, <function0>, <function0>)
Finished expensive computation
Starting expensive computation
Finished expensive computation

scala> Finished expensive computation


scala> m(0).apply
res11: Int = 2

scala> m(0).apply
res12: Int = 2

Also, if you try out the first code snippet on Scala 2.8, "x.x(0)" will also throw an exception. Now, if we want the previous behavior, we can just call the "view" method. It will work not only on Range, but on pretty much all standard collections, as it is defined on the class IterableLike.

scala> val m = (1 to 10 view) map (i => future(expensiveComputation(i)))
m: scala.collection.SeqView[scala.actors.Future[Int],Seq[_]] = SeqViewM(...)

scala> m.toList
Starting expensive computation
Finished expensive computation
Starting expensive computation
Finished expensive computation
Starting expensive computation
Finished expensive computation
Starting expensive computation
Starting expensive computation
Starting expensive computation
Starting expensive computation
Finished expensive computation
Starting expensive computation
Finished expensive computation
Finished expensive computation
Finished expensive computation
Finished expensive computation
Starting expensive computation
Starting expensive computation
Finished expensive computation
res5: List[scala.actors.Future[Int]] = List(, , , , , 
, , , , )
Finished expensive computation

scala> m(0).apply
Starting expensive computation
Finished expensive computation
res6: Int = 2

scala> m(0).apply
Starting expensive computation
Finished expensive computation
res7: Int = 2

And, for the first example:

scala> object X {
| val x = (-10 to 10 view) map (2 / _)
| }
defined module X

scala> object Y {
| val y = List.range(-10, 10).view map (2 / _)
| }
defined module Y

scala> Y.y(0)
res0: Int = 0

scala> X.x(0)
res1: Int = 0

And, speaking of Scala 2.8 changes, there is one that is also likely to reduce confusion among newcomers, and is related to what we spoke of. It's related to how guards on for-comprehensions work. For instance, take a look at this code:

scala> def find(n: Int, l: List[Int]) = {
| var found = false
| for (el <- l; if !found) found = el == n
| found
| }
find: (Int,List[Int])Boolean

scala> find(5, List.range(1, 10))
res14: Boolean = false

This code doesn't work as expected because of how for-comprehensions are translated:

l.filter(el => !found).foreach(el => found = el == n)

Since "filter" for List is a strict method, this just doesn't work, as "filter" evaluates before "foreach". However, Range's "filter" on Scala 2.7 is non-strict. Does it work? Yes:

scala> def findR(n: Int, l: Range) = {
| var found = false
| for (el <- l; if !found) found = el == n
| found
| }
findR: (Int,Range)Boolean

scala> findR(5, 1 to 10)
res17: Boolean = true

But, back to the first example, as of Scala 2.8 the for-comprehension code will translate like this:

l.withFilter(el => !found).foreach(el => found = el == n)

This new function, "withFilter", will be non-strict for standard Scala collections. There's no way, however, to ensure that third-party collections will preserve the non-strictness. Hopefully, people will act in a sensible manner! :-) At any rate, the "find" function, as written, will work on Scala 2.8.

I hope this helps people working with Scala 2.7, and hope even more for Scala 2.8 to arrive soon! As a parting thought, though, I'd like to briefly speak of "<-", seen in for-comprehensions. I have seen people calling it many things. Martin Odersky's (et al) Programming in Scala book, however, calls it "in". So "for (el <- l)" ought to read "for el in l". So, if you weren't sure what to call it, now you know! Happy coding!

Scala's Delimited Continuations -- A Use Case

2009-09-29T23:26:00.003-03:00

When I first talked about the upcoming Scala 2.8 Delimited Continuations, I did not go into what uses I foresaw for them, mostly because I was pretty sure people would find uses I could never have imagined for it.

Well, people did find uses I could never have imagined, it turns out! If Scala and Distributed Computing are your things -- hell, if even one of them is your thing! -- do go check Swarm out.

Is rewritting really bad?

2009-09-17T22:46:00.002-03:00

Paul Chiusano tell us his Scala success story, and while I find it interesting, there's something that attracts my attention in it. He says:

Finally, I'd like to scrutinize the folk wisdom that rewrites are generally a bad idea.

That got me thinking a bit. That wisdom predates some developments which only became widespread practices recently. In particular, BDD and Continuous Integration.

It occurs to me that if I decide to rewrite something from scratch, I'll have a large set of tests in the form of BDD (which tests for Behavior, so a lot of it should still apply), plus the tests for all bugs that were caught and fixed, for which you them add tests to help with CI.

Furthermore, because you are doing BDD and CI, and possibly TDD for low level stuff, you won't get far with the same errors in case you re-introduce them.

That's something to think about... maybe the old wisdom requires some revisiting.

At any rate, I'd like to point out that this particular piece of wisdom might have become widespread because of this article by Joel Spolsky. I'll quote one part of it, though:

These problems can be solved, one at a time, by carefully moving code, refactoring, changing interfaces. They can be done by one programmer working carefully and checking in his changes all at once, so that nobody else is disrupted. Even fairly major architectural changes can be done without throwing away the code.

Well, that's precisely what Paul Chiusano did! So, on the other hand, perhaps is too soon to dispose of that wisdom...

Type Safe Builder Pattern

2009-09-09T21:29:00.004-03:00

I was reading these days an interesting article by Jim McBeath about type safe builder patterns. The interesting part was the use of Church encoding to be able to control the ordinality of certain types, but as I went to the original article by Rafael de F. Ferreira, I found the silliest criticism, which I quote below:

My but it's sad that Java/Scala has to resort to a design pattern for this (if I'm understanding the post correctly).

In Python, we have keyword arguments and default argument values, which allows for very rich parameter declarations.

Well, first of all, a builder pattern is targetted at complex objects. Imagine, for instance, a maze with multiple rooms and passages, where the creation process might entail adding hundred of such components. Not exactly the sort of thing you want to pass as a single parameter list, I'd imagine. In fact, it might not even be possible to do it, because you might not have all information needed in the same place and/or time.

But, most importantly, "keyword arguments" do not enforce type safety. So even if it were an alternative to any problem requiring the Builder pattern, it would fail at the basic premise of the article, which is providing type safety.

So, I decided to show something you can't do with keyword arguments, which, by the way, are called "named parameters" in Scala 2.8, which is mutual exclusion. I'm adapting this example from here, which was written in reply to a follow up by Jim on his original article.

For this example, I assume a "Car" builder, where one has to make a choice about number of doors and brand, and may also choose to get a convertible, but the convertible is incompatible with cars with five doors. This code is nowhere as clear as Jim's, but gets the job done faster, so I could get on with my life. :-)

So, I hope you like it. And if you can clean it up, or come up with more likely scenarios, please share it.


// This code is based on an idea of Rafael de F. Ferreira and was implemented as a response to
// Jim McBeath's blog post http://jim-mcbeath.blogspot.com/2009/09/type-safe-builder-in-scala-part-2.html
// Everyone is free to use, modify, republish, sell or give away this work without prior consent from anybody.

object Scotch {
sealed abstract class Preparation
case object Neat extends Preparation
case object OnTheRocks extends Preparation
case object WithWater extends Preparation

case class OrderOfScotch private[Scotch](val brand:String, val mode:Preparation, val isDouble:Boolean)

trait Option[+X]
case class Some[+X](x:X) extends Option[X]{
  def get:X = x
}
trait None extends Option[Nothing] // this differs in the original implementation
case object None extends None

case class Builder[HAS_BRAND<:Option[String],HAS_MODE<:Option[Preparation],HAS_DOUBLE<:Option[Boolean]] private[Scotch]
             (brand:HAS_BRAND
             ,mode:HAS_MODE
             ,isDouble:HAS_DOUBLE
             ) {
  def ~[X](f:Builder[HAS_BRAND,HAS_MODE,HAS_DOUBLE] => X):X = f(this)
}
           
def withBrand[M<:Option[Preparation],D<:Option[Boolean]](brand:String)(b:Builder[None,M,D]):Builder[Some[String],M,D] =
  Builder(Some(brand),b.mode,b.isDouble)
def withMode[B<:Option[String],D<:Option[Boolean]](mode:Preparation)(b:Builder[B,None,D]):Builder[B,Some[Preparation],D] =
  Builder(b.brand,Some(mode),b.isDouble)
def isDouble[B<:Option[String],M<:Option[Preparation]](isDouble:Boolean)(b:Builder[B,M,None]):Builder[B,M,Some[Boolean]] =
  Builder(b.brand,b.mode,Some(isDouble))

def build(b:Builder[Some[String],Some[Preparation],Some[Boolean]]):OrderOfScotch =
  OrderOfScotch(b.brand.get,b.mode.get,b.isDouble.get)

def builder:Builder[None,None,None] = Builder(None,None,None)

def test {
  val x:OrderOfScotch = builder ~ isDouble(true) ~ withMode(Neat) ~ withBrand("Blubber") ~ build
  // builder ~ isDouble(true) ~ withMode(Neat) ~ build // fails
  // builder ~ isDouble(true) ~ withMode(Neat) ~ withBrand("Blubber") ~ withBrand("Blubber") ~ build // fails
  x
}
}

A Number Puzzle

2009-09-08T22:21:00.003-03:00

My friend came up with a new puzzle. Given a 3x3 matrix, fill it with the numbers 1 through 9, without repetition, in such a way that adding the three digits from any line, column or diagonal will yield exactly the same result.

This time I went for conciseness. Instead of laying out a 3x3 array -- or what have you -- I'll take a list of 9 elements, and assume the elements are laid out left to right, then top to down, so that the third element of the second line is the sixth element of the list, for example. Now, before I try to solve it, I have to devise a way to test the conditions. First, let's create a list of list of indices for each line, column of diagonal possible. This can be done programmatically, of course, like this:

 
val cols = List.range(0,3)
val lines = cols map (_ * 3)
val allLines = lines map (l => cols map (l + _))
val allCols = cols map (c => lines map (c + _))
val diagLR = lines zip cols map Function.tupled(_+_)
val diagRL = lines zip cols.reverse map Function.tupled(_+_)
val indices = diagLR :: diagRL :: allLines ::: allCols

I decided just to enter it by hand, though:

 
val indices = List(List(0,1,2), List(3,4,5), List(6,7,8), List(0,3,6), List(1,4,7), List(2,5,8), List(0,4,8), List(2,4,6))

Now, I want to test this. Suppose I have a list of numbers representing the solution. I can replace the indices by the corresponding number like this:

 
indices map (_ map (solution(_)))

from which is quite easy to compute how much each line, column and diagonal adds to:

 
indices map (_ map (solution(_)) sum)

One way, then, to check if all numbers are equal is to simply compare them:

 
indices map (_ map (solution(_)) sum) match { case head :: tail => tail forall (_ == head) }

Not concise enough for me, though. I prefer this:

 
(indices map (_ map (solution(_)) sum) removeDuplicates).size == 1

Our test function, then, is:

 
def test(solution: List[Int]) = (indices map (_ map (solution(_)) sum) removeDuplicates).size == 1

Now, how to compute the solutions? We can do it recursively with lists, recursions, filters, etc. Too much work. Let's just enumerate the possible solutions. The first element can be represented by the index over a nine-elements list of a "seed" solution. The second element can be represented by an index over the eight-element list of remaining elements, and so on. We can disambiguate the first index from the second by multiplying the second by 9, and add both. We can repeat this over and over for every other element in the list. So, to go from a number representing the solution, plus a seed list, to the solution, we can write this function:

 
def numToIndices(n: Int, l: List[Int]): List[Int] =
  if (l.isEmpty) Nil else l(n % l.size) :: numToIndices(n / l.size, l filter (_ != l(n % l.size)))

Now, given this representation of the solutions of this problem, it should be clear that the number of solutions is the factorial of 9, so there are solutions from 0 to 9! - 1. So, let's create a seed, and, non-strictly (to avoid out of memory errors), generate our possible solutions:

 
val seed = 1 to 9 toList
val possibleSolutions = Stream.range(0, seed reduceLeft (_*_)) map (numToIndices(_, seed))

Keeping the head of a stream is not a good idea, though. We need to filter for the actual solutions before assigning it to any val. Which, of course, we'll give you the final solutions:

 
val solutions = (0 until seed.reduceLeft(_*_)).toStream map (numToIndices(_, seed)) filter (test(_)) toList

Not particularly efficient, but the line count is good:

 
val indices = List(List(0,1,2), List(3,4,5), List(6,7,8), List(0,3,6), List(1,4,7), List(2,5,8), List(0,4,8), List(2,4,6))
def test(solution: List[Int]) = (indices map (_ map (solution(_)) sum) removeDuplicates).size == 1
def numToIndices(n: Int, l: List[Int]): List[Int] =
  if (l.isEmpty) Nil else l(n % l.size) :: numToIndices(n / l.size, l filter (_ != l(n % l.size)))
val seed = 1 to 9 toList
val solutions = (0 until seed.reduceLeft(_*_)).toStream map (numToIndices(_, seed)) filter (test(_)) toList

Which we can then print with:

 
println(solutions map (_.iterator grouped 3 map (_ mkString) mkString "\n") mkString "\n")

A Puzzle

2009-09-04T20:35:00.012-03:00

A couple of days ago a friend of mine was playing with a puzzle I knew of a few years ago: a maze through which one had to drive a car. Here's the setup:

At each intersection, the car must take one of a limited number of allowed paths, as indicated by the arrows. The goal is to reach the exit on the other side.

At any rate, I felt an urge to solve it programmatically -- in Scala, of course. So, later, I sat down and started coding the solution. The first step, obviously, was getting the maze into some sort of data structure. I briefly tried to find the data being used in the puzzle, but gave up on it. Instead, I'd input the maze by hand.

I had two problems to solve, then. First, I had to figure out a good data structure to represent the maze. I thought a directed graph with the intersections as vertices seemed like a good representation to me, but the matricial nature of the maze was also appealing. So I decided on a compromise: I'd store the maze as a matrix, but each element of the matrix would be a vertex, which would be represented as a set of arrows.

The second problem related to how I'd represent the maze before inputting it. I decided to write it down as a big string and then parse it, but that still leaves the problem of what to write. I pondered writing each edge, but that seemed a bit error-prone. So I decided on a rather unconventional format: I'd write the directions going out from each intersection, as well as undirected edges represented by the two directions the edge connects.

In effect, the actual vertices of my graph are not the intersections, but the streets! Each intersection is just a set of directed edges.

So, having decided all that, I wrote down the data I expected to be used for the maze:


 val graphString = """|
                      |DR: DR, RLD: RD LD, L: DL LR, LR: DR LR, DL: DL
                      |UR: LU RU DU LR, LRD: LR UD LU RU LD RD, UDLR: UD LR UR LD, UDLR: UD LR RD, UL: UD UL
                      |UDR: UD RU RD, UDLR: LR LD DR RU, UD: UD UL DL, UDR: UD UR, UD: UD LD
                      |UDR: UD RU RD, UDLR: UR UL LR RD, UR: UD LR LU RU DR, ULR: LR UR UL DR DL, UDLR: UD UL DR
                      |UR: UR, ULR: UL UR LR, ULR: UL UR RL, ULR: UL UR RL, UL: UL
                      |""".stripMargin

Ugly as hell, but it should do the job. My task, then, was to specify the data structure, and write a parser for that.

First, directions. Not only my input is written in terms of directions, I was thinking of solving the problem by manipulating directions. So, let's create them. I don't particularly like Scala's Enumeration class, so I went with case objects:


object DirectionSet {
 sealed abstract class Direction
 case object Up extends Direction
 case object Down extends Direction
 case object Left extends Direction
 case object Right extends Direction
 val U = Up
 val D = Down
 val L = Left
 val R = Right
}

That gives me warnings on pattern matching, and short aliases for each direction. Please note, though, that Scala already has objects called Left and Right. This shouldn't present much of a problem, but, once I improved on these objects a bit, I made sure Scala knew to which objects I was referring to. Let's talk about these improvements and show them.

As I wrote the code, I found myself needing to get the opposite direction to the one I had. This was clearly a method to be added to Direction, and so I did. Another thing I did was to write a function to convert a Char into a Direction. Later, while refactoring, it was clear this function was better as a DirectionSet method, so I added it, and, while doing it, wrote a variant for Strings, though I never use it in my final code. Let's see, them, the full object:


object DirectionSet {
 sealed abstract class Direction {
   def opposite: Direction
 }
 case object Up extends Direction { override def opposite = DirectionSet.Down }
 case object Down extends Direction { override def opposite = DirectionSet.Up }
 case object Left extends Direction { override def opposite = DirectionSet.Right }
 case object Right extends Direction { override def opposite = DirectionSet.Left }
 val U = Up
 val D = Down
 val L = Left
 val R = Right
 def apply(s: Char): Direction = s.toLowerCase match {
   case 'u' => Up
   case 'd' => Down
   case 'l' => Left
   case 'r' => Right
   case _ => throw new IllegalArgumentException
 }
 def apply(s: String): Direction = s.toLowerCase match {
   case "up" => Up
   case "down" => Down
   case "left" => Left
   case "right" => Right
   case _ => throw new IllegalArgumentException
 }
}

And that's that. So, let's proceed. Our graph is composed of intersections, each of which is composed of the arrows present at that intersection. The next step, then, is defining these arrows. Here's how I did it:


import DirectionSet.{apply => _, _}


case class Arrow(from: Direction, to: Direction) {
 override def toString = from+"->"+to
} 
object Arrow {
 def apply(t: Tuple2[Direction,Direction]): Arrow = new Arrow(t._1, t._2)
}

Each arrow is described as going from a Direction to another Direction. A couple of helper methods, and we are done. At first, it might seem that the intersection being just a set of arrows, so it doesn't need a class of it's own. However, to validate the correctness of the maze I inputted, it would be nice to have a more "graphical" representation of it. I could leave that to the graph class, but, as it happens, it's a rather long code, so I separated it into a class of its own.

So, first, I decided on the ASCII-art I'd be using to represent an intersection. I got it in as a literal, converted it into an array of arrays, and then, in the class main constructor, changed each relevant character from the ASCII-art into a space if the intersection didn't contain the corresponding arrow. The central character was a little bit more complex than that, and I used some pattern matching on it. Here's the final result:


case class Intersection(arrows: List[Arrow]) {
 private val drawing = """|  ^ 
                          | /|\
                          |<-+->
                          | \|/
                          |  v  """.stripMargin split "\n" map (_ toArray)
 private def hasUp = arrows exists (_.to == Up)
 private def hasDown = arrows exists (_.to == Down)
 private def hasLeft = arrows exists (_.to == Left)
 private def hasRight = arrows exists (_.to == Right)
 private def hasArrowBetween(a: Direction, b: Direction) = (arrows contains Arrow(a, b)) || (arrows contains Arrow(b, a))
 private def testAndSet(line: Int, col: Int, test: Boolean) =
   if (!test) drawing(line)(col) = ' '

 testAndSet(0, 2, hasUp)
 testAndSet(1, 1, hasArrowBetween(Left, Up))
 testAndSet(1, 2, hasArrowBetween(Up, Down))
 testAndSet(1, 3, hasArrowBetween(Up, Right))
 testAndSet(2, 0, hasLeft)
 testAndSet(2, 1, hasArrowBetween(Left, Right))
 testAndSet(2, 3, hasArrowBetween(Left, Right))
 testAndSet(2, 4, hasRight)
 testAndSet(3, 1, hasArrowBetween(Left, Down))
 testAndSet(3, 2, hasArrowBetween(Up, Down))
 testAndSet(3, 3, hasArrowBetween(Down, Right))
 testAndSet(4, 2, hasDown)
 drawing(2)(2) = (hasArrowBetween(Left, Right), hasArrowBetween(Up, Down)) match {
   case (false, false) => ' '
   case (false, true) => '|'
   case (true, false) => '-'
   case (true, true) => '+'
 }
  
 override def toString = drawing map (_ mkString) mkString "\n"
}
object Intersection {
 def apply(arrows: Arrow*): Intersection = new Intersection(arrows.toList)
}

The main class, the graph, started as simple as this:


case class Graph(g: Array[Array[Intersection]])

After that, I started on the parser. The first thing was breaking up the string into basic components: each line, each intersection on the line, the outgoing arrows and the edges:


def brkString(s: String) = s.trim split "\n" map (_.trim split "," map (_.trim split ":"))

Lot's of "trim" just so I needn't worry where there were space. The next two steps were easy: for each line, for each intersection... It looks like a for-comprehension, but to return an array of arrays I'd need to nest two for-comprehensions, which makes them unyieldy. It's better simply to go with "map". So, given the input string representing each intersection, return an intersection instance. The mapping code ended looking like this:


   (
     brkString(s)
     map (line =>
       line map (col =>
         Intersection(arrows(col): _*)
       )
     )
   )

Which leaves just "arrows" to be defined. The idea behind "arrows" is to convert each letter into a direction, then, for each direction representing an outgoing arrow, find all undirected edges containing that direction and yield a directed edge in the form of an Arrow instance:


   def arrows(a: Array[String]): List[Arrow] = {
     def str2Directions(s: String): List[Direction] = s map (DirectionSet(_)) toList
     val dsts = str2Directions(a(0).trim)
     val paths = a(1).trim split "\\s+" map str2Directions
     for(dst <- dsts;
         path <- paths if path contains dst;
         org <- path filter (_ != dst))
     yield Arrow(org, dst)
   }

These functions were all independent originally, but, as I refactored, they came to be part of the Graph object:


object Graph {
 def apply(s: String) = new Graph(str2Graph(s))

 def str2Graph(s: String) = {
   def brkString(s: String) = s.trim split "\n" map (_.trim split "," map (_.trim split ":"))
   def arrows(a: Array[String]): List[Arrow] = {
     def str2Directions(s: String): List[Direction] = s map (DirectionSet(_)) toList
     val dsts = str2Directions(a(0).trim)
     val paths = a(1).trim split "\\s+" map str2Directions
     for(dst <- dsts;
         path <- paths if path contains dst;
         org <- path filter (_ != dst))
     yield Arrow(org, dst)
   }
   (
     brkString(s)
     map (line =>
       line map (col =>
         Intersection(arrows(col): _*)
       )
     )
   )
 }
}

With that I could now create an instance of my graph. I could verify each intersection individually, but printing them side by side posed a problem: each intersection was composed of multiple lines, so I needed to interpolate the lines of all intersections belonging the the same "line" in the graph before I could concatenate them.

I approached this as a general problem in concatenating string with multiple lines. I'd split each string into its component lines, and keep a list of those. I'd then try to "fold" them into a big string, but that was too hacky for my tastes. I then modified it to iterate over these lists, concatenating the "heads" and looping with the "tails". Finally, I'd take each of those lines of intersection, and concatenate with interpoling newlines to the next. Here's the final result:


 override def toString = {
   def concatStrings(ss: String*) = {
     // Turn my arguments into a list of lists of lines, get the length
     // of the biggest chunk, a pad of the same size, and a function to
     // make them all the same length
     val lines = ss.toList map (_ split "\n" toList)
     val maxLineSize = lines flatMap (_ map (_ length)) reduceLeft (_ max _)
     val pad = " " * maxLineSize
     def fmtStr(s: String) = "%"+maxLineSize+"s" format s

     // Make an iterator for "lines"
     def tailOrNil[T](l: List[T]) = if (l.isEmpty) Nil else l.tail
     def getTails[T](l: List[List[T]]): List[List[T]] = l map tailOrNil[T]
     def hasLines(l: List[List[_]]) = l exists (!_.isEmpty)
     val linesIterator = Iterator.iterate(lines)(getTails) takeWhile hasLines

     // Get the head of each list, or a pad in the absence of a head,
     // make them all the same size, and then concatenate with an interpoling
     // pad.
     def concatHead(l: List[List[String]]): String =
       l map (_.headOption getOrElse pad) map fmtStr mkString pad
    
     // Iterate over lines, concatenating the heads of the list, and then
     // concatenate them all with interpolating newlines
     (for(nextLines <- linesIterator)
      yield concatHead(nextLines)) mkString "\n"
   }
   g map (line => concatStrings(line map (_ toString): _*)) mkString "\n\n\n"
 }

You can tell by the amount of comments that I'm not really satisfied with it yet, but it does its job. Here's an example:






   >     <   >     <---      <--->     <
  /       \ /       \           /       \
 v         v                             v




 ^                   ^         ^         ^
/|\       /|\        |\        |        /|
-+->     <-+->     <-+->     <-+->     < |
 |        \|/       \|         |/        |
           v         v         v




 ^         ^         ^         ^         ^
 |\         \       /|         |\        |
 | >     <--->       |         | >       |
 |/       \ /       \|         |        \|
 v         v         v         v         v




 ^         ^         ^         ^         ^
 |\       / \       /|\       / \       /|
 | >     <--->      -+->     <--->     < | >
 |/         /        |/       \ /        |/
 v         v                             v




 ^         ^         ^         ^         ^
  \       / \       / \       / \       /
   >     <--->     <--->     <--->     <

Now I started on the solving algorithm properly. This part of it was rather faster and problem-free. First, I had to have a way to indicate where my car was. I created a class Position for that. This class has two components: one is the actual coordinates, indicating at which intersection the car had stopped -- I called it Coordinates. The other component is the direction from which the car was entering the intersection. Here's the class:


case class Coordinates(line: Int, column: Int) {
 override def toString = "("+line+","+column+")"
}
case class Position(from: Direction, at: Coordinates) {
 override def toString = from.opposite.toString.toLowerCase+" to "+at
}

They didn't have any toString method originally. When I finally got to print the answer, I changed those methods to make the answer more readable.

Finally, I added a couple of methods to Graph. First, given a Position, to which directions the car could go? This one is quite natural:


 def directionsFrom(pos: Position):List[Direction] = (
   g(pos.at.line)(pos.at.column).arrows
   filter (_.from == pos.from)
   map (_.to)
 )

Next, given a Position, which would be the next available positions? This one required a helper method, which would compute the correct coordinates when moving in a given direction. I use "opposite" here. The idea is that, if I'm going "down", for example, I'd end at the upper side of the next intersection.


 def positionsFrom(pos: Position): List[Position] = {
   def moveTo(to: Direction) = Position(to.opposite, to match {
       case Up => Coordinates(pos.at.line - 1, pos.at.column)
       case Down => Coordinates(pos.at.line + 1, pos.at.column)
       case Left => Coordinates(pos.at.line, pos.at.column - 1)
       case Right => Coordinates(pos.at.line, pos.at.column + 1)
   })
   directionsFrom(pos) map moveTo
 }

And, with that, we are ready to solve the problem. All we need to do is keep following the coordinates. Since I receive a list of coordinates at each intersection, I have to try all of them. There's two ways of going about it. First, I can take the first option out of each intersection and keep going, until I start looping around, get to a dead end, or arrive at my destination. I can then opt to backtrack and try one of the other options. That's a depth first algorithm, a natural for recursion.

Alternatively, I can keep a list of all possible paths, and keep extending each one until one arrives. That can be done nicely with queues. I take one path from the beginning of a queue, compute all possible paths from there, and add them to the back of the queue. Once I find a path that has arrived at the goal, I stop. This is what I decided to do. Here's the algorithm:


 val graph = Graph(graphString)
 val origin = Position(Left, Coordinates(1, 0))
 val goal = Coordinates(3, 5)

 def solve = {
   import scala.collection.mutable.{Set, Queue}
  
   def nextPaths(path: Path, visited: Set[Position]): List[Path] = (
     graph
     positionsFrom path.head
     filter (to => !(visited contains to))
     map (to => to :: path)
   )
   val visited = Set[Position]()
   val next = new Queue[Path]()
   var path = List(origin)
   while(path.head.at != goal) {
     visited += path.head
     next enqueue (nextPaths(path, visited): _*)
     path = next dequeue
   }
   printAnswer(path)
 }

I still did a little trick to print the answer in a readable way, but it was hacky enough that I won't get into details. Here's the whole program, though. You can paste it directly into REPL and run it with "Problem.solve", or compile it and run Problem. So, how would you code this in YOUR favorite language? Please drop me a link on the comments below if you take this challenge too.


object DirectionSet {
 sealed abstract class Direction {
   def opposite: Direction
 }
 case object Up extends Direction { override def opposite = DirectionSet.Down }
 case object Down extends Direction { override def opposite = DirectionSet.Up }
 case object Left extends Direction { override def opposite = DirectionSet.Right }
 case object Right extends Direction { override def opposite = DirectionSet.Left }
 val U = Up
 val D = Down
 val L = Left
 val R = Right
 def apply(s: Char): Direction = s.toLowerCase match {
   case 'u' => Up
   case 'd' => Down
   case 'l' => Left
   case 'r' => Right
   case _ => throw new IllegalArgumentException
 }
 def apply(s: String): Direction = s.toLowerCase match {
   case "up" => Up
   case "down" => Down
   case "left" => Left
   case "right" => Right
   case _ => throw new IllegalArgumentException
 }
}

import DirectionSet.{apply => _, _}

case class Arrow(from: Direction, to: Direction) {
 override def toString = from+"->"+to
} 
object Arrow {
 def apply(t: Tuple2[Direction,Direction]): Arrow = new Arrow(t._1, t._2)
}

case class Intersection(arrows: List[Arrow]) {
 private val drawing = """|  ^ 
                          | /|\
                          |<-+->
                          | \|/
                          |  v  """.stripMargin split "\n" map (_ toArray)
 private def hasUp = arrows exists (_.to == Up)
 private def hasDown = arrows exists (_.to == Down)
 private def hasLeft = arrows exists (_.to == Left)
 private def hasRight = arrows exists (_.to == Right)
 private def hasArrowBetween(a: Direction, b: Direction) = (arrows contains Arrow(a, b)) || (arrows contains Arrow(b, a))
 private def testAndSet(line: Int, col: Int, test: Boolean) =
   if (!test) drawing(line)(col) = ' '

 testAndSet(0, 2, hasUp)
 testAndSet(1, 1, hasArrowBetween(Left, Up))
 testAndSet(1, 2, hasArrowBetween(Up, Down))
 testAndSet(1, 3, hasArrowBetween(Up, Right))
 testAndSet(2, 0, hasLeft)
 testAndSet(2, 1, hasArrowBetween(Left, Right))
 testAndSet(2, 3, hasArrowBetween(Left, Right))
 testAndSet(2, 4, hasRight)
 testAndSet(3, 1, hasArrowBetween(Left, Down))
 testAndSet(3, 2, hasArrowBetween(Up, Down))
 testAndSet(3, 3, hasArrowBetween(Down, Right))
 testAndSet(4, 2, hasDown)
 drawing(2)(2) = (hasArrowBetween(Left, Right), hasArrowBetween(Up, Down)) match {
   case (false, false) => ' '
   case (false, true) => '|'
   case (true, false) => '-'
   case (true, true) => '+'
 }
  
 override def toString = drawing map (_ mkString) mkString "\n"
}
object Intersection {
 def apply(arrows: Arrow*): Intersection = new Intersection(arrows.toList)
}

case class Coordinates(line: Int, column: Int) {
 override def toString = "("+line+","+column+")"
}
case class Position(from: Direction, at: Coordinates) {
 override def toString = from.opposite.toString.toLowerCase+" to "+at
}

case class Graph(g: Array[Array[Intersection]]) {
 def directionsFrom(pos: Position): List[Direction] = (
   g(pos.at.line)(pos.at.column).arrows
   filter (_.from == pos.from)
   map (_.to)
 )

 def positionsFrom(pos: Position): List[Position] = {
   def moveTo(to: Direction) = Position(to.opposite, to match {
       case Up => Coordinates(pos.at.line - 1, pos.at.column)
       case Down => Coordinates(pos.at.line + 1, pos.at.column)
       case Left => Coordinates(pos.at.line, pos.at.column - 1)
       case Right => Coordinates(pos.at.line, pos.at.column + 1)
   })
   directionsFrom(pos) map moveTo
 }

 override def toString = {
   def concatStrings(ss: String*) = {
     // Turn my arguments into a list of lists of lines, get the length
     // of the biggest chunk, a pad of the same size, and a function to
     // make them all the same length
     val lines = ss.toList map (_ split "\n" toList)
     val maxLineSize = lines flatMap (_ map (_ length)) reduceLeft (_ max _)
     val pad = " " * maxLineSize
     def fmtStr(s: String) = "%"+maxLineSize+"s" format s

     // Make an iterator for "lines"
     def tailOrNil[T](l: List[T]) = if (l.isEmpty) Nil else l.tail
     def getTails[T](l: List[List[T]]): List[List[T]] = l map tailOrNil[T]
     def hasLines(l: List[List[_]]) = l exists (!_.isEmpty)
     val linesIterator = Iterator.iterate(lines)(getTails) takeWhile hasLines

     // Get the head of each list, or a pad in the absence of a head,
     // make them all the same size, and then concatenate with an interpoling
     // pad.
     def concatHead(l: List[List[String]]): String =
       l map (_.headOption getOrElse pad) map fmtStr mkString pad
    
     // Iterate over lines, concatenating the heads of the list, and then
     // concatenate them all with interpolating newlines
     (for(nextLines <- linesIterator)
      yield concatHead(nextLines)) mkString "\n"
   }
   g map (line => concatStrings(line map (_ toString): _*)) mkString "\n\n\n"
 }
}
object Graph {
 def apply(s: String) = new Graph(str2Graph(s))

 def str2Graph(s: String) = {
   def brkString(s: String) = s.trim split "\n" map (_.trim split "," map (_.trim split ":"))
   def arrows(a: Array[String]): List[Arrow] = {
     def str2Directions(s: String): List[Direction] = s map (DirectionSet(_)) toList
     val dsts = str2Directions(a(0).trim)
     val paths = a(1).trim split "\\s+" map str2Directions
     for(dst <- dsts;
         path <- paths if path contains dst;
         org <- path filter (_ != dst))
     yield Arrow(org, dst)
   }
   (
     brkString(s)
     map (line =>
       line map (col =>
         Intersection(arrows(col): _*)
       )
     )
   )
 }
}

object FormatLines {
 def apply(s: String): String = {
   def breakAt80(s: String): (String, String) = {
     val m = """^(.{0,80})( (.*))?$""".r findFirstMatchIn s
     m match {
       case Some(result) =>
       val rest = if (result.group(3) == null) "" else result.group(3)
       (result.group(1), rest)
       case None => (s, "")
     }
   }
   def fmt(input: String, output: String): String =
   if (input.isEmpty)
   output
   else {
     val (nextLine, rest) = breakAt80(input)
     fmt(rest, output+nextLine+"\n")
   }
   fmt(s, "")
 }
}

object Problem {
 type Path = List[Position]
 val graphString = """|
                      |DR: DR, RLD: RD LD, L: DL LR, LR: DR LR, DL: DL
                      |UR: LU RU DU LR, LRD: LR UD LU RU LD RD, UDLR: UD LR UR LD, UDLR: UD LR RD, UL: UD UL
                      |UDR: UD RU RD, UDLR: LR LD DR RU, UD: UD UL DL, UDR: UD UR, UD: UD LD
                      |UDR: UD RU RD, UDLR: UR UL LR RD, UR: UD LR LU RU DR, ULR: LR UR UL DR DL, UDLR: UD UL DR
                      |UR: UR, ULR: UL UR LR, ULR: UL UR RL, ULR: UL UR RL, UL: UL
                      |""".stripMargin
 val graph = Graph(graphString)
 val origin = Position(Left, Coordinates(1, 0))
 val goal = Coordinates(3, 5)

 def printAnswer(path: Path) {
   val answer = FormatLines(
     "Arrived at "+path.head.at+
     " through "+path.tail.reverse.mkString(", ")+
     " and then "+path.head.from.opposite.toString.toLowerCase+"."
   )
   println(graph)
   println(answer)
 }

 def solve = {
   import scala.collection.mutable.{Set, Queue}
  
   def nextPaths(path: Path, visited: Set[Position]): List[Path] = (
     graph
     positionsFrom path.head
     filter (to => !(visited contains to))
     map (to => to :: path)
   )
   val visited = Set[Position]()
   val next = new Queue[Path]()
   var path = List(origin)
   while(path.head.at != goal) {
     visited += path.head
     next enqueue (nextPaths(path, visited): _*)
     path = next dequeue
   }
   printAnswer(path)
 }

 def main(args: Array[String]) {
   solve
 }
}

Regex and Option trick

2009-08-17T18:39:00.006-03:00

Neat trick:


def findBetween(s: String, p1: String, p2: String) = (
  ("\\Q"+p1+"\\E(.*?)\\Q"+p2+"\\E").r 
  findFirstMatchIn s 
  map (_ group 1) 
  getOrElse ""
)

The trick here is that map, on an Option, applies the function if the option is Some, otherwise returns None. So I get to convert my Match into a particular group before I check if I got anything at all and return a default if not.

Software Engineering -- An Idea Whose Time Has Gone?

2009-07-19T20:11:00.004-03:00

That's a powerful statement over there. One I'd never dare state (aloud, at least :). They are not my words, though, they are Tony DeMarco's, who famously said "You can't control what you can't measure" in his book, Controlling Software Projects: Management, Measurement, and Estimation, Prentice Hall/Yourdon Press, 1982.

Well, he hasn't changed his mind about that, but he seems to have come to the conclusion that the relative value of that, particularly balanced against the costs of measuring -- which he once discounted -- is not what he once thought. You can read it on this IEEE-published article.

Getting Around Type Erasure with Manifests

2009-07-07T15:51:00.002-03:00

A friend posed an interesting problem to me yesterday. He wanted a registry-like structure in which he would put pairs of key/value, and then get them back. However, he wished for it to be type-safe. Specifically, if he put a List[Int] inside it, and tried to get a List[String] out, he shouldn’t get anything.

This is generally a problem because of type erasure, a restriction of the JVM. At runtime, a List object knows it is a List, but not of what kind of element.

Alas, an obscure, and experimental, feature of Scala let you get around that. It’s the Manifests. A Manifest is class whose instances are objects representing types. Since these instances are objects, you can pass them around, store them, and generally call methods on them. With the support of implicit parameters, it becomes a very powerful tool:


object Registry {
  import scala.reflect.Manifest
  
  private var _map= Map.empty[Any,(Manifest[_], Any)] 
  
  def register[T](name: Any, item: T)(implicit m: Manifest[T]) {
    _map = _map(name) = (m, item)
  }
  
  def get[T](key:Any)(implicit m : Manifest[T]): Option[T] = {
    val o = _map.get(key)
   
    o match {
      case Some((om: Manifest[_], s : Any)) =>
        if(om <:< m) Some(s.asInstanceOf[T]) else None
      case _ => None
    }
  }
}

scala> Registry.register('a, List(1,2,3))

scala> Registry.get[List[Int]]('a)
res6: Option[List[Int]] = Some(List(1, 2, 3))

scala> Registry.get[List[String]]('a)
res7: Option[List[String]] = None

Above, Manifest is being passed as an implicit parameter – defined inside scala.reflect.Manifest – based on the type parameter T, and stored along the value. When you put a value in the register, it is not necessary to specify its type, as this gets inferred.

When you take a registry out, though, you specify the type the type you want (inference won’t help you here), and, if the key does not exist or does not store the desired type, it will return None. If a key exists and the type is correct, it will return Some(value).

Note that the operator <:< tests for subclassing. That is, the desired type m must be a superclass of the stored type om.

Delimited Continuations Explained (in Scala)

2009-07-04T02:04:00.008-03:00

One of the promised features for Scala 2.8 is a delimited continuations plugin. A brief description was given in the Scala site, though the examples were, in my opinion, badly chosen.

Though my understanding is still pretty bare, I intend to shed a bit of light on it here. This is not directed at the experts, the people who will actually use them regularly, but at the people who will see them occasionally and will wonder what the heck is happening. Also, I might quite possibly have made mistakes below. If you do find mistakes, please correct me and I’ll fix the post.

First, let’s discuss why Scala is adopting continuations, and what, exactly, are them.

Continuations are, in essence, a program flow control structure, like conditional statements, loops, exceptions, etc. As mentioned in Scala’s Continuations Paper, classical, or full, continuations can be seen as a functional version of GOTO statements. If you haven’t heard of GOTO statements before, it’s enough to know they are essentially extinct for good reason.

Still quoting, delimited continuations are more like regular functions and less like GOTOs, and this makes them more powerful than the classical ones. So, basically, we are looking into a way of changing the execution flow of a program.

Using continuations is not easy. In fact, it’s difficult and error-prone, according to some references. But they can be very efficient performance-wise, and they allow one to build libraries with some interesting flow control abstractions built on top of continuations.

For these reasons, I doubt most Scala users will have much contact with them, and I suspect the ones who do will regret the necessity. The people writing libraries and frameworks, though, will likely be grateful that they are available. In that respect, continuation is not unlike some other advanced Scala features.

Ok, so let’s get to them. In Scala, continuations will be used through two keywords (or functions?), “reset” and “shift”. Like “catch” and “throw”, a “shift” always happen inside a “reset”, the later being responsible for delimiting the scope of the continuation. Before we proceed, let’s give some usage examples, which I’ll then try to explain.

Example 1:


reset {
shift { k: (Int=>Int) =>
 k(7)
} + 1
}
// result: 8

Example 2:


def foo() = {
println("Once here.")
shift((k: Int => Int) => k(k(k(7))))
}
def bar() = {
1+ foo()
}
def baz() = {
reset(bar() * 2)
}
baz()  // result 70

Example 3:


reset {
 println(1)
}
//prints: 1

reset {
 println(1)
 shift { (cont: Unit => Unit) => }
 println(2)
}
//prints: 1

reset {
 println(1)
 shift { (cont: Unit => Unit) =>
     println(2)
 }
 println(3)
}
//prints: 1 2

reset {
 println(1)
 shift { (cont: Unit => Unit) =>
     cont()
     println(2)
 }
 println(3)
}
//prints: 1 3 2

reset {
 println(1)
 shift { (cont: Unit => Unit) =>
     cont()
     cont()
     println(2)
 }
 println(3)
}
//prints: 1 3 3 2

So we have two examples of continuations as expressions, and one as purely flow control. The first example seems pretty simple: the whole shift is replaced with “7”, and, therefore, reset returns “7+1”. The third example shows that, in fact, the code before shift is executed once, the code after shift as many times as the function inside shift is repeated, and the code inside the shift itself is executed once, going back and forth to the code after it.

So we look at the second example, and see that… the code before shift seems to get executed many times! Actually, the method receiving the result of shift is being executed many times, once for each time “shift” return, but the statement right before shift only gets executed once.

These examples were probably enough to… make things more confusing, right? So let’s understand what is happening. Scala’s continuations are based on a selective Continuation Passing Style (CPS) transformation. The Wikipedia page on CPS is actually pretty good, so, please, take a moment to peruse it, and understand the examples given at the beginning, and then come back here.

Ready? Well, one thing that immediately came to mind is that this looks like programming backwards! They call it “inside-out” in that page, which is more appropriate, I suppose, but one has to pay attention to first impressions. :-)

What is happening there is that the innermost functions of normal programming style are outmost, and vice versa. You’ll see that this is what is happening with shift and reset.

I’ll now explain a bit of what is happening in a continuation. Notice, first, that the code associated with the shifts are functions: they are all in the form { k => … }. So, the first thing to keep in mind is that shifts are functions taking a parameter.

Now, pay attention, again, to the very first example. It defines the type of k as being “Int => Int”. In the first example, then, shift is a function which takes as parameter another function. This is actually true of all shifts, even if the function being passed to shift takes no parameters and returns Unit.

So a shift is a function which receives another function as parameter. As the body of the shift gets executed, that function-parameter may get called or not. From the second example, it is pretty obvious that the code after the shift only gets executed if that function-parameter is called.

By now you probably have an uneasy intuition that that parameter is, in fact, the code after the shift. That’s essentially right, but let’s further into this.

The result of reset is the result of the code inside shift. So, in the first example, “8”, the result of reset, is also the result of the shift code, “k: (Int => Int) => k(7)”. It should be obvious, then, that the value passed to “k” is “x: Int => x + 1”, which is a function of Int => Int, as required. Now, take a look at the two lines below:


shift { k: (Int=>Int) => k(7) } + 1
x                               + 1

So, the function being passed as parameter is formed by taking the whole code from the shift on, and replacing shift with “x”. In effect, when k(7) is executed, this is like replacing the whole shift with 7, and then continuing until the end of reset. At that point, though, the execution resumes inside the shift. In this example there is nothing more in there, so the result is 8.

What is actually happening is this:


((k: Int => Int) => k(7))((x: Int) => x + 1)

As said before, we are passing a function to another. You can paste that code inside REPL and it will work as expected. You may also try this code here:


((k: Int => Int) => k(k(k(7))))((x: Int) => (1 + x) * 2)

Are you getting a feeling now for it? So, whenever you see reset/shift, first think of the whole reset expression, replacing the shift inside it with an unknown variable – we’ll keep calling it x for now:


Reset { before shift { k => ... k(something) ... } after }
Reset { before x after }

Now replace Reset with a function declaration of one parameter:


Reset { before x after }
x => { before x after }

What type is “x” supposed to be? You can find it inside the shift, by looking into what is being passed to “k” – the “something” in the example. We can now rewrite the whole reset statement, placing first the shift code, then the reset code as parameter, like we did before:


( k => ... k(something) ... ) {x => { before x after }}

And this is pretty much what happens when you use continuations.

As for the second example, though the “1 + “ looks to be to the “left” of shift, it actually gets executed after shift returns, so it is part of the function being passed to shift. You find the same situation when making tail recursive functions. If you tried “1 + recurse()”, it would not be tail recursive, because “+” would only be executed after the call to “recurse” returned.

Pretty easy, right? Let’s try something with two shifts:


type Monadic[+U, C[_]] = {
def flatMap[V](f: U => C[V]): C[V]
}

class Reflective[+A, C[_]](xs: Monadic[A,C]) {
def reflect[B](): A @cps[C[B], C[B]] = {
 shift { k:(A => C[B]) =>
   xs.flatMap(k)
 }
}
}

implicit def reflective[A](xs:Iterable[A]) =
new Reflective[A,Iterable](xs)

reset {
val left = List("x","y","z")
val right = List(4,5,6)

List((left.reflect[Any], right.reflect[Any]))
}
// result: List[(String, Int)] = List((x,4), (x,5), (x,6), (y,4), (y,5), (y,6), (z,4), (z,5), (z,6)

Don’t hate me, it is in good cause. :-) If you can understand this… well, you can understand this. But I’m sure you’ll start to really get a grip in it.

First, let’s discard the irrelevant parts of the code above. Everything but the “reflect” definition and the reset code is irrelevant. They are there just to make “reflect” available to a List, it’s plain-old Enrich My Library pattern, though the use of a structural type is cool. :-)

Now, let’s replace left.reflect and right.reflect with the actual code getting executed – I’ll change k into k1 and k2 so as not to confuse both, so we are left only with the reset code:


reset {
val left = List("x","y","z")
val right = List(4,5,6)

List((shift { k1:(String => List[Any]) => left.flatMap(k1)}, shift { k2:(Int => List[Any]) => right.flatMap(k2)}))
}

Since there are two shifts, should we have two unknowns being passed to shift? If you look at the type signatures for k1 and k2, the answer is no. Each shift gets a single parameter.

You may think that the “Any” type means one list is formed by a single element, and the other by a tuple, but that’s not true. You can change both types to “List[(String,Int)]”, and it would still work. No, the type signatures are right, the trick is in how they are composed together.

If you think it through simply in terms of flow control, the first shift will return a value (“x”), and then the second shift will return a value (4), producing a list. The flow then returns to the last shift, which will return another value (5), and then another still (6). At this point, the flow returns once again to the first shift, which will produce it’s next value (“y”). So the trick is in how we compose the functions.

Let’s see, first, both shifts:


((k1: String => List[(String,Int)]) => left.flatMap(k1))
((k2: Int => List[(String,Int)]) => right.flatMap(k2))

These can’t and won’t be changed. The trick is how we compose them:


((k1: String => List[(String,Int)]) => left.flatMap(k1))
((x: String) => ((k2: Int => List[(String,Int)]) => right.flatMap(k2))
             ((y: Int) => List((x,y)))
)

So what happens is that the function which takes a String and returns a List of (String,Int) that gets passed to the first shift is composed of both the reset function and the second shift function.

The function passed to the second shift does not need an additional String parameter because the string is already bound.

Now you have seen both the control flow of reset/shift, and how to translate them into common functions to understand what values they will produce. I hope it will be of help when the time comes in which you need to understand these structures.

Note: many things have changed since I wrote this blog. Continuations have gone through minor changes in the annotations, and collections have gone through big changes. I haven't checked out all examples yet, but I know the one with the two lists doesn't work anymore. The following code will work for that example, though I wish I could make it more general than it presently is:


type Monadic[+U, C[_]] = {
  def flatMap[V, That](f: U => C[V])(implicit cbf: collection.generic.CanBuildFrom[C[U], V, That]): That
}

class Reflective[+A](xs: Monadic[A,Traversable]) {
  def reflect[B](): A @cps[Traversable[B]] = {
    shift { k:(A => Traversable[B]) =>
      xs.flatMap(k)(collection.breakOut) : Traversable[B]
    }
  }
}

implicit def reflective[A](xs:Traversable[A]) = new Reflective[A](xs)

reset {
  val left = List("x","y","z")
  val right = List(4,5,6)

  List((left.reflect[Any], right.reflect[Any]))
}

Matrices 6

2009-07-02T17:29:00.002-03:00

In this last installment of the Matrices series, we’ll look into making the Matrix class parameterized. What does that means? Basically, we want to have Matrix declared like this:

class Matrix[T]

So that we can create matrices of Ints, Doubles, or whatever other numeric type we need. This is not a trivial exercise, because of the way numeric types are defined in Java, and Scala’s backward compatibility with it. Basically, there is no common superclass to them.

Paul Chisuano offered two alternatives around that. One would involve the “Enrich My Library” pattern, but I do not think it would offer any gains over MatrixInt as it was built, and I see a problem or two implementing it.

We’ll discuss the other solution he proposes, which is, indeed, very clever. If we were building this in Java, would idea would be creating an interface with the operations we need, and a concrete class for each type we need. For instance, let’s call our interface Scalar, and our concrete classes implementing it IntScalar, DoubleScalar, etc. We would then define a Matrix class parameterized with an “upper bound” of Scalar, created from an Array of Arrays of Scalar. That would work, but can be quite slow.

Instead of that, we’ll use one of the more wizardry of Scala’s features, the implicit type conversion argument. You have probably seen things like this before:


implicit def xToY(x: X): Y = Y(x)

This definition makes it possible to convert an object of class X to an object of class Y without explicitly doing so. If I ever need an object of class Y and I have an object of class X instead, Scala will apply that definition to object X without any explicit statement on my part to do so.

Even if you haven’t seen that before, you almost certainly have used it. See the two examples below:


scala> val a = 1.0; val b = 1
a: Double = 1.0
b: Int = 1

scala> a + b
res12: Double = 2.0

scala> val c = Map('a -> 1)
c: scala.collection.immutable.Map[Symbol,Int] = Map('a -> 1)

In each case, there is an implicit conversion at work. These definitions can, in fact, be found inside the object scala.Predef, which is imported automatically into scope of every Scala program. The first one is obvious, the second one, not so much. To understand the second, you have to realize that class Symbol does not define the method “->”, and that “->” is not a Scala keyword. I’ll leave as an exercise to find what implicit conversion is being used here.

What that means for us is that we can create a Scalar class, as well as implicit conversions from our desired types to it. Scalar would look like this:


abstract class Scalar[T](self: T) {
 def +(other: T): T
 def -(other: T): T
 def /(other: T): T
 def %(other: T): T
 def *(other: T): T
}

One thing to note here is that none of the operations defined for Scalar take another Scalar as argument, nor do they return a Scalar. The reason for this is that we do not want to store Scalars. They are bulky and inefficient. We just want to quickly convert an Int or Double into Scalar, and then produce, through an Int or Double operation, and Int or Double result to be stored in an Array, or returned as result of determinant or similar methods.

Even without implicits, we could define Matrix like this:


class Matrix[T](self: Array[Array[T]], toScalar: T => Scalar[T])

We could then use toScalar everywhere we do an operation over a type T. With implicit, we could just add an implicit definition to the top of class Matrix, so we don’t need bother explicitly using toScalar. But we don’t need to do even that. Look at the following definition:


class Matrix[T](self: Array[Array[T]])(implicit toScalar: T => Scalar[T])

This definition of Matrix constructor, with two sets of () for arguments, is said to be curried. I won’t be explaining what that means here, because what interests us is the implicit keyword in there. The important thing here is that when you define something like that, then two things useful for us happen:

1. If there is an implicit definition of the type “T => Scalar[T]” in scope when we call Matrix, then it will be automatically passed to the constructor. Or, in other words, you can call “new Matrix(Array(Array(1)))” anywhere there is an implicit definition from Int to Scalar[Int], without having to pass that implicit definition as well.
2. There is no need to define an implicit conversion inside Matrix itself. Any implicit conversion passed as an argument will already be used inside the class.

This rule is also valid for implicit conversions arguments on method definitions, by the way.

Anyway, this is so useful and powerful that Scala has another way of saying the same thing:


class Matrix[T <% Scalar[T]](self: Array[Array[T]])

The “<%” keyword means there should be an implicit conversion between the first type and the second in scope where Matrix constructor is called, or that one such conversion must be explicitly passed.

So, we search&replace every instance of MatrixInt for Matrix[T], define our constructor as above (plus minor details such as “private” and “val”), replace Int with T where appropriate (remember that row and column coordinates are still Ints!), create the Scalar class, the subclasses for the types we want, the implicit conversions, and we are done, right?

Not so. Scalar, alas, is not enough. If you look at the definitions of sign, isDivisibleBy and invert, you will see we mix “T” with -1, 0 and 1. Since we do not know that -1, 0 and 1 can be mixed with “T”, we still need something else. Alas, what we need is actually very simple: an implicit definition between Int and T, so that when we use -1, it can be converted to the proper type, be it Int, Double or whatever.

We have to be careful of one thing, though. See the two lines below:


map Function.tupled((value, col) => value * cofactor(0, col).determinant * sign(0, col))
map Function.tupled((value, col) => sign(0, col) * value * cofactor(0, col).determinant)

The first line works, because it is converted into this:


map Function.tupled((value, col) => toScalar(value) * toScalar(cofactor(0, col).determinant) * intToT(sign(0, col)))

The second line doesn’t work, as it would need to be converted into this:


map Function.tupled((value, col) => toScalar(intToT(sign(0, col))) * toScalar(value) * cofactor(0, col).determinant)

On the first line there was at most one implicit conversion for each parameter. On the second line, though, since T doesn’t have the method “*”, and Int doesn’t have the method “*(T)”, two implicit conversions would need to be applied.

Scala won’t apply two implicit conversions on the same element. In this case, we can make “sign” return T, so the extra implicit conversion will be applied inside “sign”, thus avoiding this rule. We need to be careful, however, about such situations. As it happens, MatrixInt, as it was written, won’t present any such problems.

Anyway, we need, thus, two implicit conversions. The “<%” syntax isn’t enough for our particular case, so we have to do it the other way. Here’s our Matrix declaration:


class Matrix[T] private (private val self: Array[Array[T]])
                       (implicit toScalar: T => Scalar[T], intToT: Int => T) {

Note that I write “implicit” only once in the declaration. All parameters in these last parentheses will be defined as implicit. Also, please note that implicit parameters must come last in such a declaration.

This does take care of almost everything, with a bit of judicious editing on various declarations to make the signatures match. There are some places, though, where that is not the case. Look at these lines inside the method “toString”:


   val maxNumSize = self.projection flatMap (_ map (_.toString.size)) reduceLeft (_ max _)
   val numFormat = "%"+maxNumSize+"d"
   def formatNumber(n: T) = numFormat format n

We obviously can’t use “%d” for Doubles, for one thing. Also, maxNumSize doesn’t quite cut it, since we would like numbers to be aligned on the decimal point (or comma, depending on your locale), so we need to know at least two sizes. And then there are complex numbers, and who knows what else, so we don’t really know what information might be needed.

Therefore, I feel it is better to leave the choice inside Scalar itself. I propose to add the method below to Scalar, define it for Int as shown next, and then use as show last:


abstract class Scalar[T](self: T) {
 ...
 def numFormat(xs: Iterator[T]): String
}

class IntScalar(self: Int) extends Scalar(self) {
 ...
 def numFormat(xs: Iterator[Int]) = {
   val maxNumSize = xs map (_.toString.size) reduceLeft (_ max _)
   "%"+maxNumSize+"d"
 }
}

 lazy val numFormat = this(0,0).numFormat(self flatMap (x => x) elements)
 override def toString = {
   def formatNumber(n: T) = numFormat format n
   ...

It would have been more appropriate to define that method inside a companion object, but this way is simpler. Note, as well, that “numFormat” became a visible property, so we can re-use all this logic inside LinearEquations.

Another place that needs fixing is inverse. We use the following rule:


 lazy val inverse: Option[Matrix[T]] =
   if (determinant == 0 || !isDivisibleBy(determinant))

Now, isDivisibleBy is implemented in terms of “%”, but that is just plain wrong for Double numbers. We could “fix” it by defining “%” to return 0, but that would make “%” act in a very unexpected way. So, instead, I’ll just define an “isDivisibleBy” operator inside Scalar:


 def isDivisibleBy(other: T): Boolean

The last problem, as far as I can see, is with the equality methods. You’ll get erasure warnings in them if you use “Matrix[T]” on the case statement of equals or inside asInstanceOf on canEqual. Instead, use “Matrix[_]”, to indicate you don’t care what type T is. Since we are doing a deepEquals, T will sort itself out.

The Scalar class and subclasses for Int and Double look like this:


abstract class Scalar[T](self: T) {
 def absolute: T
 def +(other: T): T
 def -(other: T): T
 def /(other: T): T
 def %(other: T): T
 def *(other: T): T
 def numFormat(xs: Iterator[T]): String
 override def numberSign: String
 def isDivisibleBy(other: T): Boolean
}

class IntScalar(self: Int) extends Scalar(self) {
 override def absolute = self.abs
 override def +(other: Int) = self + other
 override def -(other: Int) = self - other
 override def /(other: Int) = self / other
 override def %(other: Int) = self % other
 override def *(other: Int) = self * other
 override def numFormat(xs: Iterator[Int]) = {
   val maxNumSize = xs.map(_.toString.size).foldLeft(0)(_ max _)
   "%"+maxNumSize+"d"
 }
 override def numberSign = if (self < 0) "-" else "+"
 override def isDivisibleBy(other: Int) = (self % other) == 0
}

class DoubleScalar(self: Double) extends Scalar(self) {
 override def absolute = self.abs
 override def +(other: Double) = self + other
 override def -(other: Double) = self - other
 override def /(other: Double) = self / other
 override def %(other: Double) = self % other
 override def *(other: Double) = self * other
 override def numFormat(xs: Iterator[Double]) = {
   val numbers = xs.toList
   val maxIntSize = (
     numbers
     .map(_.toString.takeWhile(c => c != '.' && c != ',').length)
     .foldLeft(0)(_ max _)
   )
   val maxDecimalSize = (
     numbers
     .map(_.toString.dropWhile(c => c != '.' && c != ',').length)
     .foldLeft(0)(_ max _)
   ) - 1
   "%"+maxIntSize+"."+maxDecimalSize+"f"
 }
 override def numberSign = if (self < 0) "-" else "+"
 override def isDivisibleBy(other: Double) = true
}

Note that we transform “xs” into a List inside DoubleScalar. That’s because we are iterating through it twice, which isn’t possible with an Iterator. Also note we added “absolute” and “numberSign”, which are used by LinearEquations.

The method “absolute” is not called “abs”, though, because “abs” is defined on RichInt, RichDouble, etc. So if we defined it for IntScalar, and then tried to use “abs” on an Int, the compiler would not know whether to use RichInt’s abs or IntScala’s abs.

We’ll also add the following two lines to the Matrix companion-object:


 implicit def intToScalar(n: Int): Scalar[Int] = new IntScalar(n)
 implicit def doubleToScalar(n: Double): Scalar[Double] = new DoubleScalar(n)

This way these two types, Int and Double, will automatically become available after importing “Matrix._”. The user can arbitrarily extend Matrix to cover any type, though, by creating a subclass of Scalar and defining an implicit conversion from the desired type to it.

Performance-wise, the boxing of the numeric types for each operation is detrimental, but it can probably be optimized by either the compiler or the JIT. In Scala 2.8 there will also be the option of marking a class “specialized”, which is creates specially optimized versions of a class for Java’s “primitive” types. I’m not sure it applies in this situation, though.

I’ll finish with the revised code for Matrix. If you have any questions or suggestions, please send them to me and I’ll try to address them. I hope you found this series useful!


class Matrix[T] private (private val self: Array[Array[T]])
                       (implicit toScalar: T => Scalar[T], intToT: Int => T) {
 import Matrix._

 val rows = self.size
 val cols = self(0).size

 private def _row(n: Int): Array[T] = self(n)
 private def _col(n: Int): Array[T] = self map (_(n))

 def row(n: Int): Array[T] = _row(n) map (x => x)
 def col(n: Int): Array[T] = _col(n)

 def apply(i: Int, j: Int): T =
   if (i >= rows || j >= cols || i < 0 || j < 0)
     throw new IndexOutOfBoundsException
   else
     self(i)(j)

 def update(row: Int, col: Int, newValue: T): Matrix[T] =
   new Matrix(createArrays(rows, cols, (i,j) =>
     if (row == i && col == j) newValue else this(i,j)))

 def update(what: Dimension, where: Int, newValue: Array[T]): Matrix[T] =
   what match {
     case Row => replaceRow(where, newValue)
     case Column => replaceCol(where, newValue)
   }
    
 def replaceCol(col: Int, newValue: Array[T]): Matrix[T] =
   new Matrix(createArrays(rows, cols, (i,j) =>
     if (col == j) newValue(i) else this(i,j)))

 def replaceRow(row: Int, newValue: Array[T]): Matrix[T] =
   new Matrix(createArrays(rows, cols, (i,j) =>
     if (row == i) newValue(j) else this(i,j)))

 override def equals(other: Any): Boolean = other match {
   case that: Matrix[_] =>
     that.canEqual(this) && self.deepEquals(that.self)
   case _ => false
 }

 def canEqual(other: Any): Boolean = other.isInstanceOf[Matrix[_]]
  
 def *(n: T): Matrix[T] =
   new Matrix(createArrays(rows, cols, (row, col) => this(row,col) * n))

 def /(n: T): Matrix[T] =
   new Matrix(createArrays(rows, cols, (row, col) => this(row,col) / n))

 def %(n: T): Matrix[T] =
   new Matrix(createArrays(rows, cols, (row, col) => this(row,col) % n))

 def +(other: Matrix[T]): Matrix[T] =
   if (rows != other.rows || cols != other.cols)
     throw new IllegalArgumentException
   else
     new Matrix(createArrays(rows, cols, (row, col) => this(row,col) + other(row,col)))

 def -(other: Matrix[T]): Matrix[T] =
   if (rows != other.rows || cols != other.cols)
     throw new IllegalArgumentException
   else
     new Matrix(createArrays(rows, cols, (row, col) => this(row,col) - other(row, col)))

 def *(other: Matrix[T]): Matrix[T] =
   if (cols != other.rows)
     throw new IllegalArgumentException
   else
     new Matrix(createArrays(rows, other.cols, (row, col) =>
       this._row(row) zip other._col(col) map Function.tupled(_*_) reduceLeft (_+_)
     ))

 def **(n: Int): Matrix[T] =
   if (rows != cols)
     throw new UnsupportedOperationException
   else n match {
     case 0 => unitMatrix(rows)
     case 1 => this
     case 2 => this * this
     case negative if negative < 0 =>
       (this ** negative.abs).inverse getOrElse (throw new UnsupportedOperationException)
     case odd if odd % 2 == 1 => this ** (odd - 1) * this
     case even => this ** (even / 2) ** 2
   }

 def toArray = Matrix.clone(self)

 def transpose = new Matrix(createArrays(cols, rows, (row,col) => this(col,row)))

 def cofactor(row: Int, col: Int) = new Matrix(createArrays(rows-1, cols-1, (i,j) =>
   this(i + (if (i < row) 0 else 1), j + (if (j < col) 0 else 1))))

 protected def sign(row: Int, col: Int): T = if ((col + row) % 2 == 0) 1 else -1

 lazy val determinant: T =
   if (rows != cols)
     throw new UnsupportedOperationException
   else rows match {
     case 1 => this(0,0)
     case 2 => this(0,0)*this(1,1) - this(1,0)*this(0,1)
     case n => (
       _row(0).zipWithIndex
       map Function.tupled((value, col) => value * cofactor(0, col).determinant * sign(0, col))
       reduceLeft (_+_)
       )
     }

 def minor(row: Int, col: Int) = cofactor(row, col).determinant

 lazy val adjugate: Matrix[T] = new Matrix(createArrays(cols, rows, (row, col) =>
   minor(col, row) * sign(col, row)
 ))

 def isDivisibleBy(n: T): Boolean =
   self flatMap (row => row) forall (_ isDivisibleBy n)

 lazy val inverse: Option[Matrix[T]] =
   if (determinant == 0 || !isDivisibleBy(determinant))
     None
   else
     Some(adjugate / determinant)

 lazy val numFormat = this(0,0).numFormat(self flatMap (x => x) elements)

 override def toString = {
   val numFormat = this(0,0).numFormat(self flatMap (x => x) elements)
   def formatNumber(n: T) = numFormat format n
   val top = rows match {
     case 1 => _row(0) map formatNumber mkString ("< ", " ", " >")
     case _ => _row(0) map formatNumber mkString ("/ ", " ", " \\") // Fix highlighter: "
   }
   val middle = rows match {
     case 1 | 2 => Nil
     case _ => self.toList.tail.init map (_ map formatNumber mkString("| "," "," |"))
   }
   val bottom = rows match {
     case 1 => Nil
     case _ => List(_row(rows - 1) map formatNumber mkString ("\\ ", " ", " /"))
   }
  
   top :: middle ::: bottom mkString "\n"
 }
}

object Matrix {
 import Matrix._
 implicit def toMatrix[T](m : Array[Array[T]])
                         (implicit toScalar: T => Scalar[T], intToT: Int => T) = Matrix(m)

 def apply[T](array: Array[Array[T]])
             (implicit toScalar: T => Scalar[T], intToT: Int => T): Matrix[T] =
   new Matrix(clone(array))
 def apply[T](rows: Int, cols: Int)
             (implicit toScalar: T => Scalar[T], intToT: Int => T): Matrix[T] =
   Matrix(rows, cols, 0)
 def apply[T](rows: Int, cols: Int, value: T)
             (implicit toScalar: T => Scalar[T], intToT: Int => T): Matrix[T] =
   new Matrix(createArrays(rows, cols, ((_,_) => value)))
 def apply[T](rows: Int, cols: Int, f: (Int,Int) => T)
             (implicit toScalar: T => Scalar[T], intToT: Int => T): Matrix[T] =
   new Matrix(createArrays(rows, cols, f))

 def unitMatrix[T](n: Int)(implicit toScalar: T => Scalar[T], intToT: Int => T) =
   Matrix[T](n, n, (row: Int,col: Int) => (if (row == col) intToT(1) else intToT(0)))

 protected def createArrays[T](rows: Int, cols: Int, f: (Int, Int) => T) =
   for((i: Int) <- (0 until rows).toArray)
     yield for((j: Int) <- (0 until cols).toArray)
       yield f(i,j)

 protected def clone[T](a: Array[Array[T]]) =
   createArrays(a.size, a(0).size, (row, col) => a(row)(col))
  
 sealed abstract class Dimension
 case object Row extends Dimension
 case object Column extends Dimension

 implicit def intToScalar(n: Int): Scalar[Int] = new IntScalar(n)
 implicit def doubleToScalar(n: Double): Scalar[Double] = new DoubleScalar(n)
}

class LinearEquations[T](val m: Matrix[T], val r: Matrix[T])
                       (implicit toScalar: T => Scalar[T], intToT: Int => T) {
 require(m.rows == r.rows && r.cols == 1)

 def maxColumnSize(matrix: Matrix[T], isAbs: Boolean): Int = (
   matrix.toArray
   flatMap (row => row)
   map (value => (if (isAbs) value.absolute else value).toString.length)
   reduceLeft (_ max _)
 )

 lazy val maxColsSize = m.cols.toString.length

 def numberSign(n: T) = " %s " format n.numberSign
 def formatConstant(n: T) = r.numFormat format n
 def formatCoefficient(n: T) = m.numFormat format n.absolute
 def formatUnknown(index: Int) = "x("+("%0"+maxColsSize+"d" format index)+")"

 // On Scala 2.8, replace drop(1) with tail and first with head below
 def formatLine(coefficients: Array[T],
                constant: T,
                printUnknown: Int => String) =
   coefficients
   .zipWithIndex
   .drop(1)
   .foldLeft(formatCoefficient(coefficients.first)+printUnknown(0))(
     (x,y) => x+numberSign(y._1)+formatCoefficient(y._1)+printUnknown(y._2)
   )+" = "+formatConstant(constant)

 def makeString(printUnknown: Int => String) = (
   for(row <- 0 until m.rows)
   yield formatLine(m.row(row), r(row,0), printUnknown)
 ).mkString("\n")
  
 override def toString = makeString(formatUnknown)

 def getUnknowns(u: Matrix[T]): Int => String =
   (index: Int) => " * "+(u.numFormat format u(index,0))

 lazy val solutionInverse: Option[Matrix[T]] =
   if (m.inverse == None)
     None
   else
     Some(m.inverse.get * r)

 def solveInverse =
   if (solutionInverse == None)
     "There is no unique solution"
   else
     makeString(getUnknowns(solutionInverse.get))

 lazy val solutionCramer: Option[Matrix[T]] = {
   val vector = r.toArray.flatMap(x => x)
   if (m.determinant == 0)
     None
   else
     Some(Matrix(
       for((col: Int) <- (0 until m.cols).toArray)
       yield for(row <- Array(0)) // Array[T](...) doesn't work, as it requires T <: AnyRef
         yield m.replaceCol(col, vector).determinant / m.determinant
     ))
 }
    
 def solveCramer =
   if (solutionCramer == None)
     "There is no unique solution"
   else
     makeString(getUnknowns(solutionCramer.get))
}

Matrices 5b

2009-07-01T20:53:00.003-03:00

To finish my last post I wrote a quick&dirty class to show MatrixInt in use. Alas, it was so dirty I couldn't stand the shame, so I rewrote it. Have fun. :-)


class LinearEquations(val m: MatrixInt, val r: MatrixInt) {
  require(m.rows == r.rows && r.cols == 1)
  
  def maxColumnSize(matrix: MatrixInt, isAbs: Boolean): Int = (
    matrix.toArray 
    flatMap (row => row) 
    map (value => (if (isAbs) value.abs else value).toString.length)
    reduceLeft (_ max _)
  )
  
  lazy val maxCoefficientsColumnSize =  maxColumnSize(m, true)
  lazy val maxConstantsColumnSize = maxColumnSize(r, false)
  lazy val maxColsSize = m.cols.toString.length
  
  def numberSign(n: Int) = if (n < 0) " - " else " + "
  def formatNumber(n: Int, size: Int) = "%"+size+"d" format n
  def formatConstant(n: Int) = formatNumber(n, maxConstantsColumnSize)
  def formatCoefficient(n: Int) = formatNumber(n.abs, maxCoefficientsColumnSize)
  def formatUnknown(index: Int) = "x("+("%0"+maxColsSize+"d" format index)+")"
  
  // On Scala 2.8, replace drop(1) with tail and first with head below
  def formatLine(coefficients: Array[Int], 
                 constant: Int, 
                 printUnknown: Int => String) =
    coefficients
    .zipWithIndex
    .drop(1)
    .foldLeft(formatCoefficient(coefficients.first)+printUnknown(0))(
      (x,y) => x+numberSign(y._1)+formatCoefficient(y._1)+printUnknown(y._2)
    )+" = "+formatConstant(constant)

  def makeString(printUnknown: Int => String) = (
    for(row <- 0 until m.rows)
    yield formatLine(m.row(row), r(row,0), printUnknown)
  ).mkString("\n")
    
  override def toString = makeString(formatUnknown)
  
  def getUnknowns(u: MatrixInt): Int => String =
    (index: Int) => " * "+u(index,0)

  lazy val solutionInverse: Option[MatrixInt] =
    if (m.inverse == None)
      None
    else
      Some(m.inverse.get * r) 

  def solveInverse =
    if (solutionInverse == None)
      "There is no unique solution"
    else
      makeString(getUnknowns(solutionInverse.get)) 

  lazy val solutionCramer: Option[MatrixInt] = {
    val vector = r.toArray.flatMap(x => x)
    if (m.determinant == 0)
      None
    else
      Some(MatrixInt(
        for((col: Int) <- (0 until m.cols).toArray)
        yield Array(
            m.replaceCol(col, vector).determinant / m.determinant 
          )
      ))
  }
      
  def solveCramer =
    if (solutionCramer == None)
      "There is no unique solution"
    else
      makeString(getUnknowns(solutionCramer.get))
}

Matrices 5

2009-06-30T21:39:00.002-03:00

Our Matix class is now almost complete. There are few methods I intend to add to it, and one I intend to change. Most of this is pretty straight-forward, though, so I’ll be quick about it.

First, matrix transposition:

def transpose = new MatrixInt(createArrays(cols, rows, (row,col) => this(col,row)))

Pretty trivial. Next, determinant. To compute the determinant of a matrix, though, I need to compute some co-factors of it. The co-factor method is the only one I’m unhappy about. My original implementation was something like this:


    for((i: Int) <- (0 until rows).toArray; if i != row)
      yield for((j: Int) <- (0 until cols).toArray; if j != col)
        yield f(i,j)

That’s a pretty good implemention, but then I went and factored that code out of it and into createArrays. Unfortunately, there is no “if” in createArrays, and I’m not willing to add them for the sake one one method, as this can have some performance impact, and createArrays is used everywhere.

I could create a “createArraysCond” or something. That would do, but there is only one method that would make use of it. I’m wary of premature refactoring. :-)

So I ended with the method below. Also, the determinant:


  def cofactor(row: Int, col: Int) = new MatrixInt(createArrays(rows-1, cols-1, (i,j) =>
    this(i + (if (i < row) 0 else 1), j + (if (j < col) 0 else 1))))

  protected def sign(row: Int, col: Int) = if ((col + row) % 2 == 0) 1 else -1
  
  lazy val determinant: Int =
    if (rows != cols)
      throw new UnsupportedOperationException
    else rows match {
      case 1 => this(0,0)
      case 2 => this(0,0)*this(1,1) - this(1,0)*this(0,1)
      case n => (
        _row(0).zipWithIndex
        map Function.tupled((value, col) => value * cofactor(0, col).determinant * sign(0, col))
        reduceLeft (_+_)
        )
      }

I factored out “sign” because it is used in another method, and makes the code much clearer. Since our matrix is immutable, I made determinant “lazy val”. It’s a val because I need compute it only once – it’s value won’t change. It’s lazy because, that way, it won’t get computed until someone actually uses it. Otherwise, all matrices would have their determinant computed at creation time. This way, if you never need the determinant of a matrix, it won’t ever get computed.

The last methods I want to create for Matrix are “adjugate”, which will compute the adjugate, or adjoint, matrix, and “inverse”, which will compute the inverse of a Matrix. Since we are dealing with integers, computing the inverse will be a bit more difficult than if we were using doubles. Anyway, let’s do it. First, let’s define a “/” operator between matrix and integer. We’ll also define a “%” operator, which is pretty useful when dividing integers.


  def /(n: Int): MatrixInt = 
    new MatrixInt(createArrays(rows, cols, (row, col) => this(row,col) / n))

  def %(n: Int): MatrixInt = 
    new MatrixInt(createArrays(rows, cols, (row, col) => this(row,col) % n))

Next, I’ll do the adjugate:


  def minor(row: Int, col: Int) = cofactor(row, col).determinant
  
  lazy val adjugate: MatrixInt = new MatrixInt(createArrays(cols, rows, (row, col) =>
    minor(col, row) * sign(col, row)
  ))

This is a bit confusing because I’m inverting at the same time I’m computing the minors. This saves a transposition step, though.

Finally, I’ll compute the inverse matrix, after asserting the matrix does have an integer inverse:


  def isDivisibleBy(n: Int): Boolean =
    (this % n).self flatMap (row => row) forall (_ == 0)
  
  lazy val inverse: Option[MatrixInt] =
    if (determinant == 0 || !isDivisibleBy(determinant))
      None
    else
      Some(adjugate / determinant)

We finally have something new to look at. In the method isDivisibleBy, we first use the method “flapMap” to unnest the arrays, producing an Array[Int] containing all values of the matrix. Then we use “forall” in that. The method “forall” returns true if, and only if, the function passed to it (“_ == 0”) is true for all elements of the collection on which “forall” was invoked.

Or, in other words, “forall” will check that (this % n) results in a matrix of zeros.

The other interesting thing here is the use of Option. If you haven’t seen Option before, you probably haven’t seen much Scala code before. Option is Scala’s way of saying “this is not available”. An Option is a class, with a subclass called “Some”, and a singleton object called “None”. So where, in other languages, you might see a “null” value, in Scala the library will usually return a None instead.

On the other hand, instead of returning the value you want, it returns Some(value). This way, you need to test to see if the value you want is actually available, and then get it. There are many ways of doing that, and it pays to look up the API for Option.

The very last thing I’ll do with MatrixInt is change the exponentiation to be able to receive negative values, and we’ll see here one way of getting the value for an Option:


  def **(n: Int): MatrixInt =
    if (rows != cols)
      throw new UnsupportedOperationException
    else n match {
      case 0 => unitMatrixInt(rows)
      case 1 => this
      case 2 => this * this
      case negative if negative < 0 => 
        (this ** negative.abs).inverse getOrElse (throw new UnsupportedOperationException) 
      case odd if odd % 2 == 1 => this ** (odd - 1) * this
      case even => this ** (even / 2) ** 2
    }

We’ll finish this installment with a couple of methods to solve systems of linear equations. It is tempting to create the methods inside MatrixInt itself, but solving linear equations is something you can do using matrices, not a matrix operation in itself.

I’m not sure what a good abstraction would be. We might just create the functions inside an object, and import them. Instead, I’ll create a small class to do that. First, let’s get a toString method. This method is quick and dirty, and could use some improvements. In particular, we could align the columns, like MatrixInt does, and we could treat negative numbers to avoid showing things like “+ -5”. That, I’ll leave as an exercise! :-)


class LinearEquations(val m: MatrixInt, val r: MatrixInt) {
  require(m.rows == r.rows && r.cols == 1)
  
  override def toString =
    (for (rowNumber <- 0 until m.rows;
          row = m.row(rowNumber).zipWithIndex)
     yield (row 
            map Function.tupled(_+"x("+_+")") 
            mkString (""," + "," = ")) + r(rowNumber,0))
    .mkString("\n")
}

To this class, we’ll add two solvers. First, through the inverted matrix, which should be pretty easy. We’ll also add a method which prints the equation with the unknowns replaced with the solution, so we can easily verify it by eye:


  lazy val solutionInverse: Option[MatrixInt] =
    if (m.inverse == None)
      None
    else
      Some(m.inverse.get * r) 

  def solveInverse =
    if (solutionInverse == None)
      "There is no unique solution"
    else
      (for (rowNumber <- 0 until m.rows;
            row = m.row(rowNumber).zipWithIndex)
       yield (row 
              map Function.tupled((value, col) => value+"*"+solutionInverse.get(col,0)) 
              mkString (""," + "," = ")) + r(rowNumber,0))
      .mkString("\n")

We can already see the potential for refactoring. Now, the Cramer’s Rule. This is more difficult, because we need to compute each element of the solution. Though a bit more complex, it isn’t terribly so:


  lazy val solutionCramer: Option[MatrixInt] = {
    val vector = r.toArray.flatMap(x => x)
    if (m.determinant == 0)
      None
    else
      Some(MatrixInt(
        for((col: Int) <- (0 until m.cols).toArray)
        yield Array(
            m.replaceCol(col, vector).determinant / m.determinant 
          )
      ))
  }
      
  def solveCramer =
    if (solutionCramer == None)
      "There is no unique solution"
    else
      (for (rowNumber <- 0 until m.rows;
            row = m.row(rowNumber).zipWithIndex)
       yield (row 
              map Function.tupled((value, col) => value+"*"+solutionCramer.get(col,0)) 
              mkString (""," + "," = ")) + r(rowNumber,0))
      .mkString("\n")

More refactoring potential. We’ll finish this installment with an example of LinearEquations in action, followed by the complete source code for what we have done so far.


scala> m
res5: Array[Array[Int]] = Array(Array(5, -4), Array(6, -5))

scala> r
res6: Array[Array[Int]] = Array(Array(2), Array(1))

scala> new LinearEquations(m, r)
res2: LinearEquations =
5x(0) + -4x(1) = 2
6x(0) + -5x(1) = 1

scala> res2.solveInverse
res3: java.lang.String =
5*6 + -4*7 = 2
6*6 + -5*7 = 1

scala> res2.solveCramer
res4: java.lang.String =
5*6 + -4*7 = 2
6*6 + -5*7 = 1

And now, the source code:


package com.blogspot.dcsobral.matrix

class MatrixInt private (private val self: Array[Array[Int]]) {
  import MatrixInt._

  val rows = self.size
  val cols = self(0).size
  
  private def _row(n: Int): Array[Int] = self(n)
  private def _col(n: Int): Array[Int] = self map (_(n))
  
  def row(n: Int): Array[Int] = _row(n) map (x => x)
  def col(n: Int): Array[Int] = _col(n)

  def apply(i: Int, j: Int): Int =
    if (i >= rows || j >= cols || i < 0 || j < 0)
      throw new IndexOutOfBoundsException
    else
      self(i)(j)

  def update(row: Int, col: Int, newValue: Int): MatrixInt = 
    new MatrixInt(createArrays(rows, cols, (i,j) =>
      if (row == i && col == j) newValue else this(i,j)))

  def update(what: Dimension, where: Int, newValue: Array[Int]): MatrixInt =
    what match {
      case Row => replaceRow(where, newValue)
      case Column => replaceCol(where, newValue)
    }
      
  def replaceCol(col: Int, newValue: Array[Int]): MatrixInt =
    new MatrixInt(createArrays(rows, cols, (i,j) =>
      if (col == j) newValue(i) else this(i,j)))

  def replaceRow(row: Int, newValue: Array[Int]): MatrixInt =
    new MatrixInt(createArrays(rows, cols, (i,j) =>
      if (row == i) newValue(j) else this(i,j)))

  override def equals(other: Any): Boolean = other match {
    case that: MatrixInt => 
      that.canEqual(this) && self.deepEquals(that.self)
    case _ => false
  }
  
  def canEqual(other: Any): Boolean = other.isInstanceOf[MatrixInt]
    
  def *(n: Int): MatrixInt = 
    new MatrixInt(createArrays(rows, cols, (row, col) => this(row,col) * n))

  def /(n: Int): MatrixInt = 
    new MatrixInt(createArrays(rows, cols, (row, col) => this(row,col) / n))

  def %(n: Int): MatrixInt = 
    new MatrixInt(createArrays(rows, cols, (row, col) => this(row,col) % n))

  def +(other: MatrixInt): MatrixInt =
    if (rows != other.rows || cols != other.cols)
      throw new IllegalArgumentException
    else
      new MatrixInt(createArrays(rows, cols, (row, col) => this(row,col) + other(row,col)))

  def -(other: MatrixInt): MatrixInt =
    if (rows != other.rows || cols != other.cols)
      throw new IllegalArgumentException
    else
      new MatrixInt(createArrays(rows, cols, (row, col) => this(row,col) - other(row, col)))

  def *(other: MatrixInt): MatrixInt =
    if (cols != other.rows)
      throw new IllegalArgumentException
    else 
      new MatrixInt(createArrays(rows, other.cols, (row, col) =>
        this._row(row) zip other._col(col) map Function.tupled(_*_) reduceLeft (_+_)
      ))

  def **(n: Int): MatrixInt =
    if (rows != cols)
      throw new UnsupportedOperationException
    else n match {
      case 0 => unitMatrixInt(rows)
      case 1 => this
      case 2 => this * this
      case negative if negative < 0 => 
        (this ** negative.abs).inverse getOrElse (throw new UnsupportedOperationException) 
      case odd if odd % 2 == 1 => this ** (odd - 1) * this
      case even => this ** (even / 2) ** 2
    }

  def toArray = MatrixInt.clone(self)
  
  def transpose = new MatrixInt(createArrays(cols, rows, (row,col) => this(col,row)))

  def cofactor(row: Int, col: Int) = new MatrixInt(createArrays(rows-1, cols-1, (i,j) =>
    this(i + (if (i < row) 0 else 1), j + (if (j < col) 0 else 1))))

  protected def sign(row: Int, col: Int) = if ((col + row) % 2 == 0) 1 else -1
  
  lazy val determinant: Int =
    if (rows != cols)
      throw new UnsupportedOperationException
    else rows match {
      case 1 => this(0,0)
      case 2 => this(0,0)*this(1,1) - this(1,0)*this(0,1)
      case n => (
        _row(0).zipWithIndex
        map Function.tupled((value, col) => value * cofactor(0, col).determinant * sign(0, col))
        reduceLeft (_+_)
        )
      }

  def minor(row: Int, col: Int) = cofactor(row, col).determinant
  
  lazy val adjugate: MatrixInt = new MatrixInt(createArrays(cols, rows, (row, col) =>
    minor(col, row) * sign(col, row)
  ))

  def isDivisibleBy(n: Int): Boolean =
    (this % n).self flatMap (row => row) forall (_ == 0)
  
  lazy val inverse: Option[MatrixInt] =
    if (determinant == 0 || !isDivisibleBy(determinant))
      None
    else
      Some(adjugate / determinant)

  override def toString = {
    val maxNumSize = self.projection flatMap (_ map (_.toString.size)) reduceLeft (_ max _)
    val numFormat = "%"+maxNumSize+"d"
    def formatNumber(n: Int) = numFormat format n
    val top = rows match {
      case 1 => _row(0) map formatNumber mkString ("< ", " ", " >")
      case _ => _row(0) map formatNumber mkString ("/ ", " ", " \\") // fix highlighter: "
    }
    val middle = rows match {
      case 1 | 2 => Nil
      case _ => self.toList.tail.init map (_ map formatNumber mkString("| "," "," |"))
    }
    val bottom = rows match {
      case 1 => Nil
      case _ => List(_row(rows - 1) map formatNumber mkString ("\\ ", " ", " /"))
    }
    
    top :: middle ::: bottom mkString "\n"
  }
}

object MatrixInt {
  import MatrixInt._
  implicit def toMatrixInt(m : Array[Array[Int]]) = MatrixInt(m)

  def apply(array: Array[Array[Int]]): MatrixInt = new MatrixInt(clone(array))
  def apply(rows: Int, cols: Int): MatrixInt = MatrixInt(rows, cols, 0)
  def apply(rows: Int, cols: Int, value: Int): MatrixInt = 
    new MatrixInt(createArrays(rows, cols, ((_,_) => value))) 
  def apply(rows: Int, cols: Int, f: (Int,Int) => Int): MatrixInt = 
    new MatrixInt(createArrays(rows, cols, f))
  
  def unitMatrixInt(n: Int) = MatrixInt(n, n, (row,col) => (if (row == col) 1 else 0)) 

  protected def createArrays(rows: Int, cols: Int, f: (Int, Int) => Int) =
    for((i: Int) <- (0 until rows).toArray)
      yield for((j: Int) <- (0 until cols).toArray)
        yield f(i,j)

  protected def clone(a: Array[Array[Int]]) =
    createArrays(a.size, a(0).size, (row, col) => a(row)(col))
    
  sealed abstract class Dimension
  case object Row extends Dimension
  case object Column extends Dimension
}

class LinearEquations(val m: MatrixInt, val r: MatrixInt) {
  require(m.rows == r.rows && r.cols == 1)
  
  override def toString =
    (for (rowNumber <- 0 until m.rows;
          row = m.row(rowNumber).zipWithIndex)
     yield (row 
            map Function.tupled(_+"x("+_+")") 
            mkString (""," + "," = ")) + r(rowNumber,0))
    .mkString("\n")

  lazy val solutionInverse: Option[MatrixInt] =
    if (m.inverse == None)
      None
    else
      Some(m.inverse.get * r) 

  def solveInverse =
    if (solutionInverse == None)
      "There is no unique solution"
    else
      (for (rowNumber <- 0 until m.rows;
            row = m.row(rowNumber).zipWithIndex)
       yield (row 
              map Function.tupled((value, col) => value+"*"+solutionInverse.get(col,0)) 
              mkString (""," + "," = ")) + r(rowNumber,0))
      .mkString("\n")

  lazy val solutionCramer: Option[MatrixInt] = {
    val vector = r.toArray.flatMap(x => x)
    if (m.determinant == 0)
      None
    else
      Some(MatrixInt(
        for((col: Int) <- (0 until m.cols).toArray)
        yield Array(
            m.replaceCol(col, vector).determinant / m.determinant 
          )
      ))
  }
      
  def solveCramer =
    if (solutionCramer == None)
      "There is no unique solution"
    else
      (for (rowNumber <- 0 until m.rows;
            row = m.row(rowNumber).zipWithIndex)
       yield (row 
              map Function.tupled((value, col) => value+"*"+solutionCramer.get(col,0)) 
              mkString (""," + "," = ")) + r(rowNumber,0))
      .mkString("\n")
}

Matrices 4

2009-06-28T23:43:00.003-03:00

We have a reasonable Matrix class at this point, but it still has some deficiencies. There are a few common matrix operations we can add to it, and there are some problems related to the usability of the class. Let’s see them.

Equality

If you try “unitMatrixInt(2) == unitMatrixInt(2)”, you’ll get false as result. This happens because we did not provide an “equals” method, and the default “equals” method compares object references. Or, in other words, it tests if the objects are the same, not if the objects are equal. If that’s still unclear, see the following example:


scala> unitMatrixInt(2) == unitMatrixInt(2)
res8: Boolean = false

scala> val a = unitMatrixInt(2)
a: teste.MatrixInt =
/ 1 0 \
\ 0 1 /

scala> val b = unitMatrixInt(2)
b: teste.MatrixInt =
/ 1 0 \
\ 0 1 /

scala> val c = a
c: teste.MatrixInt =
/ 1 0 \
\ 0 1 /

scala> a == a
res9: Boolean = true

scala> a == b
res10: Boolean = false

scala> a == c
res11: Boolean = true

Writing an equals method can be tricky, but I’m not going to discuss here why such a method must be written this or that way, as there are good references on the web. I usually recommend this one.

I will talk about the syntactical aspect of making such a method. First, though the examples show the method “==”, I keep talking about “equals”. That’s because “==”, as well as “!=”, in Scala is implemented in terms of the “equals” method. So if you want to change them, you implement “equals”.

Now, it’s not enough just to call it “equals”. It has to have the correct signature, which is to receive a single parameter of type Any, and return a Boolean. The method below will be good enough, with the addition of a canEqual method, and a small change in our class declaration:


class MatrixInt private (private val self: Array[Array[Int]]) {
...
  override def equals(other: Any): Boolean = other match {
    case that: MatrixInt =>
      that.canEqual(this) && self.deepEquals(that.self)
    case _ => false
  }
 
  def canEqual(other: Any): Boolean = other.isInstanceOf[MatrixInt]

We changed the constructor so that self got declared as a “private val”, otherwise it won’t be visible even to other objects of the same class. We could also get a copy of a MatrixInt’s array representation, and compare against that, but that can make equals quite slow. To get such a copy, though, we would use the “toArray” method, which I thought I had presented in the first installment of these posts, but I now find I didn’t. Let’s correct that oversight:


  def toArray = MatrixInt.clone(self)

We produce a copy of the array, so that changes to it won’t affect this object. Anyway, now the test works as expected:


scala> val a = unitMatrixInt(2)
a: teste2.MatrixInt =
/ 1 0 \
\ 0 1 /

scala> val b = unitMatrixInt(2)
b: teste2.MatrixInt =
/ 1 0 \
\ 0 1 /

scala> val c = a
c: teste2.MatrixInt =
/ 1 0 \
\ 0 1 /

scala> a == a
res12: Boolean = true

scala> a == b
res13: Boolean = true

scala> a == c
res14: Boolean = true

Updating

We also want to check to see it returns false for different matrices. To do that, though, we would like to produce a different matrix easily. Unfortunately, we have no way to do that. Well, we can generate unit matrices of different sizes, but if we just wanted to change a small value in one we have, we can do that.

Since our class is immutable, we do not expect it to actually change to something else, but when we do “1+1”, we do not change “1”, we just produce a new value. We can do the same thing, and enable individual cell changes in our matrix, like this:


  def update(row: Int, col: Int, newValue: Int): MatrixInt =
    new MatrixInt(createArrays(rows, cols, (i,j) =>
      if (row == i && col == j) newValue else this(i,j)))

Here are some tests, then:


scala> val a = unitMatrixInt(2)
a: teste3.MatrixInt =
/ 1 0 \
\ 0 1 /

scala> a == unitMatrixInt(3)
res20: Boolean = false

scala> a == unitMatrixInt(2)
res21: Boolean = true

scala> a == (a + a)
res22: Boolean = false

scala> a == a*2
res23: Boolean = false

scala> a == a * a // True! 1 == 1 * 1
res24: Boolean = true

scala> val b = a(1,0) = 1
b: teste3.MatrixInt =
/ 1 0 \
\ 1 1 /

scala> a
res25: teste3.MatrixInt =
/ 1 0 \
\ 0 1 /

scala> a == b
res26: Boolean = false

So, where’s “update”? It is actually used when declaring “b”. When you write “id(…) = value” in Scala, the compiler translates that to “id.update(…,value)”. So we could have also written this:


scala> val b = a.update(1,0,1)
b: teste3.MatrixInt =
/ 1 0 \
\ 1 1 /

Let’s also make it easy to change a whole column or a whole row. We can already do “a.row(0)” or “c.col(1)”, so doing “a.row(0) = …” would be nice. Scala has something similar, in that any method called “field_=” will be called if you write “id.field = …”. Unfortunately, if we try that here it won’t work, because “id.field” is already the name of a method which takes a parameter (the row or column). If it did not take any parameters, it would work. As it is, we’ll just have to make do with something else:


  def replaceCol(col: Int, newValue: Array[Int]): MatrixInt =
    new MatrixInt(createArrays(rows, cols, (i,j) =>
      if (col == j) newValue(i) else this(i,j)))
     
  def replaceRow(row: Int, newValue: Array[Int]): MatrixInt =
    new MatrixInt(createArrays(rows, cols, (i,j) =>
      if (row == i) newValue(j) else this(i,j)))

And we can use it like this:


scala> val a = unitMatrixInt(3)
a: teste6.MatrixInt =
/ 1 0 0 \
| 0 1 0 |
\ 0 0 1 /

scala> a.replaceCol(0, a.col(2))
res39: teste6.MatrixInt =
/ 0 0 0 \
| 0 1 0 |
\ 1 0 1 /

There is one alternative, though, which I show below. I’m using the update method, and a symbol to identify what is being updated:


  def update(what: Symbol, where: Int, newValue: Array[Int]): MatrixInt =
    what match {
      case 'row => replaceRow(where, newValue)
      case 'col | 'column => replaceCol(where, newValue)
      case _ => throw new IllegalArgumentException
    }

scala> val a = unitMatrixInt(3)
a: teste7.MatrixInt =
/ 1 0 0 \
| 0 1 0 |
\ 0 0 1 /

scala> a('row, 1) = a.row(0)
res41: teste7.MatrixInt =
/ 1 0 0 \
| 1 0 0 |
\ 0 0 1 /

scala> a('column, 2) = a.row(0)
res42: teste7.MatrixInt =
/ 1 0 1 \
| 0 1 0 |
\ 0 0 0 /

Symbols are similar to String. The technical differences aren’t really much important – it’s their intent usage that differs. While strings are made to be shown to a user or received from them, a symbol is a piece of information exchanged between different parts of a program. They are very popular in some languages, but not so much on Scala.

One reason for their lack of popularity is that you don’t get any compile-time checks using them. If I misspelled “colunm” instead of “column”, the program would compile, and I’d get an exception at run-time – if I was lucky enough to catch it before the user.

Since we are using a statically typed language, we would like to catch such errors at compile-time. We can do that with Enumerations. Using a Scala enumeration is a bit more complex than other languages, as it’s not built in the language, but a library like anything else. It will provide just the checks we want, though.

First, we need to declare an object to be our enumeration. We’ll do this in the MatrixInt object-companion. We’ll also declare a type inside the object, to be used in our method declaration. It goes like this:


  object Dimension extends Enumeration {
    type Dimension = Value
    val Row, Column = Value
  }

“Value”, here, is both a subclass of Enumeration and a method which will return a new instance of type Value each time it is called. These instances will always be different between them. Note that when you declare “val Row, Column = Value”, Scala converts this into “val Row = Value; val Column = Value”, so “Value” gets invoked twice. If “Value” was called only once, then Row would be equal to Column, which is not something we want.

We might like to import the contents of the Dimension object inside the class too, so that we can write “what: Dimension” instead of “what: Dimension.Dimension” (or even “what: MatrixInt.Dimension.Dimension”, if we hadn’t imported object MatrixInt’s contents already). Simple line:


  import MatrixInt.Dimension._

Now we can rewrite our method:


  def update(what: Dimension, where: Int, newValue: Array[Int]): MatrixInt =
    what match {
      case Row => replaceRow(where, newValue)
      case Column => replaceCol(where, newValue)
    }

It’s important that Row and Column were declared capitalized – the first letter is uppercase. If we used “row” and “column”, then the match would simply assign “what” to “row”, like it did to “even” and “odd” in “**”, and execute the first statement. Since we used capitalized identifiers, the case statement compares “what” to the value of Row, as if it was a literal, and assigns nothing.

Note also that we dropped the default case. One has to be careful, though, because the compiler won’t warn against missing case statements. Here are some usage examples:


scala> a(Row, 2) = a.row(1)
<console>:13: error: not found: value Row
       a(Row, 2) = a.row(1)
         ^

scala> a(Dimension.Row, 2) = a.row(1)
res1: teste.MatrixInt =
/ 1 0 0 \
| 0 1 0 |
\ 0 1 0 /

scala> import Dimension._
import Dimension._

scala> a(Row, 2) = a.row(1)
res2: teste.MatrixInt =
/ 1 0 0 \
| 0 1 0 |
\ 0 1 0 /

Can we do something about not getting warnings about missing case statements? As a matter of fact, yes, we can. Let’s rewrite once again our method. This time, we’ll use a case objects. Let’s show it first, and then discuss it. First, we replace the whole Dimension object by this:


  sealed abstract class Dimension
  case object Row extends Dimension
  case object Column extends Dimension

Since we don’t have any nested declaration, we can do away with the extra import line. As for the rest… the update method doesn’t actually need any changes! The type, Dimension, has been declared. Row and Column are singleton objects, capitalized so that they can be used inside case statements as if they were literals.

There are two new things here. The “sealed” keyword, and the “case” keyword. Anyone reading about Scala has probably seen case classes. A case class is a class mostly like any other, but with a few methods automatically created by the compiler. A case object is similar to case class, and used instead of them when a case class would not declare any parameter in its constructor.

The “sealed” keyword means any subclass of “Dimension” must be declared in the same file as it. This way, the compiler can know, without doubt, all subclasses of Dimension, and, thus, perform checks when they get used in match statements. Leave “case Column” out of “update”, and you’ll get this warning:


MatrixInt.scala:70: warning: match is not exhaustive!
missing combination         Column

    what match {
    ^
one warning found

The usage won’t differ much either, and, in fact, won’t require any import beyond the object-companion’s contents:


scala> val a = unitMatrixInt(3)
a: teste3.MatrixInt =
/ 1 0 0 \
| 0 1 0 |
\ 0 0 1 /

scala> a(Row,2) = a.row(0)
res15: teste3.MatrixInt =
/ 1 0 0 \
| 0 1 0 |
\ 1 0 0 /

You might wonder, then, why ever use an Enumeration instead of case objects. As a matter of fact, case objects do have advantages many times, such as here. The Enumeration class, though, has many Collection methods, such as elements (iterator on Scala 2.8), which returns an Iterator, map, flatMap, filter, etc.

We have seen three different ways of implementing our “update” method for rows and columns, each with different characteristics. The very thing that made symbols a bad choice for us – the inability to define what symbols are possible in advance – can be a necessary characteristic in other situations. This goes to the very heart of Scala’s philosophy: do not dictate a solution, but let the programmer find and use the optimal one for his needs.

In the next installment we’ll look into computing cofactors, determinants, inverse matrices and then use all that to solve linear equations. I’m afraid there won’t be almost anything new, but, on the positive side, it shouldn’t take long either, and we’ll end up with a reasonable complete Matrix class.

After that, we’ll look into branching Matrix into other types, and the trade-offs we must make.

A Mind is a Terrible Thing to Waste

2009-06-26T16:39:00.002-03:00

I have just seen a presentation about Agilists and Architects, which resonated with an old thought of mine: the waste of experience in the software development process.

Writing software – programming – is something that takes a huge amount of experience to get right. You have to know the language, of course. You have to know it well enough to avoid getting things wrong because of an unknown feature or characteristic of the language. You have to know the language libraries, frameworks, and development tools. This is the very basic.

You have to know patterns, and you have to know anti-patterns too. You need experience to realize that a pattern apply to a problem, or that some solution is inching toward an anti-pattern.

You have to know about security, about protocols, about distributed systems, about parallel systems, about algorithms – of so many types I can’t even list them here. You have to know about databases, persistence, XML, MVC, DSL, regex, grammars, state machines… we could go on and on. You have to know usability.

You have to know about programming paradigms. That’s easy, there’s only four or five of them. Or maybe more, depending on who’s definition you are using. And, of course, each paradigm has many variations preferred by one language or another – and who has to deal with a single language these days?

You have to know computers, and experience here will bring you understanding of performance issues. Experience will also let you identify bugs, or avoid them altogether.

Then, of course, you have to know CMMI, PMBoK, FPA or any of dozens standards and best practices and processes for software development, quality, testing, team working, etc.

Finally, of course, you have to know how to communicate with other people, understand the business needs, know the existing systems, the explicit and implicit rules, and, if possible, why it exists in the state it is, why certain decisions were taken, what were the conditions that might change and make it interesting – or even necessary – to take another path, or to avoid certain paths.

Each of those things you know or don’t have a direct impact on the quality of the code you write. Sure, you can write software with only a small glimpse of all this knowledge, but many times you would have written better, more efficient and more maintainable code if you only knew there was a word to what you were doing. Whole classes might have crumbled to a single library call. You might have avoided code which is intrinsically insecure, protocols which are unfixable. Hell, you might have avoided trying to solve problems known to be unsolvable.

While deep knowledge is clearly the domain of experts in a field, all those domains come together through the hands of the generalist, who has to know something exists before he can use it.

So there are architects, who are meant to have all that experience, and lay down the trail for those inexperienced to follow. Only, of course, it doesn’t work that way. The sheer level of detail required in developing software preclude architects from being able to know or influence but a thin, though important, layer of all there is.

It couldn’t be other way, in truth – if it were possible to write a precise specification of what the software should do, what should be its structure, how it should go about doing what it is supposed to do, well, if it were possible to write such a specification, then we could feed it to the computer and be done with it. In fact, we can write those specifications – they are called “source code”. Source code is not what a computer executes. It’s a specification detailing how to produce the instructions the computer will follow to provide the service required.

In short, or, rather, in conclusion, programming experience results in code with fewer bugs, that satisfy more completely the users needs, easier to adapt to new needs, and in a shorter time.

So why the hell does any company even contemplates hiring “junior” programmers? No, let me rephrase that. Why is the average experience of programmers working – coding – for corporations so low? There is an obvious – to me – inversion of value going on there. And looking at companies that make software to be sold as service or at retail – as opposed to producing software to someone else’s specs – I don’t see much disagreement.

I can see a few reasons why that might be true, of course. First, just because someone acquires experience doesn’t mean he or she learns new stuff. And the transition from mainframe to personal computing pretty much proved that can be detrimental – when people cling to what they know against the unknown, instead of avoiding what they know to be wrong, or taking the better one of known alternatives.

So, corporations “solve” the problem by making experienced people into architects and managers. Being a manager has a quality of its own, and having experience writing software does not really add anything to it. Being an architect takes you too far from where you can make most use of your experience.

Hopefully, if you are lucky enough to work somewhere software architects have meaningful influence on the software development process, you might get programmers to avoid huge mistakes. And if your corporation is really lucky, you’ll do so without critically impairing the software development process with decisions detached from the reality of the problems being faced.

I was happy, then, with the ideas presented by Rebecca Parsons and Martin Fowler. It pains me to see so much experience and knowledge wasted because of misguided – or misinformed – processes.

Matrices and Fibonacci 3

2009-06-25T18:57:00.008-03:00

Continuing our series on creating a Matrix class for Scala, now that we have the basics laid down, let’s go back to the Fibonacci problem. We need to do exponentiation of matrices. To do that, we first need to get multiplication going.

While I have no intention of explaining how to multiply matrices – the web is full of resources if you aren’t familiar with it – it’s important to restate the problem:

To find element of (row i, column j) of the matrix resulting from AxB, I need to multiply the nth element of row i of matrix A by the nth element of column j of matrix B, for all elements of said row and column, and then add the results. An initial, misguided, attempt might go like this:


(for(row <- 0 to rows
     col <- 0 to B.cols
    ) yield A(i,col)*B(row,j)) reduceLeft (_+_)

The problem here is that you are multiplying each element of the row by every element of the column. What we want to do is to “pair” the first element of the row with the first element of the column, the second element of the row with the second of the column, and so forth, and then multiply each pair. This pairing is called “zip” in Scala. You’ll find “zip” – and the occasional variation, such as zipWithIndex – on sequence-like collections, such as List and Array. The zipping thing goes like this:


_row(i) zip other._col(j)

That will create an Array of tuples of Int: Array[Tuple2[Int,Int]], or simply Array[(Int,Int)]. Tuples can be thought of as a small “package” of objects. It’s not a collection – you do not traverse it or iterate through it. Also, each component of it has its own type, as you can see. The only thing you can do with tuples, aside from passing it around, is accessing a tuple’s element. You do this with the methods “_1”, “_2”, “_3”, etc.

Next, we need to do _1*_2 for each element of that array. You can’t do "map (_._1 * _._2)", as this translates into "map ((x1, x2) => x1._1 * x2._2)", but map only passes a single argument: the tuple. You can do this, then: "map (t => t._1 * t._2)". You can, but I won’t… Instead, I’ll pass "(_*_)", an anonymous function that takes two parameters and return the result of their multiplication, to a factory of functions.

Factories, as anyone familiar with OOP might know, are methods which create new instances of objects. So, what that has to do with a function? Well, a function in Scala is an object that implements the method “apply”. You might wonder if MatrixInt isn’t a function, then, as it implements apply itself. In fact, it could be one, if we chose to extend MatrixInt with the trait Function2 (two arguments to apply).

At any rate, we’ll use a function factory to produce a new instance of a function, based on (_*_). This factory, called Function.tupled (method “tupled” on singleton object Function), takes a function which receives multiple parameters, and converts it into a function which receives a single tuple instead. After that, we can apply the reduceLeft. Our computation, then, will go like this:


this._row(i) zip other._col(j) map Function.tupled(_*_) reduceLeft (_+_)

The method, then, is thus defined:


  def *(other: MatrixInt): MatrixInt =
    if (cols != other.rows)
      throw new IllegalArgumentException
    else
      new MatrixInt(createArrays(rows, other.cols, (row, col) => {
        this._row(row) zip other._col(col) map Function.tupled(_*_) reduceLeft (_+_)
      }))

If we do away with the check to see if the matrices are compatible in size, and make allowance for the verbosity of the identifiers being used (like row and col instead of I and j), it comes down to a one-liner. Truly:


def *(o: MatrixInt) = new MatrixInt(createArrays(rows, o.cols, (i,j) => _row(i) zip o._col(j) map Function.tupled(_*_) reduceLeft (_+_)))

The only thing left to do is exponentiation. We could do it as a one-liner too:


def ^(n: Int) = (0 until n).foldLeft(unitMatrixInt(rows))((acc,_) => acc*this)

The method foldLeft is similar to reduce. But where reduce can be thought of as (((a+b)+c)+d)+e, foldLeft is more like this:


var acc = ?
acc = op(acc,a)
acc = op(acc,b)
acc = op(acc,c)
acc = op(acc,d)
acc = op(acc,e)

The most important difference between foldLeft and reduceLeft is that the result of foldLeft, and its accumulator, might be of a different type than the elements the operation is applied upon. With reduceLeft, once you applied acc = op(a,b), if acc where of a different type, then op(acc,c) would be a different method. It might work with some implicits or subtypes, but not for entirely different types.

Now, I’m not using the range for nothing, except counting the number of times I want to multiply the matrix. Acc is initialized with “unitMatrixInt(rows)”, which would be a method producing a “unit” matrix of the appropriate size. The “1” of matrices. Then I keep multiplying “this” against this accumulator.

I could create a list of copies of “this”, and then multiply them with reduceLeft too. It would go like this:


def **(n: Int) = List.fill(n)(this) reduceLeft (_*_)

Much simpler, but I wanted to mention foldLeft somehow. :-)

While simplicity has its merits, there is a simple optimization when doing exponentiation by taking advantage of common factors. I went for it in my final implementation:


  def **(n: Int): MatrixInt =
    if (rows != cols  n < 0 =""> unitMatrixInt(rows)
      case 1 => this
      case 2 => this * this
      case odd if odd % 2 == 1 => this ** (odd - 1) * this
      case even => this ** (even / 2) ** 2
    }

I'll make a note on the method name, here. I chose ** as this is one of the common names for such an operation on computer languages. Another, less common, name is ^. I prefer the later, but it has a very low precedence. In fact, this very method would be broken as written, because "(odd - 1) * this" would have precedence over "this ** (odd - 1)", which would completely invert the logic and cause a compilation error.

Now, aside from , ^, &, <>, = and !, :, +, -, * and / and % (ordered by precedence, by the way), all other special characters have a higher precedence. If I called it "@", for instance, then "a * b @ c" would behave as one would expect it too. Unfortunately, no one would expect "@" to be an exponentiation character. But if I were to make extensive use of this library in formulas and expressions, I might well go for something like that, to prevent unexpected errors due to precedence.

Anyway, we need to define unitMatrixInt too. We’ll do so in a companion object. This way, users of this package can create unix matrices if they want to. To create this method, we’ll need a more general factory method, though. We already have most of what we need in createArrays.

But before I get into that, I want to revise my class definition. Presently, this is what we have:


class MatrixInt(array: Array[Array[Int]]) {
  private val self = clone(array)
}

I receive a matrix, and then replicate it internally, so I can be sure it won’t be changed outside my class – and I take care of not changing it inside. But there is a downside to it: “array” continues to be part of my object (see footnote 1)! It becomes a private reference inside my object, and this has some unfortunate consequences. For one thing, since each instance of my class makes reference to the arrays used to build them, those arrays never get deallocated. Now think about all references to “new MatrixInt” inside the class. I use that for every operator. That means I keep TWO copies of a MatrixInt’s array in memory, even when the copy used for construction gets immediately discarded.

This presents a conundrum.On one hand, if the instances of my class are immutable, then I need the full array to begin with. On the other hand, if I receive an array from an external source, I need to copy it before using, as the original array might get changed by whoever passed it to me.

We solve this with the help of a private constructor and an object companion. A private constructor is, of course, a constructor that cannot be accessed from outside the class. The private constructor thing is easy:


class MatrixInt private (array: Array[Array[Int]]) {

Now, how to access it? We cannot define another constructor inside MatrixInt with the same signature – receiving an array of array of Int as parameter – because it would conflict with the first. What we do, then, is use an object companion.

Simply put, an object companion is a singleton object – declared with the “object” keyword – which has the same name as a class. That grants both the object and the class visibility of each other’s private definitions.

We’ll then define an “apply” method in that object companion. As you may remember, the “apply” method receives special treatment from the Scala compiler, which enables you to do away with the name – apply – and just pass the parameters to the instance of your object. Since we have to call our object companion “MatrixInt”, then MatrixInt(…) will be converted by Scala into MatrixInt.apply(…). It looks like the instantiation of a new object, only it lacks the “new” keyword.

Let’s define it, then. First, let’s remove the “val self” from the class, and just receive it in its private constructor. As that constructor will only be accessed through MatrixInt’s object companion, that will be safe.


class MatrixInt private (self: Array[Array[Int]]) {
  import MatrixInt._

The import statement makes it possible to access the methods of the object companion without preceding them with “MatrixInt.”. Being a companion object makes the private methods accessible, but does not bring them into scope automatically.

Now, for the object companion, let’s create it, the factory for MatrixInt, and a couple of helpful factories. We’ll also transfer the “clone” and “createArrays” methods to it, as this method does not make reference to a MatrixInt’s own data, so it doesn’t need to be part of each instance. The definition of toArray needs “MatrixInt.” prepended to “clone” to avoid an ambiguous reference, but nothing else should change.


object MatrixInt {
  import MatrixInt._
  implicit def toMatrixInt(m : Array[Array[Int]]) = MatrixInt(m)

  def apply(array: Array[Array[Int]]): MatrixInt = new MatrixInt(clone(array))
  def apply(rows: Int, cols: Int): MatrixInt = MatrixInt(rows, cols, 0)
  def apply(rows: Int, cols: Int, value: Int): MatrixInt =
    new MatrixInt(createArrays(rows, cols, ((_,_) => value)))
  def apply(rows: Int, cols: Int, f: (Int,Int) => Int): MatrixInt =
    new MatrixInt(createArrays(rows, cols, f))
 
  def unitMatrixInt(n: Int) = MatrixInt(n, n, (row,col) => (if (row == col) 1 else 0))

  protected def createArrays(rows: Int, cols: Int, f: (Int, Int) => Int) =
    for((i: Int) <- (0 until rows).toArray)       yield for((j: Int) <- (0 until cols).toArray)         yield f(i,j)    protected def clone(a: Array[Array[Int]]) =     createArrays(a.size, a(0).size, (row, col) => a(row)(col))
}

We can now create a MatrixInt by using MatrixInt(Array(Array(…))), but we didn’t – and won’t – change that in the class. The companion object factory produces a clone of the array, just as we wanted. But the arrays produced by MatrixInt’s methods don’t get exposed, so there is no risk in using them. So, by keep using the private constructor inside MatrixInt itself, we prevent unnecessary copies of the arrays produced by each of MatrixInt’s operators.

We’ll finish today with Fibonacci, but we’ll continue later on. I’ll add some methods for completeness to MatrixInt, and then look into MatrixDouble and solve some linear equations with it.

After that, we’ll briefly explore ways to make our Matrix class parametrizable, though I’m still in doubt about performance. Still, I’m reading the comments, and I plan to address them one way or another in these posts.

So, the Fibonacci!


def fibonacci(n: Int) = (MatrixInt(Array(Array(1,1),Array(1,0))) ** n)(1,0)

Footnote 1:

A reader has brought to my attention that, actually, "array" is not being preserved. I haven't found in Scala specification anything about this, so I'm putting it down to optimization. But because it is not explicitly documented, I advise against taking advantage of it.

Do note, please, that if you declare "array" to be protected, val or var, or if any method makes use of it, then it will be preserved in the object.

Matrices 2

2009-06-24T19:44:00.005-03:00

I’ll continue today with a little series for beginners. On my first post I forgot something important. One of the very first things I do with a class is create a toString method. This way, I get instant feedback on how my class is doing, as I paste it into the REPL, and try out the methods I defined.

So, let’s think of a toString method. Since all data in my class is stored in the private val “self”, we could simply delegate the task of producing a string:


override def toString = self.toString

That might do at first, but it would be unreasonable to expect something better formatted than that. First, let’s see if we can’t get the output in multiple lines, using mkString:


override def toString = self mkString “\n”

Unfortunately, the output of that looks like this:


res6: String =
[I@196a753
[I@1c36f46

This wouldn’t happen with a List, but an Array is implemented to be compatible with Java, and Java had Arrays have some intrinsic limitations, as they were present in the language from the very beginning, much before generics, and some design decisions about them proved to be unfortunate. Anyway, let’s fix that:


override def toString = self map (_ mkString “ “) mkString “\n”

Better, but we can improve on that still. For one thing, it would be much better if the columns were aligned. Now, to align the columns, we first must know how big a column can get. Or, in other words, we must know the size of the number with the biggest string representation in the matrix.

So, summing it up, we have to look through all of the matrix elements, get their sizes, and choose the biggest one. Getting a number’s size is easy: number.toString.size. Now, if we had a list, this would be easy, but we have an array of arrays. When we have nested collections and we want to unnest them, we use flatMap. For instance:


scala> Array(Array(15,0),Array(2,-30)) flatMap (x => x)
res19: Array[Int] = Array(15, 0, 2, -30)

The flatMap operation we used, (x => x), simply returns what it was given. If all you want is unnest the collections, this suffices. But, actually, we want the number sizes. Since “x” is an Array, not a number, we can’t do flatMap (x => x.toString.size). But we can replace the numbers with their sizes, and then unnest the arrays, like this:


scala> Array(Array(15,0),Array(2,-30)) flatMap (_ map (_.toString.size))
res20: Array[Int] = Array(2, 1, 1, 3)

Next, we want to get the biggest one. We have a collection of number sizes, and we want to reduce it to the single biggest one. We have two such methods in Scala: reduceLeft and reduceRight. Since “max” is commutative, both will produce the same result. But reduceLeft has a better performance, as it iterates over the collection in the order given. The final code should look like this, then:


val maxNumSize = self flatMap (_ map (_.toString.size)) reduceLeft (_ max _)

Pretty easy, eh? My first version had three lines, and was much more confusing to read. It helps stating what your problem is – you’ll often see you can do exactly that in Scala. So, we have a size, what do we do with it? Well, let’s just make sure all numbers are printed to that size. If we format them with “%2d”, for instance, every number will take at least two characters, with the left side being filled with a space as needed. To produce such formatted numbers, we’ll make use of RichString’s “format” method:


override def toString = {
 val maxNumSize = self.projection flatMap (_ map (_.toString.size)) reduceLeft (_ max _)
 val numFormat = "%"+maxNumSize+"d"
 self map (_ map (numFormat format _) mkString “ “) mkString “\n”
}

That’s it! I added a “projection” there to make it a bit more performatic, as it doesn’t produce intermediate arrays. On Scala 2.8, that method gets replaced with “view”, with “projection” remaining as deprecated. Well, that was so easy I want to do more. First, I want to produce little vertical bars on the sides, to make clear the matrix boundaries, in case we are printing them side by side. That just requires changing the inner mkString to mkString(“| “, “ “, “ |”). But I also want to bend the bars up and down, to indicate the top and bottom lines, as well as produce something special for one-line matrices.

For all of them, we are just making small changes in the inner mkString. We have one for the top line, one for the intermediate ones, and one for the bottom line. We could make a list of all these lines, and then use mkString on the list, but we have to be careful, because the “bottom” line and the “intermediate” lines might not exist, and the top line has two different formats depending on whether the matrix has more than one line or not. Taking that into account, here is a much larger, but, hopefully, nicer toString method:


 override def toString = {
   val maxNumSize = self.projection flatMap (_ map (_.toString.size)) reduceLeft (_ max _)
   val numFormat = "%"+maxNumSize+"d"
   def formatNumber(n: Int) = numFormat format n
   val top = rows match {
     case 1 => _row(0) map formatNumber mkString ("< ", " ", " >")
     case _ => _row(0) map formatNumber mkString ("/ ", " ", " \\")
   }
   val middle = rows match {
     case 1 | 2 => Nil
     case _ => self.toList.tail.init map (_ map formatNumber mkString("| "," "," |"))
   }
   val bottom = rows match {
     case 1 => Nil
     case _ => List(_row(rows - 1) map formatNumber mkString ("\\ ", " ", " /"))
   }
  
   top :: middle ::: bottom mkString "\n"
 }

In a parting note, someone suggested one technique to be able to parametrize the class. There are many, but they are slower than using "AnyVal" types directly. If I happen to be mistaken, please do post about it at length!

Matrices and Fibonacci 1

2009-06-23T20:00:00.006-03:00

When I was beginning to learn Scala, I decided one of my projects would be rewrite this stuff in Scala. The idea behind that is to compute Fibonacci Numbers using matrices. I won’t bother describing how it is done, as this is well covered on both of those links. Suffice to say that I need to computer the nth power of a 2x2 matrix of integers. This project was all but forgotten for a long time…

So it happened that just yesterday I was cleaning my to-do list, and I came upon that. I took a second look into it, and decided to take the plunge. Now, Raganwald uses an optimization which enables him to do the operations on vectors, but, by now, I actually thought the whole exercise was trivial and pointless.

I took a brief look into matrix libraries for Scala. I found the Scalala (as in Scala Linear Algebra) library, which does everything I need, very efficiently at that. My problem would be reduced to something like this (untested):


def fib(n) = n match {
  case 0 => throw new IllegalArgumentException
  case 1 => 1
  case _ =>
    val m = DenseMatrix(2,2)(1); m(1,1) = 0
    val mPowered = m :^ n
    mPowered(0,1)
}

Boring, wasn’t it? Yeah, I thought so too. Instead, I decided to write my own Matrix library. Pretty trivial stuff, but at least I’d take something out of it, I thought. So, I’ll talk about that: writing my Matrix library. If that will bore you, you might as well stop right here. I’ll show, though, some of the design decisions and constrains I faced. For someone new to Scala, it might be interesting read.

Well, then, where to start? With a class, of course. Ideally, I’d like to write something like this:


class Matrix[T]

This way, I could use matrices of Double for most use cases, of Ints or Longs for things like the Fibonacci problem, and BigDecimal for tough stuff. Unfortunately, we can’t do that. We need access to operators such as +, - and * over type T, and that means I need an upper bound for T defining these operators. Unfortunately, these types do not share an interface defining those elements. You see, they are not really “classes” as far as Java is concerned, and not being a proper class, they can’t share an abstract class or interface with these methods. Well, BigDecimal is a class, alright, but that’s it.

Because of this, I decided, instead, to define my class as MatrixInt. This was enough for Fibonacci, but later I created a MatrixDouble as well, just to finish implementing the most basic methods such a class would need.

There is a way around that. I can get away with a structural type, but that would be so slow as to defeat the whole purpose of a Matrix class. So I’ll skip it altogether.

The next design decision is how to store my data, and what constructor to use. Generally speaking, there are two strategies for storing a matrix: as a dense matrix or as a sparse matrix. A dense matrix is simply stored as an addressable, fixed-size, contiguously allocated buffer. Or, in other words, an array. A sparse matrix is used for matrices that are very large in their dimensions, but are mostly populated with zeros. Performance can go either way, depending on what kind of data and algorithms you are using those matrices for. For Fibonacci, dense is the way to go. Since it is also the easier way to go, I chose that way.

We also need to know how many dimensions the matrices may have. For simplicity sake, I chose bi-dimensional matrices, and that’s it. With all that in mind, my class thus began:


class MatrixInt(array: Array[Array[Int]]) {

I decided to take an array of proper dimensions as my constructor, instead of providing something special myself. With Scala 2.8, you can pass Array.ofDim(2,2) and be done with it. We’ll see something similar further down too.

Now, one important thing to consider is that an Array is a mutable object. I have decided to make my matrices immutable, so that I could use them just like I use Ints or Doubles. But, to ensure that is true, I can’t really on the array passed with the constructor, as it might change. So, first thing I do is copy it. Here:


  private def clone(a: Array[Array[Int]]) =
    for((i: Int) <- (0 until a.size).toArray)
      yield for((j: Int) <- (0 until a(0).size).toArray)
        yield a(i)(j)

  private val self = clone(array)

This clone array method will help in places other than the constructor. For instance, if the user wants the Array representation of the matrix, I have to clone my internal representation before passing it on. But there are more interesting things about it. Let’s consider it…

One thing to notice about it, is that instead of having a single for/yield statement, I have two, the second being fed to the first’s yield. It is built this way because I want to create an Array of Arrays. Each yield will result in one collection. Two collections, two yield statements.

Then we have ranges: (0 until a.size) and (0 until a(0).size). A statement like (0 until 5) will produce a range which, when iterated over, will yield 0, 1, 2, 3 and 4. It can do a few other things too, but let’s not be bothered by them. Note that if you want an “inclusive”, range, one which will include the upper limit (5, in the example), you use “to” instead of “until”. Or you create a new range from the existing one with “inclusive”.

Next, “.toArray”. Though a range will do as far as generating indices, I want yield to return an Array. If you want yield to return collection X, pass a collection X to the for statement. Therefore, “.toArray” to convert the range into an array.

The final thing to consider is the last yield statement. Yield a(i)(j). As I started writing my methods, I got very similar patterns, with only the last yield changing. So I started to consider how to reuse that code. The thing to consider, here, is that the intent of this double for/yield pattern is to create an array of arrays of the proper size, and populate it with a function of my choosing. Thinking about it that way, a refactoring might be done as follow:


  protected def createArrays(rows: Int, cols: Int, f: (Int, Int) => Int) =
    for((i: Int) <- (0 until rows).toArray)
      yield for((j: Int) <- (0 until cols).toArray)
        yield f(i,j)

  protected def clone(a: Array[Array[Int]]) =
    createArrays(a.size, a(0).size, (row, col) => a(row)(col))

Here I changed from private to protected, as I decided if I ever subclassed it, there would be no point in hiding these methods. I do not publish them, though, because they are helper methods, instead of methods acting upon the object itself.

Next, a.size and a(0).size were a bit cryptic, weren’t they? When we work on the matrices algorithms, it would be preferable to call them by what they are:


  val rows = array.size
  val cols = array(0).size

We would also like to be able to get a particular row or a particular column. It seems getting a particular row would be easy. Just return the subarray:


  def row(n : Int): Array[Int] = self(n)

There is a serious problem with that, though. I’m returning a mutable object from my own internal data! We could solve that with clone, but clone only worked for bi-dimensional arrays. Well, before we create new clone, let’s consider a simpler alternative:


  private def _row(n: Int): Array[Int] = self(n)
  def row(n: Int): Array[Int] = _row(n) map (x => x)

The private definition is here so we can avoid creating new arrays unnecessarily. Internally, we’ll make sure we never change the value of our arrays. The public method creates a new array by the magic of “map”. The method “map” is, in fact, used when you do a for/yield, along with flatMap when the for/yield has multiple iterators. So, in fact, the createArrays method is actually implemented as using map.

A map will take a collection and produce a new collection with a given mapping. In this case, our mapping is (x => x), or, in other words, given x, return x, producing a copy of that array. We define cols in a likewise fashion:


  private def _col(n: Int): Array[Int] = self map (_(n))
  def col(n: Int): Array[Int] = _col(n)

In this case, the private definition and the public definition are the same. Still, I decided to keep a private definition so that I could use _row and _col throughout my class. We’ll also define a method to access a particular element of our matrix:


  def apply(i: Int, j: Int): Int =
    if (i >= rows || j >= cols || i < 0 || j < 0)
      throw new IndexOutOfBoundsException
    else
      self(i)(j)

The method “apply” has a special meaning in Scala, as the compiler translates object(parms) into object.apply(parms). This means that I will be able to access a particular element of a matrix m with “m(i,j)”. Of course, because a matrix has bounds, I must test for them, and throw an appropriate exception if need be.

Note that I do not declare an @throws annotation, though I might if I wished to. Also, note that I’m returning the result of the if/else expression, and its type should be Int. But in the if statement, I’m throwing an exception, so what gives?

As it happens, throwing an exception has type Nothing, which is subtype to everything. I’m not sure if the compiler actually assigns a type to “throw”, as this is a keyword. But if I used Scala’s library “error” function instead, the question of the type would be important. For methods and functions which never return, such as error, declaring its type to be Nothing makes it possible to make use of them inside statements whose return type is important.

We’ll stop today with just three more definitions. Let’s multiply a matrix by an integer, producing a new matrix, as well as add and subtract two arrays. Here is how:


  def *(n: Int): MatrixInt = 
    new MatrixInt(createArrays(rows, cols, (row, col) => this(row,col) * n))

  def +(other: MatrixInt): MatrixInt =
    if (rows != other.rows || cols != other.cols)
      throw new IllegalArgumentException
    else
      new MatrixInt(createArrays(rows, cols, (row, col) => this(row,col) + other(row,col)))

  def -(other: MatrixInt): MatrixInt =
    if (rows != other.rows || cols != other.cols)
      throw new IllegalArgumentException
    else
      new MatrixInt(createArrays(rows, cols, (row, col) => this(row,col) - other(row, col)))

Catching Exceptions

2009-06-22T15:44:00.008-03:00

A fellow blogger was complaining about Google Code returning an exception instead of null, which made his code look ugly. Not so, says I! Scala (and monads, I suppose) come to rescue:


def exceptionToLeft[T](f: => T): Either[java.lang.Throwable, T] = try {
  Right(f)
} catch {
  case ex => Left(ex)
}


exceptionToLeft(obj.methodWhichMightThrow()) match {
  case Right(x) => // do stuff with x
  case Left(ex) => println("Oops, got exception " + ex.toString)
}

Enjoy!

Update:

Scala 2.8 has library help for this, at scala.util.control.Exception. It does require one to specify the exception or exceptions to be caught, which is a good thing, and it has many more usage modes. You can just ignore the exception for computations returning Unit, you can get the result as Some(T) and transform the exceptions in None, etc.

Equality & Scala 3

2009-06-18T00:08:00.003-03:00

This one is a quickie. I forgot -- again -- to mention that Scala does provide a way around having to define your own equals method. To be more specific, case classes come with reasonably defined equals methods.

Equality & Scala 2

2009-06-17T22:11:00.010-03:00

My efforts, yesterday, to come up with an Equatable trait that could ease a bit the knowledge and sheer drudgery of making a valid “equals” method met with unexpected difficulties. While tempted to replace the incorrect code with a correct one before the article got many hits, I decided that the problems I encountered and the mistakes I made taught a lesson by itself.

Anyway, I'd like first to make a few remarks that were missing from that post. One thing to notice here is that while this trait might be useful to some people, it is slower than a well thought-out equals definition. What I'm trying to do is see how much Scala let me make the job of creating valid equals methods both easier and safer.

It all comes down to the idea that, being equality in languages with subclassing so full of pitfalls, and the general solution to it being a well-defined pattern, those languages ought to be doing something about it at the language level. Or library level, if possible.

It does cross my mind that this problem might be much more efficiently and elegantly solved in languages which makes it possible to generate code at compile time, such as Lisp with its macros, and Ruby with access to the AST. This is one thing I miss in Scala, and while I understand the reasons for it and empathize with them, I do come up some roadblocks to a scalable language now and then.

That said, let’s analyze what happened. I tried to model my trait after the Hashable class. There are two things, though, that made my job harder than Hashable’s. First, I depended on super.equals, while hashCode doesn’t depend on its super. This becomes important as super.equals would make reference to definitions such as testSuperEquals or equateValues, and these definitions would be overridden in the subclass. Therefore, when Point3D.equals called Point.equals (its super.equals), the method Point.equals would make use of Point3D.equateValues and Point3D.testSuperEquals instead of Point.equateValues and Point.testSuperEquals.

This is difficult enough to get around, but it gets worse because, as opposed to hashCode, equals has to reference not one, but two objects. Calling a super of oneself is easy. Not so calling a super to a method on another object.

Another problem is the warning about type erasure. The case match never tests for type "This", so it is necessary to resort to reflection, to make sure we don't try to assign a superclass to a subclass. I didn't get any error on that because the hash test was returning false first. Well, fixed that, and changed the test code to produce constant hashCode.

The goal, then, is to make equals independent on any definition that might get overridden by later equals. Or, in other words, independent of any other definition related to the trait Equatable itself. Of course, it still will need to access members of the other object, and those might get overridden. That, however, is expected and shouldn’t have any influence on the equals method.

To begin with, let’s think how our equals definition would look like in the class. In the next to last definition, we had this:

override def equals(other : Any) = equalsTo[Point](other, true)

where equals was defined as

protected def equalsTo[This <: Equatable](other : Any, superEquals : => Boolean) : Boolean

This definition delegates to the class the task of calling super.equals – or passing “true” if not appropriate. We can’t do that inside equalsTo, because the equalsTo method is never overridden. “Super”, inside it, will have only one meaning. So this solution will do.

Now, how do we deal with equateValues? One obvious solution would be doing this:

protected def equalsTo[This <: Equatable](other : Any, equateValues : Seq[Any], superEquals : => Boolean) : Boolean

There are at least two reasons this isn’t going to work. First, while it solves the problem of equateValues on “this” object, as it get passed as a parameter on equals’ definition, it doesn’t solve it for “that” object! In fact, we now have no way of finding out what are the elements to be compared in the other object.

A second problem, though, might not be as obvious. We might depend on mutable data or data which isn’t computed yet at the time we define equals. Getting around that is possible, but would be much worse than defining an equals method by oneself!

So, what we’ll do is pass a function instead. A function which, given a “that” object, returns the sequence we need. Or, in other words, we want a object of this type:

(that : This) => Seq[Any]

The only problem with that is that “this” inside our trait does not have type This. We’ll need to receive a reference to ourselves, properly typed! Our definition, then, should be:

protected def equalsTo[This <: Equatable](self : This, other : Any, equateValues : This => Seq[Any], superEquals : => Boolean) : Boolean

The body of our function, then, becomes:

(other : @unchecked) match {
    case that : This =>
      (
        that.canEqual(this)
        && superEquals
        && hashCode == that.hashCode // Can speed up or slow down 
        && equateValues(self).zip(equateValues(that)).foldLeft(true) {
          (equals, tuple) => equals && tuple._1 == tuple._2
        } && equateValues.size == that.equateValues.size
      )
    case _ => false
  }}
}

Now, how would our equals definition look like? Here:

override def equals(other : Any) = equalsTo[Point](this, other, that => List(that.x, that.y), true)
override def equals(other : Any) = equalsTo[Point3D](this, other, that => List(that.z), super.equals(other))

For big objects, inserting the function in the parameters might be awkward. Instead, we might prefer to assign the function to a val first. For example:

private val pointValues = (that : Point) => List(that.x, that.y)

So, here’s everything together, with a bit of further editing for performance resons:


trait Equatable extends scala.util.Hashable {
  def canEqual (that : Any) : Boolean
  
  protected def equalsTo[This <: Equatable](self : This, other : Any, equateValues : This => Seq[Any], superEquals : => Boolean) : Boolean = 
    (other : @unchecked) match {
      case that : This if self.getClass.isAssignableFrom(that.getClass) =>
        // Testing for hash code can improve or decrease performance, depending on the implementation;
        // if hashCode gets implemented as a val, it will make equality faster
        if (that.canEqual(this) && superEquals && hashCode == that.hashCode) {
          val thisValues = equateValues(self)
          val thatValues = equateValues(that)
          (thisValues.zip(thatValues).foldLeft(true) { (equals, tuple) => equals && tuple._1 == tuple._2 } 
           && thisValues.size == thatValues.size)
        } else false
      case _ => false
    }
}

class Point (val x : Int, val y : Int) extends Equatable {
  override def toString = "(%d, %d)" format (x, y)

  // Hashable definitions
  // override def hashValues = List(x, y)
  override def hashValues = List(0) // We don't want the hash skipping our tests
  
  // Equatable definitions
  private val pointValues = (that : Point) => List(that.x, that.y) // one way
  override def equals(other : Any) = equalsTo[Point](this, other, pointValues, true)
  override def canEqual(other : Any) : Boolean = other.isInstanceOf[Point]
}

class Point3D(x : Int,y : Int, val z : Int) extends Point(x,y) with Equatable {
  override def toString = "(%d, %d, %d)" format (x, y, z)

  // Hashable defintions
  // override def hashValues = List(x, y, z)
  override def hashValues = List(0) // We don't want the hash skipping our tests

  // Equatable defintions
  // private val point3DValues = (that : Point3D) => List(that.z)
  override def equals(other : Any) = equalsTo[Point3D](this, other, that => List(that.z), super.equals(other))
  override def canEqual(other : Any) : Boolean = other.isInstanceOf[Point3D]
}

And the tests. I thought about doing them as assertions, but it was too silent for my taste. Anyway,


scala> val x = new Point(1, 2); val x2 = new Point(1, 2)
x: Point = (1, 2)
x2: Point = (1, 2)

scala> x == x2 // super.equals does not get called, so we do not perform reference equality
res0: Boolean = true

scala> val y = new Point(2, 1)
y: Point = (2, 1)

scala> x == y // expected false
res1: Boolean = false

scala> val z = new Point3D(1, 2, 0)
z: Point3D = (1, 2, 0)

scala> x == z // false in that canEqual this test
res2: Boolean = false

scala> z == x // false through reflection isAssignableFrom
res3: Boolean = false

scala> val z2 = new Point3D(2, 1, 0)
z2: Point3D = (2, 1, 0)

scala> z == z2 // expected false
res4: Boolean = false

scala> val z3 = new Point3D(1, 2, 0)
z3: Point3D = (1, 2, 0)

scala> z == z3 // expected true
res5: Boolean = true

scala> val z4 = new Point3D(1, 2, 1)
z4: Point3D = (1, 2, 1)

scala> z == z4 // extected false
res6: Boolean = false

scala> x == x
res7: Boolean = true

Equality & Scala

2009-06-16T15:02:00.011-03:00

I'm just through reading three different sources on equality in less than a week. They all said pretty much the same thing, with a minor variation here or there. It got me thinking about it, and I have some thoughts to share. For this discussion, I'll assume you are familiar with how to do equality correctly. My examples follow the model given in this article.

Let's start with two simple classes:


class Point (val x : Int, val y : Int) {
 override def toString = "(%d, %d)" format (x, y)
}

class Point3D (x : Int, y : Int, val z : Int) extends Point(x,y) {
  override def toString = "(%d, %d, %d)" format (x, y, z)
}

Now, a proper equality method in these classes would look like the following:


class Point (val x : Int, val y : Int) {
  override def toString = "(%d, %d)" format (x, y)
  override def hashCode = 41 * (41 + x) + y
  override def equals(other : Any) : Boolean = other match {
    case that : Point => (
      that.canEqual(this)
      && this.x == that.x
      && this.y == that.y
    )
    case _ => false
  }
  def canEqual(other : Any) : Boolean = other.isInstanceOf[Point]
}

class Point3D (x : Int, y : Int, val z : Int) extends Point(x,y) {
  override def toString = "(%d, %d, %d)" format (x, y, z)
  override def hashCode = 41 * (41 * (41 + x) + y) + z
  override def equals(other : Any) : Boolean = other match {
    case that : Point3D => (
      that.canEqual(this)
      && super.equals(that)
      && this.z == that.z
    )
    case _ => false
  }
  override def canEqual(other : Any) : Boolean = other.isInstanceOf[Point3D]
}

Now, Scala has, starting with version 2.8, a Hashable trait, with which we can simplify things:


class Point (val x : Int, val y : Int) extends scala.util.Hashable {
  override def toString = "(%d, %d)" format (x, y)
  override def hashValues = List(x, y)
  override def equals(other : Any) : Boolean = other match {
    case that : Point => (
      that.canEqual(this)
      && this.x == that.x
      && this.y == that.y
    )
    case _ => false
  }
  def canEqual(other : Any) : Boolean = other.isInstanceOf[Point]
}

class Point3D (x : Int, y : Int, val z : Int) extends Point(x,y) {
  override def toString = "(%d, %d, %d)" format (x, y, z)
  override def hashValues = List(x, y, z)
  override def equals(other : Any) : Boolean = other match {
    case that : Point3D => (
      that.canEqual(this)
      && super.equals(that)
      && this.z == that.z
    )
    case _ => false
  }
  override def canEqual(other : Any) : Boolean = other.isInstanceOf[Point3D]
}

While it doesn't seem to have gained us anything, it might for larger objects, and, at any rate, it removes the "magic" of a hash code, and let someone else worry how to do it.

Still, there's a lot of stuff in there just to get equality right, and these are pretty simple classes. What we see is a programming pattern, but one so common and so important that, in my opinion, it merits special attention from the language itself.

Barring that, let's see what we can do programmatically about it. I'll start with a helper function, and how it would be used:


def testEquality(one : AnyRef, other : AnyRef, elementsOne : Seq[Any], elementsOther : Seq[Any]) : Boolean = {
  val classOfOne = one.getClass
  val classOfOther = other.getClass

  def sameClassOrSubclass: Boolean = classOfOne.isAssignableFrom(classOfOther)

  def superEquals : Boolean = try {
    val superEqualsMethod = classOfOne.getSuperclass.getMethod("equals", classOf[Any])
    if (superEqualsMethod.getDeclaringClass != classOf[Any])
      superEqualsMethod.invoke(one, other) match {
        case flag : java.lang.Boolean => flag.booleanValue // Translate boxed boolean into boolean
        case _ => error("Method equals on the parent class of object " + one + " does not return a boolean")
      }
    else true
  } catch {
    case _ => true
  }

  def canEqual : Boolean = try {
    val canEqualMethod = classOfOther.getMethod("canEqual", classOf[Any])
    canEqualMethod.invoke(other, one) match {
      case flag : java.lang.Boolean => flag.booleanValue // Translate boxed boolean into boolean
      case _ => error("Method canEqual on object " + other + " does not return a boolean")
    }
  } catch {
    case _ => true
  }

  def elementsEquals : Boolean = {
    elementsOne.zip(elementsOther).foldLeft(true) {
      (equals, pair) => equals && pair._1 == pair._2
    } && elementsOne.size == elementsOther.size
  }

  (sameClassOrSubclass(classOfOne, classOfOther)
    && canEqual
    && superEquals
    && elementsEquals
  )
}

class Point (val x : Int, val y : Int) extends scala.util.Hashable {
  override def toString = "(%d, %d)" format (x, y)

  // Hashable
  override def hashValues = List(x, y)

  // Equality
  override def equals(other : Any) : Boolean = other match {
    case that : Point => testEquality(this, that, List(x, y), List(that.x, that.y))
    case _ => false
  }
  def canEqual(other : Any) : Boolean = other.isInstanceOf[Point]
}

class Point3D(x : Int,y : Int, val z : Int) extends Point(x,y) {
  override def toString = "(%d, %d, %d)" format (x, y, z)

  // Hashable
  override def hashValues = List(x, y)

  // Equality
  override def equals(other : Any) : Boolean = other match {
    case that : Point3D => testEquality(this, that, List(x, y, z), List(that.x, that.y, that.z))
    case _ => false
  }
  override def canEqual(other : Any) : Boolean = other.isInstanceOf[Point3D]
}

Now, this method always calls the parent's equals, unless it's Any's equals. You might want to parametrize this. Also, it expects canEqual to be defined if needed, which might lead to bugs. Furthermore, its usage of reflection makes it slower than needed. Finally, the definition of equals is not that much simpler than what we had before.

So, can we do better? Ideally, one could build a trait similar to Hashable, but it turns out that is not that simple. Let's try:


trait Equatable extends scala.util.Hashable {
  protected type EquateThis <: Equatable
  private def equalsFromAny : Boolean = {
    this.getClass.getSuperclass.getMethod("equals", classOf[Any])
    .getDeclaringClass == classOf[Any]
  }

  protected def equateValues : Seq[Any]

  def canEqual (that : Any) : Boolean = true

  abstract override def equals(other : Any) : Boolean = (other : @unchecked) match {
    case that : EquateThis =>
      (
        that.canEqual(this)
        && (equalsFromAny || super.equals(that))
        && hashCode == that.hashCode // Can speed up or slow down
        && equateValues.zip(that.equateValues).foldLeft(true) {
          (equals, tuple) => equals && tuple._1 == tuple._2
        } && equateValues.size == that.equateValues.size
      )
    case _ => false
  }
}

class Point (val x : Int, val y : Int) extends Equatable {
  override def toString = "(%d, %d)" format (x, y)

  // Hashable definitions
  override def hashValues = List(x, y)

  // Equatable definitions
  override type EquateThis = Point
  override def equateValues = List(x, y)
  override def canEqual(other : Any) : Boolean = other.isInstanceOf[Point]
}

class Point3D(x : Int,y : Int, val z : Int) extends Point(x,y) with Equatable {
  override def toString = "(%d, %d, %d)" format (x, y, z)

  // Hashable defintions
  override def hashValues = List(x, y, z)

  // Equatable defintions
  override type EquateThis = Point3D
  override def canEqual(other : Any) : Boolean = other.isInstanceOf[Point3D]
  override def equateValues = List(z)
}

That looks more like it, but it has a few problems still. It still uses reflection, for one thing, to test for super's equals method. Also, you can't parametrize that is it is. It won't get Equatable's own equals, though, as traits compiles down to part of the class being defined, not as an ancestor to it.

Next, it has a default for canEqual, and a dangerous one at that. If the programmer forgets to override it, it will lead to trouble.

But, most importantly, it doesn't work. The class Point3D can't override Point's definition for type EquateThis. I don't understand precisely why this is the case, and I'd be glad if anyone stepped in to explain this.

Anyway, let fix these problems:


trait Equatable extends scala.util.Hashable {
  protected def testSuperEquals : Boolean
  protected def equateValues : Seq[Any]
  def canEqual (that : Any) : Boolean

  protected def equalsTo[This <: Equatable](other : Any) : Boolean = (other : @unchecked) match {
    case that : This =>
      (
        that.canEqual(this)
        && ((!testSuperEquals) || super.equals(that))
        && hashCode == that.hashCode // Can speed up or slow down
        && equateValues.zip(that.equateValues).foldLeft(true) {
          (equals, tuple) => equals && tuple._1 == tuple._2
        } && equateValues.size == that.equateValues.size
      )
    case _ => false
  }
}

class Point (val x : Int, val y : Int) extends Equatable {
  override def toString = "(%d, %d)" format (x, y)

  // Hashable definitions
  override def hashValues = List(x, y)

  // Equatable definitions
  override def testSuperEquals = false
  override def equateValues = List(x, y)
  override def equals(other : Any) = equalsTo[Point](other)
  override def canEqual(other : Any) : Boolean = other.isInstanceOf[Point]
}

class Point3D(x : Int,y : Int, val z : Int) extends Point(x,y) with Equatable {
  override def toString = "(%d, %d, %d)" format (x, y, z)

  // Hashable defintions
  override def hashValues = List(x, y, z)

  // Equatable defintions
  override def testSuperEquals = true
  override def equals(other : Any) = equalsTo[Point3D](other)
  override def canEqual(other : Any) : Boolean = other.isInstanceOf[Point3D]
  override def equateValues = List(z)
}

This finally get us where we wanted. Or as close to as I could, at least. :-)

The definition of canEqual is made abstract. That forces the first class to mix Equatable in to define it, even if to a default of "true". Next, instead of trying to figure out if equality must be called on the super, we simply require the class to tell us.

Finally, the equals method. We can't (or I couldn't) get the trait to define it, but I got pretty close. In the end, class still has to define an equals method, but that method pretty much gets reduced to a simple call to one defined in the trait, passing the object being compared to and the class expected. The class expected gets passed as an explicit type parametrization.

Neat. I didn't think I'd be able to get this much! Now, who's going to port it to Java?

Update:

Ok, I spoke too soon. This method fails here:


scala> val x = new Point(1, 2); val x2 = new Point(1, 2)
x: Point = (1, 2)
x2: Point = (1, 2)

scala> x == x2 // super.equals does not get called, so we do not perform reference equality
res7: Boolean = true

scala> val y = new Point(2, 1)
y: Point = (2, 1)

scala> x == y // expected false
res8: Boolean = false

scala> val z = new Point3D(1, 2, 0)
z: Point3D = (1, 2, 0)

scala> x == z // false in the canEqual call
res9: Boolean = false

scala> z == x // false in the type check
res10: Boolean = false

scala> val z2 = new Point3D(2, 1, 0)
z2: Point3D = (2, 1, 0)

scala> z == z2 // false in the super.equals call
res11: Boolean = false

scala> val z3 = new Point3D(1, 2, 0)
z3: Point3D = (1, 2, 0)

scala> z == z3 // false in the super.super.equals call - it should have been true
res12: Boolean = false

Anyone up for fixing it?

Update 2:

Ok, I fixed it. I resorted to delegating this task to the calling class. That means I do away with testSuperEquals, but require a second parameter to equalsTo. I make it by name, so that it doesn't get evaluated needlessly.


trait Equatable extends scala.util.Hashable {
  protected def equateValues : Seq[Any]
  def canEqual (that : Any) : Boolean
  
  protected def equalsTo[This <: Equatable](other : Any, superEquals : => Boolean) : Boolean = (other : @unchecked) match {
    case that : This =>
      (
        that.canEqual(this)
        && superEquals
        && hashCode == that.hashCode // Can speed up or slow down 
        && equateValues.zip(that.equateValues).foldLeft(true) {
          (equals, tuple) => equals && tuple._1 == tuple._2
        } && equateValues.size == that.equateValues.size
      )
    case _ => false
  }}
}

class Point (val x : Int, val y : Int) extends Equatable {
  override def toString = "(%d, %d)" format (x, y)

  // Hashable definitions
  override def hashValues = List(x, y)
  
  // Equatable definitions
  override def equateValues = List(x, y)
  override def equals(other : Any) = equalsTo[Point](other, true)
  override def canEqual(other : Any) : Boolean = other.isInstanceOf[Point]
}

class Point3D(x : Int,y : Int, val z : Int) extends Point(x,y) with Equatable {
  override def toString = "(%d, %d, %d)" format (x, y, z)

  // Hashable defintions
  override def hashValues = List(x, y, z)

  // Equatable defintions
  override def equals(other : Any) = equalsTo[Point3D](other, super.equals(other))
  override def canEqual(other : Any) : Boolean = other.isInstanceOf[Point3D]
  override def equateValues = List(z)
}

And the testing:


scala> val x = new Point(1, 2); val x2 = new Point(1, 2)
x: Point = (1, 2)
x2: Point = (1, 2)

scala> x == x2 // super.equals does not get called, so we do not perform reference equality
res105: Boolean = true

scala> val y = new Point(2, 1)
y: Point = (2, 1)

scala> x == y // expected false
res106: Boolean = false

scala> val z = new Point3D(1, 2, 0)
z: Point3D = (1, 2, 0)

scala> x == z // false in the canEqual call
res107: Boolean = false

scala> z == x // false in the type check
res108: Boolean = false

scala> val z2 = new Point3D(2, 1, 0)
z2: Point3D = (2, 1, 0)

scala> z == z2 // false in the super.equals call
res109: Boolean = true

scala> val z3 = new Point3D(1, 2, 0)
z3: Point3D = (1, 2, 0)

scala> z == z3 // expected true
res110: Boolean = true

Update 3:

This is still seriously broken, as the very test above indicates. What is happening is that when super.equals gets called, it uses this.equateValues instead of the super's version of it. It might be easy to fix for "this", but not for "that". At this point, I'm giving up on super.equals. Let's assume the equality for all classes is defined by the equalsTo method, and require a call to super.equateValues at every subclass (that finds it necessary). Here it is


trait Equatable extends scala.util.Hashable {
  protected def equateValues : Seq[Any]
  def canEqual (that : Any) : Boolean
  
  protected def equalsTo[This <: Equatable](other : Any) : Boolean = (other : @unchecked) match {
    case that : This =>
      (
        that.canEqual(this)
        && hashCode == that.hashCode // Can speed up or slow down 
        && equateValues.zip(that.equateValues).foldLeft(true) {
          (equals, tuple) => equals && tuple._1 == tuple._2
        } && equateValues.size == that.equateValues.size
      )
    case _ => false
  }}
}

class Point (val x : Int, val y : Int) extends Equatable {
  override def toString = "(%d, %d)" format (x, y)

  // Hashable definitions
  override def hashValues = List(x, y)
  
  // Equatable definitions
  override def equateValues = List(x, y)
  override def equals(other : Any) = equalsTo[Point](other)
  override def canEqual(other : Any) : Boolean = other.isInstanceOf[Point]
}

class Point3D(x : Int,y : Int, val z : Int) extends Point(x,y) with Equatable {
  override def toString = "(%d, %d, %d)" format (x, y, z)

  // Hashable defintions
  override def hashValues = List(x, y, z)

  // Equatable defintions
  override def equals(other : Any) = equalsTo[Point3D](other)
  override def canEqual(other : Any) : Boolean = other.isInstanceOf[Point3D]
  override def equateValues = z :: super.equateValues
}

And test:


scala> val x = new Point(1, 2); val x2 = new Point(1, 2)
x: Point = (1, 2)
x2: Point = (1, 2)

scala> x == x2 // super.equals does not get called, so we do not perform reference equality
res138: Boolean = true

scala> val y = new Point(2, 1)
y: Point = (2, 1)

scala> x == y // expected false
res139: Boolean = false

scala> val z = new Point3D(1, 2, 0)
z: Point3D = (1, 2, 0)

scala> x == z // false in the canEqual call
res140: Boolean = false

scala> z == x // false in the type check
res141: Boolean = false

scala> val z2 = new Point3D(2, 1, 0)
z2: Point3D = (2, 1, 0)

scala> z == z2 // expected false
res142: Boolean = false

scala> val z3 = new Point3D(1, 2, 0)
z3: Point3D = (1, 2, 0)

scala> z == z3 // expected true
res143: Boolean = true

Using Implicits to Select Types

2009-06-11T23:05:00.009-03:00

Scala 2.8's collection revision is doing interesting things. The most obvious one will be the methods revision. One thing that shouldn't be all that obvious, though, is how much code will be shared, and how that shared code will still look like it was specific to a class.

I'll quote here a couple of examples from the Scala 2.8 Collection's Whitepaper (pdf at the bottom):


scala> "abc" map (x => (x + 1).toChar)
res1: scala.runtime.RichString = bcd

scala> "abc" map (x => (x + 1))
res2: scala.collection.immutable.Vector[Int] = Vector(98, 99, 100)

scala> Map("a" -> 1, "b" -> 2) map { case (x, y) => (y, x) }
res3: scala.collection.immutable.Map[Int,java.lang.String] = Map(1 -> a, 2 -> b)

scala> Map("a" -> 1, "b" -> 2) map { case (x, y) => y }
res4: scala.collection.immutable.Iterable[Int] = List(1, 2)

Now, this "map" method is inherited from a common trait, and yet it knows when the result of a map over a RichString is a RichString, when the result of a map over a Map is a Map, and when it's not. How can it be?

The answer is implicit parameters. One thing about implicits, is that a more specific implicit has preference over a more generic one. Take a look at this example:


scala> abstract class X[T] { def id : Unit }
defined class X

scala> implicit def a[T] = new X[T] { def id = println("generic") }
a: [T]X[T]

scala> implicit def b = new X[Int] { def id = println("Int") }
b: X[Int]

scala> def f[T](a : T)(implicit g : X[T]) = g.id
f: [T](T)(implicit X[T])Unit

scala> f(5)
Int

scala> f('c')
generic

Both "a" and "b" have the correct type, X[T]. The second definition, though, will return X[Int], which is more specific than X[T], which the first definition returns. So, whenever X[Int] is required, "b" will take precedence over "a". Naturally, if some other type of X is required, "b" won't be used at all.

This is how map can do its trick. To compose the result, it uses methods from the class Builder[-Elem, +To]. Such a build will create a collection of type To from elements of type Elem. Now, this is not enough to solve map's problem. For example, I want a RichString as result, if I'm doing a map over a RichString, but not if I'm mapping over a List of Chars. See the two examples below:


scala> "abc" map (x => (x + 1).toChar)
res1: scala.runtime.RichString = bcd

scala> List('a', 'b', 'c') map (x => (x + 1).toChar)
res11: List[Char] = List(b, c, d)

So, for methods with more complex semantics, like map, we need something else which can produce the correct Builder. For that, the trait BuilderFactory[Elem,

+To, From] exists. BuilderFactory will produce a Builder for a method which takes a collection of type From, and uses elements of type Elem to produce a collection of type To.

Now, the more generic implicit for a BuilderFactory is BuilderFactory[A, Iterable[A], Iterable[_]], which should be pretty obvious. Other implicits exists, though, such as BuilderFactory[Char, RichString, RichString]. Now, look at map's declaration:


def map[B, That](p: Elem => B)(implicit bf: BuilderFactory[B, That, This]): That

So, when you do "abc".map( x => (x + 1).toChar), the compiler knows that "B" is Char (the result of the function being mapped). "This" is known to be RichString, from the definition of class RichString itself. Now, given that "B" = Char and "This" = RichString, then BuilderFactory[Char, RichString, RichString] is a more specific match than the other implicit definitions. And, because it gets used, "That" gets defined to be RichString also, thus defining the result type for that map.

The cleverness of it is to use implicits to define unknown type parameters as a function of known type parameters. This is can be a very useful pattern for those who want to take maximum advantage of static type checking.

Case Classes and Product

2009-06-11T17:36:00.004-03:00

It's a well-known fact that by adding "case" before "class" in Scala, the compiler will generate some scaffolding for you like making all your paremeters "val", creating apply and unapply in a companion object. etc.

It's not a particular known fact that one of the things it does is extending the class with the trait Product. This trait makes it easy to access the elements of the class, like in the example below:


scala> trait recordType {
     |   self : Product =>
     |   def records : String = (
     |     for(parm <- self.productIterator)
     |       yield parm.asInstanceOf[AnyRef].getClass.getSimpleName+": "+parm
     |     ) mkString "\n"
     | }
defined trait recordType

scala> case class X(i : Int, c : Char, s : String) extends recordType
defined class X

scala> val x = X(5, 'd', "this")
x: X = X(5,d,this)

scala> println(x.records)
Integer: 5
Character: d
String: this

Let me talk about the trait recordType a bit first. Its body first line declares that "self : Product =>". This has two purposes. First, it creates an alias for "this". Second, and most important, it tells the compiler that to be able to use this trait, a class must mix in the trait Product.

Anyway, the code works fine for simple classes, but it might be weird for collections:


scala> case class Y(a : Array[String], l : List[Int]) extends recordType
defined class Y

scala> val y = Y(Array("this", "example"), List(1,2,3))
y: Y = Y([Ljava.lang.String;@60a517,List(1, 2, 3))

scala> println(y.records)
String[]: [Ljava.lang.String;@60a517
$colon$colon: List(1, 2, 3)

Here, Array is mucked up because Java's Array are mucked up. As for the List, any non-empty List actually belongs to class "::", a subclass of List.

Function.tupled, Function.curried

2009-06-07T18:15:00.004-03:00

Scala's library hides small gems of which little is said. Let me speak of a personal favorite here, the object Function.

This object has a number of methods to construct a function from another function (or others, in the case of "chain"). They are variations of "curried", "tupled", "uncurried" and "untupled". As their names makes clear, they transform a function whose arguments are not curried or are not a tuple into a function whose arguments are curried, or which receives a tuple as an argument. Take, for instance, this definition of zipMap, which applies a function of two arguments between two lists:


scala> def zipMap[A,B,C](l1 : Seq[A], l2 : Seq[B])(f : (A,B) => C) =
     | l1 zip l2 map (x => f(x._1, x._2))
zipMap: [A,B,C](l1: Seq[A],l2: Seq[B])(f: (A, B) => C)Sequence[C]

scala> zipMap (List(1, 3, 9), List(5, 2, 3)) ((x,y) => x max y)
res5: Sequence[Int] = List(5, 3, 9)

This is not a bad definition, but accessing the tuple arguments to pass to f is too much mechanics for my taste. So, instead, we could do this:


scala> def zipMap[A,B,C](l1 : Seq[A], l2 : Seq[B])(f : (A,B) => C) =
     | l1 zip l2 map Function.tupled(f)
zipMap: [A,B,C](l1: Seq[A],l2: Seq[B])(f: (A, B) => C)Sequence[C]

scala> zipMap (List(1, 3, 9), List(5, 2, 3)) ((x,y) => x max y)
res4: Sequence[Int] = List(5, 3, 9)

Much better, don't you think? By the way, this was done on 2.8, where Seq has the method zip.

Scalable Algorithms 3

2009-06-05T22:54:00.008-03:00

Back to matching shortcuts to menu options, I decided my best option would be a deterministic finite automaton. It would make excellent use of partial input, and take much less space than a set of all possible inputs accepted -- to make use of state machine lingo -- by each menu option.

Now, anyone who has ever worked with DFA before will tell you that the trick to build one is to first generate the regular expression which represents what you want to match. Yes, that's your good, old RegExp. Well, not fully... you can't have back references, for one thing. But most of what you think of as regexp will do.

So, what regular expression would match our input? Let's take a small menu option: "New Tab". We want to accept either word as well as its abbreviation, so "New", "Tab" and "NT" should be matched. Any prefix of either word should be taken as well, so we add "N", "Ne", "T" and "Ta" to it. Finally, we want to combine word prefixes, like "NTab" or "NeTa", you get the idea.

So, let's get the first word, and see how far we can take. We have "N", "Ne" and "New". So "N" is mandatory, and "e" is optional. That would be "Ne?" in regexp. Next, "w" is also optional, but it can only appear if "e" appears as well. That's "N(ew?)?" in regexp, or, to make regular use of parenthesis, "N(e(w)?)?". Now, since we may as well only match the second word, the whole first word is optional, which gives us "(N(e(w)?)?)?".

Naturally, each word would follow the same pattern, but what about the whole menu option? As it happens, you only have to concatenate the patterns: "(N(e(w)?)?)?(T(a(b)?)?)?". It should be pretty simply to create such a function.

In fact, we can do it using foldRight. As you know, foldRight combines things from right to left, using the result of the last operation and the next element. Now, it may not be immediately obvious what the operation is, so let's assume we already processed "w". That means we have "(w)?" as the last result, and "e" as the next letter, and the result we want to come up with is "(e(w)?)?". It's trivial to see, then, that the operation is "("+"e"+"(w)?"+")?".

Now that we know what the operation is, let's think about the initial "result" that fold takes as parameter. We want x in "("+"w"+x+")?". Since that must be equal to "(w)?", x = "".

Ok, so now we know what the regular expression for a menu option must look like, as well as how to build one from its string. We can now proceed to building a DFA.

But... we can match regular expressions to strings just as well as DFA. I might not take advantage of partial inputs, and I can't go the next step, which is creating one DFA which will accept all menu options and, as an added bonus, have the associated menu options at each state.

Still, how hard would it be to match against regexp? Well, let's try...


val wordsep = "\\W+"
def words(s : String) = s.split(wordsep)
def phraseRegex(s : String) = 
  "^" + words(s).map(_.foldRight("")("(" + _ + _ + ")?")).mkString
def regexList(l : List[String]) = l.map(s => phraseRegex(s) -> s)
def regexSearcher(l : List[String]) = {
  val r = regexList(l)
  (s : String) => r.filter(s matches _._1).map(_._2)
}

That's it. You could, and should improve it by pre-compiling the regexp expressions. It's a bit uglier, but for the sake of doing things right, I'll post it at the end. Anyway, this is fairly inexpensive in terms of memory usage, and regexp matches are very fast. I doubt it can beat a hash tree, but it should give it a run for its money. Still, the fact that you'll be matching every menu option against the input is problematic, and the hash tree doesn't suffer that problem. The setup time for this algorithm should be pretty fast too, even precompiling the regexp.

Anyway, it's short, it's obvious, and it's not too shabby. We'll next get into DFA, and do it by using Scala's standard library. That should be the worst of all algorithms, but a stepping stone to the last one I'll present. For now, here's the revised code.


val wordsep = "\\W+"
def words(s : String) = s.split(wordsep)
def phraseRegex(s : String) = 
  ("^" + words(s).map(_.foldRight("")("(" + _ + _ + ")?")).mkString).r
def regexList(l : List[String]) = l.map(s => phraseRegex(s) -> s)
def regexSearcher(l : List[String]) = {
  val r = regexList(l)
  (s : String) => r.filter(_._1.findPrefixOf(s) == Some(s)).map(_._2)
}

Compiling Remotely

2009-06-03T21:03:00.003-03:00

As you may know, the fsc compiler, the recommended way to compile Scala, and used by the Scala interpreter by default, detaches a daemon service the first time it is run. After that, fsc will always call the daemon service to compile for it, to save time.

It does this through TCP, which begs the question... can I compile remotely? The answer is Yes! It's not documented, and it is a bit awkward, but...

First, you get fsc running on the server by running fsc -verbose, like this:


$fsc -verbose
[Server arguments: -d C:\Users\Daniel\Documents\Programas\. -verbose]
[VM arguments: ]
[Temp directory: C:\PROGRA~1\Scala\bin\..\var\scala-devel]
[Executed command: C:\PROGRA~1\Scala\bin\..\bin\scala.bat scala.tools.nsc.CompileServer]
[Port number: 1385]
[Connected to compilation daemon at port 1385]
Usage: fsc  
where possible standard options include:
  -g:                       Specify level of generated debugging info (none,source,line,vars,notailcalls)
  -nowarn                      Generate no warnings
  -verbose                     Output messages about what the compiler is doing
  -deprecation                 Output source locations where deprecated APIs are used
  -unchecked                   Enable detailed unchecked warnings
  -classpath             Specify where to find user class files
  -sourcepath            Specify where to find input source files
  -bootclasspath         Override location of bootstrap class files
  -extdirs               Override location of installed extensions
  -d                Specify where to place generated class files
  -encoding          Specify character encoding used by source files
  -target:             Specify for which target object files should be built (jvm-1.5,jvm-1.4,msil)
  -print                       Print program with all Scala-specific features removed
  -optimise                    Generates faster bytecode by applying optimisations to the program
  -explaintypes                Explain type errors in more detail
  -uniqid                      Print identifiers with unique names for debugging
  -version                     Print product version and exit
  -help                        Print a synopsis of standard options
  -X                           Print a synopsis of advanced options
  @<file>                      A text file containing compiler arguments (options and source files)

This will get you the port number. Next, you can compile whatever you like from a remote client like this:

$fsc -server 192.168.1.35:1385 strategy.scala

That's it. Cool, eh?

Parser Surprise

2009-06-03T11:39:00.009-03:00

David Vydra found it surprising that he couldn't do the following:

scala> -1.toString

:1: error: ';' expected but '.' found.

-1.toString

^

I was surprised too by some similar example, from page 208 of Programming in Scala: A Comprehensive Step-by-step Guide.

Given that example, I would not expect that message in particular, but I would expect an error: that "unary_-" is not a member of java.lang.String, like this:

scala> -(1 toString)

:5: error: value unary_- is not a member of java.lang.String

-(1 toString)

^

Or, in fact, like this:

scala> +1.toString

:5: error: value unary_+ is not a member of java.lang.String

+1.toString

^

Some people have raised the question of operator precedence, claiming "-" ought to have more precedence than ".". It might seems reasonable in this example, where "1" is obviously an integer literal. But what about "-object.size"? Would you expect it to negate the object's size, or to negate the object and then return the size?

So let's take a look at Scala's operator precedence rule. The rules states that, with a sole excetion, the precedence, from the lowest to the highest, is based on an operator's first character as follow:

(all letters)

|

^

&

< >

= !

:

+ -

* / &

(all other special characters)

The exception is that an assignment has lower precedence than any other operator. Because of this excection, += -- an assignment -- has lower precedence than <=, the less-than-or-equal-to operator, even though operators starting with + have precedence over those starting with "<".

These, though, are the precedence rules for infix operators, and "-" in "-1" is not infix, but prefix. So, does infix precedence applies for prefix operators? No, as the example below shows:

scala> class X {

| def unary_- = {println("Unary -"); this}

| def *(b : X) = {println("operator *"); this}

| def -(b : X) = {println("operator -"); this}

| override def toString = "class X"

| }

defined class X



scala> new X

res16: X = class X



scala> new X

res17: X = class X



scala> -res16 * res17

Unary -

operator *

res18: X = class X



scala> res16 - res17 * res16

operator *

operator -

res19: X = class X

So we can see clearly that unary_- has precence over "*", which, itself, has precedence over "-".

So, back to ".", what is happening? Well, for one thing, "." is not an operator. Dot is considered an operator in some other languages. In Scala, though, it is a syntactic construct. If it were an operator, you would be able to define it in a class. As it is, it's a reserved symbol. So any operator will only be considered after resolving ".".

Still, again, why isn't the error as follow?

scala> -(1 toString)

:5: error: value unary_- is not a member of java.lang.String

-(1 toString)

^

Johannes Rudolph has since investigated this further. Here is his analysis:

Originally(*), and despite of the language specification (**),
negative number literals could not appear in a select expression
(-1.max(5)). Since [19950] which 'fixed' #2378 (***), the balance
between integer and floating point literals drifted: for with what the
parser was concerned, negative floating point literals received no
special treating any more, so -5f.max(2) was seen as
(5f.max(2)).unary_-, simple negative floating literals as 5f.unary_-
(*!*). For negative integer literals the situation stayed the way it
was the way before: -1.max(5) was simply not allowed by the parser.

(*) That's [3930], the commit with the unimpressive empty log message
where nsc sprang to life.
(**) The SLS would allow both 5.unary_- and the literal -5 and does at
least not specify how to resolve this ambiguity.
(***) The real cause of #2378 can be found in the backyard of the
backend: FJBG generates a DCONST_0 if a double literal == 0.0, what
-0.0 is.
(*!*) This behaviour caused #3486, where negative constants in
annotations wouldn't be possible any more.

Scalable Algorithms 2

2009-06-02T12:54:00.015-03:00

In my last post, I told of a programming challenge taken, and my first go at it. While the algorithm I came up with had a certain cleverness, there was much to criticize about it.

Another friend, who had received the same challenge, attacked the problem from a different perspective. His algorithm was not as liberal with the input as mine, as it accepted only abbreviations or single words. It would match a prefix of a word other than the first one, though, which is something mine didn't.

For instance, if there was an option "create application shortcuts", it would match that against "cas" or any prefix of it (eg. "ca"), "create" or any prefix of it, "application" or any prefix of it and "shortcuts" or any prefix of it.

Map of Prefixes

I won't post his algorithm of it here (though I'd be happy to link to a post of his, if he does so), but the idea was precomputing a couple of maps: one of full abbreviations into set of menu options, and one of words into set of menu options.

The cleverness of it, though, is that he did not precompute all possible prefixes. Instead, he used ranges, close-ended at the input being matched, and open ended at the input being matched with the last character replaced by it's successor, and applied that range to the keys of each map. The result was that all keys to which the input was a prefix of would be selected.

Now, there were two things about his algorithm I didn't like. First, it would use mutable sets and maps when precomputing. I was trying to avoid that. Second, it would not match a concatenation of the prefix of different words, so appshort would match the example previously given.

So I decided to take a shot at it, which, sadly, did not benefit from the range cleverness. As before, I'll follow the code with my criticisms of it.


val wordsep = "[ :,;]"
def words(s : String) = s.split(wordsep)
def wordPrefixes(s : String) = (0 to s.length).map(s.substring(0,_))
def combinedPrefixes(s : String) =
  words(s).foldLeft(Set(""))((set, word) =>
    set.flatMap(x => wordPrefixes(word).map(y => x + y)))

def reversePhraseMap(l : List[String]) =
  l.foldLeft(Map[String,Set[String]]())((map, phrase) =>
    map + (phrase -> combinedPrefixes(phrase)))

def allPrefixes(m : Map[String,Set[String]]) = m.values.reduceLeft(_ ++ _)

def phraseMap(m : Map[String,Set[String]]) =
  Map[String,Set[String]]() ++ allPrefixes(m).
  map(p => p -> m.foldLeft(Set[String]())((s, x) =>
    if(x._2.contains(p)) s + x._1 else s))

def indexPhrases(l : List[String]) = phraseMap(reversePhraseMap(l))

def searchPhrases(l : List[String]) = {
  val index = indexPhrases(l.map(_.toLowerCase))
  (s : String) => index(s.toLowerCase)
}

The way you use it is you pass a list of menu options to searchPhrases, and searchPhrases returns a function which will look up an input in the list and return the result.

Well. I'm not particularly fond of this algorithm, but the code is much more obvious, in my opinion, than the first one. I had to compute the reversed map first (ie, the menu options pointing to a set of their abbreviations), and then reverse that. I wonder if I shouldn't have reversed the definitions name, though (pun half-intended).

Now, this code is 19 lines vs the first's 34, but this isn't really enough of a difference when considers code complexity. But the first code had 4 "if" statements, all of them followed by "else" statements, one "match" statement and, to boot, a couple of mutually recursive functions. This one has a single "if". This is functional programming at it's best (well, almost best :). In fact, the whole code could be written as a single expression, a single statement:


def searchPhrases(l : List[String]) = 
  (s : String) => (
    Map[String,Set[String]]() ++ 
    (
      (
        l
        map (_ toLowerCase)
        foldLeft Map[String,Set[String]]()
      ) ((map, phrase) =>
        map + (phrase -> 
          (
            (
              phrase 
              split "[ :,;]"
              foldLeft Set("")
            ) ((set, word) =>
              set flatMap (x => (
                  0
                  to word.length
                  map (word substring (0, _))
                  map (x + _)
                )
              )
            )
          )
        )
      ).values
      reduceLeft (_ ++ _)
      map (p => 
        p -> (
          (
            (
              (
                l
                map (_.toLowerCase)
                foldLeft Map[String,Set[String]]()
              ) ((map, phrase) =>
                map + 
                (phrase -> (
                  (
                    phrase
                    split ("[ :,;]")
                    foldLeft Set("")
                  ) ((set, word) =>
                    (
                      set
                      flatMap (x => 
                        (
                          0 
                          to word.length
                          map (word substring (0, _)) 
                          map (x + _)
                        )
                      )
                    )
                  )
                ))
              )
            )
            foldLeft Set[String]()
          ) ((s, x) =>
            if (x._2 contains p) s + x._1 else s
          )
        )
      )
    )
  ) (s toLowerCase)

Now, that's a long, long expression to keep track of, and there's some repetition in it. Broken up in smaller definition helps manage the size, and the definition's names help understand what is being done.

Still, the fact the lack of control structures helps one to focus on what is being done. You don't have to keep backtracking the code and thinking what happens on that other condition. So, while both algorithms deal in immutable objects only, the more you keep to high order functions in place of control structures, the clearer becomes the code.

This algorithm has a fast search, and it can catch any variation of prefixes, as long as no words are inverted. To do that it spends some time building the map, and the map itself is very wasteful of memory. It doesn't make take advantage of character-by-character input, but it doesn't really need it. It has no heuristics to order the list of matched menu options, though, and no easy way to retrofit it. That I can see, at least.

At this point, I decided that what I wanted was a DFA matcher, but this took me to an unexpected place first. The next algorithm has 9 lines of code, two being def lines without code, one being a constant definition, and one being "}". At that, it matches everything this algorithm does. Can you beat that before my next post? :-)

Scalable Algorithms

2009-06-01T14:12:00.011-03:00

It's common knowledge that the best way of learning a new language is writing a program you wanted in it. Or, perhaps I should say, that's the quickest way of learning a language -- you should beware of the gaps in knowledge of the language that can result from this approach.

Well, I was trying to do that with Scala, but I always stopped because there was something more I wanted to learn before continuing with one project or other. It was then that a friend posed a challenge, and that finally broke the programmer's block I was having.

He has written a small program -- in Scala -- with few but loyal followers to help in his gaming sessions, and he wanted something to help with fast keyboard selection. His idea was having an algorithm that would search available menu options based on a few input characters, which would typically stand for an abbreviation of that menu.

As I took the challenge, I formally specified the algorithm requirement to the following: given a list of phrases (representing menu options) and a string of characters (representing user input), select all phrases for which exists a combination of prefixes of arbitrary length whose concatenation equals the string of characters.

Preferably, order the result too using some kind of heuristics.

Well, I wound up writing many solutions to the problem. Of course, there are MANY solutions to the problem -- my friend himself wrote something completely different from any of mine. But I discovered real joy in programming with Scala as I wrote them. So, let me share them with you.

List decomposition

The first concept I came up with was essentially based on lists. Scala has brought me back with full force to the lists algorithms I used once with functional languages.

I'll follow the code with my own thoughts about it. But, first, I want to explain the basic concept. First, I transform each phrase into a list of words, each word being a list of characters. The user input also gets transformed into a list of characters. Next, for each phrase I try possible matches against the input, and return a score.

This is where it gets recursive. After matching each character to the first character of the first word in the list, I select the better of the next two possible options: matching the next character in the word, or the first character in the next word.

The heuristics I used here gives preference first for matches that consume the whole input, and, next, to matches that match most of the words in the input. As such, and keeping in mind abbreviations are the most likely input, I use a function which receives the recursion as by name parameters, and only computes the second option if the first one doesn't return a perfect match (all input consumed, no words left unmatched).

Different from the algorithms wrote next, you can't skip words when matching. Also note I severely shortened the comments, as they got a bit too lengthy for a blog.


// Given two tuples formed by the length of unmatched input and
// the number of unmatched words, choose the "best" of them.
def isBetterThan(a: (Int, Int), b: (Int, Int)) : Boolean = if (a._1 == b._1) {
 if (a._2 < b._2) true else false
} else {
  if (a._1 < b._1) true else false
}

// Receives two expressions by nam, who, in turn, return a tuple representing
// matching efficacy. Evaluates the first expression and, if the efficacy is
// not the best possible, evaluates the second expression and return the better
// one.
def bestOf(aL: => (Int, Int), bL : => (Int, Int)) : (Int, Int) = {
 val a = aL
 if( a == (0,0)) a
 else {
   val b = bL
   if (isBetterThan(a, b)) a else b
 }
}

// Try to match the first character of input and menu option. Recurse if
// succesful.
def matchInputToOption(input : List[Char], op : List[List[Char]]) : (Int, Int) = {
 (input, op) match {
   case (in1 :: Nil, (op11 :: op1s) :: ops) if (in1 == op11) =>
     (0, ops.length)
   case (in1 :: ins, (op11 :: op1s) :: ops) if (in1 == op11) =>
     bestOf(matchInputToOption(ins, ops),
     matchInputToOption(ins, op1s :: ops))
   case (_, _) =>
     (input.length, op.length)
 }
}

// Listify inputs, zip menu options with computed matches, filter for
// matches which consume the whole input, sort them, return.
def searchOptions(input : String, menu : List[String]) : List[(String, Int)] = {
 val inputList = input.toList
 val menuList = menu.map(_.split(" ").toList.map(_.toList))

 (menu
   zip (menuList map (menuOp => matchInputToOption(inputList, menuOp)))
   filter (_._2._1 == 0)
   sort ((a,b) => isBetterThan(a._2,b._2))
   map (x => (x._1, x._2._2))
 )
}

This algorithm was born of matchInputToOption. I was charmed by the flexibility of match, and thinking myself oh-so-clever by realizing I could call tail on the list of words or the list of characters of the head of list of words as the only two alternatives after each match. All the rest as created to make this function work.

I do think that function is clever, and it does go to show Scala's power. The algorithm, itself, can go directly to the nearest trash can. It is easy to check it's correctness -- and please note it only works with immutable objects -- but that isn't enough to make up for its many failings.

First, I do not precompute anything, and I do require some work transforming all those strings into lists. If Scala is using projections to do it, it might not be all that bad though.

Next, it has no memory of previous matches. Each time it's called, it matches the whole input. If you happen to feed it character by character, this becomes very wasteful.

Memory-wise... well, that depends on that projection thingy. If split and toList are being strict (precomputing everything), then we have lists of characters, which are very wasteful.

It is rather fast, but there are faster ones.

And, finally, it's not particularly pretty to look at or easy to understand.

In my next post I'll show a truly memory wasteful algorithm, but a very quick one.

Scala's Projections

2009-05-28T21:06:00.012-03:00

While reading a cool posting by Chris Smith regarding F#, I noticed something he did not remark on, which is very common in functional programming languages. In his code, he makes a sequence from 3 to 3,628,800, and then does a lot of stuff on it. He transforms everything into strings, computes stuff from that string, etc. Here's a Scala equivalent:

object Factorial {
  private [Factorial] class Fact(n : Int) {
    def ! : Int = if (n <= 1) 1 else (n * new Fact(n-1).!)
  }
  implicit def toFact(n : Int) : Fact = new Fact(n)
}

import Factorial._

println((3 to (10!))
  map (n => (n, (n.toString
    map (_ asDigit)
    map (_ !)
    reduceLeft (_+_))))
  map (p => (p._1, p._1 == p._2))
  filter (_._2)
  map (_._1)
  reduceLeft (_+_)
)

Go ahead, open an interpreter and try it. The factorial stuff was just for fun -- a simpler definition would work more efficiently, in fact. Now, type the following:

(3 to 3628800).toList

Depending on your Java memory settings, you'll get an Out of Memory error. That's just too much data to store! So, how come you can not only generate that(*), but actually do a bunch of stuff on it?

This magic happens because those map and filter functions are non-strict. A strict function will compute every value and return its result. A non-strict function will return immediately, and each value will only be computed on demand.

As it happens, you are probably familiar with this concept at another level. Take, for instance, the following two declarations:

val ex1 = 2 + 3
def ex2 = { 2 + 3 }

It must be obvious that ex1 == ex2. It should be clear, too, that "2 + 3" was evaluated before its assignment to ex1, but that, in ex2's case, it only gets evaluated when you use ex2 somewhere (like in "ex1 == ex2"). In Scala, another variation exists:

lazy val ex3 = 2 + 3

With that declaration, ex3 will only be evaluated when you use it. For example, when the interpreter calls toString on it to display its result. But try this:

lazy val ex3 = { println("here!"); 2 + 3 }; println("Not there yet")

You'll see that the second println statement is executed before the first one. Only afterwards, when the interpreter calls toString, is the first one executed. For many, if not most, functional languages, that's how ALL expressions work: lazily.

Anyway, back to ex2, please note that ex2 is a strict function, because it computes "2 + 3" before it returns that value. Then again, there isn't really anything you can do with an Integer that does not require evaluation. But think about a List. You do not need to compute the whole list just to call an isEmpty method on it, for instance. Just the head will do.

This is what happens in our example. The expression "3 to (10!)" generates a Range. If you look up Scala's Library documentation on the class Range you'll see that it inherits from Projection, and that Projection has a few "non-strict" methods, and that they return Projections too. Among them are map and filter, the very same methods I'm using in most of that code.

The method reduceLeft, though, is strict. So, what happens is this:

reduceLeft gets the "head" of the projection it receives, forcing map (_._1) to compute it
map gets its value from filter (_._2)
filter now starts iterating on the projection it received from the map above it, searching for the first value satisfying its predicate.
as each element tested by filter, both maps above it, and the range itself, compute the next value
after filter finds its first element, it delivers it, and it goes all the way back to reduceLeft
reduceLeft checks if the tail of the projection it received is empty
and that forces all the maps and filters to act again

Now, as soon as each element gets consumed by reduceLeft, they get disposed by the garbage collector, because they won't be used anymore. The elements still to be consumed haven't been computed yet, so they don't take any memory either. The only elements taking space in memory are the ones in the act of being processed. And, of course, the data structures used by the projection to make its magic possible.

Compare that to this code:

println((3 to (10!)).force
  map (n => (n, (n.toString
    map (_ asDigit)
    map (_ !)
    reduceLeft (_+_))))
  map (p => (p._1, p._1 == p._2))
  filter (_._2)
  map (_._1)
  reduceLeft (_+_)
)

Here, we use the method force to get a strict sequence. Even before the first map is executed, a complete sequence of all numbers between 3 and 3,628,800 will be stored in memory. Or, rather, will fill the heap and cause an exception.

In conclusion, I'd like reinforce that Scala is NOT non-strict by default. It has non-strict collections which can be used within limits. In other functional languages, not even reduceLeft would cause anything to be computed: it would be println causing that. Still, Scala's Projections are powerful tools, which the smart Scala programmer will use wisely to his or her advantage.

(*) I had originally used "3 to 3628800" instead of "(3 to 3628800).toList", which causes out of memory error on Scala 2.7.4 just fine, but Scala 2.8 is a bit smarter about it, and Range's toString method avoids fully evaluating it, for reasons I hope are now obvious. Thus, I changed the example to something which forces a strict evaluation of the range.

What does a Scala program looks like?

2009-04-20T02:00:00.017-03:00

I'm worried.

So, last Friday, as the daylight slowly disappeared, much in the same way and same rate as the people in the immense building that someone somehow thought was fit to be called a workplace -- and, worse yet, be used as such -- I was engaged in a deep conversation about miscellaneous subjects with a colleague. Or, as someone else might rudely put it, I was chit chatting.

At some point, the conversation turned to Java, Ruby on Rails, money, and, finally Scala. My colleague was ignorant of the ways of Rails, and I was telling him how mind blowing it was when it came to creating web sites. I mistakenly mentioned to him having seen a weblog being created in just 25 minutes on a screencast (it's actually 15 minutes -- first screencast here). I urged him to look it up.

Anyway, the conversation briefly turned into Java, and how it came to be because it was basically the only game in town for webapps at the beginning, and how, basically, everything was better than Java. But don't take this too literally -- I was chit chatting... Anyway, the conversation gave a final turn towards Scala at this point.

As my colleague was leaving, he asked me if Scala really was that good, whether it was compiled or interpreted, etc. I told him yes, it was that good, compiled, but with an "interpreter" available, that it produced JAR which could be decompiled by cavaj into readable Java, and then invited him into taking a look into a small program I have to check lottery results.

So, this is a small program I did mainly as a learning experiment. I have one written in Perl, which could have been easily ported to Scala, but I was interested into how a Scala programmer might have gone about it. My present solution is rather functional in style, though I'm considering a couple of case classes for it.

At any rate, I gave a brief overview on some concepts, such as val, def, extending Application, access to Java types and library, explained a few helping functions, and then got to the meat of the program, which I post below.


val prizes = lines.
    dropWhile(!_.startsWith("1 ")).              // Remove header
    map(_.stripLineEnd.split(" ")).              // Tokenize line
    takeWhile(s => isInt(s(0))).                 // Remove trailer
    map(s => readGame(s)).                       // Turn list into tuple
    map(s => (s, ticketPrizes(s._3, tickets))).  // Compute winning tickets
    filter(s => s._2.size > 0)                   // Remove losing games

There's actually a lot of stuff going on there, but the point of that code was figuring out what an elegant Scala program might look like. Now, it does take advantage of some of Scala's power, but there's a lot it doesn't take advantage of. In particular, it doesn't take advantage of anything in Scala's type system or class system.

With that in mind, I started to tell my colleague this was written in a functional style, but you can have OO style as well. Before I finished, though, he inquired about Scala's usual style. Which, finally, led to my present worry.

I do not claim to have seen tons of Scala code, but I have been reading pretty much any blog posting about Scala and I haven't seen any common style.

Now, when Java came to be, some effort went into defining the style a proper Java program ought to be written in. I do claim to have seen a lot of Java code, both ugly and elegant, and all of it looked the same. Whenever a beginner broke with Java style, it came across in stark contrast -- and was a sign of programmer's inexperience.

Now, as for Scala, there's really very little emphasis on style being done. In fact, Scala's emphasis on not dictating how to solve a problem seems to be spilling into not dictating a coding style. And, as all of this went through my head in the space of a few seconds (I hope!), I realized something about Java's emphasis on style. It was comforting.

Let's put that thought on hold for a second, while I digress a bit. I have been programming for 26 years now. I started with BASIC, did some assembler (Z-80 mostly, but also 8080 and 6502), then learned Forth, because a FIG member, and then... C, Logo, MUMPS, LISP, APL, and anything I could put my hands on. I don't recall what languages I have once learned, but every now and then someone will mention an obscure language, such as Oberon, and I'll remember having learned it.

Forth, in particular, is a language whose main intent seems to be modifying the language. Something I did with much gusto. So it's not like I'm a conservative guy when it comes to languages.

Now, back to the comfort of Java's uniform style, the thing is... it's easier on my mind that every piece of Java code I lay my eyes on follows it. And, as I realized that, I was sure as hell that was also the case for the huge mass of average programmers that abound in the Enterprise world. The uniform style makes the code look professional, no matter how messy it actually is.

And, then, back to Scala, I answered my friend: "Scala doesn't have a style right now. It might develop one." Well, actually, it has dozens of style, but you get my drift.

And this, my friends, worries me. I can't see Scala going mainstream if a consistent style doesn't start showing up. Right now, everyone seems to be playing with it, figuring out what works and what doesn't. Scala is so powerful that people are actively trying to push the envelope, to test its limits in concision and expressiveness. It might take a while for its best practices to develop.

Hopefully, it won't be too late.