Lazy Streams

I’ve been watching the SICP Lectures with a group of coworkers and friends. We just finished the lectures 6a and 6b which describe how to implement lazy lists or streams. I found these stream lectures to be very enlightening, mostly because they teach a new method of solving problems that is not typical in your average programming job. If you have never watched the lectures I highly recommend it!

Implementing streams requires two new special forms, DELAY and
CONS-STREAM. Neither the book or the video lectures go into great
detail about the actual implementation of DELAY and CONS-STREAM. I
assume the reason is you need access to the compiler code or macros to
implement them, and that is surely beyond the scope of the class.

So I decided to take a crack at implementing the code in Common Lisp,
and I was surprised how simple it is. Common lisp of course has
macros, so implementing the special forms is easy:

(eval-when (:compile-toplevel :load-toplevel :execute)
  (defmacro delay (exp)
    "creates a promise to calculate exp"
    `(memo-proc #'(lambda () ,exp)))

  (defmacro cons-stream (a b)
    `(cons ,a (delay ,b))))

DELAY is simply a macro that wraps its arguments into a lambda
expression. This causes the evaluation of the expression to be delayed
until the lambda expression is executed, using FORCE. MEMO-PROC
creates a memoized version of the lambda, making multiple calls to the
expression more efficient.

CONS-STREAM must also be a macro because it needs to pass its
second argument unevaluated to DELAY. The rest of the stream code can
be implemented using plain-old-procedures.

You can do some pretty neat things with streams, like create a
lazy Sieve of Eratosthenes:

(defun sieve (stream)
  "lazy sieve of eratosthenes"
  (cons-stream
   (stream-car stream)
   (sieve (stream-filter
           #'(lambda (x)
               (not (= 0 (mod x (stream-car stream)))))
           (stream-cdr stream)))))

SICP-STREAMS> (defparameter primes (sieve (integers-from 2)))
PRIMES
SICP-STREAMS> (stream-ref primes 100)
547
SICP-STREAMS> (stream-ref primes 1000)
7927

STREAM-REF finds the Nth element in the stream, so the examples
show the 100th and 1000th primes. It turns out that the lazy sieve is
horribly inefficient because it creates a new stream filter for every
prime found. Finding the 10,000th prime will create 10,000 filter
procedures and execute them all to find the next prime!

Here’s an infinite Fibonacci stream:

SICP-STREAMS> (defparameter fibs (cons-stream
                                  0
                                  (cons-stream
                                   1
                                   (add-streams (stream-cdr fibs)
                                                fibs))))
FIBS
SICP-STREAMS> (stream-ref fibs 10)
55
SICP-STREAMS> (stream-ref fibs 50)
12586269025
SICP-STREAMS> (stream-ref fibs 100)
354224848179261915075

And finally, the complete source code:

#|

Lazy Streams in Common Lisp
Author: Anthony Fairchild

Created: 2008.01.05
Last Modified: 2008.01.07

An implementation of the lazy streams found in SICP, using Common
Lisp.

|#

(defpackage sicp-streams
  (:use :common-lisp))

(in-package :sicp-streams)

;; (declaim (optimize (debug 3)))

(eval-when (:compile-toplevel :load-toplevel :execute)
  (defmacro delay (exp)
    "creates a promise to calculate exp"
    `(memo-proc #'(lambda () ,exp)))

  (defmacro cons-stream (a b)
    `(cons ,a (delay ,b))))

(defun memo-proc (proc)
    "returns a memoized version of proc"
    (let ((already-run-p nil)
          (result nil))
      #'(lambda ()
          (if already-run-p
              result
              (progn (setf result (funcall proc))
                     (setf already-run-p t)
                     result)))))

(defun force (exp)
    "evaluates a previously created promise"
    (funcall exp))

(defun stream-car (s) (car s))
(defun stream-cdr (s) (force (cdr s)))

(defun stream-ref (s n)
  "finds the Nth element of stream S"
  (if (= 0 n)
      (stream-car s)
      (stream-ref (stream-cdr s) (- n 1))))

(defun stream-map (proc &rest streams)
  "executes PROC for every element in each stream"
  (if (null streams)
      nil
      (cons-stream
       (apply proc (mapcar #'stream-car streams))
       (apply #'stream-map
              proc
              (mapcar #'stream-cdr streams)))))

(defun stream-filter (pred stream)
  (cond ((not stream) nil)
        ((funcall pred (stream-car stream))
         (cons-stream (stream-car stream)
                      (stream-filter pred
                                     (stream-cdr stream))))
        (t (stream-filter pred (stream-cdr stream)))))

(defun add-streams (s1 s2)
  (stream-map #'+ s1 s2))

(defun stream-for-each (proc stream)
  (if (not stream)
      'done
      (progn (funcall proc (stream-car stream))
             (stream-for-each proc (stream-cdr stream)))))

(defun print-stream (stream)
  (stream-for-each #'print stream))

;;;; Example Usage ;;;;

(defun integers-from (n)`
  "returns a stream of integers starting from N"
  (cons-stream n (integers-from (+ n 1))))

(defun sieve (stream)
  "lazy sieve of eratosthenes"
  (cons-stream
   (stream-car stream)
   (sieve (stream-filter
           #'(lambda (x)
               (not (= 0 (mod x (stream-car stream)))))
           (stream-cdr stream)))))

(defun make-primes-stream ()
  (sieve (integers-from 2)))

(defun make-fibs-stream ()
  (let ((fibs nil))
    (setf fibs (cons-stream
                0
                (cons-stream
                 1
                 (add-streams (stream-cdr fibs)
                              fibs))))
    fibs))

Continuo: Part 2

I decided to create a more graphical view of my continuo game. I find it easier to look at compared to the ASCII version in my previous entry. The color chains are much easier to follow.

I used lispbuilder-sdl to generate the graphics. Each 4×4 card has a thick black border and is labelled with a number representing the play order.

Score: 908

Score: 919

Score: 799

Score: 830

Continuo: My ILC contest entry

This year’s International Lisp Conference is having a programming contest for those attending. Unfortunately for me, I live in the Seattle, WA area and the conference is in Cambridge, England! I love contests like this anyway so I decided to take a crack at it.

The contest is to play a solitaire version of the card game Continuo. The contest page gives a good description of how the game is played so I wont get into that here. The game looks like a lot of fun so I ordered a copy of the real game from a local game shop.

My Lisp solution is very naive but appears to play a decent game. It simply plays the next card in the highest scoring position. I think higher overall scores could be achieved if you take into account cards that have been played already as well as the ones not yet played. I cant really wrap my brain around that one at the moment so my naive solution works just fine for now

I wont post my code until the contest is over, but I will say that it is about 200 lines of highly unoptimized code, including comments and some test code. Using SBCL on Linux it runs in about 16 seconds and conses like nobody’s business. Here’s an example run with test data that scores 852.

CONTINUO> (time (play-continuo '(:RBRB :GYGB :GYRY :BYBY :RBYR :RGRB :RGBG
                                 :BYGY :RGRY :RBRY :RYRY :RYGY :YRBY :BYRY
                                 :BRBY :GBYB :RBGB :GBGB :RYBY :RYRG :GYBY
                                 :RGYR :GBRB :RBYB :YGBY :GBGY :GRBG :BRGB
                                 :YRGY :BGBY :GYGY :RYRB :GRYG :GRGY :RBRG
                                 :RGYG :BGYB :BRYB :GBYG :RGRG :GRGB :RGBR)))
score=852
    - - - - - - - - - - - - - - - - - - - -
    2 1 1 1 1 1 1 1 1 1 1                                       1 1 1 1 1 1
    0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
-22                 G R G B
-21                 R R G G G Y B G
-20                 G G R R Y Y B B
-19                 B G R G B B Y Y
-18                 Y G R G G B Y G R G Y G
-17                 G G R R Y G Y G G G Y Y
-16                 R R G G G G Y Y Y Y G G R G R G
-15                 G R G Y Y Y G G G Y G R G G R R
-14                 B Y B R G Y G Y R Y G R R R G G
-13                 Y Y B B G Y B Y Y Y G G G R G R
-12         Y G B G B B Y Y Y Y B B G G Y Y Y R G Y     B R Y B
-11         G G B B R B Y B B B Y Y R G Y R R R G G     R R Y Y
-10 B Y G B B B G G Y B Y R Y B Y G Y G Y R G G R R     Y Y R R
 -9 Y Y G G G B G Y B B Y Y Y R Y B G G Y Y Y G R Y     B Y R B
 -8 G G Y Y Y B G Y Y Y B B R R Y Y Y Y G G R Y R Y B R B G R B R G
 -7 B G Y B B B G G R Y B Y Y Y R R R Y G Y Y Y R R R R B B B B R R
 -6 G R Y G G G B B B Y B G B Y R Y B Y G Y R R Y Y B B R R R R B B
 -5 R R Y Y Y G B Y Y Y B B B Y B Y Y Y G G Y R Y R G B R B G R B R R G B R
 -4 Y Y R R B G B Y B B Y Y Y Y B B G G Y Y Y R B R Y B R Y G R B G G G B B
 -3 G Y R G G G B B G B Y B B B Y Y Y G Y B R R B B B B R R R R B B B B G G
 -2         B B G G G R Y R Y B Y B B G Y G B B R R R R B B B B R R R B G R
 -1         Y B G B R R Y Y Y R Y G G G Y Y R B R Y Y R B Y G B R G
  0                 Y Y R R R R Y Y Y Y G G R B R B B R B Y   B R G B
  1                 R Y R G Y Y R R G Y G B B B R R R R B B   R R G G
  2                 R Y R B G Y R Y R Y B R R R B B B B R R   G G R R
  3                 Y Y R R R G R Y Y Y B B B R B R Y B R B   B G R B
  4                 R R Y Y G G R R B B Y Y B R G R R B G B
  5                 B R Y R R R G G R B Y R R R G G B B G G
  6                         Y R G R G B G R G G R R G G B B
  7                         G B G B B B G G R G R B B G B R
  8                         B B G G G G B B
  9                         G G B B R G B G
 10                         B G B G
Evaluation took:
  16.28 seconds of real time
  15.820989 seconds of user run time
  0.220014 seconds of system run time
  [Run times include 1.612 seconds GC run time.]
  0 page faults and
  1,848,458,504 bytes consed.
NIL

EDIT: I used slime-profile-package to profile my code and was able to make a very small change that produces the same result as above in only 1.35 seconds. I really love slime

Evaluation took:
  1.35 seconds of real time
  1.352084 seconds of user run time
  0.0 seconds of system run time
  [Run times include 0.048 seconds GC run time.]
  0 page faults and
  62,727,048 bytes consed.

Easy bookmarks in Emacs

Emacs is an incredibly feature rich editor. You can do just about anything you would ever want to do and much more. Unfortunately the power and flexibility of Emacs can be a bit unfriendly and cumbersome at times. I seem to rediscover this fact every 2-3 weeks and I usually customize Emacs in some way to make things easier for me.

My latest discovery is the complicated bookmarking system. Setting a bookmark in Emacs involves moving to the line in the file you want to bookmark, typing C-x r m and then giving the bookmark a unique name. To find the bookmark later, you type C-x r b and then type the unique name you gave the bookmark. This bookmarking system is very flexible but can difficult to work with.

I’ve used Visual Studio in the past and I became quite fond of its simple bookmarking system. You simply type Ctrl-F2 to set a bookmark and F2 to cycle between bookmarks. Shift-F2 cycles bookmarks in reverse. It is such a brain dead system. No need to remember bookmark names. No tiresome keystrokes to type.

Since Emacs is *the* programmable text editor, I was able to extend the existing bookmarking system to emulate the Visual Studio style bookmarks. Now I have a “dumbed down” bookmarking system that is quick and easy to use.

Here’s the code I wrote to make it happen:

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; 
;; Easy bookmarks management
;;
;; Author: Anthony Fairchild
;;

;;;; Keymaping examples
;; (global-set-key [(control f2)]  'af-bookmark-toggle )
;; (global-set-key [f2]  'af-bookmark-cycle-forward )
;; (global-set-key [(shift f2)]  'af-bookmark-cycle-reverse )
;; (global-set-key [(control shift f2)]  'af-bookmark-clear-all )

;; Include common lisp stuff
(require 'cl)
(require 'bookmark)
(defvar af-current-bookmark nil)

(defun af-bookmark-make-name ()
  "makes a bookmark name from the buffer name and cursor position"
  (concat (buffer-name (current-buffer))
          " - " (number-to-string (point))))

(defun af-bookmark-toggle ()
  "remove a bookmark if it exists, create one if it doesnt exist"
  (interactive)
  (let ((bm-name (af-bookmark-make-name)))
    (if (bookmark-get-bookmark bm-name)
        (progn (bookmark-delete bm-name)
               (message "bookmark removed"))
      (progn (bookmark-set bm-name)
             (setf af-current-bookmark bm-name)
             (message "bookmark set")))))

(defun af-bookmark-cycle (i)
  "Cycle through bookmarks by i.  'i' should be 1 or -1"
  (if bookmark-alist
      (progn (unless af-current-bookmark
               (setf af-current-bookmark (first (first bookmark-alist))))
             (let ((cur-bm (assoc af-current-bookmark bookmark-alist)))
               (setf af-current-bookmark
                     (if cur-bm
                         (first (nth (mod (+ i (position cur-bm bookmark-alist))
                                          (length bookmark-alist))
                                     bookmark-alist))
                       (first (first bookmark-alist))))
               (bookmark-jump af-current-bookmark)
               ;; Update the position and name of the bookmark.  We
               ;; only need to do this when the bookmark has changed
               ;; position, but lets go ahead and do it all the time
               ;; anyway.
               (bookmark-set-position af-current-bookmark (point))
               (let ((new-name (af-bookmark-make-name)))
                 (bookmark-set-name af-current-bookmark new-name)
                 (setf af-current-bookmark new-name))))
    (message "There are no bookmarks set!")))

(defun af-bookmark-cycle-forward ()
  "find the next bookmark in the bookmark-alist"
  (interactive)
  (af-bookmark-cycle 1))

(defun af-bookmark-cycle-reverse ()
  "find the next bookmark in the bookmark-alist"
  (interactive)
  (af-bookmark-cycle -1))

(defun af-bookmark-clear-all()
  "clears all bookmarks"
  (interactive)
  (setf bookmark-alist nil))

A Lispy Jigsaw Puzzle Game

My blog has been neglected lately, but I have a good reason. I’ve been playing around with lispbuilder-sdl, a Lisp interface to SDL, used for creating games. I decided to resurrect an old jigsaw puzzle game I wrote a few years ago using pygame. The game was never really finished, as with many of my other personal programming projects.

Converting the old Python code to Lisp was fun. I was able to simplify a lot and performance is much better, mostly due to Lisp being a compiled language. The python version was slow and I really had no way to optimize unless I wrote C extensions. Now with Lisp I can profile the code and add compiler optimizations and declarations to speed things up where they need to be. I still have the option to write C extensions but its unlikely I’ll need to for this game.

Creating each jigsaw puzzle piece was a little challenging and very processor intensive. I start by chopping up an image into square pieces. Each piece overlaps adjacent pieces by about 1/3. These pieces are then rotated 90, 180 and 270 degrees. Next I create a mask image where I draw the puzzle piece outline using bézier curves. I flood fill the outside of the mask image with the mask color, then blit it onto original piece image. Repeat for each rotation. OK, I think I left a few steps out, but my point is, it takes a while to create a puzzle from a source image. Using this process I can create a puzzle from any image.

Each puzzle piece is placed randomly on the screen. Right clicking a piece rotates it. Pieces that belong together can be joined by dragging one piece next to another. They snap together and then remain joined when moving them around. Joined pieces can also be rotated.

It is nowhere near done. I plan on adding many features, at least enough to be able to call it a beta. I would like to get a website with a downloadable binary and source code going soon. Hopefully I can maintain my interest in this and finish something for a change

Here are few screenshots of the game (sorry about the imageshack ads):

Remembering Passwords with Password Grids

Edit: I was contacted by *the* guy, Mike, that invented the password grids, see his comments below. He has republished his article here: http://www.vvsss.com/grid/ I recommend reading it first!

If you are really paranoid like I am then you have a different password for every computer login and Internet site you subscribe to. Hopefully you are not one of the many people out there that use the same password for *everything*. That’s just begging to get your identity stolen.

For years I’ve struggled to come up with the perfect way to keep track of all of my 100+ passwords. Years ago I tried various free and commercial password keeping products such as Passwords Plus, Splash! Wallet and MobiPassword and I never really felt comfortable using them.

Since then I’ve used a simple solution: an encrypted OpenOffice Calc (or MS Excel) spreadsheet. I encrypt the file with a master password and then put all of my login and password information in the file. This system has its own set of vulnerabilities. For example, if I put the spreadsheet on a thumb-drive and lose it, some hacker with too much free time might turn cracking the file into a hobby. Another issue is after I decrypt the spreadsheet it is placed in RAM or a swap file as plain text. Furthermore, when I had to enter my password on a website I would often copy the password to the clipboard and paste it into the web form. The clipboard makes my password available to any other program to read.

I know this sounds like an overly paranoid PITA, but that’s what I did. Until now. I’ve decided to take a more low-tech approach to remembering passwords. I found a web page about password grids years ago and thought it was a neat idea. I wish I could find a link to the site but Google is failing me now. The closest thing I could find was a comment about it on this site. I never really adopted the system before because it seemed a bit silly at the time. After trying all of the other methods and not liking any of them, I’ve decided to give the grids a try. And so far I like them!

The basic idea behind the password grids is simple. Think of an easy to remember but hard to guess pattern on an 8×8 grid. For example, here’s a very simple pattern, the letter F:

+-------------------------------+
|   |   |   |   |   |   |   |   |
|---+---+---+---+---+---+---+---|
|   |   |   |   |   |   |   |   |
|---+---+---+---+---+---+---+---|
|   | 1 | 6 | 7 |   |   |   |   |
|---+---+---+---+---+---+---+---|
|   | 2 |   |   |   |   |   |   |
|---+---+---+---+---+---+---+---|
|   | 3 | 8 |   |   |   |   |   |
|---+---+---+---+---+---+---+---|
|   | 4 |   |   |   |   |   |   |
|---+---+---+---+---+---+---+---|
|   | 5 |   |   |   |   |   |   |
|---+---+---+---+---+---+---+---|
|   |   |   |   |   |   |   |   |
+-------------------------------+

The pattern starts with the number 1 and ends with the number 8. Now that we have a pattern, we can generate a random password grid:

+-------------------------------+
| x | ~ | d | [ | : | j | < | @ |
|---+---+---+---+---+---+---+---|
| ; | , | S | K | ` | a | f | n |
|---+---+---+---+---+---+---+---|
| f | ! | D | ! | u | 7 | 1 | A |
|---+---+---+---+---+---+---+---|
| ~ | s | V | a | 5 | N | k | v |
|---+---+---+---+---+---+---+---|
| V | 9 | | | K | | | o | y | a |
|---+---+---+---+---+---+---+---|
| K | J | H | " | s | r | ] | _ |
|---+---+---+---+---+---+---+---|
| Q | = | y | : | s | # | x | m |
|---+---+---+---+---+---+---+---|
| I | k | T | t | p | ? | T | w |
+-------------------------------+

With the random grid and the pattern we can derive the password. Do this by traversing the pattern on the random grid. The password for this example would be “!s9J=D!|”. Although the password is short, it is very secure. It contains upper and lower case letters, numbers and symbols, like all good passwords should! As I mentioned above, the pattern you use should be easy for you to remember, but hard for others to guess. The patterns can start at any location, move backwards, forwards, diagonal and even skip around. Edit: I’m not sure I made this clear and it may be causing confusion. You only need to remember one pattern for all of your password grids. It would be insanely difficult to remember a different pattern for each grid.

The way you manage your passwords is also simple. Print out a page of random grids, one for each login you have, cut them out into cards, and put them in your wallet. If someone sees the password grid, they cannot derive the password easily unless they know your pattern. If your pattern is ever discovered, then your password cannot be retrieved without having the grid for that password. So its a double-key system, both parts are necessary to get the password. You can also carry around blank grids in case you need to create a new login account while you are sipping coffee at the cyber-cafe.

I created a JavaScript program to generate the password grids. I chose JavaScript (and not Lisp) because it can generate the grids on the client side, not requiring a server. It also makes printing the grids easy from the browser. Here’s a link to the program. It generates 9 password grids and allows you to toggle upper/lower case alpha, numbers and symbols. When printing the page make sure you set it up to shrink to fit.

If you like the system and want to use it, I recommend you save the html file to your local machine. I also highly recommend backing up the grids you use to a text file in case your wallet is lost.

I’m not sure how secure this system really is. With a complicated pattern it seems to me to be very secure. If anyone has an opinion I’d like to hear it.

Edit: If you have a system that works for you, that’s great. One person suggested grouping sites into high/medium/low and only memorizing the passwords for the high’s. This system works good when you have a low number of high security systems. Password grids would be ideal for those high importance passwords. I agree the password grid may be overkill for most people, but for paranoid people like me, it helps me sleep better at night

Coding in !C (or using fseek to make really huge files quickly)

I’ve been crazy busy at work so I’ve been slacking on my posts. Lots of cool things to write about but not enough time! On a positive note I’ve been doing more utility code in Lisp at work. At work I call Lisp !C (not C) to avoid any political issues that could arise. When asked “What’s !C?”, I answer “Its like C, only better! It’s all the rage! Everyone is doing it!”.

This past weekend I worked on a program for work that fragments the hell out of a hard disk. Why, you ask? Its a tool to test the performance of our product under extreme conditions. It fragments the disk by creating files of random size util it reaches a free space threshold, then deletes random files which it previously created. After a few deletes, it creates more randomly sized files. Rinse, repeat. If you let the program run for a while on a disk it produces files with 200+ fragments.

The first working version of the code was horribly slow. It took an *extremely* long time to fill up a disk with files before it got to the delete stage. The file writes were taking way to long to complete. I got to talking to my coworker about this problem and he suggested an old hack which I have never heard of. Instead of writing data to the files, use fseek() to seek to the position where the desired EOF should be and then write a single byte to it. This technique can be used to create huge files in a matter of milliseconds. He explained that this hack can be used to “see” the data in the free space on a disk. How evil is that?

Changing my code to use the new technique made it orders of magnitude faster. But it wasn’t long before we discovered a bug in the new system. I was able to allocate huge files on the system (1GB+) but it would not decrease the amount of free space on the disk. After a throwing out a few wild a crazy theories about it my coworker and I finally discovered what was going on. The file system was not reserving space for blocks that were not written to. So for a 1GB file only one block was getting reserved. The rest of the file must be in the “free block pool” until data is written to it.

To fix the problem I changed the code to write out a single byte per block, thus allocating the the entire block without the overhead of filling the entire block with data. This solution is not quite as fast but it is still way more efficient than the original one, and it works!

The program was written in CLISP, which is a very cool Lisp for doing shell scripting an quick one-off utilities. Here’s the code for the function that eats the disk space:

(defun eat-space (file-name size)
  "Create a bogus file that chews up disk space.  Size is in bytes."
  (let ((file (linux:fopen file-name "w")))
    ;; write a byte every 4k so a block gets allocated
    (loop for x from 0 to (1- size) by 4096
          do (progn (linux:fseek file x 0)
                    (linux:fputc 1 file)))
    (linux:fclose file)))

One other thing to note for any lispers that may be reading this. The code above uses the LINUX package in CLISP, not the standard CL file IO functions. The reason I cannot use the standard functions is FILE-POSITION throws an error when attempting the seek past the end of a file. So in other words, the seek hack does not work in standard common lisp (or at least CLISP’s version of it).

Reader Macros

I’m working on a Lisp program for a friend right now that will import old blog entries from a giant XML file. The file is about 60MB, mostly containing images in base64 format. I’m using CL-XMLS to parse the XML file and for some reason it takes a *long* time (15+ minutes) to parse a large file. It could be that the library was never meant to parse files that big. So working with this data file is a real pain.

Disclaimer: I’m going to have to say at this point that I’ve only been coding Lisp for a year, maybe a little more, so I may get some of this wrong. Corrections are welcome!

Edit: See Levi’s comments and corrections below as I am a bit mixed up on terminology.

Common Lisp has a handy feature that makes working with large amounts of external data easier: reader macros. A reader macro allows you to embed the results of a lisp expression into your code. The lisp expression can be anything, like loading an image file or in my case, a very large XML file. This pushes the time it takes to load the XML file to compile time, rather than run time. Once I’ve compiled the source file, everything is fast binary data at that point. As long as the XML data or the source file doesn’t change, I never have to load it again.

Here are the details. I have a file called blog.lisp that contains the code to load the data from the XML file and the reader macro to embed the results into the code:

(in-package :erik-blog)

(eval-when (:compile-toplevel :load-toplevel :execute)
  (defun parse-blog ()
    (with-open-file (in (merge-pathnames #p"erik-blog.xml" (util:source-file-directory)))
      (xmls:parse in))))

(defvar *blog-data* '#.(parse-blog))

In Common Lisp the syntax for a reader macro is #.(some lisp expression). The last line above embeds the results of the PARSE-BLOG function into the code, which then gets assigned to *BLOG-DATA*. When blog.lisp is compiled, it produces a blog.fasl file which is like a .obj file in C except it can be dynamically loaded. The blog.fasl file that is produced is large because it contains the entire binary representation of the blog data. It takes about a second to load the FASL file into my running lisp image but that is nothing compared to the 15+ minutes it would take to load it from scratch.

This technique can be used to embed any type of data asset into an application. I read somewhere on-line about a game company (Naughty Dog) that compiled graphics, sounds and other assets into their Lisp game. Very cool stuff!

Accused of cheating!

I was accused of cheating today. I’m all riled up so I can’t possibly sleep, which is what I should be doing right now. Grr!

I’m taking a web publishing class as part of my degree program at a local college. The teacher mentioned to us on several occasions that we were not allowed to use WYSIWYG editors for the class. He wants us to hand type all the HTML. That’s fine with me, in fact, I hate WYSIWYG editors. I figured I would not be violating this rule if I were to use Emacs (my editor of choice) which is text based and provides absolutely no WYSIWYG functionality at all. I also assumed it would be OK to write the HTML using compact lisp symbolic expressions to save my poor hands from RSI. In case you’ve never seen HTML written this way, here’s an example:

(:html
(:head (:title “Title of the web page”))
(:body (:h1 “Hello World!”))))

Writing HTML this way saves a lot of typing and avoids the “angle bracket tax”. After writing the HTML using s-exprs I run it through a translator that spits out normal HTML, which is what I turn in to the teacher.

Well, today I got 2 emails from my teacher. The first one said I did a excellent job with my assignment and he even gave me some extra credit points. The next email, which came a few hours later, he retracted my grade stating that I must have used a WYSIWYG editor to do the assignment. My HTML was too advanced and well formatted to be hand written. He then said he would give me a break this one time and let me redo my assignment by hand like the rest of the students in the class.

His response to my assignment made me very mad. I spent a lot of time working on that assignment and to be called a cheater without first allowing me to explain myself really ticks me off. So after cooling down a little bit I sent him a nice email explaining exactly how I did the assignment and included the s-expr source file. I also explained why I did it that way, mentioning RSI and the AB Tax. Hopefully the issue will be resolved in the morning and I can get my excellent grade with extra credit back!

Alright, I’m done venting, maybe I can get some sleep now!

Finally using Lisp at work

I wrote my first Lisp program for work today.   Its a short program that traverses a huge file system (about 1 TB) and finds duplicate files and then prints a nice report showing file names, counts, space consumed, etc.   Ok, it does a little more than that but I can’t talk about the specifics .    Anyway, I had a lot of fun writing it and I finally got a good grasp of working with pathnames, which can be a little confusing in Lisp.  I also got to use quite a bit of my existing utility code like my table printer.

I hope to be able to write more Lisp code at work.  Its unlikely that I will be able to do anything big with it but the quick one-offs are very easy to sneak in without too much resistance!