read


read
or learn more

A city is not a tree

Feb 22, 2019

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

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

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

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

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

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

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

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

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

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

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

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 email

:F


  1. A topic for another day… but Alexander’s work is as good a summary as any I suppose. 

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

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

  4. 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”