CMSC 330, Fall 2008
Organization of Programming Languages
In this project, you will build some simple functions to show the relationship betewen locking and message passing, and you will reimplement part 2 from project 5 using Concurrent ML-style message passing concurrency (the Event module) in OCaml instead of shared memory concurrency in Ruby.
For this project, you will probably want to look at the Thread library documentation from the OCaml manual. To make a version of the OCaml top level in which these functions are available, run the following command:
ocamlmktop -thread unix.cma threads.cma -o mytop
This creates a program mytop, which is the OCaml top level, except threads are enabled. To use it, run
./mytop -I +threads
To save everyone from having to build mytop themselves, you can run
which is already in your path if 330submit is in your path.
Part 1: Encodings
As we mentioned in class, message passing and locking are both representable using the other. In this part of the project, you will demonstrate this very concretely by developing two encodings.
First, in the file channel.ml, fill in the implementation of the Channel module, which has the following signature:
type 'a t val new_channel : unit -> 'a t val send : 'a t -> 'a -> unit val receive : 'a t -> 'a
Here new_channel makes a new channel; send sends a value over a channel, blocking until a receiver tries to receive it; and receive receives a value from a channel, blocking until a sender sends something over the channel.
In your implementation of this module, you must use OCaml's Mutex and Condition modules, and you must not use OCaml's Event module. In this way, you will show that you can build channels using locks. Hint: You can probably just port the producer consumer example code from lecture, except you will need to make sends block until a receiver is ready.
Second, in the file lock.ml, implement the Lock module, which has the following signature:
type t val create : unit -> t val acquire : t -> unit val release : t -> unit
Here create makes a new lock, which can be acquired and released by calling the appropriate functions. In your implementation of this module, you must use OCaml's Event module, and you must not use OCaml's Mutex or Condition modules. Your locks do not have to be reentrant, i.e., it is OK to block if the same thread tries to acquire a lock more than once. Your code can also behave arbitrarily if a thread tries to unlock a lock it doesn't hold.
Part 2: The Simulation
Finally, implement exactly the same simulation as project 5, with the same output. Specifically, write a function
simulate : string list list -> unitthat accepts a description of the riders' paths through the metro, and then runs the simulation, printing the results to standard output. There is a sample input in the file metro.ml we've supplied you with to start out.
You can get a (very minimal) skeleton for this project at
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.