From Tony Hoare to Graydon Hoare

1

Ever since I discovered Rust and that it was initiated by Graydon Hoare I have wondered if there was any relation to my hero Tony Hoare. I find no family relationship but today I find a curious conceptual connection.

In 1966 Tony wrote a paper called "RECORD HANDLING". In which he describes what sounds a lot like Rust's enums and match statements. He says:

In the real world, it is often useful to consider a class of object as being split into a number of mutually exclusive subclasses. For example, the class of algebraic expressions will include constants, variables, and dyadic expressions..

And gives as example (I assume pseudo code):

record class expression (
  subclasses
    constant (real value),
    variable (string printname),
    ...
);

And goes on to say:

...the programmer will usually at some stage wish to determine to which of the possible subclasses the record currently referenced by that variable actually belongs. This can be achieved by a construction known as a record class discriminator...

With example:

consider e when constant then ...
           when variable then ...
           when pair then ...

Saying:

Thus within each of the sections program, the variable e may safely be used in field designators for private fields of the relavent subclass, exactly as if it had been restricted by declaration to point only to records of that subclass.

Well, holy s**t, if that is not enum and match in Rust. It took forty years for this to get from Tony Hoare to Rust. And 54 years to get to me discovering Rust and immediately falling in love with enums and match!

Yeah, I know some will say such things existed in other languages along the way. I don't care, they were not main stream, at least not anywhere near my career path. Such ideas were rejected from C++ in favour of inheritance and virtual methods etc.

For anyone interested in such history I get all this from a recent presentation by Casey Muratori on YouTube: "The Big OOPS : Anatomy of a Thirty-five-year Mistake". Which has a lot of other gems in it. It's over two hours long! https://www.youtube.com/watch?v=wo84LFzx5nI

All this starts to explain why I was immediatley atracted to and comfortable with Rust, a feeling I had not had since starting out with ALGOL back in the day. A language that Tony Hoare had a lot to do with and had an emphasis on "doing the right thing".

5 Likes
2

No family relation.

2 Likes
3

I wasn't aware of that paper, thanks. I believe ALGOL 68 was the first reasonably widely-known language to feature discriminated unions. It never really became popular (probably due to its kitchen-sink complexity after the comparatively bare-bones ALGOL 60) but it certainly influenced many that came after it.

As an aside, it occurred to me that Graydon Hoare is a pretty gray name.

1 Like
4

It was either FORTRAN, BASIC or ALGOL 68 back in my Uni in 1976 on an ICL 2960 mainframe.

Like so:

NODE n := "1234";
 # or n := EMPTY; #
  CASE n IN
   (VOID):     print(("void:", "EMPTY")),
   (REAL r):   print(("real:", r)),
   (INT i):    print(("int:", i)),
   (COMPL c):  print(("compl:", c)),
   (STRING s): print(("string:", s))
   OUT         print(("?:", n))
 ESAC

To be honest I'm not sure I ever got that sophisticated in my ALGOL programming. I was supposed to be studying physics at the time...

2 Likes
5

Not in the language per say - but "tagged unions" are not uncommon in C.

6

Indeed. As a long time C user I am familiar with that. As you say not in the language as such. It lacks all the type checking goodness. None of the safety that Tony Hoare called for in his paper.

7

Seems to be a popular video - I watched it last night. Some people think about if they had a time machine whether they would kill Hitler or make money on the stock market - I think about what programming language features and other technology I come introduce earlier. Looking at what SketchPad was implemented on, I'm pretty sure I wouldn't want to try anything earlier than about 1970, when all the interesting stuff had already been done in one way or another :grinning_face_with_smiling_eyes:

Turns out most technology is really marketing, not brilliance.

1 Like
8

Except for monads and borrow checkers, you mean?

9

The notion of monad was invented by Roger Godement in 1958 under the name "standard construction".

From Wikipedia. But I'm not sure i would want to go down the pure FP route anyway, there's good stuff but it generally makes my head hurt when you get into the weeds. Trying to present Haskell as my own work would go very poorly, very quickly :grinning_face_with_smiling_eyes:

Borrow checking is a more squirrelly one - my understanding is there's a lot of linear type theory bubbling away in academic languages with several near-miss precedents for the current Rust borrow checker: I did a little bit of digging (Rust influences -> ml kit (a language nearly impossible to find now there's an Android machine learning library with that name) -> chasing some of the papers in there) and it seems that "region" based analysis for GC optimization was highly active in the 70s. Apparently nobody managed to both put together that it would be a good idea to just give an error and remove the GC and actually make that language and advertise it.

Certainly trying to make Dumb Rust would be the most fruitful approach I can think of, but I don't know if it would manage to take off at the time when garbage collection and FP and the precursors to OOP was all the craze in academia, and everyone was writing assembly in business.

3 Likes
10

I was wondering about that a while ago. Now I start to think that maybe a Rust without the borrow checker might have made for more memory misuse problems than say C.

Why? Because Rust is such a richer more complicated language it might make it harder for the programmer to keep track of memory use.

Still, I always wished C++ had adopted more Rust like type checking and such instead of faithfully maintaining all the problems of C.

1 Like
11

Yes, but the idea that the obscure concept from category theory could be applied in programming is from the late 80s, probably first explicitly formulated by Moggi in ’89.

12

I don't really know how long that path was, but the true story is even sadder. Sum types (that's what we are talking about here) were a part of mainstream languages. Absolutely. ALGOL 68 have them. And surprisingly, Pascal have them, too. And Pascal was pretty damn mainstream in the middle of 1980th: macOS classic is written in Pascal, first versions of Microsoft products are written in Pascal… that's as mainstream as one may imagine!

Yet that concept was deemed “too academic” by C developers and was “dropped on the floor” when they were adding features from ALGOL 68 to BCPL.

It took us few decades and billions spent on snake oil solutions (mostly OOP) to finally go back to what was invented decades ago.

And when people have become convinced that OOP is superior solution to the same problem (Java even had no C-style enums in the version 1.0 and emulated them with classes, remember?)… even Pascal got OOP and people have forgotten that it had the sum types from the day one.

Sum types, of course, survived in ML all that time, and that's who they survived to be resurrected in Rust: even ML got infected (and was tuned into Ocaml) – but in that world OOP have never become the dominant religion… sum types were remembered and used extensively there…

2 Likes
13

I think you could get a Dumb Borrow Checker in Rust 70 or earlier, it's a mostly local check so not that expensive compared to types. The main issue would be doing proper control flow analysis and generics to some extent to make it not suck, so I'm not sure how feasible those would be performance wise. Compilers of the day already took hours with garbage optimizers and no use before declaration!

The things I think you would have to kill are most trait stuff, global lookup and blanket implementations, maybe generics in general. It would be pretty rough to get rustc fast enough on CPUs measured in kHz with single cores, no pipelining or cache.

1 Like
14

You could get it in Rust 70… and then it would have been replaced with C, anyway.

When people talk about how we have spent 35 years for “useless regression”, they forget why that regression happened and thus don't disuss if it would have been unavoidable.

And it looks that, to a large degree, it would have be unavoidable.

Languages in the beginning of 1970th were, actually, more advanced than languages of 1980th, surprisingly enough. And they had to regress.

PDP-1 arrived in 1959 and Altair 8800 arrived in 1974… computer have become widely available – but they couldn't ever hope to run compiler for advanced languages like ALGOL 68 or Rust 70, even the very dumb one!

That is why language theory regressed so much: languages had to become extremely dumb to work in this super-constrained environment.

Maybe if some version of “Rust 70” would have existed in 1970th we wouldn't have spent so much time on OOP (extremely clever yet extremely dangerous hack that makes it possible to implement in 128K of RAM something that otherwise would have required megabytes) and skip the tracing GC craze entirely… hard to say.

But extreme regression of languages to the level of Forth and BASIC in 1980th was more or less unavoidable. Languages have started to become more capable and more expressive again after the point where “make computer even smaller and even cheaper to attract more buyers” stopped working… alas, by that time things that were explored in 1970th were mostly forgotten and for a long time computer languages practice and computer language theory existed in a parallel worlds with both sides mostly ignoring existence of the other side. Developers of the practically used systems went with C and numerous C descendants, while academic researchers were inventing new things (by mostly expnding on research done in 1970th)… but these new things were ignored by practical programmers…

1 Like
15

phew, thread's moving fast!

I think it's important to remember both FP and OOP came from academia - it's hardly surprising someone would merge them at some point (I think Common Lisp added something recognizable as modern OOP well before OCaml, right?)

Yeah, that's fair but in the thought experiment of in pretending I'm the smart person who thought of this, I'd have to either actually learn the maths so I could pretend I figured out how it applies, or pretend that I figured it out from scratch, call it something else (AI already stole "Transformers" at this point, right?), and talk to a bunch of academics about it.

Probably doable, but I'd be a lot more stressed than "just adding an error message" for borrow checking and programming like it's the 50s (with maybe better syntax) for performance that making a dumb Rust would be.

I don't think I could make anything more likely to be popular than any of the other languages that were far better than the mainstream, though, which is the real disappointing point. Really I think the trick would be beating K&R to the punch with a Unix and C and publishing it free (at least for academics), meaning I'm doing this in the 60s with terrible mini computers I have to negotiate time on rather than a "cheap" and crap micro. Then using those pseudo Unix and Cs as a Trojan Horse for better language features like a real type system, let alone a borrow checker!

Realistically, you would have to be stupidly lucky to even get in the right place to pull any of this off... but we do already have a time machine, so...!

Yeah, that!

1 Like
16

I would say most OOP practioners couldn't even imagine the concepts that CLOS was designed around.

Just read the name of them book that brought us Lisp-style OOP: The Art of the Metaobject Protocol… ask typical OOP-practioner “what is a metaobject” and he'll look on you like you are an alien with two heads.

17

Ha! Fair enough, I guess I was thinking "you could program it in a way that's recognizable as modern OOP" but I suppose that's true of most languages... for better or worse.

18

Thinking on the Casey Muratori presentation I linked to in the first post it realised that he was making a significantly different point about OOP than I have heard from him before.

Previously I had heard him bashing on C++ style OOP for performance reasons. How spreading data around in thousands of objects scattered throughout dynamically allocated memory was a performance hit on modern processors with their memory caches and such. He'd also mention how OOP modelling was likely not a good fit for all the entities in games. He is a game guy after all.

This time though he had a perhaps more serious theme. That we now have generations of programmers who can only think about programming in OOP terms. Classes, inheritance hierarchies etc. Because that is all they have ever been taught and all they ever see. That they are blind to other possibilities. That OOP actively blocks them from thinking about solutions to problems that may be simpler or realising there are solutions at all. That it limits the scope of problems they can tackle.

All of which sounds very profound.

I have no idea how true it is. But I do recall wanting to write parser for arithmetic expressions a few months into being introduced to programming with good old line numbered BASIC. I could not see how that was even possible. It became clearer to me when we were introduced to assembler later in that course. Had my programming education stoped at BASIC I would never have seen the solution.

1 Like
19

I've also asked Graydon directly on Mastodon and he confirmed the lack of familial relationship, though they did meet once iirc. I'm 99% sure his account there is private, otherwise I'd dig up the link to it.

20

The talk was way better than I expected!

I was prepared to roll my eyes at yet another ECS vs OOP rant and C++ bashing, but it's actually a lot of deeper analysis, well-researched historical background, and many interesting tidbits.

4 Likes