...
The open and close parenthesis objects (not the symbols '|(|
and '|)|
) clearly play a critical role in token streams because they delimit general lists.
Examples:
Code Block |
---|
(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))) |
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:
- 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.
- 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.
- 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.
- 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".
- 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.
- Write helper functions (let's call them "listify-phrase" and "listify-rest" for consistency's sake) to process these pieces of the token list.
- 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?).
- 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.
- Now write the helpers.
- listify-rest: Once again, break the function down into cases corresponding to the possible token types.
- This function must find the matching "close" and return the list after that point.
- Are there illegal tokens you could encounter?
- What happens if you encounter an "open"?
- listify-phrase: Once again, break the function down into cases corresponding to the possible token types.
- This must create a gen-list and assumes that the last token it needs to process is a "close".
- Are there illegal tokens you could encounter?
- What should you return if you encounter a "close"?
- What should you do if your encounter an "open"?
- What about something else, e.g. a symbol, number, whatever? What about an empty list?
- listify-rest: Once again, break the function down into cases corresponding to the possible token types.
Here's some test cases to use:
Code Block |
---|
(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:
Code Block |
---|
(define |
You will probably want to define the following predicate
Code Block |
---|
(define (input? t) (and (not (open? t)) (not (close? t))))
|
in your program. As a rough guideline follow the this parse.ss|^parse.ss.txt program that we wrote in class on Monday, Feb 2. program. Note that finding the first input is more involved than finding the first line. You will probably want to explicitly check for errors in the input because they correspond to natural tests on the form of the input.
...
- 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 with0
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 usingbuild-list
that you can retrieve it. Similarly, write a functiondown: nat -> (list-of nat)
that constructs a list of naturals ending in0
in descending order. For example,(nums-down 7)
returns(list 6 5 4 3 2 1 0)
. - Now write a function
that constructs a list of random numbers in the range from {{Code Block unmigrated-wiki-markuprands
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:
Note:Code Block (define max-rand 32768) (random max-rand) ; random is built-in
random
is a function in the Scheme library, but it is not a mathematical function, since the output is not determined by the input. - Make sure you know how to use
time
by using it to timeisort
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). - Use the
time
operation to fill in the following chart.When you are done, compare your results with those generated by other pairs in the lab.input size
input size
input size
200
1000
5000
up
isort
down
rand
up
qsort
down
rand
...