Scheme: Evaluating a Logical expression List

Question

I am trying to write a program in Scheme that takes in a list which represents a logical expression and evaluates the total expression. I need to return a list which contains every intermediate result done before reaching the final value. The input will look like '(((~ #t) V #t V (#f & (~ #f))) & #t & (~ (#t V #f))) where & => and, V => or, and ~ => not. The output for that input should look like '(#f #t #f #f #f #f #t #f #f) with the far right being the final result and the far left being the very first evaluation done.

I've got a function which can evaluate the list however I haven't been able to figure out how to build the history list. Here is the code I've gotten thus far.

(define atom?
  (lambda (x)
    (and (not (pair? x)) (not (null? x)))))

(define evaluate1
  (lambda (lst rst)
   (cond
    ((null? lst) 'ErrEmptyList)
    ((equal? (cadr lst) 'V) (cons rst (or (car lst) (caddr lst))))
    ((equal? (cadr lst) '&) (cons rst (and (car lst) (caddr lst)))))))

(define evaluate
  (lambda (lst)
    (cond
      ((null? lst) 'ErrEmptyList)
      ((null? (cdr lst))
       (cond
         ((atom? (car lst)) (car lst))
         (else
          (evaluate (car lst)))))
      ((equal? (car lst) '~) (not (cadr lst)))
      ((and (and (atom? (car lst)) (atom? (caddr lst))) (null? (cdddr lst))) (evaluate1 lst))
      (else
       (cond
         ((atom? (car lst)) (evaluate (flatten (cons (cons (car lst) (cadr lst)) (evaluate (cddr lst))))))
         (else
          (evaluate (flatten (cons (cons (evaluate (car lst)) (cadr lst)) (list (evaluate (cddr lst))))))))))))

My code simply returns the result of #f for the given example, How can I build up a result list to be returned instead of just the final result. I'm new to scheme and any direction or help is greatly appreciated.

Answer 1

If I'm reading it correctly, this question is essentially an example of "store-passing style." (ooh, there's no wikipedia entry for SPS?) The idea is that every function will have to return a history list, and every call will have to include one.

The best way to develop this will be to follow the design recipe from (How To Design Programs)[http://www.htdp.org/]. I can't summarize it in a paragraph, but among other things, it requires that you write tests before writing the program.

Finally, if you're using Racket, the match form will make your code a lot more readable.