Programming Languages

Actors

Due on Friday, May 4th at 11:59 PM. This is a team lab. You may work alone or you may work with a partner. If you’d like to work with a partner, make sure to indicate your preferred partner using Teammaker and be familiar with the Partner Etiquette guidelines. You may discuss the concepts of this lab with other classmates, but you may not share your code with anyone other than course staff and your lab partner(s). Do not look at solutions written by students other than your team. If your team needs help, please post on the Piazza forum or contact the instructor. If you have any doubts about what is okay and what is not, it’s much safer to ask than to risk violating the Academic Integrity Policy.

Overview

This lab involves writing some actor-based programs in a variant of F♭; the interpreter is provided. Doing so will yield experience with this alternate form of concurrency. As usual, you will use Teammaker to form your repositories.

AF♭V

This assignment is to be written in an extended version of AF♭V; you will find the interpreter in your starting repository. Despite its name, AF♭V actually has a number of syntactic and semantic features which are listed here.

Actors

First and foremost, AF♭V supports concurrency via the actors discussed in the book and in class. Actors may be created via the Create call, which yields an actor address. Actors may be messaged by sending values to that address using <-.

An AF♭V program is an expression just like every other F♭-based program. This expression typically creates a series of actors and sends some initial messages to them. The result of evaluation is the result of that initialization expression, which is printed by the interpreter at the end of the program. Between the evaluation of the initial expression and the printing of the resulting value, however, messages are delivered from the message queue to the actors until no more messages exist in the queue.

Match

As expressed by the name of the language, AF♭V supports Match expressions. These work just like F♭V from the textbook: variants are created via e.g. `Name 0, variants need not be declared, and Match expressions only match variants.

Pairs and Lists

The AF♭V interpreter also supports pairs and lists. Pairs are created via the OCaml-like syntax e.g. (4, True). Lists are created via semicolon-separated bracket-delimited lists ([1;4;7]) or via the empty list and OCaml-like constructor (1::4::7::[]).

Note that neither of these data types can be matched using a Match expression, nor can they be destructed using a Let expression (since F♭ Let expressions only bind to a single variable, not a pattern like in OCaml). In order to access the contents of a tuple, AF♭V provides Fst and Snd expressions; for instance, Fst (4, True) evaluates to 4. For lists, the Head and Tail expressions are used: Tail [1;4;7] evaluates to [4;7].

Strings and Printing

The AF♭V interpreter provides string literals such as "hello". The only operation defined for strings is =, which determines whether two strings are equal. No operations will concatenate strings, nor is it possible to convert other data to or from strings.

This AF♭V interpreter also provides output via the Print expression. All values can be printed; this includes integers, booleans, strings, lists, pairs, and even actor addresses. For instance, we might write Print [1;2;3]. After the side-effect of printing, Print expressions always evaluate to False.

As a result of this side-effect behavior, AF♭V also supports the sequence operator ;. Note that there is no string formatting or concatenation in this language. As a result, a sequence of prints may be necessary to print a specific message. For instance, we might write:

Print "I have ";
Print apples_count;
Print " apples.\n"

Don’t forget the newline!

Using the Interpreter

The AF♭V interpreter may be launched on the command line via ocamlrun ./afbv.byte from within your assignment repository. This binary works just like the reference binaries provided in previous assignments: it will execute the contents of a file if one is provided as an argument and otherwise will take input from the user. In any case, the ;; delimits the end of the expression to be evaluated and all expressions are evaluated in isolation.

The AF♭V interpreter provides special behavior to support debugging actor-based programs. The --show-messages flag will cause the interpreter to print a message each time a message is delivered to an actor; the --show-states flag will cause each global state to be printed as the program executes. The --deterministic flag may also be useful in debugging behavior. Ordinarily, the AF♭V interpreter delivers messages in an arbitrary order; the --deterministic flag will cause the same program executed twice to deliver its messages in the same order both times. This can be useful if you are trying to track down a bug that has to do with message delivery.

A Note About Syntax

As you develop your code for this assignment, there are two important development practices to follow:

• As with previous assignments, write small amounts of code and make sure it parses as you go. The parser produces unhelpful error messages, so the easiest way to catch a syntax error is to check your syntax often.
• Use parentheses generously. There are a number of parse precedence issues that may be somewhat surprising (e.g. in If b Then 4 Else (Print 5; 0), the parentheses are necessary; otherwise the expression always evaluates to zero) and the easiest way to avoid this issue is to be explicit about how things are grouped.

The lab repository contains an updated Atom syntax highlighting plugin for F♭. You are encouraged to use this: syntax highlighting will also assist you in avoiding syntax errors.

Part 1: Even-Odd Countdown

The first part of this assignment requires you to write a program in countdown.afbv. This program should print the numbers from 10 down to 0 (inclusive), each one on its own line. At the end of the program, the string "End" should be printed.

The caveat is the order in which these values should be printed. All even numbers should be printed in descending order and all odd numbers should be printed in descending order. However, the relative ordering between even and odd numbers must be non-deterministic. For instance, one run of the program may print

10
9
7
8
5
6
4
2
0
3
1
End

while another run may print

9
10
7
8
6
4
2
0
5
3
1
End

Your program is required not to print anything else.

To accomplish this, you will need to create two actors and have them message themselves to produce the countdown behavior. The "End" string can simply be the result of your initialization expression. Note that both actors can be created using the same function definition; you don’t need to write any redundant code. A canonical solution to this problem may be as little as twenty-five lines of code.

Part 2: Phone Bank

The second part of this assignment requires you to write a program in phone.afbv. This program will simulate the behavior of a tech support system in which the support staff field customer calls and help them fix things that are broken. Our model includes three kinds of actors: the customers, the 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 the customer to an available staff member. The customer and staff member then have a conversation which resolves the customer’s issue and the staff member notifies the phone bank that the conversation is finished and that the staff member is ready to receive another customer. This process continues until all customers have been helped.

In our simulation, this process works as follows:

• The customer receives the message `broken(0) (from the initialization code).
• The customer responds by sending a message `call(me) to the phone bank.
• The phone bank responds with the message `connect(staff) to connect the customer with a staff member. That staff member must not be assigned to any customers at the moment.
• The customer sends the message `help(me) to that staff member.
• The staff member responds by sending `answer(me) back to the customer.
• The customer sends the message `thanks(me) to the staff member.
• The staff member prints a message of the form "Staff member @10 completed call with customer @7" to the terminal and then sends a `ready(me) message to the phone bank.

In the above steps, each me value is the address of the actor sending the message while the staff value is the address of the staff member selected by the phone bank. 0 is used as the value in a message when no other information is necessary.

Of course, at any given time, any number of customers and staff members may be at any of these steps during the execution of the program. The role of actors in this program is to coordinate that process.

Requirements

Here are some requirements for your program:

• As with the previous program, the application must run non-deterministically. The order of messages should be different each time the program is run (unless --deterministic is passed on the command line).
• Your program must define the runSimulation function provided in the starter file. It must use the parameters of that function to control the number of customers and staff members in the simulation.
• The output message must be of the form "Staff member $X completed call with customer $Y" where $X and $Y are the actor addresses of the staff member and customer, respectively. Your program must not print anything else.
• Your program must operate correctly for any positive values of customers and support staff. It’s possible that there may be more staff than customers or that there may be more customers than staff. No staff member should ever be assigned two customers at once.
• You may not use a “busy-wait” loop to address cases in which there are insufficient support staff. In this actor model, such a busy-wait loop takes the form of sending yourself a message you’re not prepared to handle (in the hopes that a different message will be delivered instead).
• You are not required to handle invalid messages. If this were somehow to happen (e.g. the support staff member receives a `profanity(0) message from a customer), your program’s requirements are undefined and your program may even diverge.

Suggestions

Some amount of design is necessary to complete this program. Here are some thoughts that may be helpful:

• Before writing any code, make a list for each actor of the messages that the actor will receive, how the actor will respond, and what kind of local data the actor needs to preserve (if any).
• Note that the phone bank and the support staff are aware of each other. The initialization code can’t create a referential cycle in one step, so we have to tie the knot using the actor system. For instance, you could create your phone bank actor before creating your support staff actors; then, each support staff actor could send `ready(self) to the phone bank to start the simulation.
• You’ll need some way of keeping track of which support staff members are currently available as well as a way of keeping track of which customers are currently waiting for help.
• Once all of your actors are created, remember to send `broken(0) to each customer to start the simulation.

Here is a sample run of the program using eight customers and two support staff:

Staff member @11 completed call with customer @4
Staff member @10 completed call with customer @8
Staff member @10 completed call with customer @7
Staff member @11 completed call with customer @2
Staff member @11 completed call with customer @6
Staff member @10 completed call with customer @9
Staff member @11 completed call with customer @5
Staff member @10 completed call with customer @3
Finished

Here is another run with the same parameters:

Staff member @10 completed call with customer @2
Staff member @11 completed call with customer @9
Staff member @11 completed call with customer @5
Staff member @10 completed call with customer @6
Staff member @10 completed call with customer @4
Staff member @11 completed call with customer @7
Staff member @10 completed call with customer @8
Staff member @11 completed call with customer @3
Finished

Note that the customers are not helped in any specific order and the staff members do not complete the calls in a specific order with respect to each other.

A relatively straightforward implementation of this program takes about one hundred lines of AF♭V code, though your answer may be of a different size.

Deliverables

Only the contents of countdown.afbv and phone.afbv will be graded for this assignment. Code containing syntax errors or other flaws which prevent it from being run will not receive full credit. As always, please ask your instructor if you have any questions!

Submitting

To submit your lab, just commit and push your work. The most recent pushed commit as of the due date will be graded. For more information on when assignments are due, see the Policies page.

If You Have Trouble…

…then please contact your instructor! Piazza is the preferred method, but you can reach out via e-mail as well. Good luck!