Page History

...

(check-expect (listify empty) empty)
(check-error (listify '(a))  "listify: no open token found!")
(check-expect (listify (list (make-open) (make-close))) (list empty))
(check-expect (listify (list (make-open) 'a (make-close))) (list '(a)))
(check-expect (listify (list (make-open) 'a 'b (make-close))) (list '(a b)))
(check-expect (listify (list (make-open) (make-open) 'a (make-close) 'b (make-close))) (list '((a) b))) 

You will probably want to define the following predicate

Note the error style that is used:  the error message starts with the name of the function where the error occurred.   This is VERY useful when you have many functions that are calling each other and you have to figure out where an error occurred!

Methodology:

1. Always start with the structural function template for the data structure that you are processing -- your code must fundamentally match the data you are working on.
   1. In this case, with generative recursion, we can modify our standard function template on a list, wtih the notion that the list of tokens has 4 possibilities: empty, open, close and everything else.   Create a template based on that "virtual" structural breakdown of the data.
   2. Are all the cases valid here?  For instance, can a valid list of tokens start with a "close"?    Write your listify function in terms of what is legal and what is not, leaving "..." where the list is legal.  We'll come back and fill that part in. 
2. Next, consider how else the data breaks down.   Once again, in this generative recursion example, we can think of how the list of tokens breaks down into "phrases" that begin with "open" and end with "close".  
   1. The processing the list of tokens thus breaks down into processing a phrase, which ends with a "close" and the rest of the list of tokens, which is the rest of the token list after the matching "close" that ends the phrase.
   2. Write helper functions (let's call them "listify-phrase" and "listify-rest" for consistency's sake) to process these pieces of the token list.
3. Write listify in terms of these helper function -- don't worry yet about how they work, just assume that they do  (maybe you should write their contract and purposes now?).  
   1. Since we've broken the problem down in terms of these two pieces, the "phrase" and the "rest of the tokens", the job now is to combine those results.
4. Now write the helpers. 
   1. listify-rest:    Once again, break the function down into cases corresponding to the possible token types. 
      1. This function must find the matching "close" and return the list after that point.
      2. Are there illegal tokens you could encounter?
      3. What happens if you encounter an "open"?
   2. listify-phrase:   Once again, break the function down into cases corresponding to the possible token types.
      1. This must create a gen-list and assumes that the last token it needs to process is a "close".
      2. Are there illegal tokens you could encounter?
      3. What should you return if you encounter a "close"?
      4. What should you do if your encounter an "open"?
      5. What about something else, e.g. a symbol, number, whatever?   What about an empty list?

Here's some test cases to use:

(check-error (listify-rest empty) "listify-rest: encountered empty list!")
(check-expect (listify-rest (list (make-close))) empty)
(check-expect (listify-rest (list 1 (make-close))) empty)
(check-expect (listify-rest (list 1 (make-close) 2)) '(2))
(check-expect (listify-rest (list 1 (make-open) 2 3 (make-close) 4 (make-close) 5 6)) '(5 6))

(check-error (listify-phrase empty)  "listify-phrase: empty list encountered!")
(check-error (listify-phrase (list (make-open) (make-close)))  "listify-phrase: empty list encountered!")
(check-expect (listify-phrase (list (make-open) (make-close) (make-close))) '(()))
(check-error (listify-phrase (list (make-open) 'a (make-close))) "listify-phrase: empty list encountered!")
(check-expect (listify-phrase (list (make-open) 'a 'b (make-close) (make-close))) '((a b)))
(check-expect (listify-phrase (list 'x (make-open) 'a 'b (make-close) 'y (make-close))) '(x (a b) y))
(check-expect (listify-phrase (list 'x (make-open) (make-open) 'a (make-close) 'b (make-close) 'y (make-close))) '(x ((a) b) y)) 

You might find it useful to define the following predicate, though it is possible to not need it:

(define (input? t) 

(define (input? t) (and (not (open? t)) (not (close? t))))

...

1. We need some data to use for our timing experiments. Write a function up: nat -> (list-of nat) which constructs a list of naturals starting with 0 in ascending order or retrieve it from a previous lab. For example, (up 7) returns (list 0 1 2 3 4 5 6). You can probably write it faster using build-list that you can retrieve it. Similarly, write a function down: nat -> (list-of nat) that constructs a list of naturals ending in 0 in descending order. For example, (nums-down 7) returns (list 6 5 4 3 2 1 0).
2. Now write a function

   Code Block
   rands
   Wiki Markup

   that constructs a list of random numbers in the range from {{0}} to {{32767}}. To create a single random number in the range from {{0}} to {{{_}n{_}}}, compute {{(random}} {{{_}n+1{_}{}}}{{)}}. For larger numbers in the range {{\[0, 32768)}}, try:

   Code Block
   (define max-rand 32768) (random max-rand) ; random is built-in

   Note: random is a function in the Scheme library, but it is not a mathematical function, since the output is not determined by the input.
3. Make sure you know how to use time by using it to time isort on a list of 200 elements. Run the exact same expression again a couple times. Note that the time varies some. We typically deal with such variation by taking the average of several runs. The variation is caused by a number of low-level hardware phenomena that are beyond the scope of this course (see ELEC 220 and COMP 221).
4. Use the time operation to fill in the following chart.

   		input size	input size	input size
   		200	1000	5000
   	up
   isort	down
   	rand
   	up
   qsort	down
   	rand

   When you are done, compare your results with those generated by other pairs in the lab.

...