Miser Project Notes

N020300: Evolution of Ob Structure

Version 0.10 Last updated 2002-03-09-17:45 -0800 (pst)


Ob: The Structure

Ob: The Very Idea

Ob: Precursors

Ob: 0.10 Formulation

Ob: 1.0 Simplicity


Ob: The Structure

Today (March, 2002), I think of Ob as a mathematical structure, Ob: Obs, Inds, Ops.  

In this structure, Obs is the domain of Ob, Inds are the set of distinguished individuals (also in Obs), and Ops are the fundamental operations/functions/predicates of the structure.  The formalization of the structure comes in through reliance on an informal or formal logical system.  

I also realize today (March 9, 2002) that I should begin speaking of Ob in the singular. This comes from the following realization:

Ob: The Very Idea

Some days I think I must be very slow.  

The original ideas for Miser didn't have Obs at all (and I hadn't called it Miser yet).

The initial thinking, around a simple, complete structure for computation involved stratified strings like those of Algol 60.  With stratified strings, there is a way of including an arbitrary string as an individual bead. (example)

This is more than enough to demonstrate a complete computational model, and around 1970 I thought this was appropriate to build.  The inspiration was a 1965 paper by Christopher Strachey on a general-purpose macro processor that operated with stratified strings.  McG, as it was known by its friends, inspired me because of a bug I found in it and in a generalization that was missing from it.  Noticing the generalization, a small, simple thing, gave me insight into what it took to have a complete abstraction for computation.

I chose list structures, and called them Obs, only after looking at a description of a LISP interpreter in Dr. Dobb's Journal.  (I think it was about XLISP, but can't be sure.  Maybe a precursor to XLISP.)  It isn't that I was ignorant of LISP.  I had read and been inspired by McCarthy's 1960s papers.  

Switching to Obs, which are equivalent to stratified strings, was because they are simpler to build and they saved me from the problem I had with stratified strings: Having to make deep copies of large strings to accomplish very elementary operations (such as removing the leading character of a very big string).  It was the lisp cons[] operation, and the use of a garbage collector that had me be interested.

The other appeal of Obs was that atoms are a way to have essentially an unlimited alphabet, and freedom from string-based schemes which are always constrained by character sets.  As I began the formulation, I found even more ways to simplify the picture until it was very close to what there is now.  The simple primitives of a, b, c, match, and apply.  The single ob for self-reference, the single ob for argument reference.  And most of all the idea that Ob is a closed, floating structure.  Only through the applicative interpretation of individuals is there interaction with any external world or realization of other models of representation.  And it is all manifest through Ob.

By 1980 the initial formulation of Ob was complete.  In building the first implementation, I had come up with a class-oriented implementation, and Miser 0.1 reflected that.  

I didn't begin thinking about the current formulation until at least 10 years later, and I started writing it down in 2000.  The biggest reason for revising Ob was my being unhappy about quotation and the way it was involved in the eval rules of Miser 0.1.  I wanted to have something structural in place of a reserved individual (which makes quotation a linguistic but not a structural device).  I see now that I was hankering for a stronger resemblance to stratified strings, but mostly it just bothered me to have this device extra-structural.  And to accomplish that, I had to give up the nice class-oriented structure from Miser 0.1.  I realize now that this was a very smart move.

Ob: Precursors

Christopher Strachey's McG

Inspiration by a bug / oversight - making McG computationally complete

The omission of quotation operator

The clever identity and name-resolution mechanism

A bug on the stack

Recognizing the Algol 60 string in Strachey's McG data structure

From McG to Plex

[The name was certainly from Doug Ross, though I was not applying it very faithfully.  Mostly I was pretty certain that a Plex was enough.]

Having self and arg as the only special symbols

Operating as a pure suffix-notation processor

[ and ] instead of  ` and ´ directed quotes

Printer in 1970 didn't have the characters, and it would have also been too confusing

Limitations

It is all done with character strings and is completely closed (sort of the Turing Machine interpretation of Ob).

Garbage collection and/or string copying were problematic

It is enough of a really simple model to show that all programs on strings can be done this way.

[See if I can find note from Knuth asking just what is the point of the Algol 60 version of the Plex interpreter.]

Ob: 0.10 Formulation

 

Ob: 1.0 Simplicity

 


References

[Strachey1965] General Purpose Macrogenerator.  Cite the 1965 British Computer Journal publication and link to the on-line edition.

History

0.10 2002-03-09 Create Initial Boilerplate and resolve Ob versus Obs (orcmid)
I started thinking about Miser 0.x and the model that I had then.  This reminded me that the structure is Ob, not Obs, and that Obs are just a way of speaking, so I am capturing that too. 

created 2002-03-09-14:37 -0800 (pst) by orcmid
$$Author: Orcmid $
$$Date: 04-01-06 13:03 $
$$Revision: 6 $

Home