[Prev][Next][Index][Thread]

Re: Imperative structure-copying languages?

     Thanks to all for the interesting recent discussion on C
semantics.  There are still a lot of problems with C-like
languages, many of them having to do with pointer aliasing.
Pointer aliasing makes semantics more difficult to specify and
analysis more difficult to do.  Pure functional languages are
nicer wrt pointer aliasing, but a lot of people don't seem to
want to switch to them.

     A reasonable compromise might be imperative languages with
no destructive pointer aliasing.  What I mean by that is
imperative languages in which two pointers A and B can point to
the same object, but in which it is impossible for an update to
A to affect what pointer B points to.  This would presumably be
implemented by some sort of partial structure copying.

     The kind of algorithms we could write in such languages
would be the same as the kind we could write in functional
languages, with similar efficiency, just expressed using
imperative language constructs.  This may prompt the thought
that if people don't use functional languages, they won't use
such languages either.  On the other hand, if someone had told
me 10 years ago that we would now have a very well-established
language which is imperative but does garbage collection and
uses type tags on data structures, I don't know if I would have
believed it.  Maybe imperative structure-copying languages are
the way of the future.

     The ideas that follow are probably half-baked versions of
well-known research, so please save me the further embarrassment
of continuing to erroneously re-state the obvious and let me
know where I can find work in this area.

Here is the kind of thing I mean.  We interpret the statement

  p = e;

where p is a pointer and e is an expression, exactly as in C.
That is, the current value of p gets clobbered and becomes the
value of the expression e.  However, we interpret the statement

  p->f = e;

where f is a field, as

  p = p[e/f];

where the expression on the right of the = means "a copy of the
thing that p points to, only with the field f changed to the
value of e".  Similarly, when passing a pointer value inside a
pointed-to struct, to a function that can change what it points
to, e.g.

  change_pointer(p->next);

we interpret this as the same as

  fresh_p = p->next;
  change_pointer(fresh_p);
  p->next = fresh_p;  /* i.e. p = p[fresh_p/next] */

Thus, a function which appends a new node to the end of a linked
list would act just like a functional-program "append" function,
copying the old list all the way down (or rather, all the way
back up, if you take my meaning).

cheers
--Jamie.