CMSC 330, Spring 2013
Organization of Programming Languages
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 will also learn a little about programming language design.
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. You are allowed to write separate helper functions if you like.
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 * regexpFor example, here is a table of regular expressions, and their representation in this data type:
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:
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 stringFor example, here are several expressions and their representation in OCaml using the above data type:
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) listto represent an assignment of variable names (which are arbitrary strings) to integers. Here if an assignment contains the pair (x,n), then the assignment gives the variable named x the value n. The type assignment is a kind of associative list, and there are a number of functions for working with such lists available in the OCaml standard library, including List.assoc, List.mem_assoc, and others. See the OCaml library documentation for more information.
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:
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?
Hints and Tips
You may either submit over the web or under command line interface.
Submitting over the webPut your files (warmup.ml, regexp.ml, arith.ml, cmd.ml) in a zip archive. Don't put things under a directory but on the top level.
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 interfaceMake a directory and put your files in it. Download .submit and submit.jar in Project Files to the same directory. Then run the following command under that directory:
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:
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.