[TUHS] arithmetic IF (was origin of string.h and ctype.h)

[TUHS] arithmetic IF (was origin of string.h and ctype.h)

[Paul McJones]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1892 bytes --]

On Aug 17, 2017, arnold at skeeve.com wrote:

> I remember reading an article somewhere on the history of the first
> FORTRAN compiler.  The guys doing it wanted it to succeed, and they
> were fighting the mentality that high level languages could not possibly
> be as efficient as hand-coded assembly, so they put a lot of work into
> the optimization of the generated code.
> 
> It worked so well that the results that came out of the compiler
> sometimes suprised the compiler writers!  They then would have to
> dive into the compiler sources to figure out how it was done.
> 
> I don't remember where I read this article. If the story rings a
> bell with anyone, let me know.

In his paper "The history of FORTRAN I, II and III” presented at the First ACM SIGPLAN conference on History of Programming Languages (1978), John Backus said:

> It was an exciting period; when later on we began to get fragments of compiled programs out of the system, we were often astonished at the surprising transformations in the indexing operations and in the arrangement of the computation which the compiler made, changes which made the object program efficient but which we would not have thought to make as programmers ourselves (even though, of course, Nelson or Ziller could figure out how the indexing worked, Sheridan could explain how an expresssion had been optimized beyond recognition, and Goldberg or Sayre could tell us how section 5 had generated additional indexing operations). Transfers of control appeared which corresponded to no source statement, expressions were radically rearranged, and the same DO statement might produce no instructions in the object program in one context, and in another it would produce many instructions in different places in the program.

The paper is available here, courtesy of ACM: http://www.softwarepreservation.org/projects/FORTRAN/index.html .

[TUHS] arithmetic IF (was origin of string.h and ctype.h)

[arnold]

That's it!  Much thanks!

Arnold

Paul McJones <paul at mcjones.org> wrote:

> On Aug 17, 2017, arnold at skeeve.com wrote:
>
> > I remember reading an article somewhere on the history of the first
> > FORTRAN compiler.  The guys doing it wanted it to succeed, and they
> > were fighting the mentality that high level languages could not possibly
> > be as efficient as hand-coded assembly, so they put a lot of work into
> > the optimization of the generated code.
> > 
> > It worked so well that the results that came out of the compiler
> > sometimes suprised the compiler writers!  They then would have to
> > dive into the compiler sources to figure out how it was done.
> > 
> > I don't remember where I read this article. If the story rings a
> > bell with anyone, let me know.
>
> In his paper "The history of FORTRAN I, II and III??? presented at the
> First ACM SIGPLAN conference on History of Programming Languages (1978),
> John Backus said:
> 
> > It was an exciting period; when later on we began to get fragments
> > of compiled programs out of the system, we were often astonished at
> > the surprising transformations in the indexing operations and in the
> > arrangement of the computation which the compiler made, changes which
> > made the object program efficient but which we would not have thought
> > to make as programmers ourselves (even though, of course, Nelson or
> > Ziller could figure out how the indexing worked, Sheridan could explain
> > how an expresssion had been optimized beyond recognition, and Goldberg
> > or Sayre could tell us how section 5 had generated additional indexing
> > operations). Transfers of control appeared which corresponded to no
> > source statement, expressions were radically rearranged, and the same
> > DO statement might produce no instructions in the object program in one
> > context, and in another it would produce many instructions in different
> > places in the program.
>
> The paper is available here, courtesy of ACM:
> http://www.softwarepreservation.org/projects/FORTRAN/index.html .

[TUHS] arithmetic IF (was origin of string.h and ctype.h)

[Doug McIlroy]

> [Fortran's optimization]  worked so well that the results that came out of the compiler
> sometimes suprised the compiler writers!

Except when it didn't. They gave particular attention to nested
loops with subscripted variables, exemplified by linear-algebra
computations. But their algorithms behaved quite wildly on
nonstandard loops. Vic Vyssotsky cooked up a nest of loops
surrounding a single awful statement that filled up the
maximum 10 continuation lines with triple subscripts in all
permutations of several variables. That statement compiled
into thousands of instructions, far more than a naively
written compiler would have produced.

doug

[TUHS] arithmetic IF (was origin of string.h and ctype.h)

[Doug McIlroy]

> According to the Wikipedia article on FORTRAN, CAS was usually not the
> most efficient way to implement arithmetic IF anyway.  CAS takes up
> four words of memory and takes three cycles to execute, whereas you
> can do it in two words and two cycles with the transfer instructions.

Though the article's conclusion was right, its numbers were wrong. 
As a correct discussion of possible implementations of arithmetic-IF
would be long and essentially off topic, I have chopped most of it
out of the article.

doug

[TUHS] arithmetic IF (was origin of string.h and ctype.h)

[Paul Winalski]

On 8/16/17, Doug McIlroy <doug at cs.dartmouth.edu> wrote:
>>> the 709 added CAS
>
>> It was my understanding that the 704 had this instruction too
>
> Yes. It's in the manual.
>
> (I searched in vain for an online manual. A quick trip to the
> attic turned up the real thing in less time.)
>
> Doug
>
From what I've been able to determine, FORTRAN came out shortly after
the IBM 704.  Undoubtedly both were under development at the same
time.  So the question is, was arithmetic IF put in FORTRAN to take
advantage of the CAS instruction, or was CAS added to the IBM 704
instruction set to provide hardware support for arithmetic IF?  Or
maybe neither?

According to the Wikipedia article on FORTRAN, CAS was usually not the
most efficient way to implement arithmetic IF anyway.  CAS takes up
four words of memory and takes three cycles to execute, whereas you
can do it in two words and two cycles with the transfer instructions.

-Paul W.

[TUHS] arithmetic IF (was origin of string.h and ctype.h)

[Greg 'groggy' Lehey]

On Wednesday, 16 August 2017 at 14:04:47 -0400, Paul Winalski wrote:
> On 8/16/17, Doug McIlroy <doug at cs.dartmouth.edu> wrote:
>>>> the 709 added CAS
>>
>>> It was my understanding that the 704 had this instruction too
>>
>> Yes. It's in the manual.
>>
>> (I searched in vain for an online manual. A quick trip to the
>> attic turned up the real thing in less time.)
>
> From what I've been able to determine, FORTRAN came out shortly
> after the IBM 704.  Undoubtedly both were under development at the
> same time.

I think there's some doubt about those statements.  The 704 was
introduced in 1954, and FORTRAN didn't appear until late 1956 or 1957.
That's a long time in the history of computing.

> So the question is, was arithmetic IF put in FORTRAN to take
> advantage of the CAS instruction, or was CAS added to the IBM 704
> instruction set to provide hardware support for arithmetic IF?  Or
> maybe neither?

I think the arithmetic IF was put into FORTRAN because it was easy to
implement with the CAS instruction.  It doesn't make much sense from a
mathematical point of view.

> According to the Wikipedia article on FORTRAN, CAS was usually not the
> most efficient way to implement arithmetic IF anyway.  CAS takes up
> four words of memory and takes three cycles to execute, whereas you
> can do it in two words and two cycles with the transfer instructions.

Looking at the assembly listings of the FORTRAN II compiler
(http://www.softwarepreservation.org/projects/FORTRAN/source/fortran-ii/fort1.lst.html,
mentioned by Paul McJones), a typical use of CAS is followed by two
unconditional TRA (transfer) instructions and further code, though
presumably early FORTRAN compilers would not optimize in this way.
Timing includes loading an operand from memory.  The conditional
transfer instructions are based on accumulator contents, so you'd need
to perform some arithmetic operation first, in the process possibly
destroying accumulator contents that you want.

Doubtless you're right in some (many) cases, but my guess is that the
authors of FORTRAN were looking for the cheapest solution, not the
fastest one.  For decades to come, the fastest solution was assembler.

Greg
--
Sent from my desktop computer.
Finger grog at lemis.com for PGP public key.
See complete headers for address and phone numbers.
This message is digitally signed.  If your Microsoft mail program
reports problems, please read http://lemis.com/broken-MUA
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 163 bytes
Desc: not available
URL: <http://minnie.tuhs.org/pipermail/tuhs/attachments/20170817/fc50a99c/attachment.sig>

[TUHS] arithmetic IF (was origin of string.h and ctype.h)

[arnold]

"Greg 'groggy' Lehey" <grog at lemis.com> wrote:

> Looking at the assembly listings of the FORTRAN II compiler
> (http://www.softwarepreservation.org/projects/FORTRAN/source/fortran-ii/fort1.lst.html,
> mentioned by Paul McJones), a typical use of CAS is followed by two
> unconditional TRA (transfer) instructions and further code, though
> presumably early FORTRAN compilers would not optimize in this way.

You'd have to run some FORTRAN through the compiler to see.  :-)

I remember reading an article somewhere on the history of the first
FORTRAN compiler.  The guys doing it wanted it to succeed, and they
were fighting the mentality that high level languages could not possibly
be as efficient as hand-coded assembly, so they put a lot of work into
the optimization of the generated code.

It worked so well that the results that came out of the compiler
sometimes suprised the compiler writers!  They then would have to
dive into the compiler sources to figure out how it was done.

I don't remember where I read this article. If the story rings a
bell with anyone, let me know.

Thanks,

Arnold