[COFF] Re: ancient macros, machine code translation,as mental architecture models

[COFF] Re: ancient macros, machine code translation,as mental architecture models

[Douglas McIlroy]

[-- Attachment #1: Type: text/plain, Size: 1534 bytes --]

In 1959, when Doug Eastwood and I,  at the suggestion  of George Mealy, set
out to add macro capability to SAP (Share assembly program), the word
"macro"--short for "macroinstruction"--was in the air, though none of us
had ever seen a macroprocessor. We were particularly aware that GE had a
macro-capable assembler. I still don't know where or when the term was
coined. Does anybody know?

We never considered anything but recursive expansion, where macro
definitions can contain macro calls; thus the TX-0 model comes as quite a
surprise. We kept a modest stack of the state of each active macro
expansion. We certainly did not foresee that within a few years some
applications would need a 70-level stack!

General stack-based programming was not common practice (and the term
"stack" did not yet exist). This caused disaster the first time we wrote a
macro that generated a macro definition, because a data-packing subroutine
with remembered state, which was used during both definition and expansion,
was not reentrant. To overcome the bug we had in effect to introduce
another small  stack to keep the two uses out of each other's way. Luckily
there were no more collisions between expansion and definition. Moreover,
this stack needed to hold only one suspended state because expansion could
trigger definition but not vice versa.

Interestingly, the problem in the previous paragraph is still with us 65
years later in many programming languages. To handle it gracefully, one
needs coroutines or higher-order functions.

Doug

[-- Attachment #2: Type: text/html, Size: 1729 bytes --]

[COFF] Re: ancient macros, machine code translation,as mental architecture models

[Paul Winalski]

[-- Attachment #1: Type: text/plain, Size: 1311 bytes --]

On Mon, Jul 15, 2024 at 8:46 AM Douglas McIlroy <
douglas.mcilroy@dartmouth.edu> wrote:

>
> We never considered anything but recursive expansion, where macro
> definitions can contain macro calls; thus the TX-0 model comes as quite a
> surprise. We kept a modest stack of the state of each active macro
> expansion. We certainly did not foresee that within a few years some
> applications would need a 70-level stack!
>
> As I mentioned in a previous reply, BLISS has a very powerful and
extensive macro facility.  This led to an obscure and difficult to fix
parser bug.

The outermost organizational unit of a BLISS program is the module.  All
declarations, routines, identifiers, etc. have a syntactic scope limited to
the module in which they occur.  Modules are delimited by the keywords
MODULE and ELUOM (module spelt backwards).

The bug was triggered by a call to a macro that included an ELUDOM followed
by a new MODULE declaration.  When the parser saw the ELUDOM it threw away
all of the context for the current module, including the parser context for
the macro that was being processed.  The parser blew its brains out and the
compilation terminated with an internal compiler error.

-Paul W.

P. S. - I once remarked that in BLISS we don't solve problems, we ELUDOM.

[-- Attachment #2: Type: text/html, Size: 1727 bytes --]

[COFF] Re: ancient macros, machine code translation,as mental architecture models

[Bakul Shah via COFF]

On Jul 15, 2024, at 7:26 AM, Paul Winalski <paul.winalski@gmail.com> wrote:
> 
> Modules are delimited by the keywords MODULE and ELUOM (module spelt backwards)

I wonder who was the person who came up with the idea of reversing the beginning keyword to end the corresponding block in Algol68.

[COFF] Re: ancient macros, machine code translation,as mental architecture models

[John Levine]

It appears that Douglas McIlroy <douglas.mcilroy@dartmouth.edu> said:
>In 1959, ...

>We never considered anything but recursive expansion, where macro
>definitions can contain macro calls; thus the TX-0 model comes as quite a
>surprise. We kept a modest stack of the state of each active macro
>expansion. We certainly did not foresee that within a few years some
>applications would need a 70-level stack!

As the PDP-1 Macro imeplementation manual said about the macro feature:

   It is the weakest
  in that it is quite inflexible and does not incorporate any of the more significant improvements
  in assembler technology that have occurred since the logic was first written in 1957.

The PDP-1 was not a very big machine, only 4K words and the only
standard I/O device was paper tape, so no overlays or multiple passes.
I can imagine that while they knew how to write a better macro
processor, they didn't want to use up the memory it would have needed.

Bitsavers has a bunch of memos about the TX-0.

Memo 39 describes TX-0 assembler as of 1962, which had real macros
that could insert arbitrary strings, as they show in an example on
pages 10-11.

https://bitsavers.org/pdf/mit/tx-0/memos/M-5001-39_MIDAS_Nov62.pdf

There are earlier memos about MACRO in 1959 and 1961 which suggest a weaker
macro facility but don't have details.

R's,
John

[COFF] Re: ancient macros, machine code translation,as mental architecture models

[Aron Insinga]

On 7/15/24 15:39, John Levine wrote:
> It appears that Douglas McIlroy <douglas.mcilroy@dartmouth.edu> said:
>> In 1959, ...
>> We never considered anything but recursive expansion, where macro
>> definitions can contain macro calls; thus the TX-0 model comes as quite a
>> surprise. We kept a modest stack of the state of each active macro
>> expansion. We certainly did not foresee that within a few years some
>> applications would need a 70-level stack!
> As the PDP-1 Macro imeplementation manual said about the macro feature:
>
>     It is the weakest
>    in that it is quite inflexible and does not incorporate any of the more significant improvements
>    in assembler technology that have occurred since the logic was first written in 1957.
>
> The PDP-1 was not a very big machine, only 4K words and the only
> standard I/O device was paper tape, so no overlays or multiple passes.
> I can imagine that while they knew how to write a better macro
> processor, they didn't want to use up the memory it would have needed.
>
> Bitsavers has a bunch of memos about the TX-0.
>
> Memo 39 describes TX-0 assembler as of 1962, which had real macros
> that could insert arbitrary strings, as they show in an example on
> pages 10-11.
>
> https://bitsavers.org/pdf/mit/tx-0/memos/M-5001-39_MIDAS_Nov62.pdf
>
> There are earlier memos about MACRO in 1959 and 1961 which suggest a weaker
> macro facility but don't have details.
>
> R's,
> John

At MIT they wrote two assemblers on the TX-0, and retargeted/ported both 
of them to the PDP-1.  (The machines were in adjacent rooms at the 
time.  Their architectures were very similar.)

* MACRO (macro expansion by limited partly-assembed memory words). DEC 
adopted MACRO, but its later MACRO assemblers do not seem to be at all 
based on that one.

* Midas (generalized macro expansion by inserting a character 
sequence).  MIT chose Midas for future work, and they rewrote it for the 
PDP-6, so that's what you find on ITS.

One of these retargets/ports was a challenge by Jack Dennis to a group 
of 4 or 5 students (the original hackers from the Tech Model Railroad 
Club) to do it over a weekend.

I agree, there is a lot of great stuff in these memos, from both MIT and 
from DEC, and in the oral histories done by the Computer History Museum 
and/or  the Smithsonian.

Bitsavers also has the hardware details, although they are in a very old 
notation, more abbreviated circuit schematics than logic diagrams..

- Aron

[COFF] Re: ancient macros, machine code translation,as mental architecture models

[Aron Insinga]

On 7/16/24 15:55, Aron Insinga wrote:
> On 7/15/24 15:39, John Levine wrote:
>> It appears that Douglas McIlroy <douglas.mcilroy@dartmouth.edu> said:
>>> In 1959, ...
>>> We never considered anything but recursive expansion, where macro
>>> definitions can contain macro calls; thus the TX-0 model comes as 
>>> quite a
>>> surprise. We kept a modest stack of the state of each active macro
>>> expansion. We certainly did not foresee that within a few years some
>>> applications would need a 70-level stack!
>> As the PDP-1 Macro imeplementation manual said about the macro feature:
>>
>>     It is the weakest
>>    in that it is quite inflexible and does not incorporate any of the 
>> more significant improvements
>>    in assembler technology that have occurred since the logic was 
>> first written in 1957.
>>
>> The PDP-1 was not a very big machine, only 4K words and the only
>> standard I/O device was paper tape, so no overlays or multiple passes.
>> I can imagine that while they knew how to write a better macro
>> processor, they didn't want to use up the memory it would have needed.
>>
>> Bitsavers has a bunch of memos about the TX-0.
>>
>> Memo 39 describes TX-0 assembler as of 1962, which had real macros
>> that could insert arbitrary strings, as they show in an example on
>> pages 10-11.
>>
>> https://bitsavers.org/pdf/mit/tx-0/memos/M-5001-39_MIDAS_Nov62.pdf
>>
>> There are earlier memos about MACRO in 1959 and 1961 which suggest a 
>> weaker
>> macro facility but don't have details.
>>
>> R's,
>> John
>
> At MIT they wrote two assemblers on the TX-0, and retargeted/ported 
> both of them to the PDP-1.  (The machines were in adjacent rooms at 
> the time.  Their architectures were very similar.)
>
> * MACRO (macro expansion by limited partly-assembed memory words). DEC 
> adopted MACRO, but its later MACRO assemblers do not seem to be at all 
> based on that one.
>
> * Midas (generalized macro expansion by inserting a character 
> sequence).  MIT chose Midas for future work, and they rewrote it for 
> the PDP-6, so that's what you find on ITS.
>
> One of these retargets/ports was a challenge by Jack Dennis to a group 
> of 4 or 5 students (the original hackers from the Tech Model Railroad 
> Club) to do it over a weekend.
>
> I agree, there is a lot of great stuff in these memos, from both MIT 
> and from DEC, and in the oral histories done by the Computer History 
> Museum and/or  the Smithsonian.
>
> Bitsavers also has the hardware details, although they are in a very 
> old notation, more abbreviated circuit schematics than logic diagrams..

p.s. That was too sweeping of a statement.  For the machines built by 
MIT, I found block diagrams and some instruction flows and lots of 
memos, but not the clock distribution matrix details.  Since the WW 
clock distribution matrix (ROM) triggered Wilkes' invention of 
microprogramming, I'd love to compare WW's with their later machines'.  
And I haven't found more than a little on Wes Clark's later machines, 
L-1 and ARC-1.  I know some info is in the U. Wash. archives.  So many 
curiosities, so little time. :-)

Best,

- Aron

[COFF] Re: ancient macros

[Aron Insinga]

This has nothing to do with compiling to code for other architectures!  
This is just for the record regarding the history of *assemblers*.

Here is a 1984 version of the DEC VAX-11 MACRO-32 *assembler* source 
listings:

http://www.bitsavers.org/pdf/dec/vax/microfiche/vms-source-listings/AH-BT13A-SE__VAX-VMS_V4.0_SRC_LST_MCRF/AH-BT13A-SE__VAX-VMS_V4.0_SRC_LST_MCRF/059__MACRO/

Unfortunately, they don't have the ASCII text attached, so you can't 
search.  Go up a level to find the linker, etc.

- Aron

[COFF] Re: machine code translation,as mental architecture models

[John Levine]

It appears that Douglas McIlroy <douglas.mcilroy@dartmouth.edu> said:
>-=-=-=-=-=-
>
>> the DEC PDP-1 MACRO assembler manual says that a macro call
>> is expanded by copying the *sequence of 'storage words' and
>> advancing the current location (.) for each word copied*
>
>> I am quite surprised.

I looked at the manual and I think he's misreading it. The "words" in
question are the tokens in the macro definition. 

The example macros look pretty straightforward, instructions and
pseudo-ops that are expanded replacing dummy arguments by actual ones.
There's no conditional assembly so each macro is just a parameterized
chunk of code.

https://bitsavers.org/pdf/dec/pdp1/PDP-1_Macro.pdf

R's,
John

[COFF] Re: machine code translation,as mental architecture models

[Douglas McIlroy]

[-- Attachment #1: Type: text/plain, Size: 342 bytes --]

> the DEC PDP-1 MACRO assembler manual says that a macro call
> is expanded by copying the *sequence of 'storage words' and
> advancing the current location (.) for each word copied*

> I am quite surprised.

I am, too. It seems that expansion is not recursive. And that it can only
allocate storage word by word, not in larger blocks.

Doug

[-- Attachment #2: Type: text/html, Size: 586 bytes --]

[COFF] Re: machine code translation,as mental architecture models

[Aron Insinga]

On 7/13/24 19:46, John Levine wrote:
> It appears that Douglas McIlroy <douglas.mcilroy@dartmouth.edu> said:
>> -=-=-=-=-=-
>>
>>> the DEC PDP-1 MACRO assembler manual says that a macro call
>>> is expanded by copying the *sequence of 'storage words' and
>>> advancing the current location (.) for each word copied*
>>> I am quite surprised.
> I looked at the manual and I think he's misreading it. The "words" in
> question are the tokens in the macro definition.
>
> The example macros look pretty straightforward, instructions and
> pseudo-ops that are expanded replacing dummy arguments by actual ones.
> There's no conditional assembly so each macro is just a parameterized
> chunk of code.
>
> https://bitsavers.org/pdf/dec/pdp1/PDP-1_Macro.pdf
>
> R's,
> John

Possibly, but they use 'syllables' for tokens (symbols or integers), and 
they say here that they advance the location counter after each word 
copied.  If they were copying characters into the input stream, they 
would not be incrementing the location counter ('.') after each word 
transferred.

And as you say, it is simple parameter substitution, so tracking which 
macro argument goes into which instruction's address field is easy.  The 
instruction format is simple.  So for each line in the macro definition 
body, if the opcode is a memory reference instruction, put the argument 
number in the binary instruction address field before storing the 
instruction word in a list/block. When expanding the macro, if the 
opcode is a memory reference instruction, get the argument number from 
the address field and replace it with the symbol table value of the 
symbol passed in as the actual argument, and store the word in the 
output stream (and incrememnt '.').

I haven't yet gotten the 18-bit-but-incompatible PDP-4 documentation for 
comparison.  [IIRC the PDP-4 assembler was the one with a single pass 
assembler that punched the symbol table at the end of the tape, and the 
clever loader that read the tape upside down and backwards to first 
rebuild the symbol table and then fix up the instructions and load them 
into memory.]

- Aron

[COFF] Re: ancient macros, machine code translation,as mental architecture models

[John Levine]

According to Aron Insinga <aki@insinga.com>:
>On 7/13/24 19:46, John Levine wrote:
>> I looked at the manual and I think he's misreading it. The "words" in
>> question are the tokens in the macro definition. ...

>Possibly, but they use 'syllables' for tokens (symbols or integers), and 
>they say here that they advance the location counter after each word 
>copied.  If they were copying characters into the input stream, they 
>would not be incrementing the location counter ('.') after each word 
>transferred.

If you really want to know what it did, here's the internals manual.
The description of the macro facility starts on page 19 and it is
quite clear that they're storing a tokenized version of the macros, so
they're not copying characters, but they're not just copying assembled
instructions either.

https://bitsavers.org/pdf/dec/pdp1/F36P_PDP1_Macro_Internals.pdf

  The macro instruction facility in MACRO is both the strongest and weakest part of the program.
  It is the strongest in the sense that it is thot part of the program which contributes most toward
  ease of programming, especially in setting up tables of specialized format. It is the weakest
  in that it is quite inflexible and does not incorporate any of the more significant improvements
  in assembler technology that have occurred since the logic was first written in 1957.

-- 
Regards,
John Levine, johnl@taugh.com, Primary Perpetrator of "The Internet for Dummies",
Please consider the environment before reading this e-mail. https://jl.ly

[COFF] Re: ancient macros, machine code translation,as mental architecture models

[Aron Insinga]

[-- Attachment #1: Type: text/plain, Size: 2779 bytes --]

On 7/14/24 14:02, John Levine wrote:
> According to Aron Insinga<aki@insinga.com>:
>> On 7/13/24 19:46, John Levine wrote:
>>> I looked at the manual and I think he's misreading it. The "words" in
>>> question are the tokens in the macro definition. ...
>> Possibly, but they use 'syllables' for tokens (symbols or integers), and
>> they say here that they advance the location counter after each word
>> copied.  If they were copying characters into the input stream, they
>> would not be incrementing the location counter ('.') after each word
>> transferred.
> If you really want to know what it did, here's the internals manual.
> The description of the macro facility starts on page 19 and it is
> quite clear that they're storing a tokenized version of the macros, so
> they're not copying characters, but they're not just copying assembled
> instructions either.
>
> https://bitsavers.org/pdf/dec/pdp1/F36P_PDP1_Macro_Internals.pdf

Thank you!!  I found the PDP-1 and TX-0 MACRO sources and was sadly 
unsurprised by the lack of comments, so they are difficult reading.

    http://www.bitsavers.org/bits/DEC/pdp1/papertapeImages/20040106/macro_6-63/_text/part2.txt

They are not storing tokens.  In fact, the list of 'codes' for items 
stored as the macro body on p 20 is:
     a storage word,
     a dummy symbol specification.
     a constant,
     a dummy symbol parameter assignment, or
     an end marker.
So it is not storing tokens for instructions, just storage words 
(instructions or data) as mentioned in the user manual.

In the discussion in the internals manual, after the paragraph 
mentioning the year this was designed (a nice touch), they say that they 
are storing the macro body as 'partially assembled' 'words' into which 
the dummy symbols are 'inserted'.  (And in a single-address architecture 
with a small memory address, addition is enough to do that insertion.)  
They explain why they did this instead of storing characters:

They do not look at the opcode as I suggested was possible, they have a 
more general solution that works for a word containing either code or data.

I think that this may be (at least as far as any of us know) a unique 
case from the early days of computing where, on the TX-0 and a port to 
the PDP-1, a macro body *is* stored as a list of 'machine words' instead 
of source text.  The macro  body is not manipulated as a 'higher-level 
construct', it is just used for quite limited macro expansion.

This has NO bearing on what DEC/HP/VSI did more than two decades later 
for the Alpha, Itanic, and x86_64 (where macros are expanded by the 
conventional insertion of characters from the macro body into the source 
text stream).

- Aron

[-- Attachment #2.1: Type: text/html, Size: 4118 bytes --]

[-- Attachment #2.2: 1RaBLgOaK9W7nogv.png --]
[-- Type: image/png, Size: 101224 bytes --]

[COFF] Re: ancient macros, machine code translation,as mental architecture models

[Paul Winalski]

[-- Attachment #1: Type: text/plain, Size: 912 bytes --]

On Sun, Jul 14, 2024 at 9:44 PM Aron Insinga <aki@insinga.com> wrote:

> I think that this may be (at least as far as any of us know) a unique case
> from the early days of computing where, on the TX-0 and a port to the
> PDP-1, a macro body *is* stored as a list of 'machine words' instead of
> source text.  The macro  body is not manipulated as a 'higher-level
> construct', it is just used for quite limited macro expansion.
>

Thanks for clearing this up.  I think you're right that this is a unique
case.  All assemblers I've ever dealt with expanded macros into text that
was then fed to the assember's parser just as if it were ordinary source
program text.  On a machine with limited memory it makes sense not to have
to re-parse the expanded source after macro expansion, but instead to do
the translation on the fly.  It saves a second pass over the expanded macro
call.

-Paul W.

[-- Attachment #2: Type: text/html, Size: 1264 bytes --]