The functions remove-first and remove were defined over lists of symbols. To illustrate the use of mutual recursion, we will explore a more complicated data structure called an s-list. The difference between a list of symbols and an s-list is that the members of the list can themselves be s-lists. Here is the BNF:
| The BNF for <s-list>, <symbol-expression> |
|---|
|
We wish to define a function, subst, that substitutes one symbol for another in an s-list. The function thus takes three parameters: the new symbol, the old symbol, and an s-list:
==> (subst 'a 'b '((a b) (((b g r) (f r)) c (d e)) b)) ((a a) (((a g r) (f r)) c (d e)) a)
Naturally, the structure of subst follows the structure of the BNF specification:
(define subst (lambda (new old slst)
(if (null? slst)
'()
...
)
))
If the s-list is empty, there is nothing to substitute and the answer is the empty list.
When s-list is not empty, the first element is a <symbol-expression>. Note however, that <symbol-expression> is defined in terms of a choice. Thus, our function will reflect this with a conditional expression. There are two alternatives: the first element is a symbol or it is not:
(define subst (lambda (new old slst)
(if (null? slst)
'()
(if (symbol? (car slst))
...
...
)
)
))
If it is a symbol, we must determine whether or not to replace it with new. We replace the symbol if it is equal to old and otherwise leave it alone:
(define subst (lambda (new old slst)
(if (null? slst)
'()
(if (symbol? (car slst))
(if (eq? (car slst) old)
(cons new (subst new old (cdr slst)))
(cons (car slst) (subst new old (cdr slst)))
)
...
)
)
))
Note that we must still perform the substitution in the remainder of the list, so we recurse in both cases.
The only thing left to do is to decide what to do when the first member of s-list is not a symbol. In that case, it is a symbol expression. We're in luck, however, we already have a function for performing substitutions in symbol expressions, its called subst. We get the result we want by constructing a new list from the result of substituting in the first symbol expression and substituting in the tail of the list:
(define subst (lambda (new old slst)
(if (null? slst)
'()
(if (symbol? (car slst))
(if (eq? (car slst) old)
(cons new (subst new old (cdr slst)))
(cons (car slst) (subst new old (cdr slst)))
)
(cons (subst new old (car slst))
(subst new old (cdr slst)))
)
)
))
The above procedure works, but its not really very true to the structure suggested by the BNF. We used the BNF to make the definitions, but the structure of the program doesn't closely follow the structure of the BNF. Let's look closely at the BNF again:
| The BNF for <s-list>, <symbol-expression> |
|---|
|
Note that <s-list> is defined in terms of <symbol-expression> and <symbol-expression> is defined in terms of <s-list>. This sort of pattern is called mutual recursion.
For our program structure to follow the pattern of the BNF, we can define a procedure for substituting in s-list's called subst defined in terms of a function for substituting in symbol expressions, called subst-in-symbol-expression (which will be defined in terms of subst!). Suppose subst-in-symbol-expression exists, then the definition of subst becomes:
(define subst (lambda (new old slst)
(if (null? slst)
'()
(cons (subst-in-symbol-expression new old (car slst))
(subst new old (cdr slst)))
)
))
The definition of subst-in-symbol-expression can be derived from the BNF. The BNF list two alternatives for a symbol expression, its a symbol or its not:
(define subst-in-symbol-expression (lambda (new old se)
(if (symbol? se)
...
...
)
))
If the symbol expression is a symbol, then we decide whether to replace it with the new symbol:
(define subst-in-symbol-expression (lambda (new old se)
(if (symbol? se)
(if (eq? se old) new se)
...
)
))
If not, then its an s-list and we can call subst:
(define subst-in-symbol-expression (lambda (new old se)
(if (symbol? se)
(if (eq? se old) new se)
(subst new old se)
)
))
The definition now more closely follows the BNF. In addition, we have simplified the definition considerably and made it more readable. Defining separate procedures for each non-terminal in the BNF breaks the programming process into manageable parts and allows us to concentrate our efforts on one thing at a time.
Our original definition of subst was somewhat confusing. We
just saw that following the BNF can make the program easier to understand.
This understanding comes, however, at the expense of more procedure calls.
Note that we now make two procedure calls for each node in the
<s-list> instead of one.
We can substitute one function's body for it's call in the other to get back to a single procedure. Our solution now looks like this:
(define subst (lambda (new old slst)
(if (null? slst)
'()
(cons (subst-in-symbol-expression new old (car slst))
(subst new old (cdr slst)))
)
))
(define subst-in-symbol-expression (lambda (new old se)
(if (symbol? se)
(if (eq? se old) new se)
(subst new old se)
)
))
First, we substitute the lambda in
place of the name of subst-in-symbol-expression:
(define subst (lambda (new old slst)
(if (null? slst)
'()
(cons ((lambda (new old se)
(if (symbol? se)
(if (eq? se old) new se)
(subst new old se)
))
new old (car slst))
(subst new old (cdr slst)))
)
))
Next we replace the application with the body of the lambda substituting
new for new, old for
old, and (car slst) for se:
(define subst (lambda (new old slst)
(if (null? slst)
'()
(cons (if (symbol? (car slst))
(if (eq? (car slst) old) new (car slst))
(subst new old (car slst))
)
(subst new old (cdr slst)))
)
))
The result is a single function that behaves exactly like the two functions we had before (after all its derived, so provided we made no errors in our derivation, the result has the same functionality).
Note that the single function we derived is not like the single function we
wrote. Its nearly as readable as the two function version. This is due primarily
to the collection of common subterms in the problem such as (subst new
old (cdr slst)) into a single instance. We can do this because the if
structure is an expression and returns a value. We would not have been able
to do this with an if structure like the one in Pascal that is
a command and returns no value.
Unless you are omniscient, writing recursive functions may sometimes require "fixing" functions along the way instead of writing them straight through from beginning to end.
The function anno takes a list of symbols, for instance,
(matthew mark luke john)
and returns a list with each symbol annotated by its position in
the list:
((matthew 1) (mark 2) (luke 3) (john 4))
Here is the BNF for a list of symbols:
| The BNF for <list-of-symbols> |
|---|
|
The first case in the BNF is an empty list. In this case, an empty list is returned:
(define anno (lambda (los)
(if (null? los)
'()
...
)
))
The other case is a symbol followed by a list of symbols. We can combine the annotated symbol with the rest of the list annotated using cons, so the structure is
(define anno (lambda (los)
(if (null? los)
'()
(cons (... (car los))
(anno (cdr los)))
)
))
How can we annotate a symbol? By creating a list of the symbol and the position of the symbol in the list:
(define anno (lambda (los)
(if (null? los)
'()
(cons (list (car los) position)
(anno (cdr los)))
)
))
Now we've run into a slight problem. We need the position of the symbol in the list, but we haven't provided it anywhere. We can pass the current position down to each recursive call:
(define anno (lambda (los position)
(if (null? los)
'()
(cons (list (car los) position)
(anno (cdr los) (+ position 1)))
)
))
This does the work we need, but anno takes one parameter; we've ended up with a function which takes two. So we will rename this function anno-aux and write an interface function:
(define anno (lambda (los)
(anno-aux los 1)))
(define anno-aux (lambda (los position)
(if (null? los)
'()
(cons (list (car los) position)
(anno-aux (cdr los) (+ position 1)))
)
))
notate-depth function that
combines the ideas of auxiliary functions and mutual recursion. Make sure to take
a careful look at it.
The function append combines two lists into a single list. This may be helpful in some of the homework.
The function member tests for the occurrence of something in a list.
Draw the box and pointer diagram for the following list:
((a b) (((b g r) (f r)) c (d e)) b)
What sequence of car and cdr calls would return
a d?
==> (fringe '((a b) (((b g r) (f r)) c (d e)) b)) (a b b g r f r c d e b)
Do it first using append. This should be straightforward (much like the subst function).
The problem is that append makes the run time of the function quadratic. If we just use cons, the run time would be linear. Can you write fringe without using append?
| The BNF for <s-list> |
|---|
|
Using Scheme's cond expression, rewrite the subst
using this BNF as the model. Note: you should have one function
that does not use if at the top level, but rather a
cond with three choices.
Last updated at 10:20 am on Friday, September 17, 2004.