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