Path: utzoo!attcan!uunet!cs.utexas.edu!yale!cmcl2!lanl!jlg
From: jlg@lanl.gov (Jim Giles)
Newsgroups: comp.lang.misc
Subject: Re: Some things that pointer-less languages can't do efficiently
Message-ID: <65450@lanl.gov>
Date: 11 Oct 90 06:29:18 GMT
References: <26739:Oct1023:44:2690@kramden.acf.nyu.edu>
Organization: Los Alamos Natl Lab, Los Alamos, N.M.
Lines: 56

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