Re: pointer elimination in C

Karen Miller <miller@crx.ece.cmu.edu> writes:
>I am translating C into another language which does not implement pointers.


Unfortunately this is an instance of a problem deeply studied and well
beyond the state of the art; I've heard it discussed as "the aliasing
problem" and as "the name problem" (as in "name" = "address").


You will definitely be able to solve some instances of it. It's the
general solution that is thus far unsolved...unless you take the cheap way
out, which I'll mention shortly.


The general difficulty can be state thusly: a pointer can be the result of
arbitrary computation, for instance:


int *
foo(i)
int i;
{
int *base = hairy_pointer_computation(i);


return &base[ hairy_integer_computation(i) ];
}


To figure out the return value (e.g. in order to translate it into a
non-pointer form) could require predicting at translation-time the results
of both hairy computations, which is known to be insoluble in general,
since this amounts to the halting problem, and even for limited classes of
algorithms, is often intractable even if a specific finite computation is
involved that side-steps the general halting problem.


But there is that cheap way out that I mentioned. To wit: make all of
memory in the source language a single array in the target language, and
then translate all pointer arithmetic in the source language (C) into
indexes in the target language.


That will work in all theoretical cases, although you'll probably run into
nasty implementation issues.


This is an unesthetic solution, but it is general, and short of some
completely new way of approaching things that doesn't involve the halting
problem, appears to be the *only* completely general solution.


Then again, I could be wrong. But you see the *apparent* problem, yes?


On the third hand you might find that you can achieve what you need to by
implementing a less than general data dependency algorithm as others
suggested. It depends on your purpose, but if you can get away with it,
that approach is probably the most rewarding.


I thank my former co-worker Dr. John Banning for teaching me anything in
the above that I said that is correct, and accept full blame for anything
that may be incorrect.


That's one way of saying that I haven't kept up on the literature. :-)
Doug
--
Doug Merritt doug@netcom.com
--

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