Homework 5: Recursion in Theseus

DUE: Mar 7th, 2002

In this homework you will explore how to write recursive Theseus plans. Recursion is used in Theseus as means for achieving loop-like control flow. Expressing loops in dataflow systems often requires a lot of ugly synchronization; however, looping with recursion results in shorter, elegant dataflow plans that do not require the same type of synchronization.
 
 
Given a large list of restuarants, suppose you would like to pick out a subset that has an average health rating of 90. You don't care which ones are in the subset (or that some might be lower than 90, while others are higher) - you just want a set that averages 90.

For example, given the following input set of restaurants and their health ratings. 

RELATION restaurants: place char, rating number
Burger King|81
Taco Bell|72
McDonalds|51
Subway|77
California Pizza Kitchen|95
Baja Fresh|90
Berris|92
Natalee|96
Edies|45
Chin Chin|89
Islands|84
Il Fornaio|87
Cheesecacke Factory|82
McCormick and Schmicks|85
Youngsusan|91
Lawrys|92
Wolfgang Pucks|81
Spago|90
Alto Palato|94
Ruths Chris Steak House|92
Chart House|93
Benihanas|88
Panda Express|67
You want the following result: 
Youngsusan, 91
Ruths Chris Steak House, 92
Alto Palato, 94
Lawrys, 92
California Pizza Kitchen, 95
Berris, 92
Natalee, 96
Chart House, 93
To do this, you are going to use recursion. The pseudo-code for what you want to do is shown below; your challenge is to translate it into a dataflow plan that runs in Theseus.

Your plan should have one input (that takes a restaurant list) and one output (the ones that average above 90). It should somehow call itself recursively to solve the problem presented above.

Pseudo-code

  1. Compute the average of the current list.
  2. If it is above 90 (you should hardcode this criteria), then return the list.
  3. Else, filter out those restaurants that are above the current average and go to 1 (these above average restaurants are now the "current list")
What to turn in
 
You should turn in the following:
Questions and comments
 
If you have any, contact Greg Barish.