Due date: 11/16 @ at the beginning of class

DRAFT

Purpose: The goal of this problem set is to develop an implementation of the CEK machine for the simple-lang language that lives up to the specification of problem set 9.

---

Background:

The SimpleLang.com start up has decided to offer a new web service, namely, an evaluator for an XML version of the simple-lang programming language. Their star language designer has used Redex to create the language, its CEK machine, and its rendering as an XML dialect. For the latter part, see 10-provided.rkt. Since the CEK machine is clearly the fastest implementation yet, the company had decided to base its first implementation on this specification.

Problem:

Implement the CEK machine for the simple-lang language. Since the implementation must run on a cloud server and connect to the web via CGI, it must accept simple-lang programs in XML form from the standard input port and deliver it to the standard output port, also in XML form.

Here would be a sample interaction:

  $ ./evaluate < in > out 

where in is the input file

  <block>
    <declarations> <var label="x" /> <num val="0" /> </declarations>
    <assign> <var label="x" /> <pls> <var label="x" /> <num val="1" /> </pls> </assign>
  </block>  

and evaluate creates the out file with content equivalent to

  <block>
    <declarations> <var label="x" /> <num val="1" /> </declarations>
  </block>  

The evaluate program must live up to the CEK machine specification. That is, if i is a simple-lang program and o its expected result block, then running evaluate on a XML representation of i must produce an XML representation of o.

Use any language of your choice.

Hints (1) My test harness will enforce the specification requirement automatically. (2) Your evaluate program should in principle have the following approximate shape:

  void main() {
    State s = read_XML_from_standard_input(); 
    while (! s.isFinal()) do 
      s = s.nextState();
    s.write_as__XML_to_standard_output();
  }

The code is in C++/Java-ish pseudo code to accommodate the majority of students in this course. You should not feel obliged to use such a language, however. There are no restrictions as long as evaluate runs as a pure batch program (without access to a display) on the College's login-linux machine.

Deliverable:

Send in a single tar file. Its name should consist of the two last names in alphabetical order separated with a hyphen; its suffix must be .tar.

Your tar file must unpack into a directory that

1. either contains an executable file called evaluate,
2. or a Makefile so that running make creates the executable.

In addition, the directory should contain a file called README that starts with the following two lines:

  NameOfPartner1, NameOfPartner2 
  email@of.partner1.com, email@of.partner2.com

appropriately instantiated of course. The README file should explain how to find the source code for evaluate in the directory.