Scalable Algorithms 2

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

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

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:

1. reduceLeft gets the "head" of the projection it receives, forcing map (_._1) to compute it
2. map gets its value from filter (_._2)
3. filter now starts iterating on the projection it received from the map above it, searching for the first value satisfying its predicate.
4. as each element tested by filter, both maps above it, and the range itself, compute the next value
5. after filter finds its first element, it delivers it, and it goes all the way back to reduceLeft
6. reduceLeft checks if the tail of the projection it received is empty
7. 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?

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.