Today's lab will be about:

• Sets: collections of unique elements.
• Maps: unique keys correlated with values.

To start with we have provided a lot of code; this week the code is in several packages.

• types: Contains all our interfaces. Read this first, then come back for descriptions of the rest.
• structures: Contains our data structures. First of all, we are using structures.basic.Int and structures.basic.Str to store int and String (because these classes implement ISame).
• procedures: Contains procedure objects, implementing familiar interfaces such as ICompare and ISelect, plus some newer ones. Most of these are "glue" code, you won't be touching them.
• algorithms: Provides static methods to process the more interesting data structures. Useful once you find the right tool, but you can always write your own if you'd rather.
• exceptions: Provides the exceptions raised by provided methods.
• htdp: This is our exercise for the day. See below.
• test: Contains the usual test harness with Examples and Interfaces classes.

Part 1: Using Sets

Let's look at the htdp.DrScheme class. We use it to simulate a homework assignment a student might be given in their first programming course. We want to process these homeworks and eventually grade them and check if they are cheating.

The first thing DrScheme provides is:

  public static ISet keywords()

We'll be seeing a lot of static methods in this lab. These methods belong to a class rather than to a specific object. To call this one, you would write DrScheme.keywords().

What does this produce? According to its purpose statement, all the keywords in the Beginning Student language level. These are the words we can pay the most or the least attention to on a student's homework, depending on how we want to evaluate it.

But what the heck is an ISet? You should look at this interface in package types.structures. Between the purpose statements, method headers, and any other interfaces that are mentioned, you should be able to piece together how it works.

Ask a TA if you're unclear of what part of the interface means. Take your time.

Done yet?

Let's look at the second thing in DrScheme:

  public static IList tokenList( String program )

This turns a program text into a list of tokens (our Str class). It produces an IList, another interface in types.structures. This one should be more familiar, but it doesn't have any voids in it like java.util.List. Instead, this interface works more like a Scheme list or an IRange.

Exercise 1

Now that you've seen ISet, IList, and DrScheme, let's write a program.

• Add a method to DrScheme which, given a program text as a single String, produces the list of all non-keyword tokens from that string.
• Add tests for this method to the Examples class. Feel free to remove all ridiculously long test cases I used to test my support code.
• Add a method to Interactions so you can type in a "program" interactively and have the non-keyword tokens printed back for you.

Part 2: Using Maps

Now we're going to strike out on our own. We want to represent homework submissions now. Each homework submission has to have a student's name (or possibly a list of teammates?) and a program. For this we'll want a new class Homework.

Next we get to using IMaps. We want to have a link between each submitter and their program. The class DrScheme needs a new method:

  // Given a list of Homeworks, produces an IMap
  // from submission names to ILists of tokens.
  public static IMap handins( IList homeworks )

What does this mean? Start by reading the interface for IMap. To produce your result, use the class SimpleMap in package structures.map. (Calling new SimpleMap() creates a new, empty map.)

Exercise 2

Moving right along. Let's write that IMap code.

• Add class Homework to structures.basic.
• Add the method handins to DrScheme. You may want to look up types.procedures.ICombine and algorithms.ListAlgorithms.foldLeft for this, but if another way seems more natural to you go for it.
• Add test cases to Examples.
• Add a method to Interactions which prompts the user for submissions (names and programs) until they decide they're done. Then call handins on the resulting IList and print out the result (all of our classes have toString() implemented).

Part 3: Sorted Maps

You may have noticed a couple things by now. (Or not.) One of the things we have in mind is that SimpleMaps print out their keys and values in very bizarre orders. If you build big enough maps, the keys and values change order as you add elements! (Guilty admission: it didn't have to be that way with these SimpleMaps. But it is that way with Java HashMaps, and we wanted you to see the phenomenon. So we faked it.) You may have also seen a HashCollisionException raised at some point if you picked unlucky test data. This also could have been avoided if we got really clever with our coding - but the first problem is real. Let's fix it!

The problem is that SimpleMap doesn't know anything about the order our keys should go in, so it picks something arbitrary. We want to use OrderedMap instead. But to construct OrderedMap, we need an ICompare (remember that interface? look it up in types.procedures.) to sort our keys (in this case, names on homeworks).

Exercise 3

Let's fix our unordered mess of homeworks.

• Write a new class in procedures.orderings implementing ICompare to compare your IMap keys.
• Replace your SimpleMap with an OrderedMap using the new ordering you have constructed.
• Run your old examples and tests - see how the output improves.

Part 4: Playing God (Ahem, I mean, TA)

We've got these homeworks, now what are we going to do with them? There are two interesting options: we can grade them to find the good ones, or we can catch cheaters to find the bad ones. There's a number of ways to go about each.

To grade the homeworks, we can give someone a grade on several metrics.

• If we value no-nonsense code, we can grade based on the ratio of keywords to non-keywords in the code.
• If we value descriptive variable names, we can grade based on the average length of each non-keyword token.
• If we have a solution in mind, we can verify that they have the same keywords in the same order as the solution.

To catch cheaters we have a few options as well.

• Students may cheat by using the same variable names. See if the set of non-keywords in a pair of programs are the same.
• Students may cheat by cutting and pasting similar code. Make a mapping from code words (not keywords) to their number of occurrences and compare.
• Students may cheat by using the same algorithm and just changing the names. Make a mapping from keywords to positions in the homework and compare.

Exercise 4

Using one of the above options, write either of:

  // Convert a names->homeworks mapping to a names->grades (Int) mapping.
  public static IMap grades( IMap homeworks )

  // Tells whether two homeworks are too similar.
  public static boolean cheating( Homework h1, Homework h2 )

As always, test your code in Examples and Interactions.

Part 5: There's a Part 5?

Because we couldn't let you leave just yet!

Challenge Exercise

Oh, what the heck. While you're here, implement the other method from above!

Now go home!