[comp.lang.fortran] data types without pointers

jlg@lanl.gov (Jim Giles) (09/24/88)

> [...]                             Try representing a dynamic length
> fifo using Hoare's structure and answering the questions:
>
> 1) What happens when I add to a fifo?
> 2) How do I represent this structure?
> 3) How do I keep track of the head/tail?
> 4) How do I detect an empty fifo?

Fifo's _can_ be implemented as recursive data structures, but arrays
with indices are easier and more efficient.  So I'll do that with a
Fortran 8x-like syntax.

      MODULE FIFO           !declare a module full of the FIFO queuing
			    !routines

      Type FIFO
	 integer head=0, tail=0, size=0   ! initialize as well as declare
	 logical full=.true., empty=.true.
	 allocatable real :: data(:)      ! array is dynamic - can be resized
      end type FIFO

      subroutine ADDTO (queue, item) assignment
C     assignment subroutines - all the user says is 'queue = item'

	 FIFO :: queue
	 real item
	 constant integer :: default_increase = 200   !initialize to 200

	 if (queue%full) then
	    queue%size=queue%size+default_increase
	    allocate(queue%data(size))    !I assume that allocate will resize
					  !if the array already existed
	 endif

	 queue%head = queue%head + 1
	 if (queue%head.gt.queue%size) queue%head=1
	 if (queue%head.eq.queue%tail) queue%full=.true.

	 queue%data(queue%head) = item
	 queue%empty=.false.
	 return

      end subroutine ADDTO

      subroutine TAKEFROM (item, queue) assignment
C     All the user says is 'item = queue'

	 FIFO :: queue
	 real item

	 if (queue%empty) then
C           CODE FOR EMPTY QUEUE REQUEST
	 endif

	 queue%tail = queue%tail + 1
	 if (queue%tail.gt.size) queue%tail = 1
	 if (queue%head.eq.queue%tail) queue%empty=.true.

	 item = queue%data(queue%tail)
	 queue%full = .false.

	 return

      end subroutine TAKEFROM

      END MODULE FIFO

      Program FIFO_USER

	 include fifo

	 FIFO :: p, q        !declare two different queues
	 real :: x, y
	 ...
	 p = 5.0             !push 5.0 onto queue p
	 x = p               !get next item off p
	 ...
	 if (p%empty) then   !easy to test if queue is empty
	 ...
      END PROGRAM FIFO_USER

Note: Fortran 8x is not case sensitive but I tried to use the same case
for each item consistently anyway.

Well, there you are.  You even have the assignment operators you asked
for.  There aren't any pointers here either.

> BTW, recursive structures are a very clumsy way to think about bags,

I agree.  So don't implement them with recursive structures.  Recursive
structures aren't for everything.  Use the structure which best fits
the problem.  This means: rarely use pointers - if you can avoid it.
And, if you're talking about language _design_, don't force pointers
onto your users.

> [...]                                                    I said that
> if I don't have the data types and have to build my own abstractions,
> I prefer to use pointers to do it.

And (rather obviously) I'd rather not.  Certainly I don't want something
like C where I get pointers defined automatically every time I delcare
a dynamically allocatable data item - whether I need the pointer or not!
It is better to have different functionality actually have different
syntax as well.  Most uses of pointers are actually something else
in disguise.

J. Giles
Los Alamos

fouts@lemming.nas.nasa.gov.nas.nasa.gov (Marty Fouts) (09/24/88)

In article <4108@lanl.gov> jlg@lanl.gov (Jim Giles) writes:
>
>> [...]                             Try representing a dynamic length
>> fifo using Hoare's structure and answering the questions:
>>
>> 1) What happens when I add to a fifo?
>> 2) How do I represent this structure?
>> 3) How do I keep track of the head/tail?
>> 4) How do I detect an empty fifo?
>
>Fifo's _can_ be implemented as recursive data structures, but arrays
>with indices are easier and more efficient.  So I'll do that with a
>Fortran 8x-like syntax.

>[Fortran 8x-like syntax deleted]

>Well, there you are.  You even have the assignment operators you asked
>for.  There aren't any pointers here either.
>

Err, you didn't even try to answer my question.  Your fortran 8x was
just like my fortran, except that 8x allows you to keep the pieces
together in a structure.  I already showed how to do it with arrays.
Any thoughts on the question I asked?

>> BTW, recursive structures are a very clumsy way to think about bags,
>
>I agree.  So don't implement them with recursive structures.  Recursive
>structures aren't for everything.  Use the structure which best fits
>the problem.  This means: rarely use pointers - if you can avoid it.
>And, if you're talking about language _design_, don't force pointers
>onto your users.
>

OK.  How do I implement bags.  Certainly not with arrays. (;-)  Best
with linked lists.

>[...] It is better to have different functionality actually have different
>syntax as well.  Most uses of pointers are actually something else
>in disguise.

And most other forms of other addressing are just uses of pointers in
disguise. It is better to have different syntax for each notational
way of thinking of the same functionality.  I agree that generic C
pointers, when thought of as memory references are a poor choice.  I
disagree that the model of pointers/pointer arithmetic as an
alternative way of thinking about name space mapping to things like
arrays and recursive structures is a problem.  I find the semantics
isomorphic and I find times when the syntax is a notational win -- for
either arrays or pointers.

>
>J. Giles
>Los Alamos


+-+-+-+     I don't know who I am, why should you?     +-+-+-+
   |        fouts@lemming.nas.nasa.gov                    |
   |        ...!ames!orville!fouts                        |
   |        Never attribute to malice what can be         |
+-+-+-+     explained by incompetence.                 +-+-+-+

jlg@lanl.gov (Jim Giles) (09/25/88)

From article <1058@amelia.nas.nasa.gov>, by fouts@lemming.nas.nasa.gov.nas.nasa.gov (Marty Fouts):
>>> [...]                             Try representing a dynamic length
>>> fifo using Hoare's structure and answering the questions:
>>> 1) What happens when I add to a fifo?
>>> 2) How do I represent this structure?
>>> 3) How do I keep track of the head/tail?
>>> 4) How do I detect an empty fifo?
>> [... stuff deleted which deteted my Fortran 8x - like versions ...]
> Err, you didn't even try to answer my question.  Your fortran 8x was
> just like my fortran, except that 8x allows you to keep the pieces
> together in a structure.  I already showed how to do it with arrays.
> Any thoughts on the question I asked?

I thought I had answered your question.  The differences between the
8x-like program I presented and the syntax Hoare used are trivially
superficial:

1) Hoare uses semicolon ';' to end statements, Fortran 8x uses end
   of line.

2) Hoare uses parenthesis to begin and end a type declaration, Fortran 8x
   uses an explicit END TYPE ... statement:
       Hoare                        Fortran
       type example (               TYPE EXAMPLE
       ...                          ...
       );                           END TYPE EXAMPLE

3) Hoare puts the data type after the variable list and Fortran 8x puts
   it before:
       Hoare                        Fortran
       head, tail : integer         integer head, tail

4) Hoare always requires a colon between the variables and the type
   (as above), Fortran 8x _allows_ double colons but doesn't require it.

5) I don't have the book in front of me, so I can't be sure, but I think
   Hoare used ':=' for assignment rather than just '='.

6) Again, I don't have the book with me, but I think Hoare used the
   Pascal - like rule for IF control (more than one statement in the
   scope of an IF required BEGIN ... END marks - rather like C {...}).

7) I think Hoare used square brackets '[...]' for array indices.

8) Hoare used '.' rather than '%' to reference components of syructured
   variables.

Apply those rules to the Fortran-like code I already posted and you'll 
have a pretty good imitation of Hoare's version of FIFOs.  So, in
answer to your 'Any thoughts on the question I asked?':

> [...]                             Try representing a dynamic length
> fifo using Hoare's structure and answering the questions:

I think that's pretty clear by now.  In any well designed language
the implementation of a FIFO queue is pretty much the same (including
your C version).

> 1) What happens when I add to a fifo?

The same thing that most of the other versions do:  if there's no
room for the new element, the queue is extended to make room, when
there's room the new element is added and the queue is tested to see
if it's full (for future reference).  Then the ADDTO routine returns.

> 2) How do I represent this structure?

Internally, it's probably the same as the C version of the same thing.
The only difference from the user's point of view is the lack of 
explicit pointers so that it is not possible for the queue%data array
to be aliased to something else.

> 3) How do I keep track of the head/tail?

queue%head and queue%tail are indexes into queue%data.  What else do
you need?

> 4) How do I detect an empty fifo?

queue%empty is a boolean variable which always is true if the queue is
empty, and false otherwise.

>>> BTW, recursive structures are a very clumsy way to think about bags,
>> [... my agreement ...]
> OK.  How do I implement bags.  Certainly not with arrays. (;-)  Best
> with linked lists.

Now you've got me confused again.  Linked lists are for large lists
in which the order is important and which are often altered.  For other
things, arrays (or some other structure) are best.  All the implementations
of bags I've seen were done with arrays (all from SmallTalk to data
packages for Pascal code).  The order is simply not important for a bag.

The other thing that confuses me is that recursive structures and pointers
implement linked lists in exactly the same way.  The difference between
them is the lack of an explicit pointer.  Semantically and syntactically
the difference is otherwise completely superficial.

>>[...] It is better to have different functionality actually have different
>>syntax as well.  Most uses of pointers are actually something else
>>in disguise.
> 
> And most other forms of other addressing are just uses of pointers in
> disguise.  [...]

I agree.  Many of the data structures people use are internally
implemented with pointers.  But making the pointer explicit carries
penalties that the user doesn't want.  As I just finished pointing
out in another article, explicit pointers clutter the scope with
unneeded names and degrade performance because the compiler must
assume possible aliasing (where the user intended none).  There
are probably many other problems with explicit pointers as well,
but just one of these is sufficient cause to reject explicit
pointers if something else is available.

J. Giles
Los alamos