Programming Languages Assignment 6

Due: Friday May 6th

  1. (75 points)

    Implement the type inference algorithm for EF♭ in Caml. You are to use the book presentation (also given in class) as the "specification" of your implementation. Write a function typecheck which takes an expression and either returns the inferred type of F♭ program e or raises an exception if type inference fails.

    You need to implement the full algorithm except you do not need to implement the cycle detection algorithm - your checker can loop forever on programs with cyclic constraints (but only on such programs). Extra credit will be given for implementing cycle detection. Also you don't need to include let-polymorphism.

    Here are some suggestions:

    • Use the F♭DK and just modify your file fbinterp.ml to include typecheck and affiliated functions.

    • Types need an abstract syntax. Here is a good one: 

      type fbtype = TInt | TBool | TArrow of fbtype * fbtype | TVar of string

      The "T" prefixes above are for "type". 'a has the abstract syntax TVar "a".

    • Break down your implementation into the same phases as in the book:

      1. Generate the type τ \ E using the ideas in the type system (and also following the typechecker for TF♭ in the book),

      2. Perform the closure on E,

      3. Check the closure for immediate inconsistencies, and

      4. Substitute equations of E into τ to solve.

    • The E is a set of pairs (the type equations τ = τ'); the built-in Caml types such as Set or Map may prove useful in your implementation of this data structure.

    • In the closure outlined the book we assumed = was symmetric; in your implementation, one easy (but inefficient) method to achieve this is every time you add τ = τ' also add τ' = τ.

    • The "substitute to solve" phase is the same idea as your substitution function you wrote on terms, just do it on types.

    • Don't worry about efficiency. Do worry about correctness.

  2. (25 points)

    This question concerns concurrency. Please refer to Chapter 7 in the book.

    One application of the actor model is in the telephony switching system. Consider a case in which we have customers calling a phone bank of tech support staff. The different kinds of actors in this model include the customer, the tech support staff, and the phone bank itself. Customers initially only have access to the phone bank (because they only know the customer support phone number); the phone bank then relays them to an available staff member. A conversation ensues between the customer and the staff member until the customer's problem is resolved; afterward, the customer hangs up (terminates) and the staff member notifies the phone bank that he/she is available to take another call. This process continues until all customers have been helped.

    Our model starts by sending customers a message `broken(0). Customers then send a message `call(self) to the phone bank; the phone bank responds with `connect(staff), which connects the customer with a staff member. The customer then sends a message `help(self); the staff member replies with `answer(self). The customer replies `thanks(0). The staff member then sends `ready(self) to the phone bank. (Each message containing a non-zero value contains a reference to an actor.)

    You will write AF♭rVR code (F♭ with actors, rings, variants and records) which implements this actor model of the phone bank. You may also assume that this version of rings allows rings of zero length (which can be created by the syntax EmptyRing, as in Let x = EmptyRing In...) and that RingSize is available. You may also use Let Rec, Let...In, and the sequence operator ;. Your answer will be in the form of a function 

                Function numCustomers -> Function numStaff -> ...

    This function will, when applied to arguments, Create one phone bank and an appropriate number of customers and staff. It then sends the correct `broken(0) to each customer to get things started. You can imagine the initial state of the system being a startup message passed to a single actor whose only behavior is to evaluate your function.

    Here are some hints to get you started:

    • Before you write any actor code at all, stop to consider what states an actor may have and how an actor transitions from one state to another. It may be helpful to write a state transition diagram if you are familiar with UML.

    • There will often be more customers than support staff. As a result, your phone bank may not have an available staff member when a `call(0) is received. You will need to have some way of tracking which customers are currently "on hold".

    • It may be helpful to use Let...In in order to define certain utility functions. For instance, you might write a function which, when invoked with a reference to the phone bank, creates and returns a customer actor.

    • Remember to use the built-in AF♭ function Create to launch your actors. Also, remember to kick off the calls by passing `broken(0) to each customer.

    • Observe that the phone bank has to have a reference to all of the staff (so it can give customers references to them) and the staff member has to have a reference to the phone bank (so it can report that it is now available). Because this is a circular reference, you won't be able to make both entities have access to the other when they are defined. But you can make one of them expect an initialization message; for instance, you can write the staff member actor to expect an `init(phonebank) message as the first message it receives.

    • If something unexpected happens (like the customer sending a `profanity(0) message), you are permitted to diverge. No error handling is expected.

    • Because you are writing this code in AF♭rV (a language for which you do not have an interpreter), we will overlook the occasional syntax mistake (e.g., a missing semicolon). But the semantics of your program are important; make sure your program does what you think it does.

    • A relatively straightforward implementation of this problem comes to about 60 lines of code (give or take, depending on how you format it and where your like breaks are). You answer should not need to be hundreds of lines long, but any 20 line solution is probably missing something.