Paraprogramming Dispatches

Sharing here a small collection of documents by Douglas B. Lenat related to design AM and EURISKO that I assembled over the years. These are among the most famous programs of symbolic AI era. They represent so-called ‘discovery systems’. Unlike expert systems, they run loosely-constrained heuristic search in a complex problem domain.

AM was Lenat’s doctoral thesis and the first attempt of such kind. Unfortunately, it’s all described in rather informal pseudocode, a decision that led to a number of misunderstandings in follow-up criticism. Lenat has responded to that in one of the better known publications, Why AM and EURISKO appear to work.

AM was built around concept formation process utilizing a set of pre-defined heuristics. EURISKO takes it a step further, adding the mechanism of running discovery search on its own heuristics. Both are specimen of what we could call ‘Lisp-complete’ programs: designs that require Lisp or its hypothetical, similarly metacircular equivalent to function. Their style was idiomatic to INTERLISP of 1970s, making heavy use of FEXPRs and self-modification of code.

There’s quite a lot of thorough analysis available in three-part The Nature of Heuristics: part one, part two. The third part contains the most insights into the workings of EURISKO. Remarkable quote of when EURISKO discovered Lisp atoms, reflecting it was written before the two decade pause in nuclear annihilation threat:

Next, EURISKO analyzed the differences between EQ and EQUAL. Specifically, it defined the set of structures which can be EQUAL but not EQ, and then defined the complement of that set. This turned out to be the concept we refer to as LISP atoms. In analogy to humankind, once EURISKO discovered atoms it was able to destroy its environment (by clobbering CDR of atoms), and once that capability existed it was hard to prevent it from happening.

Lenat’s eventual conclusion from all this was that “common sense” is necessary to drive autonomous heuristic search, and that a critical mass of knowledge is necessary. That’s where his current CYC project started off in early 1990s.

Bonus material: The Elements of Artificial Intelligence Using Common Lisp by Steven L. Tanimoto describes a basic AM clone, Pythagoras.

It all started with a raid on a long abandoned hosting service. Seen a mention of it in the news, leading to a vague recollection of using it for something. Email address associated with the account was long defunct, and the service itself changed ownership a few times in the past two decades. But incredibly, I could recall login credentials and they worked still.

Amazingly, in a pile of abandoned HTML templates, obsolete software archives and Under Construction GIFs there was a source file for a project I long considered lost. It’s a minimal Lisp bytecode interpreter written in assembly for ZX Spectrum along the lines of MIT AIM-514. Save for address locations and maybe a couple ROM calls for error reporting it’s generic Z-80 code.

It was a part of bigger project that should have included a primitive REPL, but no trace of that was found. Also, am quite sure there is a henious bug lurking in the mark&sweep GC. Should really find time to finally debug that!

After having some issues with microphone input handling in portaudio I took a shortcut and sketched Also ALSA: an interface to Advanced Linux Sound Architecture library. As the name suggests, it’s not the first CL wrapping of it. It is however small, reasonably self-contained and can handle both input and output.

LGPL to comply with alsa-lib.

This week I put together a small NTP client. To keep dependencies at minimum and to avoid forcing a permanently running process onto users, it does not attempt to adjust system RTC clock, compensate jitter or evaluate time server quality. As I see it, much of that behaviour is easy enough to add via mixins with the defined NTP class.

NTP timestamp is two 32-bit values: seconds and fraction of a second. NTP conveniently counts seconds from Jan 1 1900, just like universal time in Common Lisp. There is however no portable Common Lisp representation for fractions of a second. Thus the client sticks to using NTP formatted fraction for that. It is way more precision than any existing CL implementation has in INTERNAL-TIME-UNITS-PER-SECOND, but this makes the value comparable across implemenations. The new GET-ADJUSTED-UNIVERSAL-TIME method then returns a pair of values: universal time and NTP fraction. The fraction can be converted to the implementation’s internal time scale with FRACTION-TO-INTERNAL.

Internally we define no special arithmetic on NTP timestamps but provide two conversion macros for single integer space. BIG-TIME converts NTP stamp into a large integer. We then do all calculations in that domain, and convert back to NTP timestamp using SMALL-TIME when it’s time to send it over the wire. An NTP instance stores adjusted time as an offset from internal real time. The offset is roughly intialized with universal time and then adjusted after each server request.