dimare@ucla-cs.UUCP (01/11/85)
I just ran into a problem with pointers in Pascal: I have two lists of pointers, and I need to find the intersection of them. Due to the nature of the problem, it's cheaper to keep these lists ordered. However, Pascal complains when I try to campare two pointer variables with operators different than = and <>: > Script started on Thu Jan 10 23:30:45 1985 > Warning: no access to tty; thus no job control in this shell... > e[2:1] c p.p; pi p.p > program blah (input, output); > var > x,y: ^integer; > begin > new(x); > if x<y then new(y); > end. > Thu Jan 10 23:27 1985 p.p: > E 6 - < not allowed on pointers - only allow = and <> > e[2:2] > script done on Thu Jan 10 23:31:03 1985 I'm not trying to do arithmetic with pointers, I only need to order them. I think this restriction is excessive. Is there a good reason for it? Would Modula-2 behave in the same way? Is it that Berkely Pascal is a wacko? Adolfo ///
ian@loral.UUCP (Ian Kaplan) (01/13/85)
> I just ran into a problem with pointers in Pascal: I have > two lists of pointers, and I need to find the intersection > of them. Due to the nature of the problem, it's cheaper to > keep these lists ordered. > > However, Pascal complains when I try to campare two pointer > variables with operators different than = and <>: > > [ Some more text which I have ommited ] > > I'm not trying to do arithmetic with pointers, I only need > to order them. I think this restriction is excessive. Is there > a good reason for it? Would Modula-2 behave in the same way? > Is it that Berkely Pascal is a wacko? > > Adolfo Berkeley Pascal is a fathful implementation of standard Pascal. You can get your code to work by using Pascal's infamous tagless case variant records. This sort of trick is commonly used by Pascal hackers to escape Pascal's type restrictions. A function like Equal below should work for pointer equality checks. It is not tested, so no guarantees. TYPE Pointer = ^Object; (* Function Equal returns TRUE if PtrOne is equal to PtrTwo, FALSE otherwise. *) FUNCTION Equal( PtrOne, PtrTwo : Pointer ) : BOOLEAN; (* Assuming that pointers occupy the same amount of memory as integers (an admittedly bad assumption on some systems) *) Trix = RECORD CASE INTEGER OF 1 : Ptr : Pointer; 2 : Int : INTEGER; END (* Case *) END; (* Record *) VAR One, Two : Trix; BEGIN One.Ptr := PtrOne; Two.Ptr := PtrTwo; Equal := One.Int = Two.Int; END; (* Equal *) Modula is designed for systems programming and provides much better facilities for type manipulation than Pascal. One of the standard Modula types is named CARDINAL. The CARDINAL type is used to represent unsigned integers. The type name can be used like a "cast" in C to tranform type. For example: TYPE Pointer = POINTER TO Object; (* Modula is case sensitive *) PROCEDURE Equal( PtrOne, PtrTwo : Pointer ) : BOOLEAN; BEGIN RETURN CARDINAL( PtrOne ) = CARDINAL( PtrTwo ); END Equal; The Modula standard procedure VAL could also be used: VAL( CARDINAL, PtrOne ) = VAL( CARDINAL, PtrTwo ) VAL is given two arguments, the destination type and the value to be transformed. VAL is usually safer to use since on some Modula implementations range checking is performed. Of course the Modula code is no more portable than the Pascal code, since its function is based on the assumption that pointers and CARDINALs are size compatible. Ian Kaplan Loral Data Flow Group Loral Instrumentation San Diego, CA (619) 560-5888 x4812 ucbvax!sdcsvax!sdcc6!loral!ian
herbie@watdcsu.UUCP (Herb Chong [DCS]) (01/13/85)
>However, Pascal complains when I try to campare two pointer >variables with operators different than = and <>: If I remember correctly, the Pascal language explictly states that those are the only two comparison operations allowed on pointers. Can someone verify this? Herb Chong... I'm user-friendly -- I don't byte, I nybble....
shor@sphinx.UChicago.UUCP (Melinda Shore) (01/14/85)
>>However, Pascal complains when I try to campare two pointer >>variables with operators different than = and <>: >If I remember correctly, the Pascal language explictly states that >those are the only two comparison operations allowed on pointers. >Can someone verify this? This is true. See p. 108 of J & W. Melinda Shore University of Chicago Computation Center
robert@gitpyr.UUCP (Robert Viduya) (01/15/85)
> I just ran into a problem with pointers in Pascal: I have > two lists of pointers, and I need to find the intersection > of them. Due to the nature of the problem, it's cheaper to > keep these lists ordered. > > However, Pascal complains when I try to campare two pointer > variables with operators different than = and <>: > > > Script started on Thu Jan 10 23:30:45 1985 > > Warning: no access to tty; thus no job control in this shell... > > e[2:1] c p.p; pi p.p > > program blah (input, output); > > var > > x,y: ^integer; > > begin > > new(x); > > if x<y then new(y); > > end. > > Thu Jan 10 23:27 1985 p.p: > > E 6 - < not allowed on pointers - only allow = and <> > > e[2:2] > > script done on Thu Jan 10 23:31:03 1985 > > I'm not trying to do arithmetic with pointers, I only need > to order them. I think this restriction is excessive. Is there > a good reason for it? Would Modula-2 behave in the same way? > Is it that Berkely Pascal is a wacko? > In most Pascal's I've used, the predefined function 'ord' can be used on pointer variables to return the actual machine address of whatever the pointer points to (the pointee?). You might want to try that method. Or you can be more unportable and do the following: program blah (input, output); type a = record case boolean of true: (i : integer); false: (p : ^integer); end; var x,y: a; begin new(x.p); if x.i<y.i then new(y.p); end. The strange record declaration makes a pointer to an integer look like an integer. However, this is not very portable as you are by no means guaranteed that a pointer is the same size as an integer. robert -- Robert Viduya Office of Computing Services Georgia Institute of Technology, Atlanta GA 30332 Phone: (404) 894-4669 ...!{akgua,allegra,amd,hplabs,ihnp4,masscomp,ut-ngp}!gatech!gitpyr!robert ...!{rlgvax,sb1,uf-cgrl,unmvax,ut-sally}!gatech!gitpyr!robert
hedrick@topaz.ARPA (Chuck Hedrick) (01/15/85)
> I just ran into a problem with pointers in Pascal: I have > two lists of pointers, and I need to find the intersection > of them. Due to the nature of the problem, it's cheaper to > keep these lists ordered. > > However, Pascal complains when I try to campare two pointer > variables with operators different than = and <>: Yes, the standard says that only = and <> work on pointers. However in many implementations, there is a simple dodge that will solve your problem. According to the standard, ORD is only legal on ordinal types. However in many implementations, ORD will work on pointers. It simply converts it to an integer. (Typically it just defeats typechecking. No extra code is generated.) If your implementation is like this, then you can do if ord(x) < ord(y) This works on the DEC-20, Pyramid, and SUN. Since it works on both the Pyramid and the SUN (which are 4.2 systems), I assume it would work on the Berkeley VAX compiler. It does not work on the VMS Pascal compiler. You should probably segregate any code that uses this into an implementation- dependent part, since this is a violation of the standard. Although I may have found you a kludge for this particular case, it is certainly true that this sort of thing is a problem with Pascal. I agree that some form of type cast would be desirable.
b-davis@utah-cs.UUCP (Brad Davis) (01/15/85)
[] In response to using ORD() on a pointer: There is no claim in Pascal that integers and pointers occupy the same space. If the pointer is larger than an integer then the comparison will be wrong. Even if a pointer and an integer occupy the same space the pointer may become a negative integer so that the comparison ord(p1) < ord(p2) will not tell you if p1 is in lower memory than p2. Since pointers may not be real addresses anyway the comparison would have no relation to where the data was stored. In response to pointing at staticly declared objects: As opposed to C, Pascal has no static memory space (an implementation may store globals as such but the language not have such a concept), all declared variables are automatics i.e. they are allocated as part of the stack frame. Pointing at stack spaces is one of the most common errors we find with programmers in their first large project in C. This capability (and danger) would be contrary to the philosophy behind Pascal. (Try to find a philosophy for C.) Brad Davis
gijs@vu44.UUCP (Gijs Mos) (01/17/85)
> [] Even if a pointer and an integer occupy > the same space the pointer may become a negative integer so that > the comparison ord(p1) < ord(p2) will not tell you if p1 is in > lower memory than p2. Since pointers may not be real addresses > anyway the comparison would have no relation to where the data was > stored. Since many pascal implementations tend to reclaim unused heap space it's useless to try to compare pointers anyway. You are never shure that an object A created with new after an object B is always higher/lower in memory then B. Consider the following example: new(x); new(b); dispose(x); new(a); Many implementations will re-use the space freed with the dispose of x for the object a points to. Gijs Mos {seismo,decvax,philabs}!mcvax!vu44!gijs
sahunt@snow.UUCP (Stephen Hunt) (01/23/85)
[ Even the line eater couldn't eat THREE Shreadded Wheat! ] In <ucla-cs.3161> ucla-cs!dimare writes:- > I just ran into a problem with pointers in Pascal: I have > two lists of pointers, and I need to find the intersection > of them. Due to the nature of the problem, it's cheaper to > keep these lists ordered. > However, Pascal complains when I try to campare two pointer > variables with operators different than = and <> ...... > I'm not trying to do arithmetic with pointers, I only need > to order them. I think this restriction is excessive. Is there > a good reason for it? Would Modula-2 behave in the same way? > Is it that Berkely Pascal is a wacko? > Adolfo > /// Berkley Pascal is quite normal in this respect. Comparisons like less-than are not allowed simply because they are meaningless. When you conjure up two pieces of storage with new(), say x and y in that order, there is no guarantee that y will directly follow x in memory - it may even be at a lower address. I don't understand why you feel it is "cheaper to keep these lists ordered" - I can't envisage a situation where it would be advantageous to know the real order of this type of structure in store. Are you sure you're not confusing a comparison of pointers with a comparison of pointees? If you *really* want to compare pointers I'm sure you will be able to fudge something with the ubiquitous variant records (unions) - but you will have to know how many bytes a pointer variable takes up, and other similarly nasty (and unportable) pieces of miscellany, --- Steve Hunt ... mcvax!ukc!qtlon!flame!ubu!snow!sahunt
mcnabb@uiucdcsb.UUCP (01/29/85)
/* Written Jan 28, 1985 by pdbain@wateng in net.lang.pascal */ Say I had a set of records, which I represented as a vector of pointers. Suppose further that I wanted to test for set membership by comparing pointers. If I keep the vector sorted by increasing pointer value, I can do the test in O(lg(N)), using a binary search, but I need < and > on pointers. If all I have is == and !=, it takes O(N) time. - peter bain /* End of text from net.lang.pascal */ It seems to me that the important point here is that Pascal objects to the use of the value of a pointer in any attempt to ascertain information about where the "pointee" lies in memory. Pascal does not object to the use of an assumption that every unique pointer has a corresponding unique scalar value, which may be sorted, compared, etc. just like any integer. Why not use "ord (your_pointer)" for the problem above? Pascal permits the conversion of (unique?)* pointers into (unique?)* integers, but tries to prevent direct arithmetic on pointers because this is clearly implementation-dependent. BTW, ord (pointer) is a freebie (i.e. NOP) in most Pascal compilers. * I am not sure, and rather doubt, that Pascal guarantees that pointers and integers will always be the same size. In an implementation with pointers larger than integers, the uniqueness assumption of the "ord" solution might not hold. Still, this kind of implementation-dependency seems both less likely and less serious. I guess that to be completely safe, one would have to use some other mechanism to obtain a unique key for each pointer. These keys could be kept with the pointers in the sorted vector (now a vector of records), or could be stored in the "pointee" records. Either way, it would be dead easy to keep your sorted vector - with only a small space (one integer) and perhaps time penalty (need extra indirection on compares if key stored with pointee). Either approach is still O(ln(N)), but is now implementation-independent.
pdbain@wateng.UUCP (Peter Bain) (02/01/85)
In article <9300010@uiucdcsb.UUCP> mcnabb@uiucdcsb.UUCP writes: >It seems to me that the important point here is that Pascal objects to the >use of the value of a pointer in any attempt to ascertain information about >where the "pointee" lies in memory. Pascal does not object to the use of >an assumption that every unique pointer has a corresponding unique scalar >value, which may be sorted, compared, etc. just like any integer. Why not >use "ord (your_pointer)" for the problem above? Pascal permits the conversion ----------------------- (emphasis mine) >of (unique?)* pointers into (unique?)* integers, but tries to prevent direct >arithmetic on pointers because this is clearly implementation-dependent. >BTW, ord (pointer) is a freebie (i.e. NOP) in most Pascal compilers. I asked our local Pascal guru and he said: From watmath!water!watbun!atbowler Thu Jan 31 14:08:04 1985 From: watmath!water!watbun!atbowler Message-Id: <8501311844.AA09296@water> Date: Thu 31 Jan 1985 13:44 To: water!pdbain@wateng Sent: Thu 31 Jan 1985 13:44 Status: RO Re: ORD in Pascal ORD of a pointer is quite definitly not legal. Some Pascal supply a method of producing an integer from a pointer so that you have a printable value. In Pascal-8 this is the ADDR function. This is an extension not part of the language. -peter -- - peter bain ...!{allegra|decvax|clyde|ihnp4 }!watmath!wateng!pdbain hard mail: CCNG, CPH-2369A, University of Waterloo, Waterloo, Ont. Canada N2M 5G4 telephone: (519) 885-1211 x2810
ee163acp@sdcc13.UUCP (DARIN JOHNSON) (02/01/85)
> > Say I had a set of records, which I represented as a vector of pointers. > Suppose further that I wanted to test for set membership by comparing > pointers. If I keep the vector sorted by increasing pointer value, > I can do the test in O(lg(N)), using a binary search, but I need > < and > on pointers. If all I have is == and !=, it takes O(N) time. > > > It seems to me that the important point here is that Pascal objects to the > use of the value of a pointer in any attempt to ascertain information about > where the "pointee" lies in memory. Pascal does not object to the use of > an assumption that every unique pointer has a corresponding unique scalar > value, which may be sorted, compared, etc. just like any integer. Why not > use "ord (your_pointer)" for the problem above? Pascal permits the conversion > of (unique?)* pointers into (unique?)* integers, but tries to prevent direct > arithmetic on pointers because this is clearly implementation-dependent. The whole idea of type checking and other Pascal-gripes is to check for potential errors. This doesn't necessarily restrict you. As shown above, you can get around the type IF THIS IS WHAT YOU WANTED. Type checking is to detect things you didn't want to happen. With the pointer case, Pascal checks for < or > comparison because it assumes that 99% of the time the programmer goofed (admit it, it happens), but if that is what you really want, use an ord(p) call. If your system has strange pointer sizes or doesn't allow ord on pointers, use case variant records (although you lose portability somewhat). Darin Johnson @ UCSD center for study of centers.
robertd@tektronix.UUCP (Bob Dietrich) (02/08/85)
> ... Pascal does not object to the use of > an assumption that every unique pointer has a corresponding unique scalar > value, which may be sorted, compared, etc. just like any integer. Why not > use "ord (your_pointer)" for the problem above? Pascal permits the conversion > of (unique?)* pointers into (unique?)* integers, but tries to prevent direct > arithmetic on pointers because this is clearly implementation-dependent. > BTW, ord (pointer) is a freebie (i.e. NOP) in most Pascal compilers. Application of 'ord' to pointers (or any type other than enumerations, integers, chars, Boolean, or subranges thereof) is an extension available in various Pascal implementations, but it is not a standard feature of Pascal. Berkley Pascal has this extension, although it is not documented. > * I am not sure, and rather doubt, that Pascal guarantees that pointers and > integers will always be the same size. In an implementation with pointers > larger than integers, the uniqueness assumption of the "ord" solution might > not hold. Still, this kind of implementation-dependency seems both less > likely and less serious. Good point. The Pascal standards explicitly avoid specifying implementation details to give an implementor freedom to do a good job. An implementation may have 3 different sizes of pointers (such as for the Intel 286) if it wants, or define type 'char' to be 16-bits to accomodate extended character sets (such as for Japanese or the other character sets being standardized). > I guess that to be completely safe, one would have to use some other > mechanism to obtain a unique key for each pointer. These keys could be kept > with the pointers in the sorted vector (now a vector of records), or could > be stored in the "pointee" records. Either way, it would be dead easy to > keep your sorted vector - with only a small space (one integer) and perhaps > time penalty (need extra indirection on compares if key stored with pointee). > Either approach is still O(ln(N)), but is now implementation-independent. Good! Whenever you run into a roadblock in a language, there's a better than even chance that you're trying the wrong approach, instead of the language being deficient. All idioms in German do not translate literally into English, and vice versa. Each language has its model of the world, which does not make either wrong. By modifying your design, you may get faster run time, shorter code, less storage, easier maintenance, better portability, etc. Bob Dietrich Tektronix, Inc. (503) 629-1727 {ucb or dec}vax!tektronix!robertd uucp address robertd@tektronix csnet address robertd.tektronix@rand-relay arpa address