Hi Jeff, (01)
This is some very interesting information. Thanks for relating it to me. (02)
A few notes to myself and others, to track historical context: (03)
* CDC 3300, released June 1963. 24 bit words (four 6 bit characters).
Used core memory. Built by Control Data Corporation. (04)
* SDS 940, released April 1966. 24 bit words. Included Project Genie,
a timesharing system on which Tenex (later TOPS-20) was based on. Built
by Scientific Data Systems, with help from UC Berkeley and Tymshare. (05)
* XDS 940 - Xerox bought the SDS 940 in 1968, renamed it XDS 940. (06)
Links used to obtain info:
http://landru.myhome.net/jtrees/sortedcmplist.htm
http://simh.trailing-edge.com/sds940.html
http://foldoc.org/foldoc.cgi?XDS+940
http://en.wikipedia.org/wiki/CDC_3000 (07)
Jeff, a few questions are inline. (08)
Thanks, (09)
Jonathan (010)
Jeff Rulifson wrote:
> I did all the design for the data structures for the CDC 3300 and the
> SDS940. The 940 is the one of most interest. (011)
I assume that your initial work would have been sometime between 1963
and 1968? It would be great if you could pin down some years for me. (012)
Was the CDC 3300 the first machine that NLS ran on? (013)
> 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. (014)
ok. (015)
>>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. (016)
I think this has remained true even on the latest version of Augment
that Doug is still running, yes? (017)
> Think of the statements as the CAR of a Lisp list CONS. CDRs in the same
> page displayed faster. (018)
Makes sense. (019)
> 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. (020)
I'm not sure what attribute-value pair you are referring to. I
understand that statements are just a string of words that must be less
than a single page. More clarification on the pairs? (021)
I'm also not clear on what is stored in 19 bits? Is there a 5 bit header
with 19 bits of data (5 + 19 = 24 bit words, used by the SDS 940)? (022)
> An NSL statement had a fixed length header and a variable length string. (023)
I think this has remained true, yes? (024)
> 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. (025)
Makes sense. (026)
> 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. (027)
I noticed when looking through the L10 code from Doug's version of
Augment, that the initials are now allowed to be up to seven characters
(packed into a PDP-10 36 bit word). It seems to use a 5-bit character
set (7 * 5 = 35 with one unused bit), with only the following characters
supported:
" ABCDEFGHIJKLMNOPQRSTUVWXYZ23456". (no number 1.) This is pretty
interesting. (028)
> 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. (029)
I guess the Meta Compiler and compiler were all rewritten from SNOBOL to
use L10 at some point, once L10 itself was written? (030)
Did this occur during the transition from the SDS 940 to the PDP-10? (031)
> So, statement names were "(" $(L/D) ")" at the start of a statement. View
> specification control was "[" name ":" flags "]" in the string. (032)
I'm reasonably comfortable with LISP, but I'm afraid I don't know any
SNOBOL. I assume the L and D represent some kind of string processing
functions? (033)
> 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. (034)
That's pretty cool. (035)
> 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. (036)
Interesting. (037)
> 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. (038)
I guess we take a lot of this for granted nowadays. With built-in hash
algorithms and a fast machine, it matters less if we have collisions.
This is a good image of all the work that you had to do back then. (039)
Thanks again for the info. (040)
_________________________________________________________________
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 (041)
|