Announcement: the reading for next week is Chapter 3 and Appendix B of EoPL.
;; A ListofNum is one of: ;; - '() ;; - (cons Number ListofNum) ;; A ListofStr is one of: ;; - '() ;; - (cons String ListofStr)
This is a common pattern; we can see it again here:
;; A ListofSym is one of: ;; - '() ;; - (cons Symbol ListofSym)
A common adage in Computer Science is D.R.Y.: "Don't Repeat Yourself"
Rather than write several expressions that all look similar, it is better figure out how to abstract over the expressions, and make a single definition that can be reused. (Sound familiar?)
When you see two expressions that look similar and decide that you want to try to factor out a reusable abstraction of them, start by identifying what is different between them. Then parameterize over those components.
Here is a way to do this with data definitions:
;; A Listof[X] is one of: ;; - '() ;; - (cons X Listof[X] )
Different people (and languages) use different notations
for this idea, e.g. "[Listof X]", or
"α list." But the particular syntax of how you
notate such parameterization and instantiation
is not nearly as important as the idea of such abstraction.
You can test these abstractions, at least in your head. A crucial test of a parameteric data definition is to check that you can get back to what you had before.
So in the case of Listof[X], we should test
it by making sure we can use it to again define classes
corresponding to ListofNum and ListofStr.
ListofNum back by plugging Number
in for X:
;; A Listof[Number] is one of: ;; - '() ;; - (cons Number Listof[Number] )
ListofStr back by plugging
String in for X:
;; A Listof[String] is one of: ;; - '() ;; - (cons String Listof[String] )
Another example:
;; A Toy is one of: ;; - Symbol ;; - (cons Integer (cons Toy (cons Toy '()))) ;; A Game is one of: ;; - Integer ;; - (cons Integer (cons Game (cons Game '())))
Ex 1. What common abstraction can we make from these definitions?
Write down a parametric data definition for the abstraction.
Test it by plugging in appropriate arguments to
get classes equivalent to Toy and Game.
Ex 2. Can you use your definition from the previous exercise to describe a class equivalent to the following:
;; A Puzzle is one of: ;; - String ;; - (cons String (cons Puzzle (cons Puzzle '())))Why or why not?
;; An NeLof[X] is one of: ;; - (cons X '()) ;; - (cons X NeLof[X] )
What are examples of this kind of data?
What kind of data does this remind you of? How are they related?
What is the template for processing this kind of data?
(This section corresponds to section 1.3 of the reading in EoPL.)
Sometimes a function needs to track information about where it has been before it can get to where it wants to go.
rev-list, which takes a list and returns a new list
with all of the elements from the input, but in reverse order.
Examples: what should rev-list produce for the following inputs:
(list)
(list 'a 'b 'c)
(list 1 3 2 4 3)
(list "time" "and" "time" "again")
Now, as for the function itself:
let us develop this together using our standard techniques.
(interactive development of a function.)
Lets work on a version of longest-runs
(a function from MP1), that works on
Listof[Integer]
(instead of the IntegerSequence
data definition described in MP1).
Examples: what should longest-runs produce for the following
inputs:
(list)
(list 1 1 1)
(list 3 3 3 2 2 2 2 1 1 1)
(list 1 1 1 2 2 3 3 3)
Now, as for the function itself:
The following exercises are designed to be easiest to implement if you write a helper procedure with a context parameter. So as you work through each problem, keep in mind the question of what state would be most useful to carry along as your function traverses its input.
Ex 3. Develop the function make-palindrome,
which accepts a NeLof[Symbol] and constructs
a palindrome by mirroring the list around the last item.
For example, (make-palindrome '(a b c))(a b c b a)rev-list or reverse
function in your answer.)
Remember to start by writing some tests!
Ex 4. Develop the function to-ten, which consumes
a list of digits (numbers between 0 and 9) and produces the
corresponding number. The first digit is the most significant
one. Examples: (to-ten (list 1 0 2))(to-ten (list 2 1))
Remember to start by writing some tests!
Here is a data definition for representing HTML-like documents:
;; An AttrList is one of: ;; - '() ;; - (cons (list Symbol String) AttrList) ;; An X-exp is one of: ;; - String ;; - (cons Symbol (cons AttrList X-list)) ;; An X-list is one of: ;; - '() ;; - (cons X-exp X-list) ;; Examples: ;; "Hello" ;; '(b () "Hi" (em () "ther") "e") ;; represents Hithere ;; '(strike () "and " (a ((href "http://www.google.com")) "Google")) ;; representsandGoogle
What does the template for processing an X-exp look like?
We start by noting that in addition to the self-references in
AttrList and X-list, there are
cross-references, where the definition for X-list
refers to X-exp, and the definition for
X-exp refers to AttrList and X-list
This is an example of a data definition that exhibits mutual recursion, because there is a cycle in the cross-references between the data definitions. So the rule of thumb for developing a template for this is the following: when we make a function to process data from mutually recursive definitions, we make a separate function for each definition.
;; process-x-exp : X-exp -> ???
;; usage: (process-x-exp an-xexp) does what???
(define process-x-exp
(lambda (xe)
(cond
((string? xe) ...)
(else ... (car xe) ... ; tag
... (car (cdr xe)) ... ; attribute list
... (process-x-list (cdr (cdr xe))) ... ; remaining x-exp's.
))))
;; process-x-list : X-list -> ???
;; usage: (process-x-list an-xlist) does what???
(define process-x-list
(lambda (xl)
(cond
((null? xl) ...)
(else ... (process-x-exp (car xl)) ... ; x-exp
... (process-x-list (cdr xl)) ... ; remaining x-exp's
))))
Here's another example, based on the grammar for S-list from the book,
(but extended with Numbers).
;; An Nus-list is one of: ;; - '() ;; - (cons Nus-exp Nus-list) ;; An Nus-exp is one of: ;; - Number ;; - Symbol ;; - Nus-list
Ex 5. What does the template/skeleton of a function to process this data look like? Get a lab helper to approve your template/skeleton before moving onto the next problem.
Ex 6. Implement symbols-of, which
produces a list of the symbols in an argument Nus-list.
Remember to start by writing some tests!
Ex 7. Implement reverse-nuslist, which
reverses the tree structure of its argument Nus-list.
For example, the reverse of ((z a) ((b a) c) d)(d (c (a b)) (a z))
Remember to start by writing some tests!
Consider trying to make an operators-of function,
which, when given an S-list, returns a list
of all of the symbols that occur in operator position
in the argument.
For example, the operators in the expression
(* x (max (+ y (cos z)) min))
are (* max + cos)
In this situation, the first S-exp of an S-list is given
a special role. But the standard template
for the S-list grammar above,
does not treat the first S-exp in an S-list
any differently from the second S-exp, or the third,
or the fourth, etc.
So when one attempts to follow the grammar
above, the "natural recursion"
that results when evaluating an expression
like (operators-of '(+ x (sub1 y))operators-of on the rest of the list: (x (sub1 y)),
and then on the rest of that, ((sub1 y)).
But the (operators-of '(x (sub1 y)))(x sub1),
have nothing to do with the
(operators-of '(+ x (sub1 y)))(+ sub1).
This is a case where following the original grammar
leads us astray. But that is because the role of the operator
is not distinquished from the roles of the operands in the
original grammar for S-list.
So an appropriate solution starts by developing a different
grammar for the same class of data.
Lets develop such a grammar together; we'll call this
grammar S-list-alt (The grammar
we develop needs to be able to represent every S-list
from the original grammar, and should not introduce any
elements that are not in the set S-list
Ex 8. Now that we have a grammar for processing
instances of S-list-alt, implement operators-of.
Ex 9. Consider the problem of printing Scheme values; we've encountered
the difference between printing pairs: (a . b)
and printing lists: (a b c d e).
The task of this exercise is to write a function,
value->string, that convert
Scheme values into strings much like how
Scheme's internal printer works.
Examples for value->string:
(value->string 2) ;; => "2" (value->string (cons 1 2)) ;; => "(1 . 2)" (value->string (cons 1 (cons 2 (cons 3 '())))) ;; => "(1 2 3)"
Start by developing a grammar for Scheme values that is suitable
for writing the function, value->string.
For the purposes of this problem, you may assume that Scheme values are defined by the following grammar.
;; A SchemeValue is one of: ;; - Boolean ;; - Number ;; - Symbol ;; - String ;; - (cons SchemeValue SchemeValue)You should get your new grammar approved by a helper in the lab before you begin development of your function.
In Scheme, functions are first class values.
We can thus abstract over them, the same way that we can abstract over any other sort of data.
Instead of (define (f1 x y) (+ x y))
could do (define (f2 op x y) (op x y))
This becomes very useful for abstracting over list processing
The templates we've been writing are common patterns.
The "MAP" pattern
;; g : Listof[Number] -> Listof[Number]
(define g
(lambda (l)
(cond
((null? l) '())
(else (cons (* 2 (car l))
(g (cdr l)))))))
;; h : Listof[Number] -> Listof[Number]
(define h
(lambda (l)
(cond
((null? l) '())
(else (cons (+ 3 (car l))
(h (cdr l)))))))
There is a lot of stuff that is the same between g and h above.
Here's another one:
;; strs-to-nums : Listof[String] -> Listof[Number]
(define strs-to-nums
(lambda (l)
(cond
((null? l) '())
(else (cons (string->number (car l))
(strs-to-nums (cdr l)))))))
The only essential difference is that h has a (+ 3 elem)
where g has a (* 2 elem). That is, they only differ
in what operation they perform on each element elem of the list.
In Scheme, we can abstract over such differences!
;; map : (Number -> Number) * Listof[Number] -> Listof[Number]
(define map
(lambda (f l)
(cond
((null? l) '())
(else (cons (f (car l))
(map f (cdr l)))))))
;; mul2 : Number -> Number
(define mul2 (lambda (x) (* 2 x)))
;; add3 : Number -> Number
(define add3 (lambda (y) (+ 3 y)))
;; (g lon) is same as (map mul2 lon) !
;; (h lon) is same as (map add1 lon) !
Exercise: The "FILTER" pattern
;; evens : Listof[Number] -> Listof[Number]
(define evens
(lambda (l)
(cond
((null? l) '())
(else (cond
((even? (car l)) (cons (car l) (evens (cdr l))))
(else (evens (cdr l))))))))
;; all-less-than-ten : Listof[Number] -> Listof[Number]
(define all-less-than-ten
(lambda (l)
(cond
((null? l) '())
(else (cond
((< (car l) 10)
(cons (car l)
(all-less-than-ten (cdr l))))
(else (all-less-than-ten (cdr l))))))))
Ex 10. What are the essential differences between
evens and all-less-than-ten above?
Ex 11. Come up with a function, filter, that is an abstraction of
evens and all-less-than-ten
For the filter procedure you define, it should be the case that:
;; (evens l) is same as (filter even? l) !
;; (all-less-than-ten l) is same as (filter less-than-ten l),
;; where less-than-ten is defined as follows:
;;
;; less-than-ten : Number -> Boolean
;; Produces #t iff n < 10
(define less-than-ten
(lambda (n)
(< n 10)))
Felix S. Klock II