Nick Levine’s cl-log rocks… December 10th, 2012
Patrick Stein

Whenever I need logging in my Common Lisp applications, I use Nick Levine’s cl-log library. For many applications, spending the time to run CL:FORMAT during runtime is unreasonable. It is often much better to log something in a raw form and do any formatting/presentation offline rather than online. The cl-log library is the only one that I know of which supports binary logging readily.

Additionally, Nick is incredibly responsive. I found an oversight in a corner-case of cl-log last Friday at 1am. I emailed him about it at 1:19am. In under 5 hours, I had email back pointing me to a new release with that case corrected.

I hope to do a more complete comparison of the existing log libraries at some point. At this point, know that I’ve tried all of the ones on the Cliki which had obvious documentation or examples, and I’ll be using cl-log.

Coder’s Asceticism October 14th, 2012
Patrick Stein

A month or two ago, I watched a bunch of videos of Uncle Bob speaking at various conferences. He’s thought a lot about what makes code testable and maintainable, and he’s an excellent speaker. I’ve even paid to watch some of his hour-ish videos at his Clean Coders site.

In Clean Code, Episode 3 – Functions, he makes the case that we should be striving to keep each function under five lines long. So, over the past month or so, I’ve been trying this out in all of my Scala and Lisp endeavors.

Once you get each function down to four lines or fewer, you start running into symbol-proliferation. You pretty much throw out (LABELS ...) and (FLET ...) unless you need the closure (and then try to say that when you can’t that it’s good enough to just keep the subfunctions under five lines and the body under five, too). You create bunches of functions that should never be called anywhere except the one place it’s called now.

Enter Package Proliferation!

Then, I remembered some Lisp coding style guidelines that I read early this year sometime. Those guidelines advocated having one package for each Lisp file and explicitly making peer files have to import or qualify symbols used from other peer files. This will help me with the symbol-proliferation! Let’s do it!

Enter File Proliferation!

After two weeks of that, I woke up yesterday morning realizing that I wasn’t getting the full benefit from this if I was exporting more than one symbol from each package. If keeping each function tiny is Good and limiting a package to one file is Good, then it is certainly Bad to have one file’s package exporting eight different functions.

So, today, I reworked all of the UNet that I wrote in the last couple of weeks to have one package per file and as few exported symbols per package as possible.

In the interest of testability and modularity, I had broken out a subpackage of UNet called UNet-Sockets that is to be the interface the UNet library uses to interact with sockets. I had realized that I had a file called methods.lisp with four different publicly available (DEFMETHOD ...) forms in it. Now, each is in its own file and package. I did the same for various other declarations.

Now, there is a top-level package which uses Tim Bradshaw’s Conduit Packages to collect all of the symbols meant to be used externally from these packages. If there is an exported function in a package, that is the only exported symbol in that package. If there is an exported generic function declaration in a package, that is the only exported symbol from that package. If there is an exported method implementation in a package, there aren’t any exported symbols from that package. If there is an exported condition in a package, that condition and its accessors are the only exported symbols from that package. If there is an exported class in a package, that class and its accessors are the only exported symbols from that package.

Example

The top-level package of the UNET-SOCKETS system, that defines the interface that UNet will use to access its sockets, consists of just a (DEFPACKAGE ...) form. You can see the full package on github in the unet-sockets.asd and the sockets/ directory.

(org.tfeb.conduit-packages:defpackage :unet-sockets
  (:use :cl)
  (:extends/including :unet-sockets-interface
                      #:sockets-interface)
 
  (:extends/including :unet-sockets-base-socket
                      #:base-socket)
 
  (:extends/including :unet-sockets-hostname-not-found-error
                      #:hostname-not-found-error
                      #:hostname-not-found-error-hostname)

  (:extends/including :unet-sockets-get-address
                      #:get-address)

  (:extends/including :unet-sockets-address+port-not-available-error
                      #:address+port-not-available-error
                      #:address+port-not-available-error-address
                      #:address+port-not-available-error-port)

  (:extends/including :unet-sockets-create-datagram-socket
                      #:create-datagram-socket)
 
  (:extends/including :unet-sockets-send-datagram
                      #:send-datagram)
 
  (:extends/including :unet-sockets-poll-datagram
                      #:poll-datagram))

Conclusion?

The jury’s still out on this for me. On the one hand, the self-flagellation is an interesting exercise. On the other hand, if I’m going to have to export everything useful and import it in multiple places then I’m taking away some of the fun. I feel like I’m maintaining C++ header files to some extent.

I think I’ll keep it up for the UNet project, at least. It makes good documentation to have each exported symbol in a package and file named for that exported symbol. You can open up any file and read the three-to-four line exported function in it. You can see, right there with it, any supporting function it uses that no other files need to use. You can see from the (DEFPACKAGE ...) form at the top where any other supporting functions came from. And nothing else is cluttering up the landscape.

We’ll see if I develop religion on this topic. At the moment, I think it’s eventually going to fall into the moderation in all things bucket. Time will tell.

Polylinguistic Code Improvement September 24th, 2012
Patrick Stein

I have started the Coursera course: Functional Programming Principles in Scala. The first assignment was a few simple recursion problems: calculate a given entry in Pascal’s triangle, verify that the parens are balanced in a list of characters, and count the number of ways one can give change for a given amount with given coin denominations. I did those assignments six days ago.

Last night, for grins, I thought I would implement them in Common Lisp. I started out doing them without referencing the Scala code that I’d written. Then, I got lazy and pulled up the Scala code for the last problem and a half.

For all three problems, I came up with better solutions that translated back into the Scala. Some of it was just the benefit of looking at the previous solution again. Some of it was thinking about it with a new language in mind. Some of it was being more comfortable with Lisp. It was such a dramatic improvement in the code that even though I had scored 10/10 six days ago, I still reworked the Scala code and resubmitted it last night.

As it relates to Common Lisp development specifically…. One of the first Lisp books that I read was Paul Graham’s On Lisp. In that book, he does a great deal of turning recursive functions into tail-recursive functions. I had followed his idiom of calling the internal function rec:

(defun factorial (n)
  (labels ((rec (n accum)
             (if (zerop n)
                 accum
               (rec (1- n) (* n accum)))))
    (rec n 1)))

For the Scala, I started out naming the internal function with a Rec suffix on the function name:

def factorial (n: Int): Int =
  def factorialRec (n: Int, accum: Int): Int =
    if (n == 0) accum
    else factorialRec(n-1, n*accum)
  factorialRec(n,1)

Now, I’m partial to just re-using the function name:

(defun factorial (n)
  (labels ((factorial (n accum)
             (if (zerop n)
                 accum
               (factorial (1- n) (* n accum)))))
    (factorial n 1)))

Some simple tools for processing debug output and log files August 29th, 2012
Patrick Stein

In my current job, we do a great deal of “ex post facto” debugging from debug data that we record during operations. To help me do off-the-cuff analysis of these, I make heavy use of egrep and sed. I have created three scripts that encapsulate the most common patterns where I had complicated sed lines before.

The three scripts are:

  • clip – used to pluck out a particular portion of a line based on a regex of what comes before the portion and a regex of what comes after it
  • clipc – like clip except counts the number of occurrences of each unique plucked-out portion
  • clips – like clip but assumes the plucked out portion is numeric and outputs the sum of all of the plucked out portions

For example, if I had a snippet of Apache log files:

127.0.0.1 - - [10/Apr/2007:10:39:11 +0300] "GET / HTTP/1.1" 500 606 "-" "Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.8.1.3) Gecko/20061201 Firefox/2.0.0.3 (Ubuntu-feisty)"
127.0.0.1 - - [10/Apr/2007:10:39:11 +0300] "GET /favicon.ico HTTP/1.1" 200 766 "-" "Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.8.1.3) Gecko/20061201 Firefox/2.0.0.3 (Ubuntu-feisty)"
139.12.0.2 - - [10/Apr/2007:10:40:54 +0300] "GET / HTTP/1.1" 500 612 "-" "Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.8.1.3) Gecko/20061201 Firefox/2.0.0.3 (Ubuntu-feisty)"
139.12.0.2 - - [10/Apr/2007:10:40:54 +0300] "GET /favicon.ico HTTP/1.1" 200 766 "-" "Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.8.1.3) Gecko/20061201 Firefox/2.0.0.3 (Ubuntu-feisty)"
127.0.0.1 - - [10/Apr/2007:10:53:10 +0300] "GET / HTTP/1.1" 500 612 "-" "Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.8.1.3) Gecko/20061201 Firefox/2.0.0.3 (Ubuntu-feisty)"
127.0.0.1 - - [10/Apr/2007:10:54:08 +0300] "GET / HTTP/1.0" 200 3700 "-" "Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.8.1.3) Gecko/20061201 Firefox/2.0.0.3 (Ubuntu-feisty)"
127.0.0.1 - - [10/Apr/2007:10:54:08 +0300] "GET /style.css HTTP/1.1" 200 614 "http://pti.local/" "Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.8.1.3) Gecko/20061201 Firefox/2.0.0.3 (Ubuntu-feisty)"
127.0.0.1 - - [10/Apr/2007:10:54:08 +0300] "GET /img/pti-round.jpg HTTP/1.1" 200 17524 "http://pti.local/" "Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.8.1.3) Gecko/20061201 Firefox/2.0.0.3 (Ubuntu-feisty)"
127.0.0.1 - - [10/Apr/2007:10:54:21 +0300] "GET /unix_sysadmin.html HTTP/1.1" 200 3880 "http://pti.local/" "Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.8.1.3) Gecko/20061201 Firefox/2.0.0.3 (Ubuntu-feisty)"
217.0.22.3 - - [10/Apr/2007:10:54:51 +0300] "GET / HTTP/1.1" 200 34 "-" "Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.8.1.3) Gecko/20061201 Firefox/2.0.0.3 (Ubuntu-feisty)"
217.0.22.3 - - [10/Apr/2007:10:54:51 +0300] "GET /favicon.ico HTTP/1.1" 200 11514 "-" "Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.8.1.3) Gecko/20061201 Firefox/2.0.0.3 (Ubuntu-feisty)"
217.0.22.3 - - [10/Apr/2007:10:54:53 +0300] "GET /cgi/pti.pl HTTP/1.1" 500 617 "http:/contact.local/" "Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.8.1.3) Gecko/20061201 Firefox/2.0.0.3 (Ubuntu-feisty)"
127.0.0.1 - - [10/Apr/2007:10:54:08 +0300] "GET / HTTP/0.9" 200 3700 "-" "Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.8.1.3) Gecko/20061201 Firefox/2.0.0.3 (Ubuntu-feisty)"
217.0.22.3 - - [10/Apr/2007:10:58:27 +0300] "GET / HTTP/1.1" 200 3700 "-" "Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.8.1.3) Gecko/20061201 Firefox/2.0.0.3 (Ubuntu-feisty)"
217.0.22.3 - - [10/Apr/2007:10:58:34 +0300] "GET /unix_sysadmin.html HTTP/1.1" 200 3880 "http://pti.local/" "Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.8.1.3) Gecko/20061201 Firefox/2.0.0.3 (Ubuntu-feisty)"
217.0.22.3 - - [10/Apr/2007:10:58:45 +0300] "GET /talks/Fundamentals/read-excel-file.html HTTP/1.1" 404 311 "http://pti.local/unix_sysadmin.html" "Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.8.1.3) Gecko/20061201 Firefox/2.0.0.3 (Ubuntu-feisty)"

Then, I might like to quickly see how often different URLs are fetched. I could do this with:

% clipc GET < apache.log | sort -n
1 /cgi/pti.pl
1 /img/pti-round.jpg
1 /style.css
1 /talks/Fundamentals/read-excel-file.html
2 /unix_sysadmin.html
3 /favicon.ico
7 /

If I want to see how often GET is done from various IP addresses, I could do this:

% clipc '^' '- .* "GET' < apache.log
8 127.0.0.1
2 139.12.0.2
6 217.0.22.3

If I wanted to add up the number of bytes sent sending successful pages, do:

% clips '" 200' < apache.log
50078

The clip program defaults to having the what-comes-before regex matching open paren, open bracket, double quote, single quote, or equal sign. It defaults to having the what-comes-after regex matching close paren, close bracket, double quote, single quote, comma, or whitespace. So, if I wanted just the first few dates from the above, I wouldn’t need any arguments:

% clip < apache.log | head -3
10/Apr/2007:10:39:11
10/Apr/2007:10:39:11
10/Apr/2007:10:40:54

Or, I might be interested in my busiest minute:

% clipc '\[' ':\d\d ' < apache.log | sort -nr | head -1
8 10/Apr/2007:10:54

Implementations of the Above Scripts

The clip could be written simply in a few lines of Perl:

my $pre  = shift || '[\[("\'=]';
my $post = shift || '[,\s"\')\]]';

while ( my $line = <> ) {
  # look for $pre followed by whitespace then the (non-greedy) portion to keep
  # followed by some (non-greedy) amount of whitespace followed by $post.
  print "$1\n" if ( $line =~ m{$pre\s*(.*?)\s*?$post}o );
}

From there, clipc is simply:

#!/bin/sh
clip "$@" | sort | uniq -c | sed -e 's/^ *//'

And, clips is simply:

#!/bin/sh
clip "$@" | awk '// { SUM += $1 } END { printf("%d\n", SUM) }'

Visualizing Galois Fields (Follow-up) May 21st, 2012
Patrick Stein

In my previous article, I should have finished by remapping the multiplication and addition tables so that the multiplication table was in cyclic order. In cyclic order, the zeroth column (or row) represents zero and the (i+1)-th column (or row) (for i \neq 0) represents a^i for some generator a. As such, the multiplication table is simply 0 in the zeroth row and column and 1 + ((i+j) \mod 255) for the spot (i+1,j+1).

Once resorted by the order of the powers of a generator a, the multiplication table look the same regardless of the a. The addition, however, looks different for different generators. Below are the addition tables for two of them: a = (1+x) on the right and a = x^3 + x^6 + x^7 on the left. They make as decent a stereo as any of the other pairs so far.

 

Here’s the code that I used to generate the remapping for a given generator.

(defun make-cyclic-remapping (fn generator &optional (limit 256))
  (let ((to (make-array (list limit) :initial-element 0))
        (from (make-array (list limit) :initial-element 0))
        (used (make-hash-table :test #'equal)))
    ;; fill up the lookup tables
    (setf (gethash 0 used) t)
    (nlet fill-tables ((exp 1) (acc 1))
      (when (< exp limit)
        (setf (aref to exp) acc
              (aref from acc) exp
              (gethash acc used) t)
        (fill-tables (1+ exp) (funcall fn acc generator))))
    ;; return a closure around the lookup tables
    (when (= (hash-table-count used) limit)
      (lambda (direction n)
        (ecase direction
          (:to (aref to n))
          (:from (aref from n)))))))

If you’ve read it, you can probably tell by my code that I’m still under the influence of Let Over Lambda. If you haven’t read it, it is quite worth the read.

Then, I used a modified version of the draw-heightmap function which also takes in the remapping function.

(defun draw-mapped-heightmap (op map filename &optional (limit 256))
  (let ((png (make-instance 'zpng:pixel-streamed-png
                            :color-type :grayscale
                            :width limit
                            :height limit)))
    (with-open-file (stream filename
                            :direction :output
                            :if-does-not-exist :create
                            :element-type '(unsigned-byte 8))
      (zpng:start-png png stream)
      (dotimes (xx limit)
        (dotimes (yy limit)
          (let* ((a (funcall map :to xx))
                 (b (funcall map :to yy))
                 (c (funcall map :from (funcall op a b))))
            (zpng:write-pixel (list c) png))))
      (zpng:finish-png png)))
  (values))

Updates In Email

Email:

l