Generative Recursion
Students should use DrScheme, following the design recipe, on the exercises at their own pace, while labbies wander among the students, answering questions, bringing the more important ones to the lab's attention.
Generative Recursion Design Recipe Review
In class, we presented a new more general methodology for developing Scheme functions called generative recursion.
To develop a generative recursive, we use a generalized design recipe that incorporates the following changes:
- When making function examples, we need even more examples, as they help us to find the algorithm we will use.
- When making a template, we don't follow the structure of the data. Instead, we ask ourselves six questions:
- What is (are) the trivial case(s)?
- How do we solve the trivial case(s)?
- For the non-trivial case(s), how many subproblems do we use?
- How do we generate these subproblems?
- Can we combine the results of these subproblems to solve the given problem?
- How do we combine the results of these subproblems?
*We use the answers to the preceding questions to fill in the following very general template:*We add a step to reason about why our algorithm terminates, since this is no longer provided by simply following the structure of the data.(define (f _args_) (cond [(_trivial_? _args)) (_solve-trivial_ _args_)] [else (_combine_ (f (_generate-subproblem-1_ _args_)) ... (f (_generate-subproblem-n_ _args_)))]))
Converting a token stream to a list input stream
The Scheme reader reads list inputs rather than symbols or characters where a list input is defined by the following set of mutually recursive data definitions:
An input is either:
- any built-in Scheme value that is not a list (
empty?
or =cons?=) - a general list.
A general list is either:
empty
,(cons i agl)
wherei
is an input andagl
is a general list.
Note that the second clause above could be written as the following two clauses:
(cons p l)
wherep
is a primitive Scheme value that is not a list, or(cons el l)
whereel
andl
are general lists.
Your task is to write the core function listify
used in an idealized Scheme reader stream. listify
converts a list of tokens, where a token is defined below, to a list of inputs as defined above.
A token is either
- any built-in Scheme value (including symbol, boolean, number, string,
empty
, etc.; or - (make-open), or
- (make-close)
given the structure definitions
(define-struct open ()) (define-struct close ())
The open and close parenthesis objects (not the symbols '|(|
and '|)|
) clearly play a critical role in token streams because they delimit general lists.
Examples:
(listify empty)
{{ =empty}} .(listify (list (make-open) (make-close) )
{{ =(list empty)}} .(listify (list (make-open) 'a (make-close) )
{{ =(list '(a))}}(listify (list (make-open) 'a 'b (make-close) )
{{ =(list '(a b))}}(listify (list (make-open) (make-open) 'a (make-close) 'b (make-close))
{{ =(list '((a) b))}}
You will probably want to define the following predicate
(define (input? t) (and (not (open? t)) (not (close? t))))
in your program. As a rough guideline follow the parse.ss (https:wikiriceedudisplayCSWIKI211lab04parsess) program that we wrote in class on Monday, Feb 2. 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.
Insertion Sort vs. Quicksort
In class, we've described two different ways of sorting numbers, insertion sort and quicksort.
;; insertion sort (define (isort alon) (cond [(empty? alon) empty] [(cons? alon) (insert (first alon) (isort (rest alon)))])) (define (insert new sortedlon) (cond [(empty? sortedlon) (list new)] [else (if (< new (first sortedlon) (cons new sortedlon)] (cons (first sortedlon) (insert new (rest sortedlon))))])) ;; quicksort (adapted to functional lists) (define (qsort alon) (cond [(empty? alon) empty] [(cons? alon) (local [(define pivot (first alon)) (define other (rest alon)) (define lesser (filter (lambda (n) (<= n pivot)) other)) (define greater (filter (lambda (n) (> n pivot)) other))] (append (qsort lesser) (list pivot) (qsort greater)))]))
So we have two fundamentally different approaches to sorting a list (and there are lots of others, too).
It seems unsurprising that each might behave differently.
Can we observe this difference? Can we provide explanations?
We'll do some timing experiments,
outline the theoretical analysis,
and see if the two jive.
If your programs only sort small lists a few times, it doesn't matter;
any sort that is easy to write and have correct is fine.
However, for longer lists, the difference really is huge.
In Real Life (tm), sorting is an operation often done
on very long lists (repeatedly).
There is an expression
(time <em>expr</em>)
, which
can be used to time how long it takes the computer to
evaluate something. It is used like
(time (isort big-list))
where
big-list
would be previously defined.
This expression prints out the time taken during evaluation,
along with the evaluation result. Since we're only interested in
the time, we can avoid seeing the long sorted list by using
something like
(time (empty? (isort big-list)))
time
prints three times, each in milliseconds.
The first is the amount of computing time elapsed -- thus, it doesn't
count whatever else your computer was doing at the same time.
This is what we're interested in.
Partner with someone else in lab to split the following work. First, we need some data to use for our timing experiments.
Now, make sure you know how to use time .
Continue timing, filling in the following chart.
|
COMP 280
introduces concepts of how these algorithms behave in general.
The punchline is that we can say that both insertion sort and
quicksort on lists are "_O(n
2
)_"
in the worst case.
I.e., for a list of n elements, they each take about
_c × n
2
_ evaluation steps to sort
the list, for some constant
c
.
Furthermore, in the "average" case, Quicksort does better:
O(n log n).
COMP 280, and later COMP 482, show precisely what these statements
mean and how to derive them.
Ackermann's Function Example
If you have time…
Here's the definition of a strange numerical function on natural numbers,
called Ackermann's function:
A(m,n) = 0, if n=0
= 2×n, if n>0 and m=0
= 2, if n=1 and m>0
= A(m-1,A(m,n-1)), if n>1 and m>0
Note that this definition is not structurally recursive.
In fact, it cannot be defined in a structurally recursive manner.
(In technical jargon, the function is not
primitive recursive
.
See
COMP 481
for what that means.)
Here's the equivalent Scheme code:
(define (ack m n)
(cond
[(= n 0) 0]
[(and (> n 0) (= m 0)) (* 2 n)]
[(and (= n 1) (> m 0)) 2]
[(and (> n 1) (> m 0)) (ack (sub1 m) (ack m (sub1 n)))]))
|
This function isn't very useful, except as a theoretical example of a
function that grows faster than probably any one you've seen before.
In
COMP 482
,
you'll learn one use for this function.
!! Access Permissions
- Set ALLOWTOPICCHANGE = Main.TeachersComp211Group