A city is not a tree
While reading Christopher Alexander’s amazing essay “A City is Not a Tree” I was reminded of a page in one of my old notebooks. On that page I had taken some notes on some amazing computer science (and related) dissertations that might form the basis for a personal program design gestalt.1
In this post I’ll mention each paper that I wrote and provide a little context for my choice and add a little motivation.
Constraint programming
“The Definition and Implementation of a Computer Programming Language Based on Constraints” By Guy Steele
follow-up reading / viewing
- Scheme code implementing the constraint language in the paper
- Constraint logic examples presented in The Joy of Clojure 2nd edition
- Building Problem Solvers by Forbus and de Kleer — a great book that I’ve been slowly working my way through for a couple of years.
- Algorithm = Logic + Control by Robert Kowalski
- Constraints by Steele and Sussman
- We Really Don’t Know How To Compute! — a talk by Gerald J. Sussman at the 2011 Strange Loop conference that builds on all of the ideas in Steele’s original and also the “Constraints” paper.
Actors
“ACTORS: A Model of Concurrent Computation in Distributed Systems” by Gul Agha
This was perhaps the work that built on the previous 14 years of Actor theory and formalized it into a practical and workable model of computation.
follow-up reading / viewing
- A Universal Modular Actor Formalism for Artificial Intelligence
- Semantics of communicating parallel processes. by Irene Greif
- Early history of Erlang by by Bjarne Däcker
Continuations
“Portable and high-level access to the stack with Continuation Marks” by John Clements
This is a generalization of continuations to provide a way to store tagged marks in each continuation frame. This is a bit nuanced, but I learned a lot about “classic” continuations by seeing this contrasting approach.
follow-up reading / viewing
Internet of Things
“Programming Memory-Constrained Networked Embedded Systems” by Adam Dunkels
I read this a long time ago most because I was interested in the idea that someone had developed a fairly modern operating system and TCP stack on the classic Commodore 64. While this was not the progenitor of the “Internet of Things” meme, it went well with (at the time) my exposure to the beginnings of IoT as a stand-alone movement, stemming from what was the seeds of sensor network simulation techniques.
follow-up reading / viewing
SHRDLU
“Procedures as a representation for data in a computer program for understanding natural language“
One of my summer projects in college2 was to pick a famous paper and implement the system described therein. My choice (with some prompting from my professor) was a “Blocks World” program that, given an abstract representation of stacked colored blocks, took English-language commands to manipulate the blocks. The program was written in XLISP and while it did understand a limited subset of English, the language that it understood was more Zork-like than anything else. For a grad school project I further built on that codebase by wiring in CLIPS and allowing the specification of a goal state, after which the program would solve the required steps to reach that goal.
follow-up reading / viewing
- Understanding Natural Language by Terry Winograd
Speaking of CLIPS…
Production Rules
“On the efficient implementation of production systems” by Charles Forgy
My undergrad and graduate focus was on expert systems design and development3 so needless to say this paper was kinda the whizz for me.
follow-up reading / viewing
- Rete: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem by Charles Forgy — I’m very familiar with the Rate algorithm and a couple of its implementations in CLIPS and OPS5. Indeed, I’ve poured over this paper more than any other in my life as I’ve implemented Rete my fair share of times in various languages.
- Expert Systems Principles Programming
- Jess in Action — IMO the best book ever published by Manning
- A teeny tiny production rules system in Clojure
fexprs
“Fexprs as the basis of Lisp function application; or, $vau: the ultimate abstraction” by John Shutt
It was long into my life as a Lisp adherent that I learned about fexprs, which have a long history in LISP. Simply put (nearly to the point of libel) fexprs are functions that do not evaluate their arguments. For a long time fexprs were a dead branch of the Lisp family lineage, but Shutt’s paper gives them the thorough and respectful treatment that they deserve.
follow-up reading / viewing
- The LISP 1.5 Programmer’s Manual
- The Evolution of Lisp by Steele and Gabriel
- The theory of fexprs is trivial by Wand
Contracts
“Behavioral Software Contracts” by Robby Findler
At one time I was really into contracts programming and its applicability in ensuring correct software, both of the object-oriented and functional kinds. In the realm of the functional, the most interesting aspect of contract specification came when dealing with, using, and eventually assigning blame to higher-order functions. This paper was a godsend for me in trying (stress on the “try”) to get that correct in my own explorations.
follow-up reading / viewing
- Behavioral subtyping using invariants and constraints by Liskov and Wing
- Programming with specifications by Luckham
- Object-oriented Software Construction by Meyer — For a time this was my personal programming bible.
- Getting Erlang to talk to the outside world by Joe Armstrong — a cool spec for shipping contracts along with data packets
Kay
“The Reactive Engine” by Alan Kay
I find Alan Kay’s work inspiring especially in the magnitude of breadth at which it tends to operate, even when it appears to have a narrow focus. Kay’s thesis is about the design of a portable tablet computer and methods for extending it via an environment called FLEX. In the age of ubiquitous computing in one’s pocket, it’s fascinating to see how close we’ve come, yet simultaneously falling so short.
follow-up reading / viewing
- The Viewpoints Research Institute
- Bret Victor — perhaps the spiritual successor to Kay
- The Mother of All Demos
Distributed Systems
“Data-centric Programming for Distributed Systems” by. Peter Alvaro
I worked in distributed simulations for a long time and for most of that time the task of specifying those simulations and managing and synchronizing their executions was a black art. The teams that I worked for during those years spent vast resources in an attempt to make sense of a very non-deterministic environment. Our approach, which was inspired by Alvaro’s work in Daedalus and Bloom, was that we needed to start with a solid simulation federation specification language.4
follow-up reading / viewing
- “Dedalus: Datalog in Time and Space” also by Peter Alvaro
- “Guarded Horn Clauses by Kazunori Ueda — a side branch that we were exploring during my simulations work
- “Lineage-driven Fault Injection” by Alvaro, Rosen, and Hellerstein. — more amazing work by Alvaro that’s currently melting my mind
Programming Environments
“Sketchpad: A man-machine graphical communication system” by Ivan Sutherland
It’s hard to express how influential Sutherland’s work has been not only in the realm of environment interactivity, but also to object-oriented programming, constraints programming, and graphics.
follow-up reading / viewing
Presentation based user interfaces by Eugene Ciccarelli IV
PYGMALION: A Creative Programming Environment by David Smith — perhaps one of the more prominent early attempts to build a system around Sutherland’s ideas and lessons.
Principles of Interactive Computer Graphics — A nice snapshot of computer graphics in the 1960s
Lisp and Such
“Implementation of a list processing machine” by Tom Knight
Tom Knight is a giant in the annals of computing history having directly participated in important contributions to the field, including but not limited to: ARPANET, AI, the Connection Machine, bitmapped displays, synthetic biology, Project MAC, and Lisp Machines. It’s the last topic that forms the topic of this astonishing thesis that sowed the seeds for the eventual Lisp machine industry.
follow-up reading / viewing
- CONS and CADR
- CADR emulation
- The Connection Machine“by Daniel Hillis
- LISP Lore — focuses on the Symbolics Lisp Machine
Smalltalk and Such
“The Design and Evaluation of A High Performance Smalltalk System” by David Ungar
Ungar is known primarily for his work on the SELF programming language, but prior to that he was a Smalltalk luminary. His thesis describes a RISC machine architecture called SOAR that can run Smalltalk (and languages like it) efficiently. The “Previous Work” section is worth its proverbial weight in gold.
follow-up reading / viewing
- SELF: The Power of Simplicity
- The Early History of Smalltalk by Alan Kay — generally fascinating, especially in light of the “Previous Work” section.
There are so many more examples of stunning graduate work that with this paltry list I’ve barely scratched the surface. Feel free to comment below with your own choices or drop me an email to discuss 
:F
-
A topic for another day… but Alexander’s work is as good a summary as any I suppose. ↩
-
My college had a summer program for its computer science department where students could work full-time with a local tech company and also work on a summer-long project. I learned a tremendous amount during this time and am still influenced by those lessons even today. ↩
-
A decidedly unfashionable branch of Ai these days… though I’ve often found that most systems that I consult for could use an expert system or have a “ad-hoc, informally-specified, bug-ridden, slow implementation of” an expert system embedded within. Even in the face of the fact that I rarely do active expert systems development, the processes of expert system design still influence the way that I do greenfield systems development. ↩
-
Sadly, I never got the chance to fully follow through with the ideas but we were definitely on to something. ↩
No Comments, Comment or Ping
Reply to “A city is not a tree”