Two-level control structure for nondeterministic programming

ABSTRACT

The basic ideas of nondeterministic programming are critically reconsidered to single out a proper attitude and programming style for languages allowing direct control of nondeterministic features. The proposed attitude aims at retaining the purity of the nondeterministic formulation of search processes on one level (the attempt level), deferring the coordination of problem solving efforts to another (the choice level). The feasibility of recognizing these two levels is discussed, stressing that the structure to be managed at the choice level is a tree of contexts. The leaves are computational environments, each holding an alternative under inspection, while the other nodes are associated with choice points. According to the proposed programming style, a generative function is associated with each choice point, which expresses the desired choice strategy. The main advantage of this approach is the localization of the search strategies: Each nonterminal node of the tree keeps track of the state of the computation as it was when the choice point was last interrogated, holding at the same time the strategy to coordinate the available alternatives. Examples are given in term of ND-Lisp, an extension of Lisp designed and implemented according to these guidelines.

REFERENCES

• 1: Daniel G. Bobrow , Ben Wegbreit, A model and stack implementation of multiple environments, Communications of the ACM, v.16 n.10, p.591-603, Oct. 1973 [doi>10.1145/362375.362379]
• 2: Daniel G. Bobrow , Bertram Raphael, New Programming Languages for Artificial Intelligence Research, ACM Computing Surveys (CSUR), v.6 n.3, p.153-174, Sept. 1974 [doi>10.1145/356631.356632]
• 3: Davies, D. Popler: A POP2 planner. Memo MIP-89, Dep. Machine Intel. and Perception, U. of Edinburgh, Edinburgh, 1971.
• 4: Fahlman, S.E. A planning system for robot construction tasks. Artificial Intel. J. 5,1 (Spring 1974), 1-50.
• 5: Robert W. Floyd, Nondeterministic Algorithms, Journal of the ACM (JACM), v.14 n.4, p.636-644, Oct. 1967 [doi>10.1145/321420.321422]
• 6: 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]
• 7: Hewitt, C. Procedural embedding of knowledge in PLANNER. Proc. 2nd Int. Joint Conf. Artificial Intel., London, 1971, pp. 167- 182.
• 8: John McCarthy, LISP 1.5 Programmer's Manual, The MIT Press, 1962
• 9: Montangero, C., Pacini, G., and Turini, F. Magma-LISP: A machine language for Artificial Intelligence. Proc. 4th Int. Joint Conf. Artificial Intel., Tbilisi, 1975, pp. 556-561.
• 10: Reboh, R., and Sacerdoti, E. A preliminary QLISP manual. Tech. Note No. 81, Stanford Res. Inst. AI Center, Stanford, Calif., Aug. 1973.
• 11: Rulifson, J.F., Waldinger, R.J., and Derksen, J.A. QA4: A procedural calculus for intuitive reasoning. Tech. Note No. 73, Stanford Res. Inst. AI Center, Stanford, Calif., Nov. 1972.
• 12: Smith, D.C., and Enea, H.J. Backtracking in MLISP2. Proc. 3rd Int. Joint Conf. Artificial Intel., Stanford, Calif., 1973, pp. 671-685.
• 13: Gerald Sussman , Terry Winograd, Micro-Planner Reference Manual, Massachusetts Institute of Technology, Cambridge, MA, 1970
• 14: Sussman, G.J., and McDermott, D.V. From Planner to Conniver, a genetic approach. Proc. AFIPS F JCC 72, Vol. 41, Pt. II, AFIPS Press, Montvale, N.J., 1171-1179.
• 15: Teitelman, W. Interlisp Reference Manual. Xerox Palo Alto Res. Ctr., Palo Alto, Calif., 1974.

INDEX TERMS

Keywords:
artificial intelligence, backtracking, context tree, control structures, nondeterministic programming, search strategy planning