Scheme: Evaluating a Logical expression List

3
votes

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.

2
schemelisp
It looks like interesting problem. Unfortunately, I don't have time to look at it in all the details. But it looks like this is the case for a "reductions" procedure: it works the same as reduce (or foldl or fold-left) but instead of keeping only the last result, it accumulates all the results into the list. – mobiuseng

2 Answers

1
votes

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.

0
votes

You could use SPS or a "state monad" for that, but you could also resort to plain old ugly side-effects:

(define (evaluate lst)
  (let ((vals '()))
    (define (eval lst)
      (cond
       [...]
       ((equal? (car lst) '~)
        (let ((result (not ...)))
          (setq vals (cons result vals))
          result))
       [...]))
    (let ((val (eval lst)))
      (reverse (cons val vals)))))

You could define a macro for the (let ((result ...)) (setq ...) result) part that gets repeated at various places.