Comp 210 Lab 4: And More Data Structures

Index: S-expressions, Variations on natural numbers

Many kinds of software needs to be able to represent a program as a piece of data. For example, to DrScheme, your programs are just pieces of data which it needs to understand how to evaluate. Such software needs a data definition of the programming language that is to be represented. Will will represent a subset of Scheme code as data, using the following definitions.

A S-expression is one of

• empty,
• (cons a s), where a is an atom and s is an S-expression, or
• (cons s1 s2), where s1 and s2 are S-expressions

• a boolean, or
• a number, or
• a symbol.

The third case of S-expressions allows us to represent the clauses of a conditional. It also allows us to represent more general Scheme expressions that you'll see later in the course.

Let's make some example S-expressions:

     3
     fred
     (symbol? 'hello)

To do: Develop the function atom? : any -> boolean.

To do: Develop the template for functions of type

     f : S-expression -> X

To do: Using this template, write the following functions. Where applicable, finish the examples.

•      ;; subst : atom atom S-expression -> S-expression 
       ;; returns an S-expression like s, except that new has been
       ;;    substituted for each occurrence of old
       (define (subst new old s) ...)
  
       #|
       Example:
       (subst 'b 'a (cons (list 'a)
                          (cons (list 'b 'c)
                                (list 'a)))) =
       (cons (list 'b)
             (cons (list 'b 'c)
                   (list 'b)))
       |#
       

  This function is useful for implementing one of the rules for evaluating Scheme. When evaluating a Scheme function call, our rules say to replace the function call with the function body, except that we substitute the given argument(s) for the function's parameter(s). Here, new, old, and s would be the representations of the argument, parameter, and function body, respectively.

•      ;; expand-or : S-expression -> S-expression 
       ;; (define (expand-or s) ...)
  
       #|
       Example:
       (expand-and (list 'or 'foo 'bar)) =
       ...
       |#
       

  This converts the representation of

       (or foo bar)
       

  to the representation of the equivalent Scheme expression

       (cond (foo #t)
             (else bar))
       

•      ;; first-atom : S-expression -> (atom or empty))
       ;; returns the first (leftmost) atom in s
       (define (first-atom s) ...)
       
       #|
       Example:
       (first-atom (cons (list 'a) (list 'b))) = 'a
       (first-atom empty) = empty
       |#