Pete's Log: I like reading! part 7
Entry #1152, (Coding, Hacking, & CS stuff)(posted when I was 23 years old.)
A Model and Stack Implementation of Multiple Environments
by Daniel Bobrow, Ben Wegbreit, CACM, Oct. 1973
This paper rocked. I wish to read it a few more times (I've already read it twice). It kind of saddens me, though, that the Communications of the ACM used to publish stuff this cool. The communications of recent that I've looked at didn't seem interesting to me at all. So basically this paper addresses the problem of using a single LIFO stack for procedure linkage and such when an application may not access context frames in a LIFO manner, such as in a parallel processing environment where several procedures may be called at the same time.
The scheme introduced is fascinating. I think having read it, I have gained a greater understanding of various issues of runtime execution models in general, as well as a better understanding of some of the issues I had trouble with while taking Programming Languages. The model presented is useful for various things such as backtracking, coroutines, and parallel processing.
Basically what they do is use a data structure resembling a stack, but which is no longer strictly LIFO. Dynamic and static links are used for tracking the enclosing control and naming environments. Stack frames are divided into two parts, the part that holds local variables and the part that holds return address, links, and such. If control inside a frame is "split" (due to a fork or something) then the second part of the frame (return address, links, and such) is duplicated, but the first is not. Reference counts and such are maintained to keep track of when different frames are no longer in use. Since the stack is no longer LIFO (so it's no longer really a stack, though it behaves exactly like a stack if no parallel activity takes place) techniques such as compression and such need to be used ...
As far as implementation goes, the model seems designed for very dynamic languages, and seems intended to be implemented in an interpreter. So the actual model itself seems unfit to be adapted to our needs. But the ideas and issues presented in this paper are worthy of plenty of consideration when designing runtime models in the future.
From PLANNER to CONNIVER -- A genetic approach
by Sussman, McDermmott. AFIPS 1972 FJCC
This paper presents PLANNER and the problems inherent to it and then introduces CONNIVER as a solution to those problems. The main problem with PLANNER, they say, is that backtracking is generally a poor programming paradigm. Forall loops should be used instead. Kind of interesting, and definitely a good source if I ever need to argue that backtracking is bad. The real reason I read this paper is that the title it was cited as having was "Why conniving is better than planning" and with that kinda title, I couldn't resist...
Very Long Instruction Word Architectures and the ELI-512
by Joseph Fisher, 1983 ISCA
This paper wasn't too exciting. I just happened upon it while looking for something else, and I want to learn more about VLIW at some point, so I read it.
The work presented is definitely compiler intensive. It has an introduction to the use of trace scheduling to find parallelism that can be scheduled for VLIW machines. Comparison of VLIW with vector machines and other horizontal machines. Description of the Bulldog compiler for VLIW. Description of the ELI-512 architecture, which uses 512 bit instructions (f-in' huge! ELI = excessively long instruction). How to deal with jumps. How to deal with loop unrolling. etc.
Recursive Programming by E. W. Dijkstra, in Programming Systems and Languages, 1967
Wow. Dijkstra rules. This paper describes the use of a stack to implement recursive function calls. It describes static and dynamic links, and describes the use of this method in algol. Basically, this paper is the introduction of a technique that is now used everywhere. yay Dijkstra. I didn't really learn much from this, I just enjoyed reading it.
I think that's it for now, there's more that needs adding, but I'm taking a break.