8 Likes
Nice tutorial, Brad. I’m glad you didn’t opt for the obvious things like a linked list or a BST, since you can find those in many textbooks. On the other hand, the Fibonacci calculation felt a bit silly to me. I understand your goal is to illustrate the technique on a familiar calculation, but it felt like a lot of scaffolding compared to just writing a recursive function. It’s not obvious to me after watching which types of problems are worth the extra labor of defining 3+ classes and overriding procedures, etc. Which of your projects make use of this pattern? It would be interesting to see how you use this in “real” code.
Seems like the branches of the tree structure could be evaluated in parallel. Any Fortran example doing this?
At an OpenMP seminar I attended they had some nice examples of using tasks to achieve this; here is an excerpt from the slides belonging to the Leibniz Supercomputing Centre:
4 Likes
Glad you liked it. Vegetables and jsonff both make use of recursive data structures. and parff can be used to build one up, which is what jsonff uses.
@rouson and I have aspirations of writing a task scheduling library in pure Fortran, and you just gave me the idea that this example could be extended to demonstrate its use. Unfortunately I don’t have any estimate for when that might be done.
1 Like
I had the very same thought. Modern Fortran can do with continuous good advertisement and computations such as the Fibonacci sequence are nice, compact illustrators of other capabilities in Fortran such as with improved support starting Fortran 95 but ongoing with the current standard revision toward the functional programming paradigm e.g., all procedures are now recursive by default, elemental, etc.:
print *, "32nd in Fibonacci sequence = ", fibonacci_number(32), "; expected is 2178309"
contains
elemental integer function fibonacci_number( n ) result(num)
integer, intent(in) :: n
select case ( n )
case ( 0:1 )
num = n
case default
num = fibonacci_number(n-1) + fibonacci_number(n-2)
end select
end function
end
C:\Temp>ifort /standard-semantics fibonacci.f90
Intel(R) Fortran Intel(R) 64 Compiler Classic for applications running on Intel(R) 64, Version 2021.3.0 Build 20210609_000000
Copyright (C) 1985-2021 Intel Corporation. All rights reserved.Microsoft (R) Incremental Linker Version 14.29.30038.1
Copyright (C) Microsoft Corporation. All rights reserved.-out:fibonacci.exe
-subsystem:console
fibonacci.objC:\Temp>fibonacci.exe
32nd in Fibonacci sequence = 2178309 ; expected is 2178309C:\Temp>
When it comes to a tutorial toward recursive data structures in Fortran, my 2 cents is a more conventional example - say with a stack use case - will be apt.
1 Like
I have a stack example, and a couple of exercises to go with it in my course, Intermediate Fortran
type :: domain
type(domain), allocatable :: subdomains(:)
...
end type domain
is a common pattern in numerical weather prediction models that use nests to incrementally refine the grid resolution.
4 Likes
Should not be:
elemental recursive integer function …
?
I thought elemental and recursive are mutually exclusive, but I’m far from an expert of the standard.
Intel says
The Fortran 2018 Standard specifies that the default mode is recursion; previous standards specified the default was no recursion.
and they describe how their compiler handles this. Gfortran 12.0.0 20210718 from equation.com still requires functions that use recursion to be declared recursive, so for the code
module foo
implicit none
contains
integer function fibonacci(n) result(fib)
integer, intent(in) :: n
if (n == 0) then
fib = 0
else if (n == 1) then
fib = 1
else
fib = fibonacci(n-1) + fibonacci(n-2)
end if
end function fibonacci
end module foo
it says
fib1.f90:11:36:
11 | fib = fibonacci(n-1) + fibonacci(n-2)
| 1
Error: Function 'fibonacci' at (1) cannot be called recursively, as it is not RECURSIVE
IBM says
If the ELEMENTAL prefix specifier is used, the RECURSIVE specifier cannot be used.
I will avoid elemental functions that use recursion until gfortran supports the default recursive behavior of F2018.
cc: @Jamie , @epagone @Beliavsky
Please note the bit about current standard revision in my description. The code I showed upthread indeed conforms to the current Fortran standard. If your basis is gfortran which has gaps relative to current standard and has outstanding support requests with Bugzilla among other things with Fortran 2003 and 2008 features, please work with what is supported by that compiler while you take note the current standard may have other facilities.
Readers should take a look at this not-so-recent thread from comp,lang.fortran:
https://groups.google.com/g/comp.lang.fortran/c/4Pxokm3EA24/m/QF8nwjFDw84J
More the things change with Fortran, the more they stay the same!
It is truly not much of a leap to take the position jumping off the quoted snip above to “avoid” modern Fortran, or even Fortran altogether, if one takes stock of the state of affairs!
You linked to a 2013 comp.lang.fortran post by Terence, who wrote that few post-F77 features were needed, such as
(E.g. 'IMPLICIT NONE', the ability to perform bit-wise logic, and the
IF..THEN..ELSE. ENDIF paragraph in particular).And very important, the
ability to use unformatted streams of data ('BINARY' or 'TRANSPARENT'
attributes)
In 2013 there were many Fortran 95 compilers (I don’t remember the state of F2003 compliance at that time.) available, including the free g95 and gfortran, yet Terence recommended avoiding most F95 features. That is needlessly conservative IMO, but waiting for at least 2 compilers to implement a feature before you use it in production is reasonable, especially if the feature’s benefit is marginal.
“waiting for at least 2 compilers to implement a feature” is “needlessly conservative”, IMO. Especially on Windows OS where 100x or more billions of $$ of work is done where there is only one compiler.
Separately if you base matters on gfortran, that essentially places you in the position of sticking to some arbitrary keystone and circling around it, whatever that be. For the comp.lang.fortran thread, that keystone was FORTRAN 77 plus that OP’s pet features. But you can pick your own “poison”, Fortran 95 or whatever. Otherwise with anything else, you can’t go with a “tickmark” in any compiler support list (ACM Fortran or FortranPlus.co.uk or whatever) and run with it. Like in this comment of yours, you will soon be “fed up with … compilers that claim support for a feature, but have a half-assed implementation that only works for simple usage and fails badly for more complex usage”
The bottom-line is the comp.lang.fortran post I linked starts with “a constant series of problems” and that’s otherwise the constant world of Fortran.
A far more preferable approach, I firmly believe, is to forge ahead with the standard and making the processor implementations to follow; the processor shown upthread with the Fibonacci sequence example has been really good at it of late, supporting all of current standard (bugs notwithstanding for which they constantly face a barrage of support requests from me which they gamely fix rather quickly too). Employing that processor for “good” advertisement of Fortran is all that makes sense now.
Then, Intel compiler accepts lack of recursive keyword in function definition only if /standard-semantics option is explicitly used. Option /stand:f18 , which is default BTW, gives error about recursion used, which is wrong.