Home > Archive > Fortran > June 2005 > Fortran and simple tree recursion
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Fortran and simple tree recursion
|
|
| Michael Bader 2005-05-24, 8:57 am |
| Hi,
It may sound a bit strange, but I am trying to find the proper
language/compiler for a special type of tree recursion, and I've
been thinking about Fortran (which I'm not at all familiar with ...).
I have several recursive function A(), B(), C(), etc., which will
call each other recursively.
However, I can easily get rid of any local variables or parameters,
or have them as some kind of static parameter (similar to a
call-by-reference parameter).
For reasons of speed, I would like to avoid that the compiler
generates any kind of stack frame. In an assembler setting, I'd just
need the 'call' and 'return' command available in the assembler
language (so only the return address needs to be put onto the stack).
Could I do something like this in Fortran77 or Fortran90?
Or, to put it in another way:
- what kind of code will a Fortran77 compiler produce, if a actually
do use functions that call each other (and themselves).
- can I prevent a Fortran90 compiler to generate a stack frame?
Thanks for any advice
Michael
| |
| Michael Metcalf 2005-05-24, 8:57 am |
|
"Michael Bader" <bader@in.tum.de> wrote in message
news:d6um5p$hci$1@wsc10.lrz-muenchen.de...
> Or, to put it in another way:
> - what kind of code will a Fortran77 compiler produce, if a actually
> do use functions that call each other (and themselves).
> - can I prevent a Fortran90 compiler to generate a stack frame?
>
I can't answer your question about the object code, but you have no standard
method of using recursion in FORTRAN 77. In Fortran 90 it can be done simply
by adding a recursive keyword to the procedure names. You will find examples
in Fortran 95 textbooks, and you can examine the code generated to see if it
satisfies your conditions. Note that each time a recursive procedure is
invoked, a fresh set of local data objects is created, which ceases to exist
on return; dummy arguments and local variables with the save attribute are
not included. If you really are new to Fortran you will need to read up
about it, but you'll always find quick help in c.l.f.
Regards,
Mike Metcalf
| |
| Richard Edgar 2005-05-24, 8:57 am |
| Michael Bader wrote:
> It may sound a bit strange, but I am trying to find the proper
> language/compiler for a special type of tree recursion, and I've
> been thinking about Fortran (which I'm not at all familiar with ...).
> I have several recursive function A(), B(), C(), etc., which will
> call each other recursively.
> However, I can easily get rid of any local variables or parameters,
> or have them as some kind of static parameter (similar to a
> call-by-reference parameter).
>
> For reasons of speed, I would like to avoid that the compiler
> generates any kind of stack frame. In an assembler setting, I'd just
> need the 'call' and 'return' command available in the assembler
> language (so only the return address needs to be put onto the stack).
I'm not quite sure what you're doing here, but if you don't need a new
stack frame (i.e. new procedure invocation, with its own local
variables) on each call, haven't you really got an iterative function,
but which happens to be implemented recursively? Something like
fun facti( x, 1) = x
| facti( x, i) = facti( x*i, i-1);
which is recursive, but _tail_ recursive (apologies for my poor memory
of ML... and probably the odd bit of language terminology)
Richard
| |
| Michael Bader 2005-05-24, 8:57 am |
| Richard Edgar wrote:
> I'm not quite sure what you're doing here, but if you don't need a new
> stack frame (i.e. new procedure invocation, with its own local
> variables) on each call, haven't you really got an iterative function,
> but which happens to be implemented recursively? Something like
>
> fun facti( x, 1) = x
> | facti( x, i) = facti( x*i, i-1);
>
> which is recursive, but _tail_ recursive (apologies for my poor memory
> of ML... and probably the odd bit of language terminology)
Well, the problem is that the recursion is not tail recursive but tree
recursive. So, it's not easy to come up with an iterative variant.
Think about a construction like this:
proc A(x, depth)
return if depth=0
call B(x, depth-1);
call C(x, depth-1);
call A(x, depth-1);
... do something on x
end proc;
B(...) and C(...) have a structure that is similar to that of A.
Think of a code, where x could be directly replaced by a global
variable, and the depth-counter could also easily be replaced by
a construction that uses a global variable.
Then, any saving of local variables or parameters on a stack would
be just a waste of time - only the call stack of return addresses
would be required.
Best regards
Michael
| |
| Michael Metcalf 2005-05-24, 8:57 am |
|
"Michael Bader" <bader@in.tum.de> wrote in message
news:d6usal$k8m$1@wsc10.lrz-muenchen.de...
>
> proc A(x, depth)
> return if depth=0
> call B(x, depth-1);
> call C(x, depth-1);
> call A(x, depth-1);
> ... do something on x
> end proc;
>
> B(...) and C(...) have a structure that is similar to that of A.
> Think of a code, where x could be directly replaced by a global
> variable, and the depth-counter could also easily be replaced by
> a construction that uses a global variable.
>
> Then, any saving of local variables or parameters on a stack would
> be just a waste of time - only the call stack of return addresses
> would be required.
>
You mean like this?
Regards,
Mike Metcalf
module stuff
integer :: depth = 0
real :: x = 0.0
contains
recursive subroutine A
if (depth==0) return
depth = depth -1
call B
call C
call A
print *, "I'm in a"
x = x + 1.0
end subroutine a
recursive subroutine b
if (depth==0) return
depth = depth -1
call B
call C
call A
print *, "I'm in b"
x = x + 1.0
end subroutine b
recursive subroutine c
if (depth==0) return
depth = depth -1
call B
call C
call A
print *, "I'm in c"
x = x + 1.0
end subroutine c
end module stuff
program crazy
use stuff
depth = 6
call a
print *, x
end program crazy
| |
| Michael Metcalf 2005-05-24, 8:57 am |
|
"Michael Bader" <bader@in.tum.de> wrote in message
news:d6usal$k8m$1@wsc10.lrz-muenchen.de...
> Richard Edgar wrote:
>
> Well, the problem is that the recursion is not tail recursive but tree
> recursive. So, it's not easy to come up with an iterative variant.
> Think about a construction like this:
>
> proc A(x, depth)
> return if depth=0
> call B(x, depth-1);
> call C(x, depth-1);
> call A(x, depth-1);
> ... do something on x
> end proc;
>
> B(...) and C(...) have a structure that is similar to that of A.
> Think of a code, where x could be directly replaced by a global
> variable, and the depth-counter could also easily be replaced by
> a construction that uses a global variable.
>
> Then, any saving of local variables or parameters on a stack would
> be just a waste of time - only the call stack of return addresses
> would be required.
>
> Best regards
>
> Michael
>
>
| |
|
|
> recursive subroutine A
> if (depth==0) return
> depth = depth -1
> call B
> call C
> call A
> print *, "I'm in a"
> x = x + 1.0
> end subroutine a
>
Be careful when using global variables in recursive subroutines, here
you should add:
> ...
> x = x + 1.0
depth = depth + 1 !<<<<<<<<<<<<< in a,b,c.
> end subroutine a
And I think it is compiler depended how it is translated into machine
language.
| |
| Jon Harrop 2005-05-24, 3:59 pm |
| Michael Bader wrote:
> Richard Edgar wrote:
>
> Well, the problem is that the recursion is not tail recursive but tree
> recursive.
As Richard suggests - you can transform your function into tail-recursive
form so that it is not necessary for the compiler to use the stack.
However, tail-recursion optimisation is mainly done in compilers of modern
languages and may not be done by a Fortran compiler.
> So, it's not easy to come up with an iterative variant.
The CS jargon is "imperative".
> Think about a construction like this:
>
> proc A(x, depth)
> return if depth=0
> call B(x, depth-1);
> call C(x, depth-1);
> call A(x, depth-1);
> ... do something on x
> end proc;
>
> B(...) and C(...) have a structure that is similar to that of A.
> Think of a code, where x could be directly replaced by a global
> variable, and the depth-counter could also easily be replaced by
> a construction that uses a global variable.
>
> Then, any saving of local variables or parameters on a stack would
> be just a waste of time - only the call stack of return addresses
> would be required.
If you use tail calls, they will not need to return and the return address
will not need to be stored.
--
Dr Jon D Harrop, Flying Frog Consultancy
http://www.ffconsultancy.com
| |
| James Van Buskirk 2005-05-24, 8:57 pm |
| "Michael Bader" <bader@in.tum.de> wrote in message
news:d6usal$k8m$1@wsc10.lrz-muenchen.de...
> Then, any saving of local variables or parameters on a stack would
> be just a waste of time - only the call stack of return addresses
> would be required.
On perusing the thread, I noticed that nobody has yet mentioned
the SAVE statement. Just put a SAVE statement in each subroutine
that is not supposed to have variables created on a per-instance
basis, and all variables in that subroutine will then be shared
among all instances of that subroutine. Fortran allows you to
control whether local variables of a recursive procedure (well,
the ones which are not automatic data objects) are private
to the instance or shared among all instances and the SAVE
statement or attribute is the way you achieve that control.
--
write(*,*) transfer((/17.392111325966148d0,6.5794487871554595D-85, &
6.0134700243160014d-154/),(/'x'/)); end
| |
| glen herrmannsfeldt 2005-05-24, 8:57 pm |
| James Van Buskirk wrote:
(previously snipped question regarding recursion in Fortran)
> "Michael Bader" <bader@in.tum.de> wrote in message
> news:d6usal$k8m$1@wsc10.lrz-muenchen.de...
In Fortran 66, which did not have SAVE, it was not unusual to do
static allocation for all variables.
OS/360 Fortran compilers also used static storage to save the return
address. If you did try recursion you would lose the previous return
point.
The PDP-10 (TOPS-10) Fortran compiler used static allocation for
variables, but a stack for return addresses, as the OP asked. I did
once write a recursive routine using arrays for each variable and an
integer variable incremented on entry and decremented before exit,
just to see if it would work.
[color=darkred]
> On perusing the thread, I noticed that nobody has yet mentioned
> the SAVE statement. Just put a SAVE statement in each subroutine
> that is not supposed to have variables created on a per-instance
> basis, and all variables in that subroutine will then be shared
> among all instances of that subroutine. Fortran allows you to
> control whether local variables of a recursive procedure (well,
> the ones which are not automatic data objects) are private
> to the instance or shared among all instances and the SAVE
> statement or attribute is the way you achieve that control.
I believe this is true, though SAVE came in Fortran 77 and recursive
calls didn't come until later. SAVE also allows non-recursive routines
to keep their internal state, such as random number generators keeping
the seed used to generate the next random value.
Arguments will still likely go onto the stack, but, yes, SAVE should
reduce the size of the stack frame required.
-- glen
| |
| Michael Metcalf 2005-05-24, 8:57 pm |
|
"James Van Buskirk" <not_valid@comcast.net> wrote in message
news:q5Wdnf8MBrTu5A7fRVn-tQ@comcast.com...
>
> On perusing the thread, I noticed that nobody has yet mentioned
> the SAVE statement.
It was:
From: "Michael Metcalf" <metcalfmetcalf@compuserve.com>
Subject: Re: Fortran and simple tree recursion
Date: 24 May 2005 10:09
[snip]
Note that each time a recursive procedure is
invoked, a fresh set of local data objects is created, which ceases to exist
on return; dummy arguments and local variables with the save attribute are
not included.
[snip]
Regards,
Mike Metcalf
| |
| e p chandler 2005-05-25, 3:59 am |
|
glen herrmannsfeldt wrote:
> James Van Buskirk wrote:
>
>
> (previously snipped question regarding recursion in Fortran)
>
>
>
> In Fortran 66, which did not have SAVE, it was not unusual to do
> static allocation for all variables.
>
> OS/360 Fortran compilers also used static storage to save the return
> address. If you did try recursion you would lose the previous return
> point.
>
> The PDP-10 (TOPS-10) Fortran compiler used static allocation for
> variables, but a stack for return addresses, as the OP asked. I did
> once write a recursive routine using arrays for each variable and an
> integer variable incremented on entry and decremented before exit,
> just to see if it would work.
>
If memory serves me properly, there were two different Fortran
compilers on the PDP-10. The older one used JSA and JRA instructions,
not a stack. I believe that the later version used PUSHJ and POPJ, but
did something other than simply push the return address onto the stack.
(After 30+ years my memory is a bit foggy.)
| |
| glen herrmannsfeldt 2005-05-25, 3:59 am |
| e p chandler wrote:
(snip)
> If memory serves me properly, there were two different Fortran
> compilers on the PDP-10. The older one used JSA and JRA instructions,
> not a stack. I believe that the later version used PUSHJ and POPJ, but
> did something other than simply push the return address onto the stack.
> (After 30+ years my memory is a bit foggy.)
It would have been about 1978 that I used it.
PUSHJ and POPJ sound familiar, only slightly less than 30 years.
-- glen
| |
| Michael Bader 2005-05-25, 8:57 am |
| FJRA wrote:
>
> Be careful when using global variables in recursive subroutines, here
> you should add:
>
> depth = depth + 1 !<<<<<<<<<<<<< in a,b,c.
That's exactly the way it would be done.
>
> And I think it is compiler depended how it is translated into machine
> language.
So, it might happen that the compiler generates a simple jump in the
machine language instead of a call (with saved return address)?
Michael
| |
| Michael Bader 2005-05-25, 8:57 am |
| James Van Buskirk wrote:
>
> On perusing the thread, I noticed that nobody has yet mentioned
> the SAVE statement. Just put a SAVE statement in each subroutine
> that is not supposed to have variables created on a per-instance
> basis, and all variables in that subroutine will then be shared
> among all instances of that subroutine.
Which seems to be exactly what I need - thanks for the suggestion.
There's just no similar statement in C/C++, or, in fact, any other
programming language I know ...
So I'll probably do a test implementation in Fortran90 (to be save on
the recursion side), a try to exploit the SAVE command.
It'll be interesting to compare the generated code with that obtained
from a C-compiler.
Thanks again
Michael
| |
| Michael Bader 2005-05-25, 8:57 am |
| Jon Harrop wrote:
>
> If you use tail calls, they will not need to return and the return address
> will not need to be stored.
Well, that's exatly the problem - there is no tail recursive version
of this code. Any function will successively call a sequence of other
recursive functions.
Michael
| |
| Jon Harrop 2005-05-25, 8:57 am |
| Michael Bader wrote:
> Jon Harrop wrote:
>
> Well, that's exatly the problem - there is no tail recursive version
> of this code. Any function will successively call a sequence of other
> recursive functions.
In the current form the program must know where to jump to after the first
and second function calls. That information is generated at run-time and so
it must be stored on the stack. The best you can do (assuming you cannot
"factor it out symbolically") is move this information onto your own stack
so that you don't use the system stack. This is equivalent to continuation
passing. SML-NJ does continuation passing for you.
In a functional programming language, the easiest way to implement this is
to pass a list of future tail-calls as a function argument.
Are you doing this to evade the problem of running out of stack with deep
recursions?
--
Dr Jon D Harrop, Flying Frog Consultancy
http://www.ffconsultancy.com
| |
| Jon Harrop 2005-05-25, 8:57 am |
| Michael Bader wrote:
> James Van Buskirk wrote:
>
> Which seems to be exactly what I need - thanks for the suggestion.
> There's just no similar statement in C/C++, or, in fact, any other
> programming language I know ...
The C/C++ equivalent is putting "static" before every local variable
definition.
Modern languages don't let you do this yourself because it breaks
modularity, concurrency, safety, determinism. Instead, it is left as an
optimisation for the compiler to do when it can prove that there are no ill
effects.
--
Dr Jon D Harrop, Flying Frog Consultancy
http://www.ffconsultancy.com
| |
| glen herrmannsfeldt 2005-05-25, 8:57 am |
| Michael Bader wrote:
> James Van Buskirk wrote:
(snip)
[color=darkred]
> Which seems to be exactly what I need - thanks for the suggestion.
> There's just no similar statement in C/C++, or, in fact, any other
> programming language I know ...
Well, in C, and I believe also C++, you would have to put a static
attribute on all variables. It is a convenience of Fortran that a
single SAVE statement applies to all variables.
-- glen
| |
| glen herrmannsfeldt 2005-05-25, 8:57 am |
| Michael Bader wrote:
(snip describing tail recursion)
> So, it might happen that the compiler generates a simple jump in the
> machine language instead of a call (with saved return address)?
I have known it done in assembly, but not by any compilers of high
level languages. It would be interesting to know of compilers that
would do this.
-- glen
| |
| Michael Bader 2005-05-25, 8:57 am |
| Reply-To: mail@michaelbader.de
NNTP-Posting-Host: atsccs15.informatik.tu-muenchen.de
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7Bit
X-Trace: wsc10.lrz-muenchen.de 1117018309 2177 131.159.36.104 (25 May 2005 10:51:49 GMT)
X-Complaints-To: news@lrz-muenchen.de
NNTP-Posting-Date: 25 May 2005 10:51:49 GMT
User-Agent: KNode/0.8.1
Xref: number1.nntp.dca.giganews.com comp.lang.fortran:132183
Jon Harrop wrote:
> In the current form the program must know where to jump to after the first
> and second function calls. That information is generated at run-time and
> so it must be stored on the stack. The best you can do (assuming you
> cannot "factor it out symbolically") is move this information onto your
> own stack so that you don't use the system stack. This is equivalent to
> continuation passing. SML-NJ does continuation passing for you.
>
> In a functional programming language, the easiest way to implement this is
> to pass a list of future tail-calls as a function argument.
>
> Are you doing this to evade the problem of running out of stack with deep
> recursions?
The stack size is actually not a problem at all - the calling tree is not
very deep. It's just that producing the stack frame leads to superfluous
operations in that special code.
In machine code a pure subroutine call would be sufficient - jump to new
address and put the PC counter on the stack.
Building that stack by myself would therefore be of no help. However, the
stack frame is not easily avoided in programming languages. That's why I
thought about Fortran, which has (or used to have) a different concept
for function calls.
Michael
| |
| Michael Bader 2005-05-25, 8:57 am |
| Jon Harrop wrote:
>
> The C/C++ equivalent is putting "static" before every local variable
> definition.
Not quite: I'd need a static that's static to a group of functions, and
not only to one.
> Modern languages don't let you do this yourself because it breaks
> modularity, concurrency, safety, determinism.
Exactly :-) But still it would be very useful in my case.
> Instead, it is left as an
> optimisation for the compiler to do when it can prove that there are no
> ill effects.
Which is almost impossible to grasp by a compiler - recognizing such a
system of nested recursive calls should be quite difficult.
Michael
| |
| Jon Harrop 2005-05-25, 3:58 pm |
| Michael Bader wrote:
> Jon Harrop wrote:
>
> Not quite: I'd need a static that's static to a group of functions, and
> not only to one.
That would need to be a global static in C. It could be an outer-scope
static in C++. In OCaml (or ML) you would write something like:
let a, b, c, d =
let my_static = 1 in
let rec a = ...
and b = ...
and c = ...
and d = ... in
a, b, c, d
So there is only one "my_static" and it is local to a, b, c and d.
I use this style when memoizing a function. The hash table used to store the
memoized results is then local to the function in question but there is
only one such hash table in this scope.
>
> Exactly :-) But still it would be very useful in my case.
Yes.
>
> Which is almost impossible to grasp by a compiler - recognizing such a
> system of nested recursive calls should be quite difficult.
Essentially, tail calls are simply determined by whether or not the result
is returned immediately or used as a subexpression in further computation.
In functional languages (even impure functional languages), recursion is so
common that spotting tail recursion is almost essential. Consequently, most
such compilers spot 99% of tail calls.
--
Dr Jon D Harrop, Flying Frog Consultancy
http://www.ffconsultancy.com
| |
| Jan Vorbrüggen 2005-05-25, 3:58 pm |
| > The stack size is actually not a problem at all - the calling tree is not
> very deep. It's just that producing the stack frame leads to superfluous
> operations in that special code.
> In machine code a pure subroutine call would be sufficient - jump to new
> address and put the PC counter on the stack.
Have you ever checked that the compiler indeed produces unnecessary code
in such cases?
Jan
| |
| glen herrmannsfeldt 2005-05-25, 3:58 pm |
| Michael Bader wrote:
> Jon Harrop wrote:
(snip)
[color=darkred]
> Not quite: I'd need a static that's static to a group of functions, and
> not only to one.
static external, in C a variable or structure declared outside of
any function. If you actually declare it static it is local to
that file, a new definition of the word static.
static external structures are reasonably equivalent to Fortran COMMON.
While the time required to allocate the stack frame might be small,
there could be some savings due to keeping the variables in cache.
That is, many accesses to the same variable tend to be faster than
accesses to many different variables.
-- glen
| |
| Dr Ivan D. Reid 2005-06-01, 8:58 pm |
| On Tue, 24 May 2005 22:15:12 +0200,
Michael Metcalf <metcalfmetcalf@compuserve.com>
wrote in <d701rm$t8l$00$1@news.t-online.com>:
> "James Van Buskirk" <not_valid@comcast.net> wrote in message
> news:q5Wdnf8MBrTu5A7fRVn-tQ@comcast.com...
[color=darkred]
> It was:
> From: "Michael Metcalf" <metcalfmetcalf@compuserve.com>
> Subject: Re: Fortran and simple tree recursion
> Date: 24 May 2005 10:09
> [snip]
> Note that each time a recursive procedure is
> invoked, a fresh set of local data objects is created, which ceases to exist
> on return; dummy arguments and local variables with the save attribute are
> not included.
> [snip]
Shame on you Mike, you know FORTRAN keywords should be capitalised!
<invoke multi-level smilie...>
--
Ivan Reid, Electronic & Computer Engineering, ___ CMS Collaboration,
Brunel University. Ivan.Reid@brunel.ac.uk Room 40-1-B12, CERN
KotPT -- "for stupidity above and beyond the call of duty".
|
|
|
|
|