Path: utzoo!utgpu!news-server.csri.toronto.edu!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: <65642@lanl.gov>
Date: 12 Oct 90 22:17:27 GMT
References: <10397:Oct1212:55:1090@kramden.acf.nyu.edu>
Organization: Los Alamos Natl Lab, Los Alamos, N.M.
Lines: 146

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