Path: utzoo!attcan!uunet!wuarchive!cs.utexas.edu!yale!cmcl2!kramden.acf.nyu.edu!brnstnd
From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein)
Newsgroups: comp.lang.misc
Subject: Re: Some things that pointer-less languages can't do efficiently
Message-ID: <21253:Oct1323:11:5090@kramden.acf.nyu.edu>
Date: 13 Oct 90 23:11:50 GMT
References: <10397:Oct1212:55:1090@kramden.acf.nyu.edu> <65642@lanl.gov>
Organization: IR
Lines: 136

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