Re: Death by pointers.

johnston@imec.be (Adrian Johnstone) writes:


> In the C language, alias detection in the presecence of recursive data
> structures (i.e. linked lists and up) is an NP-complete problem, which
> certainly meets my definition of insoluble ;-). I'm not at home right
> now so I can't find the reference but it's derived in someone's PhD
> thesis.


But, so's register allocation, but that doesn't stop people from trying,
and doing well enough to get by. 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.


Similarly, it appears that the targets of C pointers can often be
accurately figured out (see works of Hendren, Emami, Landi, Ryder, Pande,
Wilson, Lam, Ruf) with non-exponential analyses, though there's some
question (literally, at the last SIGPLAN conference, there were several
questions) about the validity of the benchmarks.


So, difficulty of analysis is not necessarily a show-stopper.


> In the not so distant future, all common computers will use
> superscalar processors of one form or another, and I predict that the
> detailed dataflow analysis required to get the best out of these
> machines will mandate a move towards languages which are easier to
> analyse, that is with restricted use of pointers and possibly a
> complete lack of side effects.


I think you are forgetting an obvious alternative to C and C++, that
is neither new nor sexy. 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). Dialects of Fortran are
designed to allow distribution of data across distributed-memory-
massively-parallel-processors. Hundreds, if not thousands, of
person-years of research and development have been devoted to the
greater speed of compiled Fortran. Friends still working in the
go-fast business tell me that they're having much more success with
the FP (i.e., "Fortran") benchmarks than with the integer (i.e., "C")
benchmarks on new machines with ever-deeper pipelines.


I'm not claiming that it's the language that I'd design if I were
given a chance to start from scratch, but it's there. (It's not like
C and C++ are winning any beauty contests, either.) It will be
entertaining watching speed-conscious C and C++ programmers attempt
to keep up with Fortran numerical applications.


I think you're also overestimating the efficiency of languages that
completely lack side-effects -- a naive translation of in-place pivoting
matrix factorization into a side-effect-free-language might run O(N^2)
times slower than the original, if your compiler fails to figure out that
the storage can be reused (I added the pivoting because that's what
people do, and because it will make access patterns harder to analyze).


> ...


> The most pressing question, of course, is what the new, side-effect
> reduced, language should be called.


I think the answer remains "Fortran".


speaking for myself,


David Chase


--

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