MarbleMice.com

I lurk on a couple the scala mailing list mostly to keep up with the latest going ons as well as absorb some of the culture/idioms associated with scala. The scala IDE issue often comes up. A poster on the mailing list (Ray) put together an article on setting up emacs for use with scala. Here’s the link.

A Little code dump… An imaginary number class for scala, written in a functional style.

case class Im(val re:Double, val im:Double)
{
  def +(rhs:Im) = Im(re+rhs.re, im+rhs.im)
  def -(rhs:Im) = Im(re-rhs.re, im-rhs.im)

  def *(rhs:Im) = {
    val re_part = rhs.re*re - rhs.im*im
    val im_part = rhs.im*re + rhs.re*im
    Im(re_part, im_part)
  }

  def /(rhs:Im) = {
    val denom = rhs.re*rhs.re + rhs.im*rhs.im
    val re_part = (re*rhs.re+ im*rhs.im)/ denom
    val im_part = (im*rhs.re - re*rhs.im) / denom

    Im(re_part, im_part)
  }

  def *(factor:Double) = Im(re*factor, im*factor)
  def /(factor:Double) = Im(re/factor, im/factor)

  def conjugate = new Im(re, -im)
  def magnitude = Math.sqrt(magnitudeSqrd)
  def magnitudeSqrd = re*re +im*im
  def inverse = conjugate/ magnitudeSqrd
}

And here is all the tests for it using scalacheck.

import org.scalacheck._

object imaginarySpecification extends Properties("Im (imaginary numbers)")  {
  implicit def arbPoint:Arbitrary[Im] = Arbitrary {
    for{
      re <- Gen.choose(-10000.0, 10000.0)
      im <- Gen.choose(-10000.0, 10000.0)
    } yield new Im(re, im)
  } 

  specify("complex conjugate", (i:Im) => i.conjugate == new Im(i.re, -i.im) )
  specify("Add", (i1:Im, i2:Im) => i1+i2==new Im(i1.re+i2.re, i1.im+i2.im) )
  specify("Sub", (i1:Im, i2:Im) => i1-i2==new Im(i1.re-i2.re, i1.im-i2.im) )
  specify("division", (i1:Im, i2:Im) => {
    val denom = i2.re*i2.re + i2.im*i2.im
    i1/i2 == (i1*i2.conjugate)/denom
  })

  specify("mult by factor", (i1:Im, f:Double)=>  i1*f==new Im(i1.re*f, i1.im*f) )
  specify("divide by factor", (i1:Im, f:Double)=>  i1/f==new Im(i1.re/f, i1.im/f) )
  specify("magnitude", (i:Im) => i.magnitude == Math.sqrt(i.re*i.re + i.im*i.im))

  // Here are a seies of identities that hold for complex numbers and conjugates. Should give the
  // Im class a really good work out. Taken from http://en.wikipedia.org/wiki/Complex_number
  specify("conjugate adding", (i1:Im, i2:Im) => (i1+i2).conjugate== i1.conjugate + i2.conjugate )
  specify("conjugate multiplication", (i1:Im, i2:Im) => (i1*i2).conjugate == i1.conjugate * i2.conjugate )
  specify("conjugate division", (i1:Im, i2:Im) => (i1/i2).conjugate == i1.conjugate / i2.conjugate )
  specify("conjugate reversable", (i:Im) => i == i.conjugate.conjugate )
  specify("Real == half i + conjugate", (i:Im) => i.re == 0.5*(i + i.conjugate).re )
  specify("Im == 1/2i(i-conjugate)", (i:Im) => i.im == ((i - i.conjugate)/Im(0,2)).re)
  specify("magnitudes the same", (i:Im) => i.magnitude == i.conjugate.magnitude )
  specify("magnitude sqrd", (i:Im) => i.magnitudeSqrd == (i*i.conjugate).re)
}

Sometime ago when I was first began writing SpiderSynth I took a look at JFreeChart with the aim of using to display various waveforms and for the frequency and amplitude editors. I struggled to say the least and ended up coding my own. They never looked as good but I managed to convince myself that JFreeChart was a dependency I didn’t want and was not suited to what I wanted to do.

Rewriting SpiderSynth in scala has given me the change to review these conclusions with a lot more experience of how things work in Java land. JFreeChart not having a great deal of free documentation really steepens the learning curve when you are new to Java and not used to rummaging around JavaDoc documentation. A year on and I find JFreeChart can be made to do what I want it to do. No surprise there really! Experience seems to count.

To test out JFreeChart I wrote a small example program in scala that lets you click on the nodes of a line and move them around. It may be possible to write this a better way and I will go over the code again when I extend it to behave the way I want for spidersynth.

As I could find no examples out on the web using JFreeChart in this way I decided to publish this example. Any comments welcome but keep in mind it is really a quickly put together prototype bit of code.

// JFreeChart Example 

import org.jfree.data.general._
import org.jfree.data._
import org.jfree.data.xy._
import org.jfree.chart._
import org.jfree.chart.plot._
import org.jfree.chart.renderer._
import org.jfree.chart.renderer.category._
import org.jfree.chart.renderer.xy._
import org.jfree.ui._
import org.jfree.chart._
import org.jfree.chart.entity._

import javax.swing.JFrame
import javax.swing.JPanel

import java.awt.event._
import java.awt.Color

// Assume you have the two jars in the same directory as you source code file
// compile: scalac ChartExample.scala -cp "jcommon-1.0.14.jar;jfreechart-1.0.11.jar;."
// run:     scala -cp "jfreechart-1.0.11.jar;jcommon-1.0.14.jar;." Main

class DraggingModel(panel:ChartPanel, series:XYSeries) extends MouseMotionAdapter {
  var selected:Option[XYDataItem] = null

  override
  def mouseMoved(e:MouseEvent) = {
    val entity = panel.getEntityForPoint(e.getX, e.getY)
    selected = if(entity.isInstanceOf[XYItemEntity]) Some(series.getDataItem(entity.asInstanceOf[XYItemEntity].getItem))
               else None
  }

  override def mouseDragged(e:MouseEvent) = {
    selected match {
    case Some(_) => adjustEntityPositionToMouse(e.getX, e.getY)
    case None    => ()
    }
  }

  def adjustEntityPositionToMouse(x:Int, y:Int) = {
    val (mx,my) = convertToNormalisedCoords(x,y)
    val chart = panel.getChart
    val plot  = chart.getXYPlot
    val range = plot.getDomainAxis.getRange  // x-axis
    val domain = plot.getRangeAxis.getRange

    series.remove(selected.get.getX)
    val item = new XYDataItem(range.getLowerBound +mx*range.getLength, domain.getLowerBound+my*domain.getLength)
    series.add(item, true) // true will notify listeners and cause a repaint
    selected = Some(item)
  }

  private def convertToNormalisedCoords(x:Int, y:Int) = {
      val dataArea = panel.getScreenDataArea
      val dx = dataArea.getMaxX - dataArea.getMinX
      val dy = dataArea.getMaxY - dataArea.getMinY

      val normalX = (x-dataArea.getMinX)/dx
      val normalY = 1.0-(y-dataArea.getMinY)/dy
      (normalX, normalY)
  }
}

object Main {
  def main(args:Array[String]) = {
    // Create a simple line chart
    val series = new XYSeries("A Line", true, true);
    for(x <-10 to 30) series.add(x, 5.0+Math.random * 3)

    val dataset = new XYSeriesCollection(series);

    val chart = ChartFactory.createXYLineChart( "Test",
            "X",
            "Y",
            dataset,
            PlotOrientation.VERTICAL,
            false,                    // include legend
            false,                    // tooltips
            false                     // urls
    );				

    // Make it look nice
    val plot = chart.getPlot().asInstanceOf[XYPlot];
    plot.setBackgroundPaint(Color.lightGray);
    plot.setAxisOffset(new RectangleInsets(5.0, 5.0, 5.0, 5.0));
    plot.setDomainGridlinePaint(Color.white);
    plot.setRangeGridlinePaint(Color.white);

    val renderer = plot.getRenderer().asInstanceOf[XYLineAndShapeRenderer];
    renderer.setShapesVisible(true);
    renderer.setShapesFilled(true);

    // Set up swing with our chart
		val frame = new JFrame("Hello Moving World")
		frame.setDefaultCloseOperation( JFrame.EXIT_ON_CLOSE )

		frame.setSize(640,420)
    val chartPanel = new ChartPanel(chart)
		chartPanel.setMouseZoomable(false)

    val draggingModel = new DraggingModel(chartPanel, series)
		chartPanel.addMouseMotionListener(draggingModel)

		frame.add(chartPanel)
		frame.pack()
		frame.setVisible(true)
  }
}

Here is a small example of using JFreeChart from Scala. Ok it looks like Java code really but that seems to be what happens in small example code using Java libraries. I assume you have both the JFreeChart and the JCommon jar in the same directory as the example code file.

In the comments in the code I show how to add jars to you classpath, remember to put the “.” in there – I kept forgetting and those little pesky compile or run time errors kept appearing…

Enjoy

// JFreeChart Example

import org.jfree.chart.ChartFactory;
import org.jfree.chart.ChartUtilities;
import org.jfree.chart.JFreeChart;
import org.jfree.data.general._
import org.jfree.data._
import org.jfree.chart.ChartPanel
import org.jfree.chart.plot.PiePlot

import javax.swing.JFrame
import javax.swing.JPanel

// compile: scalac ChartExample.scala -cp "jcommon-1.0.14.jar;jfreechart-1.0.11.jar;."
// run:     scala -cp "jfreechart-1.0.11.jar;jcommon-1.0.14.jar;." Main

object Main {
  def main(args:Array[String]) = {
    // Create a simple pie chart
    var pieDataset:DefaultPieDataset = new DefaultPieDataset();
    pieDataset.setValue("A", 75);
    pieDataset.setValue("B", 10);
    pieDataset.setValue("C", 10);
    pieDataset.setValue("D", 5);
    val chart = ChartFactory.createPieChart(
           "Hello World",
            pieDataset,
            true,
            true,
            false);

		println("Hello world");

		val frame = new JFrame("Hello Pie World")
		frame.setDefaultCloseOperation( JFrame.EXIT_ON_CLOSE )

		frame.setSize(640,420)
		frame.add( new ChartPanel(chart) )
		frame.pack()
		frame.setVisible(true)
  }
}

A few weeks ago I took a look at combinator parsers, I figured it would make an interesting blog entry. In this entry I will take a look at how to create a simple calculator parser and generate an abstract syntax tree from it, using this we will evaluate the expression to get the value.

Introduction

Combinator parsers a domain speficic language used to create a parsers and lexers using the same language that you are using for the rest of the program. They differ from Lex and Antlr as these tools use a different language and an extra tool, hence build stage, to generate code in the language you are using. Parser combinators are not unique to Scala as most functional programming languages have an implementation as does C++. Generally you do not get such good debugging facilities.

Documentation wise some examples exist and there is a chapter in this book about them, overall the book is quite good. I have noticed a number of blog entries on the topic recently. Google is your friend here.

We are going to develop a calculator that accepts add, subtract, multiply and divide operators on decimal numbers. We won’t deal with the unary minus problem so “-2″ will not be a valid input, unary operators are easy to add in but I wanted the example to be as small as possible.

The Skeleton Parser

As it is the classic example I will give the just give the expression

def expr:Parser[Any]   = term~rep("+"~term | "-"~term)
def term:Parser[Any]   = factor~rep("*"~factor | "/"~factor)
def factor:Parser[Any] = (
    decimalNumber
    | "("~>expr<~")"
    )

The parser accepts a term followed by zero or more terms seperated with a + or – symbol. A term is a factor followed by zero or more factors seperated by a * or / symbol, finally a factor is either a number or some brackets with an expression enclosed in them.

The ~ is a scala operator that means sequential composition so “+”~term means “+” followed by a term.
The | is a scala operator means or – rather obvious really.
Finally the ~> and <~ are again sequential operators but the tell us to ignore any nodes to theleft or right of the operator. In our case it says we are only interested in the expr part.

AST Construction

Before we get onto adding actions to our simple parser we need to create the objects for our tree. Here is the code.

case class Node
case class Add(lhs:Node, rhs:Node)  extends Node
case class Sub(lhs:Node, rhs:Node)  extends Node
case class Div(lhs:Node, rhs:Node)  extends Node
case class Mult(lhs:Node, rhs:Node) extends Node
case class Num(d:Double)            extends Node

Define our base class and then create all out binary operation and our Num class. For example “6+2*3″ would be turned into the tree Add(6,Mult(Num(2),Num(3)))

We are ready to actually start to define out operators in the parser to actually create these trees. Scala provides the ^^ operator which calls a function a match has occured.  Here is out parser with actions added.

def expr:Parser[Node]   = term~rep("+"~term | "-"~term)  ^^
                   { case head~tail => processTerms(head, tail) }
def term:Parser[Node]   = factor~rep("*"~factor | "/"~factor) ^^
                   {case head~tail => processFactors(head, tail)}
def factor:Parser[Node] = (
          decimalNumber ^^( d =>Num(d.toDouble) )
          | "("~>expr<~")"    // Just returns the nodes generated by expr
          )

Notice the return types of all the function has changed from Parser[Any] to Parser[Node]. Starting at the bottom factor function decimalNumber is just converted into a decimal number and then put inside a Num Node with is returned. The expr just returns itself excluding the the “(” and “)” matches.

The term and expr functions follow the same pattern so are treated in a similar way. The first item of the expr function is considered as the head of the list of terms. The rep function returns a list of matches for us so can be considered the tail. The problem we have is creating a Node tree from this list of matches. Lets take a look at how we do this.

def processNodeList(top:Node, nodes:List[~[String, Node]], converter:((Node, (String~Node))=>Node) ):Node ={
  if(nodes.isEmpty) return top
  processNodeList(converter(top, nodes.head), nodes.tail, converter)
}

def processTerms(top:Node, sub:List[~[String, Node]] ):Node = {
  processNodeList(top, sub, {(top, n) => n match {
      case ("+"~node) => Add( top,node)
      case ("-"~node) => Sub( top,node)
    }}
  )
}

To understand this code you need to know the ~ combinator function returns a type of class ~ that can be used in a match statement. So looking at process terms we actually delegate the hard work to processNodeList but provide a anonymous function to convert from these ~ classes to our nodes. The function processNodeList is a two liner, if the node list is empty just return top otherwise combine the top and the head of the node list into a Node using the supplied converter function and then call processNodeList again with this combined node as top. From a list we create a tree. A similar function called processFactors was also created. If I am honest I was quite suprised how little code was needed to do this as my initial implementation was quite a bit longer.

This is all we need to create the node tree (I have supplied full source code at the bottom of this blog entry).

Interpretation (Calculating the value).
Next up is the simple task of calculating the value. Here’s the code.

class Evaluator{
  def apply(node:Node):Double = {
    node match {
      case Num(v) => v
      case Add(n1,n2)  => this(n1)+this(n2)
      case Sub(n1,n2)  => this(n1)-this(n2)
      case Mult(n1,n2) => this(n1)*this(n2)
      case Div(n1,n2)  => this(n1)/this(n2)
    }
  }
}

The power of match and case statements combined with recursion really show though here. If it is a Num object return the value otherwise work out the value of the two child objects and then apply the correct operator(+,-,*,/).

Conclusion
In the past I wrote a series of articles about creating a simple calculator program using C++.
It went from a hand rolled parser to using Spirit all the time using boost graph library. In truth the articles were more about introducing the boost graph library rather than a how to implement a calculator program but they do demonstrate scala can achieve some rather nice and compact code that is very readable code.
As usual any comments are welcome.

Here is the full code.

import scala.util.parsing.combinator._

case class Node
case class Add(lhs:Node, rhs:Node)  extends Node
case class Sub(lhs:Node, rhs:Node)  extends Node
case class Div(lhs:Node, rhs:Node)  extends Node
case class Mult(lhs:Node, rhs:Node) extends Node
case class Num(d:Double)            extends Node

class Arith extends JavaTokenParsers {

  def processNodeList(top:Node, nodes:List[~[String, Node]], converter:((Node, (String~Node))=>Node) ):Node ={
	if(nodes.isEmpty) return top
	processNodeList(converter(top, nodes.head), nodes.tail, converter)
  }

  def processFactors(top:Node, sub:List[~[String, Node]] ):Node = {
	processNodeList(top, sub, {(top, n) => n match {
        case ("*"~node) => Mult( top,node)
        case ("/"~node) => Div( top,node)
      }}
	  )
  }

  def processTerms(top:Node, sub:List[~[String, Node]] ):Node = {
		processNodeList(top, sub, {(top, n) => n match {
        case ("+"~node) => Add( top,node)
        case ("-"~node) => Sub( top,node)
      }}
	  )
  }

	def expr:Parser[Node]   = term~rep("+"~term | "-"~term)  ^^
                            { case head~tail => processTerms(head, tail) }
	def term:Parser[Node]   = factor~rep("*"~factor | "/"~factor) ^^
                            {case head~tail => processFactors(head, tail)}
	def factor:Parser[Node] = (
          decimalNumber ^^( d =>Num(d.toDouble) )
          | "("~>expr<~")"    // Just returns the nodes generated by expr
          )
}

class Evaluator{
	def apply(node:Node):Double = {
		node match {
			case Num(v) => v
			case Add(n1,n2)  => this(n1)+this(n2)
			case Sub(n1,n2)  => this(n1)-this(n2)
			case Mult(n1,n2) => this(n1)*this(n2)
			case Div(n1,n2)  => this(n1)/this(n2)
		}
	}
}

object ArithTest extends Arith {
	def main(args:Array[String]){
		val nodes = parseAll(expr, "8.2*2-16-4").get
		println(nodes)
		val evaluator = new Evaluator
		println("Value is:" +evaluator(nodes))
	}
}