Shunting Yard Algorithm

So, the next JUG meeting is introducing the concept of a code kata. One suggestion for an example topic was the Shunting Yard Algorithm. I remember using an HP 42S RPN calculator all through school, and well into my professional life. So, I thought I'd give it a go.

Looking at the Wikipedia entry, they outline an algorithm in pseudo-english-code that can be implemented fairly easily in scala like this:

package org.okcjug.kata.shuntingyard

import scala.util.parsing.combinator._
import scala.util.matching.Regex
import scala.util.parsing.input.CharSequenceReader 
import scala.collection.mutable.Stack
import scala.collection.mutable.Queue

object ShuntingYardWikipediaParser extends RegexParsers {
  
  // the actual algorithm
  def rpn(s: String) = {
    val stack = new Stack[String]
    val queue = new Queue[String]
    
    for (t: String <- parseAll(tokens, new CharSequenceReader(s)).get) {
      
      if (t isNumber) { queue += t }
      if (t isOperator) { 
        while ((!(stack isEmpty) && (stack.top isOperator)) && (
               ((t isLeftAssociative) && (t isLowerOrEqualPrecedenceThan stack.top)) ||
               ((t isRightAssociative) && (t isLowerPrecedenceThan stack.top)))) {
          queue += stack.pop
        }
        stack push t
      }
      if (t isLeftParenthesis) ( stack push t )
      if (t isRightParenthesis) {
        while (!(stack.top isLeftParenthesis)) { queue += stack.pop }
        stack.pop
      }
    }
    while (!(stack isEmpty)) {
      if (stack.top isLeftParenthesis) { error("mismatched parens") }
      queue += stack.pop
    }
    queue.mkString(" ")
  }
  
  // definitions
  val number = """(\d+(\.\d+)?)""".r
  val product = """[\*\/]""".r
  val term = """[\+\-]""".r
  val exponent = """\^""".r
  val negation = """\!""".r
  val leftParens = """\(""".r
  val rightParens = """\)""".r
  val parens = leftParens | rightParens
  val token = number | product | term | exponent | negation | parens ^^ { case s: String => s }
  val tokens = token*
  
  // tricky implicit conversions to make the syntax prettier
  implicit def stringToSmartToken(s: String): SmartToken = { SmartToken(s) }
  case class SmartToken(s: String) {
    implicit def regexMatches(r: Regex): Boolean = { s.matches(r.toString) } 
    def isNumber: Boolean = number
    def isOperator = product || term || exponent || negation
    def isLeftAssociative = isOperator && ( product || term || negation )
    def isRightAssociative = isOperator && exponent
    def isLeftParenthesis: Boolean = leftParens
    def isRightParenthesis: Boolean = rightParens
    def precedence = {
      if (term) 1
      else if (product) 2
      else if (exponent) 3
      else if (negation) 4
      else error("Not an operator")
    }
    def isLowerPrecedenceThan(o: String) = {
      (s precedence) < (o precedence)
    }
    def isLowerOrEqualPrecedenceThan(o: String) = {
      (s precedence) <= (o precedence)
    }
  }
}
 

Note that I ignored the possibility of a function as described in the Wikipedia entry, but added the concept of a unary operator (negation, which I represent as a prefixed "!").

The interesting part of this starts at line 41, which has (through line 47) a bunch of regex definitions of the tokens to be read. Scala can convert a string to a regex using the ".r" method.

Lines 48 - 50 take the regular expressions and combine them into parsers combinators, which produce string tokens.

To make the string tokens syntactically pleasing, we implicitly convert them into a "SmartToken" (lines 53 - 75) which has methods relevant to this particular algorithm. Another interesting thing is line 55, which auto-magically converts a regex (defined in an outer scope) to be treated like a boolean value of that regex applied to the SmartToken's wrapped string. Yee-haw! A few more refactoring passes and it will look like Ruby while still allowing you to argue with the compiler over types.

But, I'll be honest. If I didn't find the Wikipedia description of the algorithm, I probably wouldn't have implemented it in the same way. Also, if I'm going to take the trouble to parse a language, I might as well build an abstract syntax tree.

Here is my elaborate AST model:

package org.okcjug.kata.shuntingyard

import scala.util.parsing.combinator._

abstract class Expression {
  def rpn: List[String]
}

case class NumberExpr(n: String) extends Expression {
  def rpn = List(n)
}

abstract class Operator extends Expression
case class UnaryOp(op: String, e: Expression) extends Operator {
  def rpn = e.rpn ::: List(op)
}
case class BinaryOp(op: String, l: Expression, r: Expression) extends Operator {
  def rpn = l.rpn ::: r.rpn ::: List(op)
}
 

And, I can parse it with this object:

package org.okcjug.kata.shuntingyard

import scala.util.parsing.combinator._
import scala.util.parsing.input.CharSequenceReader

object ShuntingYardParser extends RegexParsers {
   
  def expression(s: String) = parseAll(expr, new CharSequenceReader(s))
  def rpn(e: Expression) = e.rpn.mkString(" ")
  def rpn(s: String) = {
    val e = expression(s)
    if (e.successful) {
      e.get.rpn.mkString(" ")
    }
    else {
      error("Could not parse: " + s)
    }
  }
  
  // parser definitions
  def expr: Parser[Expression] = term 
  def num = """\d+(\.\d+)?""".r | failure("Some number expected")
  def number = num ^^ { case s => NumberExpr(s) }
  def group = "(" ~> expr <~ ")" ^^ { case e => e }
  def singular: Parser[Expression] = number | group | unaryOp | failure("Some expression expected")
  def unaryOp = "!" ~ singular ^^ { case s ~ e => UnaryOp(s, e) }
  def exponent = rightChain(singular, "^")
  def product = leftChain(exponent, "*"|"/")
  def term = leftChain(product, "+"|"-")
  
  // I think this is redundant, but couldn't figure out the chainx1(...) methods in scala's Parser class
  def rightChain(p: Parser[Expression], x: Parser[String]) = {
    ((p ~ x)*) ~ p ^^ {
      case Nil ~ tail => tail
      case rest ~ tail => rest.foldRight(tail) {
        case (p ~ s, z) => BinaryOp(s, p, z)
      }
    }
  }
  def leftChain(p: Parser[Expression], x: Parser[String]) = {
    p ~ ((x ~ p)*) ^^ {
      case head ~ Nil => head
      case head ~ rest => rest.foldLeft(head) {
        case (z, s ~ p) => BinaryOp(s, z, p)
      }
    }
  }

}
 

This code really does all the parsing definitions in lines 21 - 29. We produce an AST that can be output in RPN form.

The really tricky part (for me) about this code was defining it is such a way that we didn't get any recursive parsers as the first (leftmost) term of a sequential combination. This will lead to immediate stack-overflow purgatory as the parser infinitely recurses. Surprisingly, the compiler/type-checker allows it, and I've heard that it might be supported in a future implementation.

Well, do they work?

I guess we should actually test these implementations to see if they do what they are supposed to. Probably better even still to have defined some tests up front to allow the algorithm to be developed under that guidance. Scala has a wonderful testing facility called specs that allows you to specify test in a very intuitive way. Drop a library in my path and make some specifications>:

package org.okcjug.kata.shuntingyard

import org.specs._
import ShuntingYardParser._

object ShuntingYardTest extends Specification {
  
  def passStdTests(parser: { def rpn(s: String): String }) = {
    "be able to add and subtract" in {
      parser.rpn("3+4-2") must beEqual("3 4 + 2 -")
    }
    
    "do unary negation correctly" in {
      parser.rpn("! 3 + 2") must beEqual("3 ! 2 +")
      parser.rpn("!(3 + 2)^2") must beEqual("3 2 + ! 2 ^")
    }
    
    "parse Wikipedia example correctly" in {
      val input = "3 + 4 * 2 / (1-5) ^2 ^3"
      val result = parser.rpn(input)
      result must beEqual("3 4 2 * 1 5 - 2 3 ^ ^ / +")
    }
  }

  "ShuntingYardParser" should { 
    passStdTests(ShuntingYardParser)
  }
  
  "ShuntingYardParser" can { 
    "blow the stack" in {
      val sb = new StringBuffer
      val max = 1000
      for(i <- 1 to max) { sb append "(" }
      sb append "(4-3)"
      for(i <- 1 to max) { sb append "*(4-3))" }
      ShuntingYardParser.rpn(sb.toString) must throwA(new StackOverflowError)
    }
  }
    
  "ShuntingYardWikipediaParser" should {
    passStdTests(ShuntingYardWikipediaParser)
    
    "not blow the stack" in {
      val sb = new StringBuffer
      val max = 1000
      for(i <- 1 to max) { sb append "(" }
      sb append "(4-3)"
      for(i <- 1 to max) { sb append "*(4-3))" }
      ShuntingYardWikipediaParser.rpn(sb.toString) mustNot throwAn(new Exception)
    }
  }
}
 

This spec produces an executable class that produces this output:

Specification "ShuntingYardTest"
  ShuntingYardParser should
  + be able to add and subtract
  + do unary negation correctly
  + parse Wikipedia example correctly

  Total for SUT "ShuntingYardParser":
  Finished in 0 second, 0 ms
  3 examples, 4 expectations, 0 failure, 0 error

  ShuntingYardParser can
  + blow the stack

  Total for SUT "ShuntingYardParser":
  Finished in 0 second, 0 ms
  1 example, 1 expectation, 0 failure, 0 error

  ShuntingYardWikipediaParser should
  + be able to add and subtract
  + do unary negation correctly
  + parse Wikipedia example correctly
  + not blow the stack

  Total for SUT "ShuntingYardWikipediaParser":
  Finished in 0 second, 0 ms
  4 examples, 5 expectations, 0 failure, 0 error

Total for specification "ShuntingYardTest":
Finished in 0 second, 563 ms
8 examples, 10 expectations, 0 failure, 0 error

Notice that I'm testing both implementations of the parser with the same code, except for one test (blow the stack). This is because the AST version will blow up when it encounters some input that nests thousands of levels deep. I verify this and also verify that is doesn't affect the Wikipedia version. I'm am deeply embarrassed that a Wikipedia algorithm is more feature-full than my home-grown version.

What next?

Well, we could actually calculate the results of the input from either the AST or the rpn input. Both of these would be almost trivial to implement. We could randomly generate input strings, feed them into both parsers and compare the results. It is nice to have Scala's parser combinators as a tool in your belt. There is a dead zone between what can/should be done with one-off regular expressions, and generating a full-fledged language with an external tool (JavaCC, ANTLR, etc). Another option for these situations is to use an internal DSL (like the specs library I used). But, that's a topic for another post...

Disjoint Bounded Views - Redux

I cleaned up my previous post on "stuttering-or". The import would now look like this:

package org.okcjug.imports

class DisjointBoundedView[A,B](val a: Option[A], val b: Option[B])

object DisjointBoundedView {
  // namespace pollution?  Maybe use "||" or "OrType"
  type or[A,B] = DisjointBoundedView[A,B]
  
  // convenience of definition functions
  private def da[A,B](a: A): or[A,B] = { new DisjointBoundedView(Some(a),None) }
  private def db[A,B](b: B): or[A,B] = { new DisjointBoundedView(None,Some(b)) }
  private def na[A,B](n: Nothing): or[A,B] = { new DisjointBoundedView(None, None) }
  
  // implicit defs - stuttering-or
  implicit def noneToOr2[A,B](n: Nothing): or[A,B] =
    { na(n) }
  implicit def aToOr2[A,B](a: A): or[A,B] =
    { da(a) }
  implicit def bToOr2[A,B](b: B): or[A,B] =
    { db(b) }
  implicit def aToOr3[A,B,C](a: A): or[or[A,B],C] =
    { da(da(a)) }
  implicit def bToOr3[A,B,C](b: B): or[or[A,B],C] =
    { da(db(b)) }
  implicit def aToOr4[A,B,C,D](a: A): or[or[or[A,B],C],D] =
    { da(da(da(a))) }
  implicit def bToOr4[A,B,C,D](b: B): or[or[or[A,B],C],D] =
    { da(da(db(b))) }
  implicit def aToOr5[A,B,C,D,E](a: A): or[or[or[or[A,B],C],D],E] =
    { da(da(da(da(a)))) }
  implicit def bToOr5[A,B,C,D,E](b: B): or[or[or[or[A,B],C],D],E] =
    { da(da(da(db(b)))) }
  // more? ...

}
 

Calling code would look like this:

package org.okcjug.test

import org.okcjug.imports.DisjointBoundedView._

class Foo {

  def bar[T <% Int or String or Double](t: Option[T]) = {
    t match {
      case Some(x: Int) => println("processing Int: " + x)
      case Some(x: String) => println("processing String: " + x)
      case Some(x: Double) => println("processing Double: " + x)
      case None => println("empty and I don't care the type")
    }
  }
  
  def baz[T <% String or Int](t: List[T]) = {
    for (x <- t) x match {
      case x: String => println("String list item: " + x)
      case x: Int => println("Int list item: " + x)
    }
  }
}

object Foo extends Application {
  
  val f = new Foo
  
  f.bar(None)
  f.bar(Some(1))
  f.bar(Some("blah"))
  f.bar(Some(3.45))
  // f.bar(Some(Some(2))) // compiler error
  // f.bar(Some(Set("x", "y"))) // compiler error
  
  f.baz(List(1,1,2,3,5,8,13))
  f.baz(List("boogie", "woogie"))
  // f.baz(List(3.4, 3.14)) // compiler error
  // f.baz(List(1,"one")) // compiler error
  // f.baz(Some(1)) // compiler error
}
 

The only difference is that we now don't require clarifying the type for a None, and the class name more accurately reflects what it does.

UPDATE: Per Ittay's suggestion below, I've updated the implementation to use Either as the backing class (shown below). This simplifies the code and allows extraction of values from the composite type via pattern matching. Also, it can no longer accurately be described as "stuttering-or".

package org.okcjug.imports

object DisjointBoundedView { 
  // namespace pollution?  Maybe use "||" or "OrType"  
  type or[A,B] = Either[A,B]  
    
  // implicit defs 
  implicit def l[T](t: T) = Left(t)
  implicit def r[T](t: T) = Right(t)
  implicit def ll[T](t: T) = Left(Left(t))
  implicit def lr[T](t: T) = Left(Right(t))
  implicit def lll[T](t: T) = Left(Left(Left(t)))  
  implicit def llr[T](t: T) = Left(Left(Right(t))) 
  implicit def llll[T](t: T) = Left(Left(Left(Left(t))))  
  implicit def lllr[T](t: T) = Left(Left(Left(Right(t))))  
  // more? ...  
    
}

OKCJUG Slides

Although they may not make much sense without the code and explanation that goes along with them, I've posted the slides used in my JUG presentation yesterday.

Stuttering Or

So I read both Jim McBeath and Michid's blog entries on implementing polymorphism using implicit conversions, especially where it would be otherwise difficult because of type erasure. But, I was uneasy with their approaches. Jim's required implementing redundant classes in a heirarchy and Michid's seemed comlex. Both required that you explicity implement an implicit function for each disjoint type you want one of your method's parameters to be called as. And, even worse, the calling code has to remember to import the implicit functions for this to work.

I call my attempt at a better version the "stuttering-or" method, and it looks like this:

package org.okcjug.typeerasure.arrrgh.util

case class DisjointType[A,B](val a: Option[A], val b: Option[B])

object DisjointType {
  type or[A,B] = DisjointType[A,B] // who wants to type "DisjointType" all the time?
  
  // convenience of definition functions
  private def da[A,B](a: A): or[A,B] = { DisjointType(Some(a),None) }
  private def db[A,B](b: B): or[A,B] = { DisjointType(None,Some(b)) }
  
  // implicit defs - stuttering-or
  implicit def aToDisjointType2[A,B](a: A): or[A,B] =
    { da(a) }
  implicit def bToDisjointType2[A,B](b: B): or[A,B] =
    { db(b) }
  implicit def aToDisjointType3[A,B,C](a: A): or[or[A,B],C] =
    { da(da(a)) }
  implicit def bToDisjointType3[A,B,C](b: B): or[or[A,B],C] =
    { da(db(b)) }
  implicit def aToDisjointType4[A,B,C,D](a: A): or[or[or[A,B],C],D] =
    { da(da(da(a))) }
  implicit def bToDisjointType4[A,B,C,D](b: B): or[or[or[A,B],C],D] =
    { da(da(db(b))) }
  implicit def aToDisjointType5[A,B,C,D,E](a: A): or[or[or[or[A,B],C],D],E] =
    { da(da(da(da(a)))) }
  implicit def bToDisjointType5[A,B,C,D,E](b: B): or[or[or[or[A,B],C],D],E] =
    { da(da(da(db(b)))) }

}
 

The "magic" part of this is that it allows infix type notation to represent "Type1 or Type2" as "DisjointType[Type1,Type2]". Then, the implicit defs allow the component types to be represented in a type view. This guards the methods that define it to only accept members of the component types. Note that it is up to the method implementer to cover all the possible cases as the type system will not help you there.

Defining the methods is something like this:

package org.okcjug.typeerasure.arrrgh.work

import org.okcjug.typeerasure.arrrgh.util.DisjointType._

class Foo {

  def erasureMethod[T <% Int or String or Double](t: Option[T]) = {
    t match {
      case Some(x: Int) => println("processing Int: " + x)
      case Some(x: String) => println("processing String: " + x)
      case Some(x: Double) => println("processing Double: " + x)
      case None => println("empty and I don't care the type")
    }
  }
  
  def erasureMethod2[T <% String or Int](lt: List[T]) = {
    for (x <- lt) x match {
      case x: String => println("String list item: " + x)
      case x: Int => println("Int list item: " + x)
    }
  }
  
}
 

And, the calling code looks like this:

package org.okcjug.typeerasure.arrrgh

import org.okcjug.typeerasure.arrrgh.work.Foo
import org.okcjug.typeerasure.arrrgh.util.DisjointType._

object App extends Application {

  val f = new Foo()
  
  f.erasureMethod(Some("blah"))
  // f.erasureMethod(None) // compiler error
  f.erasureMethod(None.asInstanceOf[Option[String]]) // ok
  f.erasureMethod(Some(42))
  // f.erasureMethod(Some(List("b"))) compiler error
  
  f.erasureMethod2(List("a","b","c"))
  f.erasureMethod2(List(5,4,3,2))
  // f.erasureMethod2(List(4.3)) compiler error

}
 

So, what does this get me? Well, implementing the code is fairly straightforward, just using a "Type1 or Type2 or Type3 ..." construct for the disjoint types (up to 5 in the given code). Also, discerning the specific type within the polymorphic method for purposes of dispatch is done using the standard "match" keyword.

What I don't like about my solution is that the calling code must import the implicit methods (here: org.okcjug.typeerasure.arrrgh.util.DisjointType._). Each of the the compared methods from the top of this article also required importing the implicit methods. However, I think my approach shows more promise because the implicit defs that need to be imported are not specific to the pseudo-polymorphic methods I'm implementing. In fact, the content of this import is suitable to be included in the Predef object.

Maybe I'll poke around the scala mailing list and see if any library maintainers want to oblige me...

Lazy initialization of blog posts

Well, it has been a couple of years since my last post and we did not get the opportunity to use Scala at work. I lost interest and started chasing other shiny, twinkly things.

But, I did get a chance to give a presentation on Scala at the local JUG. I'll post slides when it is done if I don't completely embarrass myself.

More Ant builds

Since the Scala compiler is a pretty heavy process to run in buildfiles where it is not needed, I've nested it within a conditional to only run when the Scala library is in the classpath.

My new build macro looks like this:

    <macrodef name="build">
        <attribute name="srcdir"/>
        <attribute name="builddir"/>
        <sequential>
            <mkdir dir="@{builddir}" />
            <javac srcdir="@{srcdir}" 
                destdir="@{builddir}"
                source="${compile.source}"
                target="${compile.target}"
                deprecation="${compile.deprecation}"
                debug="${compile.debug}">
                <classpath refid="classpath" />
            </javac>
            
            <if>
                <available classpathref="classpath" classname="scala.ScalaObject"/>
                <then>
                    <scalac srcdir="@{srcdir}"
                                    destdir="@{builddir}"
                                    classpathref="classpath" />   
                </then>   
            </if>   

            <copy todir="@{builddir}">
                <fileset dir="@{srcdir}">
                    <include name="**/*"/>
                    <exclude name="**/*.java" />
                    <exclude name="**/*.scala" />   
                    <exclude name="**/.svn/*" />
                </fileset>
            </copy>
        </sequential>
    </macrodef>

We also need to define the scalac task like so:

    <taskdef resource="scala/tools/ant/antlib.xml">
        <classpath>
            <pathelement location="ant/jars/scala-compiler.jar" />    
        </classpath>
    </taskdef>

Ant builds

We have a standardized ant build file(s) at work. There is usually not much thinking needed other than naming the project. If we used Scala regularly, we would need to incorporate the <scalac ... /> target into our buildfiles in such a way that it would transparently build Scala code if it existed. It is also important that the build succeed in one pass with no manual intervention for the CI server to perform its automated builds.

How can we structure our code and build files to satisfy this requirement? Scala code and freely call Java code (and vice-versa). In our build files we need to call both javac and scalac in some particular order. If we call javac first, then code like following will fail because the java compiler cannot yet see the scala class when it executes.

--- Foo.java ---
public class Foo {
 private Bar bar;
 // ...
}

--- Bar.scala ---
class Bar {
 // ...
}

Of course, you have the reverse situation if you call scalac first, with same-project Java code invisible to the Scala compiler. A post to the Scala mailing list brought the following suggestion:

--- Foo.java ---
public class Foo {
    private Bar bar;
    // ...
}

--- Bar.java ---
public interface Bar {
    // ...
}

--- BarImpl.scala ---
class BarImpl() extends Bar {
    // ...
}

This allows us to statically reference a Java interface from Java code and to implement the class in Scala. Instances can be created at runtime, using the container (EJB, Spring, or JSF) or by using

Class.forName("package.BarImpl").newInstance();

Of course, we can still easily reference our Java object from Scala.

--- Baz.scala ---
class Baz {
    def doSomething(foo: Foo): Unit = {
        // do something with our Java object Foo
    }
    def doSomethingElse(): Unit = {
        // instantiate our own Java-defined object
        foo = new Foo();
    }
}

So, the plan is to require Java interfaces for any Scala objects that are referenced from Java code. Of course, many of the advantages from Scala come from using its type system and will only show if whole layers of an application are implemented in Scala. Luckily, most of our layers are hidden behind interfaces anyway.

Next I'd like to experiment with different types of container-instantiation of Scala classes.