CSC 324 Assignment 3

  1. Throwing exceptions in Scheme

    Your goal is to create a simple exception throwing system using Scheme continuations. We want to be able to write guarded sections of code where we can throw exceptions to an exception handler.

    (define (sum list-o-nums)
      (throwing
       (((throw error) (for-each display (list "Error: " error "\n"))))
       (let sumloop ((l list-o-nums))  
         (cond ((null? l) 0)  
               ((number? (car l)) (+ (car l) (sumloop (cdr l))))  
               (else (throw "not a number"))))))
    

    It may be that we want to handle various type of exceptions differently, so we want to be able to define several handers for the same piece of guarded code.

    (define (average list-o-nums)
      (throwing
       (((throw-nan term) (for-each display (list "Not a number: " term "\n"))) 
        ((throw-div0) (display "Divide by zero exception\n")))
       (let ((len (length list-o-nums))) 
         (if (eq? len 0) (throw-div0)) 
         (/
          (let sumloop ((l list-o-nums))  
            (cond ((null? l) 0)  
                  ((number? (car l)) (+ (car l) (sumloop (cdr l))))  
                  (else (throw-nan (car l)))))  
          len))))
    

    Write a syntactic form named throwing that allows for a guarded section of code. Several handlers can be installed (such as throw), which can be called to "throw" an exception from the guarded code. Execution of the guarded section should be aborted if an exception is thrown.

    To be precise, throwing takes a list of handlers to be installed, and one or more expressions to be guarded. Each handler is specified as list, whose first element is the handler name and any formal arguments, followed by a body of one or more expressions. Put your solution in a file called throwing.scm.

  2. Mimicking a sequence using C++

    You'll write a program for `mimicking' any sequence of values. The idea is to analyze a given sequence for local properties (like "what number should come next?"), and create a new sequence that also has these local properties. We could mimic a sequence of bits, a sequence of numbers, or a sentence (a sequence of words). Advanced forms of this technique have even been used to write entire scientific papers (which even seem to get accepted into conferences).

    Consider for example the following sequence of digits:

    1 3 2 1 3 3 3 1 3 2 3 3
    
    We start mimicking the sequence by picking a "window size" (let's choose two for now) and copying that many digits from the beginning:
    1 3
    
    Now we look through the original sequence to see what follows the pair 1 3 (regardless of where it occurs). There's a 2/3 chance of 1 3 being followed by 2, and a 1/3 chance of it being followed by 3. We choose the next digit in our mimicking sequence randomly with these odds. One possible outcome is:
    1 3 3
    
    Now we consider what follows the pair 3 3. There's a 1/3 chance it's a 3, a 1/3 chance it's a 1 and a 1/3 chance it's the end of the sequence. So our mimicking sequence might become:
    1 3 3 1
    
    Looking at the pair 3 1, the only possible next digit to choose is 3:
    1 3 3 1 3
    
    We continue this process. Here's one possible way it might end up:
    1 3 3 1 3 2
    1 3 3 1 3 2 1
    1 3 3 1 3 2 1 3
    1 3 3 1 3 2 1 3 3
    
    And this time the random choice for 3 3 ended the sequence.

    Implementation

    You will make two templated functions chop and choose, a templated class Special, and a main function.

    chop and choose

    The function chop preprocesses a sequence using a given window size. It takes each segment whose length is the window size, and records the element immediately after it. For our example sequence and a window size of 2, we have the following table.

    1 3  |  2 3 2
    3 2  |  1 3
    2 1  |  3
    3 3  |  3 1 END
    3 1  |  3
    2 3  |  3
    

    For the table, use std::map< list<E>, vector<E> >, where E is the type of value in the sequence. Store the segments as lists, and the set of elements that can come after them in an associated vector. You access entries in a map using the overloaded operator []. Here's an example:

      map<int, int> m;
      m[3] = 5;     // creates an entry
      m[3] = 4;     // overwrites it
      cout << m[3]; // displays it
    

    The vector class also allows access via operator [].

    The list class is another kind of collection. It doesn't allow random access the way vector does, but it has the methods push_back(val) and pop_front(). (Can you deduce how the two classes are likely implemented?)

    The function choose takes a segment and randomly chooses one of the associated elements from the table made by chop.

    Examine the starter code to determine more information about chop and choose.

    Special

    You need a special value to indicate the end of a sequence. Make a templated class Special<T> for objects that can either hold a given T value or else indicate they're special. Examine the starter code to determine more information about Special.

    One aspect not clear from the starter code is that Special needs an operator <. It turns out that map does its lookup using binary search, so list<E> must implement operator <, which means that E must implement it. Assume T implements operator <, and use that to compare regular elements. For a consistent and general comparison of a special element and a regular one, consider the regular element smaller than the special one. Consider two special elements equal, so neither is smaller than the other.

    main

    This function takes a command line argument for the window size, and then reads in words separated by whitespace. It considers the words as elements of a sequence, and prints out a mimicked version (much like the function test in the starter code). This is fun: when you're done you can take any text and make a stream-of-consciousness version of it!

    Starter Code

    mimic.cc gets you started. Put your whole solution in this one file.

    You may add helper classes and/or functions. But you shouldn't have to do anything too fancy. Study test for help with main and to further specify chop, choose and Special. The functions test and main could be partially combined, but don't alter test.


Learning Objectives

Assignment Submission

All code should be included in one file for each question, as described above. Helpers should be included in the same file. Include your name and student number at the top of each file, and use good programming style for your code.