Ken%MIT-OZ%MIT-MC@sri-unix.UUCP (01/17/84)
When I was visiting ICOT, Ehud Shapiro suggested a way to incorporate mutable arrays into Prolog. His idea is that you have predicates for creating arrays, referencing elements, and updating that in principle could have been written in Pure Prolog using ordinary terms. The updating in principle works by copying the entire array except for the changed element. The idea though was that behind the scenes the system would be using real arrays and if one tried to use an old (obsolete) version of an array one got an error or failure (its a matter of taste which one). Well, I implemented his scheme in LM-Prolog. (It took less than one hour since the Lisp Machine provides arrays and LM-Prolog is designed to be extensible.) Then I showed it to people here in Uppsala and we came up with the idea that the old versions of an updated array may be useful and besides its nicer to have a more complete implementation. Manny Rayner had recently sketched out a rather different scheme for solving the same problem. After a few hours of discussion with Lars-Henrik Eriksson and Manny we worked out a solution that we are happy with. I implemented it yesterday and would like people to tell me what they think of it. The basic idea is that an old array reference is a data structure which contains old indices and values for elements that have been updated and a pointer to another array reference or the real array. An array reference of the most recent version of an array has practically no overhead over an array reference in Lisp or Pascal. Older versions of arrays don't even exist is other programming languages and the overhead for their use is proportional to the number of updates that have been performed since it was created. One difficulty is that an array update is fairly expensive. It needs to create at least one new array reference (in the current implementation that takes 5 words) and needs to do trailing. Several compile-time optimizations are possible. In the case where the relevant part of the program is deterministic and the variables holding the old array references are not used after being updated, then in principle all this could compile to just ordinary array references and updates. A couple of interesting features of our scheme: (1) Arrays can be created as initialized or not. If not then they behave as if they are full of independent variables. This is handy when the array is being used as a table but is not being updated. (2) All of the Lisp Machine array features are available. Multiple dimensions, overlays, offsets, etc. Also for initialized arrays the array elements can be 1 bit, 2 bit, 4 bit, 8 bit, 16 bit or 32 bit long. This means that, E.g. character strings can be represented at least 8 times more densely than if lists are used as in other Prologs. (3) Old arrays references are garbage collectable. All consing, including the construction of the array itself, is done on the equivalent of the local stack, so that the memory they use are reclaimed upon failure. (4) If an old array reference is being used a lot then it could be converted to being an ordinary array for improved lookup at the cost of memory. This should perhaps be viewed as control information that the user provides. This part of the scheme is not yet implemented. All this and yet the three predicates involved (CREATE-ARRAY, UPDATE, and LOOKUP) could have been written in Pure Prolog. I've neglected to give a list of useful applications for arrays, character and bit strings since any book on algorithms is full of them. Also, this scheme very easily generalizes to any large data structure which one normally deals with by side-effecting elements. (E.g. hash tables, record structures...) Comments ?
grunwald@uiuccsb.UUCP (01/27/84)
#R:sri-arpa:-1582300:uiuccsb:9400003:000:369 uiuccsb!grunwald Jan 26 18:39:00 1984 re: definition of arrays in Prolog You might want to look at the CLU reference manual. They provide a facility similar to what you descibe. An array or record are inmutable, but you may create a new one which containing modified cells. Look at Springer-Verlag Lecture Series in Computer Science, Issue #114. Dirk Grunwald University of Illinois grunwald@uiuc (CSnet)