Partial evaluation as a means for inferencing data structures in an applicative language: a theory and implementation in the case of prolog

ABSTRACT

An operational semantics of the Prolog programming language is introduced. Meta-IV is used to specify the semantics. One purpose of the work is to provide a specification of an implementation of a Prolog interpreter. Another one is an application of this specification to a formal description of program optimization techniques based on the principle of partial evaluation.Transformations which account for pruning, forward data structure propagation and opening (which also provides backward data structure propagation) are formally introduced and proved to preserve meaning of programs. The so defined transformations provide means to inference data structures in an applicative language. The theoretical investigation is then shortly related to research in rule-based systems and logic.An efficient well-integrated partial evaluation system is available in Qlog --- a Lisp programming environment for Prolog.

REFERENCES

• 1: Jacques J. Arsac, Syntactic source to source transforms and program manipulation, Communications of the ACM, v.22 n.1, p.43-54, Jan. 1979 [doi>10.1145/359046.359057]
• 2: {Apt 81} K Apt, M H Emden, Contributions to the Theory of Logic Programming, Erasmus University, The Netherlands, 1981.
• 3: {Beckman 76} L Beckman, A Haraldsson, Ö Oskarsson, E Sandewall, A Partial Evaluator and its Use as a Programming Tool, Artificial Intelligence Journal 7, 1976, pp. 319--357.
• 4: {Björner and Jones 78} D Björner, C B Jones, eds, The Vienna Development Method: The Meta-Language, Lecture Notes in Computer Science, Vol 61, Springer-Verlag, 1978.
• 5: {Boyer and Moore 72} R S Moore, J S Moore The Sharing of Structure in Theorem Proving Programs, in Machine Intelligence 7, Meltzer and Michie, eds, Edinburgh 1972.
• 6: {Burstall 78} R M Burstall, M S Feather, Program Development by Transformations: An Overview, Toulouse CREST Course of Programming, Toulouse, 1978.
• 7: {Cheatham 79} T Cheatham, G Holloway, J Townley, Symbolic Evaluation and the Analysis of Programs, IEEE Transactions on Software Engineering, Vol SE-5, No 4, July 1979.
• 8: {Clark 80} K Clark, F McCabe, IC-Prolog --- Language Features, in: {Tärnlund 80}.
• 9: {Davis 80} R Davis, Meta-rules: Reasoning about Control, Artificial Intelligence Journal Vol 15, 1980.
• 10: {Dincbas 80} M Dincbas, The METALOG Problem Solving System: An Informal Presentation, in: {Tärnlund 80}.
• 11: {Emanuelson 80} P Emanuelson, Performance enhancement in a well-structured pattern-matcher through partial evaluation, Ph.D. Thesis, Linköping University, 1980.
• 12: M. H. Van Emden , R. A. Kowalski, The Semantics of Predicate Logic as a Programming Language, Journal of the ACM (JACM), v.23 n.4, p.733-742, Oct. 1976 [doi>10.1145/321978.321991]
• 13: {Ershov 77} A P Ershov, Correctness of Mixed Computation in Algol-like Programs, Proceedings of the 6th MFCS Symposium, in: Lecture Notes in Computer Science, Vol 53, Springer-Verlag, 1977.
• 14: {Ershov 80} A P Ershov, Mixed Computation: Potential Applications and Problems for Study, Computing Center, Siberian Branch, USSR Ac. Sci. Novosibirsk 630090, USSR.
• 15: {Ershov and Itkin 77} A P Ershov, V E Itkin, Corectness of Mixed Computation in an Algol-like programs, in Lecture Notes in Computer Science, vol 53, Springer Verlag, 1977.
• 16: {Futamura 71} Y Futamura, Partial Evaluation of Computer Programs: An Approach to A Compiler-compiler, J. Inst. Electronics and Communication Engineers, 1971.
• 17: {Gallaire 80} H Gallaire, C Lasserre, A Control Metalanguage for Logic Programming, in: {Tärnlund 80}.
• 18: Michael J. C. Gordon, The Denotational Description of Programming Languages: An Introduction, Springer-Verlag New York, Inc., Secaucus, NJ, 1979
• 19: {Haraldsson 74} A Haraldsson, PCDB --- A Procedure Generator for A Predicate Calculus Data Base, IFIP-74 Information Processing, North-Holland, 1974.
• 20: {Haraldsson 77} A Haraldsson, A Program Manipulation System Based on Partial Evaluation, Ph.D. Thesis, Linköping University, Sweden 1977.
• 21: {Haraldsson 80} A Haraldsson, Experiences from a program manipulation system, Linköping University, July 1980, LiTH-MAT-R-80-24.
• 22: {Henhapl 78} W Henhapl, C B Jones, A Formal Definition of Aigol-60 as described in the modified Report, in {Björner and Jones 78}
• 23: Cliff B. Jones, The META-Language: A Reference Manual, The Vienna Development Method: The Meta-Language, p.218-277, January 1978
• 24: Richard B. Kieburtz , Jonathan Shultis, Transformations of FP program schemes, Proceedings of the 1981 conference on Functional programming languages and computer architecture, p.41-48, October 18-22, 1981, Portsmouth, New Hampshire, United States [doi>10.1145/800223.806761]
• 25: {Kleene 52} S C Kleene, Introduction to Metamathematics, Van Nostrand, New York 1952.
• 26: {Komorowski 76} H J Komorowski, Familia --- A Question-Answering System in Prolog with Natural Language Interface, M Sc Thesis, University of Warsaw, 1976. In Polish.
• 27: {Komorowski 79} H J Komorowski, Qlog Interactive Programming Environment --- The Experience form Embedding A Generalized Prolog in Interlisp, paper read at International Summer Seminar on Artificial Intelligence, Dubrovnik, August 1979. Also, Informatics Laboratory, Linköping University, LiTH-MAT-R-79-19.
• 28: {Komorowski 80} H J Komorowski, Qlog --- The Software for Prolog and Logic Programming, in: {Tärnlund 80}.
• 29: {Komorowski 81} H J Komorowski, J W Goodwin, Embedding Prolog in Lisp: An Example of A Lisp Craft Technique, SSRC, Linköping University, March 1981, LiTH-MAT-R-81-2. Paper read at Symposium on Functional Programming Languages and Computer Architecture in Gothenburg, June 1981, Sweden.
• 30: {Komorowski 81a} H J Komorowski, A Specification of an Abstract Prolog Machine and its Application to Partial Evaluation, Ph.D. thesis no 69, Linköping University, Sweden 1981.
• 31: {Kowalski 74} R Kowalski, Predicate Logic as a Programming Language, IFIP 74 Information Processing, North-Holland 1974.
• 32: David B. Loveman, Program Improvement by Source-to-Source Transformation, Journal of the ACM (JACM), v.24 n.1, p.121-145, Jan. 1977 [doi>10.1145/321992.322000]
• 33: {Martelli 76} A Martelli, U Montanari, Unification in Linear Time and Space: A Structured Presentation, Consiglio Nazionale delle Recierche, Istituto di Elaborazione della Informazione, Nota Interna B76-16, Pisa, 1976.
• 34: John McCarthy, LISP 1.5 Programmer's Manual, The MIT Press, 1962
• 35: {Ollongren 80} A Ollongren, On the Implementation of Parts of Meta-IV in Lisp, SSRC, Linköping University, LiTH-MAT-R-81-7, April 1981.
• 36: {Ostrovsky 80} B N Ostrovsky, Obtaining Language Oriented Parser Systematically by Means of Mixed Computation, in: Translation and Program Models, Ed. I V Pottosin, Computing Center, Novosibirsk, 69--80. In Russian.
• 37: {Pereira 78} L M Pereira et al, User's Guide to DECsystem-10 Prolog, September 1978.
• 38: J. A. Robinson, A Machine-Oriented Logic Based on the Resolution Principle, Journal of the ACM (JACM), v.12 n.1, p.23-41, Jan. 1965 [doi>10.1145/321250.321253]
• 39: {Sandewall 71} E Sandewall, A Programming Tool for Management of a Predicate Calculus-Oriented Data Base, Proceedings of the 2nd IJCAI, London, 1971.
• 40: {Standish 76} T A Standish, An Example of Program Improvement Using Source-to-Source Transformations, Computer Science Conference, Anaheim, February 1976.
• 41: Joseph E. Stoy, Denotational Semantics: The Scott-Strachey Approach to Programming Language Theory, MIT Press, Cambridge, MA, 1977
• 42: Gerald Sussman , Terry Winograd, Micro-Planner Reference Manual, Massachusetts Institute of Technology, Cambridge, MA, 1970
• 43: {Teitelman 78} W Teitelman, Interlisp Reference Manual, Xerox, PARC, 1978.
• 44: {Tärnlund 80}, S-Å Tärnlund, Proceedings of the Logic Programming Workshop, John von Neumann Society, Debrecen, Hungary, 1980.