markh@csd4.milw.wisc.edu (Mark William Hopkins) (02/11/88)
In the book "Programming in Modula 2" written by the designer Niklaus Wirth,
the author goes over an example illustrating the use of pointer types. Consider
the following definition:
ListPointer = POINTER TO ListNode;
ListNode = RECORD
Key: ... ;
Data: ... ;
Next: ListPointer
END;
The author makes the comment that the following is not a substitute for the
definition above:
List = RECORD
Key: ... ;
Data: ... ;
Next: List
END;
he goes on to say that this would not be a valid definition because "it does not
terminate" and seems to argue from there that direct recursion should not be
represented in the language.
My comment is that of course you would not represent a list like that,
because you have to account for the possible null value of the pointer. The
proper abbreviation is a VARIANT record with a null variant for the empty list:
List = RECORD CASE Null:BOOLEAN OF
TRUE: |
FALSE: Key: ... ;
Data: ... ;
Next: List
END;
This definition does terminate.
The question then is why is direct recursion excluded from Modula-2?
The only major use of pointers in the language is to make type definitions that
are indirectly recursive. Having pointers in the language, though, seems to be
much like having goto statements. The latter can lead to "spaghetti programming"
and the former to "spaghetti data structures". So the other question is why
pointers are included in the language when direct recursion may be more
appropriate?BOTCHAIR@UOGUELPH.BITNET (Alex Bewley) (02/12/88)
Pointers are extremely useful. They can be used for type conversion (but
we, being good programmers :-), don't do this). They can also be used to
'fix' data structures to certain locations in memory. For example consider the
video screen of a PC. It is composed of 4000 bytes. The colour screen memory
is located at B800H:0000H, and the monochrome screen memory is located at
B000H:0000H. A small procedure could determine which type of video card is
being used and set an array to point to the appropriate memory location. Thus,
every time you use a data structure (usually a two dimensional array, in this
case) it will change the screen display.
Some code is included below.
For this screen exercise you could use the absolute variable declaration, but
that would mean defining an array for each screen.
Alex
-----
TYPE
ScreenType = POINTER TO ARRAY [0..25-1],[0..80-1] OF RECORD
Char, Attr : CHAR;
END;
VAR
Screen : ScreenType;
BEGIN
(* determine video card type *)
...
IF ColourMonitor THEN
Screen := 0B800H:0000H;
ELSE
Screen := 0B000H:0000H;
END;
...
Screen[0][0].Char := "A"; (* put an 'A' in the top left corner of the *)
END; (* screen *)carroll@snail.CS.UIUC.EDU (02/12/88)
I think you are missing the point. The definition below is in fact an infinitely sized data object. > List = RECORD > Key: ... ; > Data: ... ; > Next: List > END; > >he goes on to say that this would not be a valid definition because "it does not >terminate" and seems to argue from there that direct recursion should not be >represented in the language. There is a difference between data recursion and program recursion. I am not sure which one you are referring to. > > My comment is that of course you would not represent a list like that, >because you have to account for the possible null value of the pointer. The >proper abbreviation is a VARIANT record with a null variant for the empty list: > > List = RECORD CASE Null:BOOLEAN OF > TRUE: | > FALSE: Key: ... ; > Data: ... ; > Next: List > END; > >This definition does terminate. >(...) When? The compiler can't know when it terminates at compile time. And accessing elements far down the chain is going to be a major amount of typing. In fact, I would like to see how you would, say, sum up all the data elements. You'd have to explicitly code the level of depth in the structure when you referenced it. How would you allocate it? For a normal variant record, there is an exact number of variant tags. In this case there is an arbritrary and unknown number. The reason for pointers is to allow, in a reasonable way, what you seem to want to do. Alan M. Carroll amc@woodshop.cs.uiuc.edu carroll@s.cs.uiuc.edu ...{ihnp4,convex}!uiucdcs!woodshop!amc Quote of the day : "I've consulted all the sages I could find in Yellow Pages, but there aren't many of them" - AP & EW
firth@sei.cmu.edu (Robert Firth) (02/15/88)
In article <4572@uwmcsd1.UUCP> markh@csd4.milw.wisc.edu (Mark William Hopkins) writes: >I guess this gets me to my next question, somewhat related: > > If Modula-2 goes so far as to include Procedure as a data type, > then why not memory cell? > > One can imagine a type Cell internally defined as an array of W bits > ... But Modula-2 DOES include this feature, in a manner pretty close to what you'd like. Check out PIM2 #rd Edition, Chapter 12, on System-dependent facilities. You'll find types WORD and ADDRESS. You can convert a WORD into a set (former Modula-2 BITSET) and munge the bits. You can generate the address of any cell by ADR. And so on. There are also rules for formal/actual parameter compatibility that allow you to evade the typing mechanism by using WORD, ADDRESS, and open arrays. It's all good stuff!
scc@cl.cam.ac.uk (Stephen Crawley) (02/16/88)
>> List = RECORD CASE Null:BOOLEAN OF >> TRUE: | >> FALSE: Key: ... ; >> Data: ... ; >> Next: List >> END; >> While the above type would indeed be infinite in the sense that some of its ''possible'' values would be infinite, some of its values would also be finite. The problem is that the size of a value of such a type would not in general be determinable at compile time. This implies automatic allocation of dynamic storage, and that would break Modula-2 ... which has no garbage collection. A more sensible implementation would use hidden pointers (hence the sizes would be determinable at compile time), but that would still require garbage collection. BTW-1: It is not at all hard to distinguish at compile time between infinite types that are useful and those that are non-useful; i.e. those for which all values are infinite. BTW-2: There ARE languages that allow infinite types; e.g. ML. BTW-3: There ARE languages in which infinite types are represented without pointers; e.g. Courier and ANS 1. Of course, these are not programming languages but languages for defining application level communication protocols. -- Steve