Assignment 2 for CSCI 431

Running Scheme

MIT Scheme has been installed on all Sun workstations (i.e., flat-rock, hendersonville, and marshall), and on the linux boxes in 004. You can invoke the Scheme interpreter by giving the command:


   scheme

at the system prompt. To leave the Scheme interpreter give the command:


   (exit)

To load files of Scheme code, use the function load:


   (load "assign2.scm")

On-Line Resources

The primary URL is http://www.swiss.ai.mit.edu/projects/scheme/. This site contains a manual as well as various implementations.

There were also a number of good on-line resourses:

Your Assignment

(I would like to thank Michael Bogomolny for this assignment, including the detailed explanation.)

A discussion of disjoint union types and recursive types:

When writing routines that operate on disjoint union types, we generally write conditionals, which check which kind of thing we've got, of the multiple kinds of things that count as members of the larger type. For example:

   a list is:
      * the empty list, OR
      * a pair whose cdr is a list

Notice that the main structure of this definition is a disjoint union; the set of empty lists and the set of pairs don't overlap, because an empty list is never a pair and vice versa. They're disjoint types, with no members in common. But the type list is defined by combining them; a list is either the empty list or a pair whose cdr is also list.

Note that the first case, empty lists, is not recursive. But the second case is defined recursively. Not just any old pair is a list--only those whose cdrs are lists. When we do normal recursion over lists, this disjoint union definition guides us--we usually have some kind of conditional as the body of our function, which checks which of these two kinds of list we've got; in the second case, we use recursion where there's recursion in the definition:


   (define (list-sum lis)
      (if (null? lis)               ;; empty list OR other kind?
          0                         ;; empty list case
          (+ (car lis)              ;; other case, of a pair
             (list-sum (cdr lis)))  ;; whose cdr is a list

Likewise, when we evaluate simple infix expressions, we have a disjoint union:

   an _infix_expression_ is:
      * a literal number, or
      * a binary expression of the form
        (<infix expression> <operator> <infix expression> )

   an <operator> is:
      +, or
      -

When we think about the s-expression data structures we use to represent these expressions, we get a disjoint union. Let's call a data structure representing an infix expression an infix-expr.

   an infix-expr is
      * a number
      * a three-element list whose 
          1st element is an infix-expr
          2nd element is an operator symbol (+ or -)
          3rd element is an infix-expr

From this description we can write a Scheme predicate to tell if something is an infix-expr:


(define (infix-expr? thing)                ;; a thing is an infix-expr if
   (or (number? thing)                     ;; it's a number OR if
       (and (list? thing)                  ;; it's a list, and
            (= (length thing) 3)           ;; it has exactly 3 elements, and
            (infix-expr? (car thing))      ;; its car is an infix-expr, and
            (member (cadr thing) '(+ -))   ;; its cadr is + or -, and
            (infix-expr? (caddr thing))))) ;; its caddr is an infix-expr

(In the above code, cadr is a built-in function that returns the car of the cdr of its argument, i.e., (car (cdr thing)). The function caddr is similarly equivalent to (car (cdr (cdr thing))).)

Note that our predicate corresponds exactly to the English definition of an infix-expr data structure, representing an infix expression in the obvious way. Similarly, if we want to know the value of of an infix expression represented by an infix-expr data structure, we can say that:

   the value of an infix expression is:
      * if it's a number, just that number, OR
      * (if it's a binary expression)
            if the operator is plus:
               the sum of
                  the value of the left subexpression
                  and the value of the right subexpression
            otherwise
               the difference of the value of the left subexpression
                   and the value of the right subexpression

Notice that the structure of this definition of the value of an infix expression is a conditional--there are two kinds of infix expressions, and the value of each kind is computed differently. Also notice that the definition of the value of an infix expression is recursive in the case where the value isn't just a number--the value of a binary expression is defined in terms of the value of its left subexpression and the value of its right subexpression. These two basic facts guide the writing of the infix-eval function:


   (define (infix-eval infix-expr)
      (if (number? infix-expr)  ;; if it's just a number
          infix-expr            ;; the value is that number
          ;; otherwise it's a binary expression whose value is:
          ;;   if the operator is plus,
          ;;      the sum of the values of the subexpressions
          ;;   otherwise,
          ;;      the difference of the values of the subexpressions
          (if (eq? (cadr infix-expr) '+)
              (+ (infix-eval (car infix-expr))
                 (infix-eval (caddr infix-expr)))
              (- (infix-eval (car infix-expr))
                 (infix-eval (caddr infix-expr))))))

Notice that in this case, too, the basic structure is a conditional to discriminate between the two basic types in our disjoint union. And within the branch for the recursive case, we have recursion for each part that is recursive in the definition--a binary infix-expr has two subexpressions that are also infix-expr's, so when we compute the value of a binary infix-expr, we must compute the values of those infix-exprs (the car and the caddr).

Consider the following definition of a number tree:

   a number-tree is:
     * a number, OR
     * a two-element list whose
         first element is a number-tree
         second element is a number-tree

By this definition, the following are number-trees:

   1
   2
   (1 (2 3))
   (((2 4) 6) (8 (10 11)))
the following are NOT number trees: 
   (1 (2))
   (1 . 2)
   foo
   (1 2 3)
   (1)
   ((1 . 2) . (3 . 4))

Think about why these don't meet the definition.
(Note that number-trees are binary trees, where a leaf node is a number and an interior node is a two-element list, not a single pair, and not a list of any other length.)

This kind of tree is like our expression trees, but with no operator symbol.

Your Task

Write a Scheme predicate number-tree? which determines whether or not its argument is a number-tree. Your definition should correspond to the disjoint union definition of a number-tree given above. (Your function should be very simple--its body should be about 5 lines long.)
Write an English definition (i.e., pseudo-code) of the sum of the elements of a number-tree; this should mainly be a conditional corresponding to the or in the definition of a number-tree, with a recursive case. Included this definition in your code file as comments.
Write a Scheme function number-tree-sum, which adds the leaves (i.e., the numbers) in a whole number tree. This should correspond closely to the English definition.
Write a Scheme function number-tree->list, which ``flattens'' a number tree to a list of numbers. Your recursive function should follow the same general plan as the others, with one branch for each case of the disjoint union, and recursion corresponding to the recursion in the definition of a number-tree.
Hint: the result of number-tree->list should always be a list, even if the input is just a number. You can use list to put a single number in a one element list. (Remember, list can take any number of arguments, including one.) If the result is always a list, you can use use append to append two lists into a single list. (Your function should be simple; its body should be about 4 lines long.)
```
Example uses: 
   (number-tree->list 1)                  => (1)
   (number-tree->list '(1 2))             => (1 2)
   (number-tree->list '((1 2) (3 4)))     => (1 2 3 4)
   (number-tree->list '((4 8) ((2 3) 1))) => (4 8 2 3 1)
```
Now consider the following prefix arithmetic expressions using the operators + and -:
```
   1
   22
   (+ 1 3)
   (- (+ 3 6) (- 2 1))
```
Write an English definition of a prefix expression, for a language like our infix expressions, but with prefix syntax. (Assume we only have + and - operators, and compound expressions are all binary.) Your definition should resemble the definition of an infix expression given earlier. Include this definition in your code file in the form of comments.
Write an English definition of a prefix-expr, which is a kind of s-expression data structure that represents a prefix expression, in much the same way an infix-expr represents an infix expression. Your definition should resemble the definition of an infix-expr data structure given earlier. Include this definition in your code file in the form of comments.
Note: the previous question asked you to define a prefix expression as a general construct, but this question asks you about the structure you would use to represent it in Scheme. For example, if we were talking about sets, part of the definition might be ``a set is a collection of unique elements'', whereas we might define our set representation as ``a list of unique symbols''.
Write a Scheme predicate that checks whether something is a prefix-expr, i.e., an s-expression data structure corresponding to an prefix expression as described above. Your definition should correspond closely to the English definition.
Write a function prefix-eval, which computes the value of a prefix expression represented by a prefix-expr.
Write an English description of an operation infix->prefix, which converts infix expressions to prefix expressions. This should have one base case and two recursive cases. Include this definition in your code file in the form of comments.
Write a Scheme function infix->prefix, which converts an infix-expr to a prefix-expr. This function should closely correspond to your English description. Its body should be 4 or 5 lines long, and its overall structure should resemble infix-eval, but it should do something different in the recursive cases. You might want to use cond for this.
```
Example uses: 
   (infix->prefix '1) => 1
   (infix->prefix 22) => 22
   (infix->prefix '(1 + (3 - 2))) => (+ 1 (- 3 2))
```
Recall that a read-eval-print loop uses the function read to read an s-expression, evaluates it, and prints the result, then loops to do it over again, ad infinitum. Here's a read-eval-print-loop function using our prefix-eval function:
```
   (define (repl)
     (display "REPL>")   ;; print prompt to show we're ready for input
     (let ((input (read)))  ;; read input
       (display (infix-eval input)) ;; evaluate it and write result
       (newline)         ;; write a newline character 
                         ;; to start another line
       (repl)))          ;; call self to do it again
```
This uses the standard Scheme functions read (which can read any s-expression that the user types in textually, converting it to a data structure) and display, which can write the textual representation of any s-expression for the user to see. We can call the repl function above, and it will repeatedly:
1. call read to accept input that the user types,
2. pass the resulting s-expression data structure to eval to be interpreted as an expression, and
3. display the printed representation of the resulting s-expression (the value of the input expression) for the user to see.
Note that since the read function accepts what the user types and just returns an s-expression data structure (without evaluating it) the result of (read) will just be an s-expression; you don't have to quote it when you type it in to make it a data structure; instead, the repl function will hand it to infix-eval to be evaluated as an infix-expr.
Modify this read-eval-print-loop to do something special if the input is the symbol halt; that is, if the user types halt, which the reader will read as the symbol halt, the read-eval-print loop should NOT try to evaluate it; it should display the string quitting... and then just return #t.
(Note: this is very easy; the read function will read the character sequence h-a-l-t as the symbol halt and return a pointer to that symbol.)
Test your function as shown in the example below. REPL> is what the repl function writes, what follows that is what you type, and the next line is the result it should write. To get it to look nice when you quit out, we put a call to newline after the call to display that displays ``quitting...'' and before the line that returns #t.
(Note that after your function returns when you quit, the Scheme system will print the value it returns. That's normal--you're letting control go back to your Scheme system's own read-eval-print-loop, and it just prints the value returned from the call to repl.)
```
   (repl) ;; start up your read-eval-print-loop by calling repl function
   REPL>1
   1
   REPL>(1 + 3)
   4
   REPL>((1 + 3) - 2)
   2
   REPL>halt
   quitting...
   \#t
```
Make another read-eval-print loop repl2 which is a higher-order function, i.e. it takes an evaluation function as its argument. So instead of just calling prefix-eval, it should accept an argument (give it a formal parameter name of eval) and call whatever function that is. When it calls itself recursively, of course, repl should pass that evaluator along as its argument.
Test your new repl function using your infix-eval and your prefix-eval:
```
   > (repl2 infix-eval)   ;; start up with infix evaluator
   REPL2>(1 + (3 - 2))
   2
   REPL2>5
   5
   REPL2>(6 - (3 + 1))
   2
   REPL2>halt
   quitting...
   \#t
   > (repl2 prefix-eval)  ;; start up with prefix evaluator
   REPL2>(+ 1 (- 3 2))
   2
   REPL2>5
   5
   REPL2>(- 6 (+ 3 1))
   2
   REPL2>halt
   quitting...
   \#t
```

To Be Handed In

You should turn in code implementing all of the functions detailed above, as well as any supporting routines that you write that are necessary for these functions to work correctly. All functions should be included in one file along with the English pseudo-code incorporated as comments. Your code file be submitted electronically to your class ftp directory.