I’ve been looking for an excuse for familiarising myself with PLT scheme’s pattern matching library for a while. Finally, I came across an article about implementing a basic Computer Algebra System. The Ocaml source code can be found here. Using the pattern matching library it can be fairly mechanically translated into scheme.
(require (lib "match.ss")) (define-struct plus (e1 e2)) (define-struct times (e1 e2)) (define-struct divide (e1 e2)) (define MP make-plus) (define MT make-times) (define MD make-divide) (define simplify (match-lambda (($ times a ($ plus b c)) (MP (simplify (MT a b)) (simplify (MT a c)))) (($ divide ($ divide a b) ($ divide c d)) (MD (simplify (MT a d)) (simplify (MT b c)))) (e e))) (define expr->list (match-lambda (($ times a b) (list (expr->list a) '* (expr->list b))) (($ plus a b) (list (expr->list a) '+ (expr->list b))) (($ divide a b) (list (expr->list a) '/ (expr->list b))) (e e))) (define expr (make-times 'x (make-plus 'y 'z))) (printf "orig: ~a~n" (expr->list expr)) (printf "new: ~a~n" (expr->list (simplify expr))) (let ((e (MD (MD 'a 'b) (MD 'c 'd)))) (printf "div: ~a -> ~a~n" (expr->list e) (expr->list (simplify e))))
If I had come across this post a few weeks ago, I probably wouldn’t have even considered the implementation using define-struct. HTDP has certainly improved the way I think about coding scheme now and indeed several of the exercises in the book involve constructing various scheme evaluators that embed a simple CAS like the one above.
The article concludes with the following quote:
“…as you can see, Ocaml’s variant types and pattern matching are a perfect fit for the problems a programmer writing a CAS would face. In fact, few other languages, with the possible exception of Haskell, would have fit this problem as well.”
It seems that with the appropriate extensions, scheme can be a good fit for this type of problem too.