Software Development: the Secret of Success

Recently I revealed the secret of academic success . This was so popular (16000 views!) that I decided I would follow up with the secret of software success – success in producing software.

Not that I’ve always been that successful – but the secrets are mainly avoiding the mistakes I made.

Griff

When I was 19 I had a reasonably good idea one summer. Reasonably good. Not brilliant. Needed work (though I didn’t realize it at the time).

Anyway the idea was a character/string based macro processor (which for reasons I’ve forgotten I called “Griff”). A Griff macro call was the $ symbol followed by characters; it evaluated the longest initial segment of the input that had an entry in the macro table.

For example suppose the working string (the string being evaluated) is

$Et&f+t&t;

and the macro table has rules

$Et&f –> f

$Et&f+ –>$E

Then one step of the evaluation reduces the working string to

$Et&t;

Obviously the $E macros (I won’t give them all) are for evaluating boolean expressions. I wanted to give you an idea of the complexity of the macro processor. The main complication is that it needed nested strings – strings where a character can be a whole subtring.

By the end of summer I had most of the ideas worked out and wisely decided that the first step was to tell people about it.

When I got to Berkeley (as a grad student) I told my my advisor, who we agreed didn’t know much about practical computing, and he sent me to the professor (in the math department) who taught numerical analysis. He listened and said that in his opinion this was “all known” (I knew better). But he sent me in turn to a new young professor in engineering who was interested in computers. Off I went.

The GENIE project

The professor was Butler Lampson . I couldn’t have done better.

Butler Lampson listened to me very respectfully and asked me to produce a short writeup of my ideas. He thought Griff was at least promising (certainly not “known”) and introduced me to other members of their GENIE project. Among these was a certain grad student named L. Peter Deutsch .

Their project involved designing and implementing a (pioneering) time sharing system on the SDS 940, which was designed for this purpose. It could handle up to 40 simultaneous users and offered FORTRAN IV, Basic, and … LISP.

Peter Deutch was a phenomenon.  He could sit down and type in LISP at top speed, dozens of balanced parentheses, then it all worked.

They gave me an account on their machine and introduced me to LISP, which I quickly learned. I loved recursion and hierarchical data, which  Griff also had. LISP and Griff seemed ideally matched so I set out implementing Griff in LISP.

At first it went well. I quickly had the binary expression evaluator macros working. Soon, however, it dawned on me that I had a problem. The Griff interpreter was very, very slow.

Hardly suprising, really. On the one hand, you had two layers of interpretation – one for Griff, one for LISP (they didn’t have a LISP compiler). On the other hand, the SDS machine was absurdly underpowered by modern standards. For example, it had 64K of 24 bit memory. That’s not a misprint; 64k !

It soon became apparent that the only hope for a useful Griff implementation was an assembly language program. That was beyond my skill set. But one day I came in and Peter Deutsch showed me a printout of several pages of assembly. He’d started to implement Griff himself but had run out of steam.

I think I know why. On the surface evaluating Griff seems straight forward, matching strings and copying. But you have to have patterns that match (the one pseudo character) substrings. And there’s two ways to match. One way is to match an arbitrary substring.  The other is to match only one specific substring. The result is situations in which more than one match is possible.

It soon becomes apparent that the more specific match has priority. But with multiple substrings and sub-substrings you can get a partial order of matches and you have to determine the ‘best fit’. If it exists. I rediscovered this phenomenon in connection with parametrized versioning and it was challenging. There’s no easy solution.

By then I was making good progress on my PhD work (what became the “Wadge degrees”) and I gave up on doing Griff on  top of LISP.  Which seemed like wise choice at the time.

I also stopped visiting the GENIE project, which was really unfortunate. They were brilliant and going places – literally. A couple of years later Butler Lampson and Peter Deutsch ended up across the bay in Xeros Parc, Palo Alto, where they helped invent the technology (e.g. ethernet, laser printer, personal workstation) we still use today. Damn.

The great Canadian program

However my luck held out. I’d previously spent a summer at the UBC computer center where I had an IBM ‘scholarship’ that allowed me a whole summer of playing with the computer and learning a lot.

Al Fowler (my mentor) at the UBC computer center agreed to hire me for the summer and was fine with me working on Griff.

So I arrive at UBC and set to work. I decided to implement Griff in assembler – IBM  7040 assembler (the 7040 was, I believe, the only computer on campus at the time). The alternative was to use FORTRAN IV, which did not have recursion.

Really what I should have done first was to produce a report describing Griff, giving examples, plus an implementation strategy.

Instead, I decided not to tell anyone about what I was doing till it was ready. That was crazy because we had a community of bright summer students. We all got along great, hung out together, and were very close. But when anyone asked me what I was doing, I said I was writing “the great Canadian program”.

By the end of the summer I had a long extremely clever 7040 assembler program. Extremely clever, boy it ran fast. But not finished. I couldn’t evaluate even simple Griff rule sets.

Al and I sometime later discussed my experience and concluded that I should have written the first implementation of Griff in FORTRAN after all. Copying strings like mad and using simple minded matching algorithms. Producing something I could experiment with, and something others could use, even if it was slow. FORTRAN was compiled and the 7040 was a powerful machine – it had an incredible 250k of memory.

That was basically the end of Griff. To this day I haven’t implemented it and don’t know if it would have been useful.

Lucid

Fortunately when I was 28 I (and Ed Ashcroft) had another good idea. Maybe brilliant, I’ll let you be the judge. Briefly, the idea was to make a program be a set of equations defining the flow of streams through a network.

However this time I didn’t rush to implement, thanks mainly to the influence of Ed Ashcroft. In retrospect Ed’s first impulse when he had an idea was to document, not implement. We produced a series of widely read papers and soon had other researchers and brilliant students of our own working on it.

At Warwick in the UK David May (then a colleague’s grad student) produced the first Lucid interpreter – lazy (demand driven) and fully correct. Then at Waterloo Ed’s students Tom Cargill and Calvin Ostrum followed. Ostrum’s was the most complete and development was taken over by Tony Faustini, who had been my first PhD student. Faustini added error handling, storage management, sophisticated I/O and a UNIX escape. S. Matthews and A. Yaghi wrote an excellent user manual and the resulting “pLucid” interpreter was widely circulated.

There’s one person missing from this list – a certain Bill Wadge. I helped design pLucid but (wisely) didn’t write a line of code. By then I’d learned the what I thought at the time was most important secret of software success:

get help from people who know what they’re doing

Where is the pLucid interpreter now? Unfortunately it was written in a more carefree age, when C compilers were very tolerant. Today, if you try to compile the pLucid source, you get a warning or an error about every 10 lines. There’s a secret in there somewhere.  In fact it’s

write for the future .

Epilogue

In the end I couldn’t resist the urge to code myself. I started working on an elaborate plan for a multi purpose Lucid implementation in C. Everything would be reusable and there were strict levels of abstraction. I was writing for the future and I got help from a student named Martin Davis, who definitely knew what he was doing.

In the end it finally dawned on me that I would never solve the memory management problem (C having no garbage collector). I dropped what I called the “popshop”. (So called because the data types and operations are those of POP-2, a now dead LISP-like language developed at Edinburgh.)

Many years later (i.e. recently) I learned Python and re-evaluated the popshop. For a start, Python has garbage collection, so that solves memory management. Also, it has essentially all the data types of POP-2. Furthermore it has functions as first class objects, whereas C has only function pointers. Python’s dictionaries are perfect for e.g. the evaluator’s cache. Finally, and this seems a small point but isn’t, functions can return multiple values.

I decided that reviving the popshop in Python was feasible and set to work. Well, I finally have a success to report because within a few weeks it wasdone (you can find it on Github).

The secret

In retrospect I think that write for the future is the real secret of software success. For example, take the decision to drop the development of the LISP implementation of Griff.

It seemed like a wise decision at the time. Who needed an impossibly slow Griff interpreter? But suppose I’d persisted and produced an (admittedly useless) Griff interpretation. Modern LISP implementations are a million times faster than the old SDS 940 interpreter. I’d have a usable Griff implementation today, and in fact would have had one only a short time after the original effort.

Clearly write for the future applies not only to software. It applies also to documentation, which almost by definition is produced for future use. In fact you can generalize it even more to the secret of engineering success,

Build for the future

And one instance comes to mind: if our healthcare systems had been built for the future, we might not be in the current coronavirus mess.