Deriving Procedures from BNF specifications

Problems for Sun 3/11/96

In all the following questions, make sure you derive your function from the BNF specification of lists, s-lists and binary-search-trees. For reference: 
<list>   ::= ({<expr>}*)

<s-list> ::= ({<s-expr>}*)
<s-expr> ::= <symbol> | <s-list>

<bin-search-tree> ::= () | (<number> <bin-search-tree> <bin-search-tree>)
From the textbook:

filter-in

(filter-in pred list) where pred is a predicate, returns the list of those elements in list that satisfy the predicate. 
> (filter-in number? '(a 2 (1 3) b 7))
(2 7)
> (filter-in symbol? '(a (b c) 17 foo))
(a foo)

down

(down lst) wraps parentheses around each top-level element of lst. 
> (down '(1 2 3))
((1) (2) (3))
> (down '(a (more (complicated)) object))
((a) ((more (complicated))) (object))

count-occurrences

(count-occurrences s slist) returns the number of occurrences of s in slist. 
> (count-occurrences 'x '((f x) y (((x z) x))))
3
> (count-occurrences 'w '((f x) y (((x z) x))))
0
Do a tail-recursive version of count-occurrences.

flatten

(flatten slist) returns a list of the symbols contained in slist in the order in which they occur when slist is printed. Intuitively, flatten removes all the inner parentheses from its argument. 
> (flatten '(a b c))
(a b c)
> (flatten '((a b) c (((d)) e)))
(a b c d e)
> (flatten '(a b (() (c))))
(a b c)

path

(path n bin-search-tree) where n is a number and bin-search-tree is a binary search tree that contains the number n, returns a list of Ls and Rs showing how to find the node containing n. If n is found at the root, it returns the empty list. 
> (path 17 '(14 (7 () (12 () ()))
	              (26 (20 (17 () ())
                          ())
                (31 () ()))))
(R L L)

car-cdr

(car-cdr s slst errvalue) returns an expression that, when evaluated, produces the code for a procedure that takes a list with the same structure a slst and returns the value in the same position as the leftmost occurrence of s in slst. If s does not occur in slst, then errvalue is returned. 
> (car-cdr 'a '(a b c) 'fail)
(lambda (slst) (car slst))
> (car-cdr 'c '(a b c) 'fail)
(lambda (slst) (car (cdr (cdr slst))))
> (car-cdr 'dog '(cat lion (fish dog) pig) 'fail)
(lambda (slst) (car (cdr (car (cdr (cdr slst))))))
> (car-cdr 'a '(b c) 'fail)
fail

car-cdr2

(car-cdr2 s slst errvalue) like car-cdr but generates procedure compositions. 
> (car-cdr 'a '(a b c) 'fail)
car
> (car-cdr 'c '(a b c) 'fail)
(compose car (compose cdr cdr))
> (car-cdr 'dog '(cat lion (fish dog) pig) 'fail)
(compose car (compose cdr (compose car (compose cdr cdr))))
> (car-cdr 'a '(b c) 'fail)
fail