13

According to a 2019 presentation about Burroughs Extended Algol, the Burroughs B5000 and B5500 (and presumably their descendants) had “Hardware support for Call-by-Name (‘thunks’)”. It goes on to say that

One of the most challenging features of Algol-60 was its call-by-name semantics, which required dynamic evaluation of expressions passed as procedure parameters each time they were referenced. The B5000 included hardware features to make this efficient and easy to implement in compilers.

I understand that the presentation is not implying that the computer actually performed the textual substitution described in the Algol report, but rather that some feature(s) of the computer facilitated implementing an equivalent operation. What were these features?

5
  • 3
    From vague memory (and bitsavers.org seems to be down right now), there was a form of operand descriptor that resulted in a call to the thunk routine when the operand was pushed. But I could be wrong here. – another-dave May 15 at 21:52
  • 3
    I don't think this deserves to be called an answer, but I presume that you have reviewed Waychoff's document at archive.computerhistory.org/resources/text/Knuth_Don_X4100/… and the developers' oral history session. – Mark Morgan Lloyd May 16 at 21:22
  • 1
    @MarkMorganLloyd I had read Waychoff's document (which doesn't mention call-by-name, as far as I can tell), but the oral history completely slipped my mind. And it was a good lead (thanks): Starting on page 60 there is discussion of the origin of the machine's call-by-name support. – texdr.aft May 16 at 21:32
  • @MarkMorganLloyd But I already have enough to read. How can I ever get anything done. – David Tonhofer May 16 at 22:31
  • 1
    @texdr.aft I remember when the Waychoff document came out, and for many years disparaged it as being written by a company man for company men. However I've come to believe that if one reads between the lines there are some gems in there... I just wished there was more detail on Knuth's "Half-true" annotation. – Mark Morgan Lloyd May 17 at 6:08
7

Based on a reading of a document titled Operational Characteristics of the processors for the Burroughs B5000, and applying a lot of interpretation, it appears that thunks are compiled in a fairly normal way.

The called procedure executes either an "Operand Call" or an "Descriptor Call" operator (B5000-ish for "instruction") in order to evaluate a parameter. The call references a Program Descriptor in the Program Reference Table -- this is the normal sort of "code pointer" in the B5000. Subroutine-entry preamble is executed, and the thunk is entered.

In general, Operand Call syllables are used to enter a subroutine and obtain an operand, which Descriptor Call syllables are used to enter a subroutine to obtain an address.

(page 3-4, "Subroutine Entry")

(Editorial) I find the description fairly opaque, in that it's written in terms of setting flip-flops and moving registers, and it's hard for me to discern the logical intent behind it. And again, the unusual (for me) division between operation and data -- one operation code, what it does depends on the type of descriptor -- does not make it any easier.

To summarize, I'd say that what's special here is that the instruction sequence of a procedure contains a generalized "get me an operand value" or "get me an operand address" instruction. The instruction refers to a descriptor which then determines whether it's a simple fetch of a value, possibly indirect, or a full thunk call.

(The author of this answer has no experience with B5000 systems beyond reading about them on the internet).

7
  • 1
    I also took the question as an opportunity to read up details on the B5000, and what I don't understand is how the "frame" (F register) would get set for thunks - I can't see anything in the ISA that would have supported that (as "advertised"). In addition, passing around thunks to other procedures with call-by-name can get interesting without a full closure (and I don't even know if they implemented it properly). I gave the emulator a spin to have a look at the compiled code, but I didn't work for me. Maybe it does for somebody else. – dirkt May 16 at 18:53
  • 1
    @texdr.aft yes, both operand calls and descriptor calls can be used on (a) program ("code") descriptors, (b) data descriptors, (c) operands, (d) control words. The docs describe in detail what happens. – dirkt May 16 at 18:55
  • 1
    "it's hard for me to discern the logical intent behind it." A/M/G/H point to the top of stack, B/S/K/V to the word below. Both have a "presence" flag for automatic spill/reload. The "mark stack flip flop" toggles between normal mode and setting up a call frame. "Control words" are the links (they contain registers) in the call frame. In "subroutine mode" (another flipflop), there are more ways to address stack/frame relative arguments (but less range for the offset) beyond R-relative PRT entries. – dirkt May 16 at 19:00
  • 1
    @dirkt = Most of that I got, or at least enough of it, but the "big picture" still feels very foreign - e.g., there's an actual machine state that is for setting up a call frame (rather than, say, different instructions). That is, I have to work at it, rather than thinking it's obvious. But that of course is the benefit of looking at what now looks like an exotic architecture. – another-dave May 16 at 19:31
  • 1
    If you've seen UCSD p-code, it's not that different, except it's done in hardware, and it's missing the "go up n static/dynamic frames" access for nested procedures, which would be useful for thunks. Yes, the MSFF to "re-use" the desc/op calls for pushing parameters is surprising; OTOH that's were at least part of the secret sauce for the thunk handling is. – dirkt May 16 at 19:46
4

Purely from the first principles, given that Burroughs was a tagged architecture, it would be logical to pass arguments by name by setting the corresponding formal parameter to either the address of the actual parameter if it was an l-value (assignable) with one tag, or the address of the thunk computing the actual parameter expression with another tag, and, if the tag was of the latter kind, to make the indirect load instruction perform an indirect function call instead, and the indirect write instruction - to trap.

3

Partial answer:

The only three features I have found in the ISA so far that I think can help with call-by-name are the following:

a) As call-by-name can be used both for an assignment ("l-value" in C terms) and in an expression ("r-value"), normally you'd need two thunks for it (one to return the address as l-value, one to return the value, as returning an address may be impossible depending on the thunkified expression, and one cannot recover the address from the value). The ISA handles this by having "operand calls" for r-values and "descriptor calls" for l-values, and when a procedure is called either way, this information is stored on the stack. So the same thunk can either return an address or a value.

b) Accessing a program ("code") descriptor works differently during "normal" expression evaluation and making calls, so thunks could be potentially handled here (but I don't understand the full mechanism, see below).

c) There is a "return special" operator (opcode) which is based on the stack pointer S instead of the frame pointer F. The thunk needs to execute with reference to the frame of the calling procedure, and then it also needs to unwind the stack based on this, so potentially this operator could be used to return from a thunk.

But I have not seen how thunks are set up so they refer to the correct frame. Also, this can get nasty when having chains of procedure calls with call-by-name, unless you do a full closure and pass along the frame reference as additional parameter. But that would defy the "have hardware support for thunks" advertisement.

I tried to use the emulator in a browser to get an ALGOL program to compile and inspect the resulting code, but it doesn't work for me no matter which browser I tried. Also, it looks like inspecting the compiled code is not going to be easy, probably it needs to be dumped to "tape" or another emulated device. Maybe somebody else has more luck with that.

4
  • 2
    I managed to get it to work. There is a compiler option to list the object code (DEBUGN on a dollar sign card), and I've saved the input/output for a run on GitHub. There's a lot of garbage along with the machine code. – texdr.aft May 16 at 20:27
  • Also, note that B5000/B5500 Algol forbid accessing nonlocal quantities (except for global variables) in blocks. (See pages 31 and 32 in the presentation linked in my question.) I'm not sure whether this is relevant. – texdr.aft May 16 at 20:55
  • Right - it wasn't until the B6500 that they had display hardware (based on Randell & Russell's description of their compiler) for uplevel references. – another-dave May 16 at 21:13
  • @dirkt If you have problems with the compiler please go into more detail for discussion. It certainly works for me, although I'm not using Paul Kimpel's emulator. – Mark Morgan Lloyd May 16 at 21:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.