I’m foolishly trying to write a javac annotation processor in Scala. This has already been a road fraught with gratuitous obstacles, but the latest wrinkle has driven me to vent in public.

When I run my annotation processor thusly:

javac -processor FooProcessor -processorpath fooproc/classes:blah/scala-library.jar SomeFile.java

I get “java.lang.IllegalStateException: zip file closed” when my processor tries to load Scala classes. But if I unpack scala-library.jar into fooproc/classes then it works. Joy! Somehow the scala-library.jar file causes javac to choke.

I of course tried repacking the jar file, in case perhaps something in the stock scala-library.jar was weird, but using the repacked version still failed with “zip file closed.” What’s even more awesome is that javac 1.6 does not have a problem with scala-library.jar, only javac 1.7.

Problem 064 (source):

object Euler064 extends EulerApp {
  case class Root (root :Int, add :Int, div :Int) {
    def expand = {
      val term = ((math.sqrt(root) + add)/div).toInt
      val nadd = term*div - add
      (term, Root(root, nadd, (root - nadd*nadd)/div))
    }
    override def toString = "(√" + root + "+" + add + ")/" + div
  }
  def expansion (terms :List[Int], roots :List[Root]) :List[Int] = {
    val (term, root) = roots.head.expand
    if (root.div == 0 || roots.contains(root)) term :: terms
    else expansion(term :: terms, root :: roots)
  }
  def answer = 1 to 10000 map(n => expansion(Nil, Root(n, 0, 1)::Nil).length) count(_%2==0)
}

Here we have a nice little case class to represent a single step in the infinite expansion. The process of generating the next expansion could be done purely with simple arithmetic, but I’m lazy, so I just use math.sqrt to obtain the non-fractional part. I don’t actually need to keep track of the terms to obtain the solution, but it was handy to have when I was validating the solution, so I kept it around. Same goes for toString. I just love that little root sign!

Problem 063 (source):

object Euler063 extends EulerApp {
  def pows (n :Int) = Stream.from(1) prefixLength(p => BigInt(n).pow(p).toString.length == p)
  def answer = 1 to 9 map(pows) sum
}

The main observation here is that the number of digits of a^x, for a ≥ 10, is guaranteed to exceed x. So we can restrict ourselves to looking only at the numbers from 1 to 9. Furthermore, the number of digits of a^x, for 1 ≤ a ≤ 9, will equal x up to some maximum x, and then be less than x for all higher x. That enough xs for you?

Problem 062 (source):

object Euler062 extends EulerApp {
  def search (n :Long, cubes :Map[Long,List[Long]]) :Long = {
    val cube = n*n*n
    val key = cube.toString.sortWith(_>_).toLong
    val perms = cube :: cubes.getOrElse(key, Nil)
    if (perms.length == 5) perms.last
    else search(n+1, cubes + (key -> perms))
  }
  def answer = search(1, Map())
}

I was originally using the dreaded mutation here, and then realized that I could easily rewrite the code to use an immutable map, making it about 10% shorter and about 10% slower. Of course, the garbage collector gets a great big free ride when the program terminates and it most certainly hasn’t collected any of the intermediate map bits.

The algorithm is pretty straightforward, iterate up the cubes, collecting them into lists of cubes which permute to one another (I bet there’s some fancy math term for lists that are equivalent up to permutation). When we find one with five permutations, we’re done. We’re sort of cheating here because it would be possible to find a cube that permutes to four other seen cubes, but also permutes to as yet unseen cubes, and the problem asks for the smallest cube for which exactly five permutations of its digits are a cube. Fortunately, we find the fifth permutation of the correct cube before we find the fifth permutation of any cube that has more permutations, so we’re in the clear.

Aside from describing how Scala structural types are implemented (via reflection), this paper shows that such an approach isn’t wildly slower than an approach that generates shim classes on the fly. Certainly it’s not ideal for the programmer to have to remember that some kinds of method calls are three times slower than others, but the shim class approach is not without drawbacks either. In addition to the problem of the type of this, it has performance related problems as well, as discussed by Charles Nutter of JRuby fame.

Two interesting developments may change the landscape here: interface injection, which would solve the problem outright, but has low odds of ever seeing the light of day in a shipping JVM, and invokedynamic which could make a reflection-like approach more performant, and should ship with Java 7 (assuming Java 7 ever ships).

Source: ACM PDF

I backed into type classes via Scala’s poor man implementation thereof. Thus it is illuminating to see them formulated as ML modules, even though I’m not particularly familiar with ML modules either.

Given the global nature of Haskell’s type classes, a limitation remedied by both this work and Scala’s implicits, I wonder what’s so poor about Scala’s approach. Are there things that are expressible with “real” type classes that are not expressible with implicits? Or maybe it’s just a matter of preserving the holy grail of perfect type inference.

Source: ACM PDF

I am a heavy user of virtual desktops. I generally have a couple of shell windows, an emacs window, possibly a browser, and whatever target program I’m working on, on each of a few virtual desktops. When I’m interrupted from one project, I flip to the next virtual desktop, open a shell window, open an emacs window and start hacking away on said interruption. Often the stack will get three or four virtual desktops deep, and I’ll find myself flipping back and forth between the various in-progress projects.

I generally try to open new files from within emacs, rather than from a terminal, but occasionally the terminal is more expedient, except that it results in an entirely new emacs process and window being created on that virtual desktop. The additional virtual memory consumption isn’t a big deal, but the fact that it screws up my ability to alt-tab between windows is a major annoyance. Plus my brain naturally assumes there’s one emacs process on each virtual desktop and that process contains all the buffers that have been opened thereon. So when I go to switch to a buffer that I know is open only to discover that it’s in a different emacs process whose window is hidden behind the one I’m currently using, it harshes my mellow.

I have played with emacsclient a bit in the past, but it assumes that you use one emacs to rule them all. So if I have an emacs open on virtual desktop one, and run emacsclient on virtual desktop three, it will happily open the requested file on the completely invisible and completely inappropriate emacs instance on virtual desktop one. Not useful. Further, it assumes that you’re the sort of developer that started emacs back in the late seventies and have kept that instance running ever since. So if you run emacsclient when there’s no emacs instance running, it happily spits out seven or eight lines of error message and does nothing especially useful.

For whatever reason (probably me subconsciously avoiding the tedious work that I have to get done before the end of this weekend), the camel’s back broke today (even though this has been bothering me since I started using FVWM in like 1995). I scoured the interwebs for a way to find out what virtual desktop was active (wmctrl FTW) and wrote the necessary scripts and elisp to cause “emacs filename” executed on the command line to always do the Right Thing. If there’s no emacs instance on the active virtual desktop, one is started with the requested file(s). If an instance is running on that virtual desktop, it is instructed to open the requested file(s). And as an added bonus, since I use “emacs -nw” for $EDITOR jobs, if the script sees -nw on the command line, it just forks off a whole new emacs with the supplied args, knowing that it will remain safely ensconced in the terminal.

If you too are an emacs user whose workflow resembles mine, feel free to reap the fruits of my labor. Add the following to your .emacs file:

(defun cur-desk ()
  "Returns the numeric identifer of the current desktop."
  (replace-regexp-in-string "\\(^[[:space:]\n]*\\|[[:space:]\n]*$\\)" ""
    (shell-command-to-string "wmctrl -d | grep '\*' | awk '{ print $1 }'"))
  )
(if (string= "x" window-system)
    (progn (setq server-name (format "server%s" (cur-desk)))
           (server-start)))

and create a shell script in your favorite location with the following contents:

#!/bin/sh

EMACS=/usr/bin/emacs

# if we have -nw on the command line, invoke a separate emacs instance
for ARG in $*; do
    if [ $ARG = "-nw" ]; then
        exec $EMACS $*
    fi
done

# otherwise send the file(s) to the emacs instance on this virtual desktop
CURDESK=`wmctrl -d | grep '\*' | awk '{ print $1 }'`
emacsclient -s "server$CURDESK" --no-wait $* > /dev/null 2>&1
if [ $? != 0 ]; then
    # no instance running on this virtual desktop, so start one
    $EMACS $* &
fi

There are probably better ways to accomplish both of the above bits of code. My bash and elisp skills have both perpetually lingered in the “good enough to get the job done” realm.

Side note: I can’t believe the SyntaxHighlighter WordPress plugin doesn’t have support for Lisp. They support actionscript3, bash, coldfusion, cpp, csharp, css, delphi, erlang, fsharp, diff, groovy, javascript, java, javafx, matlab, obj-c, perl, php, text, powershell, python, ruby, scala, sql, vb, xml, and have the audacity to claim that “most widely used languages are supported”. Perhaps Lisp no longer rates as widely used. Ah well, I just used the Ruby highlighter. Ruby is just an accessible Lisp right?

Problem 061:

object Euler61 extends EulerApp {
  case class Pn (card :Int, value :Int) {
    def valid = (value < 10000) && (value > 999)
    def ab = value / 100
    def cd = value % 100
  }

  def tri (n :Int) = Pn(3, n*(n+1)/2)
  def square (n :Int) = Pn(4, n*n)
  def pent (n :Int) = Pn(5, n*(3*n-1)/2)
  def hex (n :Int) = Pn(6, n*(2*n-1))
  def hept (n :Int) = Pn(7, n*(5*n-3)/2)
  def oct (n :Int) = Pn(8, n*(3*n-2))
  def gen (max :Int)(gen :(Int) => Pn) = (1 to max) map(gen) filter(_.valid)
  val nums = List(square _, pent _, hex _, hept _, oct _) flatMap(gen(100))

  def search (nums :Seq[Pn], set :List[Pn]) :Option[List[Pn]] = {
    if (!nums.isEmpty) (for (n <- nums; if (n.ab == set.last.cd);
                             s <- search(nums filter(_.card != n.card), set :+ n))
                        yield s) headOption
    else if (set.last.cd == set.head.ab) Some(set)
    else None
  }
  def sets = for (n <- gen(150)(tri); s <- search(nums, n::Nil)) yield s
  def answer = (sets head) map(_.value) sum
}

I model a polygonal number with a case class to track it’s value and cardinality. Since I care about four-digitality and two digit prefixes and suffixes, those fit nicely as methods on the class. The main search proceeds by starting with a given triangle number (since all sets must have one triangular element), and then looks for a number that matches the suffix of said number. If one is found, it is added to the ordered set, all other numbers with the same cardinality are dropped from the candidates list, and a new number is sought that matches the suffix of the value just added.

If we match a number for each cardinality, then we’ll finally end up in the search procedure with an empty candidates list, in which case we check whether the last number in the ordered set matches the first.

Functional programming comment: when I first wrote this, I was using Nil to indicate a non-match, and had a few find(Nil.!=) calls sprinkled around to find matching elements. That smelled suspiciously like using null, so I decided to be a good functional programmer and use Option. However, this left me in situations where I’d have a List[Option[Pn]] and I’d need the first non-None element. I know that I can take such a list and do list flatMap(x => x) head but that seems insufficiently scrutable to people not familiar with the idiom.

This motivated me to switch to for-comprehensions. Instead of writing:

nums filter(_.ab == set.last.cd) map(n => search(...)) flatMap(s => s) headOption

I use what you see above:

(for (n <- nums; if (n.ab == set.last.cd); s <- search(...)) yield s) headOption

The for-comprehension turns out to be a little shorter, a lot easier to line-wrap (if needed), and I think probably slightly more comprehensible. You still have to deduce that Option behaves like a zero-or-one element list when used in a for-comprehension, but that seems more intuitive than figuring out that List(Some(1), None, Some(2)) flatMap(x => x) gives you List(1, 2).