Paraprogramming Dispatches

Serious Software SpecLisp for Sinclair ZX Spectrum

Eugene Zaikonnikov

The first computer I owned and learnt the basics of programming on was a Sinclair ZX Spectrum clone. Very modestly specced machine even for its heyday, it nonetheless could run a range of high level languages aside from built-in BASIC. I remember successfully porting backpropagating network code from German C't magazine to HiSoft Pascal, and fumbling around in HiSoft C.

Seirous Software SpecLisp, however, was a bit of enigma. Lisp tutorials were relatively hard to come by in pre-Internet age, and naive tinkering led nowhere.

Booting up

Fast forward to 2015, the days of information abundance, when things like SpecLsp user guide are floating around. The interpreter can be downloaded off the net as well, and ran under a number of free emulators. Let's finally have a look.

The origins of this dialect can be immediately traced to Lisp 1.5, down to the use of plist markers such as PNAME and APVAL, and rather specific (oblist) function, serving the original function of dumping the definitions in memory. As expected, it uses dynamic binding and FUNARG problem is not quite solved. And no QUOTE shortcuts: you have to spell it like you mean it.

Just like Lisp 1.5, it comes from the times predating bike helmets, mandatory seatbelts and interpreter sandboxes. Native function definitions are stored as call addresses via SUBR property of symbol plists. As such it perhaps makes the most concise FFI ever. Here's it issuing a system reset by jumping to 0x0000. I dare you to do that with a modern Lisp!


Being a true Lisp interpreter, it allows one to edit lambda definitions equally trivially:

Modify lambda

Now, it's easy to rationalize how self-modifying code is not really a feature and there's no need for it in the age of macros. But admit it, this is still kind of neat, in its own old school way. Feels just right. Besides, there's no other way to edit the definitions..

Remarkably, SpecLisp is case sensitive and lowercase by deafault, predating Franz bold introduction of that to the world of Common Lisp by 17 years.

Case sensitivity

But perhaps the most surprising part is SpecLisp's graphics extension. The interpreter was probably meant to serve educational purposes (even by 1983 standards, ZX Spectrum was an underwhelming Lisp machine), hence it featured a set of Logo-like turtle control commands.

Let's put it to good use by making a period true graphics demo.

The initialization routine to clear screen and center the pen:

(de prep (a)
  (progn nil
    (fwd 88) (right 90) (fwd 128) (right 270)

A function to render a square of specified size, and another to draw those squares in diminishing size while rotating:

(de square (n)
  (progn nil
    (fwd n) (right 90)
    (fwd n) (right 90)
    (fwd n) (right 90)
    (fwd n) (right 90)))

(de rotate (a n c)
  (while (greaterp n 0)
    (right a)
    (square n)
    (setq n (diff n c))))

In case you wondered, the opening nil in progn is the empty bindings list: the construct doubles as impromptu let.

Diminishing squares

Visualizing larger graphs with Tulip

Eugene Zaikonnikov

Simple algorithms handling large-ish data sets tend to be pretty. However, the results aren't necessarily intuitive for sifting through with REPL and Lisp inspector, and dedicated visualization tools come handy.

For sizable graphs I settled with Tulip, a powerful and comprehensive tool for juggling around massive (hundreds of thousands nodes) data sets. One can conveniently pan, rotate and zoom the graph, limit the visibility to specific clusters. It is possible to run a wide range of ordering, manipulating and testing algorithms as well.

I came up with cl-tulip-graph (formerly Bouquet) for quickly blueprinting a .tlp graph of a Lisp data structure. The README explains its use, but here's a real-life sample of generation. It generates a graph for the internal state of a computationalist pattern matcher; the particular structural details are unimportant here.

 1 (defun render-graph (&optional (filename *standard-output*))
 2     (bouquet:new-graph)
 3   (loop for entry in (append '(zero one two three four five six seven eight nine
 4           *mnist-id* *row* *image* *blob*
 5           dark light)
 6            *universum*) do
 7        (bouquet:register-node entry)
 8        (bouquet:label (bouquet:node entry) entry))
 9   (loop for entry in '(*mnist-id* *row* *image* *blob*)
10      do
11        (bouquet:make-cluster (symbol-name entry))
12        (loop for rec = (symbol-plist entry) then (cddr rec)
13    for ctxt = (first rec)
14    for links = (second rec)
15    while rec do
16      (bouquet:add-to-cluster
17       (bouquet:cluster (symbol-name entry))
18       (bouquet:node ctxt))
19      (loop for r in links do
20      (bouquet:register-edge
21        (bouquet:node ctxt)
22        (bouquet:node r)))))
23   (with-open-file (f filename :direction :output
24           :if-exists :overwrite
25           :if-does-not-exist :create)
26           (bouquet:render-graph f)))

After the graph initialziation, the loop on line 3 through 8 sets up all the nodes with labels. The next loop sets up a bunch of clusters and adding the edges between the nodes. The graph is rendered into file stream on the last line.

Unordered graph

This trihobeozar of a graph rendered nicely via Cone Tree layout:

Cone layout

CL-JPEG has been updated

Eugene Zaikonnikov

A long due update to Common Lisp JPEG Library has now been merged into sharplispers/cl-jpeg.

The summary of changes:

  • The various global state tables and counters were moved into special variables of decoder/encoder functions. This should address the concerns of thread safety.
  • The monolithic source file was broken up into several according with modern way of structuring the projects.
  • Metadata for :author and :description was added to the project's .asd.
  • The contributors are now listed. Do let me know if I forgot to add someone.

Revisiting own 16 year old code was an interesting experience. Thanks to everyone who kept the project alive over the years.

Wait channels as debugging aid for threading bugs

Eugene Zaikonnikov

..In every system programmer's career inevitably comes a moment when they encounter a non-obvious, asymptomatic, poorly reproducible bug in critical software running on remote site without remote debug instrumentation.

Well there was a symptom. The device would put up a diagnostic message amounting to "oops" and stop responding to stimuli. The log file would stop growing while the generating thread is still around. The process would not react to SIGQUIT (denying me a core dump). In other words, a very good hint of a deadlock.

To top that, the issue would appear only on few devices out of a hundred, and after running for at least few weeks.

In cases like this, however, there's still a great tool at disposal: wchan (wait channel) of procfs. Per the manpage:

 (35) wchan  %lu
      This  is the "channel" in which the process is waiting.  It is the address
      of a location in the kernel where the process is sleeping.  The corresponding
      symbolic name can be found in /proc/[pid]/wchan.

Each process has also associated tasks, in this case threads, found in /proc/[pid]/tasks/, which is again a list of PIDs with a wchan field associated. I start with skimming through the application threads on an affected system, looking for something out of ordinary.

The application is structured around a central SYSV message queue, where a state machine dispatches the messages and notifies the subscribed functional modules. Some of the modules are separate threads, but a number of simpler tasks are executed directly in the dispatcher thread.

Looking at the one of the threads reveals it is blocked in do_msgsnd(): the kernel call for sending SysV IPC message:

 # cat /proc/306/task/311/wchan 

Now, sending a message can block in one case only: the queue is full. Again, we can check that via procfs.

 # cat /proc/sysvipc/msg
       key      msqid perms      cbytes       qnum lspid lrpid 
    151273          0     0       16384        128   306   306

Yep, qnum is at 128, the limit on the system, so the queue is full. The only place that consumes the queue is the dispatcher thread, and the most likely way for that part to lock up is for notification loop to block on some call.

After checking the wchan value of the dispatcher thread versus one on a healthy system, the likely offender is found:

 # cat /proc/306/task/317/wchan 

This is the kernel call handling the opening of Unix socket. The only place where communication over AF_UNIX happens is the code forwarding system status over to snmpd. Upon examination it turns out cough the socket is being opened and closed for every message session. Normally this shouldn't be a problem, but the system runs with pretty ancient kernel, affected by certain bugs like CVE-2009-3621, and this is just not a good practice in general.

The conclusion is, there is a way out of most desperate situations. If you think you are stuck, remember it's nothing compared to what Apollo 13 crew had to go through.

« Older Posts