Emacs – The Programmable Editor

In the “real world” I work at a small software shop and I write C++ code for a Linux embedded system. I say real world because in my fantasy world I write Lisp code for my own company Anyway, about 100 or so of our C++ header files have the non-standard, Microsoft specific “#pragma once” directive. This directive is short-hand for the more wordy but standard:

#ifndef __SOMEFILE_H__
#define __SOMEFILE_H__
… lots of code…
#endif //__SOMEFILE_H__

In an effort to make the code more portable I decided to replace all of the pragmas with the standard wordy stuff. In most editors I would spend about a 1/2 hour manually searching and replacing text in these files. I would also have to hand type the unique tag for each file. What a pain!

Since I use Emacs this kind of stuff is easy with a quick Elisp helper function:

(defun fix-pragma-once ()
  (interactive)
  (goto-char 1)
  (let ((tag
          (upcase (string-replace-match "."
                                        (concat "__" (buffer-name) "__")
                                        "_"))))
    (when (search-forward "#pragma once" nil t)
      (replace-match (concat "#ifndef " tag) nil t)
      (newline)
      (insert (concat "#define " tag))
      (end-of-buffer)
      (insert (concat "#endif //" tag "n")))))

I then use GREP-FIND to find all of the files with “#pragma once” then click them and run the function. The unique tag is generated by getting the buffer name and adding the underscores and finally upcasing it.

Writing the function and then performing the change on all of the files took about 10 minutes. I saved about 2/3 of the time it would have taken me to do it in vis-studio. But blogging about how cool it is just negated the overall time savings. Oh well!

Darcs woes

I really like Darcs a lot but there are some issues that are making it very difficult for me to love it. The biggest showstopper is performance and memory consumption. My source code repository is about 350mb, not really that big. When I do a "darcs put" or "darcs push" to my remote server it chews up 99% of my processor and 1.3 gigs of memory. I let it run for about 4 hours then killed it. I imaging the 99% processor usage is due to swapping because I only have 1gig of RAM. Darcs is written in Haskell (another reason I was attracted to it) and uses garbage collection, which may be partly contributing to the memory consumption issues.

So I'm going to stick with Subversion for now and maybe try Darcs again when the performance/memory issues are resolved.

Subversion vs. Darcs

I've been keeping my life in Subversion for a few years now and used CVS for years before that. I'm really paranoid about losing data so I put all of my source code, documents, digital photos, everything in a Subversion repository on my Debian server. Subversion allows me to keep copies of my files on multiple computers and it handles all of the syncing and versioning issues for me. A positive side effect of this setup is I get a nearly effortless distributed backup system. I have never lost a file since. I have had hard drives go bad and not even care! If you are interested in setting up your life in Subversion (or any other source control system) do a Google search for "keeping your life in subversion". Many others have written about it.

I stumbled upon Darcs while working with some of the open source Common Lisp libraries. I had never heard of it before so I decided to check it out. The main difference between Darcs and other source control systems is Darcs is distributed. There is no central repository for storing versions. Each checkout of the a repository is also a repository itself. There are several benefits to this model. Each developer essentially has his own private branch and can check in anything to that branch without affecting others. Developers can also send each other patches without affecting the main repository. Darcs supports sending patches via email, which eliminates the need for a publicly accessible server.

Tonight I decided to try to convert my code repository over to Darcs so I can play around with it a bit. I managed to get Subversion and Darcs to play nice together side by side. After a while I noticed a few minor limitations. Darcs does not support soft-links. This is not a big issue since I had a bit of trouble getting subversion to work well with links. Darcs also does not support partial source tree checkouts as far as I can tell. I depend on this in Subversion so I hope I can get over this need.

Next I'll test how well Darcs works with large files. I have 10+ gigs of digital photos, hopefully it won't choke on it! If all goes well I may say goodbye to Subversion!

Pretty Printing Tables

Common Lisp has a really nice function called FORMAT which is like C's printf on steriods. FORMAT uses an embedded language as a format string to allow you to print any data types and structures with ease. Unfortunately I haven't found a way to print tables the way I want using a single format command. So I wrote a function called PRINT-TABLE that takes a two-dimensional array or a list of lists as input and prints something nice like this:

EULER> (defparameter people '(("ID" "First Name" "Last Name")
                              (1 "Fred" "Flintstone")
                              (2 "Barney" "Rubble")
                              (3 "Wilma" "Flintstone")))
PEOPLE
EULER> (print-table people t)
ID|First Name|Last Name
--+----------+----------
1 |Fred      |Flintstone
2 |Barney    |Rubble
3 |Wilma     |Flintstone
NIL

The function has two modes. One mode uses the first row as a header and prints a separator after it, like above. The other mode prints a grid. This is useful when printing the output of my sudoku solver:

EULER> (print-table (solve-sudoku *test-puzzle*))
4|8|3|9|2|1|6|5|7
-+-+-+-+-+-+-+-+-
9|6|7|3|4|5|8|2|1
-+-+-+-+-+-+-+-+-
2|5|1|8|7|6|4|9|3
-+-+-+-+-+-+-+-+-
5|4|8|1|3|2|9|7|6
-+-+-+-+-+-+-+-+-
7|2|9|5|6|4|1|3|8
-+-+-+-+-+-+-+-+-
1|3|6|7|9|8|2|4|5
-+-+-+-+-+-+-+-+-
3|7|2|6|8|9|5|1|4
-+-+-+-+-+-+-+-+-
8|1|4|2|5|3|7|6|9
-+-+-+-+-+-+-+-+-
6|9|5|4|1|7|3|8|2
NIL

Of course for printing soduku puzzles it would be nice to only draw the grid lines for each of the nine regions. I'll probably write a different grid printer for soduku puzzles later and leave this one more general-purpose.

Being fairly new to Lisp I'm sure the code I wrote is not as efficient or small as it could be.  I'm open for suggestions on ways to improve it.  Or perhaps someone can show me a library function or a way to use FORMAT to do this.  Here's the code:

(defun repeat-char (c n)
  "Returns a string repeating character c n times."
  ;TODO: There is probably a shorter/better way to do this
  (format nil "~a" (with-output-to-string (s)
                     (loop for x from 1 to n do (princ c s)))))

(defun calc-column-widths (table)
  "Returns the column widths of a table by iterating thru all cells
and using the max cell width in a column as that column's width"
  (loop with num-of-cols = (length (first table))
        with widths = (loop for x from 1 to num-of-cols collect 0)
        for row in table
        do (loop for cell in row
                 for col-index from 0
                 for cell-length = (length (format nil "~a" cell))
                 when (> cell-length (nth col-index widths))
                 do (setf (nth col-index widths) cell-length))
        finally (return widths)))

(defun print-row-divider(col-widths)
  (print-row (loop for w in col-widths
                   collect (repeat-char #\- w))
             col-widths #\+))

(defun print-row (row col-widths &optional (divider-char #\|))
  (loop for cell in row
        for col-index from 0
        with col-count = (length row)
        when (= col-index (1- col-count))
        do (format t "~a" cell)
        else
        do (format t (format nil "~~~da~~c" (nth col-index col-widths))
                   cell divider-char))
  (format t "~%"))

(defun array->list (a)
  "Converts an array of any dimension to a list of lists."
  (read-from-string (write-to-string a) t t :start 3))

(defun print-table (table &optional (header-p nil))
  "Prints a list of lists or a 2d array in a nicetable format.
If HEADER-P is T then the first row is considered a header and
a divider is printed after it.  If HEADER-P is NIL then all
rows get dividers between them."
  (let* ((table (if (arrayp table)
                    (array->list table)
                    table))
         (col-widths (calc-column-widths table))
         (num-of-rows (length table)))
    (when header-p
        (print-row (pop table) col-widths)
        (print-row-divider col-widths))

(loop for row in table
          for row-index from 0
          do (print-row row col-widths)
          when (and (null header-p)
                    (< row-index (1- num-of-rows)))
          do (print-row-divider col-widths))))

Closures

Before I learned Ruby and Lisp I had no idea what a closure was. I had heard the term quite often but never really cared or understood what it was all about until I learned a programming language that uses them all the time. Now I feel severely crippled in languages like Java and C++ which do not support closures and many other high level language features I've come to appreciate.

Closures are function objects that contain references to variables defined in its lexical scope. They act a lot like a function which refers to and modifies a global variable, only a closure can modify any variable within its lexical scope. An example might help:

(defun make-fibonacci ()
  "returns a fibonacci counter function"
  (let ((a 0)
        (b 1))
    #'(lambda ()
        (let ((c (+ a b)))
          (setf a b)
          (setf b c)
          a))))

This function, MAKE-FIBONACCI, returns a function which can be called to get the next number in the Fibonacci sequence. The LAMBDA call creates an inline function which gets returned to the caller. The variables A and B are defined outside of the scope of the LAMBDA but the lambda can still refer to them as well as modify them with SETF. When MAKE-FIBONACCI returns, the variables A and B, which would normally go away are now still alive inside of our new closure that we returned. A and B are completely inaccessible to anything other than our returned closure. Lets take a look at it in action:

CL-USER> (defparameter next-fib (make-fibonacci))
NEXT-FIB
CL-USER> next-fib
#<Closure Over Function "DEFUN MAKE-FIBONACCI" {58D6B119}>
CL-USER> (funcall next-fib)
1
CL-USER> (funcall next-fib)
1
CL-USER> (funcall next-fib)
2
CL-USER> (funcall next-fib)
3
CL-USER> (funcall next-fib)
5
CL-USER> (funcall next-fib)
8
CL-USER> (funcall next-fib)
13

The first call above sets the variable NEXT-FIB to a new instance of a Fibonacci sequence closure created by MAKE-FIBONACCI. Note the next call correctly evaluates NEXT-FIB as a closure object. All the other calls to (funcall next-fib) call the closure. The closure returns the proper next number in the Fibonacci sequence.

Remember above I said that closures act kind-of like functions which access global variables… well, not quite. The variables that are holding the state of the Fibonacci sequence are encapsulated within the closure now. If I call MAKE-FIBONACCI again to create another sequence counter I will get a new closure with a different set of encapsulated A and B variables. If I used globals instead of closures, I could only have one instance of the sequence counter for the life of the program.

CL-USER> (defparameter fib1 (make-fibonacci))
FIB1
CL-USER> (defparameter fib2 (make-fibonacci))
FIB2
CL-USER> (loop for i from 1 to 10
               do (format t "fib1: ~a - fib2:~a~%"
                          (funcall fib1)
                          (funcall fib2)))
fib1: 1 - fib2:1
fib1: 1 - fib2:1
fib1: 2 - fib2:2
fib1: 3 - fib2:3
fib1: 5 - fib2:5
fib1: 8 - fib2:8
fib1: 13 - fib2:13
fib1: 21 - fib2:21
fib1: 34 - fib2:34
fib1: 55 - fib2:55
NIL

Admittedly this example of closures is trivial and could have easily been implemented with objects. It is in non-trivial code where closures become indispensable tools for writing elegant software.

Abstracting a Common Debugging Pattern (Part II)

I realized that I need to show a better usage example of my PRINT-VARS macro. Here’s a function that returns all the prime numbers under a given max that are a palindrome. I put a PRINT-VARS statement at the end and also added some other variables like DIGITS and DIGITS-LENGTH just for fun.

(defun palindrome-primes (&optional (max 10000))
  "Finds palindrome primes up to the given max."
  (let ((count 0)
        (primes-found nil))
    (do-primes (p 1 max)
      (let* ((digits (digits p))
             (digits-length (length digits)))
        (when (palindrome? digits)
          (incf count)
          (push p primes-found)
          (print-vars p count digits digits-length))))
    (reverse primes-found)))

And here is the output:

CL-USER> (palindrome-primes)
P=2 COUNT=1 DIGITS=(2) DIGITS-LENGTH=1
P=3 COUNT=2 DIGITS=(3) DIGITS-LENGTH=1
P=5 COUNT=3 DIGITS=(5) DIGITS-LENGTH=1
P=7 COUNT=4 DIGITS=(7) DIGITS-LENGTH=1
P=11 COUNT=5 DIGITS=(1 1) DIGITS-LENGTH=2
P=101 COUNT=6 DIGITS=(1 0 1) DIGITS-LENGTH=3
P=131 COUNT=7 DIGITS=(1 3 1) DIGITS-LENGTH=3
P=151 COUNT=8 DIGITS=(1 5 1) DIGITS-LENGTH=3
P=181 COUNT=9 DIGITS=(1 8 1) DIGITS-LENGTH=3
P=191 COUNT=10 DIGITS=(1 9 1) DIGITS-LENGTH=3
P=313 COUNT=11 DIGITS=(3 1 3) DIGITS-LENGTH=3
P=353 COUNT=12 DIGITS=(3 5 3) DIGITS-LENGTH=3
P=373 COUNT=13 DIGITS=(3 7 3) DIGITS-LENGTH=3
P=383 COUNT=14 DIGITS=(3 8 3) DIGITS-LENGTH=3
P=727 COUNT=15 DIGITS=(7 2 7) DIGITS-LENGTH=3
P=757 COUNT=16 DIGITS=(7 5 7) DIGITS-LENGTH=3
P=787 COUNT=17 DIGITS=(7 8 7) DIGITS-LENGTH=3
P=797 COUNT=18 DIGITS=(7 9 7) DIGITS-LENGTH=3
P=919 COUNT=19 DIGITS=(9 1 9) DIGITS-LENGTH=3
P=929 COUNT=20 DIGITS=(9 2 9) DIGITS-LENGTH=3
(2 3 5 7 11 101 131 151 181 191 313 353 373 383 727 757 787 797 919 929)

Also, after Keven’s suggestion in the previous post I modified the original macro to do nothing if *DEBUG* is set to NIL. Here’s the new code:

(defparameter *debug* t)

(defmacro print-vars (&rest vars)
  "If *DEBUG* is set to T, prints variables listed in vars to *trace-output*. The first argumentcan be a string which will be printed directly."
  (when *debug*
    `(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* "~%" ))))