[TUHS] Re: mental architecture models, Anyone ever heard of teaching a case study of Initial Unix?

[TUHS] Re: mental architecture models, Anyone ever heard of teaching a case study of Initial Unix?

[Douglas McIlroy]

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

> In order to port VMS to new architectures, DEC/HP/VSI ...
> turned the VAX MACRO assembly language (in which
> some of the VMS operating system was written) into a
> portable implementation language by 'compiling' the
> high-level CISC VAX instructions (and addressing modes)
> into sequences of RISC instructions.

Clem Pease did the same thing to port TMG from IBM 7000-series machines to
the GE  600 series for Multics, circa 1967. Although both architectures had
36-bit words, it was a challenge to adequately emulate IBM's accumulator,
which supported 38-bit sign-magnitude addition, 37-bit twos-complement and
36-bit ones-complement.

Doug

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

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

[John Levine]

It appears that Douglas McIlroy <douglas.mcilroy@dartmouth.edu> said:
>> portable implementation language by 'compiling' the
>> high-level CISC VAX instructions (and addressing modes)
>> into sequences of RISC instructions.

This idea, emulating one machine on another by translating strings of
instructions (basic blocks in compiler-ese) is quite old. I don't know
who did it first, and would be interested to hear if anyone knows,
although I expect it was reinvented multiple times.

It used to be harder because programs would store into the instruction
stream but these days code is all read-only it's quite standard. I'm
typing this on my M1 Macbook using an editor that thinks it's running
on an x86.

R's,
John

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

[Lars Brinkhoff]

John Levine writes:
> It used to be harder because programs would store into the instruction
> stream but these days code is all read-only it's quite standard. I'm
> typing this on my M1 Macbook using an editor that thinks it's running
> on an x86.

Note that Apple silicon has special hardware - not in standard ARM
devices - to accomodate the x86 memory model.  I don't know the detals
of Rosetta 2, but I believe this hardware is an important component to
make it work.

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

[Paul Winalski]

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

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

> >> portable implementation language by 'compiling' the
> >> high-level CISC VAX instructions (and addressing modes)
> >> into sequences of RISC instructions.
>
> No need for the quotes around 'compiling'.  VAX MACRO is a true, genuine
compiler.  The first version of it had a front end that translated VAX/VMS
assembly language into expanded IL for the GEM compiler back end.  The GEM
code generator then generated the Alpha code for that IL.  IIRC this
process bypassed most of the GEM optimizer.  But it gave you native Alpha
code.  GEM was later targeted to Itanium and that allowed the VAX MACRO
compiler to produce code for the IA64 version of OpenVMS.  The same process
was used by VSI to port OpenVMS to x86-64, but they may be using a
LLVM-based compiler back end now.

-Paul W.

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

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

[John R Levine]

On Wed, 10 Jul 2024, Lars Brinkhoff wrote:
>> typing this on my M1 Macbook using an editor that thinks it's running
>> on an x86.
>
> Note that Apple silicon has special hardware - not in standard ARM
> devices - to accomodate the x86 memory model.  I don't know the detals
> of Rosetta 2, but I believe this hardware is an important component to
> make it work.

I believe there's hardware to make it work better, but there's plenty of 
examples of object code translation without special hardware.  The last 
time Apple switched processors they compiled POWER code to x86 which was 
harder since the byte orders were different.

Still would be interested to hear when it was invented.  1967 seems early 
but not that early.

Regards,
John Levine, johnl@taugh.com, Taughannock Networks, Trumansburg NY
Please consider the environment before reading this e-mail. https://jl.ly

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

[Marc Donner]

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

Well, a computer scientist named Cathy May at IBM Research did this for the
S370 / Power PC architecture pair back in the mid-1980s.  The work was
novel to me at the time ... she and her long-term partner were close
friends of mine, so I heard about her work over shared dinners across
several years.

The basic technique was to load pages of 360 machine code unmodified into
Power PC memory, marking the pages as dirty.  If the machine branched into
one of these pages the VM trap handler would take the page and translate
all of its code from 370 instructions to Power PC instructions.  Once that
was done the branch, suitably recalculated, was reinstated.

It turned out to be remarkably easy to do the translation.  And in practice
the resulting Power PC code was only about 10% bigger than the original 370
code.  AND, since tons of code is never touched (corner cases on corner
cases) the result is quite efficient.

I don't know if IBM ever built a product based on her research, but it
seemed remarkably clever to me.

Marc
=====
nygeek.net
mindthegapdialogs.com/home <https://www.mindthegapdialogs.com/home>


On Tue, Jul 9, 2024 at 10:37 PM John Levine <johnl@taugh.com> wrote:

> It appears that Douglas McIlroy <douglas.mcilroy@dartmouth.edu> said:
> >> portable implementation language by 'compiling' the
> >> high-level CISC VAX instructions (and addressing modes)
> >> into sequences of RISC instructions.
>
> This idea, emulating one machine on another by translating strings of
> instructions (basic blocks in compiler-ese) is quite old. I don't know
> who did it first, and would be interested to hear if anyone knows,
> although I expect it was reinvented multiple times.
>
> It used to be harder because programs would store into the instruction
> stream but these days code is all read-only it's quite standard. I'm
> typing this on my M1 Macbook using an editor that thinks it's running
> on an x86.
>
> R's,
> John
>

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

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

[segaloco via TUHS]

On Wednesday, July 10th, 2024 at 7:12 AM, Marc Donner <marc.donner@gmail.com> wrote:

> The basic technique was to load pages of 360 machine code unmodified into Power PC memory, marking the pages as dirty. If the machine branched into one of these pages the VM trap handler would take the page and translate all of its code from 370 instructions to Power PC instructions. Once that was done the branch, suitably recalculated, was reinstated.
>
> ...
> 
> Marc
> =====
> nygeek.net
> mindthegapdialogs.com/home

Was this under the assumption everything else going on (bus architecture, memory map, exception/trap handling, etc.) was exactly the same or was the MMU for instance in the picture translating from 370 addresses to their equivalents on whatever PowerPC machine was in play?

That or was this only expected to work on PIC, user-level code and anything touching for instance privilege escalation or with explicit address pointers, I/O port access, etc. just understood to not be applicable to such a direct translation?  To tie it back to UNIX, for instance, was this thing also able to detect that a UNIX system call was being made and translate the 370 syscall mechanism into the PowerPC syscall mechanism?

My main experience with emulation is console video games so in that realm, you're dealing not only with a different CPU architecture but system bus, memory map, peripheral controllers, etc.  Essentially you're not just speaking another language, you're on another planet entirely.  This has lead to a entrenched belief in my mind that this sort of "direct translation" of CPU operations is a non-starter in emulation hence my curiosity.  If there's some historic approach to emulation efficiently handling system architecture diversity beyond just CPU instructions, I'm certainly interested!

- Matt G.

P.S. Feeling trepid about continuing this thread on TUHS rather than COFF, but resisting the urge to bump it (again).  To keep it on topic, I'd mostly be interested in how this sort of thing would handle the UNIX system call mechanism, because that would certainly illuminate the general idea of translating something more complicated than an algorithm.

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

[Dan Cross]

On Wed, Jul 10, 2024 at 12:58 PM segaloco via TUHS <tuhs@tuhs.org> wrote:
> On Wednesday, July 10th, 2024 at 7:12 AM, Marc Donner <marc.donner@gmail.com> wrote:
> > The basic technique was to load pages of 360 machine code unmodified into Power PC memory, marking the pages as dirty. If the machine branched into one of these pages the VM trap handler would take the page and translate all of its code from 370 instructions to Power PC instructions. Once that was done the branch, suitably recalculated, was reinstated.
>
> Was this under the assumption everything else going on (bus architecture, memory map, exception/trap handling, etc.) was exactly the same or was the MMU for instance in the picture translating from 370 addresses to their equivalents on whatever PowerPC machine was in play?
>
> That or was this only expected to work on PIC, user-level code and anything touching for instance privilege escalation or with explicit address pointers, I/O port access, etc. just understood to not be applicable to such a direct translation?  To tie it back to UNIX, for instance, was this thing also able to detect that a UNIX system call was being made and translate the 370 syscall mechanism into the PowerPC syscall mechanism?
>
> My main experience with emulation is console video games so in that realm, you're dealing not only with a different CPU architecture but system bus, memory map, peripheral controllers, etc.  Essentially you're not just speaking another language, you're on another planet entirely.  This has lead to a entrenched belief in my mind that this sort of "direct translation" of CPU operations is a non-starter in emulation hence my curiosity.  If there's some historic approach to emulation efficiently handling system architecture diversity beyond just CPU instructions, I'm certainly interested!

Surely things like this have some limitations.  Self-modifying code,
for example, would be more challenging (though not impossible) to
implement. But for _most_ programs, where text and data are mapped
separately, it wouldn't be that bad; if data formats are common across
ISAs and the instruction sets are similar-ish, it wouldn't be that
bad. For the mainframe to PowerPC, I imagine floating point would be
the sticky wicket.

> P.S. Feeling trepid about continuing this thread on TUHS rather than COFF, but resisting the urge to bump it (again).  To keep it on topic, I'd mostly be interested in how this sort of thing would handle the UNIX system call mechanism, because that would certainly illuminate the general idea of translating something more complicated than an algorithm.

In some sense, this is one of the easiest cases to support.  The
system call mechanism necessarily needs some method to trap into the
kernel; the kernel, in turn, needs to look at the state of the user
program to see what it should do in response to that trap.  In the
case of going across an ISA, the kernel's job is marginally harder in
that it has to respond to having multiple ways to end up at the system
call handler, but that's not so much different than supporting
multiple system call conventions on a single system.  For example, on
x86, we have the SYSCALL instruction, but also SYSENTER and older
software might initiate a syscall by means of the INT instruction
(e.g., INT 0x80 or INT 0x40).  Across ISAs, one might enter the kernel
on an illegal instruction trap, in which case the trap handler will
have access to the faulting address and can examine what's there; if
it's e.g. a 370 instruction, one could interpret it and figure out
what to do from there.

Usually system calls are made by calling a stub function in, say, the
C library.  That stub then sets up state in whatever manner the system
expects, such as poking the system call number and arguments into
registers or putting them on the stack in a specific order or
whatever; the stub then traps, at which point the kernel takes over,
services the syscall, and (usually) returns control to userspace, the
return value will be examined, errno might be set, and the stub
"returns" to calling code.  Of course, the process might have invoked
`exit` or something, in which case control won't be returned to
userspace.  Or the call can block, context switches might happen, the
arguments might be bad, the thing can be killed, etc, etc.  Anyway, in
the context of this kind of ISA translation, presumably the stubs
would be interpreted and the interpreter would be smart enough to
recognize the trap, in which case it might rewrite to a native trap of
some kind, instead of relying on the illegal instruction trick.

These techniques are rather old, and I think go back much further than
we're suggesting.  Knuth mentions nested translations in TAOCP (Volume
1, I believe), suggesting the technique was well-known as early as the
mid-1960s.

        - Dan C.

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

[Marc Donner]

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

I never dug that deep into her work.  If I were to guess, I would say that
this was aimed at user-space sorts of code.  It was aimed at making it
possible to run large old 370 binaries in Power PC architecture machines.
If I recall correctly, there was some discussion of migrating off of the
S370 (later S390 and then z-system) ISA to the Power PC architecture.  My
sense was that this was a research study to understand whether a naive
translation like this could work.

I can not imagine trying to translate system code in this way.
=====
nygeek.net
mindthegapdialogs.com/home <https://www.mindthegapdialogs.com/home>


On Wed, Jul 10, 2024 at 1:07 PM segaloco via TUHS <tuhs@tuhs.org> wrote:

> On Wednesday, July 10th, 2024 at 7:12 AM, Marc Donner <
> marc.donner@gmail.com> wrote:
>
> > The basic technique was to load pages of 360 machine code unmodified
> into Power PC memory, marking the pages as dirty. If the machine branched
> into one of these pages the VM trap handler would take the page and
> translate all of its code from 370 instructions to Power PC instructions.
> Once that was done the branch, suitably recalculated, was reinstated.
> >
> > ...
> >
> > Marc
> > =====
> > nygeek.net
> > mindthegapdialogs.com/home
>
> Was this under the assumption everything else going on (bus architecture,
> memory map, exception/trap handling, etc.) was exactly the same or was the
> MMU for instance in the picture translating from 370 addresses to their
> equivalents on whatever PowerPC machine was in play?
>
> That or was this only expected to work on PIC, user-level code and
> anything touching for instance privilege escalation or with explicit
> address pointers, I/O port access, etc. just understood to not be
> applicable to such a direct translation?  To tie it back to UNIX, for
> instance, was this thing also able to detect that a UNIX system call was
> being made and translate the 370 syscall mechanism into the PowerPC syscall
> mechanism?
>
> My main experience with emulation is console video games so in that realm,
> you're dealing not only with a different CPU architecture but system bus,
> memory map, peripheral controllers, etc.  Essentially you're not just
> speaking another language, you're on another planet entirely.  This has
> lead to a entrenched belief in my mind that this sort of "direct
> translation" of CPU operations is a non-starter in emulation hence my
> curiosity.  If there's some historic approach to emulation efficiently
> handling system architecture diversity beyond just CPU instructions, I'm
> certainly interested!
>
> - Matt G.
>
> P.S. Feeling trepid about continuing this thread on TUHS rather than COFF,
> but resisting the urge to bump it (again).  To keep it on topic, I'd mostly
> be interested in how this sort of thing would handle the UNIX system call
> mechanism, because that would certainly illuminate the general idea of
> translating something more complicated than an algorithm.
>

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

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

[Clem Cole]

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

On Wed, Jul 10, 2024 at 3:23 PM Marc Donner <marc.donner@gmail.com> wrote:

> I can not imagine trying to translate system code in this way.
>
 Marc, you are better than that - proof by lack of imagination is not very
effective😘

Seriously, the "VAX Compiler" that Paul describes made a great deal of
sense to the VMS team when it was developed.   It's all about *economics*,
not technical purity.  And solution actually worked really well; as Paul
points out, it lived for many different ISAs that followed VAX at DEC and
now VSi.

What I always was amazed by was the Cutler use assembler in the first place
since DEC had production quality BLISS compilers.  But as Dave Cane [VAX750
lead] once put it, it was the world's greatest assembler machine.  Dave
(famously) hated BLISS but was one heck of an assembly programmer.  VMS
both at the kernel and systems level, was (is) in assembler, so treating
the VAX as a HLL and "compiling" to a new ISA was solid economics.
ᐧ

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

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

[Marc Donner]

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

Picky, picky, Clem.

Given the dramatic differences in I/O architecture, interrupt handling, and
virtual memory between s370 and Power PC, it makes little sense to try to
translate system code this way.

On Wed, Jul 10, 2024, 15:39 Clem Cole <clemc@ccc.com> wrote:

>
>
> On Wed, Jul 10, 2024 at 3:23 PM Marc Donner <marc.donner@gmail.com> wrote:
>
>> I can not imagine trying to translate system code in this way.
>>
>  Marc, you are better than that - proof by lack of imagination is not
> very effective😘
>
> Seriously, the "VAX Compiler" that Paul describes made a great deal of
> sense to the VMS team when it was developed.   It's all about *economics*,
> not technical purity.  And solution actually worked really well; as Paul
> points out, it lived for many different ISAs that followed VAX at DEC and
> now VSi.
>
> What I always was amazed by was the Cutler use assembler in the first place
> since DEC had production quality BLISS compilers.  But as Dave Cane
> [VAX750 lead] once put it, it was the world's greatest assembler machine.
>   Dave (famously) hated BLISS but was one heck of an assembly programmer.
> VMS both at the kernel and systems level, was (is) in assembler, so
> treating the VAX as a HLL and "compiling" to a new ISA was solid economics.
> ᐧ
>

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

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

[Adam Thornton]

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

The Cathy May paper can be found at:

https://dl.acm.org/doi/pdf/10.1145/29650.29651

And it's quite interesting; the first time I was aware of work like this
was six or seven years later, when ARDI's Mac emulator "Executor" was the
new hotness.

Adam

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

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

[Dan Cross]

[TUHS to Bcc:, +COFF]

On Wed, Jul 10, 2024 at 5:26 PM John Levine <johnl@taugh.com> wrote:
> It appears that Noel Chiappa <jnc@mercury.lcs.mit.edu> said:
> >    > From: Dan Cross
> >
> >    > These techniques are rather old, and I think go back much further than
> >    > we're suggesting. Knuth mentions nested translations in TAOCP ..
> >    > suggesting the technique was well-known as early as the mid-1960s.
>
> Knuth was talking about simulating one machine on another, interpreting
> one instruction at a time.  As he notes, the performance is generally awful,
> although IBM did microcode emulation of many of their second generation
> machines on S/360 which all (for business reasons) ran faster than the
> real machines.  Unsurprisingly, you couldn't emulate a 7094 on anything
> smaller than a 360/65.

It's not clear to me why you suggest with such evident authority that
Knuth was referring only to serialized instruction emulation and not
something like JIT'ed code; true, he doesn't specify one way or the
other, but I find it specious to conclude that that implies the
technique wasn't already in use, or at least known.  But certainly by
then JIT'ing techniques for "interpreted" programming languages were
known; it doesn't seem like a great leap to extend that to binary
translation.  Of course, that's speculation on my part, and I could
certainly be wrong.

> We've been discussing batch or JIT translation of code which gives
> much better performance without a lot of hardware help.

JIT'd performance of binary transliteration is certainly going to be
_better_ than strict emulation, but it is unlikely to be _as good_ as
native code. Indeed, this is still an active area of research; e.g.,
luajit; https://www.mattkeeter.com/blog/2022-10-04-ssra/ (disclaimer:
Matt's a colleague of mine), etc.

        - Dan C.

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

[segaloco via TUHS]

On Wednesday, July 10th, 2024 at 4:00 PM, John Levine <johnl@taugh.com> wrote:

> It appears that Al Kossow aek@bitsavers.org said:
> 
> > On 7/10/24 1:53 PM, Dan Cross wrote:
> > 
> > > The idea of writing simulators for machines clearly dates to before
> > > (or near) the beginning of TAOCP.
> 
> 
> Sure, but the topic of interest here is compiling machine code from one
> machine to another. You know like Rosetta does for x86 code running on
> my Macbook (obUnix: whose OS is descended from FreeBSD and Mach and does
> all the Posix stuff) which has an M2 ARM chip.
> 
> We know that someone did it in 1967 from 709x to GE 635, which I agree
> was quite a trick since really the only thing the two machines had in
> common was a 36 bit word size. I was wondering if anyone did machine
> code translation as opposed to instruction at a time simulation before that.
> 

Attempting once again to COFF this thread as I am quite interested in the
discussion of this sort of emulation/simulation matter outside of the
confines of UNIX history as well.

To add to the discussion, while not satisfying the question of "where did
this sort of thing begin", the 3B20 was another machine that provided some
means of emulating another architecture via microcode, although what I know
about this is limited to discussions about emulating earlier ESS machines
to support existing telecom switching programs.  I've yet to find any
literature suggesting this was ever used to emulate other general-purpose
computers such as IBM, DEC, etc. but likewise no suggestion that it *couldn't*
be used this way.

- Matt G.

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

[John Levine]

It appears that Al Kossow <aek@bitsavers.org> said:
>On 7/10/24 1:53 PM, Dan Cross wrote:
>
>> The idea of writing simulators for machines clearly dates to before
>> (or near) the beginning of TAOCP.

Sure, but the topic of interest here is compiling machine code from one
machine to another.  You know like Rosetta does for x86 code running on
my Macbook (obUnix: whose OS is descended from FreeBSD and Mach and does
all the Posix stuff) which has an M2 ARM chip.

We know that someone did it in 1967 from 709x to GE 635, which I agree
was quite a trick since really the only thing the two machines had in
common was a 36 bit word size.  I was wondering if anyone did machine
code translation as opposed to instruction at a time simulation before that.

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

[Al Kossow]

On 7/10/24 1:53 PM, Dan Cross wrote:

> The idea of writing simulators for machines clearly dates to before
> (or near) the beginning of TAOCP.

Whirlwind, Summer 1954
http://bitsavers.org/pdf/mit/whirlwind/summer_session_1954

Summer Session Computer and Algebraic Systems were both
interpreters

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

[John Levine]

It appears that Noel Chiappa <jnc@mercury.lcs.mit.edu> said:
>    > From: Dan Cross
> 
>    > These techniques are rather old, and I think go back much further than
>    > we're suggesting. Knuth mentions nested translations in TAOCP ..
>    > suggesting the technique was well-known as early as the mid-1960s.

Knuth was talking about simulating one machine on another, interpreting
one instruction at a time.  As he notes, the performance is generally awful,
although IBM did microcode emulation of many of their second generation
machines on S/360 which all (for business reasons) ran faster than the
real machines.  Unsurprisingly, you couldn't emulate a 7094 on anything
smaller than a 360/65.

We've been discussing batch or JIT translation of code which gives
much better performance without a lot of hardware help.

>In a batch OS which only runs in a single mode, one _could_ just use regular
>subroutine calls to call the 'operating system', to 'get there from here'.
>The low-level reason not to do this is that one would need the addresses of
>all the routines in the OS (which could change over time). 

That was quite common. The manuals for 70xx IOCS, which was the I/O
management part of the system, show all the IOCS calls use TSX, the
usual subroutine call which saved the return address in an index
register and jumps (Transfers.) I think they avoided the address
problem by putting transfer vectors at fixed locations in low memory,
so your code did the TSX to an entry in the transfer vector which
jumped to the real routine.

>one. I happen to have a CTSS manual (two, actually :-), and in CTSS a system
>call was:
>
>	TSX	NAMEI, 4
> 	..
>	..
>NAMEI:	TIA	=HNAME
>
>where 'NAME' "is the BCD name of a legitimate supervisor entry point", and
>the 'TIA' instruction may be "usefully (but inexactly) read as Trap Into A
>core" (remember that in CTSS, the OS lived in the A core). (Don't ask me what
>HNAME is, or what a TSX instruction does! :-)

TSX we know, but I don't see TIA in the regular 7094 manual. It's
documented in the RPQ for additional core storage, a jump from core
bank B to A. The multiprogramming RPQ made TIA trap in protection mode,
so it was indeed a system call.

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

[Dan Cross]

On Wed, Jul 10, 2024 at 4:34 PM Noel Chiappa <jnc@mercury.lcs.mit.edu> wrote:
>     > From: Dan Cross
>     > These techniques are rather old, and I think go back much further than
>     > we're suggesting. Knuth mentions nested translations in TAOCP ..
>     > suggesting the technique was well-known as early as the mid-1960s.
>
> I'm not sure what exactly you're referring to with "[t]hese techniques"; I
> gather you are talking about the low-level mechanisms used to implement
> 'system calls'?

No, I was referring to the idea of binary transliteration from one
architecture to another.  I found the reference; Knuth refers to "an
extreme example of inefficient use of computer simulators [... in] the
true story of machine A simulating machine B running a program that
simulates machine C!  This is the way to make a large, expensive
computer give poorer results than its cheaper cousin."  (This is on
page 203 of my copy of Volume 1.)

The idea of writing simulators for machines clearly dates to before
(or near) the beginning of TAOCP.  The idea of binary instruction
translation during simulation is so obvious I can't imagine it wasn't
part of such simulations; particularly early on.

> If so, please permit me to ramble for a while, and revise
> your time-line somewhat.
> [snip]
>
>(I have yet to research to see if any early OS's
> did use subroutine calls as their interface.)

Not terribly early, but Xinu, as described in Comer's book, did/does.

> [snip]

This was very interesting, regardless; thanks.

        - Dan C.

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

[Noel Chiappa]

    > From: Dan Cross
 
    > These techniques are rather old, and I think go back much further than
    > we're suggesting. Knuth mentions nested translations in TAOCP ..
    > suggesting the technique was well-known as early as the mid-1960s.

I'm not sure what exactly you're referring to with "[t]hese techniques"; I
gather you are talking about the low-level mechanisms used to implement
'system calls'? If so, please permit me to ramble for a while, and revise
your time-line somewhat.

There are two reasons one needs 'system calls'; low-level 'getting there from
here' (which I'll explain below), and 'switching operating/protection
domains' (roughly, from 'user' to 'kernel').

In a batch OS which only runs in a single mode, one _could_ just use regular
subroutine calls to call the 'operating system', to 'get there from here'.
The low-level reason not to do this is that one would need the addresses of
all the routines in the OS (which could change over time). If one instead
used permanent numbers to identify system calls, and had some sort of 'system
call' mechanism (an instruction - although it could be a subroutine call to a
fixed location in the OS), one wouldn't need the addresses. But this is just
low level mechanistic stuff. (I have yet to research to see if any early OS's
did use subroutine calls as their interface.)

The 'switching operating/protection domains' is more fundamental - and
unavoidable. Obviously, it wouldn't have been needed before there were
machines/OS's that operated in multiple modes. I don't have time to research
which was the _first_ machine/OS to need this, but clearly CTSS was an early
one. I happen to have a CTSS manual (two, actually :-), and in CTSS a system
call was:

	TSX	NAMEI, 4
 	..
	..
NAMEI:	TIA	=HNAME

where 'NAME' "is the BCD name of a legitimate supervisor entry point", and
the 'TIA' instruction may be "usefully (but inexactly) read as Trap Into A
core" (remember that in CTSS, the OS lived in the A core). (Don't ask me what
HNAME is, or what a TSX instruction does! :-)


So that would have been 1963, or a little earlier. By 1965 (see the 1965 Fall
Joint Computer Conference papers:

  https://multicians.org/history.html

for more), MIT had already moved on to the idea of using a subroutine calls
that could cross protection domain boundaries for 'system calls', for
Multics. The advantage of doing that is that if the machine has a standard
way of passing arguments to subroutines, you natively/naturally get arguments
to system calls.

	Noel