ugprussa@cs.Buffalo.EDU (Michal Prussak) (05/08/89)
Wirth describes in his book "Algorithms and Data Structures" (from 1986)
a recursive data type (p 173):
TYPE
ped = RECORD
CASE known: BOOLEAN OF
TRUE: name: ARRAY[1..10] OF CHAR |
FALSE: father, mother: ped; <--- recursive fields
END (* case *);
END (* record *);
He remarks that CASE construction must be used because IF is not available
in Modula. I would therefore think that it should be legal. I can imagine
it would be very difficult to compile, and not surprisingly none of the
compilers i have access to does not allow this (one of them is LOGITECH
from Frankfurt University).
Does anybody know of a compiler that implements this? Or is this example
for future versions of Modula?
Michal Prussak
ugprussa@sunybcs.bitnet
ugprussa@cs.buffalo.edu
ugprussa@sunybcs.uucp
kloppen@gmdzi.UUCP (Jelske Kloppenburg) (05/09/89)
In article <5734@cs.Buffalo.EDU>, ugprussa@cs.Buffalo.EDU (Michal Prussak) writes: > Wirth describes in his book "Algorithms and Data Structures" (from 1986) > a recursive data type (p 173): > > TYPE > ped = RECORD > CASE known: BOOLEAN OF > TRUE: name: ARRAY[1..10] OF CHAR | > FALSE: father, mother: ped; <--- recursive fields > END (* case *); > END (* record *); > > ... That can not work. How much space should be reserved for a variable of such a type? The world is not as big! To generate recursive data structures I use the following: TYPE LinkPTR = POINTER TO Link; Link = RECORD Text: String; Count: CARDINAL; Left, Right: LinkPTR END; and I think a similar example is in Wirth's book defining modula. kloppenbrg@kmx.gmd.dbp.de UUCP: kloppen@gmdzi In real life: Jelske Kloppenburg
mlind@polyslo.CalPoly.EDU (Mark William Lind I) (05/09/89)
kloppen@gmdzi.UUCP (Jelske Kloppenburg) writes: :ugprussa@cs.Buffalo.EDU (Michal Prussak) writes: :> Wirth describes in his book "Algorithms and Data Structures" (from 1986) :> a recursive data type (p 173): ^^^^^^^^^ ^^^^ ^^^^ RECURSIVE DATA TYPE ??? :> TYPE :> ped = RECORD :> CASE known: BOOLEAN OF :> TRUE: name: ARRAY[1..10] OF CHAR | :> FALSE: father, mother: ped; <--- recursive fields :> END (* case *); ^^^^^^^^^ :> END (* record *); : :That can not work... DYNAMIC MEMORY ALLOCATION (not recursive) :TYPE : LinkPTR = POINTER TO Link; : Link = RECORD : Text: String; : Count: CARDINAL; : Left, Right: LinkPTR : END; This is dynamic memory allocation... but this is not a RECURSIVE data type. Personally, I don't see what the use of a recursive data structure is. Dynamic memory allocation is of obvious worth (no pun intended), but I don't see what the hell you would do with a recursive boolean expression?....... huh? Please Explain if you are still there. Hmmm... -- +-------------------------------------------------------------------------+ \ Mark William Lind I \ mlind@polyslo.CalPoly.EDU \ Mark L \ 8^" \ \ Std Disclaimer Assumed \ "Evel Knievel, you got nothin' on me." -_R_a_e_l \ +-------------------------------------------------------------------------+
ugprussa@sunybcs.uucp (Michal Prussak) (05/09/89)
I agree that this should not work, but... Wirth not only seems to imply that this should work, but he also gives a diagram of internal representation of such record. I was just wondering if this could be real. Michal Prussak
pcg@aber-cs.UUCP (Piercarlo Grandi) (05/10/89)
In article <11188@polyslo.CalPoly.EDU> mlind@polyslo.CalPoly.EDU (Mark William Lind I) writes:
Personally, I don't see what the use of a recursive
data structure is. Dynamic memory allocation is of obvious
worth (no pun intended), but I don't see what the hell you would
do with a recursive boolean expression?....... huh?
Please Explain if you are still there.
Maybe the best explanation would come from Hoare, in his very much forgotten
contribution to "Structured Programming", published by Academic Press. Read
also the third and last contribution...
--
Piercarlo "Peter" Grandi | ARPA: pcg%cs.aber.ac.uk@nsfnet-relay.ac.uk
Dept of CS, UCW Aberystwyth | UUCP: ...!mcvax!ukc!aber-cs!pcg
Penglais, Aberystwyth SY23 3BZ, UK | INET: pcg@cs.aber.ac.ukgateley@m2.csc.ti.com (John Gateley) (05/11/89)
In article <11188@polyslo.CalPoly.EDU> mlind@polyslo.CalPoly.EDU (Mark William Lind I) writes: >This is dynamic memory allocation... but this is not a RECURSIVE >data type. Personally, I don't see what the use of a recursive >data structure is. Dynamic memory allocation is of obvious >worth (no pun intended), but I don't see what the hell you would >do with a recursive boolean expression?....... huh? Hello Mark, This is not a recursive boolean expression, but it is a recursive data structure based on a recursive datatype. Have a datatype: infinite-list. There are three operations: head, tail, and cons (add an element). Now, we can define the Fibonacci numbers as an infinite list, the first two elements are 1, each succeeding element is the sum of the two previous elements. Even though the list is infinite, the program will actually only use a finite (but arbitrarily large) portion of it. I think this might be a recursive data type. Disclaimer: this idea comes from Lisp/Scheme streams. It doesn't have much to do with Modula2. John gateley@tilde.csc.ti.com
marti@ethz.UUCP (Robert Marti) (05/12/89)
In articles <5734@cs.Buffalo.EDU> and <5760@cs.Buffalo.EDU>, ugprussa@cs.Buffalo.EDU (Michal Prussak) writes: > Wirth describes in his book "Algorithms and Data Structures" (from 1986) > a recursive data type (p 173). > [ ... ] > Does anybody know of a compiler that implements this? Or is this example > for future versions of Modula? and > I agree that this should not work, but... > Wirth not only seems to imply that this should work, but he also gives > a diagram of internal representation of such record. I don't think he implies that it should work. In fact, p.175 of the very same book states (quoted without permission): The characteristic property of recursive structures [ ... ] is their ability to vary in size. Hence, it is impossible to assign a fixed amount of storage to a recursively defined structure, and as a consequence a compiler cannot associate specific addresses to the components of such variables. The technique most commonly used to master this problem involves _dynamic allocation_ of storage [ ... ]. I don't think there is a Modula-2 compiler that implements recursive data types _directly_, although it could be done. Indeed, someone in Wirth's group has developed an experimental language, Mona, which supports recursive data types (TREE types). Mona is _not_ a superset of Modula-2, though. -- Robert Marti Phone: +41 1 256 52 36 Institut fur Informationssysteme ETH-Zentrum CSNET/ARPA: marti%inf.ethz.ch@relay.cs.net CH-8092 Zurich, Switzerland UUCP: ...uunet!mcvax!ethz!marti