Parsing 1

• Case classes
• Trees
• The Option type
• Expression trees
• Time to move to Eclipse

Case Classes

• Special kind of class, optimized for matching

  case class ClassName(field1 : Type1, field2 : Type2, ...) extends Superclass

• Example: Binary tree with values only in the leaves

  class SimpleTree
  case class Leaf(value : Int) extends SimpleTree
  case class Node(left : SimpleTree, right : SimpleTree) extends SimpleTree 

• Construct instances with ClassName(arg1, arg2, ...)

  Node(Node(Leaf(3), Leaf(2)), Node(Leaf(7), Node(Leaf(6), Leaf(8))))

  

Pattern Matching

• selectorExpr match { 
     case pattern => expr 
     ... 
     case pattern => expr 
  }

• Many possibilities for the patterns; we care about case classes

• tree match {
    case Node(l, r) => expr1
    case Leaf(v) => expr2
  }

• Variables l, r, v are bound to the values in the case class instances; you can use them in the expressions.

  def sum(t : SimpleTree) : Int = t match { 
    case Node(l, r) => sum(l) + sum(r) 
    case Leaf(v) => v 
  }

• Matches are tried in order. To have a default, use the “wildcard” pattern at the end

  case _

The Option Type

• Option type expresses “0 or 1” relationship
• Case class with two cases: Some, None
• Example: List.find returns Option[A].

  val result = lst.find(_ % 2 == 0)
  result match { 
    case Some(x) => println(x)
    case None => println("No match") 
  }

• Why not return null if there is no match?
• null might be a valid value in the collection
• Int can't be null

Syntax Trees

• Tree that represents the syntax of a program (or a program part)
• Example: Expression tree for 3 + 4 * x

  

• Model in Scala:

  class ExprTree
  case class Number(value : Int) extends ExprTree
  case class Variable(name : String) extends ExprTree
  case class Operator(left : ExprTree, right : ExprTree, 
    f: (Int, Int) => Int) extends ExprTree

  Operator(Number(3), Operator(Number(4), Variable("x"), _ * _), _ + _)

• Next lecture: How to parse 3 + 4 * x into Scala value

Syntax Tree Evaluation

• Compute value of expression
• Need values of free variables
• Use a Map[String, Int]
• Scala immutable maps:
  • Map(key1 -> value1, key2 -> value2, ...) yields map with given key/value pairs
  • map + (key -> value) yields map with new key/value pair
  • map(key) yields value of key (must exist)
  • map.get(key) yields Option, either Some(value)or None

• def eval(expr : ExprTree, symbols : Map[String, Int]) : Int = 
    expr match {
      case Number(num) => num
      case Variable(name) => symbols(name)
      case Operator(left, right, f) => f(eval(left, symbols), eval(right, symbols))
    }

IDE Survey

• What is your favorite professional Java IDE?
  1. Eclipse
  2. NetBeans
  3. IntelliJ
  4. I have no experience with professional IDEs
  5. I prefer another IDE (Give name in text field below)

Scala IDE Plugin

• As our programs get longer, the interpreter won't cut it any more
  • Course goal from green sheet; Produce programs in a functional programming language in excess of 200 LOC
• Use Eclipse IDE plugin
• If you don't have Eclipse installed, get it here.
• Install the Scala plugin, as described here
• Prefer Netbeans? Install 6.5 beta and get a plugin here. (It is actually a bit nicer than the Eclipse plugin.)

Scala in Eclipse

• File→New Project→Scala Wizards→Scala Project (ex. Lab9)
• When the project is opened, expand it until you see the src node. Right-click and select New→Package (ex. lab9)
• Right-click on that package, select New→Scala Application (ex. Main)
• In the newly created Scala object, complete the main method

  package lab9
  
  object Main {
    def main(args: Array[String]) {
      println("Hello")  }
  }

• Scala object = class with only one instance, similar to static in Java
• Right-click and select the menu item "Run As → Scala Application".

Lab

• Check into eCampus in the usual way
• Scribe puts in report
• Buddy puts in comment with scribe's name

Step 1

Add the classes ExprTree, Number, Variable, Operator to the Main.scala file. Add the eval method to the Main object. In the main method, construct the tree

and evaluate it with a symbol table in which x is 5. What is the code of your Main.scala file?

If you didn't install Eclipse and the Scala plugin before class, then write the file with a text editor (in a lab9 subdirectory to match the package name) and compile/run with

scalac lab9/Main.scala
scala lab9.Main

Step 2

Now we want to add variable definitions (which we will write as val x = expr in the next lecture). For now, we will assume that they are already parsed into instances of

case class Definition(name : String, expr : ExprTree)

For example, a definition val x = 2 would be a Definition("x", Number(2)). A definition changes the symbol table. In a functional setting, that means we need to return a new table that contains all bindings in the old table and the new binding. For example,

val def1 = Definition("x", Number(2))
val def2 = Definition("y", Variable("x"))
val sym0 = Map[String, Int]()
val sym1 = eval(def1, sym0) // "x" -> 2
val sym2 = eval(def2, sym1) // "x" -> 2, "y" -> 2

Implement this eval method . What is the code of your method? (You can get the fields of a definition as defi.name, defi.expr.)