Parser Surprise

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

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.