An architecture for mostly functional languages (1986) [pdf] | Hacker News Reader

An architecture for mostly functional languages (1986) [pdf]

dl.acm.org

64 pointsluu14 comments

This part (which is tangential to the real thesis of the paper) is interesting:

> Advocates of strong type checking in compiled languages have attempted for years to build compilers capable of proving the type correctness of programs. We believe that they have failed. All languages sophisticated enough for serious programming require at least some dynamic checks for type safety at execution time.

In 1986, languages such as Miranda and ML existed in reasonably serious forms, and clearly had sound type type checkers and quite powerful type systems, including parametric polymorphism. Does the paper take the stronger position of counting things like array indexing as part of "proving type safety", or was there still a conception in 1986 that "serious programming" could not be done in a type-safe manner?

It is definitely true that even in 2022, the vast majority of statically typed languages still perform run-time safety checks for some operations, such as integer division and array indexing. While languages that support fully provably safe programming exists, they are clearly in the tiny minority and not widely used, and still have ergonomic problems.

He might have considered pattern matching a form of runtime type checking.

ML still needs runtime type checks due to references

How so? References are not polymorphic in SML (that's what the value restriction ensures).

You're right, I misremembered, it was for equality instead.

Isn't this what modern CPUs are effectively doing with out-of-order execution and pipelining?

Seems like this paper may have been an important precursor to that line of thinking.

Ooo is tomasulo's algorithm, 2 decades before this paper :) - https://en.wikipedia.org/wiki/Tomasulo%27s_algorithm

Out-of-order execution and pipelining date back to the 1960s. The paper calls out the similarity: "If one views the blocks of this scheme as very complex instructions, then this architecture devolves to a pipelined architecture for executing those instruction, and the interlocks to prevent inter-instruction dependency violations."

In the late 1980s it was a common belief that the limit of single-core CPU performance was very near. So there was intense research into multi-core systems, the holy grail was to find a way to efficiently execute ordinary sequential programs. That was what this paper was trying to achieve: "While we currently believe that this work will lead to an architecture which can achieve factors of 10-100 times the performance of uniprocessors on unmodified Lisp programs, we have no proof, even in simulation".

> Out-of-order execution and pipelining date back to the 1960s.

On that note: I read The Soul of a New Machine a while ago, which is about a team of engineers designing a computer with a new architecture at the end of the 70s, and while it didn't go into the specifics of how the CPU was implemented it mentioned features such as different layers of cache between the CPU and the RAM, out-of-order execution, instruction prefetching and branch prediction. You'd be surprised at how many things in computers have already been around since the 60s.

It was the DG Eclipse MV/8000. There's a pretty good overview/references at https://people.cs.clemson.edu/~mark/330/eagle.html. There is little new under the sun, and I get a migraine from the reflexive eye-roll when I read about some 'totally new and original innovation' in computers that's actually been around for decades, usually touted by people who weren't even alive when it was first created.

Many thanks for the links!

I only skimmed this paper, but the use of caches to check correct parallel execution reminds me of the hardware-aided transactional memory features of the Sun Rock processor.

No need for wayback: https://dl.acm.org/doi/pdf/10.1145/319838.319854

Changed from https://web.archive.org/web/20131101085557/http://web.mit.ed.... Thanks!

Reply on news.ycombinator.com