I did all the design for the data structures for the CDC 3300 and the
SDS940. The 940 is the one of most interest. (01)
There were two structures that fit together. One was the structure inside a
940 memory page and the other was the overall NLS three structure. (02)
>From a page management viewpoint, an NLS statement was a string of words.
The statements could be compacted within a page. Links into the page were
adjusted during the compaction. New statements were heuristically placed
close to their peers in the NLS branch. A statement could not be larger than
a single page. (03)
Think of the statements as the CAR of a Lisp list CONS. CDRs in the same
page displayed faster. (04)
Memory on the 940 was very limited. Instead of an attribute-value pair as
was used in the PDP10 version, the 940 version worked with bits inside 19
bit words. (05)
An NSL statement had a fixed length header and a variable length string. (06)
The header had a pointer to the next statement in the branch. It used a
single bit to flag the last statement in the branch. For this last
statement, the pointer pointed to the parent for the branch. (07)
All the rest of the header was bit allocated fields. Three characters for
the initials of the last person to edit the statement. A time-date field. I
think that was it, maybe there was another field -- I do not remember. (08)
On both the CDC 3300 and the 940, NLS had a built in SNOBOL system. All the
Meta Compilers, the compiler, and NLS all used my SNOBOL string processing
routines all string processing. Statement names, statement flags, embedded
view control specifications, ... everything about the string field of the
statement was done using regular expression parsing and string construction
with the SNOBOL primitives. This saved a lot of space. I know because I
built all this. (09)
So, statement names were "(" $(L/D) ")" at the start of a statement. View
specification control was "[" name ":" flags "]" in the string. (010)
The 940 had a way to extend the standard instruction set. I designed the
extended instructions to match the SNOBOL primitives. This made inline
pattern matching compact and with low overhead subroutine calling. Most of
the system ran as what today would be called objects. Almost no variables
were passed between subroutines. This was for speed. The system loader did a
static analysis of all possible subroutine calling and translated address
into fixed locations. This was modeled after the IBM 7090 overlay design. (011)
Basically, everything was modeled after LISP for the overall structure of
the nodes and SNOBOL for the strings and their contents. All the compaction
and garbage collection routines were modeled after their counterparts in
LISP and SNOBOL. Both list and string garbage collection used bit tables to
mark used and words and a second pass to compact. (012)
The only exception was a hash table for the overall file. The hash table
contained the statement address for all named statements. I remember when I
implement this and worked to find a hash algorithm with good collision
behavior for NLS statement names. (013)
Well, I'm running out of memories. I'll answer questions. That may bring
more to mind. (014)
Jeff (015)
-----Original Message-----
From: Jonathan Cheyer [mailto:jonathan@cheyer.biz]
Sent: Friday, February 10, 2006 12:40 AM
To: bootstrap-nsf@ws.blueoxen.net
Cc: NLS Restoration Technical Discussion
Subject: [bootstrap-nsf] Re: questions about Augment file structure (016)
Hi Jeff, (017)
I know you were one of the software architects during the NLS days. I'm
not sure when the Augment data structure was first designed, and how
much it changed over the years from its original implementation. (018)
Could you give me a brief history lesson on who did the original design
for the Augment data structure? Anything you remember about approximate
year and names of people involved would be very useful. (019)
(I do have some of the L10 code from within Augment itself and have
started looking through the code.) (020)
Among the documents I skimmed through from the CD that you gave me, I
came across a section that is entitled "AHI Data Structure, A.M. 276
Class Notes". It is about 20 pages long. No author and no date are
mentioned. Do you know what the A.M. initials are? I realize that AHI
stands for "Augmented Human Intellect" and was part of the AHIRC before
it was renamed ARC. That seems to suggest that this document was written
no later than 1968-9. According to this interview that Doug gave in
1987, AHIRC was renamed ARC at around that time.
http://www-sul.stanford.edu/depts/hasrg/histsci/ssvoral/engelbart/main3-ntb.
html (021)
If you know of any other technical documents that describe the data
structure, especially if they are later documents and the details have
changed, I would appreciate it if you could point me to them. (022)
Jonathan (023)
Eugene Eric Kim wrote:
> Doug and Jeff,
>
> Jon has been trying to decode the Augment file structure. He's gotten
> pretty far, but there are still some niggly baffling details. Is
> there someone we can talk to who can help explain some of the details
> without Jon having to reverse engineer everything himself?
>
> -Eugene
> (024)
--
This message is archived at: (025)
http://blueoxen.net/ws/bootstrap-nsf/forums/cgi-bin/mesg.cgi?a=bootstrap-nsf
&i=43EC5177.8010600@cheyer.biz (026)
_________________________________________________________________
Message Archives: http://chm.cim3.net/forum/nls-technical/
Shared Files: http://chm.cim3.net/file/work/project/nls-restore/
Community Portal: http://www.computerhistory.org/
To Post: mailto:nls-technical@chm.cim3.net
Community Wiki: http://chm.cim3.net/cgi-bin/wiki.pl?NLS_Restoration (027)
|