brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (10/11/90)
1. Packed array tries, as in TeX. A C version of the relevant code is amazingly fast. 2. Reversing a stack, or going through any other data structure ``backwards,'' without wasting lots of extra memory. You normally do this by ``flipping the pointers.'' 3. Simulating or interpreting machine language. Or any other language. WIth the possible exception of themselves. 4. Data compression and decompression by dictionary methods like LZW. ---Dan
jlg@lanl.gov (Jim Giles) (10/11/90)
From article <26739:Oct1023:44:2690@kramden.acf.nyu.edu>, by brnstnd@kramden.acf.nyu.edu (Dan Bernstein): > 1. Packed array tries, as in TeX. A C version of the relevant code is > amazingly fast. You have tried to fool me with this one before and consistently refused to give a specific definition of a 'trie'. Since I didn't want to look through the TeX code, I left it hanging. But, recently, I've found a reference to them and followed it back. Knuth vol. 3 discusses them. A trie is simply a recursive data structure - the Knuth examples don't even require aliased references. A recursive data structure declaration of the data type of a 'trie' node is as follows (for the example data in Knuth, Art of Computer Programming, 6.3, algorithm T): recursive type trie union (trie, ASCII sequence) :: vector(A:Z) end type trie To quote Knuth: "The nodes of a trie are vectors whose subscripts run from 0 to M-1 [M is the number of distinct characters in the alphabet - I took the obvious step of actually indexing the vector directly on the alphabet itself]; each component of these vectors is either a key [the ASCII sequence] or a link (possibly null)." Clearly the above declaration represents exactly that. There is no reason that a program using this mechanism should be any slower than your explicit pointer version. In fact, the compiler will probably produce identical code (unless, as is likely, it is able to detect that references arent aliased - which it can't detect using explicit pointers - in which case the recursive data type will result in _more_ efficient code). > [...] > 2. Reversing a stack, or going through any other data structure > ``backwards,'' without wasting lots of extra memory. You normally do > this by ``flipping the pointers.'' Flipping links in a recursive data type has exactly the same semantics. At least, if the recursive type allows aliased references and has a "shallow copy" assignment operator. Again, the speed should be identical or better than the explicit pointer version. > [...] > 3. Simulating or interpreting machine language. Or any other language. > WIth the possible exception of themselves. Most people do this with a state machine simulator. What this has to do with pointers is a mystery to me. A friend of mine does this all the time (in order to keep statistics about the code while interpreting real programs). He's never used pointers in the simulator code. > [...] > 4. Data compression and decompression by dictionary methods like LZW. Again, you'll have to explain why this necessitates pointers. The codes I've seen do this never use pointers. J. Giles
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (10/12/90)
In article <65450@lanl.gov> jlg@lanl.gov (Jim Giles) writes: > From article <26739:Oct1023:44:2690@kramden.acf.nyu.edu>, by brnstnd@kramden.acf.nyu.edu (Dan Bernstein): > > 1. Packed array tries, as in TeX. A C version of the relevant code is > > amazingly fast. > You have tried to fool me with this one before and consistently refused > to give a specific definition of a 'trie'. I'm not trying to fool you; I told you repeatedly to look it up in the TeX code. I keep using the example of packed array tries because they're the most important example I know of structures that CANNOT be expressed directly as recursive data structures (what Knuth calls general Lists). You keep saying that pointer-free languages suffice for everything, but you refuse to look at real-world examples where you're wrong. The world is not made up of recursive data structures. [ Jim finally looks up the meaning of trie ] > A trie is simply a recursive data structure [ blah blah blah, implementation equals interface crap ] That's really, really, really stupid. Sure, a trie is a recursive data structure. And sorting is the process of putting records into order by flipping adjacent records. Now go look up packed array tries in the TeX code. Try to implement them in your pointer-free language. You will NEVER make it as efficient as I can make a C version. NEVER. EVER. It is IMPOSSIBLE. Sorry to shout, but you keep blabbering on, consciously turning away from a beautiful counterexample to your philosophical crap. A packed array trie saves a huge amount of memory by aliasing---overlapping, even worse---*within* itself. And learn to pay attention to adjectives. > > 2. Reversing a stack, or going through any other data structure > > ``backwards,'' without wasting lots of extra memory. You normally do > > this by ``flipping the pointers.'' > Flipping links in a recursive data type has exactly the same semantics. Oh? I don't believe you. Show me the LISP code that flips a stack in bounded memory. Well? > > 3. Simulating or interpreting machine language. Or any other language. > > WIth the possible exception of themselves. > Most people do this with a state machine simulator. What this has to > do with pointers is a mystery to me. It's about twice as efficient with pointers, since essentially random memory references form such a huge part of an assembly-language program. Read the subject line. > > 4. Data compression and decompression by dictionary methods like LZW. > Again, you'll have to explain why this necessitates pointers. The > codes I've seen do this never use pointers. Read the subject line. You lose about 30% with arrays---though sometimes you have to use 2-byte integers rather than pointers to save memory. ---Dan
gl8f@astsun7.astro.Virginia.EDU (Greg Lindahl) (10/12/90)
In article <10397:Oct1212:55:1090@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: [ a posting in which Dan is repeatedly rude to Jim Giles ] Dan, if you want to hold a flame-war, do it in alt.flame or alt.religion.computers, not comp.lang.misc. Quotable exerpts, out of context. >I'm not trying to fool you; I told you repeatedly to look it up in the >TeX code. > [ blah blah blah, implementation equals interface crap ] > >That's really, really, really stupid. >And learn to pay attention to adjectives. -- "Restraint, hell. I'm just too fucking busy." -- Bill Wisner
jlg@lanl.gov (Jim Giles) (10/13/90)
From article <10397:Oct1212:55:1090@kramden.acf.nyu.edu>, by brnstnd@kramden.acf.nyu.edu (Dan Bernstein): > In article <65450@lanl.gov> jlg@lanl.gov (Jim Giles) writes: > [...] > I'm not trying to fool you; I told you repeatedly to look it up in the > TeX code. And, I keep telling you that I have neither the time nor the access to look at the TeX code. I suppose it's around here somewhere, but I have no interest in TeX itself. If there's something in TeX that can't be done with recursive data structures (and the other features I've supported on the net so visibly), then you ought to be able to give a specific example - in C if you like. You post so much mail and news every week, a few lines of code should hardly tax your fingers on the keyboard. > [...] > I keep using the example of packed array tries because they're the most > important example I know of structures that CANNOT be expressed directly > as recursive data structures (what Knuth calls general Lists). [...] You keep claiming that in spite of the fact that I actually posted a recursive declaration of exactly such a data structure as my last item in this thread. Please show _specifically_ why the data structure I gave last time is less efficient than pointers could do it. I would be real surprised, I've done the denotational semantics of both pointers (Pascal flavor) and recursive data structures (with aliasing permitted): the two have _exactly_ the same semantics. > [...] > saying that pointer-free languages suffice for everything, but you > refuse to look at real-world examples where you're wrong. The world is > not made up of recursive data structures. No, it's not. It also contains arrays, sequences, unions, etc.. I will look at any real world (or any other) example that you care to post. You have yet to directly post _anything_ that requires _explicit_ pointers, either for functionality or efficiency. > [...] > [ Jim finally looks up the meaning of trie ] >> A trie is simply a recursive data structure > [ blah blah blah, implementation equals interface crap ] On the contrary, I've always specifically insisted that the implementation of a feature and the syntax (or semantics) of a feature are seperable. You're the one who insists that users be forced to explicitly monkey with the implementation level of data structures. > [...] > That's really, really, really stupid. I can see that I've won the argument. Only the loser needs to resort to abuse. > [...] > Now go look up packed array tries in the TeX code. Try to implement them > in your pointer-free language. You will NEVER make it as efficient as I > can make a C version. NEVER. EVER. It is IMPOSSIBLE. [...] You keep saying that. I've not seen it. I HAVE looked up tries. They aren't the least bit difficult to do with recursive data structures (which the declaration in my last posting showed). Please show me why the thing I've already posted is impossible - or how it differs from a trie. > [...] Sorry to shout, but > you keep blabbering on, consciously turning away from a beautiful > counterexample to your philosophical crap. [...] I'm not turning away from anything. I have investigated the claim you're making, and I can't see any evidence to support it. If you have other evidence to present - PLEASE DO. > [...] A packed array trie saves a > huge amount of memory by aliasing---overlapping, even worse---*within* > itself. So? Turn on the 'aliased' attribute that I keep recommending and overlap to your hearts content. This is one of the reasons that I've fallen behind with my email correspondence with Dan: he continuously ignores two thirds of what I say and the argues against the remaining (out of context) third. The very first mention I made to him about recursive data structures, I pointed out that C.A.R. Hoare opposed allowing aliasing but that I _supported_ allowing it as an option. (To be sure, I've rather heavily extolled the virtues of non-aliased structures. But, I've consistently insisted that aliasing be an option.) In spite of this (and continued statements to the same effect), Dan continues to argue against recursive data structures as if aliasing were strictly forbidden in them. > [...] >> > 2. Reversing a stack, or going through any other data structure >> > ``backwards,'' without wasting lots of extra memory. You normally do >> > this by ``flipping the pointers.'' >> Flipping links in a recursive data type has exactly the same semantics. > > Oh? I don't believe you. Show me the LISP code that flips a stack in > bounded memory. Well? LISP is based on a single restricted model of recursive data structures which I happen not to support. Claiming that recursive data structures in general can't perform a specific because LISP can't is like claiming that aircraft can't lift two ton cargo because Sopwith Camels couldn't. Flipping links (with the 'aliased' attribute on) has the same semantics as flipping pointers, _nearly_ the same syntax, and most probably the same internal implementation. > [...] >> > 3. Simulating or interpreting machine language. Or any other language. >> > WIth the possible exception of themselves. >> Most people do this with a state machine simulator. What this has to >> do with pointers is a mystery to me. > > It's about twice as efficient with pointers, since essentially random > memory references form such a huge part of an assembly-language program. > Read the subject line. Oh, I see. This is the oft cited and easily discredited claim that *(p+i) is more efficient than a(i). Whether you use pointers or not, the simulated memory of your interpreted machine code is a bounded space within the simulator. Without pointers, simulated memory would simply be a 1-d array called MEMORY and you would use maps or some other run-time 'equivalence' to With poiners, the simulated memory would be pointed to by a base pointer called pmem (or some such). Either way, the references to simulated memory addresses would have to be added to the base address of the simulated memory region. This takes the same amount of time whether memory is simulated with pointers or arrays. > [...] >> > 4. Data compression and decompression by dictionary methods like LZW. >> Again, you'll have to explain why this necessitates pointers. The >> codes I've seen do this never use pointers. > > Read the subject line. You lose about 30% with arrays---though sometimes > you have to use 2-byte integers rather than pointers to save memory. I'm still not clear on this. How do you save with pointers by not using them? Where does the 30% figure come from - a specific (and doubtful) compiler? Our person who does research on data compression algorithms seldom uses pointers at all. I've asked: he'd never use pointers for the method you describe. Once again, can you give a _specific_ example of what you think is faster with pointers? Why can't array indices be stored as 2-byte integers too? J. Giles
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (10/14/90)
To simplify your followup job, Jim, I've separated out several paragraphs as numbered questions. Feel free to edit out the rest and just respond to those. In article <65642@lanl.gov> jlg@lanl.gov (Jim Giles) writes: [ first ] > And, I keep telling you that I have neither the time nor the access to > look at the TeX code. [ second ] > I'm not turning away from anything. I have investigated the claim you're > making, and I can't see any evidence to support it. If you have other > evidence to present - PLEASE DO. Jim, read the above two paragraphs. You wrote them. QUESTION 1: Do you see the contradiction in ``I absolutely refuse to look at the example you're giving me!'' and ``I am not turning away from anything!''? I find it surprising that you and Lindahl don't own the book presenting TeX's code. I find it sad that you're not even aware of it. It's by now a classic exposition. > If there's something in TeX that can't be > done with recursive data structures (and the other features I've supported > on the net so visibly), then you ought to be able to give a specific > example - in C if you like. Packed array tries are not trivial to implement. I don't see why I should bother to type in a presentation just for you, when Knuth has already done a much better job. QUESTION 2: Why do you refuse to look up packed array tries? Perhaps because you're afraid that I'm right? > > I keep using the example of packed array tries because they're the most > > important example I know of structures that CANNOT be expressed directly > > as recursive data structures (what Knuth calls general Lists). [...] > You keep claiming that in spite of the fact that I actually posted > a recursive declaration of exactly such a data structure as my last > item in this thread. QUESTION 3: Can you read? Do you see the word ``packed''? Does it even occur to you that there's a difference between a packed array trie and a trie (by which people usually mean a list trie or a normal array trie)? > You're the one who insists that users be forced to explicitly monkey > with the implementation level of data structures. QUESTION 4: Has it gotten through your head that nobody's forcing you to abandon your high-level structures just because pointers exist? See question 5. > > [...] > > That's really, really, really stupid. > I can see that I've won the argument. Only the loser needs to resort > to abuse. Oh? ``Gee, Jim, you started.'' > > Now go look up packed array tries in the TeX code. Try to implement them > > in your pointer-free language. You will NEVER make it as efficient as I > > can make a C version. NEVER. EVER. It is IMPOSSIBLE. [...] > You keep saying that. I've not seen it. I HAVE looked up tries. You have not looked up packed array tries. > > [...] Sorry to shout, but > > you keep blabbering on, consciously turning away from a beautiful > > counterexample to your philosophical crap. [...] > > [...] A packed array trie saves a > > huge amount of memory by aliasing---overlapping, even worse---*within* > > itself. > So? Turn on the 'aliased' attribute that I keep recommending and > overlap to your hearts content. As you would see if you bothered to borrow TeX: The Program from your library, that won't work. The moment you try to manipulate the structure you'll destroy it. > In spite of this (and continued statements to the same > effect), Dan continues to argue against recursive data structures as > if aliasing were strictly forbidden in them. QUESTION 5: Do you realize the difference between arguing *for* pointers and arguing *against* recursive data structures? Yes or no? Well? > >> > 2. Reversing a stack, or going through any other data structure > >> > ``backwards,'' without wasting lots of extra memory. You normally do > >> > this by ``flipping the pointers.'' > >> Flipping links in a recursive data type has exactly the same semantics. > > Oh? I don't believe you. Show me the LISP code that flips a stack in > > bounded memory. Well? > LISP is based on a single restricted model of recursive data structures > which I happen not to support. Claiming that recursive data structures > in general can't perform a specific because LISP can't is like claiming > that aircraft can't lift two ton cargo because Sopwith Camels couldn't. Fine, show how Nemesis does it. You're beating around the bush. (Your assertion that LISP's model is restricted is incorrect, but I won't belabor this point.) QUESTION 6: How do you express a bounded-memory reverse-direction stack or tree traversal in Nemesis? I don't believe you can. [ machine language simulation is faster with pointers ] > Oh, I see. This is the oft cited and easily discredited claim that > *(p+i) is more efficient than a(i). No, it is not. QUESTION 6: Can you see the difference between *p and *(p+i)? Do you realize that the first is more efficient than the second? Do you understand now why pointers can be more efficient than arrays? > >> > 4. Data compression and decompression by dictionary methods like LZW. > >> Again, you'll have to explain why this necessitates pointers. The > >> codes I've seen do this never use pointers. > > Read the subject line. You lose about 30% with arrays---though sometimes > > you have to use 2-byte integers rather than pointers to save memory. > I'm still not clear on this. [ various confused questions ] I have taken several LZ-type compressors and decompressors and converted them to use pointers rather than arrays with integers. This saves some indexing inside the inner loop, for an average 30% gain on various machines. Unfortunately, pointers use 4 bytes on most machines, when the application at hand only requires 2 bytes. You often have to use 2-byte integers rather than pointers to save memory. So you lose that 30%. I hope you understand what I'm saying now, so that you can ask sensible questions. ---Dan
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (10/14/90)
In article <1990Oct12.154528.25240@murdoch.acc.Virginia.EDU> gl8f@astsun7.astro.Virginia.EDU (Greg Lindahl) writes: > Dan, if you want to hold a flame-war, do it in alt.flame or > alt.religion.computers, not comp.lang.misc. Fair enough. > Quotable exerpts, out of context. As is usual for you. > >I'm not trying to fool you; I told you repeatedly to look it up in the > >TeX code. Yes! Please quote this! Every programmer who actually pays attention to the literature in the field he works in will be laughing his head off at you. You don't even realize that the TeX code has been published as a book, perhaps the greatest program exposition ever. That's funny. ---Dan ``Quotable excerpts, out of context.'' Greg Lindahl, applying his morals
gl8f@astsun9.astro.Virginia.EDU (Greg Lindahl) (10/14/90)
In article <21253:Oct1323:11:5090@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >I find it surprising that you and Lindahl don't own the book presenting >TeX's code. I read that book quite a few years ago. If you want to make incorrect personal attacks, please make them in alt.flame. -- "Restraint, hell. I'm just too fucking busy." -- Bill Wisner
ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (10/15/90)
In article <10397:Oct1212:55:1090@kramden.acf.nyu.edu>, brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: > Oh? I don't believe you. Show me the LISP code that flips a stack in > bounded memory. Well? (setq reversed-stack (nreverse original-stack)) (Since Lisp has rplaca/rplacd -- or, in Scheme, set-car!/set-cdr! -- Lisp is a very poor example of a "pointerless: language...) -- Fear most of all to be in error. -- Kierkegaard, quoting Socrates.
ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (10/15/90)
In article <65642@lanl.gov>, jlg@lanl.gov (Jim Giles) writes: > Flipping links (with the 'aliased' attribute on) has the same semantics > as flipping pointers, _nearly_ the same syntax, and most probably the > same internal implementation. Jim Giles is one of the people whose postings I read carefully. But now I am really puzzled. If recursive data structures with the 'aliased' attribute have the same semantics as pointers and very nearly the same syntax, what precisely is the advantage, and in what sense have pointers been eliminated? Is the claim that undeclared aliasing is a Bad Thing? I'll agree, but then recursive structures in Scheme are Bad Things because there is implicit aliasing, although there are no programmer-visible pointers. (Don't run away with the idea that I'm defending pointers. My favourite languages include ML, Scheme, and Prolog. But I do have to say that handling dynamic data structures in C is considerably easier and the code far less "contorted" than in Pascal.) -- Fear most of all to be in error. -- Kierkegaard, quoting Socrates.
db@cs.ed.ac.uk (Dave Berry) (10/16/90)
In article <3976@goanna.cs.rmit.oz.au> ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes: >(Don't run away with the idea that I'm defending pointers. My favourite >languages include ML, Scheme, and Prolog. ML has reference values, which are basically pointers. There just isn't much need to use them. -- Dave Berry, LFCS, Edinburgh Uni. db%lfcs.ed.ac.uk@nsfnet-relay.ac.uk "Dumping 33546240 bytes to dev 0x70e0100, offset 124968. Don't cycle power ..."
cik@l.cc.purdue.edu (Herman Rubin) (10/18/90)
In article <641@skye.cs.ed.ac.uk>, db@cs.ed.ac.uk (Dave Berry) writes: > In article <3976@goanna.cs.rmit.oz.au> ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes: > >(Don't run away with the idea that I'm defending pointers. My favourite > >languages include ML, Scheme, and Prolog. > > ML has reference values, which are basically pointers. There just > isn't much need to use them. Here is an actual situation, which I see no good way to handle without pointers. One is reading from a buffer, and the buffer can become inadequate at unpredictable times. When this happens, one calls a refill program. The information as to where the buffer is, where if ends, and possibly other necessary information for the refill procedure, as well as where the refill procedure, are changeable at run time. One could use call by value, which requires lookup. But using call by reference for both the refill procedure and the struct which contains the buffer information, usually in the form of locations and sizes, are by far the natural and logical way to do it, as well as being efficient. -- Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907 Phone: (317)494-6054 hrubin@l.cc.purdue.edu (Internet, bitnet) {purdue,pur-ee}!l.cc!cik(UUCP)
pcg@aber-cs.UUCP (Piercarlo Grandi) (10/22/90)
In article <21462:Oct1323:51:3990@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: You don't even realize that the TeX code has been published as a book, perhaps the greatest program exposition ever. That's funny. An no, this cannot pass. The TeX source code is pretty horrible. The whole idea of literate programming has been satirized effectively in "Programming Pearls". Now back to pointers: the TeX source is regrettable because, being a language implementation, it does need pointer manipulation for efficiency reasons, just like the Hermes one does. Since however it is written in a language (a subset of Pascal) without pointers, it has to be ludicrously inefficient by simulating the store with an array and pointers with indexes in that array. This to me is neither for or against pointers; it just confirms that implementations need pointers, applications do not (the TeX language itself does not need pointers), because implementations are machine oriented (even if not machine dependent) and applications are problem oriented (and relationships among data are better represented in other ways than pointers at the problem level). -- Piercarlo "Peter" Grandi | ARPA: pcg%uk.ac.aber.cs@nsfnet-relay.ac.uk Dept of CS, UCW Aberystwyth | UUCP: ...!mcsun!ukc!aber-cs!pcg Penglais, Aberystwyth SY23 3BZ, UK | INET: pcg@cs.aber.ac.uk
jeff@aiai.ed.ac.uk (Jeff Dalton) (11/08/90)
In article <3975@goanna.cs.rmit.oz.au> ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes: >(Since Lisp has rplaca/rplacd -- or, in Scheme, set-car!/set-cdr! -- Lisp >is a very poor example of a "pointerless: language...) In Lisp/Scheme, everything (all values of variables) is essentially a pointer. But then you can factor out the phrase "pointer to" and regard variables as naming the objects directly. So that's a sense in which Lisp and Scheme don't have pointers. Another sense, perhaps more relevant to the present discussion, is that in Lisp & Scheme there's no way to get a pointer to the middle of a structure. You can't have a pointer to the cdr of a list, to the 3rd element of an array, etc. It is possible in some Lisps, where such things are (usually) called "locatives". It is locatives that are most like pointers in other languages. Locatives can be simulated in Lisps that don't have them by using functions. For example, here is a "pointer" to the 3rd element of a vector: (defstruct loc read write) (make-loc :read (lambda () (aref v 3)) :write (lambda (x) (setf (aref v 3) x))) -- jeff
ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (11/08/90)
In article <3716@skye.ed.ac.uk>, jeff@aiai.ed.ac.uk (Jeff Dalton) writes: > In article <3975@goanna.cs.rmit.oz.au> ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes: > > >(Since Lisp has rplaca/rplacd -- or, in Scheme, set-car!/set-cdr! -- Lisp > >is a very poor example of a "pointerless: language...) > > In Lisp/Scheme, everything (all values of variables) is essentially a > pointer. But then you can factor out the phrase "pointer to" and > regard variables as naming the objects directly. So that's a sense > in which Lisp and Scheme don't have pointers. Jim Giles has been saying at great length that the problem is ALIASING. (The "recursive data structure" notation he has hinted at from time to time is essentially "access types without aliasing + high level shuffling operations that preserve lack-of-aliasing".) If I do (let* ((x (list 1 2 3)) ; [1 2 3] -> x; (y (list x x))) ; [%x, %x] -> y; (setf (first (first y)) 42) ; 42 -> y.hd.hd; y) ; y; the answer comes back as ((42 2 3) (42 2 3)) ^^ this changed too! The fact that (first (second y)) changed when (first (first y)) was updated is precisely the kind of aliasing that was being blamed on pointers. -- The problem about real life is that moving one's knight to QB3 may always be replied to with a lob across the net. --Alasdair Macintyre.
peter@ficc.ferranti.com (Peter da Silva) (11/09/90)
In article <3716@skye.ed.ac.uk> jeff@aiai.UUCP (Jeff Dalton) writes: > Another sense, perhaps more relevant to the present discussion, is > that in Lisp & Scheme there's no way to get a pointer to the middle > of a structure. You can't have a pointer to the cdr of a list... (setq a '(foo (bar baz))) (setq b (cdr a)) (rplaca b 'bog) -- Peter da Silva. `-_-' Professional computer nerd, second class. +1 713 274 5180. 'U` Gallery Furniture really will SAVE YOU MONEY! peter@ferranti.com (Have you hugged your wolf today?)
barmar@think.com (Barry Margolin) (11/10/90)
In article <HEZ6WP9@xds13.ferranti.com> peter@ficc.ferranti.com (Peter da Silva) writes: >In article <3716@skye.ed.ac.uk> jeff@aiai.UUCP (Jeff Dalton) writes: >> You can't have a pointer to the cdr of a list... >(setq a '(foo (bar baz))) >(setq b (cdr a)) >(rplaca b 'bog) I think what he meant was that you can't set the CDR of A's value without having a pointer to the whole cons. Lisp "pointers" always point to the beginning of some (possibly composite) object. If there were true pointers, then instead of distinct RPLACA and RPLACD operations there could be a RPLAC operation whose argument is a pointer to the specific cell. Conses are like magnets -- there's no Lisp monopole! A better example might have been that you can't have a pointer to a symbol's value cell, or to a particular cell of an array. By the way, Zetalisp (and its descendent, Symbolics Common Lisp) *does* have pointers, called locatives. They are used for implementation of many of the Lisp primitives that aren't implemented in hardware or microcode, but also in the internals of and interfaces to many OS routines for efficiency (locatives are implemented as an immediate data type, so they don't take up space or invoke the memory allocator). Locatives just contain machine addresses, like conventional machine pointers, but they are updated when the referenced object is moved by the garbage collector. -- Barry Margolin, Thinking Machines Corp. barmar@think.com {uunet,harvard}!think!barmar
jeff@aiai.ed.ac.uk (Jeff Dalton) (11/22/90)
In article <4223@goanna.cs.rmit.oz.au> ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes: >In article <3716@skye.ed.ac.uk>, jeff@aiai.ed.ac.uk (Jeff Dalton) writes: >> In Lisp/Scheme, everything (all values of variables) is essentially a >> pointer. But then you can factor out the phrase "pointer to" and >> regard variables as naming the objects directly. So that's a sense >> in which Lisp and Scheme don't have pointers. > >Jim Giles has been saying at great length that the problem is ALIASING. No kidding, Richard. You will note that I was just providing some information about pointers and Scheme. Aliasing is, of course, still a problem.
jeff@aiai.ed.ac.uk (Jeff Dalton) (11/22/90)
In article <HEZ6WP9@xds13.ferranti.com> peter@ficc.ferranti.com (Peter da Silva) writes: >In article <3716@skye.ed.ac.uk> jeff@aiai.UUCP (Jeff Dalton) writes: >> Another sense, perhaps more relevant to the present discussion, is >> that in Lisp & Scheme there's no way to get a pointer to the middle >> of a structure. You can't have a pointer to the cdr of a list... > >(setq a '(foo (bar baz))) >(setq b (cdr a)) >(rplaca b 'bog) ~= (setf (car b) 'bog) If you look back at my whole message, and the others I've sent on this topic, it should be clear what I meant. Well, perhaps not. What you can't do is: (setq a '(some list)) (setq b (pointer-to (cdr a))) [Here, the value of b is not (list), but rather a pointer object that refers to the cdr field of the cons that was (and still is, so far) the value of a. The value of the expression (reference-of b) is (list).] (setf (reference-of b) 'modified-list) and then have a = (some modified-list). If you think of a cons cell as having two fields, what you can't have is a pointer to the second field. You can, of course, assign the contents of the second field to a variable. (Actually, you can do it in a sense, because you can implement pointer-to and reference-of using a structure that contains set and reference thunks (for example). What Lisp lacks is a primitive pointer facility that does this.) Compare typedef struct cons_struct {struct cons_struct *car, *cdr} *cons; cons a, *b; a = make-list("(some list)"); b = &a.cdr; *b = make-symbol("modified-list"); -- Jeff
Chris.Holt@newcastle.ac.uk (Chris Holt) (11/22/90)
There is a discussion here (if I understand it correctly) about how one can constrain two variables in such a way that a change to one will effect a change in the other. In particular, if a is set to a list, and b is set to the cdr of that list, then a change in b ought to cause a change in a. [This is my interpretation of the discussion between Jeff Dalton and Peter da Silva re: >>(setq a '(foo (bar baz))) >>(setq b (cdr a)) >>(rplaca b 'bog) ]. Since this sort of thing only makes sense in a temporal context, would it not be reasonable to view pointers/aliasing as the introduction of a temporal constraint, along the lines of: From time_current to time_end_of_scope Ensure b = cdr a together with the assumption that everything remains the same over time unless explicitly changed, or unless a change is needed to maintain the constraints? That is, rather than view b as a pointer into a, view it as a distinct variable that is constrained with respect to a? I find the semantics of the latter easier to understand (but what do I know? :-) ----------------------------------------------------------------------------- Chris.Holt@newcastle.ac.uk Computing Lab, U of Newcastle upon Tyne, UK ----------------------------------------------------------------------------- "He either fears his fate too much, or his programming tools are small..."
peter@ficc.ferranti.com (Peter da Silva) (11/24/90)
In article <3808@skye.ed.ac.uk> jeff@aiai.UUCP (Jeff Dalton) writes: > What you can't do is: > (setq a '(some list)) > (setq b (pointer-to (cdr a))) But "a" is already a "pointer" to "cdr a". In this case the "reference" operation is simply "cdr". You want to factor the pointer out of the cons. I don't care if you can or not: the cons already has the same semantics as a pair of pointers, and everything that can be said "about" pointers can be said "about" a cons. -- Peter da Silva. `-_-' +1 713 274 5180. 'U` peter@ferranti.com
barmar@think.com (Barry Margolin) (11/28/90)
In article <5P57P18@xds13.ferranti.com> peter@ficc.ferranti.com (Peter da Silva) writes: >In article <3808@skye.ed.ac.uk> jeff@aiai.UUCP (Jeff Dalton) writes: >> What you can't do is: > >> (setq a '(some list)) >> (setq b (pointer-to (cdr a))) > >But "a" is already a "pointer" to "cdr a". In this case the "reference" >operation is simply "cdr". > >You want to factor the pointer out of the cons. I don't care if you can >or not: the cons already has the same semantics as a pair of pointers, and >everything that can be said "about" pointers can be said "about" a cons. But if you had a function that expected one pointer, you can't pass it a cons, because that is two pointers. Also, assuming that you define conses as pointers to one of their cells (Maclisp/Zetalisp "disembodied" property lists do precisely this, arbitrarily defining a cons as a pointer to its cdr, with the car being ignored -- this heritage resulted in Lisp Machines using CDR as their locative dereferencing instruction, so conses may still be used in place of locative pointers), then what about (setq c (pointer-to (symbol-value 'a))) (setq d (pointer-to (symbol-plist 'a))) (setq e (pointer-to (symbol-function 'a))) ? You could define a symbol as a pointer to one of its cells, but it can't "point" to all of them. [BTW, I don't think the Maclisp use of the cdr as the disembodied property list dereference was totally arbitrary. I think the layout of symbols and conses was such that the instruction that implements CDR of a cons happens also to implement PLIST of a symbol. This allows GET, PUTPROP, etc. operate on both symbols and disembodied plists without a runtime type check. This may not have been accidental, though, as this is true in both PDP-10 and Multics Maclisp.] -- Barry Margolin, Thinking Machines Corp. barmar@think.com {uunet,harvard}!think!barmar
jeff@aiai.ed.ac.uk (Jeff Dalton) (12/22/90)
In article <5P57P18@xds13.ferranti.com> peter@ficc.ferranti.com (Peter da Silva) writes: >In article <3808@skye.ed.ac.uk> jeff@aiai.UUCP (Jeff Dalton) writes: >> What you can't do is: > >> (setq a '(some list)) >> (setq b (pointer-to (cdr a))) > >But "a" is already a "pointer" to "cdr a". In this case the "reference" >operation is simply "cdr". And in that sense of "pointer to" it's also a pointer to (cadr a) and to (car (symbol-value (intern (elt (string (car a)) 0)))) [ie, the car of s]; it's just that the dereference operation is cadr or (lambda (x) (car (symbol-value (elt (string (car x)) 0)))). >You want to factor the pointer out of the cons. I don't care if you can >or not: the cons already has the same semantics as a pair of pointers, and >everything that can be said "about" pointers can be said "about" a cons. Then why do some Lisps add locatives? They can do things that can't be done with cons and cdr, that's why. Common Lisp simulations of locatives were posted in comp.lang.lisp not too long ago, if anyone wants to see what it involves. -- JD