Programming Praxis

Our expression evaluator consists of four functions: the driver function calc, and three functions expr, term and factor that each recognize a single metastatement of the grammar. The three grammar functions all take a single argument, a list representing the rest of the input expression, and extract and evaluate a portion of the input expression, returning the result of the evaluation and the rest of the input expression after the part it has evaluated.

(define (calc str)
  (let ((xs (filter (lambda (c) (not (char-whitespace? c)))
                    (string->list str))))
    (let-values (((c xs) (expr xs)))
      (if (null? xs) c
        (error 'calc (string-append
          "extra input at " (list->string xs)))))))

The calc function converts the input string to a list of characters, calls expr to evaluate the expression, and either returns the value of the expression or raises an error if the expression is complete before the end of the input. Here’s expr:

(define (expr xs)
  (let-values (((y ys) (term xs)))
    (let loop ((e y) (ys ys))
      (cond ((null? ys)(values e ys))
            ((char=? (car ys) #\+)
              (let-values (((z zs) (term (cdr ys))))
                (loop (+ e z) zs)))
            ((char=? (car ys) #\-)
              (let-values (((z zs) (term (cdr ys))))
                (loop (- e z) zs)))
            (else (values e ys))))))

The expr evaluator extracts a term, then loops as long as it sees a + or - as the next input character. The term evaluator is similar, looping over * and / operators:

(define (term xs)
  (let-values (((y ys) (factor xs)))
    (let loop ((t y) (ys ys))
      (cond ((null? ys) (values t ys))
            ((char=? (car ys) #\*)
              (let-values (((z zs) (factor (cdr ys))))
                (loop (* t z) zs)))
            ((char=? (car ys) #\/)
              (let-values (((z zs) (factor (cdr ys))))
                (loop (/ t z) zs)))
            (else (values t ys))))))

The factor function is the most complicated of the four functions, mostly because it has to assemble numbers as well as recognize the metastatement; an alternate program structure might include a function number that recognizes numbers. The other complication of the factor function is error-checking; the function complains if it runs out of input, or if a closing parenthesis is not in the expected place, or if it sees something other than a number or an opening parenthesis when it is expecting one or the other.

(define (factor xs)
  (define (digit x)
    (- (char->integer x) 48))
  (cond ((null? xs) (error 'factor "unexpected end of input"))
        ((char-numeric? (car xs))
          (let loop ((n (digit (car xs))) (ys (cdr xs)))
            (cond ((null? ys) (values n ys))
                  ((char-numeric? (car ys))
                    (loop (+ (* n 10) (digit (car ys))) (cdr ys)))
                  (else (values n ys)))))
        ((and (pair? (cdr xs)) (char=? (car xs) #\-)
              (char-numeric? (cadr xs)))
          (let loop ((n (digit (cadr xs))) (ys (cddr xs)))
            (cond ((null? ys) (values (- n) ys))
                  ((char-numeric? (car ys))
                    (loop (+ (* n 10) (digit (car ys))) (cdr ys)))
                  (else (values (- n) ys)))))
        ((char=? (car xs) #\()
          (let-values (((y ys) (expr (cdr xs))))
            (cond ((null? ys) (error 'factor (string-append
                    "expected ) at " (list->string ys))))
                  ((char=? (car ys) #\))(values y (cdr ys)))
                  (else (error 'factor (string-append
                    "unexpected character at " (list->string ys)))))))
        (else (error 'factor (string-append
          "unexpected character at " (list->string xs))))))

Here’s an example:

> (calc "123 + 456 * 789")
359907

Something as complicated as the four tightly-coupled functions demands a test suite, which we show below; the first time this code was run, it produced two errors, but investigation showed that both were in the checking code, not in the expression evaluator:

(define (test-calc)
  (assert (calc "123") 123)
  (assert (calc "-123") -123)
  (assert (calc "(123)") 123)
  (assert (calc "(((123)))") 123)
  (assert (calc "1 2 3") 123)
  (assert (calc "1+2") (+ 1 2))
  (assert (calc "1+-2") (+ 1 -2))
  (assert (calc "1-2") (- 1 2))
  (assert (calc "1--2") (- 1 -2))
  (assert (calc "2*3") (* 2 3))
  (assert (calc "2*-3") (* 2 -3))
  (assert (calc "2/3") (/ 2 3))
  (assert (calc "2/-3") (/ 2 -3))
  (assert (calc "2*3+4") (+ (* 2 3) 4))
  (assert (calc "2-3*4") (- 2 (* 3 4)))
  (assert (calc "2/3+4") (+ (/ 2 3) 4))
  (assert (calc "2-3/4") (- 2 (/ 3 4)))
  (assert (calc "2*(3+4)") (* 2 (+ 3 4)))
  (assert (calc "(2-3)*4") (* (- 2 3) 4))
  (assert (calc "2/(3+4)") (/ 2 (+ 3 4)))
  (assert (calc "(2-3)/4") (/ (- 2 3) 4))
  (assert (calc "1+2+3+4") (+ 1 2 3 4))
  (assert (calc "1-2-3") (- (- 1 2) 3))
  (assert (calc "1*2*3*4") (* 1 2 3 4))
  (assert (calc "1/2/3") (/ (/ 1 2) 3))
  (assert (calc "123+456*789") (+ 123 (* 456 789))))

Running the test program should produce no output, on the theory that “no news is good news.”

> (test-calc)

We used filter and assert from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/c4SNAfMw.

Pages: 1 2