Saturday, July 27, 2013

A neat reader trick for DO/DO*

So instead of using LOOP every time I needed to use a general purpose looping construct, yesterday I decided to give DO/DO* a shot. The biggest problem that I had with DO was code repetition when the step-form and init-form of an iteration variable were to be the same. For example:

(defun alignment-octets (encryption-fn)
  (let ((block-size (find-cipher-block-size encryption-fn))
        (octet-1 65)
        (octet-2 66))
    (do* ((test-input-1 (make-octets block-size :initial-element octet-1))
          (test-input-2 (make-octets block-size :initial-element octet-2))
          (change-index 0 (1+ change-index))
          (mismatch-start (mismatch (funcall encryption-fn test-input-1)
                                    (funcall encryption-fn test-input-2))
                          (mismatch (funcall encryption-fn test-input-1)
                                    (funcall encryption-fn test-input-2)))
          (mismatch-end (mismatch (funcall encryption-fn test-input-1)
                                  (funcall encryption-fn test-input-2)
                                  :from-end t)
                        (mismatch (funcall encryption-fn test-input-1)
                                  (funcall encryption-fn test-input-2)
                                  :from-end t)))
         ((= block-size (- mismatch-end mismatch-start))
          (subseq test-input-1 0 change-index))
      (setf (aref test-input-2 change-index) octet-1))))

See the iteration vars MISMATCH-START and MISMATCH-END above. I spent some time thinking about how this could be avoided. It didn't seem like DO itself would help us much here. Maybe MACROLET would help, but the solution would probably not be very clean or readable. This seemed like a dead end. However, the Common Lisp reader has a trick up its sleeve -- the dispatch macro character constructs #n= and #n#. To put it simply, if any s-expression is prefixed with #n= (where n is an unsigned decimal integer), then the Lisp reader will replace any corresponding #n# with this s-expression. To be more accurate, the reader treats #n# as a pointer to the same(eq) object that is labeled by #n=.

Let's see this in action:

(defun alignment-octets (encryption-fn)
  (let ((block-size (find-cipher-block-size encryption-fn))
        (octet-1 65)
        (octet-2 66))
    (do* ((test-input-1 (make-octets block-size :initial-element octet-1))
          (test-input-2 (make-octets block-size :initial-element octet-2))
          (change-index 0 (1+ change-index))
          (mismatch-start #1=(mismatch (funcall encryption-fn test-input-1)
                                       (funcall encryption-fn test-input-2))
                          #1#)
          (mismatch-end #2=(mismatch (funcall encryption-fn test-input-1)
                                     (funcall encryption-fn test-input-2)
                                     :from-end t)
                        #2#))
         ((= block-size (- mismatch-end mismatch-start))
          (subseq test-input-1 0 change-index))
      (setf (aref test-input-2 change-index) octet-1))))

An elegant solution to a not so simple problem. Now try this in your favourite language!

Labels: , ,



Comments: Post a Comment

Subscribe to Post Comments [Atom]





<< Home

This page is powered by Blogger. Isn't yours?

Subscribe to Posts [Atom]