CSE 130 - Programming Assignment #7

Python

110 points

(see submission instructions below)

(click your browser's refresh button to ensure that you have the most recent version)

(Programming Assignment #7 FAQ)

Note: To download and install the latest 3.6.x version of Python on your home machines see this page. Remember that this is only to enable you to play with the assignment at home: The final version turned in must work on the ACS Linux machines. While you can use MacOS or Windows to begin working with Python, the code you turn in must be that required for the Linux environment.

Code Documentation and General Requirements

Code for all programming assignments should be well documented. A working program with no comments will receive only partial credit. Documentation entails providing documentation strings for all methods, classes, packages, etc., and comments throughout the code to explain the program logic. Comments in Python are preceded by # and extend to the end of the line. Documentation strings are strings in the first line of a function, method, etc., and are accessible using help(foo), where foo is the name of the method, class, etc. It is understood that some of the exercises in this programming assignment require extremely little code and will not require extensive comments.

While few programming assignments pretend to mimic the "real" world, they may, nevertheless, contain some of the ambiguity that exists outside the classroom. If, for example, an assignment is amenable to differing interpretations, such that more than one algorithm may implement a correct solution to the assignment, it is incumbent upon the programmer to document not only the functionality of the algorithm (and more broadly his/her interpretation of the program requirements), but to articulate clearly the reasoning behind a particular choice of solution.

Assignment Overview

The objective of this assignment is to introduce you to some more advanced features of Python. This assignment will cover topics from classes and OOP, the decorator pattern, and parsing and typechecking.

The assignment is available as a zip file pa7.zip for you to download.

Assignment Testing and Evaluation

Your functions/programs must compile and/or run on a Linux ACS machine (e.g. ieng6.ucsd.edu), as this is where the verification of your solutions will occur. While you may develop your code on any system, ensure that your code runs as expected on an ACS machine prior to submission. You should test your code in the directories from which the zip files (see below) will be created, as this will approximate the environment used for grading the assignment.

Most of the points, except those for comments and style, will be awarded automatically, by evaluating your functions against a given test suite. The file, test.py contains a very small suite of tests which gives you a flavor of these tests. At any stage, by typing at the UNIX shell :

python3 test.py
you will get a report on how your code stacks up against the simple tests.

The last (or near the bottom) line of the file log must contain the word "Compiled" otherwise you get a zero for the whole assignment. If for some problem, you cannot get the code to compile, leave it as is with the raise ..., with your partial solution enclosed below as a comment. There will be no exceptions to this rule. You are encouraged to try to understand the code in test.py, and subsequently devise your own tests and add them to test.py, but you will not be graded on this.

Alternately, inside the Python shell, type (user input is in red):

>>> import test
.
.
.

Submission Instructions

1. Create the zip file for submission

Your solutions to this assignment will be stored in separate files under a directory called pa7_solution/, inside which you will place the files: decorators.py, nano.py, types.pl . These three files listed are the versions of the corresponding supplied files that you will have modified. There should be no other files in the directory.

After creating and populating the directory as described above, create a zip file called <LastName>_<FirstName>_cse130_pa7.zip by going into the directory pa7_solution and executing the UNIX shell command:

zip <LastName>_<FirstName>_cse130_pa7.zip *

2. Test the zip file to check for its validity

Once you've created the zip file with your solutions, you will use the validate_pa7 program to see whether your zip file's structure is well-formed to be inspected by our grading system by executing the UNIX shell command:

validate_pa7 <LastName>_<FirstName>_cse130_pa7.zip
The validate_pa7 program will output OK if your zip file is well-formed and your solution is compiled. Otherwise, it will output some error messages. Before going to step 3, make sure that your zip file passes validate_pa7 program. Otherwise you get a zero for the whole assignment. If you have any trouble with this, refer to the instructions in step 1.

3. Submit the zip file via the turnin_pa7 program

Once you've created the zip file with your solutions, you will use the turnin program to submit this file for grading by going into the directory pa7_solution/ and executing the UNIX shell command:

turnin_pa7 <LastName>_<FirstName>_cse130_pa7.zip

The turnin_pa7 program will provide you with a confirmation of the submission process; make sure that the size of the file indicated by turnin_pa7 matches the size of your zip file. Note that you may submit multiple times, but your latest submission overwrites previous submissions, and will be the ONLY one we grade. If you submit before the assignment deadline, and again afterwards, we will count it as if you only submitted after the deadline.

Hints

May of the questions in this assignment use more advanced features of Python. You may find the following links useful.

Useful Links

Defining Classes

All classes used in this assignment should be new-style Python classes which have either object as a base class or only other new-style classes as base classes. 
class foo: # implicit object base class
    pass

class bar(foo):
    pass

Quirks / Features of Python

Problem #0: Documentation

None of the functions in this assignment are documented (except the Failure exception). You are expected to document all modules (.py files), all classes, and all public functions with doc strings. Doc strings should describe the behavior of the function/class/module. For example:
"The function prod takes two integers and returns their product".
If the implementation is not straightforward and obvious, there should be comments. For example:
# prod is implemented using a FFT to get O(n log n) time
Once documented you should get the following behavior at the Python prompt:

>>> import decorators
>>> help(decorators)
Screen full of documentation with all your doc strings

Problem #1: Typechecking NanoML (nano.py, nanoParser.py, types.pl)

In this problem, you will write a type-inference algorithm for the NanoML language of PA4. Type-inference is very naturally expressed in Prolog and so you will implement the logic of your algorithm in a Prolog file, types.pl. You will also reuse the project from PA4, provided in the nano/ directory, to parse NanoML programs. Finally, you will use Python to coordinate between OCaml and Prolog.

First, we shall encode NanoML expressions as Prolog terms via the following grammar: 
    Expr ::= const(Ints)
           | boolean(Bools)
           | nil
           | var(VName)
           | bin(Expr, Bop, Expr)
           | ite(Expr, Expr, Expr)
           | let(Name, Expr, Expr)
           | letrec(Name, Expr, Expr)
           | fun(Name, Expr)
           | app(Expr, Expr)

    VName ::= lower case variable names

    Ints ::= 0 | 1 | 2 | ... (all integer constants)

    Bools ::= true | false

    Bop  ::= plus | minus | mul | div | eq | neq | lt | leq | and | or | cons
Similarly, we shall encode ML types as Prolog terms using the following grammar: 
   Type ::= int | bool | arrow(Type, Type) | list(Type) | TName

   TName ::= type variable names that starts with an uppercase letter (really just Prolog variables)

The table below shows several examples of Ocaml expressions, the Prolog term encoding that expression, and the Prolog term encoding the type of the expression.

NanoML Expression Prolog Expression Prolog Type
2 const(2) int
2 + 3 bin(const(2),plus,const(3)) int
2 <= 3 bin(const(2),leq,const(3)) bool
fun a -> a fun(a,var(a)) arrow(X,X)
fun x -> x <= 4 fun(x,bin(var(x),leq,const(4))) arrow(int,bool)
fun x -> fun y -> if x then y else 0 fun(x,fun(y,ite(var(x),var(y),const(0)))) arrow(bool,arrow(int,int))
let x = 10 in x let(x,const(10),var(x)) int
fun x -> let y = x in y + y fun(x,let(y,var(x),bin(var(y),plus,var(y)))) arrow(int,int)
fun a -> let b = a in b fun(a,let(b,var(a),var(b))) arrow(X,X)

This assignment is structured as follows. nano.py defines a class hierarchy for NanoML expressions and types. nanoParser.py contains parsers functions for this hierarchy. types.pl contains an (unimplemented) type-inference algorithm for NanoML expressions. The nano/ directory contains the NanoML assignment from PA4, modified to build expressions in nano.py. Finally, the nanoTypes.py file interfaces between the various languages. The only files you will need to modify are nano.py and types.pl.

Most of the provided Python code relies on the OCaml library in nano/. You will need to build this library before running many commands; to do this, cd into the nano/ directory and run make.

(a) OCaml to Prolog: 20 points

Fill in the implementation of toProlog in the file nano.py. Each class must have an implementation of toProlog that converts the given expression into a prolog term. You can for example test your implementation as follows:

>>> from nanoParser import fileToNano, parseNano
>>> parseNano("x+1").toProlog()
'bin(var(x), plus, const(1))'
>>> parseNano("if true then x else false").toProlog()
'ite(boolean(true), var(x), boolean(false))'
>>> fileToNano("nano/tests/t1.ml").toProlog()
'bin(bin(const(2), plus, const(3)), mul, bin(const(4), plus, const(5)))'
>>> fileToNano("nano/tests/map.ml").toProlog()
'letrec(map, fun(f, fun(xs, ite(app(var(null), var(xs)), nil, bin(app(var(f), app(var(hd), var(xs))), cons, app(app(var(map), var(f)), app(var(tl), var(xs))))))), var(map))'
>>> fileToNano("nano/tests/foldl.ml").toProlog()
'let(foldl, fun(f, fun(b, fun(l, letrec(worker, fun(acc, fun(xs, ite(app(var(null), var(xs)), var(acc), app(app(var(worker), app(app(var(f), var(acc)), app(var(hd), var(xs)))), app(var(tl), var(xs)))))), app(app(var(worker), var(b)), var(l)))))), var(foldl))'
>>> BoolTy().toProlog()
'bool'
>>> ListTy(IntTy()).toProlog()
'list(int)'
>>> ArrowTy(IntTy(),BoolTy()).toProlog()
'arrow(int, bool)'

(b) Write envtype: 10 points

In the file types.pl, fill in the implementation of the the Prolog predicate envtype(Env,X,T), where X is a variable, T is a type, and Env is a environment represented as a list of the form [[X1,T1],[X2,T2],...,[Xn,Tn]], where each [Xi,Ti] represents a binding stating that variable Xi has type Ti. In particular, envtype(Env, X, T) should be true if [X,T] belongs to Env and [X,T] is the first occurrence of a binding for variable X. For example:

?- envtype([[x,int],[y,bool]],x,T).
T = int ;
false.

?- envtype([[x,int],[x,bool]],x,T).
T = int ;
false.

?- envtype([[x,int],[x,bool]],x,bool).
false.

(c) Write type-checking rules: 20 points

In types.pl fill in the implementation of typeof(Env,E,T) which is true if the expression E has type T in the type environment represented by Env. Make sure to use envtype that you implemented in part (b). For example:

?- typeof([[x,int],[y,bool]],var(x),T).
T = int ;
false.

?- typeof([],bin(const(2),plus, const(3)),T).
T = int ;
false.

?- typeof([],bin(const(2),leq,const(3)),T).
T = bool ;
false.

?- typeof([],fun(x,bin(var(x),leq,const(4))),T).
T = arrow(int, bool) ;
false.

?- typeof([],fun(x,fun(y,ite(var(x),var(y),const(0)))),T).
T = arrow(bool, arrow(int, int)) ;
false.
?- typeof([],let(x,const(10),var(x)),T).
T = int ;
false.

?- typeof([],fun(x,let(y,var(x),bin(var(y),plus,var(y)))),T).
T = arrow(int, int) ;
false.

?- typeof([],app(fun(x,bin(var(x),plus,const(1))),const(19)),T).
T = int ;
false.
Once you have types.pl fully implemented, use the functions in nanoTypes.py to type check entire files. For example:
>>> from nanoTypes import fileToType, strToType
>>> strToType("true || false").toProlog()
'bool'
>>> strToType("fun x -> x").toProlog()
'arrow(_5394,_5394)'
>>> strToType("fun x -> x + 1").toProlog()
'arrow(int,int)'
>>> fileToType("nano/tests/t1.ml").toProlog()
'int'
>>> fileToType("nano/tests/t19.ml").toProlog()
'list(int)'

Problem #2: Decorators (decorators.py)

Here are some links on *args and **args tutorial, python manual. In the file decorators.py there is an example decorator, profiled and stub code for decorators that you will be writing. At the bottom of the file are many examples of decorated functions. The expected output for these functions is available here: decorators.out.

(a) 30 points

Complete the definition for the decorator traced. When the decorated function is called, the decorator should print out an ASCII art tree of the recursive calls and their return values. The format of the tree should be as follows:
  1. Print a pipe symbol followed by a space ("| ") for every level of nested function calls.
  2. Print a comma then a minus sign then a space (",- ") next.
  3. Print the name of the function being traced followed by an open parenthesis followed by the repr() of all of the arguments. Arguments should be seperated by a comma followed by a space (", "). After the normal arguments, print all the keyword arguments in the form keyword then equals sign then repr() of the value of the keyword argument. The keyword arguments should also be seperated by a comma followed by a space. Keyword arguments should be printed in the order returnd by dict.items().
  4. Next increase the nesting level and call the function itself.
  5. At the original nesting level, print a pipe symbol followed by a space ("| ") for every level of nested function calls.
  6. Print a backquote then a minus sign then a space("`- ").
  7. Finally, print the repr() of the return value.
The return value of the function should be return to the caller after all printing is complete. If an exception occurs in the funciton, the nesting level must be adjusted to the appropriate level where the exception is caught. See change for an example.

Once you have implemented the function, you should get the following behavior at the Python prompt:

>>> from decorators import *
>>> @traced
>>> def foo(a,b):
...    if a==0: return b
...    return foo(b=a-1,a=b-1)
...
>>> foo(4,5) 

,- foo(4, 5)
| ,- foo(b=3, a=4)
| | ,- foo(b=3, a=2)
| | | ,- foo(b=1, a=2)
| | | | ,- foo(b=1, a=0)
| | | | `- 1
| | | `- 1
| | `- 1
| `- 1
`- 1
1

(b) 30 points

Complete the definition of the memoized decorator. When the decorated function is called, the decorator should check to see if the function has already been called with the given arguments. If so, the decorator should return the value the the function returned when it was last called with the given arguments. If the function last threw an exception when called with the given arguments, the same exception should be thrown again. If the function has not been called with the given arguments, then call it and record the return value or exception. Then return the return value or raise the thrown exception.

Once you have implemented the function, you should get the following behavior at the Python prompt:

>>> from decorators import *
>>> from time import sleep
>>> @memoized
>>> def foo(a):
...    sleep(a)
...    return a
...
>>> foo(5)
# 5 second pause
5
>>> foo(5)
# practically instantaneous
5