Two-Level Control Structure for Nondeterministic Programming The basic ideas of nondeterministic programming are critically reconsidered to single out a proper attitude and programming style for language 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 free of contexts. The leaves are computational environments, each holding an alternative under inspection, while the other nodes are associated with choice poin ts. According to the proposed programming style, a generative function is associated with each choice poin t, which expresses the desired choice strategy. The main advantage on 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 poin t 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. CACM October, 1977 Montangero, C. Pacini, G. Turini, F. nondeterministic programming, artificial in telligence, control structures, backtracking, search strategy planning, context tree 3.64 4.22 CA771004 JB December 27, 1977 11:30 AM 2625 4 2922 2922 4 2922 3081 4 2922 3101 4 2922 3112 4 2922 2438 5 2922 2922 5 2922 2922 5 2922 2922 5 2922