►7400:   i  PPL
▼Problem Sets
    ← prev  up  next → 

Problem Set 3

home work!

Topic More Basic Programming, Plus Redex Modeling

Due Friday, February 12, 2016 at 1pm

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.

image

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

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

Design the metafunction findflights, which finds a flight plan from origin to destination for an FSL configuration. See problem set 1 for a specification of a flight plan.

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 type 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 FSL. This "type checker" ensures that an FSL specification satisfies the following conditions:

  • the origin is not the same as the destination

  • the origin and destination are actual airports

  • all airports have unique airport codes

  • no airport has a flight to itself

  • no airport specifies two flights with identical airline and flight numbers (to the same airport or different airports)

  • the airports are properly connected to each other, that is, if airport PQR has a flight on airline AL to airport XYZ, then the latter must have a flight on airline AL going to PQR.

Here is a specification that violates all of these conditions:

  <flightsearch origin="LAX" destination="ORD"

                airline="AA">

    <airport code="BOS" name="Boston Logan">

      <flight airline="UA" flightnum="139" to="ORD" />

      <flight airline="DL" flightnum="211" to="PDX" />

      <flight airline="DL" flightnum="211" to="ORD" />

      <flight airline="AA" flightnum="409" to="BOS" />

    </airport>

    <airport code="ORD" name="Chicago O'Hare">

      <flight airline="AA" flightnum="138" to="BOS" />

      <flight airline="DL" flightnum="440" to="BOS" />

    </airport>

    <airport code="BOS" name="Boston Something">

      <flight airline="DL" flightnum="212" to="BOS" />

    </airport>

  </flightsearch>

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 3.xyz (for your choice of an "xyz" extension).

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

  ;; NameOfPartner1, NameOfPartner2

  ;; email@of.partner1.com, email@of.partner2.org

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

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

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

    ← prev  up  next →