From BIT shifting to S,K,I re-writing (*)

From BIT shifting to the Combinatory Machine internals (or S,K,I graph re-writing)


After Essex University I went to St.Andrews for graduate studies and research in Mathematics. It took some time to settle in, Clifford Algebras was offered by Dr. John Amson but there was problem. Prof. Jack Cole gave me a chance to transfer to the Department of Computational Science, his research student L.Papantoniou that was testing the convergence of Turing machine and Markov Algorithms was a friend of mine and encouraged my move.

I started with the PAL manuals (Evans), the SECD machine (Landin) and the BCPL interperter of SASL that David Turner used to teach Denotational Semantics of Programming Languages. Officially I was under the instruction of Tony Davie who overtook the work left by Turner (he later wrote a book on Haskell). I ran by hand hundreds of lambda conversions and looked into parallel architectures like the Data Flow machine of Manchester.Steve Martin, a fellow student gave me his lecture notes from the Essex Comp.Sci. course so I can say that I almost completed the Computer Science B.A course at the University of Essex in spite enrolling for the 2nd and 3rd years to the B.A Mathematics.

I planned for a parallel SASL interpreter and take measurements on the factor of parallelism possessed by SASL programs.

As implementation platform I used the PDP-11/45 running UNIX edition 7 from AT&T. George Nelson's notes from a Bell lab's seminar helped me get started with trying to hack the OS scheduler written in C so that I could control the process execution profile.

"Oh no ! this is far too low level paralellism, you must play at the user data structure level of Turnerś ALGOL-S (R.Morrison turned it to S-ALGOL on the PDP-11), make a ring and give each virtual machine a tick at a time", this was Turner's advice. He wanted to find ways to optimize SASL for productive use. Reduce the massive spagetti of pointers (memory addresses) and exploit parallel execution. The latter was my task. He had just invented an alternative to SECD implementation based on Combinators of Haskell Curry (a Logic Theorist), a really ingenious programming idea (cannot call it hack) using Logic (see Dana Scott for proper analysis) as machine language ! all for the purpose of optimising pointers (variables needed memory slots that needed pointing). Turner used Combinators to do away with variables. At user level this meant a different style of programming. Well, Turner's mentor at Oxford was Strachey and his mentor was Turing.

Ronan Sleep at East Anglia, employed me as a research fellow, was interested in the R-N-Cube architecture executing SASL code. The SECD implementation was far too messy so I provided a run-time system in Pascal for him based on the C program of the Combinatory code at St.Andrews.

The environment of St.Andrews, very much influenced by David Turner's ideas, connected me with interesting concepts: C.Strachey's programme and D.Scott's mathematical foundation, Program transformation of Edinburgh and G.Steele's SCHEME and parallel garbage collection of LISP cells. Even a VLSI workshop with Conway's book to learn how transistors are printed over silicon layers. Compilers for Algol like languages and operating systems for small machines (e.g Cromenco) were all around me with students and lecturers talking at coffee time. Paul Maritz of Microsoft was next door struggling to implement S-Algol on 8088/86 board computer. From him I learned the idea of Mooreś Law "I learned hardware at Intel I came at St.Andyś to learn software¨. What an impressive statement at 1979 !!!. My goal was research to learn what is ¨programming language¨. I followed Turner's vision:

The big problem of the day was Software crisis and SASL should help to solve it because large numbers of processors had to be programmed and the cost of software had to be checked.

It seems looking back, the problem still is open but externalities kicked in, the free/open software armies emerged and Linus Law made "all bugs are shallow given enough eyeballs" provide the current solution.


(*) the title indicates that the computing model at Essex that I got familiar with as a computer science student, can be very compactly described by the notion of 'BIT' (Binary digIT). Many machine instructions (machine code) are implemented by literally shifting bits.
At St.Andrews (the next level of learning) had to do with a different computing model based on the idea of combinator, a basic construct that shifts symbols around like when passing parameters to a function or the emulation of recursion.

Both models originate in the attempt to mechanize mathematics in order to stable its foundations.