Parsing 4

• The Simple Language SL1
• Building an Interpreter

The Simple Language SL1

• Grammar

  block ::= (valdef | fundef)* expr
  expr ::= expr2 | "if" "(" expr ")" block "else" block 
  expr2 ::= term (( "+" | "-" ) term)*
  term ::= factor (( "*" | "/" ) factor)*
  factor ::= wholeNumber | "(" expr ")" | ident | funcall | funliteral
  funcall ::= ident "(" (expr ("," expr)*)? ")"
  funliteral ::= "{" (ident ("," ident)*)? "=>" block "}"
  valdef ::= "val" ident "=" expr ";"
  fundef ::= "def" ident "=" funliteral ";"

• Similar to Scala subset, but
  • Only two types: integer and functions
  • No compile-time type checking
  • if fakes Boolean, not quite like in C: > 0 is true, <= 0 is false
  • Definitions end in semicolons
  • Function literals like in BGGA

Some SL1 Examples

• Simple computation:

  val a = 3;
  val b = 4;
  a * a + b * b

• A function literal and a function call

  val max = { x, y => if (x - y) x else y };
  max(3, 4)

• A higher-order function

  val threeTimes = { f, x => f(f(f(x))) }; 
  threeTimes({x => x * x}, 2)

• A recursive function

  def fac = { x => if (x) x * fac(x - 1) else 1 };
  fac(10)

Interpreter Outline

• Parse the program, converting into ExprTree (as before) / Block
• Block is sequence of definitions, followed by one expression
• Need to add capabilities to eval(ExprTree)
  • if / else
  • function call
• Evaluating block:
  • Add definitions to symbol table
  • Evaluate expression with that table

The Symbol Table

• We had a lab (lecture 10 step 3) with evaluating variable definitions
• In that lab, we used a Map[String, Int] for the symbol table.
• Issue #1: Not all values are of type Int (i.e. functions)
• Remedy: Use Any
• Issue #2: We may have duplicate variable definitions

  val a = 3;
  val fun = { x => val a = 2; a * x };
  a * fun(4)

• Remedy: Use a List[(String, Any)] instead
• To add a definition, use ::
• Newer definitions at the front shadow the older ones

  ((a, 2), (x, 4), (a, 3))

• To look up a symbol's value, use find to find the first match:

  symbols.find(_._1 == name) match { 
    case Some(pair) => pair._2 
    case None => None 
  } 

Evaluating Expressions

• eval of an expression yields a value
• Need symbol table for looking up variables
• Result may be either an Int or a function

  val a = 3 * b;
  val sq = { x => x * x };

def eval(expr : ExprTree, symbols : List[(String, Any)]) : Any = 
  expr match {
    case Number(num) => num
    case Variable(name) => ... // find name in symbols                                                            case None => None }    
    case Operator(left, right, f) => ...
      // was f(left, right), but now we don't know they are Int
    case IfExpr(cond, block1, block2) => ...
    ...
  }

Evaluating Blocks

• Block = list of definitions + one expression
• Evaluate all definitions
• Add pairs to symbol table

  def evalDef(symbols : List[(String, Any)], defn : Valdef) =
    (defn.name, eval(defn.expr, symbols)) :: symbols

• (Additional wrinkle with function definitions—later)
• Use resulting table to evaluate expression

  def evalBlock(block : Block, symbols : List[(String, Any)]) : Any =
    eval(block.expr, (symbols /: block.defs) { evalDef(_, _) } )

  Visualize foldLeft with two definitions: (red fringe = list of defs)

               symbols
               for expr
             /        \
         augmented    2nd
          symbols     def
          /   \ 
  original    1st 
  symbols     def

Parsing Challenge: Function Calls

• Lookahead required to distinguish between variable and function(args)
• Parse with optional parameter list
• If found, generate a Funcall, else a Variable

  def valOrFuncall = valOrFun ~ opt( "(" ~> repsep(expr, ",") <~ ")" ) ^^ { 
    case expr ~ Some(args) => Funcall(expr, args)
    case expr ~ None => expr 
  }  

• Lookahead problem isn't limited to names. { x => x * x } is a function literal, { x => x * x }(3) is a function call.

  def valOrFun = "(" ~> expr <~ ")" |       
    ident ^^ { Variable(_) } | 
    funliteral
    
  def funliteral: Parser[ExprTree] = ("{" ~> repsep(ident, ",") <~ "=>") ~ expr <~ "}" ^^ { 
    case params ~ expr => Function(params, expr) 
  }

• Note: repsep(ident, ",")matches comma-separated list of ident, yielding a List[String] (with the separators discarded)

Calling a Function

• Inputs:
  • Function with parameter list and block, e.g. { x, y => (x + y) / 2 }
  • List of parameters, e.g. (10, a + 2)
• Add bindings (param name, param value) to symbol table

  x -> eval(10)

  y -> eval(a + 2)

• Evaluate body with that symbol table

  def eval(expr : ExprTree, symbols : List[(String, Any)]) : Any = 
    expr match {
      case Funcall(fun, args) => eval(fun, symbols) match {
        case Function(params, body) =>
          evalBlock(body, params.zip(args.map(eval(_, symbols))) ::: symbols)         
      }  

• params.zip(args) makes a list of pairs ((p1, a1), (p2, a2), ...)
• But we need to evaluate the arguments. The map takes care of that
• At this rate, we'll have a hard time getting to 200 lines of code
• Still need to discuss what to do with recursive function—next class

Lab

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

Step 1: Becoming Comfortable with SL1

1. Make a project SL1 in Scala. In the package lab12, make a Scala application called Main. Paste in this Scala code. Run the four SL1 programs from slide 3. What outputs do you get?
2. Write a SL1 program that defines pow2 to compute 2ⁿ for a given n, then calls pow2(10). What is your program and what is its output?

Step 2: Understanding the Parse Tree

For each of the following SL1 expressions and blocks, draw a parse tree. That should be the tree returned by parser.parse(...).get. Write the tree sideways with indentations, like this for the expression x * (y + 1). Use - for indentations so they don't get lost when pasting them into the web form.

Operator
-Variable(x)
-Operator
--Variable(y)
--Number(1)
--<add function>
-<multiply function>

1. { x, y => x + y }
2. fac(x - 1)
3. val sq = { x => x * x } ; sq(2)

Step 3: Understanding Symbol Tables

For each of the following scenarios, write the symbol table. Write it as a set of equations, like this

a = 3
sq = { x => x * x }
a = 2

where the newest symbols appear at the bottom. In our example, the last definition of a shadows the previous one. Note that each variable is bound either to an integer or a function.

1. At the end of the program val a = 3 ; val b = a + 1; val a = 2 ; a + b
2. At the execution of the function call in the program val a = 3; val sq = { x => x * x } ; sq(a + 2). Be sure to show the binding for x.
3. At the execution of the function call in the program val a = 3; val x = 2; { x => a * x } (a)

Confirm your guesses for 2 and 3 with this trick. Define a function

def spy[T](t : T) = { println(t); t }

Then add a spy(...) call around

params.zip(args.map(eval(_, symbols))) ::: syms

in the evaluation of a Funcall.