Re: pointer elimination in C (Doug Merritt)
Tue, 19 Oct 1993 04:46:50 GMT

          From comp.compilers

Related articles
pointer elimination in C (Karen Miller) (1993-10-05)
Re:pointer elimination in C (1993-10-06)
Re: pointer elimination in C (Chris DONAWA) (1993-10-10)
Re: pointer elimination in C (1993-10-19)
Re: pointer elimination in C (Robin Popplestone) (1993-10-22)
Re: pointer elimination in C (1993-10-22)
Re: pointer elimination in C (1993-10-22)
Re: pointer elimination in C (1993-10-28)
Re: pointer elimination in C (1993-10-29)
Re: pointer elimination in C rbe@yrloc.ipsa.reuter.COM (1993-11-01)
[2 later articles]
| List of all articles for this month |

Newsgroups: comp.compilers
From: (Doug Merritt)
Keywords: C, analysis
Organization: Netcom Online Communications Services
References: 93-10-032
Date: Tue, 19 Oct 1993 04:46:50 GMT

Karen Miller <> 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 *
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 Merritt

Post a followup to this message

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