Exam #1

CS 152 | Fall 2008

Exam Rules

• 10 points per problem. That isn't fair, so work the problems in an order that maximizes your score.
• You may use any books, notes, files, web sites of your choice, except as noted below.
• You may NOT communicate with anyone during the exam.
• You may NOT open any programs or web sites that allow communication with someone else. No messenger, chat, email, discussion forum, etc.
• I will randomly inspect laptops. If I inspect yours, you need take the hands off the keyboard immediately.
• Put your answers into a text or ZIP file (your choice) and paste or upload it (your choice) into eCampus.

1. Define a Scala function merge that merges two lists of strings, alternately picking elements from the first and second list (like in mergesort). If one list is shorter than the other, the unmatched tail elements of the other are appended. For example,

   scala> merge(List("1", "2", "3"), List("A", "B", "C", "D", "E"))
   res0: List[String] = List(1, A, 2, B, 3, C, D, E)

   Use nothing but head, tail, ::, isEmpty, Nil, if/else and recursion.

2. Describe in plain English what this function does.

   def mystery(l1 : List[String], l2 : List[String]) = 
     l1.zip(l2).map(Function.tupled(_ + " likes " + _))

   Also explain why Function.tupled is necessary. (That is, why doesn't l1.zip(l2).map(_ + " likes " + _) work.)

   (To find the scaladoc of Function.tupled, you need to search the Function object.)

3. Consider the following Scala application that parses and evaluates arithmetic expressions.

   package exam1.problem3
   
   import scala.util.parsing.combinator._
   
   class SimpleLanguageParser extends JavaTokenParsers {    
     def expr: Parser[Double] = (term ~ rep(("+" | "-") ~ term)) ^^ { 
         case a ~ lst =>  (a /: lst) { 
           case (x, "+" ~ y) => x + y
           case (x, "-" ~ y) => x - y
         }
       } 
     def term: Parser[Double] = (factor ~ rep(("*" | "/") ~ factor)) ^^ { 
         case a ~ lst =>  (a /: lst) { 
           case (x, "*" ~ y) => x * y
           case (x, "/" ~ y) => x / y
         }
       } 
     def factor: Parser[Double] = wholeNumber ^^ { _.toDouble } | "(" ~> expr <~ ")"
   }
   
   object Main {
     def main(args : Array[String]) : Unit = {}
     val parser = new SimpleLanguageParser
     val result = parser.parse(parser.expr, "3 + 4 * 5")
     println(result)       
   }

   Your task is to add support for an operator ^ that denotes “raising to a power”. For example, 2 ^ 3 has value 8. The ^ operator should have higher precedence than * or /. That is, 5 * 2 ^ 3 is 40, not 1000. Ten bonus points if ^ is right-associative, as in the mathematical notation. That is, 2 ^ 3 ^ 4 is 2 ^ (3 ^ 2) = 512, not (2 ^ 3) ^ 2 = 64.

4. Consider the grammar given in the following Scala program:

   package exam1.problem4
   
   import java.io._
   import scala.util.parsing.combinator._
   
   class MysteryParser extends JavaTokenParsers {    
     def expr: Parser[Any] = (term ~ rep(("+" | "-") ~ term)) 
     
     def term: Parser[Any] = (factor ~ rep(("*" | "/" ) ~ factor))
     
     def factor: Parser[Any] = 
       (wholeNumber | ident | "(" ~ expr ~ ")") ~ opt( "." ~ ident ~ "(" ~ repsep(expr, ",") ~ ")" )           
   }
   
   object Main {
     def main(args : Array[String]) : Unit = {
       val parser = new MysteryParser
       val result = parser.parse(parser.expr, new InputStreamReader(System.in))
       println(result)       
     }
   }

   Describe in plain English what this grammar describes. Give an example of a valid expression that contains a "." and a ",".

5. In lecture 12, we introduced the language SL1 and an interpreter. Consider this SL1 program:

   val a = 10;
   val f = { x => x * a };
   val g = { a => val x = a * a; f(x) };
   g(2)

   What are the symbol tables

   • When the block inside g is evaluated
   • When the block inside f is evaluated

   Write each table as a set of equations, like this

   a = 10
   f = { x => x * a }
    ...

   where the newest symbols appear at the bottom.

   Note that SL1 properly handles closures. A function's body is evaluated in the environment in which it is defined, augmented by the bindings of the parameters.

   Feel free to run the interpreter and set a breakpoint or add a println statement.