Logical Update View

Appeared in Volume 6/2, May 1993

andrew@ifc6000.IFComputer.de
Andrew Verden
11th January 1993

Does anyone know where the 'logical update view' of Prolog databases stems from? Any good references would be appreciated.

tim@quintus.com
Tim Lindholm
12th January 1993

See: T.G. Lindholm and R.A. O'Keefe, "Efficient implementation of a defensible semantics for dynamic Prolog code", In LP: Proc. of the 4th Int. Conf., Vol. 1. J.-L. Lassez (ed.), MIT Press 1987. pp21-39.

The presentation in that paper motivates the ideas and develops the implementation from a "vanilla" WAM. It should be accessible to anyone who knows how a WAM works.

rss@seg.npl.co.uk
Roger Scowen
14th January 1993

In December 1984, Prolog standardization started in Britain (BSI = British Standards Institution) and, after June 1985, ran jointly with France (AFNOR).

Chris Moss from Imperial College [1] pointed out to the BSI Prolog standardization panel in September 1985 that implementations of assert/1 and retract/1 differ. He proposed the logical update view in a paper [2] in February 1986, and this was published formally later that year [3].

The BSI and AFNOR Prolog panels adopted his proposal in July 1986 [4].

International standardization started in October 1987, and at that point, the new participants in the working group (ISO/IEC JTC1 SC22 WG17) naturally insisted on re-examining all the decisions taken so far. The `logical update view' proved contentious. Chris Moss pointed out that the work of Tim Lindholm and Richard O'Keefe [5] was pertinent - it showed that the logical update view could be implemented efficiently. Both papers [2,5] were reprinted for WG17 [6].

After much discussion, changing and rechanging of minds, and aided by Egon Boerger, Dean Rosenzweig, Bart Demoen and others, WG17 eventually reaffirmed [7] the BSI and AFNOR decision in July 1991.

[1] C D S Moss, Assert and retract tests and results, BSI IST/5/17 (Prolog) PS/74, September 1985.

[2] C D S Moss, Cut & paste - defining the impure primitives of Prolog, BSI IST/5/17 (Prolog) PS/94, [February 1986].

[3] C D S Moss, Cut & paste - defining the impure primitives of Prolog, In 3rd Int. Conf. on LP, LNCS, Vol 255, Springer Verlag, Berlin 1986, pp.686-694.

[4] T Cox, Minutes of Semantics Subgroup meeting, 8th July 1986, BSI IST/5/17 (Prolog) PS/126, July 1986.

[5] T G Lindholm, R A O'Keefe, See previous item.

[6] C D S Moss, T G Lindholm, R O'Keefe, Prolog semantics - Cut, assert and retract, ISO/IEC JTC1 SC22 WG17 N37, May 1989.

[7] N D North, R S Scowen (eds), Paris 1991 meeting: minutes, resolutions, participants, ISO/IEC JTC1 SC22 WG17 N79 (= SC22 N1054), July 1991.

tim.lindholm@quintus.com
Tim Lindholm
24th March 1993

Referring to the citations of the last email, my recollection of the development of the 'logical update view' goes like this:

When I joined Quintus in 1985, one of the first things I did was to design and implement an indexing scheme for dynamic Prolog clauses. The way we were doing dynamic code prior to that time led to some nasty memory usage and performance penalties (see [5]), so I implemented a new semantics using timestamps for Quintus Prolog 2.0. This was fully developed and ready for beta testing sometime before July, 1986, when we showed 2.0b at the London LP conference, the conference where [3] was presented. We saw [3], which agreed with our semantics but didn't propose an implementation, as a confirmation of our ideas.

My work was quite independent of [2] and [3], although I think we had [1]. Rather, the semantics was borrowed from the relational database community, and the notion of using timestamps to achieve that semantics was taken from an unfinished paper by Richard O'Keefe at Edinburgh.

I eventually wrote up my work in terms of a "vanilla WAM" rather than the actual proprietary design [5]. That paper introduced the terms "logical view", "immediate update view" and the "implementational view". It also showed that, of the two semantics which were reasonably easy to understand and close to what the LP community meant by assert/retract, only the "logical view" had an efficient implementation. The other reasonable semantics, the "immediate update view" that Quintus had been using prior to 2.0, was shown to necessarily lead to an inefficient implementation when implemented using WAM-like technology.

Quintus has used the semantics and implementation introduced for 2.0 ever since and, as far as I know, there has been no significant technical improvement or correction to it in the literature. I don't think that any of the documents coming out of the standards effort attempt to introduce anything new in this area, but rather simply discuss whether this semantics should be accepted as part of the Prolog standard.