G711 F '05
Set 1
Set 2
Set 3
Set 4
Set 5
Set 6
Set 7
Set 8
Set 9

Problem Set 5: Interpreting Closures; Understanding Control (Somewhat)

Due date: 10/18 @ 5:00 pm

This problem set has two separate goals. The first is to add first-class functions to the programming language of Problem Set 3. The second is to explore CGI/Servlet scripting programming in preparation of the next section of the course.

Use the Pretty Big language and require the EoPL language.

Add first-class procedures to the small programming language of Problem Set 3:

 Block is: { Declarations* Statement+ }

 Declaration is: (Type Variable = Expression) 

 Type is one of: 
 -- bool 
 -- int 
 -- (Type -> Type)

 Variable is: alphanumeric sequence of characters 

 Expression is one of: 
 -- Variable 
 -- Number 
 -- (Expression + Expression) 
 -- (Expression > Expression) 
 -- (procedure (Parameter*) Block)
 -- (Expression Expression*)

 Parameter is: (Type Variable)

 Statement is one of: 
 -- (Variable = Expression) 
 -- (if Expression Block else Block)
 -- (while Expression Block)
 -- (return Expression)
    Constraint: a return-statement may occur 
    only inside of a procedure body
The new procedure expression form creates recursive closures; the application form applies them to arguments. Naturally, procedures now live in the same world as other variables. Otherwise the meaning of the language is like the one from Problem Set 4.

Problem 1:

Define a representation for expressed values in this language.

Define a representation for denoted values in this language.

Design an interpreter for this variant of the language. As for Problem Set 4, use an environment mapping variables to locations and a store mapping locations to values.

Compare in one paragraph the complexities of the two interpreters. What does this predict for reasoning about programs in this language?

Problem 2:

Design an imperative interpreter for this variant of the language. That is, use an environment that maps variables to mutable Scheme records that contain expressed values.

Compare the implementations in Problem 1 and Problem 2.

Problem 3:

Implement a booking service for a bed-and-breakfast in your favorite CGI/Servlet programming language.

The College provides the CCIS CGI server, a safe and secure environment for developing and deploying interactive web programs. Please read the documentation, register for an account, and start experimenting.

The booking service allows people to view a list of available rooms in a hotel, to choose a room and view its detailed description, and to register a room. So here are your tasks:

  1. Make up a list of rooms with unique names, prices, and random descriptions. Don't overwork yourself. Some ten or twenty rooms are enough. Show imagination with the descriptions but don't make them longer than a line or two.
  2. Design and implement a simple, non-persistent room-management module (aka "model") that adds rooms, removes rooms upon registration, returns available rooms and whatever else you may need.
  3. Design and implement a CGI "view" that manages individual consumer sessions. The typical sessions consists of three steps:
    1. First, the consumer demands and receives the list of available rooms. Each entry comes with a link for each that allows "detail viewing".
    2. Second, the consumer will look at an individual room. This page contains a "book me" link so that the consumer can register for the room.
    3. Third, the registration page collects customer and payment information. For now just collect a first and a last name from the consumer.
    4. If a consumer successfully goes through the entire dialog, display a receipt page that thanks the customer and displays the name of the room just reserved.
  4. Design and implement a second CGI "view" for the hotel manager. It displays all rooms, including those that are currently registered. Allow the manager to un-register an individual room.
  5. If you believe it is helpful to first design and implement a GUI or console-based view, do so. If you do do, include the design with your submission; you won't get any credit but it may help Alex find flaws, if any, in your code.
We will ask you to demo your code to Alex during a set time. Be prepared to spend some 10 minutes with him running your web program.

last updated on Tue Jun 9 22:21:18 EDT 2009generated with PLT Scheme