SLip runs QUEEN (Lisp chess library), and a PGN viewer in browser

In the past couple of months I've added some more CL support (some bitwise operators, some multi-dimensional array, and some reader customization), so one day I was able to load my QUEEN chess library and play a bit with it in the browser. It's now included in the build, so you can try this in the REPL:

SL-USER> (load "lib/queen.lisp")
;; Loading lib/queen.lisp
NIL
SL-USER> (in-package :queen)
#<PACKAGE QUEEN>
SL-USER> 
;; package changed.
QUEEN> (defparameter g (make-game))
#S(GAME :BOARD #(0 0 0 0 0 0 0 0 ...)
        :STATE 0 :SIDE 64 :ENPA NIL :FULLMOVE 0 :HALFMOVE 0)
QUEEN> (reset-from-fen g +fen-start+)
#S(GAME :BOARD #(66 68 72 65 96 72 68 66 ...)
        :STATE 15 :SIDE 64 :ENPA NIL :FULLMOVE 1 :HALFMOVE 0)
QUEEN> (print-board (game-board g))
8 │ r n b q k b n r
7 │ p p p p p p p p
6 │ - - - - - - - -
5 │ - - - - - - - -
4 │ - - - - - - - -
3 │ - - - - - - - -
2 │ P P P P P P P P
1 │ R N B Q K B N R
  └─────────────────
    a b c d e f g h
NIL
QUEEN> (let ((*unicode* t)) (print-board (game-board g)))
8 │ ♜ ♞ ♝ ♛ ♚ ♝ ♞ ♜
7 │ ♟ ♟ ♟ ♟ ♟ ♟ ♟ ♟
6 │ □ □ □ □ □ □ □ □
5 │ □ □ □ □ □ □ □ □
4 │ □ □ □ □ □ □ □ □
3 │ □ □ □ □ □ □ □ □
2 │ ♙ ♙ ♙ ♙ ♙ ♙ ♙ ♙
1 │ ♖ ♘ ♗ ♕ ♔ ♗ ♘ ♖
  └─────────────────
    a b c d e f g h
NIL
QUEEN> (time (perft g 3))
Depth: 3, Count: 8902, Captures: 34, Enpa: 0, Checks: 12, Promo: 0, Castle: 0
Evaluation time: 1566.74ms
;; ...
QUEEN> (time (perft g 4))
Depth: 4, Count: 197281, Captures: 1576, Enpa: 0, Checks: 469, Promo: 0, Castle: 0
Evaluation time: 34678.80ms
;; ...

PERFT results are correct, which is some good indication that it's working properly. However, it's depressingly slow. Timings above are in Firefox (Chrome is almost 2x faster). For reference, SBCL runs PERFT to depth 4 in 30ms, which means SLip-on-Firefox is 1000+ times slower.

Bluntly put, using SLip for any time-intensive algorithm is an insult at your hardware.

You might recall from my previous writing on QUEEN that I was able to improve its performance by orders of magnitude by declaring types and inlining functions. But SLip is a straightforward single-pass compiler and ignores those declarations.

I added support for inlining global functions, and it helps (5 seconds gained for PERFT 4). Then I went to work on inlining local functions (I'm pretty sure that inlining alone, if done properly, would cut the run time in half) — but that's when I realised that my inlining is buggy, because free variables in inlined code could be clobbered by the foreign lexical scope. So I disabled it for now.

I hope one day to start working on a proper optimizing compiler, but it seems to be a lot of work (weeks or months? lifetime?) and it's somewhat scary.

For now I took a break from SLip internals, but I thought that since I have QUEEN, and QUEEN has a PGN parser, it would be a nice little project to implement a chess viewer. That would give me a feel of what it would be like to work on a Web application in Lisp.

PGN viewer

Here is direct link to a demo which fetches my father's most recent game from Lichess and opens the viewer1. Loading everything will take a few seconds; QUEEN is not precompiled and also, parsing PGN is somewhat slow because it calls the move generator for each move.

Or you can try this link which only loads the PGN viewer, and type in the REPL:

;; switch to package first, because nothing is exported.
;; you can also use C-c M-p, as in SLIME.
SL-USER> (in-package :pgn-viewer)

;; you can pass moves in PGN directly:
PGN-VIEWER> (display-game "d4 d5")

;; or an input stream, e.g. from lichess:
PGN-VIEWER> (display-game (sl-stream:open-url "https://lichess.org/api/games/user/vlbz?max=1"))

;; there's a shortcut for this:
PGN-VIEWER> (lichess "vlbz")

As I said in other posts — but I mention it again — you can use M-. on any symbol to jump to definition, modify the code and press C-M-x to recompile. It was pretty fun to work on it in this way, although a minor inconvenient was that in order for my changes to be picked up I had to close the dialog and eval display-game again — of course, that happens because most code is in that very function.

Some notes about the implementation

I started by writing some DOM wrappers (lib/dom.lisp). Most of them map directly to DOM APIs, although I didn't use the exact same names.

The API for event listeners, however, ended up quite different. In JS you never ask the question “which thread will run my event handler?” — because in JS there's a single thread. It runs the script tags from the page, and then it starts an event loop which responds to user actions. The event loop never stops (and by the way, this very thread runs our Lisp code as well). If this thread is busy doing something (synchronously), it won't be able to process further events and the browser will seem frozen.

For this reason (and because we can!), SLip implements “green threads”. So you can have a potentially long-running computation, but it will not freeze the browser, because SLip threads will take a break every N milliseconds, using setTimeout to resume2, in order to let the JS thread breathe and catch up with pending events.

When you input something in the REPL — for example (display-game "d4") — a new Lisp thread is spawned, the expression is parsed, compiled and executed, and then the input thread exits. But then, if display-game had set up DOM event listeners, who will execute them later when events occur?

The solution I chosen is to have display-game start its own thread, with its own event loop. On the JS side, an event handler will just send a message to the Lisp thread3. I already had an implementation for the messaging queue. The API looks like this:

(dom:on-event element "click" :signal :click :process thread)

and this states that when element is clicked, the given thread will be sent the message :click (any value will do here; it doesn't have to be a keyword, or even a symbol). The event loop will then dispatch to a handler which was installed for that value with the %receive primitive function:

(setf receivers (make-hash-table))
(setf (gethash :click receivers) #'on-click)
(%receive receivers)

%receive puts the thread on hold, so it effectively stops running, but it will be reinstated when it gets a message, it executes the associated handler, and then it continues running normally (whatever follows after the %receive form) — so in order to keep handling messages, we want to do this in a loop4. The event loop in display-game looks like this:

;; this ensures that for any JS errors we'll get a catch-eable Lisp condition
;; and our thread will keep running.
(%:%catch-all-errors)

;; event loop
(loop while running
      do (handler-case
             (%:%receive receivers)
           (error (err)
             (format *error-output* "!ERROR: ~A~%" err))))

The handler for dialog's "close" event will set running to NIL, and then the thread will exit.

I should write a separate article about the thread message system, I think it's cool. But first, I should create a proper package and decide on a public API for it.

So much for today's braindump. Working on this was, overall, a pleasant experience, even though there are many things to improve. For example, I could provide some debugging support, since the VM is interruptible and inspectable; I'd just need to add some debug info into the bytecode, and of course, an UI for it. But that fades into insignificance when PERFT to depth 4 takes 30 seconds. I'm gonna sleep on it for a while and dream about that smart optimizing compiler.

Add your comment