article

Free access

Two-level control structure for nondeterministic programming

Authors:

F. TuriniAuthors Info & Claims

Communications of the ACM, Volume 20, Issue 10

Pages 725 - 730

https://doi.org/10.1145/359842.359850

Published: 01 October 1977 Publication History

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]

Bobrow, D.G., and Wegbreit B. A model and stack implementation of multiple environments. Comm. ACM 16,10 (Oct. 1973), 591-603.

Digital Library

[2]

Bobrow, D.G., and Raphael, B. New programming languages for artificial intelligence research. Computing Surveys 6,3 (Sept. 1974), 153-174.

Digital Library

[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.

Digital Library

[5]

Floyd, R.W. Nondeterministic algorithms. J. ACM 14,4 (Oct. 1967), 636-644.

Digital Library

[6]

Golomb, S.W., and Baumert, L.D. Backtrack programming. J. ACM 12,4 (Oct. 1965), 516-524.

Digital Library

[7]

Hewitt, C. Procedural embedding of knowledge in PLANNER. Proc. 2nd Int. Joint Conf. Artificial Intel., London, 1971, pp. 167- 182.

Digital Library

[8]

McCarthy, J., et al. LISP 1.5 Programmer's Manual. M.I.T. Press, Cambridge, Mass., 1962.

Digital Library

[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]

Sussman, G.J., and Winograd, T. Micro-Planner reference manual. A.I. Memo No. 203, Project MAC, M.I.T., Cambridge, Mass., July 1970.

Digital Library

[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.

Digital Library

[15]

Teitelman, W. Interlisp Reference Manual. Xerox Palo Alto Res. Ctr., Palo Alto, Calif., 1974.

Cited By

Pacini GTurini F(2019)Semantics of production systemsInformation and Computation10.1016/0890-5401(87)90016-273:2(87-101)Online publication date: 4-Jan-2019
https://dl.acm.org/doi/10.1016/0890-5401%2887%2990016-2
Montangero CPacini GSimi MTurini F(2019)Information management in context treesActa Informatica10.1007/BF0026092610:1(85-94)Online publication date: 2-Jan-2019
https://dl.acm.org/doi/10.1007/BF00260926
Cohen J(2018)Non-Deterministic AlgorithmsACM Computing Surveys (CSUR)10.1145/356770.35677311:2(79-94)Online publication date: 29-Aug-2018
https://dl.acm.org/doi/10.1145/356770.356773
Show More Cited By

Recommendations

Converting two-way nondeterministic unary automata into simpler automata

We show that, on inputs of length exceeding 5n2, any n-state unary two-way nondeterministic finite automaton (2nfa) can be simulated by a (2n+2)-state quasi-sweeping 2nfa. Such a result, besides providing a “normal form” for 2nfa's, enables us to get a ...
Nondeterministic fuzzy automata

To handle fuzzy uncertainty in system modeling, nondeterministic finite automata have been generalized into fuzzy automata. After a reexamination of the notions of fuzzy automata in the literature, we ascertain that the fundamental property-...
Converting Two-Way Nondeterministic Unary Automata into Simpler Automata
MFCS '01: Proceedings of the 26th International Symposium on Mathematical Foundations of Computer Science

We show that, on inputs of length exceeding 5n², any n- state unary 2nfa (two-way nondeterministic finite automaton) can be simulated by a (2n+2)-state quasi sweeping 2nfa. Such a result, besides providing a "normalform" for 2nfa's, enables us to get a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Communications of the ACM

Communications of the ACM Volume 20, Issue 10

Oct. 1977

93 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/359842

Editor:
Robert L. Ashenhurst
Univ. of Chicago, Chicago, IL

Issue’s Table of Contents

Copyright © 1977 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1977

Published in CACM Volume 20, Issue 10

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
363
Total Downloads

Downloads (Last 12 months)61
Downloads (Last 6 weeks)11

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Pacini GTurini F(2019)Semantics of production systemsInformation and Computation10.1016/0890-5401(87)90016-273:2(87-101)Online publication date: 4-Jan-2019
https://dl.acm.org/doi/10.1016/0890-5401%2887%2990016-2
Montangero CPacini GSimi MTurini F(2019)Information management in context treesActa Informatica10.1007/BF0026092610:1(85-94)Online publication date: 2-Jan-2019
https://dl.acm.org/doi/10.1007/BF00260926
Cohen J(2018)Non-Deterministic AlgorithmsACM Computing Surveys (CSUR)10.1145/356770.35677311:2(79-94)Online publication date: 29-Aug-2018
https://dl.acm.org/doi/10.1145/356770.356773
Colombetti MGuida G(2018)Supporting control definition in programming languagesComputer Languages10.1016/0096-0551(84)90009-29:1(1-23)Online publication date: 23-Dec-2018
https://dl.acm.org/doi/10.1016/0096-0551%2884%2990009-2
Turini F(2008)The Semantics of Ugo MontanariConcurrency, Graphs and Models10.1007/978-3-540-68679-8_52(804-805)Online publication date: 1-Jun-2008
https://dl.acm.org/doi/10.1007/978-3-540-68679-8_52
Helsgaun K(1995)CBack: A simple tool for backtrack programming in CSoftware: Practice and Experience10.1002/spe.438025080525:8(905-934)Online publication date: Aug-1995
https://doi.org/10.1002/spe.4380250805
Yaowei Liu (1993)Prolog vs procedural backtrackingProceedings of TENCON '93. IEEE Region 10 International Conference on Computers, Communications and Automation10.1109/TENCON.1993.320003(364-368)Online publication date: 1993
https://doi.org/10.1109/TENCON.1993.320003
Turini F(1984)Magma2: a language oriented toward experiments in controlACM Transactions on Programming Languages and Systems10.1145/1780.17846:4(468-486)Online publication date: 1-Oct-1984
https://dl.acm.org/doi/10.1145/1780.1784
Degano P(1983)Artificial IntelligencePictorial Data Analysis10.1007/978-3-642-82017-5_12(239-264)Online publication date: 1983
https://doi.org/10.1007/978-3-642-82017-5_12
Bellia M(1981)Hierarchical development of programming languagesCalcolo10.1007/BF0257635818:3(219-254)Online publication date: Sep-1981
https://doi.org/10.1007/BF02576358
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents