[SlugLUG] derivation of "{}" in C, Neliac

[Bruce R. Montague]

 Peter Belew noted:

> By the way, my impression for the reason that
> Kernighan and Ritchie established the 'religion'
> of putting opening brackets at the end of lines,...


Hum, an invitation to contribute to the heat-death
of the universe in regards to placement of "{"
style... forgive me for submitting a summary of
a small investigation into, among related things,
the early evolution of the use of braces in C.
There is an interesting UCSC connection.

In mainframe environments, each program that you
ran often had to be paid for; there were elaborate
accounting schemes that took program priority,
memory use, and I/O count into account. I/O was
expensive and often a single line of output (or
a card input) counted as 1 I/O, which encouraged
craming source into a single line to keep your
budget down (I had single program bugs which cost
hundreds of dollars).

BCPL did not use braces, it used "$(". BCPL was
based on CPL, and CPL used the "section sign"
(HTML "§") instead of braces, but used them
in pretty much the same way/styles as C uses braces
today. CPL was a "paper language", never actually
implemented. You can see CPL source in a number
of places, Scientific American, 25(3)112, 1966,
C.Strachey, "Systems Analysis and Programming"
and in probably the most important paper to
indirectly influence C, Cristopher Strachey's 1967
"Fundamental Concepts in Programming Languages"
(which defined concepts and things such as L-values
and R-values). "CPL"-appearing BCPL is shown in
"OS6 - An Experimental operating system for a
small computer", 1972, Stoy and Strachey (reprinted
in Per Brinch Hansen's year 2000 "Classic Operating
Systems" book). Strachey, BTW, patented the
multiprocessing OS, I believe in 1958, to preclude
commercial vendors from doing so, see "Time sharing
in large fast computers", Strachey, IFIPS, 1960.

 http://www.kluweronline.com/issuetoc.htm/1388-3690+13+1/2+2000
 http://citeseer.nj.nec.com/context/135189/0
 http://vmoc.museophile.com/pioneers/strachey.html


I once e-mailed Ritchie and Thompson a set of
questions that including specifically what influenced
their use of "{" and they both were kind enough
to reply. Some Neliac code that looked a lot like
C raised interesting questions about Neliac's
influence on C. Interesting in their response is
Ken Thomson's assertion that he combined BCPL with
"the feel of Neliac" to create B.

Neliac was likely the first widespread "real
open-source" self-compiling compiler. Neliac has
a connection to UCSC. Harry Huskey, founding
professor of the UCSC CS department, and Maurice
Halstead of NEL appear to have been the two
principal "architects" of Neliac. Under Huskey at
UC Berkeley, Niklaus Wirth of Pascal fame worked
on Neliac (in his Turing award lecture he says:
"The compiler, itself written in Neliac, was a
most intricate mess.") Ken Thompson also worked
on Neliac. A number of other influential CS people
worked on Neliac. Since Neliac was portable,
"open-source", and rather small, individual
programmers could implement/port it. It eventually
ran on over 18 different types of machines.

Among other accomplishments, Dr. Huskey designed
and built the first general purpose computer on
the west coast (the NBS SWAC at UCLA).

 http://www.ddj.com/documents/s=895/ddj9913i/9913i.htm

Below I have included extracts from Ritchie and
Thompson's take, I think it's a useful part of
the historical record; also below are a few
interesting notes comparing Neliac and C.


-----------------------------------
Dennis Ritchie:

...
I'm sure there was influence from NELIAC but in
my case it was somewhat subliminal, part of the
cultural background. I bought Halstead's book
and read it in early grad school (must have been
about '64, if I can believe a vague visual memory
of which apartment I read it in.) However, I
definitely never actually used the language or
the compiler--though I do remember being impressed
that much of the compiler source was printed in
the book. So my own imprinting on it was sort of
second-hand.

Ken probably had closer contact with it at Berkeley.
At some point (well in the past now) the subject
came up in conversation and he seemed pretty
familiar with it.

...
The {} question is interesting.  I don't remember
them from NELIAC, but just that Richards used $(
$) in BCPL, and I have just sort of assumed that
MR was working in a starting-to- convert-to ASCII
environment and that was what he had, while by
the time of B, the characters were there--though
on the Model 33 Teletype they had to be typed with
an escape sequence.

The deepest origin of C structure notation is
something I've never been able to reconstruct
properly. I added structures to our BCPL in the
Multics days, but have not saved any documentation
and precious few memories--I am reasonably sure
that they were described in PL/I notation, with
level numbers instead of grouped nesting.  I can't
even recall whether there was a bit-field notation
(or whether it was all bit-field notation). But,
of course, structures were another thing that was
already around (e.g. in COBOL).

Three arguably-new linguistic ideas in C are the

 . declaration-mimics-expression idea, combined with
 . array-decay, and
 . the generalized for statement.

The first two are controversial and not much copied
except in languages explicitly based on C. The
third is smaller as an invention, but is, I think,
a pleasing generalization.


-----------------------------------
Ken Thompson:

i programmed in neliac in the early 60's. the
brand of neliac that you describe is unfamiliar
to me. there were nothing resembling structures
and no conditional expressions.  i think the only
real similarity is the "non-numeric" feel with
nested (begin end) if-then-else statements. it
also had a shift operator (exp) that was used to
for and-or bit programming.

i "discovered" an early version of bcpl on mit's
ctss about 1967. i combined its good parts with
the feel of neliac to make B. dennis then permuted
B into C by adding types and structures. i am sure
that dennis was more influenced by pl/1 structures
than anything neliac had.
...

huskey was my advisor in college. neliac was in
full swing in 1962. wirth was a student just
finishing up. that was before ucsc was commissioned.
i never heard any single person credited for
neliac, but rather a whole string of students
having their hands in it. i could be wrong, thats
just what i remember.

...

-----------------------------------

Neliac appears to have been written in 6 months
in 1958 at the Naval Electronics Lab (NEL) to
support Polaris nuclear submarine operations. It
was then hacked extensively in a number of places,
including UCB. Neliac was used by the Navy at
least into the mid 70s. Neliac was intended to be
ported as hardware was upgraded, and was in fact
widely ported to different machine architectures.
A primary force behind Neliac was Maurice Halstead,
whose responsibilities at NEL included, I believe,
computation for weather prediction. Halstead's
office appears to have funded and managed the
original Neliac development.

Halstead wrote a book, "Machine-Independent Computer
Programming", Maurice Halstead, 1962, that explained
the langauge, and described a small portable
"bootstrap compiler" called b-Neliac (where the
"B" in BCPL comes from?). This book also contained
listings of complete compiler source for 4 different
machines. (These 4 Neliac compiler source listings
show both styles of "{" usage (one compiler, because
of char-set limitations, uses the keywords "LBR"
and "RBR"!)).

In Halstead's book he says "... the advice and
inspiration of Prof. Harry Huskey has been basic
to the entire development." The most direct
attribution regarding the design of Neliac of
which I am aware is due to Dr. Richard Thatcher
in "The NELIAC compiler language, CDC-1604 Version",
1960. In his credits he says "... and finally to
Dr. Huskey, whose basic ideas made up the original
NELIAC language in the first place." 




Points of interest when comparing C and Neliac:


----
* Ternary conditional operator syntax:

   b-Neliac:  conditional  :  true code ; false code ; 
   Neliac:    conditional  :  true code , false code , 
   BCPL:      conditional  -> true code , false code 
   C:         conditional  ?  true code : false code ;

Neliac had the ternary if that is in C, although
syntax apparently differed in different Neliacs.
A Neliac example _from 1960_:

 a > b : {b+5 -> i, a ->j}, a/2 -> b,

Neliac evaluated assignment from left to right so
"b+5->i" would be in C "i = b+5".


----
* The use of braces to delimit the body of a
subroutine. Layout is often as with C today.  Was
NELIAC the first to use "{...}" for subroutine
bodies?

A small 1-line example routine, named CLEAR, that
appears common in Neliac doc is the following,
which assigns 0 to a set of global variables:

 CLEAR: { 0->i->j->k->l->m->n },

(this is a routine, in C, "CLEAR()".


----
* C structures look a lot like Thatcher's 1963
Neliac manual example of "part location variables".
The following declares an array of 100 "structures":

    Neliac:

           AIRCRAFT: {
                       X(0->14),
                       Y(15->29),
                       HT(30->35),
                       STAT(36->38),
                       ID(39->41),
                       TN(42->47)
                     } (100),


    C:

        struct       {
                       int X:15,    // X-coord
                       int Y:15,    // Y-coord
                       int HT:6,    // height.
                       int STAT:3,  // Status.
                       int ID:3,    // Id.
                       int TN:6     // Track #.
        }  AIRCRAFT[100];


Both define an array of 100 structures. Each
structure contains 6 integer elements, X, Y, HT,
STAT, ID, TN, with the size of these integers
specified as bit-fields, that is, memory was so
expensive these integers are packed into the
minimal bits required. Of course, most Neliacs
probably could only use a single 48-bit word for
the entire "structure"...


----
* The comma sequence operator "is identical".
Comma was the standard statement seperator in
Neliac (in C, ";"). Comma expression seperators
are rarely used in C outside "for" statements
(although they can be). They appear to act identical
to Neliac, evaluating from left to right producing
a single result value corresponding to the rightmost
expression:

    b-neliac:   statement,  statement,   ...
    C:          expression, expression,  ...


----
* Some Neliacs used "==" as in C.

----
* Halstead inconsistently calls the b-NELIAC
compiler presented in his book both "Bootstrap"
and "Basic" NELIAC; the same confusion about the
"B" is present in BCPL...



-------

I don't think Thompson's recollection that structures
and conditionals didn't exist in the early 60's
is strictly true for all Neliac's, as both appear
in Halstead's book. However, Neliac syntax was
easy to change so one persons experience with
Neliac might be quite different than anothers...

The Neliac compilers appear to have been very easy
to "hack" to provide alternate experimental syntax.
Neliac did not use recursive descent parsing and
did not support a stack, precedence, or complex
expressions (in it's basic form it did not support
parenthetical expressions). A lot of early language
experimentation (such as exploration of precedence
parsing) appears to have been done with Neliac as
the vehicle.

Although Neliac is considered in "language
dictionaries" an Algol variant, a glance at Neliac
code or Neliac compiler source shows this just
isn't true in the sense we mean today (it was true
in the sense that you could write "arithmetic
expressions"). Neliac does not really use parsing
in the sense we do today. Neliac is more a machine
independent compile-in-place-and-go super assembler,
slightly context sensitive.

An interesting feature that Neliac had that modern
languages don't is that variables could contain
spaces. Halstead's 1962 book uses a lot of variables
with names like "Standard speed", "Temp corr
table", "Operand Buffer", and routine names like
"Compute speed at all points". A fragment of this
routine showing what Neliac looked like is (note the
loop does not need a "for" keyword):

 Nr of points,
 Sound Speed (100),
 Temperature (100),
 Salinity (100),
 Depth (100),
 Temp corr,
 Sal corr,
 Depth corr,
 Temp corr table (300),
 Sal corr table (20),
 Sal table base = 20,
 Standard speed = 1446,
 Depth corr const = 210;

Compute speed at all points:

  i = 1(1)Nr of points 
    {
      Temperature[i] -> j,
      Temp corr table[j] -> Temp corr,
      Depth[i]/Depth corr const -> Depth corr,
      Standard speed + Temp corr +
      Depth corr -> Sound speed[i]  }
..