Re: Death by pointers.

hbaker@netcom.com (Henry Baker)
Mon, 11 Sep 1995 16:27:38 GMT

          From comp.compilers

Related articles
Order of argument evaluation in C++, etc. hbaker@netcom.com (1995-07-08)
Death by pointers. (Was: order of argument evaluation in C++, etc.) johnston@imec.be (1995-08-30)
Re: Death by pointers. jhallen@world.std.com (1995-09-05)
Re: Death by pointers. whitten@netcom.com (1995-09-05)
Re: Death by pointers. chase@centerline.com (1995-09-06)
Re: Death by pointers. hbaker@netcom.com (1995-09-11)
Re: Death by pointers. graham.matthews@pell.anu.edu.au (1995-09-12)
Re: Death by pointers. chase@centerline.com (1995-09-12)
Re: Death by pointers. preston@tera.com (1995-09-13)
Re: Death by pointers. ECE@dwaf-hri.pwv.gov.za (John Carter) (1995-09-23)
Re: Death by pointers. stefan.monnier@epfl.ch (Stefan Monnier) (1995-09-25)
| List of all articles for this month |

Newsgroups: comp.compilers
From: hbaker@netcom.com (Henry Baker)
Keywords: optimize, theory
Organization: nil organization
References: 95-07-068 95-09-030 95-09-074
Date: Mon, 11 Sep 1995 16:27:38 GMT

>, 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
--


Post a followup to this message

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