Project 3

Updates:

• Mar 15. Clarified that the sublist function can return anything if n or m are outside the range of the list.
• Mar 11: got rid of potential arithmetic overflow in public_prod.ml
• Mar 11: fixed a problem in public tests; if you downloaded the public tests before 10am, please update
• Mar 11: updated public tests; details about testing Part 4 in "Hints and Tips"
• Mar 10: public tests and .submit are available

Introduction

In this project, you will gain experience writing code in OCaml. The focus of this project is getting used to OCaml's syntax, using recursion to work with lists, and using data types. You may also learn a little about programming language design.

Project files

• Code skeleton
  • warmup.ml
  • regexp.ml
  • arith.ml
  • cmd.ml
• Files for command line submission (see "How to Submit" for usage)
  • .submit
  • submit.jar
• Public tests: copy your *.ml into the p3_public_tests directory and run the tests.
  • p3_public_tests.zip

Part 1: List Exercises

Write your solutions to this part in the file warmup.ml.

Implement the following functions in OCaml. Do not use any functions in the List or Array modules, i.e., write every function from scratch using just list notation [...], ::, and pattern matching. You should also not use the list concatenation operator @ from Pervasives.

• Write a function prod l : int list -> int that returns the product of the elements of l. The function prod should return 1 if the list is empty.
• Write a function add_tail l e : 'a list -> 'a -> 'a list that takes a list l and a single element e and returns a new list where e is appended to the back of l. For example, add_tail [1;2] 3 = [1;2;3].
• Write a function fill x n : 'a -> int -> 'a list that returns a list containing n copies of x. For exampe, fill 42 3 returns [42; 42; 42].
• Write a function rindex l e : 'a list -> 'a -> int that takes a list and a single element and returns the position of the last occurrence of that element in the list (indexed by zero). You should return -1 if the element is not in the list.
• Write a function even_elts l : 'a list -> 'a list that takes a list and returns a new list containing the 0th, 2nd, 4th, etc elements of l. For example, even_elts ['a';'b';'c';'d';'e'] should return ['a';'c';'e'].
• Write a function sublist n m l : int -> int -> 'a list -> 'a list that returns a new list containing the elements of l starting with element n, inclusive, and ending with element m, inclusive. For example, sublist 2 4 ['a'; 'b'; 'c'; 'd'; 'e'; 'f'] should return ['c'; 'd'; 'e']. Your function may do anything if n>m or if n or m are out of range for the list.
• Write a function rotate n l : int -> 'a list -> 'a list that returns a new list containing the same elements as l, "rotated" n times to the right. For example,
  • rotate 0 [1;2;3;4] should return [1;2;3;4]
  • rotate 1 [1;2;3;4] should return [4;1;2;3]
  • rotate 2 [1;2;3;4] should return [3;4;1;2]
  • rotate 3 [1;2;3;4] should return [2;3;4;1]
  • rotate 4 [1;2;3;4] should return [1;2;3;4]
  • etc.
• Write a function unzip l : ('a*'b) list -> ('a list)*('b list) that, given a list of pairs, returns a pair of lists with the elements in the same order. For example, unzip [(1, 2); (3, 4)] = ([1; 3], [2;4]).
• Write a function app_int f m n : (int->'a)->int->int->'a list that returns the list [f m; f (m+1); ...; f n]. It should return the empty list if n < m.

Part 2: Regular Expressions, again!

Write your solutions to this part in the file regexp.ml. From here on out in the project, you can freely use any part of the OCaml standard library.

In Project 2, you developed code to implement regular expressions as NFAs and DFAs. One interesting design choice in that project was the way regular expressions were represented, which was as a set of classes REEpsilon, REConst, REStar, REUnion, and REConcat. Consider instead representing regular expressions in OCaml using the following data type:

type regexp =
    REEpsilon
  | REConst of char
  | REStar of regexp
  | REUnion of regexp * regexp
  | REConcat of regexp * regexp

For this part of the project, implement the functions check(e) and trans(e) again (yes, you read that right!). These functions should have the following types:

• check : regexp -> bool
• trans : regexp -> (char * regexp) list

The list of pairs returned by trans should be unique, i.e., it should not contain duplicates.

After you're done implementing these functions in OCaml, recall your experience writing them in Ruby. Which language were they easier to write in? Do you prefer having the code for check and trans grouped in one unit, as they are in OCaml, or spread among different classes, as they were in Ruby? Did the OCaml type system make it easier or more difficult to implement them? You don't need to submit your answers to these questions, but please do consider them.

Part 3: Arithmetic Expressions

Write your solutions to this part in the file arith.ml.

In this part of the project, you will work with a data type that represents abstract syntax trees for arithmetic expressions that may contain variables:

type expr =
    Int of int
  | Negate of expr
  | Plus of expr * expr
  | Minus of expr * expr
  | Mult of expr * expr
  | Var of string

If an arithmetic expression has a variable, then we can only decide what an expression "means" if we know the values of its variables. We will use a type

  type assignment = (string * int) list

• Write a function no_mult : expr -> bool that returns true if the expression contains no occurrence of a value constructed with Mult, and false otherwise. For example, no_mult should return true for e1, e2, e4, and e5, and false for e3 and e6.
• Write a function vars_of : expr -> string list that returns a list containing the names of variables used in the expression. For example, vars_of e5 should return ["x"; "y"], and vars_of e2 should return []. The function vars_of should return a list in which each variable appears at most once, i.e., you should remove duplicates.
• Write a function eval : assignment -> expr -> int that returns the value an expression evaluates to. For example, here are some results of eval:
  • eval [] e2 returns 55
  • eval [] e4 returns 6
  • eval [("x", 3); ("y", 4)] e5 returns 7
  • eval [("foo", 10)] e6 aborts with an error
  • eval [("foo", 10); ("x", 3); ("baz", 2)] e6 returns 50
  If eval a e is called such that a variable in e does not occur in a, your program should use raise Not_found to throw an exception. In the case the same variable name appears multiple times in eval, your function should use the first or left-most assignment of the variable in the assignment.
• Write a function subst : expr -> (string * expr) list -> expr such that expr e s returns a new expression that is identical to e, except variables occurring in e have been replaced according to s. Here a pair ("x", e) occurring in s indicates that Var "x" should be replaced by the expression e. For example, subst e6 [("foo", Int 4)] should return Mult(Int 4, Plus(Int 3, Var "baz")). Note that your subst function should perform just one "level" of substitution. For example, subst (Plus(Var "v", Int 3)) [("v", Negate (Var "v"))] should return Plus(Negate (Var "v"), Int 3).

Part 4: Language of Commands

Write your solution to this part in the file cmd.ml.

Finally, consider embedding arithmetic expressions in a simple programming language consisting of commands:

type cmd =
    Skip
  | Assign of string * expr
  | Seq of cmd * cmd
  | IfNonZero of expr * cmd * cmd
  | WhileNonZero of expr * cmd

Since commands work with variables, we always evaluate commands with respect to some assignment (the same type as in Part 3), and executing a command produces a new assignment. For this last part of the project, you must write a function exec : assignment -> cmd -> assignment that, given the current assignment of variables to values, executes the command and returns a new assignment of variables to values. Calling exec a c should do the following, based on the command c:

• Skip does nothing, returning a.
• Assign("x",e) evaluates e under the assignment a, and then returns a new assignment that is the same as a, except now "x" is mapped to the result of the evaluation.
• Seq(c1, c2) executes c1 under assignment a, producing a new assignment a1; executes c2 under assignment a1, producing a new assignment a2; and then returns a2.
• IfNonZero(e1,c1,c2) evaluates e1 under assignment a. If evaluation returns a non-zero value, then c1 is executed under assignment a, and otherwise c2 is executed under assignment a.
• WhileNonZero(e,c) evaluates e under assignment a. If that returns zero, assignment a is returned. Otherwise, c is executed once under assignment a, producing a new assignment a'. Then WhileNonZero(e,c) is executed under assignment a'.

Hint: Above we've basically just written the exec function for you, except we used English instead of OCaml. So all you need to do is translate that into OCaml. But you should also try to understand why the execution cases above make sense. Think about the following questions: If we added a form Block of cmd list, where the list contained many commands in sequence, how would you execute a Block? What about adding an Unless conditional form? Or a For loop, or a RepeatUntil loop? What other language features would be easy to add to this language of commands?

Submission

You may either submit over the web or under command line interface.

Submitting over the web

Submit your archive directly to the submit server by clicking on the submit link in the column "web submission".

Next, use the submit dialog to submit your schedule.rb file directly.

Select your file using the "Browse" button, then press the "Submit project!" button.

Submitting in command line interface

The first time you submit this way you will be asked to enter your directory ID and password. All files in the directory (and its subdirectories) will then be put in a jar file and submitted to the submit server. If your submission is successful you will see the message:

Hints and Tips

• Start this project early! For many students, learning OCaml requires quite a leap in the way they approach programming, and you need to give yourself enough time to make that leap.
• When testing Part 4, we will plug in a correct arith.ml. While this should help make grading equitable, it also means you need to be extra careful not to change any of the interfaces we supply you with, since we will be relying on those in grading.

Academic Integrity

The Campus Senate has adopted a policy asking students to include the following statement on each assignment in every course: "I pledge on my honor that I have not given or received any unauthorized assistance on this assignment." Consequently your program is requested to contain this pledge in a comment near the top.

Please carefully read the academic honesty section of the course syllabus. Any evidence of impermissible cooperation on projects, use of disallowed materials or resources, or unauthorized use of computer accounts, will be submitted to the Student Honor Council, which could result in an XF for the course, or suspension or expulsion from the University. Be sure you understand what you are and what you are not permitted to do in regards to academic integrity when it comes to project assignments. These policies apply to all students, and the Student Honor Council does not consider lack of knowledge of the policies to be a defense for violating them. Full information is found in the course syllabus---please review it at this time.