Fortran Linked List Program: Understand Logic & Assembly

[zmth]

CAn anyone explain how this program in Fortran on linked lists is supposed to work. Actually it does work but I can not for the life of me follow the logic behind it or what is going on. I did some Fortran programming in F77 but now with this new 'pointer' type it is about impossible to understand. I have done assembly language programming so if one could translate how this is translated to assembly language of the microprocessor then i may be able to understand. Like what memory locations and what is being put in them and what is being read from the locations.

program linkedlist
    implicit none

    type :: link
        integer :: i
        type (link), pointer :: next
    end type link

    type (link), pointer :: first, current

    integer :: number

    nullify (first)
    nullify (current)

    ! read in a number, until 0 is entered
    do
        read*, number

        if (number == 0) then
            exit
        end if

        allocate (current) ! create new link
        current%i = number
        current%next => first ! point to previous link
        first => current ! update head pointer
    end do

    ! print the contents of the list
    current => first ! point to beginning of the list

    do
        if (.not. associated (current)) then ! end of list reached
            exit
        end if

        print*, current%i

        current => current%next ! go the next link in the list
    end do

end program linkedlist

One big problem is that if i change the => to just = then it does not work ! HOw can => mean anything other than = ? And if i change the statement current%i = number to
current%i = pointer then it does NOT work. CAn anyone explain why not ? Why does
current%i = number work and current%i = pointer NOT work.

 

[jedishrfu]

I adjusted your post to use fortran syntax coloring. and some indentation for readability.

That will help other posters with reading it.

The statement "current => current%next" assign the value of next to the current. "current%next" contains the address of the next element in the linked and so it points to the next element of the linked list.

 

[rcgldr]

It might help to compare Fortran syntax for pointer usage versus the equivalent C syntax:

    integer, pointer :: ptr0_to_int
    integer, pointer :: ptr1_to_int
    allocate (ptr0_to_int)
    ptr1_to_int => ptr0_to_int
    ptr1_to_int = 5

    int *ptr0_to_int;
    int *ptr1_to_int;
    ptr0_to_int = malloc(sizeof(int));
    ptr1_to_int = ptr0_to_int;
    *ptr1_to_int = 5;

For pointers, Fortran a => b is like C a = b, and Fortran a = b is like C *a = b.

 

[gsal]

Even if you don't know Fortran (which apparently you do not), if you know what the program does, you should be able to get the gist of it with a simple detective mind. The C comparison probably does not help, not to mention is not the same as it does not include a struct with an integer and, in turn, a pointer to the same struct.

"type link" (notice there shouldn't be :: in between) starts a custom type definition block, basically a "struct"...it is a container for other variables and objects...in this case for an integer and a pointer which can point to "link" kind of objects (like itself)...this is how you construct the link list.

If you are new to programming, to better understand the logic you really need to follow the loop with paper and pencil for two or three iterations and noting what is what, what stores what and what points to what...this thing about re-using a variable to store a value from the current loop for use in the next loop, makes it be the value from the "previous" loop once the "next" loop is actually the "current" loop...follow? ;-)

Think of the "type link" as a drawer with string (rope) on one side...you can put an integer in the drawer and then you can use the string to attach it to the next drawer.

Unlike an integer which comes already with its own memory, pointers need to be allocated.

Hope this helps.

 

[zmth]

I adjusted your post to use fortran syntax coloring. and some indentation for readability.

That will help other posters with reading it.

The statement "current => current%next" assign the value of next to the current. "current%next" contains the address of the next element in the linked and so it points to the next element of the linked list.

I see the current%next in the definition though I don't understand what it means but anyway..., BUT now what about the statement current%i=number ? NOwhere in the definition do I see anything with an " i " nor %i so how is this valid ?

 

[SteamKing]

CAn anyone explain how this program in Fortran on linked lists is supposed to work. Actually it does work but I can not for the life of me follow the logic behind it or what is going on. I did some Fortran programming in F77 but now with this new 'pointer' type it is about impossible to understand. I have done assembly language programming so if one could translate how this is translated to assembly language of the microprocessor then i may be able to understand. Like what memory locations and what is being put in them and what is being read from the locations.

If you've done Fortran 77 programming, you should know how old that language version is.

Starting with Fortran 90/95, the language standard changed quite a bit, although Fortran 77 is included as a subset language to help keep older programs written in that version from having to be re-written to remain compatible with the new standard.

These links may help you keep up to date with the new Fortran language features:

http://www.astro.ex.ac.uk/people/saunders/computing_tutorials/fortran.pdf

http://www.star.le.ac.uk/~cgp/f90course/f90.html

http://www.urz.uni-heidelberg.de/Dok/Fortran90forF77.html

There's quite a bit of new stuff to learn, and it will take more than a couple of days to do it. Good Luck!

 

[zmth]

Even if you don't know Fortran (which apparently you do not), if you know what the program does, you should be able to get the gist of it with a simple detective mind. The C comparison probably does not help, not to mention is not the same as it does not include a struct with an integer and, in turn, a pointer to the same struct.

"type link" (notice there shouldn't be :: in between) starts a custom type definition block, basically a "struct"...it is a container for other variables and objects...in this case for an integer and a pointer which can point to "link" kind of objects (like itself)...this is how you construct the link list.

If you are new to programming, to better understand the logic you really need to follow the loop with paper and pencil for two or three iterations and noting what is what, what stores what and what points to what...this thing about re-using a variable to store a value from the current loop for use in the next loop, makes it be the value from the "previous" loop once the "next" loop is actually the "current" loop...follow? ;-)

Think of the "type link" as a drawer with string (rope) on one side...you can put an integer in the drawer and then you can use the string to attach it to the next drawer.

Unlike an integer which comes already with its own memory, pointers need to be allocated.

Hope this helps.

That is right I don't understand Fortran at least as far as this part of the newer version esp 'pointer' and the => . I thought i did understand for the most part Fortran77 though a bit rusty on it. I do basically understand a 'recursive' procedure at least in the simplest most direct cases but this whole thing seems like ' black magic '.
I have done recursive programs in Maxima . If anyone is familiar or used Maxima could you write a routine in Maxima which would accomplish the same ? Or even a routine written in Fortran 77, say in free field form for simplicity, which would accomplish the same.

About the ' :: ' I do see it works without it also. Which brings up a new question as to what exactly does ' :: ' mean in general ? I was able to do all my programs in Fortran 77 mostly in the '90's without having to use the " :: " .

 

[zmth]

That is right I don't understand Fortran at least as far as this part of the newer version esp 'pointer' and the => . I thought i did understand for the most part Fortran77 though a bit rusty on it. I do basically understand a 'recursive' procedure at least in the simplest most direct cases but this whole thing seems like ' black magic '.
I have done recursive programs in Maxima . If anyone is familiar or used Maxima could you write a routine in Maxima which would accomplish the same ? Or even a routine written in Fortran 77, say in free field form for simplicity, which would accomplish the same.

About the ' :: ' I do see it works without it also. Which brings up a new question as to what exactly does ' :: ' mean in general ? I was able to do all my programs in Fortran 77 mostly in the '90's without having to use the " :: " .

Also for example could anyone write code in F77 using ' equivalence ' which would do the same ?

 

[jedishrfu]

I see the current%next in the definition though I don't understand what it means but anyway..., BUT now what about the statement current%i=number ? NOwhere in the definition do I see anything with an " i " nor %i so how is this valid ?

Look at the type definition earlier in your program, each node of the linked list has a field called "i" as well as a field called "next" which is a pointer to another node in the linked list:

   type::link
       integer::i
       type(link), pointer::next
   endtype link

 

[rcgldr]

Unlike an integer which comes already with its own memory, pointers need to be allocated.

The pointer comes with it's own memory, but not what it points to. Based on what I've seen of Fortran examples using pointers, It's an unitialized pointer when it's declared. nullify() can be used to set a pointer to NULL (is this the same as zero in Fortran?), or allocate() can be used to allocate memory and set the pointer to point to that allocated memory.

 

[zmth]

I see the current%next in the definition though I don't understand what it means but anyway..., BUT now what about the statement current%i=number ? NOwhere in the definition do I see anything with an " i " nor %i so how is this valid ?

Oh ;my mistake now i do see the " i " .

 

[zmth]

Does this linked list take up more memory than a conventional array with the same entries ?

 

[256bits]

Does this linked list take up more memory than a conventional array with the same entries ?

Well, what does an array store as its values?
What does the linked list store as its values?
( for the linked list see the type :: link near the top of your program. )

 

[gsal]

The pointer comes with it's own memory, but not what it points to. Based on what I've seen of Fortran examples using pointers, It's an unitialized pointer when it's declared. nullify() can be used to set a pointer to NULL (is this the same as zero in Fortran?), or allocate() can be used to allocate memory and set the pointer to point to that allocated memory.

You are correct. What I said was within the context of storing data in the pointer itself as in the example at hand (the linked list above), in these cases, you need to allocate memory using the pointer itself. Otherwise, the pointer comes ready to point to already allocated targets...where 'target' is the attribute that needs to be given to the variable/object you want to point to.

One interesting thing that helps performance is that pointers must have a type. In other words, if you want a pointer to point to an integer, you need to indicate so in the declaration statement for the pointer. This can clearly be seen in the linked list example above: the pointer is declared with "type(link)"...this is also why you can simply use " allocate(ptr)" on a pointer and you don't have to worry about how much memory you need for the item...the compiler already knows.

Does this linked list take up more memory than a conventional array with the same entries ?

By conventional array you mean an array of one of the native types? integer? real? Because you can just as easily have an array of a user defined type. Anyway, I don't know why you are even worried about memory if what you need cannot be done with a conventional array, it is not like you have choice.

Also, please stop using dirty words like equivalence and, please, move up to modern Fortran, we have had it for 20 years already, it is so much more...while it may be a natural progression, you really need to read up on it.

 

[zmth]

Yes i mean array of native type say of integers for example I post another more direct program and see if someone can explain some of the observations I have made about it.
----------------------------------------------
integer*1 i
type link
integer*1 i
type (link), pointer:: next
end type link
type (link), pointer :: first,current
nullify (first)
nullify (current)

do i=1,11
allocate (current)
current%i =i
current%next =>first
first =>current
end do
current => first
do
if (.not. associated (current)) then
exit
end if
print*, current%i
current => current%next
end do
end
---------------------------------------------------------

First of all the numbers are printed out in descending order - opposite to the order they were put in : as if they were pushed on to a stack or something which is
not the case here. In the loop statement it is continuously allocated over and again without ever any statement to be deallocated. How can this be done without error?
In the statement "if (.not. associated (current)) then.." How did it ever not get associated if it ever once was ?

 

[gsal]

But it is the case...you started the list from the bottom up by starting the list with %i=1 and having %next point to the "tail" (the not associated, nullified, initial first) of the list...and THEN, you moved up to %i=2 and had that point to the link with %i=1 (the one from the previous iteration) and so on...at the very end, the last link allocated and assigned %i=11 is what you had first point to right before exiting the loop and then you had current point to that...and this is the one you start printing with...

 

[zmth]

Yes i mean array of native type say of integers for example I post another more direct program and see if someone can explain some of the observations I have made about it.
----------------------------------------------
integer*1 i
type link
integer*1 i
type (link), pointer:: next
end type link
type (link), pointer :: first,current
nullify (first)
nullify (current)

do i=1,11
allocate (current)
current%i =i
current%next =>first
first =>current
end do
current => first
do
if (.not. associated (current)) then
exit
end if
print*, current%i
current => current%next
end do
end
---------------------------------------------------------

First of all the numbers are printed out in descending order - opposite to the order they were put in : as if they were pushed on to a stack or something which is
not the case here. In the loop statement it is continuously allocated over and again without ever any statement to be deallocated. How can this be done without error?
In the statement "if (.not. associated (current)) then.." How did it ever not get associated if it ever once was ?

 

[zmth]

There is also the question of for example
integer*1:: i
integer*1 :: j,k

is same as putting all together in one statement as
integr*1 :: i,j,k

but here has:
type (link), pointer:: next
end type link
type (link), pointer :: first,current

but if do the same there like put them all together:
type (link), pointer:: next,first,current
get error as do when try to change the order any other way

 

[Mark44]

There is also the question of for example
integer*1:: i
integer*1 :: j,k

is same as putting all together in one statement as
integr*1 :: i,j,k

but here has:
type (link), pointer:: next
end type link
type (link), pointer :: first,current

but if do the same there like put them all together:
type (link), pointer:: next,first,current
get error as do when try to change the order any other way

You can't put them all together. The next variable is a member of your derived type named link. The first and current variables aren't members of your derived type, so have to be declared after the declaration of the link derived type.

 

[zmth]

What is the purpose of
nullify (first)
nullify (current)

and why does it not make the definitions useless or canceled ?

 

[Mark44]

What is the purpose of
nullify (first)
nullify (current)

To disassociate the pointers (first and current) from their targets. See http://www.personal.psu.edu/jhm/f90/statements/nullify.html

and why does it not make the definitions useless or canceled ?

Are you asking about your variables of the user-defined link type? Your two variables above are intended to point to link instances. The nullify statement causes the pointers to not point to anything. It doesn't affect the data being pointed to.