Friday, July 26, 2013

The Land of Trac

In the third grade, our teacher Mrs. Smithy read us The Lion, the Witch and the Wardrobe, the first of C.S. Lewis's Chronicles of Narnia, in which a group of kids find a secret door in the back of a wardrobe and enter a fantastical, undreamed-of world.

In the fifth grade, in 1968, I became part of a group of kids that had found such a door.  The group was called the RESISTORS, and the door led to the world of computers and what is now called "information technology."

The group met in the house and barn of Claude Kagan, an engineer at the Western Electric Research Center in Pennington, NJ, near Princeton, where I grew up.  Claude was a complicated guy, by turns fun-loving, cantankerous, generous, childish, and more—but unswerving in his commitment to value of letting young people learn things and above all do things.  The principles of the RESISTORS were "Hands On" and "Each One Teach One," and those principles have stood me in good stead for the last 45 years.  (As I side note, last night I read a piece by Atul Gawande in the New Yorker in which he wrote that an essential realization in the dissemination of the medical miracle of oral rehydration was that when teachers fanned out to villages, the teaching was much more effective if the villagers made the solution under the teacher's instruction than if the teacher "showed them how."  This was one of the first things we learned as RESISTORS: if you are teaching people things, THEY should sit at the Teletype [a primitive 100 bps terminal, which no self-respecting Bangladeshi villager would tolerate today] and YOU should sit next to them, talking them through it.)

We used a number of computers and computer languages, but the computational beating heart of the group was Claude's PDP-8 computer at Western Electric, which we would dial into from a Teletype in his house.  It ran Trac, a computer language designed by Calvin Mooers, an independent thinker based in Cambridge, Mass.  The PDP-8 had 4K of RAM.  Yes, 4K, i.e. one one-millionth of the amount of RAM in the two-pound MacBook I'm typing on right now.  RAM was insanely expensive because it was made of little magnetic "cores" which were hand-strung, reportedly by armies of Filipinos.  OK, actually it had 4K of 12-bit words, so technically you could say it had 6K bytes.  A "Trac processor" (interpreter) could fit on such a machine, with some room left over for user-written scripts (programs).  There is really no computer today so minuscule that Trac makes sense as a language, and even fewer people would ever have heard of Trac today if Ted Nelson hadn't happened upon the RESISTORS and mentioned Trac in Computer Lib.

Eventually we had our own PDP-8 in the barn, donated by the manufacturer, DEC (Digital Equipment Corporation).  For us, DEC was the Rebel Alliance to IBM's Empire, to use an anachronistic Star Wars metaphor.  This was before Microsoft managed to suck the life out of IBM, and that was before... oh well.  The PDP-8 was the size of a "small household refrigerator," maybe 3' x 3' x 4', and it cost around $10,000 1968 dollars, and to be on the safe side you should have four guys to carry it.  And your digital watch now has a more powerful computer.

Interestingly, the one aspect of my RESISTORS experience that has been a part of my life ever since is the importance of teaching.  Computers have been a part of my life to varying degrees since those days; recently I had another spate of exposure because I had to maintain and extend a Python program that my son Ben was good enough to write me for a book project I'm working on.  It's a great program, but Ben is a busy guy and couldn't be at my beck and call to get it all spiffy, so I learned Python (which I really enjoyed, partly due to Norm Matloff's Fast Lane to Python, a great way to get started if you already know some programming).

So I finished the book draft and, unusually, had some free time while I wait for comments to come back.  Somehow I ran across Jack Trainor's partial Trac implementation in Python.  He followed Mooers' original instructions, which were designed to be implemented in assembly language, which is "goto-ful."  It looks like quite a torturous experience to try to implement them in the modern "goto-less" style, but he did it.  At the end of his post, he says "It would be interesting to rewrite this interpreter with modern techniques and to implement the rest of the primitives, as well as to set up TRAC to run interactively." Apparently I decided that's what I should do.  I didn't notice that he had in fact made (two) other implementations with more modern techniques, but oh well... and they weren't full implementations, and they weren't interactive.

I got the basics going in a weekend, but implementing the full language involved some very fussy stuff with the "form pointer," some Trac features I'd never used (the boolean primitives), and one I'd never even heard of (the IN primitive).  But after about 10 days, I wound up with what I believe is a full implementation of Mooers' "T-64" standard.  Programming in a modern high-level language, especially Python, is really quite a breeze.  Fellow RESISTOR and actual übergeek John Levine said (in an unguarded moment), "I have to say, it looks pretty good," which, if I recall correctly, is pretty much what he said when he read James Joyce's Ulysses, and which in any case is certainly the high-water mark for my programming chops.  Ben encouraged me to post it on GitHub, and (in the somewhat bizarre event that you care) you can download it from there without signing up just by hitting the "Download ZIP" button.  The README has a link to the language description and a Trac manual.

At some point, I thought, "My God, what am I doing...  I'm like a crazy middle-aged guy spending all his time in the garage restoring a Yugo to pristine condition because the first car he ever owned was a Yugo, even though his original one was always kind of a junker..."

But I started to think about the fact that my interpreter made essential use of recursion and the associated stack.  Somehow, the Mooers algorithm did all that without a stack.  Eventually I realized that the "neutral string," consisting of already-processed characters, essentially encodes the stack—it's an incredibly economical way to implement recursion.

My grandmother was born in the early 1890s and told me that she learned to drive on a "one-cylinder REO."  So after realizing how ingenious Mooers' Trac design was, I think of myself as the obsessive middle-aged guy in the garage restoring the 1906 REO, not the Yugo guy.  For whatever that's worth...

4 comments:

  1. Nice work! It must have been great to be one of the RESISTORs.

    ReplyDelete
  2. Because I followed the instructions for installation of Python 27 in a Windows env't, I was able to copy "trac.py" into the "Lib" folder under c:\python27\, and when I right-clicked on "trac.py" the Python window opened with the Trac prompt displayed. I also copied the file, "fact.trac" into the "c:\python27\lib" folder and it was findable when I entered "#(fb,fact.trac)" at the TRAC prompt. I then calulated factorials up to about 980 before I got an overflow message. That's pretty impressive capacity - and very fast!

    Great work, Nat! I've been hankering for a TRAC processor to fool around with for years! I'll be putting it through some more rigorous paces when I get home this evening.
    Andrew Walker

    ReplyDelete
  3. Thanks Andrew! I know that under OS X I could do 500! but not 1000!; if you want higher factorials, it should be possible to increase the Python recursion depth, I think.

    ReplyDelete