Fortran - recursion, stack, fortran

Author

recursion, stack, fortran

Reagan Revision

2008-01-13, 4:29 am

Does the existence of recursion in fortran95 or later imply the existence of
a stack, as far as the Fortran Programming Language is concerned?

The only reference I find in the standard is:

C.12.1.4 Automatic arrays and allocatable variables (5.1, 5.1.2.5.3) 7

Two features useful for writing modular software are automatic arrays,
created on entry to a subprogram 8

and destroyed on return, and allocatable variables, including arrays whose
rank is fixed but whose actual 9

size and lifetime is fully under the programmer's control through explicit
ALLOCATE and DEALLO- 10

CATE statements. The declarations 11

SUBROUTINE X (N, A, B) 12

REAL WORK (N, N); REAL, ALLOCATABLE :: HEAP (:, :) 13

specify an automatic array WORK and an allocatable array HEAP. Note that a
stack is an adequate 14

storage mechanism for the implementation of automatic arrays, but a heap
will be needed for some 15

allocatable variables. 16

#end excerpt

--
Reagan Revision

"We are being told that a competent, trustworthy president is someone
who brandishes his religion like a neon sign, loads a gun and goes out
hunting for beautiful winged creatures, and tries to imitate a past
president who, by the way, never shot a bird or felt the need to imitate
anybody."

~~ Patti Davis Is Not Flattered by GOP Candidates' Pale Imitations of
Her Father

----== Posted via Newsfeeds.Com - Unlimited-Unrestricted-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----

Arjen Markus

2008-01-13, 8:15 am

On 13 jan, 11:27, "Reagan Revision" <inva...@invalid.net> wrote:
> Does the existence of recursion in fortran95 or later imply the existence of
> a stack, as far as the Fortran Programming Language is concerned?
>

As fas as I understand it, the standard tries to be completely neutral
as to the
actual implementation of any feature. That would very well include
stacks as a
means to implementation recursion. Stacks would of course be a very
common
way to do it.

Regards,

Arjen

Reagan Revision

2008-01-14, 7:19 pm

"Arjen Markus" <arjen.markus@wldelft.nl> wrote in message
news:74335c2b-75a5-4752-b032-793396dc1d6b@k2g2000hse.googlegroups.com...
> On 13 jan, 11:27, "Reagan Revision" <inva...@invalid.net> wrote:
>
> As fas as I understand it, the standard tries to be completely neutral
> as to the
> actual implementation of any feature. That would very well include
> stacks as a
> means to implementation recursion. Stacks would of course be a very
> common
> way to do it.
Hmmm.... That's not the answer I was expecting.

I've never been accused of having sophisticated methods with memory
management, but I've always thought of recursion in terms of stacks. In
some sense, I'm able to "see" the stack itself for, say, a factorial
function written using recursion. I wouldn't be surprised if I had a
professor use a recursive function to motivate the discussion of a stack.

Maybe stacks are like sorting, in some sense, integral to the business at
hand for scientific computing, but non-entities in terms of the standard.

--
Reagan Revision

"We are being told that a competent, trustworthy president is someone
who brandishes his religion like a neon sign, loads a gun and goes out
hunting for beautiful winged creatures, and tries to imitate a past
president who, by the way, never shot a bird or felt the need to imitate
anybody."

~~ Patti Davis Is Not Flattered by GOP Candidates' Pale Imitations of
Her Father

----== Posted via Newsfeeds.Com - Unlimited-Unrestricted-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----

Arjen Markus

2008-01-15, 8:16 am

On 15 jan, 02:10, "Reagan Revision" <inva...@invalid.net> wrote:
> "Arjen Markus" <arjen.mar...@wldelft.nl> wrote in message
>
> news:74335c2b-75a5-4752-b032-793396dc1d6b@k2g2000hse.googlegroups.com...> =
On 13 jan, 11:27, "Reagan Revision" <inva...@invalid.net> wrote:
ce[color=darkred]
>
>
> Hmmm.... =A0That's not the answer I was expecting.
>
> I've never been accused of having sophisticated methods with memory
> management, but I've always thought of recursion in terms of stacks. =A0In=

> some sense, I'm able to "see" the stack itself for, say, a factorial
> function written using recursion. =A0I wouldn't be surprised if I had a
> professor use a recursive function to motivate the discussion of a stack.
>
> Maybe stacks are like sorting, in some sense, integral to the business at
> hand for scientific computing, but non-entities in terms of the standard.
>

Well, I am no connoisseur of the standard text, nor of
compiler writing. My answer is based on what I have picked
up from postings here. The standard is, as I understand it,
very liberal (*) wrt the actual implementation, thus giving
compiler writers every chance to come with something smart
or useful for their particular platform.

To extend the analogy with sorting: the QuickSort algorithm
is a very quick algorithm, but it may not always be the best.
For instance: MergeSort is roughly twice as slow (IIRC), but it
maintains the order of entries that sort equally, thus making
it possible to sort one column after another and get a combined
result.

Regards,

Arjen

(*) liberal in the non-political sense of the word, of course.

Richard Maine

2008-01-15, 7:16 pm

Arjen Markus <arjen.markus@wldelft.nl> wrote:
[color=darkred]
> On 15 jan, 02:10, "Reagan Revision" <inva...@invalid.net> wrote:
news:74335c2b-75a5-4752-b032-793396dc1d6b@k2g2000hse.googlegroups.com...[color=darkred]
> On 13 jan, 11:27, "Reagan Revision" <inva...@invalid.net> wrote:

(For some reason, I've not yet seen Regan's post other than the bit
quoted in Arjen's reply, so I'm replying 2nd hand as it were.)

I can confirm Arjen's answer. The Fortran standard almost *NEVER*
specifies implementation details at that level. There are times when
this makes for awkward and complicated descriptions in the standard,
where it would be much simpler to just talk about the implementation.
This is all quite intentional. For example, the descriptions of argument
passing go quite a lot out of the way to allow multiple implementation
methods. There are several conditions in the standard that are there
specifically to prohibit code that would give results that depend on
which implementation technique is selected by the compiler.

It has been noted that the Fortran standard could be implemented as a
bunch of grad students with paper and pencils.

And no, implementation of recursion does not inherently require stacks.
That just happens to be an obvious and relatively simple way to do it.
Heck, stacks themselves can be implemented in terms of other things...
and have been on machines that didn't directly support such a thng as a
stack. For that matter, Fortran programmers have been implementing
stacks in Fortran for longer than I have been proggramming (about 40
years) without needing recursion or other explicit language support for
stacks.

--
Richard Maine | Good judgement comes from experience;
email: last name at domain . net | experience comes from bad judgement.
domain: summertriangle | -- Mark Twain

glen herrmannsfeldt

2008-01-15, 7:16 pm

Richard Maine wrote:
(snip)

> And no, implementation of recursion does not inherently require stacks.
> That just happens to be an obvious and relatively simple way to do it.
> Heck, stacks themselves can be implemented in terms of other things...
> and have been on machines that didn't directly support such a thng as a
> stack. For that matter, Fortran programmers have been implementing
> stacks in Fortran for longer than I have been proggramming (about 40
> years) without needing recursion or other explicit language support for
> stacks.

IBM S/360 and S/370 don't have stack hardware. It is possible to
implement a stack in software, but that wasn't usual for the IBM
supplied systems. The system standard calling convention uses a
linked list including the register save area and return address.
For Fortran before recursion the save areas were statically allocated.
For languages that allowed recursion save areas were dynamically
allocated, (usually) along with the local variables for the called
routine.

Using a linked list instead of a stack has an advantage in not
having to anticipate the size needed in advance. Also, it is
possible to call another main program using the same calling
convention.

Linux/390 (on ESA/390, a descendant of S/370) I believe does
use a stack, as would be usual for other Linux systems.

-- glen

Reagan Revision

2008-01-18, 4:31 am

"glen herrmannsfeldt" <gah@ugcs.caltech.edu> wrote in message
news:Ia-dncfku6eQixDanZ2dnUVZ_g-dnZ2d@comcast.com...
> Richard Maine:
(snip)

[re-ordered for thematic reasons][color=darkred]
> IBM S/360 and S/370 don't have stack hardware. It is possible to
> implement a stack in software, but that wasn't usual for the IBM
> supplied systems. The system standard calling convention uses a
> linked list including the register save area and return address.
> For Fortran before recursion the save areas were statically allocated.
> For languages that allowed recursion save areas were dynamically
> allocated, (usually) along with the local variables for the called
> routine.

> Linux/390 (on ESA/390, a descendant of S/370) I believe does
> use a stack, as would be usual for other Linux systems.
You cite examples of machines without stack hardware. Furthermore they look
fossils. Did something close to standard fortran run on these machines?

> Using a linked list instead of a stack has an advantage in not
> having to anticipate the size needed in advance. Also, it is
> possible to call another main program using the same calling
> convention.
Is that why they never stop talking about linked lists in the C community:
that it's how their syntax does a stack?

--

Reagan Revision

To sum up: 1. The cosmos is a gigantic fly-wheel making 10,000 revolutions a
minute. 2. Man is a sick fly taking a dizzy ride on it. 3. Religion is the
theory that the wheel was designed and set spinning to give him the ride.
-- H L Mencken, "Coda," in Smart Set (New York, Dec. 1920; repr. in A
Mencken Chrestomathy, pt. 1, 1949).

David Flower

2008-01-18, 4:31 am

On Jan 18, 5:10=EF=BF=BDam, "Reagan Revision" <invalid.net> wrote:
> "glen herrmannsfeldt" <g...@ugcs.caltech.edu> wrote in message
>
> news:Ia-dncfku6eQixDanZ2dnUVZ_g-dnZ2d@comcast.com...> Richard Maine:
>
> (snip)
>
[color=darkred]
[color=darkred]
[color=darkred]
>
> [re-ordered for thematic reasons]
>
o[color=darkred]
[color=darkred]
>
> You cite examples of machines without stack hardware. =EF=BF=BDFurthermore=
they look
> fossils. =EF=BF=BDDid something close to standard fortran run on these mac=
hines?
>
>
> Is that why they never stop talking about linked lists in the C community:=

> that it's how their syntax does a stack?
>
> --
>
> Reagan Revision
>
> To sum up: 1. The cosmos is a gigantic fly-wheel making 10,000 revolutions=
a
> minute. 2. Man is a sick fly taking a dizzy ride on it. 3. Religion is the=

> theory that the wheel was designed and set spinning to give him the ride.
> -- H L Mencken, "Coda," in Smart Set (New York, Dec. 1920; repr. in A
> Mencken Chrestomathy, pt. 1, 1949).

I have programmed in Fortran on an IBM 360/95. This was in the late
1960's, using a subset of FORTRAN 66 (to start with, no logical IF
statements). The machine had 4.5MByte of memory (called 'core' in
those days), which was at the time awesomely huge. It shows how far
technology has gone that I have just purchased a 4MByte memory stick
for my wife's digital camera for under =EF=BF=BD30 ($60).

Dave Flower

Regan Revised

2008-01-18, 8:13 am

"David Flower" <DavJFlower@aol.com> wrote in message
news:44678e6f-f4cf-4ddf-8c60-8aa70afebb90@s13g2000prd.googlegroups.com...
On Jan 18, 5:10?am, "Reagan Revision" <invalid.net> wrote:
> "glen herrmannsfeldt" <g...@ugcs.caltech.edu> wrote in message
>
> news:Ia-dncfku6eQixDanZ2dnUVZ_g-dnZ2d@comcast.com...> Richard Maine:
>
> (snip)
>
>
> [re-ordered for thematic reasons]
>
>
> You cite examples of machines without stack hardware. ?Furthermore they
> look
> fossils. ?Did something close to standard fortran run on these machines?
>
>
> Is that why they never stop talking about linked lists in the C community:
> that it's how their syntax does a stack?
>
> --
>
> Reagan Revision
>
> To sum up: 1. The cosmos is a gigantic fly-wheel making 10,000 revolutions
> a
> minute. 2. Man is a sick fly taking a dizzy ride on it. 3. Religion is the
> theory that the wheel was designed and set spinning to give him the ride.
> -- H L Mencken, "Coda," in Smart Set (New York, Dec. 1920; repr. in A
> Mencken Chrestomathy, pt. 1, 1949).

I have programmed in Fortran on an IBM 360/95. This was in the late
1960's, using a subset of FORTRAN 66 (to start with, no logical IF
statements). The machine had 4.5MByte of memory (called 'core' in
those days), which was at the time awesomely huge. It shows how far
technology has gone that I have just purchased a 4MByte memory stick
for my wife's digital camera for under ?30 ($60).

Dave Flower

--->Interesting. I don't recall you from the somewhat recent thread
regarding the age of c.l.f. respondents. At the time, I posited that
someone would come in higher than Terence. If you were programming in the
sixties you /could/ beat 73, a sopposed to just moving up the mean from
49.5.

One thing I found on arrival here in NM was an old IBM fortran manual. I
would claim, without knowing better than what LeRoy Wentz taught me--happy
71 pal--is that IBM was the pre-standard standard.
--

Reagan Revision
ps I think that the rectangle that

usenet before the 30 was euros.

To sum up: 1. The cosmos is a gigantic fly-wheel making 10,000 revolutions a
minute. 2. Man is a sick fly taking a dizzy ride on it. 3. Religion is the
theory that the wheel was designed and set spinning to give him the ride.
-- H L Mencken, "Coda," in Smart Set (New York, Dec. 1920; repr. in A
Mencken Chrestomathy, pt. 1, 1949).

David Flower

2008-01-18, 7:15 pm

On Jan 18, 10:58=EF=BF=BDam, "Regan Revised" <inva...@invalid.net> wrote:
> "David Flower" <DavJFlo...@aol.com> wrote in message
>
> news:44678e6f-f4cf-4ddf-8c60-8aa70afebb90@s13g2000prd.googlegroups.com...
> On Jan 18, 5:10?am, "Reagan Revision" <invalid.net> wrote:
>
>
>
>
>
>
>
>
s.[color=darkred]
..[color=darkred]
..[color=darkred]
a[color=darkred]
or[color=darkred]
>
>
[color=darkred]
>
[color=darkred]
>
>
y:[color=darkred]
>
>
>
ns[color=darkred]
he[color=darkred]
..[color=darkred]
>
> I have programmed in Fortran on an IBM 360/95. This was in the late
> 1960's, using a subset of FORTRAN 66 (to start with, no logical IF
> statements). The machine had 4.5MByte of memory (called 'core' in
> those days), which was at the time awesomely huge. It shows how far
> technology has gone that I have just purchased a 4MByte memory stick
> for my wife's digital camera for under ?30 ($60).
>
> Dave Flower
>
> --->Interesting. =EF=BF=BDI don't recall you from the somewhat recent thre=
ad
> regarding the age of c.l.f. respondents. =EF=BF=BDAt the time, I posited t=
hat
> someone would come in higher than Terence. =EF=BF=BDIf you were programmin=
g in the
> sixties you /could/ beat 73, a sopposed to just moving up the mean from
> 49.5.
>
> One thing I found on arrival here in NM was an old IBM fortran manual. =EF=
=BF=BDI
> would claim, without knowing better than what LeRoy Wentz taught me--happy=

> 71 pal--is that IBM was the pre-standard standard.
> --
>
> Reagan Revision
> ps I think that the rectangle that

usenet before the 30 was euros=
..

No, it was a Pound sign

Dave Flower (Aged sixty three and a half)

>
> To sum up: 1. The cosmos is a gigantic fly-wheel making 10,000 revolutions=
a
> minute. 2. Man is a sick fly taking a dizzy ride on it. 3. Religion is the=

> theory that the wheel was designed and set spinning to give him the ride.
> -- H L Mencken, "Coda," in Smart Set (New York, Dec. 1920; repr. in A
> Mencken Chrestomathy, pt. 1, 1949).- Hide quoted text -
>
> - Show quoted text -

glen herrmannsfeldt

2008-01-18, 7:15 pm

David Flower wrote:
(snip)

> I have programmed in Fortran on an IBM 360/95. This was in the late
> 1960's, using a subset of FORTRAN 66 (to start with, no logical IF
> statements). The machine had 4.5MByte of memory (called 'core' in
> those days), which was at the time awesomely huge. It shows how far
> technology has gone that I have just purchased a 4MByte memory stick
> for my wife's digital camera for under ï¿½30 ($60).

The OS/360 compilers (G and H) supported the full Fortran 66 standard
with a small number of extensions. I would expect one of those by the
time the 360/95 came out.

The DOS/360 Fortran compiler (I believe E, but maybe D) may have
been a subset, but I would be really surprised to see DOS/360
running on a 360/95.

-- glen

glen herrmannsfeldt

2008-01-18, 10:14 pm

Reagan Revision wrote:

(snip)

> You cite examples of machines without stack hardware. Furthermore they look
> fossils. Did something close to standard fortran run on these machines?

S/360 may be a fossil, but z/Architecture is a descendant of it.

Fortran was very popular on S/360. The OS/360 compilers
version of Fortran IV was standard Fortran 66 with a relatively
small number of extensions (compared to many other contemporary
implementations).

Before 1966, IBM was the Fortran standard.

-- glen

Regan Revised

2008-01-19, 7:12 pm

"David Flower" <DavJFlower@aol.com> wrote in message
news:10589ce6-b05b-4c9f-8a93-0a649c7f0e47@h11g2000prf.googlegroups.com...
On Jan 18, 10:58?am, "Regan Revised" <inva...@invalid.net> wrote:
> "David Flower" <DavJFlo...@aol.com> wrote in message
>
> news:44678e6f-f4cf-4ddf-8c60-8aa70afebb90@s13g2000prd.googlegroups.com...
> On Jan 18, 5:10?am, "Reagan Revision" <invalid.net> wrote:

> I have programmed in Fortran on an IBM 360/95. This was in the late
> 1960's, using a subset of FORTRAN 66 (to start with, no logical IF
> statements). The machine had 4.5MByte of memory (called 'core' in
> those days), which was at the time awesomely huge. It shows how far
> technology has gone that I have just purchased a 4MByte memory stick
> for my wife's digital camera for under ?30 ($60).
>
> Dave Flower
>
> --->Interesting. ?I don't recall you from the somewhat recent thread
> regarding the age of c.l.f. respondents. ?At the time, I posited that
> someone would come in higher than Terence. ?If you were programming in the
> sixties you /could/ beat 73, a sopposed to just moving up the mean from
> 49.5.
>
> One thing I found on arrival here in NM was an old IBM fortran manual. ?I
> would claim, without knowing better than what LeRoy Wentz taught me--happy
> 71 pal--is that IBM was the pre-standard standard.
> --
>
> Reagan Revision
> ps I think that the rectangle that

usenet before the 30 was
> euros.

No, it was a Pound sign

Dave Flower (Aged sixty three and a half)
--->I meant to write pounds despite having written euros. I'm actually
surprised that pounds haven't gone the way of the mark, with the grief that
John Major was taking about it. I suppose he's now 2 p.m.'s different, so
it may be a non-issue now. BTW, can you see my pound: £ instead of a
rectangle?

63 and change is not enough to beat Terence but is sufficient to move the
average age to fifty. Thanks a lot, Dave.

I wouldn't miss a stack until a program simply didn't run. How the heck did
you get along without if?

--

Regan R.

Deep within the heart of every evangelist lies the wreck of a car salesman.
-- H L Mencken, describing the Christian author Ray Comfort.

Regan Revised

2008-01-20, 4:28 am

herrmannsfeldt" <gah@ugcs.caltech.edu> wrote in message
news:noSdnSRSPP8pwAzanZ2dnUVZ_g2dnZ2d@co
mcast.com...
> Reagan Revision wrote:
>
> (snip)
>
>
> S/360 may be a fossil, but z/Architecture is a descendant of it.
>
> Fortran was very popular on S/360. The OS/360 compilers
> version of Fortran IV was standard Fortran 66 with a relatively
> small number of extensions (compared to many other contemporary
> implementations).
>
> Before 1966, IBM was the Fortran standard.

66 was the year of my birth, so I'll make fictitious claims to contributions
to mathematical computer science by virtue of this coincidence. Revision is
in fashion.

I tried to educate myself on this and found:
http://en.wikipedia.org/wiki/OS/360

When we then read of System/370 and virtual memory operating systems, do we
get a stack?
--

Regan R.

Deep within the heart of every evangelist lies the wreck of a car salesman.
-- H L Mencken, describing the Christian author Ray Comfort.

John Harper

2008-01-21, 7:29 pm

In article <10589ce6-b05b-4c9f-8a93-0a649c7f0e47@h11g2000prf.googlegroups.com>,
David Flower <DavJFlower@aol.com> wrote:
>
>No, it was a Pound sign

Of the UK kind! In USA the pound sign is totally different, comes after
the number not before it, and it means pounds avoirdupois, not sterling.

-- John Harper, School of Mathematics, Statistics and Computer Science,
Victoria University, PO Box 600, Wellington 6140, New Zealand
e-mail john.harper@vuw.ac.nz phone (+64)(4)463 5662 fax (+64)(4)463 5045

glen herrmannsfeldt

2008-01-22, 7:27 pm

Regan Revised wrote:
(snip)

> 66 was the year of my birth, so I'll make fictitious claims to contributions
> to mathematical computer science by virtue of this coincidence. Revision is
> in fashion.

> I tried to educate myself on this and found:
> http://en.wikipedia.org/wiki/OS/360

> When we then read of System/370 and virtual memory operating
> systems, do we get a stack?

No. I believe the stack (BAKR and PR) was added in ESA/390,
and even then isn't the stack that C programmers expect.
BAKR does subroutine linkage, but arguments are passed separately.

-- glen

Gerry Ford

2008-01-26, 4:29 am

"glen herrmannsfeldt" <gah@ugcs.caltech.edu> wrote in message
news:1-6dnUoKWIhWzAvanZ2dnUVZ_qiinZ2d@comcast.com...
> Regan Revised wrote:
> (snip)
>
>
>
>
> No. I believe the stack (BAKR and PR) was added in ESA/390,
> and even then isn't the stack that C programmers expect.
> BAKR does subroutine linkage, but arguments are passed separately.
Yeah. I re-read Heathfield in Unleashed about the stack and think that the
connection I imagined to machines is wrong-headed. It's funny how abstract
notions are "concrete" in the minds of dreamers. Henry Eyring would see the
molecules of varying energies like seating at the opera.

Fortran: Born with me. :-)

--
The most common of all follies is to believe passionately in the palpably
not true. It is the chief occupation of mankind.
-- H L Mencken, A Mencken Chrestomathy (1949)

Sponsored Links