Problem Set 3

home work!

Programming Language More Basic Programming, Plus Redex Modeling

Purpose The goal of this problem set is to demonstrate additional competence in programming. In addition, the problem set requires some first Redex modeling skills.


Problem 1 Fix your memo from problem set 1 in response to the editorial criticism.

Problem 2 Develop a Redex model of DADL’s grammar.

Design the metafunction traverse, which mimics a traversal of a DADL specification. See problem set 1 for a specification of a traversal.

Problem 3 Most programming languages, including DSLs, impose conditions on programs that go beyond those of the context-free grammars. Checking these conditions is often called typed checking, even if the properties checked do not look like regular types.

Your task is to equip your solution from problem set 1, problem 2 with a "type checker" for DADL. This "type checker" ensures that a DADL specification satisfies the following conditions:
  • all rooms have unique names

  • no room specifies an exit to itself

  • no room specifies two exits in the same direction going to the same room

  • the player’s location specifies an actual room

  • the rooms are properly connected to each other, that is, if room x specifies a south-bound door to room y, the latter room must come with a north-bound door going to x.

Here is a specification that violates all of these conditions:

  <configuration name="matthias" at="living-room">

    <room name="living" description="piano">

      <exit direction="east" to="sitting" />


    <room name="master" description="bed">

      <exit direction="east" to="master" />

      <exit direction="west" to="master" />


    <room name="sitting" description="piano">

      <exit direction="east" to="dining" />

      <exit direction="north" to="living" />

      <exit direction="east" to="dining" />


    <room name="dining" description="piano">

      <exit direction="west" to="sitting" />


    <room name="living" description="pillows">

      <exit direction="south" to="kitchen" />



Add the type checker to your program from problem set 1. When the type checker discovers a violation, your program must output

  type error!

to standard output and shut down.

Deliverable Email a tar.gz bundle to my CCS email address whose name combines the last names of the pair in alphabetical order. The tar bundle must contain a single directory—with the same name as the tar ball—with a README.txt file, a memo1.pdf file, a problem2.rkt Redex file, and an executable file (for your choice of an "xyz" extension).

The README.txt file must start with the following lines:

  ;; NameOfPartner1, NameOfPartner2


When I unpack the bundle on the standard departmental LINUX boxes (login-linux is a good example), I expect to cd into this directory and run the solution as

  $ ./ < 3-example1.xml | diff - 3-output1.txt

where 3-example1.xml and 3-output1.txt are files I will supply.