Homework 7

1. Write a SL1 function reverse that reverses the digits of a positive integer. For example, reverse(1729) should yield 9271. Place the function and a call to reverse(1729) into hw7/reverse.sl1, together with any helper functions that you may need. (I needed two.) Place SL1.scala from lecture 12 into src/main/scala. Run

   sbt run < reverse.sl1
   

2. The SL1 interpreter from lecture 12 has an annoying limitation. It doesn't support multiple function invocations such as f(x)(y). What—no currying? We've got to fix that. Modify SL1.scala. Also supply a file hw7/curry.sl1 that translates the example from http://horstmann.com/sjsu/spring2018/cs152/lecture5/#(8) into SL1. Running sbt run < curry.sl1 from the hw7 directory should work. Note: We only care about curried function calls f(x)(y), not definitions. Don't change the handling of def.
   This can be done by changing three lines of SL1.
   • Where are function calls parsed?
   • Why is the current version only taking one set of parentheses?
   • What is the obvious change in the grammar rule to accept any number of parentheses?
   • When you have multiple parentheses, you want a Funcall(Funcall(...), ...). Figure out what you want. Then translate it into a fold. Draw that picture. Translate into a fold.
   • You need to reverse the ordering of the cases so you get expr when the list is empty and the function calls when it is not.
   Here is a bonus feature. Add the file y.sl1 to the hw7 directory and run sbt run < y.sl1. If you did the modification correctly, you will get 10! = 3628800. Now look inside y.sl1. Note that it does not use def! We have managed to compute a recursive function without the uncool def that requires a mutation in our interpreter. Why does this work? It is the awesome power of the Y combinator. (Not required reading for this course, but could come in handly if you want to interview for a Y Combinator startup.)
3. Add handling of lists to SL1.scala. Support lists of the form x :: y :: z :: Nil and list functions head, tail, and isEmpty. We will call them as functions, not methods. For example, evaluating head(1 :: Nil) yields 1.
   Define a case class

   case class Cons(a: Expr, b: Expr) extends Expr

   Parsing :: isn't hard—add a right-associative operator that binds more strongly than * or / and yields a Cons.
   Evaluating Cons is a little icky. We want eval(Cons(a, b), symbols) to be the Scala list eval(a, symbols) :: eval(b, symbols). But eval has return type Any. Apply a cast like this:

   eval(a, symbols) :: eval(b, symbols).asInstanceOf[List[Any]]

   
   Add four entries to the initial symbol table. Bind "Nil" to an empty Scala list and head, tail, isEmpty to instances of

   case class ListOp(f: List[Any] => Any)
   

   For example, isEmpty should be bound to

   ListOp(l => if (l.isEmpty) 1 else 0)

   Then define what it means to evaluate a ListOp. First figure out where it is evaluated. (Hint: head(x) looks like a function call fac(n), except when looking up head in the symbol table, you get a ListOp, whereas a function like fac is a Closure.) Once you have found the right spot, you just need to add a case ListOp(f) => ..., evaluating the function on the first argument. You will again need a cast to List[Any].
   Do not worry about handling incorrect programs. If someone calls head(x, y) or head(1) or head(), let it crash. This won't be tested.
   To show that your list operations work, provide a file revlist.sl1 in which you define a function reverse that reverses a list, like in lecture 3, followed by a call reverse(1 :: 2 :: 3 :: 4 :: 5 :: Nil). (It doesn't have to be tail recursive, and you don't have to use a Y combinator. But you can. If you do, remember to curry append or reverseHelper—the Y combinator produces functions with one argument.)