Article

Free access

Language facilities for programmable backtracking

Authors:

Ralph E. Griswold,

David R. HansonAuthors Info & Claims

Proceedings of the 1977 symposium on Artificial intelligence and programming languages

Pages 94 - 99

https://doi.org/10.1145/800228.806937

Published: 01 August 1977 Publication History

PDF eReader

Abstract

Most languages intended for artificial intelligence applications include a search and backtracking facility. While built-in backtracking facilities are convenient, they are often too inflexible for use beyond a limited range of applicability. Other mechanisms, such as those based on explicit manipulations of bindings or stack frames, tend to be very unstructured, and give the programmer little control over the backtracking process. This paper describes the SL5 programming language and its use for “programmable backtracking.” SL5 includes a general procedure mechanism that permits procedures to be used as recursive functions or as coroutines. Using this mechanism, the programmer can construct control hierarchies that are tailored to the specific application. A string pattern-matching facility is given as an example of the use of the SL5 facilities.

References

[1]

D. G. Bobrow and B. Rapheal. New Programming Languages for Artificial Intelligence Research, Comp. Surveys, 6, Sept. 1974, 153-174.

Digital Library

Google Scholar

[2]

C. E. Hewitt. PLANNER: A Language for Manipulating Models and Proving Theorems in a Robot, Proc. IJCAI-69, May 1969, 295-301.

Google Scholar

[3]

I. Grief and C. E. Hewitt. Actor Semantics for PLANNER-73, Conf. Rec. ACM Symp. on Princ. of Prog. Lang., Jan. 1975, 67-77.

Digital Library

Google Scholar

[4]

D. V. McDermott and G. J. Sussman. From PLANNER to CONNIVER - A Genetic Approach, Proc. FJCC, 1972, 1171-1179.

Google Scholar

[5]

G. L. Steele. LAMBDA, The Ultimate Declarative, AI Memo 379, Mass. Inst. of Tech., Nov. 1976.

Digital Library

Google Scholar

[6]

R. E. Griswold and D. R. Hanson. An Overview of SL5, SIGPLAN Notices, 12, April 1977, 40-50.

Digital Library

Google Scholar

[7]

D. R. Hanson and R. E. Griswold. The SL5 Procedure Mechanism, Comm. ACM, to appear.

Digital Library

Google Scholar

[8]

F. C. Druseikis and J. N. Doyle. A Procedural Approach to Pattern Matching in SNOBOL4, Proc. ACM Annual Conf., Nov. 1974, 311-317.

Digital Library

Google Scholar

[9]

R. E. Griswold. String Analysis and Synthesis in SL5, Proc. ACM Annual Conf., Oct. 1976, 410-414

Digital Library

Google Scholar

[10]

R. E. Griswold. The SL5 Programming Language and Its Use for Goal-Directed Programming, Proc. Fifth Texas Conf. on Computing Systems, Oct. 1976, 1-5.

Google Scholar

[11]

D. R. Hanson. A Procedure Mechanism for Backtrack Programming, Proc. ACM Annual Conf., Oct. 1976, 401-405.

Digital Library

Google Scholar

[12]

C. E. Hewitt and B. Smith. Towards a Programming Apprentice, IEEE Trans. on Software Eng., SE-1, March 1976, 26-45.

Google Scholar

Cited By

View all

Marlin C(2005)Conclusions and further researchCoroutines10.1007/3-540-10256-6_7(191-228)Online publication date: 26-May-2005
https://doi.org/10.1007/3-540-10256-6_7
Hext J(2005)Pattern-matching commandsLanguage Design and Programming Methodology10.1007/3-540-09745-7_7(105-110)Online publication date: 24-May-2005
https://doi.org/10.1007/3-540-09745-7_7
Lindstrom G(1979)Backtracking in a Generalized Control SettingACM Transactions on Programming Languages and Systems (TOPLAS)10.1145/357062.3570631:1(8-26)Online publication date: Jan-1979
https://doi.org/10.1145/357062.357063
Show More Cited By

Index Terms

Language facilities for programmable backtracking
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features
        Coroutines
2. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques
      1. Backtracking

Recommendations

Language facilities for programmable backtracking
Proceedings of the 1977 symposium on Artificial intelligence and programming languages

Most languages intended for artificial intelligence applications include a search and backtracking facility. While built-in backtracking facilities are convenient, they are often too inflexible for use beyond a limited range of applicability. Other ...
Language facilities for programmable backtracking
Proceedings of the 1977 symposium on Artificial intelligence and programming languages

Most languages intended for artificial intelligence applications include a search and backtracking facility. While built-in backtracking facilities are convenient, they are often too inflexible for use beyond a limited range of applicability. Other ...
Extending database programming language with declarative querying facilities

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Proceedings of the 1977 symposium on Artificial intelligence and programming languages

August 1977

185 pages

ISBN:9781450378741

DOI:10.1145/800228

Chairman:
James Low

ACM SIGART Bulletin Just Accepted
Proceedings of the 1977 symposium on Artificial intelligence and programming languages
August 1977
179 pages
ISSN:0163-5719
DOI:10.1145/872736
Issue’s Table of Contents
ACM SIGPLAN Notices Volume 12, Issue 8
Proceedings of the 1977 symposium on Artificial intelligence and programming languages
August 1977
179 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/872734
Issue’s Table of Contents

Permission to make digital or hard copies of part or all 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 third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 1977

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
329
Total Downloads

Downloads (Last 12 months)79
Downloads (Last 6 weeks)22

Reflects downloads up to 13 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Marlin C(2005)Conclusions and further researchCoroutines10.1007/3-540-10256-6_7(191-228)Online publication date: 26-May-2005
https://doi.org/10.1007/3-540-10256-6_7
Hext J(2005)Pattern-matching commandsLanguage Design and Programming Methodology10.1007/3-540-09745-7_7(105-110)Online publication date: 24-May-2005
https://doi.org/10.1007/3-540-09745-7_7
Lindstrom G(1979)Backtracking in a Generalized Control SettingACM Transactions on Programming Languages and Systems (TOPLAS)10.1145/357062.3570631:1(8-26)Online publication date: Jan-1979
https://doi.org/10.1145/357062.357063
Cohen J(1979)Non-Deterministic AlgorithmsACM Computing Surveys10.1145/356770.35677311:2(79-94)Online publication date: Jun-1979
https://doi.org/10.1145/356770.356773
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
Cohen J(1979)Non-Deterministic AlgorithmsACM Computing Surveys10.1145/356770.35677311:2(79-94)Online publication date: Jun-1979
https://doi.org/10.1145/356770.356773
Allison L(1978)Phrase structures, non-determinism and backtrackingInformation Processing Letters10.1016/0020-0190(78)90077-77:3(139-143)Online publication date: Apr-1978
https://doi.org/10.1016/0020-0190(78)90077-7

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

Language facilities for programmable backtracking

Language facilities for programmable backtracking

Extending database programming language with declarative querying facilities