Final Exam

CS 152 | Fall 2008

Exam Rules

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 ZIP file final_lastname_firstname.zip that contains

cs152final/Question1.scala
cs152final/Question2.scala
cs152final/Question3.scala
cs152final/Question6.scala
question4.txt
question5.pl

[5 points for correct packaging]

Upload your ZIP file to eCampus

Question 1. [10 points]

It often happens that one wants to write the entries of a List[T] in Scala as a comma-separated string. For greater flexibility, one will want to allow arbitrary functions that turn each element into a string, then concatenate the results, adding those pesky commas.

For example,

stringify(List(1, 2, 3), ((x : Int) => "$" + x))

yields the string "$1, $2, $3".

In this question, you will implement a method

stringify[T](vals : List[T], f : T => String) : String

in two ways. Neither of them involve loops.

a) Implement stringify using recursion, by considering the case of an empty list, a list with one element, and a longer list.

b) Implement stringify without recursion, using the fold operator and not map or mkString. (You may still need a separate case for the empty list.)

For comparison, the following program contains a third implementation that uses the standard Scala library.

Submit your solution by completing the following file Question1.scala:

package cs152final

object Question1 {
  def stringify1[T](vals : List[T], f : T => String) : String =
    ...
  def stringify2[T](vals : List[T], f : T => String) : String = 
    ...      
  def stringify3[T](vals : List[T], f : T => String) : String = vals.map(f).mkString(", ")
  
  def main(args : Array[String]) : Unit = {
    println(stringify1(List(1, 2, 3), ((x : Int) => "$" + x)))
    println(stringify2(List(1, 2, 3), ((x : Int) => "$" + x)))
    println(stringify3(List(1, 2, 3), ((x : Int) => "$" + x)))    
  }  
}

Question 2. [10 points] In the SL3 interpreter, we have types

class SL3Type
case class SL3Int extends SL3Type
case class SL3Bool extends SL3Type
case class SL3Fun(paramTypes : List[SL3Type], returnType : SL3Type) extends SL3Type

We want to translate objects of type SL3Type into Java types, according to these rules:

SL3Int and SL3Bool turn into the Java wrapper types Integer and Boolean

Function types turn into the following interfaces:

interface Function0<R> { public R invoke(); }
interface Function1<A1, R> { public R invoke(A1 arg1); }
interface Function2<A1, A2, R> { public R invoke(A1 arg1, A2 arg2); }

etc. You may assume that these templates are already defined.

Write a function

sl3typeToJavaType(type3 : SL3Type) : String

that returns the Java type name of type3. For example,


`input`	`sl3typeToJavaType(input)`
`SL3Int()`	`"Integer"`
`SL3Fun(List(SL3Int()), SL3Bool()))`	`"Function1<Integer, Boolean>"`
`SL3Fun(List(SL3Fun(List(SL3Int()), SL3Bool())),SL3Int()))`	`"Function2<Function1<Integer, Boolean>, Integer>"`

Hint: Use type3 match { case ... => ... }. There are three cases. In the third case, use stringify.

Submit your solution by completing the following file Question2.scala:

package cs152final

object Question2 {
  class SL3Type
  case class SL3Int extends SL3Type
  case class SL3Bool extends SL3Type
  case class SL3Fun(paramTypes : List[SL3Type], returnType : SL3Type) extends SL3Type

  def stringify[T](vals : List[T], f : T => String) : String = vals.map(f).mkString(", ")

  def sl3typeToJavaType(type3 : SL3Type) : String = 
  type3 match {    
    ...
  }
 
  def main(args : Array[String]) : Unit = {
    println(sl3typeToJavaType(SL3Int()))
    println(sl3typeToJavaType(SL3Fun(List(SL3Int()), SL3Bool())))
    println(sl3typeToJavaType(SL3Fun(List(SL3Fun(List(SL3Int()), SL3Bool())),SL3Int())))
  }  
}

Question 3. [10 points] This code modifies the SL3 interpreter in two ways:

Recursive definitions are removed for simplicity
The program translates SL3 code to Java code instead of interpreting it

The code uses the following translation strategy.

Variables, numbers, and operators are unchanged
Definitions val name = expr are translated to
```
final Type name = converted expr;
```
where Type is produced by the typeof function of the SL3 program, followed by the sl3typeToJavaType function of the preceding question.
The expression at the end of a block is turned into a return statement
Function literals are converted to anonymous inner class instances that implement the FunctionX interfaces. For example, { x : Int => 3 * x } is translated to
```
new Function1<Int, Int>() { public int invoke(int x) { return 3 * x; }
```

However, the code is incomplete. Your task is to translate function calls. (Look for TODO.) Consider the example

val triple = { x : Int => 3 * x };

In Java, this becomes

final Function1<Int, Int> triple = new Function1<Int, Int>() { public int invoke(int x) { return 3 * x; };

You should translate the expression triple(10) into triple.invoke(10). Similarly, the expression

{ x : Int, y : Int => x == y }(a, 0)

should become

new Function2<Int, Int, Bool>() { ... }.invoke(a, 0)

To get the first part, simply call codegen on the fun part of the Funcall object.

Try out your program with this SL3 example. You should get a Main.java file that can be compiled and executed, printing the result 18.

val twice = { f : (Int)=>Int, a : Int => f(f(a)) };
val n = 3;
val mul_by_n = { x : Int => n * x };
twice(mul_by_n, 2)

Turn in your completed Question3.scala file.

Question 4. [10 points] The program of the previous question should have produced this Java file (indented for ease of reading)

interface Function0<R> { R invoke(); }
interface Function1<A1, R> { R invoke(A1 a1); }
interface Function2<A1, A2, R> { R invoke(A1 a1, A2 a2); }
interface Function3<A1, A2, A3, R> { R invoke(A1 a1, A2 a2, A3 a3); }
public class Main {
  public static void main(String[] args) { System.out.println(main()); }
  public static Integer main() {
    final Function2<Function1<Integer, Integer>, Integer, Integer> twice = 
      new Function2<Function1<Integer, Integer>, Integer, Integer>() { 
        public Integer invoke(Function1<Integer, Integer> f, Integer a) {
          return f.invoke(f.invoke(a));
        }
      };
    final Integer n = 3;
    final Function1<Integer, Integer> mul_by_n = 
      new Function1<Integer, Integer>() { public Integer invoke(Integer x) {
        return n * x;
      }
    };
    return twice.invoke(mul_by_n, 2);
  }
}

(Work with this Java file for this question even if you didn't solve the previous question.) The mul_by_n function is a closure since its body has a free variable that is bound in an outer scope. Explain how the values for n and x are obtained in the expression n * x. Give evidence from running javap. Include the javap output and refer to specific line numbers in your explanations. Don't waste your time with general observations--you will get no credit for them.

Submit a file question4.txt.

Question 5. [10 points] Consider these Prolog rules.

typeof(zero, int).
typeof(one, int).
typeof(two, int).
typeof(three, int).
typeof(times(X, Y), int) :- typeof(X, int), typeof(Y, int).
typeof(invoke1(F, X), R) :- typeof(X, A), typeof(F, fun1(A, R)).
typeof(F, fun1(A, R)) :- fundef1(F, _, A, B), typeof(B, R).
typeof(X, T) :- fundef1(_, X, T, _).

fundef1(triple, x, int, times(three, x)).

a) These rules allow you to infer the types of expressions. Run this program and find the types of triple and invoke1(triple, two).

b) Add rules for functions with two parameters. For example, if you add the fact

fundef2(twice, f, fun1(int, int), a, int, invoke1(f, invoke1(f, a))).

your new rules should allow asking for the type of twice and of invoke2(twice, triple, two).

Submit a file question5.pl. In that file, provide all necessary rules and comments with the queries that you ran and the answers that you got. (In Prolog, comment lines start with %)

Question 6. [10 points] Give a grammar in Scala for parsing a set of Prolog rules, such as the ones in the preceding question. Only parse clauses that are made up from terms. Do not include list notation, numbers, arithmetic, or the is operator. Submit your solution by modifying the following Question6.scala:

package cs152final

import java.io._
import scala.util.parsing.combinator._

object Question6 {
  case class Term(fun : String, args : List[Term])
  case class Clause(...)
  
  class PrologParser extends JavaTokenParsers {
    def program : Parser[List[Clause]] = ...
    def clause : ...
    def term : Parser[Term] = ident ~ opt("(" ~> repsep(term, ",") <~ ")") ^^ {
      case f ~ None => Term(f, List())
      case f ~ Some(a) => Term(f, a)
    }
  }
    
  def main(args : Array[String]) : Unit = {
    val parser = new PrologParser
    val result = parser.parse(parser.program, new InputStreamReader(System.in)).get
    println(result)
  }
}

When your program has the input

append(nil, Ys, Ys).
append(cons(X, Xs), Ys, cons(X, Zs)) :- append(Xs, Ys, Zs).

it should produce

List(Clause(Term(append,List(Term(nil,List()), Term(Ys,List()), Term(Ys,List()))),List()), 
  Clause(Term(append,List(Term(cons,List(Term(X,List()),Term(Xs,List()))),Term(Ys,List()),Term(cons,List(Term(X,List()),Term(Zs,List()))))),
    List(Term(append,List(Term(Xs,List()), Term(Ys,List()), Term(Zs,List()))))))