btC: A Backtracking Procedural Language
Yaowei Liu, John Staples · Australian Software Engineering Conference · 1991
This paper outlines btC, a variant of the programming language C which supports backtracking computation. Backtracking is a way to deterministically emulate non deterministic computation. Providing programming support for backtracking simplifies the programmer's task and hence contributes to the reliability of the software produced. Support for backtracking is provided by logic programming languages such as Prolog, and earlier backtracking procedural languages. Prolog introduces performance penalties unrelated to backtracking, due for example to Prolog's slow database access mechanism and its limited range of data structures. Early backtracking procedural languages lack backtracking expressiveness, and are inefficient because of obsolete implementation techniques. The language btC has been designed to avoid those problems through more powerful backtracking expressions and a more efficient control structure. As well as being an efficient procedural language, it includes all of Prolog's backtracking expressiveness. Further it successfully manages backtracking over dynamic allocation of memory, and over lower level updates which may violate type constraints. In this paper, motivations for built-in support of backtracking are discussed, btC support for backtracking is described, and implementation in C by preprocessing is indicated. The implementation uses an extension of the Prolog backtracking mechanism. The techniques developed are also useful for the study of broad-spectrum programming languages which combine procedural and logic programming capabilities.