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

Re: Imperative structure-copying languages?


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

Is your primary difference compared to functional programs:

 1) how we write programs, or
 2) how efficient the programs are?

If it is 1), then it seems one would like a generalization
of record update of Haskell to nested updates.  I believe
this is interesting idea.  It also comes up in declarative
specification languages like Alloy, e.g. for expressing
frame conditions.

If your goal is 2), then this is the question of how to
implement the semantics of value copying.  I believe
copy-on-write techniques have been used in e.g. database
community but I don't know the best reference for that.

I believe that in both cases the critical question is
expressing the invariants of data structures.  There are not
too many patterns of pointer sharing in programming
languages.  For example, neither functional programming
approach nor imperative programming approach directly
support working with trees that are destructively updated,
and this covers many data structures.

In imperative programming languages, you can accidentally
create sharing, so it is hard to see that two things are
independent.  (The same thing can happen if you simulate the
heap in a functional programming language threading some
global mutable state.)  On the other hand, in functional
programming language using purely functional data structures
(like in Chris Okasaki's book), it is hard to see that two
things are almost the same, e.g. that only one part of the
structure has changed and everything else remained the same.

It seems to me that you are proposing the heap to be
immutable and local variables be mutable.  That means that
programs are essentially functional as far as reasoning
about the heap is concerned.  Consequently, if your program
does a search in a data structure and then does some local
surgery, the locality of the surgery will not be so obvious
as in an imperative programming language.  You also do not
get the efficiency of imperative data structures with
destructive updates unless you discover some pointer
uniqueness invariants and replace copy-on-write with
in-place update.

  Viktor