Algorithm = logic + control

ABSTRACT

The notion that computation = controlled deduction was first proposed by Pay Hayes [19] and more recently by Bibel [2] and Vaughn-Pratt [31]. A similar thesis that database systems should be regarded as consisting of a relational component, which defines the logic of the data, and a control component, which stores and retrieves it, has been successfully argued by Codd [10]. Hewitt's argument [20] for the programming language PLANNER, though generally regarded as an argument against logic, can also be regarded as an argument for the thesis that algorithms be regarded as consisting of both logic and control components. In this paper we shall explore some of the useful consequences of that thesis.

REFERENCES

• 1: Bibel, W., and Schreiber, J. Proof procedures in a Gentzen-like system of first-order logic. Proc. Int. Comptng. Symp., North- Holland Pub. Co., Amsterdam, 1975, pp. 205-212.
• 2: Wolfgang Bibel, Prädikatives Programmieren, Proceedings of the 2nd GI Conference on Automata Theory and Formal Languages, p.274-283, May 20-23, 1975
• 3: Bibel, W. Syntheses of strategic definitions and their control. Bericht Nr. 7610, Abt. Mathem., Techn. Miinchen, 1976.
• 4: Bibel, W. A uniform approach to programming. Bericht Nr. 7633, Abtl. Mathem., Techn. MiJnchen, 1976.
• 5: Bledsoe, W.W., and Bruell, P. A man-machine theorem-proving system. Artif. Intell. 5 (Spring 1974), 51-72.
• 6: Clark, K.L., and T~rnlund, S.A. A first order theory of data and programs. Information Processing 77, North-Holland Pub. Co., Amsterdam, 1977, pp. 939-944.
• 7: Clark, K., and Sickel, S. Predicate logic: A calculus for the formal derivation of programs. Proc. Int. Joint Conf. Artif. Intell., 1977.
• 8: Clark, K. The synthesis and verification of logic programs. Res. Rep., Dept. Comptng. and Control, Imperial College, London, 1977.
• 9: Clark, K., and Darlington, J. Algorithm analysis through synthesis. Res. Rep., Dept. Comptng. and Control, Imperial College, London, Oct. 1977.
• 10: E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
• 11: Codd, E.F. Relational completeness of data base sublanguages. In Data Base Systems, R. Rustin, Ed., Prentice-Hall, Englewood Cliffs, N.J., 1972.
• 12: Colmerauer, A., Kanoui, H., Pasero, R., and Roussel, P. Un systeme de communication homme-machine en francais. Rapport preliminaire, Groupe de Res. en Intell. Artif., U. d'Aix-Marseille, Luminy, 1972.
• 13: Darlington, J., and Burstall, R.M. A system which automatically improves programs. Proc. of Third Int. Joint Conf. Artif. Intell., S.R.I., Menlo Park, Calif., 1973, pp. 437-542.
• 14: Darvas, F., Futo, I., and Szeredi, P. Logic based program for predicting drug interactions. To appear in Int. J. Biomedical Computing.
• 15: Amaryllis Deliyanni , Robert A. Kowalski, Logic and semantic networks, Communications of the ACM, v.22 n.3, p.184-192, March 1979 [doi>10.1145/359080.359090]
• 16: Jay Earley, An efficient context-free parsing algorithm, Communications of the ACM, v.13 n.2, p.94-102, Feb 1970 [doi>10.1145/362007.362035]
• 17: van Emden, M.H. Programming in resolution logic. To appear in Machine Representations of Knowledge published as Machine Intelligence 8, E.W. Elcock and D. Michie, Eds., Ellis Horwood and John Wylie.
• 18: Robert W. Floyd, Nondeterministic Algorithms, Journal of the ACM (JACM), v.14 n.4, p.636-644, Oct. 1967 [doi>10.1145/321420.321422]
• 19: Hayes, P.J. Computation and deduction. Proc. 2nd MFCS Symp., Czechoslovak Acad. of Sciences, 1973, pp. 105-118.
• 20: Hewitt, C. Planner: A language for proving theorems in robots. Proc. of Int. Joint Conf. Artif. Intell., Washington, D.C., 1969, pp. 295-301.
• 21: Hogger, C. Deductive synthesis of logic programs. Res. Rep., Dept. Comptng. and Control, Imperial College, London, 1977.
• 22: Kleene, S.C. Introduction to Metamathematics. Van Nostrand, New York, 1952.
• 23: Robert A. Kowalski, Logic for Problem Solving, Prentice Hall PTR, Upper Saddle River, NJ, 1979
• 24: Kowalski, R.A. Predicate logic as programming language. Information Processing 74, North-Holland Pub. Co., Amsterdam, 1974, pp. 569-574.
• 25: Robert Kowalski, A Proof Procedure Using Connection Graphs, Journal of the ACM (JACM), v.22 n.4, p.572-595, Oct. 1975 [doi>10.1145/321906.321919]
• 26: Kowalski, R.A., and Kuehner, D. Linear resolution with selection function. Artif. IntelL 2 (1971), 227-260.
• 27: D. W. Loveland, A Simplified Format for the Model Elimination Theorem-Proving Procedure, Journal of the ACM (JACM), v.16 n.3, p.349-363, July 1969 [doi>10.1145/321526.321527]
• 28: Mac Carthy, J. A basis for a mathematical theory o f computation. In Computer Programming and Formal Systems, P. Bratfort and D. Hirschberg, Eds., North-Holland Pub. Co., Amsterdam, 1967.
• 29: McSkimin, J.R., and Minker, J. The use o f a semantic network in a deductive question-answering system. Proc. Int. Joint Conf. Artif. lntell., 1977, pp. 50-58.
• 30: Petri, C.A. Grundsatzliches zur Beschreibung diskreter Prozesse 3. Colloq. uber Automathentheorie, Birkhauser Verlag, Basel, Switzerland, 1967.
• 31: Vaughan R. Pratt, The competence/performance dichotomy in programming preliminary report, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.194-200, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512968]
• 32: Robinson, J.A. Automatic deduction with hyper-resolution. Int. J. Comput. Math. 1 (1965), 227-34.
• 33: Roussel, P. Manual de reference et d'Utilisation. Groupe d ' I n t e l l . Artif., UER, Marseille-Luminy, France, 1975.
• 34: Schwarz, J. Using annotations to make recursion equations behave. Res. Memo, Dept. Artif. Intell., U. of Edinburgh, 1977.
• 35: Sickel, S. A search technique for clause interconnectivity graphs. IEEE Trans. Comptrs. (Special Issue on Automatic Theorem Proving), Aug. 1976.
• 36: T~rnlund, S.A. An interpreter for the programming language predicate logic. Proc. Int. Joint Conf. Artif. Intell., Tiblisi, 1975, pp. 601-608.
• 37: Warren, D. A system for generating plans. Memo No. 76, Dept. Comput. Logic, U. o f Edinburgh, 1974.
• 38: David H D Warren , Luis M. Pereira , Fernando Pereira, Prolog - the language and its implementation compared with Lisp, Proceedings of the 1977 symposium on Artificial intelligence and programming languages, p.109-115, August 15-17, 1977
• 39: Niklaus Wirth, Algorithms & data structures, Prentice-Hall, Inc., Upper Saddle River, NJ, 1985

INDEX TERMS

Keywords:
control language, logic programming, nonprocedural language, program specification, programming methodology, relational data structures