This is a follow-up to my post last year about simplistic heat-maps using Vecto. To recap, I’m trying to make heat maps for google maps overlays.

Here’s how it works in a nutshell:

1. From javascript I pass to the server the lat/lng region currently shown on the google map, and what size heat map to generate, in pixels.
2. lisp pulls weights from my database within the given lat/lng region
3. lisp iterates over the db results, mapping lat/lng to x/y coordinates for the final heat map image
4. lisp uses the list of mapped (x y weight) to draw the heat map in png
5. javascript throws the png on top of the google map

I tried a few things based upon the comments I got back from the helpful lisp community.

• used zpng to get direct pixel access, and calculated each pixel’s color using a weighted average of nearby points using distance.  This didn’t produce good images, and was pretty slow.
• used zpng to get direct pixel access, and calculated each pixel’s color using the gravity formula against nearby points.  This didn’t produce good images, and was very slow.

I did some more research and learned about the Generic Mapping Tools and bicubic interpolation. The GMT is a set of C programs, similar to the Imagemagick suite.  GMT showed one way to draw heat maps in the Image Presentations tutorial.  It spoke of gridded data sets, and that gave me one more vecto-based idea: split the desired heat-map into a grid and color each square in the grid based upon an average of the weights mapped in that square.  This is a neat effect, but not what I was going for:

This is reasonably fast, taking about 1 second on my dev server.  To quickly find what weights belong in which grid square, I make a spatial index of all the weights, using an r-tree from the spatial-trees library.

The next method I tried was to use interpolation to get a smooth look.  I found Cyrus Harmon’s ch-image library supports image interpolation, and got to it.  As Patrick Stein noted elsewhere, ch-image isn’t easy to install.  It’s not asdf-installable, and the project page doesn’t list all its dependencies.  For future reference, here’s what I think I needed to install it:

(asdf-install:install "http://cyrusharmon.org/static/releases/ch-asdf_0.2.14.tar.gz")
(asdf-install:install "http://cyrusharmon.org/static/releases/ch-util_0.3.10.tar.gz")
(asdf-install:install "http://cyrusharmon.org/static/releases/smarkup_0.4.2.tar.gz")
(asdf-install:install "http://mirror.its.uidaho.edu/pub/savannah/cl-bibtex/cl-bibtex-1.0.1.tar.gz")
(asdf-install:install "http://cyrusharmon.org/static/releases/clem_0.4.1.tar.gz")
(asdf-install:install "http://cyrusharmon.org/static/releases/ch-image_0.4.1.tar.gz")

Armed with ch-image, now the drawing process becomes:

1. draw a small image, coloring pixels based upon weights
2. enlarge the small image with interpolation

The first step is very similar to the code I wrote to make the grid version above.   Instead of drawing a rectangle, I draw a pixel using ch-image’s pixel access functions.  This was a little weird because ch-image’s coordinate system has 0,0 at the top left of the image.  I’m still not sure how to best choose the size of this smaller image, but ultimately it should depend on my data.  For now I just have it hard-coded be 20x smaller than the desired size:

Yep, that’s pretty small.  Applying a transform to scale it up to the desired size using bilinear interpolation yields:

It looks pretty good and takes about a half-second to draw.  If you click into the larger version, you can see some discontinuities in there, which is a well-known result of bilinear interpolation.  However, based upon other graphics I’ve seen, what I really want is bicubic interpolation.  Luckily, ch-image has this built in:

Oops, maybe not so luckily.  I can certainly see the kinds of look I’m wanting in all the garbled stuff, but ch-image is freaking out somewhere there.

Bilinear it is!  Here’s a screenshot of the overlay in place on the map:

It’s pretty fast, and looks pretty nice, and is fairly close to the look I wanted.  I probably still have some off-by-one errors somewhere, and need to check the git repos for the ch-* libs to see if there might be newer versions than the tarballs I installed.  I still count this as great progress for 5 hours of coding and research.  Huzzah for the much-maligned lisp libraries!

• Common Lisp starter pack
• Forum post

The candidate will be a well-versed Lisp developer with expert system expertise. Candidates do not have to have Rules experience for this role.
The development group consists of a small focused team of professionals, responsible for the design, development, and maintenance of the Convergence Point service. ConVergence Point is offered to clients through a 24×7x365 Software as a Service (SaaS) model.

It’s been a while since we mentioned ITA.

You might look at the full time and internship jobs at ITA that mention Lisp.

Update: currently, only one of positions listed, an internship, is primarily a Lisp job.

MBA Michael Bailey Associates zoekt “Developer”

• there is an bug (#567912) that the first call to (clc:clc-require :<foo>) will fail with clisp due to a loop where there is no looping...
• We still need to find a way to precompile libraries
• Because asdf is now taking care of placing the fasl file in the correct place, we cannot remove fasls for a specific implementation or library, so we nuke them all. Not optimal.

Over the weekend, I wrote a little client library to a queue server that I’ve grown very fond of over the last year, beanstalk. It’s a very simple queue server, but it comes with a nice feature (delayed jobs) that I’ve had a use for recently.

The queue server is nicely engineered (written in C, works with queues a few million jobs deep), and very fast; it has guards in the protocol against worker failure, and it was a pleasure to implement: The whole thing is just 320 lines of code, including comments.

You can get the source (and a tiny example) at the cl-beanstalk github repository.

Hope this is useful for anyone else - I am planning on using this in autobench myself, to distribute work across several build hosts.

• 80's retro McCLIM user interface.
• No documentation or online help.
• Maximally frustrating color sliders, using IHS colorspace.
• Intuitive modeless drawing UI, achieved by including only a pencil tool.
• Saves/loads files only in its own format, based on unportable s-expressions.
• Requires X11 and SBCL with threads, to keep out the riffraff.
• User-editable brush shape.
• Remap Color and Silhouette commands, for tracing previous frames.
• Realtime animated preview plays while you work.

[note from Clemens Harsch at limedrive.de]

Hello Will,
We’re developing high-quality browser-based-games and are looking for serveral skilled CL-Programmers (Senior & Junior Software Engineers) for our Headquarters in Hamburg|Germany and/or Augsburg|Germany.
Website: http://limedrive.de
One of our projects: http://thanandar.de

Developers with powerfull skills in Steel Bank Common Lisp are absolutely prefered.

Must have:

• good German in speach and script
• strong grip over MySQL, PostgreSQL, javascript, php/html/css and CL
• expertise as Server-Administrator with Unix based Systems like Linux/Ubuntu and the Apache Webserver
• ability to write high-performant, beautiful code
• understanding of how the Web works…

Nice to have:

• experience in SBCL (Steel Bank Common Lisp)
• experience RoR, Java and C
• experience with Berkeley DB, Hunchentoot Webserver
• prior experience in leading small teams up to 5 people
• You are a highly motivated individual with leadership skills
• You’ve got experience in Game-Development, especially with browser-based-games

Please apply to:
contact then the at sign, limedrive dot de

Thanks for publishing our Lispjob!
with best regards

Clemens, CEO of limedrive studio

Title: Berlin Lispers Meetup
Date: Tuesday February 2, 2010
Time: 7pm onwards
Venue: New Thinking Store, Tucholskystr. 48, 10117 Berlin
Map: Google Map
Transport: U-Bahn Oranienburger Tor, S-Bahn Oranienburger Straße

You are kindly invited to the third "Berlin Lispers Meetup", an informal gathering for anyone interested in Lisp, beer or coffee, organized by Willem Broekema and Hans Hübner.

This time, the meeting will take place in the New Thinking Store (see address above), as we have a presentation by Stefan Richter of freiheit.com who will talk about a Cloud-deployed web application written in Clojure. The full title of his presentation is

How a Clojure pet project turned into a full-blown cloud-computing web-app.
Or:
What are the differences between a Clojure web-app and one written in Java or Common Lisp?

Stefan will give his talk in German or English, depending on the preference of the audience. It will start at 19:00h.

Thanks go to Franz Inc., the maker of Allegro Common Lisp and the Allegrograph Web 3.0 database for sponsoring the meeting by paying for the venue.

Please join for another evening of parentheses (and brackets this time)!

P.S.: If you are interested in given a Lisp related presentation on one of our next meetings, please get in touch!

I've made some minor updates to l1sp.org. Dictionaries are now accessible by section number (e.g. http://l1sp.org/cl/17.3), and the glossary is now indexed (e.g. http://l1sp.org/cl/glossary/binding). Hope it's useful.

• Matthias Felleisen, of Northeastern University and the TeachScheme! project will speak on the topic of PLT Scheme;

• Nick Levine, independent consultant at Ravenbrook, has twenty years of Lisp experience after a serendipitous encounter, and over that time has taken on roles from system implementor to contractor; from educator to conference organiser; and most currently, author of a new book on Lisp;

• Kent Pitman, with his background of over three decades of involvement in the design, implementation and use of Lisp-family languages, will offer historical perspectives and thoughts for the future.

I hope that this lineup provides additional motivation for people to complete their submissions!

I've been trying to make small improvements to the Erik Naggum comp.lang.lisp archive. One of them is to change the Google Groups link on an article from Google's individual article view to the thread view, so you can quickly see more of the context of the article without clicking multiple times.

Unfortunately, getting the thread view URL requires scraping an individual article's HTML, and Google limits the rate at which you can do that from a single IP. Fortunately, the task is easily distributed among multiple workers.

Here's a bit of client and server code I used to get some friends help me gather the 5000+ links I was looking for.

First, the client. It's meant to be run with sbcl --load megamid.lisp. Here's what it does:

• Fetch a message id from my server
• Fetch that message id's page from Google
• Scrape the thread URL from that page
• Post the message id and thread URL back to my server
• Repeat while my server still returns message ids

;;;; megamid.lisp

(sb-ext:disable-debugger)

(require 'asdf)
(require 'drakma)

(defpackage #:megamid
  (:use #:cl)
  (:shadowing-import-from #:drakma
                          #:http-request))

(in-package #:megamid)

(defun parameters (params)
  (loop for (key value) on params by #'cddr
        collect (cons (string-downcase key) (princ-to-string value))))

(defun request (url &key; (method :get) parameters)
  (multiple-value-bind (content code headers uri stream must-close)
      (http-request url
                    :method method
                    :parameters (parameters parameters)
                    :want-stream nil)
    (declare (ignore headers uri))
    (when must-close
      (ignore-errors (close stream)))
    (when (<= 400 code)
      (error "Bad response code ~A for ~A ~A" code method url))
    (unless (= 204 code)
      content)))

(defun google-page (message-id)
  (request "http://groups.google.com/groups"
           :parameters (list :selm (string-trim "<>" message-id))))

(defun extract-thread-link (string)
  "Return the URL linking to a thread discussion in STRING, which
should be a Google Groups article HTML page."
  (let ((index (search "/browse_thread/" string)))
    (when index
      (let ((start (1+ (position #\" string :from-end t :end index)))
            (end (position #\" string :start index)))
        (concatenate 'string "http://groups.google.com"
                     (remove #\? (subseq string start end)))))))

(defun thread-link (message-id)
  (extract-thread-link (google-page message-id)))

(defun message-id-p (string)
  "Is STRING a lot like a message-id?"
  (and (char= (char string 0) #\<)
       (char= (char string (1- (length string))) #\>)
       (position #\@ string)))

(defun resolver-loop ()
  (loop
    (let ((message-id (request "http://lisp.xach.com/naggum/unresolved")))
      (unless (and message-id (message-id-p message-id))
        (sb-ext:quit))
      (let ((thread-link (thread-link message-id)))
        (request "http://lisp.xach.com/naggum/resolve"
                 :method :post
                 :parameters (list :message-id message-id
                                   :url (or thread-link "none")))
        (format t "~A => ~A~%" message-id thread-link)))
    (force-output)
    (sleep (+ 3 (random 3)))))

(resolver-loop)

Here's the server. Basically:

• Keep a stack of all message ids
• If a client requests a message id, pop the stack and return one
• If a client posts a message id and url, save it to a file

;;;; megamid-server.lisp

(defpackage #:megamid-server
  (:use #:cl)
  (:shadowing-import-from #:sb-thread
                          #:make-mutex
                          #:with-mutex))

(in-package #:megamid-server)

(defvar *lock* (make-mutex :name "megamid"))
(defvar *pending-message-ids* '())

(defun message-id-p (string)
  "Is STRING a lot like a message-id?"
  (and (char= (char string 0) #\<)
       (char= (char string (1- (length string))) #\>)
       (position #\@ string)))

(defun string-digest (string)
  (ironclad:byte-array-to-hex-string
   (ironclad:digest-sequence 'ironclad:md5
                             (sb-ext:string-to-octets string
                                                      :external-format :ascii))))

(defun file (message-id)
  (make-pathname :name (string-digest message-id)
                 :type "txt"
                 :defaults #p"site:db;naggum;thread-urls;"))

(defun resolvedp (message-id)
  (probe-file (file message-id)))

(defun load-unresolved ()
  (with-mutex (*lock*)
    (setf *pending-message-ids*
          (remove-if 'resolvedp
                     (site:file-lines #p"site:db;naggum;msgids.txt")))))

(defun handle-resolve ()
  (let ((message-id (hunchentoot:post-parameter "message-id"))
        (url (hunchentoot:post-parameter "url")))
    (when (and message-id url
               (message-id-p message-id))
      (let ((file (file message-id)))
        (with-mutex (*lock*)
          (unless (probe-file file)
            (ensure-directories-exist file)
            (site:barf url file)))))
    "ok"))

(defun handle-unresolved ()
  (let ((message-id))
    (with-mutex (*lock*)
      (setf message-id (pop *pending-message-ids*)))
    (if message-id
        message-id
        (progn
          (setf (hunchentoot:return-code*) 204)
          ""))))

(site:handle-url "/naggum/resolve" 'handle-resolve)
(site:handle-url "/naggum/unresolved" 'handle-unresolved)

With a bunch of people helping me, I was able to get all the URLs I needed within a few hours.

Last post I introduced UCW and how to get started by creating a hello world page. However, in that example we were crudely using FORMAT to outtput a string to an HTTP response stream.

Today we will be rendering HTML in a much more expressive, reusable, and abstracted way by using UCW's component-oriented UI framework.

To illustrate this, we will create a web page that displays an HTML form that will simply open your default mail program and send its values. Kind of cheesy, and pre-CGI times, but hey, I don't want to distract today's subject with persistance libraries or anything like that for now. I want to focus on components as they are a basis for Uncommon Web applications.

Introducing UCW Components

Simply put, UnCommon Web components are instances of CLOS classes with the STANDARD-COMPONENT-CLASS metaclass. However, UCW provides a macro for defining component classes, giving us some syntactic sugar. The following two forms are thus the same:

(defclass example-message ()
  ((message :accessor message
	    :initarg :message
	    :initform "World!"))
  (:metaclass standard-component-class))
(defcomponent example-message ()
  ((message :accessor message
	    :initarg :message
	    :initform "World!")))

I will be using the defcomponent in my examples as it is obviously more concise, and it abstracts the MOP aspect of UCW from our view. If you want to learn more about the CLOS MetaObject Protocol, visit:
http://www.alu.org/mop/index.html

Uncommon Web defines some standard components that we can use to define our web app—such as, window components. "WINDOW-COMPONENTS are the top-level wrappers. Generally, they print the html header and then delegate to another component for the rest."

If we dive into UCW's standard components, we find the following fun inheritance chain:
STANDARD-WINDOW-COMPONENT -> BASIC-WINDOW-COMPONENT -> BASIC-WINDOW-FEATURES-MIXIN + WINDOW-COMPONENT

STANDARD-WINDOW-COMPONENT
Specializes BASIC-WINDOW-COMPONENT by adding a :body slot. The body is mainly used for nesting components as shown by the use of the :component t option. Remember that when nesting components, the slot that contains the component should be marked :component t, as the STANDARD-WINDOW-COMPONENT does:

(defcomponent standard-window-component 
  (basic-window-component)
  ((body
    :initform nil
    :accessor window-body
    :component t
    :initarg :body)))

BASIC-WINDOW-COMPONENT
No slots are defined but it inherits the BASIC-WINDOW-FEATURES and WINDOW-COMPONENT superclasses. For convenience, apparently. :)

(defcomponent basic-window-component
    (basic-window-features-mixin window-component)
  ()
  (:documentation
   "A convenience class for writing window components."))

BASIC-WINDOW-FEATURES-MIXIN
The name is pretty self-explanatory, as it defines slots for the following features of a window (descriptions are from the documentation strings):

• Title
• Stylesheet: "The URL of the css file to use as a stylesheet for this window."
• Icon: "Optional URL for an icon."
• doctype: "Doctype for this window."
• content-prologue: "Unless nil it's printed <:as-is before any other output. Suitable for <?xml...?> lines."
• html-tag-attributes: "A yaclml attribute list that'll be rendered into the <:html tag's attributes."
• javascript: "List of javascript includes."

WINDOW-COMPONENT
These components are the top-level wrappers. Generally, they print the html header and then delegate to another component for the rest.

• content-type: "The Content-Type header for the http response (also used in the meta tag)"

Defining custom components

So let's go ahead and define a new component that subclasses STANDARD-WINDOW-COMPONENT:

(defcomponent orders-window (standard-window-component)
  ()
  (:default-initargs
      :title "Book Order Form"))

Notice how we do not define any new slots, but rather supply a default initarg called :title, which refers to the title slot defined in BASIC-WINDOW-FEATURES-MIXIN.

Now let's create two components that will encapsulate our form's display code. One will be for the form itself and the other for a dropdown list.

(defcomponent form-component ()
  ())
(defcomponent products-dropdown ()
  ())

Simple enough, eh? The magic happens when we specialize the generic RENDER function and we don't need to make these components generic enough to justify defining slots for them just yet. If you find yourself defining similar components over and over, you could probably create a more generic component that could be used as a plug-in widget or something where you wouldn't even have to write the HTML code anymore in order to render it.

Rendering components

Once a component is defined, we need to specialize the generic RENDER function for it. However, components derived from UCW's standard components--such as WINDOW-COMPONENT--already have RENDER methods defined. If you don't want to change how your window component is rendered, you don't need to specialize the generic RENDER function yourself. If you did, you could combine the superclasses' RENDER method by calling CALL-NEXT-METHOD somewhere in the body---unless you wanted to completely implement the desired behavior of the generic function (PCL ch 16), in which case you'd omit CALL-NEXT-METHOD.

For the time being, let's not specialize the RENDER function on our ORDER-WINDOW. Let's go ahead and define render methods for our form and our dropdown component:

(defmethod render ((form form-component))
  (<:form :method "post" :action "mailto:felideon@gmail.com"
	  (<:as-html "Name: ") (<:text :name "Name") (<:br)
	  (<:as-html "Address: ") (<:text :name "Address")
	  (<:br)
	  (<:as-html "Phone: ") (<:text :name "Phone") (<:br)
	  (<:p) (render (make-instance 'products-dropdown))
	  (<:p) (<:submit :value "Place Order")))
(defmethod render ((products products-dropdown))
  (<:select :name "Product"
   (<:option :value "PCL" "Practical Common Lisp")
   (<:option :value "C@W" "Coders At Work")
   (<:option :value "OOPCLOS"
"OOP in Common Lisp: A Programmer's Guide to CLOS")
   (<:option :value "AMOP"
"The Art of the Metaobject Protocol")
   (<:option :value "GENTLE"
"Common Lisp: A Gentle Intro to Symbolic Computation")))

Notice how we're manually rendering the products dropdown by calling the RENDER method on an instance of PRODUCTS-DROPDOWN. This would normally never be done in UCW, since:

In general, UCW calls the RENDER method as part of the RERL. However, in this case we never pass control to a component (we haven't made it to control flow yet), so something like this is neccessary.

Finally, we define an entry point in order to get to our page:

(defentry-point "index.ucw"
    (:application *orders-ucw-application*
		  :with-call/cc nil)
    ()
  (render (make-instance 'order-window)))

Note that "The :WITH-CALL/CC option is set to NIL here. This is not strictly neccesary, but were not using UCW's continuation based features yet, so we can gain a minor performance increase by avoiding the overhead of the CPS interpreter."

UCW Method Combination

Another topic I want to touch on is regarding method combination---at least with respect to UCW. For a primer on what method combination is and how it works, I recommend reading chapter 16 of Practical Common Lisp.

UCW apparently uses a library, also written by Marco Baringer, called arnesi. In addition to other utilities, such as the CPS transformer, it provides a MOP compatibility layer (that pre-dates Pascal Constanza's closer-mop) that extends the standard method combination, like so:

"Same semantics as standard method combination but allows
\"wrapping\" methods. Ordering of methods:
 (wrap-around
   (around
     (before)
     (wrapping
       (primary))
     (after)))
:wrap-around, :around, :wrapping and :primary methods call
the next least/most specific method via call-next-method (as
in standard method combination).

You'll see these auxiliary methods used a lot in UCW's source code. I'm encouraged to encapsulate my rendering code like this as it appears to be a very malleable way to reuse and adapt display code.

Auxiliary methods are just a convenient way to express certain common patterns more concisely and concretely. They don't actually allow you to do anything you couldn't do by combining primary methods with diligent adherence to a few coding conventions and some extra typing. Perhaps their biggest benefit is that they provide a uniform framework for extending generic functions. (PCL)

So now let's refactor our form's RENDER method a bit by splitting it up using the standard method combination qualifiers:

(defmethod render :around ((form form-component))
  (<:form :method "post"
	  :action "mailto:felideon+blog@gmail.com"
	  (call-next-method)))
(defmethod render :before ((form form-component))
  (<:h1 (<:as-html "Book Order Form")))
(defmethod render ((form form-component))
  (<:as-html "Name: ") (<:text :name "Name") (<:br)
  (<:as-html "Address: ") (<:text :name "Address") (<:br)
  (<:as-html "Phone: ") (<:text :name "Phone") (<:br)
  (<:p) (render (make-instance 'products-dropdown))
  (<:p))
(defmethod render :after ((form form-component))
  (<:submit :value "Place Order"))

Note that CALL-NEXT-METHOD is required in the :around method, or it "will completely hijack the implementation of the generic function from all the methods except for more-specific :around methods." (PCL)

We didn't actually use the extended "wrapping" methods provided by arnesi this time, but I can picture a few scenarios where I would, such as using the :wrap-around method for wrapping a <table>.

How to remove a specialized RENDER method

There will be a time in your CLOS programming days where you will want to remove a method from a generic function. You can easily do this by using the Slime Inspector (thank you adeht).

For example, if we defined a RENDER method for any UCW component and wanted to get rid of it, all you need to do is start the inspecter (C-c I or M-x slime-inspect RET) and then type in, literally: (defgeneric render (component)) RET. Alternatively, you could use M-. on any method and you should see the DEFGENERIC form in the first line. At that point, once you call slime-inspect all you have to do is RET since the minibuffer will have the value.

Once you're in the *Slime Inspector* buffer, it is pretty clear what to do. Just place the cursor over the [remove method] link next to your component name, and hit RET.

Wrapping it up

So there you have it. We've started getting into real Uncommon Web application territory, as components are a basis for many of UCW's features.

[C]omponents play an important role when using UCW's advanced control flow features, and it is useful to abstract the RENDERing to a single method.

[...]

It must be said that components can do a lot more than encapsulate the display code. Components can call other components, which can answer with real lisp values. Components are also conveinent places to store data related to the application that one might traditionally keep in a 'session' variable.

If you want to compare or run today's final sample code, you can grab it at:
http://github.com/felideon/ucw-sample-code/blob/master/orders.lisp

To run it, remember to (require :ucw), (in-package :ucw) at the REPL, and then C-c C-k in the file to compile it. Call (startup-orders) in the REPL and then you should be able to browse to http://localhost:8080/orders/index.ucw to see the form.

I do apologize for the hiatus between posts, but between job hunting and the holidays I really hadn't had a chance to sit down and play with UnCommon Web much, much less write a blog post. You should follow me on twitter here as I often post updates of upcoming blog posts and tid bits regarding UCW.

References:
(PCL) Peter Seibel, Practical Common Lisp, Ch. 16
(where citation missing) Drew Crampsie, gettingstarted.txt

Permalink | Leave a comment  »

Via @robotickilldozr.

Last month, I posted some code for rendering text under CL-OpenGL with ZPB-TTF. Toward the very end of that post, I said:

Technically, that check with the squared distance from the calculated midpoint to the segment midpoint shouldn't just compare against the number one. It should be dynamic based on the current OpenGL transformation. I should project the origin and the points and through the current OpenGL projections, then use the reciprocal of the maximum distance those projected points are from the projected origin in place of the one. Right now, I am probably rendering many vertexes inside each screen pixel.

It was pretty obvious that when you tried to render something very small, it looked quite jaggy and much more solid than you would expect.

Here is the new code:

• draw: better anti-aliasing
• gl: smaller ‘frames-per-second’ indicator and some parameters to make it easier to toggle the main display
• test: small tweak to make it work better under SLIME

Using a better cutoff value

The squared distance check that I mentioned now employs a cutoff value:

I have tweaked the (render-string …) and (render-glyph …) accordingly to propagate that value down to the interpolate function, and I have added a method to calculate the appropriate cutoff value.

Calculating the appropriate cutoff value

The appropriate cutoff value depends upon the font, the desired rendering size in viewport coordinates, and the current OpenGL transformations. The basic idea is that I prepare the OpenGL transformation the same way that I will later do for rendering the font; I will reverse-project , , and ; I will calculate the distances from the reverse-projected to each of the other two reverse-projected points; and then I will take half of that as my cutoff value. This effectively means that once the midpoint of my parabola arc is within half of a screen pixel of where the midpoint of a line segment would be, I just use a line segment.

David McClain has been looking for a (portable) way to assign a total order to all Lisp objects, regardless of type... [which] need not be consistent from one Lisp session to the next, but within one session the order should be consistent and unambiguous.

You can follow his discoveries here. Or you can skip to (what's currently) the end of the line and check over his code: self-contained ... pure portable CL.

Paul Kreuger has written 70 pages of tutorial material about Cocoa and Lisp with ClozureCL. Thanks!

How would you describe your relationship with Common Lisp's logical pathname facility?

1. I use logical pathnames and they make my life easier. Here's how...
   
2. I used logical pathnames and they made my life miserable. Here's how...
   
3. I never tried logical pathnames. Here's why...
   

Please comment on my blog with your response, or send me an email, and I'll summarize the responses later. (If you don't use logical pathnames because you don't use Common Lisp, no need to respond.)

(Personally I'm in camp 3, because pathnames seem complicated and logical pathnames were lumped in with them in my mind. And I didn't really understand what problem they were solving. But now that I've read about them and how they can be used, I think I'll start using them and be in camp 1.)

I was lurking on the #lisp irc channel on freenode yesterday, and the matter of how Clozure CL implements closures came up in passing. If you use M-. to see the source of init-nclosure, you’ll see a fairly impenatrable fragment of assembly code. I thought I would try to explain it, at least for the x86 ports.

To understand how closures are implemented, it is necessary to know how functions are implemented.

A memory allocated object that isn’t a cons cell is a thing called a uvector. A uvector consists of a header word and a number of data words.

Functions are uvectors, but they are a little bit funky. Let’s look at an example.

We’re going to run the lisp under gdb so that we can examine how this function is represented in memory:

$ gdb dx86cl64
[set up how gdb deals with signals, define some utility commands]
(gdb) source /usr/local/src/ccl/lisp-kernel/darwinx8664/.gdbinit
(gdb) run
Starting program: /usr/local/src/ccl/dx86cl64
Reading symbols for shared libraries +. done
Welcome to Clozure Common Lisp Version 1.5-dev-r13385  (DarwinX8664)!
? (defun 2-to-the (x)
    (expt 2 x))
2-TO-THE
? #'2-to-the
[find out the address of the function]
#<Compiled-function 2-TO-THE #x302000A53B8F>
[now we hit C-c]
? ^C
Program received signal SIGINT, Interrupt.
0x00007fff813569ee in __semwait_signal ()
1: x/i $pc  0x7fff813569ee <__semwait_signal+10>: jae 0x7fff813569f5 <__semwait_signal+17>

We want to see the function in memory. To avoid talking about tagging, we just observe that memory-allocated objects are always dnode (two machine words) aligned. Thus we just mask off the low 4 bits.

(gdb) x/14g 0x302000A53B80
0x302000a53b80:	0x0000000000000d95	0x4c00000000000009

That first word is the header word. Note the #x95 in the low 8 bits. That’s the subtag. In this case, it’s x8664::subtag-function. The upper 56 bits are the element count. In this case, the function contains 13 (#xd) 64-bit words.

I said earlier that functions were kind of funky. The first byte of executable code is, of course, the #x4c at address #x302000A53B8F, which is the tagged address of the function object. There are 7 bytes between the start of the first uvector element and the start of the machine code. We store the number of words of code and other immediate data in the lower 32 bits of the first word. (This enables the GC to know what part of the uvector that it shouldn’t scan.)

In our example, we see that the function contains 9 words of code and other immediate data. We’ll skip over them.

0x302000a53b90:	0xf983fffffff92d8d	0x56e5894855257508
0x302000a53ba0:	0x4800000010c7c748	0x00000010b9f8758b
0x302000a53bb0:	0xc9000000419d8b49	0x00000007900a63ff
0x302000a53bc0:	0x906690666600c2cd	0x00000000000000f2

The #xf2 in the last word is an internal marker called x8664::function-boundary-marker. It too is used by the GC.

The rest of the data is the function’s gc-able “constants”.

0x302000a53bd0:	0x000030004001364e	0x0000302000a53c63
0x302000a53be0:	0x0000302000a577ee	0x0000000004000800

We can use a custom gdb command to look at them.

[pl stands for "print lisp"]
(gdb) pl 0x000030004001364e
$1 = 0x38e00 "EXPT"

The symbol EXPT.

(gdb) pl 0x0000302000a53c63
$2 = 0x38e00 "(PC-SOURCE-MAP #<4-element vector subtag = #xE7 @#x0000302000A53C2D ((UNSIGNED-BYTE 8))> ...

A list of function metadata.

(gdb) pl 0x0000302000a577ee
$3 = 0x38e00 "2-TO-THE"

The function’s name.

The last word is a fixnum, and it is the function’s “lfun-bits”. The bit $lfbits-trampoline-bit will be set if the function is a closure trampoline. There are many more $lfbits-xxx things.

There are some internal functions that we can use to look at a function’s constants and lfun bits from lisp. %NTH-IMMEDIATE will show a function’s contants, indexed from 0.

? (%nth-immediate #'2-to-the 0)
EXPT
? (%nth-immediate #'2-to-the 1)
(FUNCTION-SYMBOL-MAP (#(X) . #(63 17 44)))
? (%nth-immediate #'2-to-the 2)
2-TO-THE

One last thing to know about functions: the last three arguments to the function are passed in the registers arg_x, arg_y, and arg_z. (On x8632, we only have arg_y and arg_z). So, a function with only one argument will receive that argument in arg_z. If there are more arguments than arg registers, the arguments are passed on the stack.

OK, so that’s how functions work. If anyone is still reading, let’s look at closures now.

? (let ((n 0))
    (defun next-val ()
      (incf n))
    (defun set-val (x)
      (setq n x)))
? #'next-val
#<COMPILED-LEXICAL-CLOSURE NEXT-VAL #x302000EEA42F>

So, that’s different. Before we saw output like:

#<Compiled-function 2-TO-THE #x302000A53B8F>

Let’s look at that function’s constants:

? (%nth-immediate #'next-val 0)
#<Compiled-function NEXT-VAL (Non-Global)  #x302000EECCFF>

What’s this? The function next-val is actually a little trampoline function that sets up and calls the actual closure function.

DISASSEMBLE tries to be friendly and shows you the disassembly of the closure function rather than the trampoline, but we can directly call an internal function to see the trampoline itself:

? (x86-xdisassemble #'next-val)
L0
[0]     (leaq (@ (:^ L0) (% rip)) (% fn))
[7]     (jmpq (@ .SPCALL-CLOSURE))

Finally, we can start to see what init-nclosure does. The code fragment that is init-nclosure generates (at run-time) the little bit of code shown above. The closed-over values are found in the trampoline function’s constants.

? (%nth-immediate #'next-val 1)
#<VALUE-CELL 0 #x302000EEA46D>

And I mentioned that $lfbits-trampoline-bit would be on in the function’s lfun-bits:

? (logbitp $lfbits-trampoline-bit (%nth-immediate #'next-val 2))
T

When the trampoline is actually called, it jumps to the .SPcall-closure subprimitive in the lisp kernel (see ccl:lisp-kernel;x86-spentry64.s), which prepends the constants in the trampoline representing the closed-over values to the closure function’s arglist, and calls it.

A closure function thus sees any closed-over values as regular arguments.

? (disassemble #'next-val)
L0
[0]     (leaq (@ (:^ L0) (% rip)) (% fn))
[7]     (cmpl ($ 8) (% nargs))
[10]    (jne L93)
[...]

%nargs is the register that contains the (fixnum) count of arguments passed to the function. If it’s not fixnum 1, then error. Note that next-val’s lambda list is nil—the argument it is expecting is the closed over value of n.

Anyway, sorry to pontificate at such length about a topic of limited interest, but there it is.

[updated to correct an error explaining tagging]

I created a site with 5,121 of Erik Naggum's comp.lang.lisp articles. I hope you find it useful.

The notes include a bit about how I used bit-vectors for really fast search.

I shouldn’t complain, really: I have a decent and stable job, which is mostly fun; I have a certain amount of freedom in what I do, as long as everything that has to get done gets done; I work with all sorts of interesting people, both formally and informally. But things that I want to do have to live a long way down the priority queue; preparing lecture materials, paper drafts, committee agendas, bursary agreements, course proposals, courseworks, exams, student feedback, paper redrafts, reports, meeting notes, grant proposal drafts, paper reviews, examiners’ reports, reading lists, grant proposal redrafts, and the like all seem to take priority over even the research on a funded project that I am part of, let alone the discretionary research that I might actually want to do.

So sometimes I have to be sneaky, and combine my hacking with teaching-related work instead. One of the more fun things I’ve learnt over the last couple of years is enough colour theory to be dangerous; it started off because I was casting around for ideas on what to teach students on our Creative Computing programme – and I do teach them about colour, among other things – but it’s sufficiently interesting as a technical area in itself that I can see writing code to illustrate aspects of it. So, here’s a (not very good) colour picker “application” for McCLIM, whose only redeeming feature is that it uses knowledge of the colour attributes of consumer-grade display hardware to present colours of the same intensity together. That’s a bit hard to visualize, so here’s a screenshot, where all the colours in the triangle should seem to have about the same brightness (viewers might need to adjust their viewing angle):

Source code is here; I’m not particularly proud of it, and it needs work in all sorts of directions (optimizing, generalizing, cleaning up). One of the reasons I had put off blogging about this is that I was hoping for a lovely literate-programming system to optimized for single-file Lisp programs to appear, generating HTML and PDF output from minimally-marked-up Lisp code. Sadly, that hasn't happened, and my best attempt can only be described as, well, deranged... so no impeccably formatted and indexed code snippets in this blog, not this time anyway.