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.
I have been using my own customized version of scheme (it’s a preprocessor). One of my favorite things is a pattern matching syntax that I modeled superficially on Haskell. I tried to make it as concise as possible. It serves both as a destructive
pattern-matching system, a constructor-based algebraic type system, and an overloading system.
It’s only superficially like Haskell — it’s of course latently typed, like regular Scheme. However, I have found it to be incredibly useful. I also used to have the problem that I wrote Scheme with a ‘C++ accent’, and this pattern-matching stuff totally cured me of it.
Below is an example of some code implementing linear transformations for various types.
(fun (scale-to (a . rest) ns)
(cons (scale-to a ns) (scale-to rest ns)))
(fun (scale-to () ns) '())
(fun (scale-to a ns)
(scale a (* ns (/ 1.0 (duration a)))))
(fun (union (Extent a b) (Extent 'everything)) (Extent 'everything))
(fun (union (Extent a b) . rest) (union (Extent a b) (apply union rest)))
(fun (union (Extent 'empty) . rest) (apply union rest))
(fun (union) (Extent 'empty))
(fun (union (Extent a b) (Extent 'empty)) (Extent a b))
(fun (union (Extent 'empty) (Extent c d)) (Extent c d))
(fun (union (Extent 'empty) (Extent 'empty)) (Extent 'empty))
(fun (union (Extent 'empty) . rest) (apply union rest))
(fun (union (Extent 'everything) . rest) (Extent 'everything))