PAX PDF Output

Tags: tech, lisp,  Date: 2025-05-15

Thanks to Paul A. Patience, PAX now has PDF support. See pax-manual-v0.4.1.pdf and dref-manual-v0.4.1.pdf. The PDF is very similar to the HTML, even down to the locative types (e.g [function]) being linked to the sources on GitHub, but cross-linking between PDFs doesn't work reliably on most viewers, so that's disabled. Also, for reading PDFs so heavy on internal linking to be enjoyable, one needs a viewer that supports going back within the PDF (not the case with Chrome at the moment). Here is a blurry screenshot to entice:

There is a bit of a Christmas tree effect due to syntax highlighting and the colouring of the links. Blue links are internal to the PDF, maroon links are external. I might want to change that to make it look more like the HTML, but I have not found a way on LaTeX to underline text without breaking automatic hyphenation.

Adaptive Hashing

Tags: tech, lisp,  Date: 2025-05-02

At the 2024 ELS, I gave a talk on adaptive hashing, which focusses on making general purpose hash tables faster and more robust at the same time.

Theory vs Practice

Hash table theory most concerns itself with the asymptotic worst-case cost with a hash function chosen randomly from a family of hash functions. Although these results are very relevant in practice,

• those pesky constant factors, that the big-O cost ignores, do matter, and

• we don't pick hash functions randomly but fix the hash function for the lifetime of the hash table.

There are Perfect Hashing algorithms, that choose an optimal hash function for a given set of keys. The drawback is that they either require the set of keys to be fixed or they are too slow to be used as general purpose hash tables.

Still, the idea that we can do better by adapting the hash function to the actual keys is key. Can we do that online, that is, while the hash table is being used? Potential performance gains come from improving the constant factors mentioned above by

• having fewer collisions, and

  

• being more cache-friendly.

  

The first image above plots the regret (the expected number of comparisons of per lookup minus the minimum achievable) and the measured run-time of PUT operations vs the number of keys in the hash table with a particular key distribution. Green is Murmur (a robust hash function), Blue is SBCL's expedient EQ hash. The wiggling of the graphs is due to the resizing of the hash table as keys are added to it.

Note how SBCL's regret starts out much lower and becomes much higher than that of Murmur, but if anything, its advantage in run time (second image) grows.

Implementation

The general idea is sound, but turning it into real performance gains is hard due to the cost of choosing a hash function and switching to it. First, we have to make some assumption about the distribution of keys. In fact, default hash functions in language runtimes often make such assumptions to make the common cases faster, usually at the cost of weakened worst-case guarantees.

The rest of this post is about how SBCL's built-in hash tables, which had been reasonably fast, were modified. The core switching mechanism looks at

• the length of the collision chain on PUT operations,

• the collision count on rehash (when the hash table is grown), and

• the size of the hash table.

Adapting EQ hash tables

1. Init to to constant hash function. This a fancy way of saying that we do linear search in a vector internally. This is an EQ hash table, so key comparison is as single assembly instruction.

2. When the hash table is grown to more than 32 keys and it must be rehashed anyway, we switch to a hash function that does a single right shift with the number of bits to shift determined from the longest common run of low-bits in the keys.

3. If too many collisions, we switch to the previous default SBCL EQ-hash function that has been tuned for a long time.

4. If too many collisions, we switch to Murmur, a general purpose hash. We could also go all the way to cryptographic hashes.

In step 2, the hash function with the single shift fits the memory allocator's behaviour nicely: it is a perfect hash for keys forming arithmetic sequences, which is often approximately true for objects of the same type allocated in a loop.

In this figure, the red line is the adaptive hash.

Adapting EQUAL hash tables

For composite keys, running the hash function is the main cost. Adaptive hashing does the following.

• For string keys, hash only the first and last 2 characters.

• For list keys, only hash the first 4 elements.

• If too many collisions, double the limit.

So, SBCL hash tables have been adaptive for almost a year now, gaining some speed in common cases, and robustness in others.

The full paper is here.

PAX and DRef v0.4

Tags: tech, lisp,  Date: 2025-04-23

Version 0.4 of PAX, the documentation system, and DRef, the definition reifier, was released. There were large refactorings, bug fixes, minor features, cosmetics, documentation and performance improvements too numerous to list. Here is a summary of the new features and notable changes.

• DRef now supports DTYPEs, which allow filtering DEFINITIONS and DREF-APROPOS results according to the locative type hierarchy:

  (definitions 'print)
  ==> (#<DREF PRINT FUNCTION>
  -->  #<DREF PRINT (UNKNOWN (:DEFOPTIMIZER PRINT SB-C:DERIVE-TYPE))>
  -->  #<DREF PRINT (UNKNOWN
  -->                (DECLAIM PRINT
  -->                         SB-C:DEFKNOWN))>)

  (definitions 'print :dtype '(and t (not unknown)))
  ==> (#<DREF PRINT FUNCTION>)

  The AND T bit restricts the query to definitions in the running Lisp. The top of the DTYPE hierarchy is DREF:TOP, which includes external definitions such as the CLHS, that comes with PAX:

  (definitions 'print :dtype '(not unknown))
  ==> (#<DREF PRINT (CLHS FUNCTION)> #<DREF PRINT FUNCTION>)

  (dref-apropos "method" :package :dref :external-only t :dtype 'class)
  ==> (#<DREF METHOD CLASS> #<DREF METHOD-COMBINATION CLASS>)

  The locative type hierarchy can be queried programmatically, and this information is included in their documentation (see for example the GENERIC-FUNCTION locative type).

• The PAX Live Home Page better supports exploration without having to leave the browser. See the video.

  • It lists packages grouped by ASDF systems that define them (when this can be determined from the source locations).

  • It links to apropos pages for each locative type.

  • It has an input box for looking up documentation right from the browser (as if with mgl-pax-document from Emacs).

  • It has an input box for looking up apropos right from the browser (as if with mgl-pax-apropos from Emacs).

  • The web server can be started without Emacs.

• Completion of names and locatives in Emacs is much improved.

• New aliases were added to the CLHS pages documenting format directives (e.g. ~F), standard macro characters (#A) and loop keywords (sum, :sum, loop:sum), so that one can just C-. (mgl-pax-document) them. See the documentation of the CLHS locative.

• The DRef extension api has been cleaned up.

On Multifaceted Development and the Role of Documentation

Tags: tech, lisp, pompousness,  Date: 2023-08-17

Catchy title, innit? I came up with it while trying to name the development style PAX enables. The original idea was something vaguely self-explanatory in a straight out of a marketing department kind of way, with tendrils right into your unconscious. Documentation-driven development sounded just the thing, but it's already taken. Luckily, I came to realize that neither documentation nor any other single thing should drive development. Less luckily for the philosophically disinclined, this epiphany unleashed my inner Richard P. Gabriel. I reckon if there is a point to what follows, it's abstract enough to make it hard to tell.

... read the rest of On Multifaceted Development and the Role of Documentation.

Try in Emacs

Tags: tech, lisp,  Date: 2023-08-14

Try, my test anti-framework, has just got light Emacs integration.

... read the rest of Try in Emacs.

DRef and PAX v0.3

Tags: tech, lisp,  Date: 2023-07-26

DEFSECTION needs to refer to definitions that do not create a first-class object (e.g. stuff like (*DOCUMENT-LINK-TO-HYPERSPEC* VARIABLE)), and since its original release in 2014, a substantial part of PAX dealt with locatives and references, which reify definitions. This release finally factors that code out into a library called DRef, allowing PAX to focus on documentation. Being very young, DRef lives under adult supervision, in a subdirectory of the PAX repository.

... read the rest of DRef and PAX v0.3.

PAX Live Documentation Browser

Tags: tech, lisp,  Date: 2023-06-10

PAX got a live documentation browser to make documentation generation a more interactive experience. A great thing about Lisp development is changing a single function and quickly seeing how it behaves without the delay of a full recompile. Previously, editing a docstring required regenerating the full documentation to see how the changes turned out. The live documentation browser does away with this step, which tightens the edit/document loop.

PAX also got an apropos browser. It could always generate documentation for stuff not written with PAX in mind, so with the live browser already implemented, this was a just a small add-on.

The trouble with interactivity is, of course, that it's difficult to get the point across in text, so I made two short videos that demonstrate the basics.

• Live browsing with w3m

• Live browsing with other browsers

There is Try

Tags: lisp,  Date: 2022-10-16

Do or do not. There is now Try. I forgot to announce Try, my Common Lisp test framework, on this blog.

• Try does equally well in interactive and non-interactive mode by minimizing the function-test impedance mismatch.

• It provides a single, extensible check macro. All other checks are built on top of it.

• It is highly customizable: what to debug interactively, what to print, what to describe in detail, what to rerun, what to count can all be easily changed.

• Customization is based on complex types built from event types, which are signalled when checks or tests are run.

... read the rest of There is Try.

PAX v0.1

Tags: tech, lisp,  Date: 2022-02-16

PAX v0.1 is released. At this point, I consider it fairly complete. Here is the changelog for the last year or so.

New Features

• To reduce deployment size, made the MGL-PAX system autoload navigation, documentation generation, and transcription code.

• Symbols in the CL package are linked to the hyperspec like this: PRINT, which renders as PRINT.

• Hyperspec sections and issues can be linked to with the CLHS locative like this: [lambda lists][CLHS], which renders as lambda lists.

• Added support for [see this][foo function] and [see this][foo] style of linking.

• Added DECLARATION locative.

... read the rest of PAX v0.1.

Journal, the Kitchen Sink

Tags: lisp,  Date: 2020-09-04

Ever wished for machine-readable logs and TRACEs, maybe for writing tests or something more fancy? The Journal library takes a simple idea: user-defined execution traces and implements logging, tracing, a testing "framework" with mock support, and an Event Sourcing style database on top.

... read the rest of Journal, the Kitchen Sink.

Moving the Blog to PAX

Tags: lisp,  Date: 2020-05-05

After more than five years of silence, I may be resurrecting my old blog. I already got as far as rewriting it using MGL-PAX, which is a curious choice because PAX is a documentation generator for Common Lisp. The blog "engine" is rather bare-bones but works admirably, especially considering that the implementation is only 72 lines of code, most of which deals with post categories and overview pages with shortened posts, something PAX hasn't seen the need for.

On the Design of Matrix Libraries

Tags: ai, lisp,  Date: 2015-02-26

2020-05-03 – Things have changed the during last 5 years. This is a non-issue in Tensorflow and possibly in other frameworks, as well.

I believe there is one design decision in MGL-MAT that has far reaching consequences: to make a single matrix object capable of storing multiple representations of the same data and let operations decide which representation to use based on what's the most convenient or efficient, without having to even know about all the possible representations.

... read the rest of On the Design of Matrix Libraries.

Bigger and Badder PAX World

Tags: lisp,  Date: 2015-02-20

Bigger because documentation for named-readtables and micmac has been added. Badder because clicking on a name will produce a permalink such as this: *DOCUMENT-MARK-UP-SIGNATURES*. Clicking on locative types such as [variable] on the page that has just been linked to will take you to the file and line on github where *DOCUMENT-MARK-UP-SIGNATURES* is defined.

PAX World

Tags: lisp,  Date: 2015-01-26

A promise of PAX has always been that it will be easy to generate documentation for different libraries without requiring extensive markup and relying on stable URLs. For example, without PAX, if a docstring in the MGL library referenced the matrix class MGL-MAT:MAT from the MGL-MAT library, it would need to include ugly HTML links in the markdown:

"Returns a [some-terrible-github-link-to-html][MAT] object."

... read the rest of PAX World.

Recurrent Nets

Tags: ai, lisp,  Date: 2015-01-19

I've been cleaning up and documenting MGL for quite some time now, and while it's nowhere near done, a good portion of the code has been overhauled in the process. There are new additions such as the Adam optimizer and Recurrent Neural Nets. My efforts were mainly only the backprop stuff and I think the definition of feed-forward:

... read the rest of Recurrent Nets.

... see older posts