Thumbnail
Access Restriction
Subscribed

Author Pacini, G. ♦ Turini, F. ♦ Montangero, C.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Control structures ♦ Backtracking ♦ Search strategy planning ♦ Context tree ♦ Nondeterministic programming ♦ Artificial intelligence
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.
Description Affiliation: Univ. di Pisa, Pisa, Italy (Montangero, C.; Pacini, G.; Turini, F.)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 20
Issue Number 10
Page Count 6
Starting Page 725
Ending Page 730


Open content in new tab

   Open content in new tab
Source: ACM Digital Library