Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!uakari.primate.wisc.edu!aplcen!haven!adm!cmcl2!lanl!jlg
From: jlg@lanl.gov (Jim Giles)
Newsgroups: comp.lang.misc
Subject: Re: Answers, Chapter 1: TeX
Message-ID: <5344@lanl.gov>
Date: 8 Nov 90 19:18:48 GMT
References: <12614:Nov801:02:4990@kramden.acf.nyu.edu>
Organization: Los Alamos Natl Lab, Los Alamos, N.M.
Lines: 60

From article <12614:Nov801:02:4990@kramden.acf.nyu.edu>, by brnstnd@kramden.acf.nyu.edu (Dan Bernstein):
> In article <5241@lanl.gov> jlg@lanl.gov (Jim Giles) writes:
>> The number of different _possible_ partitions in your scheme varies
>> as 2^N where N is the number of procedure arguments.
> 
> No, it does not. That's the third incorrect formula you've posted for
> the same quantity.

You are correct, the formula (as I admitted) is incorrect.  The actual
number of different partitions is _greater_than_ 2^N (where N is the
number of parameters).

> [...]
>> This ignores the
>> possible aliasing of globals which multiplies in another big factor.
> 
> I have not been ignoring globals; as I indicate in the article you're
> studying, *all* possibly aliased pointers must be considered together.

But, my extimate (2^N) did - that is what I was referring to: the fact
that 2^N is only an estimate of the number of partitions among parameters.
In order for _my_ estimate to be correct, _I_ would have to include
globals into the mix.  _I_ was the one that was ignoring globals, not
_you_.  I never accused _you_ of ignoring globals.

> [...]
>> Well, you have an exponential naming problem (at least), which is more
>> than a few bits.
> 
> Again, you are dreaming. Say the compiler gives up at 20 copies of the
> same code (which in practice gives hellishly good coverage). How many
> bits does it take to encode an integer between 1 and 20.

Well, let's try it shall we?  I have a program with 5 parameters.
Let's call the parameters 'a' through 'e'.  The possible partitions
of these 6 are below:

   {{a}{b}{c}{d}{e}} {{a b}{c}{d}{e}} {{a b}{c d}{e}} {{a b}{c e}{d}}
   {{a b}{c}{d e}} {{a b}{c d e}} {{a c}{b}{d}{e}} {{a c}{b d}{e}}
   {{a c}{b e}{d}} {{a c}{b}{d e}} {{a c}{b d e}} {{a d}{b}{c}{e}}
   {{a d}{b c}{e}} {{a d}{b e}{c}} {{a d}{b}{c e}} {{a d}{b c e}}
   {{a e}{b}{c}{d}} {{a e}{b c}{d}} {{a e}{b d}{c}} {{a e}{b}{c d}}
   {{a e}{b c d}} {{a}{b c}{d}{e}} {{a}{b c}{d e}} {{a}{b d}{c}{e}}
   {{a}{b d}{c e}} {{a}{b e}{c}{d}} {{a}{b e}{c d}} {{a}{b}{c d}{e}}
   {{a}{b}{c e}{d}} {{a}{b}{c}{d e}} {{a b c}{d}{e}} {{a b c}{d e}}
   {{a b d}{c}{e}} {{a b d}{c e}} {{a b e}{c}{d}} {{a b e}{c d}}
   {{a c d}{b}{e}} {{a c d}{b e}} {{a c e}{b}{d}} {{a c e}{b d}}
   {{a d e}{b}{c}} {{a d e}{b c}} {{a}{b c d}{e}} {{a}{b c e}{d}}
   {{a}{b d e}{c}} {{a}{b}{c d e}} {{a b c d}{e}} {{a b c e}{d}}
   {{a b d e}{c}} {{a c d e}{b}} {{a}{b c d e}} {{a b c d e}}

Well, there are 52 of these (remember, I said that the number was
_at_least_ 2^N).  So, if you're going to stop at 20, which 20 are
you going to pick.  No matter which ones you pick, I can give
explicit assertions (remember _your_ scheme permits these) that
describe one that's not on your list of 20 - so you have to
have a consistent way of giving this new version a name.  As I
said, you have an exponential naming problem (at least).

J. Giles