Path: utzoo!utgpu!news-server.csri.toronto.edu!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: <10397:Oct1212:55:1090@kramden.acf.nyu.edu>
Date: 12 Oct 90 12:55:10 GMT
References: <26739:Oct1023:44:2690@kramden.acf.nyu.edu> <65450@lanl.gov>
Organization: IR
Lines: 61

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