PAX v0.1

Tags: Lisp, Blog

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

Journal, the kitchen sink

Tags: Lisp, Blog

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.

Perhaps the highlight from the linked tutorials is how easy persistence is. Let's write a simple game:

(defun play-guess-my-number ()
  (let ((my-number (random 10)))
    (format t "~%I thought of a number.~%")
    (loop for i upfrom 0 do
      (write-line "Guess my number:")
      (let ((guess (values (parse-integer (read-line)))))
        (format t "You guessed ~D.~%" guess)
        (when (= guess my-number)
          (format t "You guessed it in ~D tries!" (1+ i))

That came out pretty ugly, didn't it? Now, suppose we want to turn this into a browser game so:

So these are the requirements apart from adding the webby stuff, which I'm not going to bore you with. To implement them, we wrap REPLAYED around external interactions, RANDOM and READ-LINE:

(defun play-guess-my-number ()
  (let ((my-number (replayed (think-of-a-number) ; <- HERE
                     (random 10))))
    (format t "~%I thought of a number.~%")
    (loop for i upfrom 0 do
      (write-line "Guess my number:")
      (let ((guess (replayed (read-guess)        ; <- HERE
                     (values (parse-integer (read-line))))))
        (format t "You guessed ~D.~%" guess)
        (when (= guess my-number)
          (format t "You guessed it in ~D tries!" (1+ i))

Now, we need to say where to store the event journal:

(with-bundle ((make-file-bundle "/tmp/guess-my-number/" :sync t))

This is invoked from the web server's worker and it replays the game until it was interrupted last time around. Then it will block waiting for user input in READ-LINE or, if the game is finished, return.

Note the :SYNC T, which tells Journal to take durability seriously.

You can find the code here.

Moving the blog to PAX

Tags: Lisp, Tech, Blog

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, Blog

UPDATE 2020-05-03 -- Things have been moving fast. This is a non-issue in Tensorflow and possibly in other frameworks, as well.

2015-02-26 -- 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.

This allows existing code to keep functioning if support for diagonal matrices (represented as a 1d array) lands and one can pick and choose the operations performance critical enough to implement with diagonals.

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

Bigger and Badder PAX World

Tags: Lisp, Blog

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, Blog

2015-01-26 -- The promise of MGL-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 wanted to reference 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."

With PAX however, the uppercase symbol MAT will be automatically linked to the documentation of MAT if its whereabouts are known at documentation generation time, so the above becomes:

"Returns a MAT object."

The easiest way to tell PAX where to link is to let it generate the documentation for all libraries at the same time like this:

(document (list mgl-mat:@mat-manual mgl:@mgl-manual))

This is the gist of what MGL-PAX-WORLD does. It has a list of stuff to document, and it creates a set of HTML files. Check out how its output looks on github pages. Here is a good example of cross-links. It's easy to play with locally: just get the gh-pages branch and call UPDATE-PAX-WORLD.

Recurrent Nets

Tags: AI, Lisp, Blog

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:

(build-fnn (:class 'digit-fnn)
  (input (->input :size *n-inputs*))
  (hidden-activation (->activation input :size n-hiddens))
  (hidden (->relu hidden-activation))
  (output-activation (->activation hidden :size *n-outputs*))
  (output (->softmax-xe-loss :x output-activation)))

and recurrent nets:

(build-rnn ()
  (build-fnn (:class 'sum-sign-fnn)
    (input (->input :size 1))
    (h (->lstm input :size n-hiddens))
    (prediction (->softmax-xe-loss
                 (->activation h :name 'prediction :size *n-outputs*)))))

is fairly straight-forward already. There is still much code that needs to accompany such a network definition, mostly having to do with how to give inputs and prediction targets to the network and also with monitoring training. See the full examples for feed-forward and recurrent nets in the documentation.

INCLUDE locative for PAX

Tags: Lisp, Blog

2014-12-06 -- I'm getting so used to the M-. plus documentation generation hack that's MGL-PAX, that I use it for all new code, which highlighted an issue of with code examples.

The problem is that, the ideally runnable, examples had to live in docstrings. Small code examples presented as verifiable Transcripts within docstrings were great, but developing anything beyond a couple of forms of code in docstrings or copy-pasting them from source files to docstrings is insanity or an OOAO violation, respectively.

In response to this, PAX got the INCLUDE locative (see the linked documentation) and became its own first user at the same time. In a nutshell, the INCLUDE locative can refer to non-lisp files and sections of lisp source files which makes it easy to add code examples and external stuff to the documentation without duplication. As always, M-. works as well.


Tags: Lisp, Blog

2014-10-20 -- I've just committed a major feature to MGL-PAX: the ability to include code examples in docstrings. Printed output and return values are marked up with ".." and "=>", respectively.

(values (princ :hello) (list 1 2))
=> (1 2)

The extras are:

The documentation provides a tutorialish treatment. I hope you'll find it useful.

Migration to github

Tags: Lisp, Blog

2014-09-25 -- Due to the bash security hole that keeps giving, I had to disable gitweb at and move all non-obsolete code over to github. This affects:

Higgs Boson Machine Learning Challenge Bits and Pieces

Tags: AI, Lisp, Blog

2014-09-23 -- The Higgs Boson contest on Kaggle has ended. Sticking to my word at ELS 2014, I released some code that came about during these long four months.

MGL-GPR is no longer a Genetic Programming only library because it got another Evolutionary Algorithm implementation: Differential Evolution. My original plan for this contest was to breed input features that the physicists in their insistence on comprehensibility overlooked, but it didn't work as well as I had hoped for reasons specific to this contest and also because evolutionary algorithms just do not scale to larger problem sizes.

In other news, MGL got (, bagging and stratification support in the brand new MGL-RESAMPLE package documented with MGL-PAX which all of you will most definitely want to use. My winning submission used bagged cross-validated dropout neural networks with stratified splits so this is where it's coming from.

MGL itself and MGL-MAT were updated to work with the latest CL-CUDA. The neural network code also saw some additions such as ->MAX-CHANNEL activation (which originated as LWTA) and also gaussian multiplicative noise. The next steps here are further cleanups to MGL, writing documentation and moving it to github. Also, there is some hope that one day CL-CUDA can be included in quicklisp allowing my stuff there to be updated to their latest versions.

The code for this contest is available at ( from now on doubles as my skeleton for lisp projects that need to be delivered as source and as binary. It sucks in all dependencies from quicklisp available at a certain date, clones the necessary repositories not available in quicklisp, builds an executable, and has a simple 'make dist' rule as well.

There is also a fairly generic ensembling algorithm that I will factor out of the code later.

Higgs Boson Machine Learning Challenge Post-Mortem

Tags: AI, Lisp, Blog

2014-09-23 -- Actually, I'll only link to the post-mortem I wrote in the forum. There is a also a model description included in the git repo. A stand-alone distribution with all library dependencies and an x86-64 linux precompiled binary is also available.

This has been the Kaggle competition that attracted the most contestants so it feels really good to come out on top even though there was an element of luck involved due to the choice of evaluation metric and the amount of data available. The organizers did a great job explaining the physics, why there is no more data, motivating the choice of evaluation metric, and being prompt in communication in general.

I hope that the HEP guys will find this useful in their search for more evidence of tau tau decay of the Higgs boson. Note that I didn't go for the 'HEP meets ML Award' so training time is unnecessarily high (one day with a GTX Titan GPU). By switching to single precision floating point and a single neural network, training time could be reduced to about 15 minutes with an expected drop in accuracy from 3.805 to about 3.750. Even with the bagging approach the code logs out-of-bag estimates of the evaluation metric after training each constituent model and the training process can be C-c'ed early. Furthermore, the model can be run on a CPU with BLAS about 10 times slower than on a Titan.

Liblinear Support Added to cl-libsvm

Tags: AI, Lisp, Blog

2013-04-09 -- In addition to the cl-libsvm asdf system, there is now another asdf system in the cl-libsvm library: cl-liblinear that, predictably enough, is a wrapper for liblinear. The API is similar to that of cl-libsvm.

Stackoverflow Post-Mortem

Tags: AI, Lisp, Blog

2013-04-09 -- After almost two years without a single competition, last September I decided to enter the Stackoverflow contest on Kaggle. It was a straightforward text classification problem with extremely unbalanced classes.

Just as Bocsimackó did the last time around, his lazier sidekick Malacka (on the right) brought success. I would have loved to be lazy and still win, but the leaderboard was too close for comfort.

... read the rest of Stackoverflow Post-Mortem.

Dirty 36Cube

Tags: Personal, Blog

2012-08-19 -- This is a short rant on what I consider to be a good puzzle and why the trick 36Cube pulls is rather dirty.

WARNING, spoilers ahead.

... read the rest of Dirty 36Cube.

Hung Connections

Tags: Tech, Blog

2011-02-27 -- My ISP replaced a Thomson modem with a Cisco EPC3925 modem-router to fix the speed issue I was having. The good news is that the connection operates near its advertised bandwidth, the bad news is that tcp connections started to hang. It didn't take long to find out that this particular router drops "unused" tcp connections after five minutes.

The fix recommended in the linked topic (namely sysctl'ing net.ipv4.tcp_keepalive_time & co) was mostly effective but I had to lower the keepalive to one minute to keep my ssh sessions alive. The trouble was that OfflineIMAP connections to the U.S. west coast still hanged intermittently while it could work with Gmail just fine.

In the end, OfflineIMAP had to be patched to use the keepalive and the keepalive be lowered to 15s:

sysctl -w net.ipv4.tcp_keepalive_time=15 \
          net.ipv4.tcp_keepalive_intvl=15 \

Oh, and always include socktimeout in the offlineimap config, that's more important than keepalive unless you never have network issues.

OfflineIMAP with Encrypted Authinfo

Tags: Tech, Blog

2011-02-26 -- I've moved to an OfflineIMAP + Gnus setup that's outlined at various places. Gnus can be configured to use ~/.authinfo as a netrc style of file to read passwords from and can easily use encrypted authinfo files as well. Offlineimap, on the other hand, offers no such support and passwords to the local and remote imap accounts are normally stored in clear text in .offlineimaprc.

For the local account this can be overcome by not running a dovecot server but making offlineimap spawn a dovecot process when needed:

[Repository LocalGmail]
type = IMAP
preauthtunnel = /usr/sbin/dovecot -c ~/.dovecot.conf --exec-mail imap

For the remote connection, ideally it should read the password from .authinfo.gpg that Gnus may also read if it's configured to access the remote server directly. This can be pulled off rather easily. Add an /include/ to .offlineimaprc like this:

pythonfile = ~/

where ~/ just defines a single function called get_authinfo_password:

import re, os

def get_authinfo_password(machine, login, port):
    s = "machine %s login %s password ([^ ]*) port %s" % (machine, login, port)
    p = re.compile(s)
    authinfo = os.popen("gpg -q --no-tty -d ~/.authinfo.gpg").read()

Now, all that's left is to change remotepass to something like this:

remotepasseval = get_authinfo_password("", "", 993)

Of course, .authinfo.gpg should also have the corresponding entry:

machine login password <password> port 993

That's it, no more cleartext passwords.


Tags: AI, Lisp, Blog

2010-12-27 -- It hasn't been a year yet since I first promised that alpha-beta snippet and it is already added to micmac in all its 35 line glory. The good thing about not rushing it out the door is that it saw more a bit more use. For a tutorialish tic-tac-toe example see test/test-game-theory.lisp.

The logging code in the example produces output, which is suitable for cut and pasting into an org-mode buffer and exploring it by TABbing into subtrees to answer the perpetual 'What the hell was it thinking?!' question.

Nash equilibrium finder

Tags: AI, Lisp, Blog

2010-12-26 -- While I seem to be unable to make my mind up on a good interface to alpha-beta with a few bells and whistles, I added a Nash equilibrium finder to Micmac that's becoming less statistics oriented. This was one of the many things in Planet Wars that never really made it.

Let's consider the Matching pennies game. The row player wins iff the two pennies show the same side. The payoff matrix is:

|       | Heads | Tails |
| Heads |     1 |    -1 |
| Tails |    -1 |     1 |

Find the mixed strategy equilibrium:

(find-nash-equilibrium '((-1 1) (1 -1)))
#(49 51)
#(50 50)

That is both players should choose heads 50% of the time and the expected payoff (for the row player) is zero of which -0.01 is an approximation:

(find-nash-equilibrium '((-1 1) (1 -1)) :n-iterations 1000)
#(499 501)
#(500 500)

Planet Wars Post-Mortem

Tags: AI, Lisp, Blog

2010-12-01 -- I can't believe I won.

I can't believe I won decisively at all.

The lead in the last month or so was an indicator of having good chances, but there was a huge shuffling of ranks in the last week and some last minute casualties.


Note that the git repository is available at (gitweb).


I had promised myself not to enter this one and resisted for about two weeks when my defenses were worn away and I was drawn into the fray.

The game didn't look very exciting at first. I thought that the bots would soon reach a point of near perfect tactics and the rock-paper-scissors scenarios would dominate (more on this later).

That's enough of tribute, let's steer off the trodden path.

... read the rest of Planet Wars Post-Mortem.

Important Update to the Planet Wars Starter Package

Tags: AI, Lisp, Blog

2010-10-25 -- First, is it possible to get something as simple as RESOLVE-BATTLE wrong? Apparently, yes. That's what one gets for trying to port Python code that's pretty foreign in the sense of being far from the way I'd write it.

More importantly, I found out the hard way that sbcl 1.0.11 that's still on the official servers has a number of bugs in its timer implementation making WITH-TIMEOUT unreliable. Also, it can trigger timeouts recursively eventually exceeding the maximum interrupt nesting depth. Well, "found out" is not the right way to put it as we did fix most of these bugs ages ago.

In the new starter package (v0.8 in git, latest tarball), you'll find timer.lisp that's simply backported almost verbatim from sbcl 1.0.41 to sbcl 1.0.11. Seems to work for me, but I also had to lower the timeout to 0.8 from 0.98 because the main server is extremely slow.

The rate at which games are played on the servers is so low that it takes several days to ascend through the leaderboard. Nevertheless, an old buggy version is sitting on the top right now. Mind you, introducing bugs is a great way exlopore the solution space and it's quite worrisome just how adept I am at this poor man's evolutionary programming. Most of them have since been fixed while the ideas they brought to light remain, making the current version much stronger.

Planet Wars Common Lisp Starter Package Actually Works

Tags: AI, Lisp, Blog

2010-09-21 -- Released v0.6 (git, latest tarball). The way the server compiles lisp submissions was fixed and this revealed a problem where MyBot.lisp redirected *STANDARD-OUTPUT* to *ERROR-OUTPUT* causing the server to think compilation failed.

Planet Wars Common Lisp Starter Package

Tags: AI, Lisp, Blog

2010-09-19 -- The Google AI Challange is back with a new game that's supposed to be much harder than Tron was this spring. The branching factor of the game tree is enormous which only means that straight minimax is out of question this time around. Whether some cleverness can bring the game within reach of conventional algorithms remains to be seen.

Anyway, I'm adding yet another starter package (latest tarball) to the lot. It is based heavily on aerique's.

... read the rest of Planet Wars Common Lisp Starter Package.

Google AI Challange 2010 Results

Tags: AI, Lisp, Blog

2010-03-01 -- For what has been a fun ride, the official results are now available. In the end, 11th out of 700 is not too bad and it's the highest ranking non-C++ entry by some margin.

I entered the contest a bit late with a rather specific approach in mind: UCT, an algorithm from the Monte Carlo tree search family. It has been rather successful in Go (and in Hex too, taking the crown from Six). So with UCT in mind, to serve as a baseline I implemented a quick minimax with a simple territory based evaluation function ... that everyone else in the competition seems to have invented independently. Trouble was looming because it was doing too well: with looking ahead only one move (not even considering moves of the opponent) it played a very nice positional game. That was the first sign that constructing a good evaluation function may not be as hard for Tron as it is for Go.

... read the rest of Google AI Challange 2010 Results.

Google AI Challenge 2010

Tags: AI, Lisp, Blog

2010-02-11 -- Tron is a fun little game of boxing out the opponent and avoiding crashing into a wall first. The rules are simple so the barrier to entry into this contest is low. Thanks to aeruiqe who made to Common Lisp starter pack it took as little as a few hours to get a very bare bones algorithm going. It's doing surprisingly well: it is number 23 on the leaderboard at the moment with 43 wins, 2 losses and 9 draws.

Upgrade Woes 2

Tags: Tech, Blog

2010-02-08 -- Debian Squeeze finally got Xorg 7.5 instead of the old and dusty 7.4. The upgrade was as smooth as ever: DPI is off, keyboard repeat for the Caps Lock key does not survive suspend/resume and the trackpoint stopped working. Synaptics click by tapping went away before the upgrade so that doesn't count.

Micmac Initial Release

Tags: AI, Lisp, Blog

2010-02-06 -- From a failed experiment today I salvaged Micmac, a statistical library wannabe, that for now only has Metropolis-Hastings MCMC and Metropolis Coupled MCMC implemented. The code doesn't weigh much but I think it gets the API right. In other news MGL v0.0.6 was released.

Deep Boltzmann Machine on MNIST

Tags: AI, Lisp, Blog

2010-01-18 -- Let me interrupt the flow of the MGL introduction series with a short report on what I learnt playing with Deep Boltzmann Machines. First, lots of thanks to Ruslan Salakhutdinov, then at University of Toronto now at MIT, for making the Matlab source code for the MNIST digit classification problem available.

The linked paper claims a record of 99.05% in classification accuracy on the permutation invariant task (no prior knowledge of geometry). A previous approach trained a DBN in an unsupervised manner and fine tuned it with backpropagation. Now there is one more step: turning the DBN into a DBM (Deep Boltzmann Machine) and tune it further before handing the baton over to backprop. While in a DBN the constituent RBMs are trained one by one, the DBM is trained as a whole which, in theory, allows it to reconcile bottom-up and top-down signals, i.e. what you see and what you think.

... read the rest of Deep Boltzmann Machine on MNIST.

Introduction to MGL (part 3)

Tags: AI, Lisp, Blog

UPDATE: This post out of date with regards to current MGL. Please refer to the documentation instead.

2009-12-29 -- In Introduction to MGL (part 2), we went through a trivial example of a backprop network. I said before that the main focus is on Boltzmann Machines so let's kill the suspense here and now by cutting straight to the heart of the matter.

Cottrell's Science article provides a clear and easy to follow description of the spiral problem that we are going to implement. The executive summary is that we want to train an auto-encoder: a network that reproduces its input as output with a small encoding layer somewhere in between. By forcing the information through the bottleneck of the encoding layer the network should pick up a low dimensional code that represents the input, thus performing dimensionality reduction.

... read the rest of Introduction to MGL (part 3).

Introduction to MGL (part 2)

Tags: AI, Lisp, Blog

UPDATE: This post out of date with regards to current MGL. Please refer to the documentation instead.

2009-12-17 -- After Introduction to MGL (part 1), today we are going to walk through a small example and touch on the main concepts related to learning within this library.

At the top of the food chain is the generic function TRAIN:

(defgeneric train (sampler trainer learner)
  (:documentation "Train LEARNER with TRAINER on the examples from
SAMPLER. Before that TRAINER is initialized for LEARNER with
INITIALIZE-TRAINER. Training continues until SAMPLER is finished."))

... read the rest of Introduction to MGL (part 2).

Introduction to MGL (part 1)

Tags: AI, Lisp, Blog

UPDATE: This post out of date with regards to current MGL. Please refer to the documentation instead.

2009-12-02 -- This is going to be the start of an introduction series on the MGL Common Lisp machine learning library. MGL focuses mainly on Boltzmann Machines (BMs). In fact, the few seemingly unrelated things it currently offers (gradient descent, conjugate gradient, backprop) are directly needed to implement the learning and fine tuning methods for different kinds of BMs. But before venturing too far into specifics, here is a quick glimpse at the bigger picture and the motivations.

... read the rest of Introduction to MGL (part 1).

Ultimate Fallout 2 Ironman Munchkin

Tags: Personal, Blog

2009-11-21 -- I'm cleaning up the accumulated junk and found this guide that was written eons ago.

This build is focused on survival. No save/loading, killap's final patch, hard combat and game difficulty. As it is not only ironman but a munchkin too it must be a sniper since HtH is a bit underpowered.

... read the rest of Ultimate Fallout 2 Ironman Munchkin.

Upgrade Woes

Tags: Tech, Blog

2009-11-06 -- Debian Lenny was released back in February. My conservativeness only lasts about half a year so I decided to upgrade to Squeeze aka Debian testing. The upgrade itself went rather smoothly with a few notable exceptions. With KDE 4.3 I should have waited more.


Object Initialization with Slot Dependencies

Tags: Lisp, Blog

2009-07-04 -- Consider a class with a trivial initialization dependency between slots A and B:))

(defclass super ()
 ((a :initarg :a :reader a)
  (b :initform 0 :initarg :b :reader b)))

(defmethod initialize-instance :after ((super super) &key &allow-other-keys)
 (setf (slot-value super 'a) (1+ (slot-value super 'b))))

(a (make-instance 'super)) => 1
(a (make-instance 'super :b 1)) => 2

You may even subclass it, add an initform and it still works:

(defclass sub (super)
 ((b :initform 1)))

(a (make-instance 'sub)) => 2

... read the rest of Object Initialization with Slot Dependencies.

Global Compiler Policy

Tags: Lisp, Blog

2009-06-30 -- A quick note to library implementors: The effects of DECLAIM are permitted to persist after the containing file is compiled and it is unkind to mutate your user's settings. Personally, I find DECLAIM too blunt and prefer to add declarations within functions, even going as far as introducing LOCALLY subforms just to have a place on which to hang declarations. But if you are really set on using DECLAIM, please wrap it like this:

(eval-when (:compile-toplevel)
 (declaim (optimize speed)))

to ensure that the body is evaluated in the dynamic execution context of the compiler which makes a practical difference on Allegro. It goes without saying that you don't want (PROCLAIM '(OPTIMIZE ...)) in a library, either.

UPDATE: The above works, but is not mandated by the spec because the dynamic execution context of the compiler does not include the global declarations. Alas, by the spec the portable solution is to wrap the whole file in:

(locally (declare (optimize speed)) ...)

Active Learning for cl-libsvm

Tags: AI, Lisp, Blog

2009-06-22 -- Along the lines of active learning with python & libsvm, I added support for calculating distance of a point from the separating hyperplane to cl-libsvm. In binary classification there is only one SVM involved and one hyperplane. However, with N class problems there is a binary SVM for each of the N*(N-1)/2 pairs of classes and there are as many separating hyperplanes, something the linked python code fails to take into account. As per the libsvm FAQ, the absolute value of the decision value (see PREDICT-VALUES, wrapper of svm_predict_values) divided by the norm of the normal vector of the separating hyperplane is the distance. PREDICT-VALUES and MODEL-W2S are sufficient to calculate it. Note that among the distributed binaries only the linux-x86 version has been recompiled with the necessary changes, but patched sources are also included for your recompiling pleasure.

Calling Convention Hacks

Tags: Lisp, Blog

2009-04-19 -- SBCL's calling convention is rather peculiar. Frames are allocated and mostly set up by the caller. The new frame starts with a pointer to the old frame, then comes the return address, an empty slot and the stack arguments (the first three are passed in registers on x86).

Software archeology aside, the only reason I can see for this scheme is that stack arguments are easier to manipulate when they are after the return address, old frame pointer part, in particular tail calls with any number of arguments can be made without re[al]locating the frame.

The first step towards callee allocated frames is swapping the return address and old fp slots. Asking an innocent question on #lisp accomplished most of the work as Alastair Bridgewater had a patch for x86 against a 0.9ish version that does exactly this.

Forward porting it to current SBCL was a breeze. Relatively speaking, of course, because debugging cold init failures is never pleasant. He also had another patch that biases the frame pointer to point to the old fp slot instead of just before the return address. This has the benefit of making Lisp and foreign frame layouts the same which makes backtraces more reliable and allows external debugging tools recognize all frames.

Callee allocated frames are still quite some way off, but while in the area I sought a bit of optimization fun. With the return address before old fp it is now possible to return with the idiomatic POP EBP, RET sequence. Well, most of the time: when more multiple values are returned than there are argument passing registers they are placed on the stack exactly where the arguments normally reside. Obviously, in this case the frame cannot be dismantled.

... read the rest of Calling Convention Hacks.

X86oid Pseudo Atomic

Tags: Lisp, Blog

2009-03-29 -- The relatively recent chit - chat about allocation and interrupts have had me looking at ways to speed up pseudo atomic in SBCL.

 (defmacro pseudo-atomic (&rest forms)
  (with-unique-names (label)
    `(let ((,label (gen-label)))
       (inst or (make-ea :byte :disp (* 4 thread-pseudo-atomic-bits-slot))
             (fixnumize 1) :fs)
       (inst xor (make-ea :byte :disp (* 4 thread-pseudo-atomic-bits-slot))
             (fixnumize 1) :fs)
       (inst jmp :z ,label)
       ;; if PAI was set, interrupts were disabled at the same
       ;; time using the process signal mask.
       (inst break pending-interrupt-trap)
       (emit-label ,label))))

... read the rest of X86oid Pseudo Atomic.

Code alignment on x86

Tags: Lisp, Blog

2009-03-09 -- There has always been a lot of wiggling of SBCL boinkmarks results. It's easy to chalk this up to system load, but the same can be observed running the cl-bench benchmarks under more ideal circumstances. Part of the reason is the insufficient number of iterations of some tests: measurement accuracy is really bad when the run time is below 0.2s and it is abysmal when there is other activity on the system which is easy to tell even in retrospect by comparing the real and user time columns.

But that's not the end of the story, take for instance FPRINT/PRETTY: it takes more than two seconds but often experiences changes up to 7% caused by seemingly unrelated changes. People have fingered alignment as a likely cause.

Recently this issue has become more pressing as I've been trying to reduce the overhead of x86's pseudo atomic. Unfortunately, the effect is smallish which makes measurement difficult so I tried aligning loops on 16 byte boundaries. This being on x86, that meant aligning code similarly first (it's 8 byte aligned currently).

The change itself (from the allocate-code-object branch of my git tree) is rather trivial, the effects are not. It turns out that depending on the microarchitecture some x86 CPUs like alignment, while the rest should really not care much. In practice, other factors come into play at which we can only guess. It certainly seems that the Core Duo (and likely the Pentium M) is so deeply unnerved by a jump instruction near the end of a 16 byte block that it cannot execute the loop at its normal speed.

... read the rest of Code alignment on x86.

Space Cadet

Tags: Lisp, Tech, Blog

2008-12-15 -- Emacs users often report problems caused by strain on the pinky finger that's used to press the Control key. The standard answer to that is to map Caps Lock to Control. I believe that there is a better way:

Note the placement of modifiers: Control, Meta, Super, Hyper on both sides of Space in this order, with Control being the closest to it. Touch typers especially find having two of each key absolutely essential and the symmetric placement appeals to me.

... read the rest of Space Cadet.

2008 Computer Games Olympiad

Tags: AI, Blog

2008-12-11 -- It seems that the competition has not been standing still (as opposed to Six) and this year marks the end of the golden era. Congratulations to both Wolve and MoHex who beat Six! Thanks to Ryan Hayward who, again, kindly registered Six for the Olympiad.

About the future, I don't really plan on resuming work on Hex in general (and Six in particular), although losing does irk me a bit.


Tags: Tech, Blog

2008-03-28 -- My carefully updated list of files to backup had grown so long that it made me worry about losing something important and the backup didn't fit on a single dvd so I invested in a WD passport and created an encrypted file system on it:

modprobe cryptoloop
modprobe aes
losetup -e aes /dev/loop0 /dev/sdb
mke2fs /dev/loop0
tune2fs -i 0 -c 0 -j /dev/loop0

... read the rest of Backup.

Important remainder

Tags: Personal, Blog

2008-02-04 -- An example may speak a hundred words, but sometimes not even that is enough and you want to be very explicit about the dangers of hand grenades on board.

Finally, some trash talk carefully designed to intimidate: trash

Never die without having made the necessary arrangements.

All pictures were taken at M√°laga airport.

First post

Tags: Tech, Personal, Blog

2008-02-01 -- After a long time of waiting to write my own blog software like true hackers with infinite time do (and those irritated by Wordpress), I bit the bullet and installed blorg - a very low overhead emacs blog engine - on top of org-mode that I happen to use as an organizer. Blorg basically converts an org mode buffer to html files so it is completely static: send me email if you have comments, I have no desire to maintain a more complex solution with comment filtering.

Small fixes had to be made for blorg to be able to deal with org-mode 5.17a and I only had time to bring it to some basic level of functionality. That said here is the blorg-init.el file I'm using right now.

2020-05-03: Since then, this blog has been moved to MGL-PAX.