Continuation-passing Models of Backtracking

Appeared in Volume 8/4, November 1995

mikpe@ida.liu.se
Mikael Pettersson
20th September 1995

I am trying to trace the history of the use of continuations in modeling backtracking control flow, esp. for languages like Prolog.

One popular model, call it the "single-continuation model", explains backtracking by mapping it to a traditional non-backtracking language with procedure closures. "And"-control is modeled by passing a procedure (the success continuation) to the first conjunct. When it succeeds, it applies the success continuation it was given. This continuation then proceeds with the second conjunct. When all solutions have been computed, just "return".

The ordinary recursion stack deals with "or"-control. Disjunctions simply become: "prove first disjunct; prove second disjunct".

The earliest references I've seen that make exactly this connection are [MellishHardy84] and [Carlsson84]. (Many later papers reference one of these two.) A slightly different thread is [Nilsson83] which references [Sandewall76]. Sandewall's conversion uses "remainder procedures" (his terminology). As far as I can see, they are equivalent to success continuations. In a different context, Koster used this technique to perform top-down parsing of left-recursion free ambiguous grammars [Koster75].

If you know denotational semantics, then you'll also know that the ordinary recursion stack can be modeled with continuations. Applying this knowledge to the single-continuation model, one realizes that "return stack" is equivalent to "failure continuation". The earliest Prolog papers I've seen that use this explicit double-continuation model are [NicholsonFoo89] and [deBruin89]. Charniak et al [CharniakRMM87] used it to describe chronological backtracking, but exactly where they got the idea is unknown to me.

Any help in locating earlier references for the single- or double- continuation models would be much appreciated.

I'm not terribly interested in papers that use mappings to Scheme's call/cc or to languages with built-in support for coroutines.

References

[CharniakRMM87] Artifical Intelligence Programming, 2nd ed. Lawrence Erlbaum Associates, Inc. 1987.

[deBruin89] "Continuation Semantics for Prolog with Cut". Proc. TAPSOFT'89, Vol. 1: CAAP'89, pages 178-192. LNCS-351. 1989.

[Koster75] "A Technique for Parsing Ambiguous Languages". In: D. Siefkes (ed.) "GI-4.Jahrestagung", pages 233-246. LNCS 26. 1975.

[MellishHardy84] "Integrating Prolog in the POPLOG environment". In: Tick and Succi (eds.) Implementations of Logic Programming Systems, pages 147-162. 1984.

[NicholsonFoo89] "A Denotational Semantics for Prolog". ACM TOPLAS 11(4), pages 650-665. 1989.

[Nilsson83] "On the compilation of a domain-based Prolog". In: Mason (ed.) Information Processing 83, pages 293-298. 1983.

[Sandewall76] "Conversion of Predicate-Calculus Axioms to Corresponding Deterministic Programs", IEEE Transactions on Computers, Vol. C-25, No. 4, pages 342-346. 1976.