The following is my solution to the Programming Praxis' Beautiful Code problem in Common Lisp. (The final code is also in pastebin.com.)
I started from a solution in which I ported the code from C to Common Lisp as directly as possible. For instance, the code for the matchhere
function was this mess:
;;; matchhere: search for re at beginning of text (defun matchhere (re text) (if (= 0 (length re)) 1 (if (and (< 1 (length re)) (char= #\* (elt re 1))) (matchstar (elt re 0) (subseq re 2) text) (if (and (char= #\$ (elt re 0)) (= 1 (length re))) (= 0 (length text)) (when (and (< 0 (length text)) (or (char= #\. (elt re 0)) (char= (elt re 0) (elt text 0)))) (matchhere (subseq re 1) (subseq text 1)))))))
Then I changed the above to use cond
and abstracted (= 0 (length seq))
to empty
, which resulted in this:
(defun matchhere (re text) "search for re at beginning of text" (cond ((empty re)) ((and (< 1 (length re)) (char= #\* (elt re 1))) (matchstar (elt re 0) (subseq re 2) text)) ((and (char= #\$ (elt re 0)) (= 1 (length re))) (empty text)) ((and (not (empty text)) (or (char= #\. (elt re 0)) (char= (elt re 0) (elt text 0)))) (matchhere (subseq re 1) (subseq text 1)))))
Finally, I turned the loop
based match
and matchstar
into tail call form. For illustration, this is what matchstar
initially was:
;;; matchstar: search for c*re at beginning of text (defun matchstar (c re text) (loop when (matchhere re text) do (return 1) while (and (not (equal 0 (length text))) (or (char= c (elt text 0)) (char= #\. c))) when (not (= 0 (length text))) do (setf text (subseq text 1))))
And this is how it is after the refactoring:
(defun matchstar (c re text) "search for c*re at beginning of text" (cond ((matchhere re text)) ((and (not (empty text)) (or (char= c (elt text 0)) (char= #\. c))) (matchstar c re (subseq text 1)))))
All done, I'm pretty happy with the result I have now. It is very similar to the Scheme solution by the Programming Praxis author and it certainly is very Lispy.