Paraprogramming Dispatches

Plists are handy simple key/value stucures, stored in a single-linked list. A plist (a 1 b 2 c 3) holds three numeric values for properties a through c. Lisp dialects have standard functions for conveniently adding, looking up and removing the properties.

All operations are thus O(n), but shorter plists (say a dozen or two entries) typically beat hash tables due to substantial constant overhead of the latter.

Symbol-plists specifically are plists attached to a Lisp symbol via dedicated language mechanism.

History

The earliest mentions of property lists predate first Lisp manuals. In his 1958 Programs with Common Sense paper[1], John McCarthy had to say the following:

For example, to most people, the number 3812 is not an object: they have nothing to say about it except what can be deduced from its structure. On the other hand, to most Americans the number 1776 is an object because they have filed somewhere the fact that it represents the year when the American Revolution started. In the advice taker each object has a property list in which are listed the specific things we have to say about it.

Some remarkable facts can be deduced from this short passage:

• Symbol-plists predate Lisp symbols conceptually. Here, a number is used as an object with a list of properties.
• The intent is providing a form of associative memory, a key-value store for the procedural evaluator. It’s like noSQL before SQL!
• Symbol-plists are the original sin of functional programming. They were meant for side effect in FP before FP was a thing. Thus classic Lisp was never meant to be purely functional; state is not an oversight but a deliberate design decision.
• Even though the precise storage model is unspecified, a list is implied. LISP at the time was still a study in progress and hash tables were known since 1953, but they would have been too costly in terms of memory.

The earliest known object orientation mechanism

The use of word object in the quote above is not coincidental. The sets of properties were defining the object entities. The objects in early Lisp would manifest as symbols. LISP 1.5 implementation hinged on symbol-plists, with four pre-defined properties:

• PNAME, the print name of the symbol
• EXPR, a user defined associated function, stored as S-expression
• SUBR, pointer to machine code built in subroutine
• APVAL, the global scope storage, confusingly referred as “constant value” (as opposed to value within the function’s dynamic scope)

This scheme was later split into symbol-name, symbol-function and symbol-value cells.

Plists and symbols were thus providing

• User definable object properties
• Encapsulation mechanism with accessors
• Pre-defined system properties
• Dedicated property for associated function

Granted, there was no explicit this/self-reference to be used in stored function, but that’s just sugar trivia:

(defmacro mydefun (name args &rest body)
  `(defun ,name ,args
	(let ((this ',name))
	  ,@body)))

(mydefun foo ()
  this)

(foo) => FOO

..the reason it’s not there in the spec is that the “modern” OO model was not a design concern. Advice Taker was meant to be procedural logic manipulator, not an agency. This conceptual difference would lead to eventual split of McCarthy-Minsky cooperation, and we’ll see Minsky introducing the object-referencing methods with his frames effort.

It is important though that Lisp symbols were true object entities existing at run-time from day zero.

Symbol-plists as namespaces

Symbol-plists can be thought as defining factor of lisp arity. In the degraded case of Scheme we get lisp-1 with one name/value pair only.

Lisp 1.5 is an lisp-n, where n is the size of the largest symbol plist in the system.

Common Lisp is a lisp-(c + n), where c is implementation-dependent number of key-value pairs (or cells) factored out of original symbol-plist. Funny enough, symbol-plist is now one of the 4 standard mandated cells itself. The advantage here is the system cells are safe from accidental plist smashing and don’t impose a run-time penalty for user’s plist manipulating code.

Use and disuse

Nearly all early AI programs make extensive use of symbol-plists. As a didactic sample I would recommend annotated tree implemenation in Steve Tanimoto’s ID3-like inducer. However, with gradual changes in Lisp implemenation landscape and programming mindset, symbol-plists fell into disuse.

An obvious contributing factor to symbol-plists decline was the removal of system properties into separate cells. However, the bigger affecting trend was the move from symbolic manipulation in Lisp code throughout 1980-1990s. This had several reasons. The symbol manipulating, computationalist AI effort has largely collapsed facing advances in statistical ML techniques. The proliferation of viable macro systems and native compilation obliterated demand to code-as-data manipulation. This was amplified by the influx of Algol tradition programmers, where symbol entities are simply not a concept and hence the whole approach remained alien.

There is still acceptance of detached plists for transient key/value records, but unsurprisingly, symbol-plists are viewed as obsolete, almost counter-cultural thing. Now it’s certainly personal, but plists without symbols are like naked singularities: they might occur in nature but still are abominations. Or like garden slugs: sad, vulnerable version of a snail without a place to belong. As plists have no inherent type in Common Lisp[2], their interpretation is contextual, and outside of symbol-plist realm the context is not necessarily clear.

[1] Published in vol.1 1959 proceedings of Mechanisation of Thought Processes conference. A remarkable print from low hanging fruit times of Computer Science, with submissions from McCarthy, Minsky, Ershov, Hopper, Backus, McCulloh and other pioneers of note.

[2] Interestingly, in Lisp 1.5 plists were tagged by -1 value in CAR of the list. There were other storage optimizing techniques too, such as special format for flags, the valueless properties.

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.

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.

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:

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.

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.

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

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