The competence/performance dichotomy in programming preliminary report

ABSTRACT

We consider the problem of automating some of the duties of programmers. We take as our point of departure the claim that data management has been automated to the point where the programmer concerned only about the correctness (as opposed to the efficiency) of his program need not involve himself in any aspect of the storage allocation problem. We focus on what we feel is a sensible next step, the problem of automating aspects of control. To accomplish this we propose a definition of control based on a fact/heuristic dichotomy, a variation of Chomsky's competence/performance dichotomy. The dichotomy formalizes an idea originating with McCarthy and developed by Green, Hewitt, McDermott, Sussman, Hayes, Kowalski and others. It allows one to operate arbitrarily on the control component of a program without affecting the program's correctness, which is entirely the responsibility of the fact component. The immediate objectives of our research are to learn how to program keeping fact and control separate, and to identify those aspects of control amenable to automation.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Chomsky, N. Some Aspects of the Theory of Syntax, MIT Press, Cambridge Mass. 1965.
• 3: Cook, S. A. Axiomatic and Interpretive Semantics for an Algol Fragment. TR-79, Toronto, Feb. 1975.
• 4: Floyd, R. W. Assigning Meanings to Programs. in Mathematical Aspects of Computer Science (ed. J. T. Schwartz), 19-32. 1967.
• 5: Green, C. Cordell. The Application of Theorem Proving to Question-Answering Systems. Stanford University Computer Science Department Report CS-138. 1969.
• 6: Hayes, Patrick J. "Computation and Deduction," Proc. Symp. Math. Found. of Comp. Sci., Czech Acad. of Sciences. 1973.
• 7: Hewitt, C. E. Description and Theoretical Analysis (Using Schemata) of PLANNER: A Language for Proving Theorems and Manipulating Models in a Robot, MIT AI Lab TR-258. 1972.
• 8: ____, P. Bishop, and R. Steiger. "A Universal Modular ACTOR Formalism for Artificial Intelligence," Proc. IJCAI 3, p. 235. 1973.
• 9: C. A. R. Hoare, An axiomatic basis for computer programming, Communications of the ACM, v.12 n.10, p.576-580, Oct. 1969 [doi>10.1145/363235.363259]
• 10: Kowalski, R. Predicate Logic as Programming Language, University of Edinburgh Department of Computational Logic Memo 70. 1973.
• 11: Susumu Kuno, The predictive analyzer and a path elimination technique, Communications of the ACM, v.8 n.7, p.453-462, July 1965 [doi>10.1145/364995.365689]
• 12: McCarthy, J. Programs with Common Sense. In Semantic Information Processing (ed. Minsky, M. L.), MIT Press, Cambridge, Mass. 1968.
• 13: McDermott, D. and G. J. Sussman. The Conniver Reference Manual, MIT AI Lab Memo 259a. 1972.
• 14: ____. Flexibility and Efficiency in a Computer Program for Designing Circuits. Ph.D. Thesis, MIT AI Lab. Sept. 1976.
• 15: Zohar Manna, Second-order mathematical theory of computation, Proceedings of the second annual ACM symposium on Theory of computing, p.158-168, May 04-06, 1970, Northampton, Massachusetts, United States [doi>10.1145/800161.805161]
• 16: D. Marr , T. Poggio, From Understanding Computation to Understanding Neural Circuitry, Massachusetts Institute of Technology, Cambridge, MA, 1976
• 17: Pratt, V. R. Effect of Basis on the Size of Boolean Expressions. Proc. 16th Ann. IEEE Symp. on Foundations of Comp. Sci., 119-121. 1975.
• 18: Pratt, V. R. Semantical Considerations on Floyd-Hoare Logic. Proc. 17th Ann. IEEE Symp. on Foundations of Comp. 109-121. 1976.
• 19: Schwartz, J. A view of Program Genesis and its Implications for Future Programming Languages. In New Directions in Algorithmic Languages (ed. Schuman, S. A.), IRIA. 1976.
• 20: Tarnlund, Sten-Ake. "An Interpreter for the Programming Language Predicate Logic," Proc. IJCAI 4, p. 601. 1975.
• 21: Turing, A. M. On computable numbers, with an application to the Entscheidungsproblem, Proc. London Math. Soc., ser. 2, 42, 230-265, 43, 544-546. 1936.
• 22: Woods, W. A. Augmented Transition Networks for Natural Language Analysis. Report No CS-1 to the NSF, Aiken Computation Laboratory, Harvard University, Cambridge, Massachussetts. 1969.