An implementation of backtracking for programming languages

ABSTRACT

Primitive operations for backtracking and a technique for their implementation are described. The technique is applicable to all programming languages whose control structure is strictly hierarchical. A general stack model for such languages is presented and a realization of the backtracking primitives is described in terms of this model. The primitives give the user control over which assignments to variables will be 'undone' when backtracking. Moreover, their realization, at each point of choice, does not save the entire current machine state but only a relatively small amount of information sufficient to later reconstruct that machine state. Consequently, the implementation makes efficient use of storage and makes backtracking a practical programming device for dealing with complex problems.

REFERENCES

• 1: Solomon W. Golomb , Leonard D. Baumert, Backtrack Programming, Journal of the ACM (JACM), v.12 n.4, p.516-524, Oct. 1965 [doi>10.1145/321296.321300]
• 2: Robert W. Floyd, Nondeterministic Algorithms, Journal of the ACM (JACM), v.14 n.4, p.636-644, Oct. 1967 [doi>10.1145/321420.321422]
• 3: Johansen, P., "Non-deterministic, programming", BIT, 7, 289, 1967.
• 4: Wegbreit, B. et al, ECL programmer's manual, 1972, Center for Research in Computing Technology, Harvard University, Cambridge.
• 5: Wegbreit, B., "The ECL programming system", Proc. AFIPS 1971 FJCC, 39, p.253, AFIPS Press, Montvale, N.J.
• 6: Dijkstra, E.W., "Recursive programming", Numerische Mathematik, 2, 312, 1960. Also in Programming Systems and Languages., S. Rosen (ed.), 1967, McGraw-Hill, New York.
• 7: Daniel G. Bobrow, Requirements for advanced programming systems for list processing, Communications of the ACM, v.15 n.7, p.618-627, July 1972 [doi>10.1145/361454.361491]
• 8: Bobrow, D. and Wegbreit, B., "A model and stack implementation of multiple environments", BBN Report No. 3334, 1972.
• 9: Wegner, P., "Data structure models for programming languages", Proc. Symposium on Data Structures in Programming Languages, p. 1, 1971, Gainesville, Florida.
• 10: Hewitt, C., "PLANNER: A language for manipulating models and proving theorems in a robot", Proc. International Joint Conference on Artificial Intelligence, p.295, 1969, Washington, D.C.
• 11: Spitzen, J.M., "Non-deterministic algorithms in ECL", ECL Working Memo, 1971, Center for Research in Computing Technology, Harvard University, Cambridge.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Backtracking

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Control structures

General Terms:
Languages, Performance

Keywords:
Backtrack programming, Choice functions, Control structures, Dendrarchy, Environments, Extensible control structures, Heuristic methods, Non-determinism, Problem solving, Retention, Scoping of variables, Stack allocation