Homework #7

This problem requires Lecture 6 and book sections 1.1-1.2

Exercise 1.1, p.5 - (10 minutes)
Write a syntactic derivation that proves (-7 . (3 . (14 . ()))) is a list of numbers.

You should find syntactic derivations to be similar to those you might have done in CS 236 or CS 252.

Exercise 1.2, p.7 - (20 minutes)
Rewrite the <datum> grammar without using the Kleene star or plus.

You can use the following modified grammar for this exercise since the definition of list on page 6 is does not use the dot-paren notation:

   <list>         ::=  () | ( <datum> . <list> )   
   <dotted-datum> ::=  ( {<datum>}+ . <datum> )   
   <vector>       ::= #( {<datum>}* )   
   <datum>        ::=  <number> | <symbol> | <boolean> | <string>   
   |  <list> | <dotted-datum> | <vector>   
 

Hint: introduce new non-terminals for the Kleene-star parts if you need to. Please show the new derivation with your new BNF. The data type described here, <datum>, is the syntax of Scheme. This is a good example of how syntax and data type specifications are related.

Then indicate the changes to the following derivation that are required by this revised grammar.

<list>
=> (<datum><datum><datum>)
=> (<boolean><datum><datum>)
=> (#t <datum><datum>)
=> (#t <dotted-datum><datum>)
=> (#t ({<datum>}+ . <datum>) <datum>)
=> (#t (<symbol> . <datum>) <datum>)
=> (#t (foo . <datum>) <datum>)
=> (#t (foo . <list>) <datum>)
=> (#t (foo . ()) <datum>)
=> (#t (foo . ()) <number>)
=> (#t (foo . ()) 3)

Exercise 1.5, p.14 - (20 minutes)
This version of list-of-numbers? works properly only when its argument is a list. Extend the definition of list-of-numbers? so that it will work on an arbitrary Scheme <datum> and return #f on any argument that is not a list.

To save you some typing, here is the original version of the list-of-numbers? function, which you can copy and paste into your editor:

(define list-of-numbers?
(lambda (lst)
(if (null? lst)
#t
(and (number? (car lst))
(list-of-numbers? (cdr lst))))))

Instructions on submitting homework is here

Last updated at 3:52 pm on Wednesday, January 21, 2004.