4 ms·
An architecture for mostly functional languages (1986) [pdf]
- therealcamino 4y agoI 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.
- bob1029 4y agoIsn'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.
- moonchild 4y agoOoo is tomasulo's algorithm, 2 decades before this paper :) - https://en.wikipedia.org/wiki/Tomasulo%27s_algorithm https://en.wikipedia.org/wiki/Tomasulo%27s_algorithm
- pdw 4y agoOut-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".
- steinuil 4y ago> 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.
- kjs3 4y agoIt was the DG Eclipse MV/8000. There's a pretty good overview/references at https://people.cs.clemson.edu/~mark/330/eagle.html 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.
- cafard 4y agoMany thanks for the links!
- auggierose 4y agoNo need for wayback: https://dl.acm.org/doi/pdf/10.1145/319838.319854 https://dl.acm.org/doi/pdf/10.1145/319838.319854
- dang 4y agoChanged from https://web.archive.org/web/20131101085557/http://web.mit.edu/mmt/Public/Knight86.pdf https://web.archive.org/web/20131101085557/http://web.mit.ed.... Thanks!
- Athas 4y agoThis 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.