Paraprogramming Dispatches


Polymorphism with clay and sticks


c
Eugene Zaikonnikov

Sometimes in discussions of obsolete C features, union comes up. Modern style guides and books view it as poor man's struct used in the old days to shave off a few bytes. Ben Klemens in his 21st_Century_C makes it an argument that in near all uses union makes code more error prone.

Here's however an example where unions might come handy.

Imagine you have an application managing several list structures which are similar but not quite the same. They all have list links and character names, but the payloads are quite dissimilar. One obvious way is to reference type-specific payload from the list node. However implementing this naïvely leads to an extra level of indirection in manipulating code.

Let's say we want to have data types for event subscriber mechanism and a FSM.

typedef struct subscriber {
  struct subscriber *next;
  module_rec *mod;
} subscriber;

typedef struct event {
  struct event *next;
  char *name;
  subscriber *subscribers;
} event;

typedef struct transition {
  struct transition *next;
  char *name;
  struct state *node;
} transition;

typedef struct state {
  struct state *next;
  char *name;
  transition *trans;
} state;

The common theme here is the list link, followed by name and then a pointer to payload structure.

Below is the necessary indirection definitions tying it all together into one, unobjectionable to the compiler, data type.

typedef struct node {
  union entry *next;
  char *name;
} NODE;

typedef union entry {
  NODE link;
  state s;
  event e;
  transition t;
} entry;

Notice how node contains the character name, shared by all. In a way it is a "superclass" structure to all of the list types. We then can implement entirely type agnostic lookup and traversal methods.

entry* create_entry(char *name, entry *next)
{
  entry* result;

  if((result = malloc(sizeof(entry)))) {
    result->link.name = name;
    result->link.next = next;
    return result;
  }
  return NULL;
}

entry* lookup_entry(char *name, entry *cur)
{
  
  while(cur && strcmp(cur->link.name, name)) {
    cur = cur->link.next;
  }

  return cur;
}

The code remains generic. Moreover, due to the constant union container size, we can share the memory allocation code. We can refer the types natively further in the code, save perhaps for a cast to/from the generic entry values when using the methods:

event* e = (event*)lookup_entry(msg.payload.name, (entry*)events);
      if(e) {
       sub = e->subscribers;
       ......
      }

It might not seem like a big deal just for a couple of trivial access methods, but the same approach can be used to many other classic and esoteric container data types.

Serious Software SpecLisp for Sinclair ZX Spectrum


lisp
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!

Reset

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
    (cls)
    (fwd 88) (right 90) (fwd 128) (right 270)
    (pend)))

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


lisp
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


lisp
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.

« Older Posts