Final Exam

5 minute read

Prologue

This is the final exam for CS 135. This is an open-notes, open-internet, take home exam. However, this exam is individual, and you may not discuss the exam problems with anyone except the instructor.

The exam is due no later than 5:00 PM, Friday, May 14th central time. You should submit your solutions on codePost.

Problem 1: Functional Programming in Python/Java

Your task for this problem is to investigate how functional programming techniques can be applied in either Python or Java (you may choose which).

If you choose to investigate Python, you should read about the lambda keyword and look into the functools, itertools, and operator modules. You could consider also reading up on list comprehensions.
If you choose to investigate Java, you should read about lambda expressions, streams (introduced in Java 8), and functional interfaces.

You must answer the following questions about your chosen language:

Are there analogous functions to Haskell’s map, foldr, and filter? If so what are they? Provide examples.
Recall that Haskell natively supports partial application. In other words, things like map (interp env) args are possible because interp is partially applied to env before it is mapped over args.

Is there a way to partially apply functions? If so, how? Give an example.
When declaring an anonymous function, how are closures handled? Give an example demonstrating the use of a closure.

Submit your answers in a file named problem_one.py if you chose Python or in a file named ProblemOne.java if you chose Java. Your answers should be written as comments in the file and your example code should be embedded within the file.

Problem 2: Parsing a Simple Grammar

Consider the following datatype representing a binary tree of integers.

data IntTree = Empty | Node Int IntTree IntTree

Note that Empty creates an empty IntTree, and Node n l r creates an IntTree that contains the integer n with a left subtree l and a right subtree r.

We can also encode an IntTree as a string of characters:

(1, (2, nil, nil), (3, nil, nil))

Here, a string nil represents an empty IntTree and a string (<int> <exp> <exp>) represents a node. Thus, the entire string above is equivalent to the IntTree defined by:

Node 1 (Node 2 Empty Empty) (Node 3 Empty Empty)

Your task for this problem is to write a parser that parses strings formatted like the ones above into their corresponding IntTree. To complete the problem, download the following starter files and finish implementing the pTree parser:

Hint: Remember that there is a built-in parser natural for parsing natural numbers. You need not worry about negative numbers for this problem.

Problem 3: `interp` with Side Effects

On the previous two assignments, we implemented a simple functional language with no mutability. In this problem, we will extend the language to support a simple form of mutability.

Store

Similar to what we saw in class, we will separate the environment into two parts. In particular, we will now be using the types:

type Env   = [(Identifier,Location)]
type Store = [(Location,Value)]

Note that Env now maps identifiers to locations in memory and Store maps memory locations to values.

`set!`

Many Lisp-like languages have a function (set! id expr) that takes an identifier id and an expression expr and changes the value of id to be the result of expr in the local environment. (Note that set! should raise an error if id is not already defined in the environment.) Note that set! is analogous to other languages assignment statements such as x = 5 and allows us to mutate variables.

In addition to modifying the value of id, a set! expression should also return the value of the expr. (This is similar to C’s assignment statement behavior.)

For example, the expression (set! x (+ 5 4)) should change the value of x to 9 and also return 9.

In order to support the new set! operation, a new node in the Expr datatype is included: Set Identifier Expr. Your main goal in this part of the exam is to handle the Set case in the interp function.

Starter Files

Before continuing, be sure to download the following starter files.

What do you need to do?

For this problem, everything is implemented already except for three cases in the interp function, namely:

Id x -> ...
Seq xs -> ...
Set x y -> ...

The Id case is what happens when the interpreter encounters a variable name. You will need to look up the current value of x in the environment/store appropriately. (Note that there already exist some helper functions for this.)

The Seq case is for a situation where the interpreter must interpret a block of expressions, in sequence, and should return the result of the last expression. Thus, xs is a list. You may assume that xs has at least one element in it (this is enforced by the parser).

The Set x y case is for changing the identifier x to the result of the expression y. This is the Expr that statements like (set! x y) are parsed into.

Once you are done with Id and Seq, you should be able to evaluate expressions like this:

(let ((mult (lambda (x y)
              (* x y))))
  (mult 10 4))

which should evaluate to 40.

Once you are done with Set, you should be able to evaluate expressions like this:

(let ((x 0))
  (set! x (+ x 1))
  (set! x (+ x 1))
  (set! x (+ x 1))
  x)

which should evaluate to 3.

Just for Fun

You might have noticed that the parser also supports a command called letrec which allows you to define recursive functions. (It desugars into let and set!). After you are finished implementing Set in the interpreter, you should also be able to evaluate statements such as:

(letrec ((factorial
            (lambda (n)
              (if (= n 0)
                  1
                  (* n (factorial (- n 1)))))))
  (factorial 5))

which should evaluate to 120. Using letrec, you should be even able to implement mutually recursive functions such as:

(letrec ((even? (lambda (n)
                  (or (= n 0)
                      (odd? (- n 1)))))
         (odd? (lambda (n)
                 (and (> n 0)
                      (even? (- n 1))))))
  (even? 5))

which should evaluate to #f.

How to Turn in Your Code

Once you are finished with the assignment, you should go to https://codepost.io and log into your account.
Go to the CS 135 course.
Go to Final Exam and upload all of your files.
That’s it! You’ve just submitted your assignment.

Important Grading Criteria

I will evaluate your work with the following criteria in mind.

Correctness. Does your code do what is asked? (e.g. named correctly, input and outputs correct values, etc.)
Formatting. Is your code formatted so that it is easy to understand?
Elegance. Is your code concise and elegant?