Abstracting a Common Debugging Pattern

No matter what language I’m using, I often debug a program by injecting print or trace statements into the code which go to standard-out or a log file. This classic method of debugging has its advantages and disadvantages that I wont go into. While working on a Project Euler problem the other day I realized that writing trace statements can be quite tedious and make the code extremely ugly to look at. For example, if I want to print out the values of variables a, b and c I have to write this:

CL-USER> (format *trace-output* "A=~a B=~a C=~a" a b c)
A=1 B=2 C=3
NIL

The above format statement requires a format string and a list of variables to output. It may not seem like a lot but when you are adding a bunch of these statements in your code it gets old really quick.

Ideally I want to keep trace statements as small as possible, making them easy to look at and type. Common Lisp makes these kinds of things really easy. Using macros I can abstract out all of the ugliness. Here’s what I want my new trace statement to look like:

CL-USER> (print-vars a b c)
A=1 B=2 C=3
NIL

Notice the output of PRINT-VARS is the same as the FORMAT function above, but I did not have to type the *trace-output* stream or the format string. Getting rid of the *trace-output* stream could have simply been done with a wrapper function. But eliminating the format string requires knowledge of the variable names as well as their values. How could you do this in a more conventional language such as C++, Java or C#? I don’t think it can be done. C# probably stands the biggest chance of having a language feature to do it.

Enough language bashing, here’s the Common Lisp magic.. er, I mean, macro code to make it work:

(defmacro print-vars (&rest vars)
  "Prints variables listed in vars to *trace-output*. The first argument
can be a string which will be printed directly."
  `(progn ,(when (stringp (first vars))
                 `(format *trace-output* "~A " ,(pop vars)))
          ,@(loop for var in vars
                  collect `(format *trace-output* "~A=~A " ',var ,var))
          (format *trace-output* "~%" )))

Now I admit, the code looks a bit ugly, especially to those who don’t know lisp. However, I will likely never have to look at it again and my trace statements, which I write and look at all the time are now simple and clean.

Prefix Notation

It has been a while since I've posted anything so here's a quick post. In the next post I will write about a cool lisp macro I wrote for debugging so stay tuned!

Forget everything you've heard about what makes Common Lisp a cool language: real macros, code is data, dynamic variables, etc. Sometimes its just the simple things that make lisp cool, like prefix notation.

Prefix notation, also known as polish notation, is the notation lisp uses to structure code. Many other languages, like C, Java and C# use infix notation. In Java you could write:

1+1;

With lisp's prefix notation you would write:

(+ 1 1)

If you want to add a bunch of numbers together in Java you would write this:

int num = 1 + 2 + 3 + 4 + 5;

In Lisp:

(setf num (+ 1 2 3 4 5))

The major difference here is Java is limited to two operands per operator where lisp can have any number of operands per operator. Things get really interesting when using comparison operators. This lengthy comparison in Java:

a < b && b < c && c < d

can be written in Lisp like this:

(< a b c d)

You can also "apply" operators to an arbitrary list of inputs. For example, using the above comparison operator you can tell if a list of numbers is sorted:

CL-USER> (defparameter sorted-numbers '(1 2 3 4 5 6 7 8 9 10))
SORTED-NUMBERS
CL-USER> (defparameter unsorted-numbers '(7 8 2 3 4 5 9 10 1 6))
UNSORTED-NUMBERS
CL-USER> (apply #'< sorted-numbers)
T
CL-USER> (apply #'< unsorted-numbers)
NIL

It takes a while to get used to prefix notation but I am finding that there are many advantages to using it over the more often used infix style.

Project Euler and Lisp

Whenever I try to tackle learning a new programming language I look for a simple project to use as an exercise. Many times I simply rewrite one of my existing utilities in the new language. Shortly after I started learning Lisp I discovered Project Euler at Mathschallenge.net and found it was a great way to learn a new language and exercise my math skills at the same time.

Project Euler is a collection math problems that are difficult to solve on paper but easy with a program if you know the right algorithm. For example, the first euler problem is: Add all the natural numbers below 1000 that are multiples of 3 or 5. The problems range from very simple problems that can be solved in a matter of minutes to problems that require banging your head against the wall for a few days. The dynamic scoring system adjusts the points given for a solved problem based on how many others have solved it. The problem solutions have to execute in under 1 minute, which means you have to be very clever sometimes when choosing your algorithm.

After solving more than twenty problems in a single source file I started thinking about eliminating code duplication, unit testing and the other things a good programmer is always supposed to do. I went through several unsuccessful attempts at making the code clean and maintainable. I finally settled on method using macros to define a sort of domain specific language for solving euler problems. I created a single macro that defines a problem. When compiled, this macro expands into all of the necessary code to handle unit testing and pretty much anything I want it to do in the future (I've already thought of enhancements while writing this post!)

First, lets look at the code that uses the macro to define a problem. Here's the code for problem 1:

(defproblem 1 233168
  "Add all the natural numbers below 1000 that are multiples of 3 or 5."
  (loop for x from 3 to 999
        when (or (zerop (mod x 3))
                 (zerop (mod x 5)))
        sum x))

The macro is called DEFPROBLEM. The first parameter is the problem number and the second is the answer. If I don't know the answer to the problem yet I simply pass NIL. The other parameters are the description of the problem and the code itself. An unanswered problem definition looks like this:

(defproblem 113 nil
  "How many numbers below a googol (10^100) are not "bouncy"?")

After a problem is defined, I can execute the problem or its unit test at the REPL.

EULER> (problem-1)
233168
EULER> (test-problem-1)
Testing problem 1
Evaluation took:
  0.0 seconds of real time
  0.0 seconds of user run time
  0.0 seconds of system run time
  0 page faults and
  7,728 bytes consed.

NIL
EULER>

The unit test function simply times the execution of the problem and verifies the return value of the problem code matches the value of the answer supplied to the problem definition. If the answer is incorrect and not NIL, an error is thrown.

I also provide a TEST-ALL function in the framework that executes the unit test functions for all defined problems:

EULER> (test-all)
Testing problem 1
Evaluation took:
  0.0 seconds of real time
  0.0 seconds of user run time
  0.0 seconds of system run time
  0 page faults and
  8,072 bytes consed.

Testing problem 113
Problem 113 is not solved yet, skipping test.

NIL
EULER>

So what I've really done here is create a simple abstraction of a euler problem using a macro. The macro keeps all of the framework details hidden and allows me to concentrate on solving the problems.

Finally, here is the code for the definition of the framework including the DEFPROBLEM macro:

(defmacro defproblem (problem-number answer documentation &rest body)
  "Defines a euler problem.  Creates a problem-x function containing
the code for the problem and test-problem-x unit test function."
  `(progn
    ;keep track of created problem numbers
    (unless (member ,problem-number *problems*)
      (setf *problems* (sort (push ,problem-number *problems*)
            #'<)))
    ;create problem-x function
    (defun ,(intern (format nil "PROBLEM-~d" problem-number)) ()
      ,documentation
      ,@body)
    ;create test-problem-x function
    (defun ,(intern (format nil "TEST-PROBLEM-~d" problem-number)) ()
      (test-problem ,problem-number ,answer))))

(defun test-problem (problem-num answer)
  "Verifies a problem returns the correct answer. Dont test problems with NIL answers."
  (format t "Testing problem ~d~%" problem-num)
  (if (null answer)
      (format t "Problem ~d is not solved yet, skipping test.~%" problem-num)
      (assert (= answer
                 (time
                  (funcall (intern (format nil "PROBLEM-~d" problem-num)))))))
  (format t "~%"))

(defun test-all ()
  "Test all euler problems"
  (loop for problem-num in *problems*
        do (funcall  (intern (format nil "TEST-PROBLEM-~d" problem-num)))))