Requirements for advanced programming systems for list processing

ABSTRACT

List processing systems should be designed to facilitate production of large programs to manipulate large complex symbolic data stores. This paper presents an overview of a number of system features which the author feels are important to improve the productivity of programmers working in such domains. A systems view is taken, rather than focusing just on language features, since algorithms must be not only coded in a language form, but debugged, modified, made efficient, and run on data. Because of this general framework, the requirements specified are applicable to the design of advanced programming systems for a wide range of applications. Three aspects of programming systems are highlighted: good interactive facilities, programmable control structures, and sophisticated data communication mechanisms. Interactive features are described to facilitate program composition, entry, testing, debugging, editing, optimization, and packaging. Implementation of a generalized environment structure model specified would allow programming of various control regimes including multiprocesses, coroutines and backtracking. Alternative methods of procedure invocation required include invocation by pattern and by monitoring condition. The need for extended data forms, storage management, and extensibility are stressed, as is the duality of data retrieval and function evaluation. Syntax directed input and output of data would facilitate use of complex data stores.

REFERENCES

• 1: Anderson, R.H. Syntax directed recognition of hand printed two dimensional mathematics. Ph.D. Th. Harvard U., Jan. 1968.
• 2: Berkeley, E.C., and Bobrow, D.G. (Eds.) The Programming Language LISP; Its Operation and Applications. MIT Press, Cambridge, Mass., 1966.
• 3: Bobrow, D.G. Natural language input for a computer problem solving system. Ph.D. Th. MIT, 1964, In Minsky {24}.
• 4: Bobrow, D.G. Storage management in LISP. Proc. IFIP Conf. on Symbol Manipulation Languages. North Holland Pub. Co., Amsterdam, 1967.
• 5: Daniel G. Bobrow , Daniel L. Murphy, Structure of a LISP system using two-level storage, Communications of the ACM, v.10 n.3, p.155-159, March 1967 [doi>10.1145/363162.363185]
• 6: Daniel G. Bobrow , Bertram Raphael, A comparison of list-processing computer languages: including a detailed comparison of COMIT, IPL-V, LISP 1.5, and SLIP, Communications of the ACM, v.7 n.4, p.231-240, April 1964 [doi>10.1145/364005.364057]
• 7: Bobrow, D.G., and Wegbreit, B. A model and stack implementation of multiple environments. BBN Rep. No. 2334, Mar. 1972. (Submitted to a technical publication.)
• 8: P. Branquart , J. Lewi , M. Sintzoff , P. L. Wodon, The composition of semantics in Algol 68, Communications of the ACM, v.14 n.11, p.697-708, Nov. 1971 [doi>10.1145/362854.362874]
• 9: Dijkstra, E.W. Cooperating sequential processes. In Programming Languages. F. Genuys (Ed.), Academic Press, New York, 1967.
• 10: Burstall, R.M., Collins, J.S., and Popplestone, R.J. Programming in POP-2, Edinburgh U. Press, Edinburgh, 1971.
• 11: David Allen Fisher, Control structures for programming languages, 1970
• 12: Robert W. Floyd, Nondeterministic Algorithms, Journal of the ACM (JACM), v.14 n.4, p.636-644, Oct. 1967 [doi>10.1145/321420.321422]
• 13: Solomon W. Golomb , Leonard D. Baumert, Backtrack Programming, Journal of the ACM (JACM), v.12 n.4, p.516-524, Oct. 1965 [doi>10.1145/321296.321300]
• 14: Green, C.C. Theorem proving by resolution as a basis for question-answering systems. In Machine Intelligence 4. American Elsevier Pub. Co., Inc., New York, 1969.
• 15: Ralph E Griswold, The SNOBOL 4 programming language, Prentice-Hall, Inc., Upper Saddle River, NJ, 1971
• 16: Hewitt, C. PLANNER: a language for manipulating models and proving theorems in a robot. Proc. IJCAI, Washington, D.C., 1969.
• 17: Hewit, C. Description and theoretical analysis (using schemata) of PLANNER: a language for proving theorems and manipulating models in a robot. Ph.D. Th. MIT, Feb. 1971.
• 18: Hewitt, C. Procedural embedding of knowledge in PLANNER. Proc. Second lJCAl, London, 1971.
• 19: Ichbiah, J.D., and Morse, S.P. General concepts of the SIMULA 67 programming language. Companie Internationale pour le lnformatique DR. SA. 69. 132 ND, Paris, Sept. 1971.
• 20: John McCarthy, Recursive functions of symbolic expressions and their computation by machine, Part I, Communications of the ACM, v.3 n.4, p.184-195, April 1960 [doi>10.1145/367177.367199]
• 21: John McCarthy, LISP 1.5 Programmer's Manual, The MIT Press, 1962
• 22: Michie, D. Memo functions: a language feature with rote-learning properties..Proc. IFIP, Edinburgh, 1968.
• 23: Harlan D. Mills, Syntax-directed documentation for PL360, Communications of the ACM, v.13 n.4, p.216-222, April 1970 [doi>10.1145/362258.362271]
• 24: Marvin L. Minsky, Semantic Information Processing, The MIT Press, 1969
• 25: Moses, J. The function of function in LISP. ACM SIGPLAN Notices. June 1969.
• 26: Alan J. Perlis, The Synthesis of Algorithmic Systems, Journal of the ACM (JACM), v.14 n.1, p.1-9, Jan. 1967 [doi>10.1145/321371.321372]
• 27: Prenner, C. Multi-path control structures for programming languages. Ph.D. Th. Harvard U., June, 1972.
• 28: Prenner, C., Spitzer, J., and Wegbreit, B. An implementation of backtracking for programming languages. (To appear in ACM 72).
• 29: Raphael, B., Bobrow, D.G., Fein, L., and Young, J.W., A brief survey of computer languages for symbolic and algebraic manipulation. Proc. IFIP 1967 Conf. on Symbol Manipulation Languages, North Holland Pub. Co., Amsterdam.
• 30: Rulifson, J.F., Waldinger, R.J., and Dirksen, J.A. QA4, a language for writing problem-solving programs. Proc. IFIP 1968 Congress, TA-2 P111-115.
• 31: Samuels, A.L. Some studies in machine learning using the game of checkers. IBM J. R & D 3, 3 (1959).
• 32: Gerald Sussman , Terry Winograd, Micro-Planner Reference Manual, Massachusetts Institute of Technology, Cambridge, MA, 1970
• 33: Standish, T.A. A data definition facility for programming languages. PhD. Th. Carnegie Institute of Technology, Pittsburgh, Pa., May 1970.
• 34: Teitelman, W. Design and implementation of FLIP, a LISP format directed list processor. BBN Report AFCRL-67-0514, July 1967.
• 35: Teitelman, W. Toward a programming laboratory. Proc. IJCAI, Washington, D.C., 1969, 1-8.
• 36: Teitelman, W., Bobrow, D.G., Hartley, A.K., and Murphy, D.L. BBN-LISP, TENEX reference manual. Bolt Beranek and Newman, July 1971.
• 37: Wegbeit, B. Studies in extensible programming languages. Ph.D. Th. Harvard U., 1970 (available as ESD-TR-70-297).
• 38: Wegbreit, B. The ECL programming system. Proc. 1971 FJCC, Vol. 39, AFIPS Press, Montvale, N.J., pp. 253-262.
• 39: Wegner, P. Information structure models. Proc. SIGPLAN Symposium on Data Structures in Programming Languages. ACM SIGPLAN Notices 6 (Feb. 1971), 1-54.
• 40: Winograd, T. Procedures as a representation for data in a computer program for understanding natural language. Ph.D. Th. MIT, 1970, Project MAC TR-84, MIT, Cambridge, Mass., Feb. 1971.

INDEX TERMS

Keywords:
advanced programming systems, control structures, data structures, design of programming languages, interactive systems, list processing, programming languages, programming primitives, semantics