As an ArgoUML contributor I'm going to blog my activities here, so that they may draw interest by other developers or help other developers when doing tasks similar to what I've done. AND(!) the grand vision that makes an Argonaut what he is, TO THRIVE IN THE BIG DANGEROUS WORLD, TAKING THE Argo TO A GOOD SHORE ;-))

Thursday, October 22, 2009

Solution for Programming Praxis' Beautiful Code

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.

Reader Shared items

Followers