Re: Death by pointers.

>, chase@centerline.com (David Chase) wrote:


> ML type inference is DEXPTIME-complete,
> if I read the title of the paper right:
>
> @inproceedings{mairson:90,
> title="Deciding {ML} Typability is Complete for Deterministic
> Exponential Time",
> author="Harry G. Mairson",
> booktitle=popl17, address="San Francisco, California",
> year=1990, month=jan, pages="382--401"
> }
>
> but, in practice, it runs in something like linear time, because typical
> inputs are not hard to solve.


Yes, but aliasing elicits exactly the same sort of behavior that causes
the exponential nature of ML typability (ML type inference). So I
wouldn't generalize from your statement to the statement that aliasing is
also something like linear in time.


>Fortran simplifies analysis by mandating
> that parameters aren't aliased (in theory, you can check this at
> run-time, but nobody does that I know of).


Uh... I'd be interested in seeing your efficient algorithm for this. It's one
thing to check that all of the formal parameters to a procedure are not aliased
at top level to each other, but quite another to check that one parameter
doesn't point at a substructure of another parameter.


--
www/ftp directory:
ftp://ftp.netcom.com/pub/hb/hbaker/home.html
--

Return to the comp.compilers page.
Search the comp.compilers archives again.