H. Jan Komorowski
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.
- {Arsac 79} J J Arsac, Syntactic Source to Source Transforms and Program Manipulation, Communications of the ACM, Vol 22, No 1, January 1979. Google Scholar
Digital Library
- {Apt 81} K Apt, M H Emden, Contributions to the Theory of Logic Programming, Erasmus University, The Netherlands, 1981.Google Scholar
- {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.Google ScholarCross Ref
- {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.Google Scholar
- {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.Google Scholar
- {Burstall 78} R M Burstall, M S Feather, Program Development by Transformations: An Overview, Toulouse CREST Course of Programming, Toulouse, 1978.Google Scholar
- {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.Google ScholarDigital Library
- {Clark 80} K Clark, F McCabe, IC-Prolog --- Language Features, in: {Tärnlund 80}.Google Scholar
- {Davis 80} R Davis, Meta-rules: Reasoning about Control, Artificial Intelligence Journal Vol 15, 1980.Google Scholar
- {Dincbas 80} M Dincbas, The METALOG Problem Solving System: An Informal Presentation, in: {Tärnlund 80}.Google Scholar
- {Emanuelson 80} P Emanuelson, Performance enhancement in a well-structured pattern-matcher through partial evaluation, Ph.D. Thesis, Linköping University, 1980.Google Scholar
- {Emden 76} M V Emden, R Kowalski, The Semantics of Predicate Logic as a Programming Language, J of ACM, Vol 23, No 4, October 1976. Google ScholarDigital Library
- {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.Google Scholar
- {Ershov 80} A P Ershov, Mixed Computation: Potential Applications and Problems for Study, Computing Center, Siberian Branch, USSR Ac. Sci. Novosibirsk 630090, USSR.Google Scholar
- {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.Google Scholar
- {Futamura 71} Y Futamura, Partial Evaluation of Computer Programs: An Approach to A Compiler-compiler, J. Inst. Electronics and Communication Engineers, 1971.Google Scholar
- {Gallaire 80} H Gallaire, C Lasserre, A Control Metalanguage for Logic Programming, in: {Tärnlund 80}.Google Scholar
- {Gordon 79} M J C Gordon, The Denotational Description of Programming Languages, An Introduction, Springer-Veriag, 1979. Google ScholarDigital Library
- {Haraldsson 74} A Haraldsson, PCDB --- A Procedure Generator for A Predicate Calculus Data Base, IFIP-74 Information Processing, North-Holland, 1974.Google Scholar
- {Haraldsson 77} A Haraldsson, A Program Manipulation System Based on Partial Evaluation, Ph.D. Thesis, Linköping University, Sweden 1977.Google Scholar
- {Haraldsson 80} A Haraldsson, Experiences from a program manipulation system, Linköping University, July 1980, LiTH-MAT-R-80-24.Google Scholar
- {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}Google Scholar
- {Jones 78} C B Jones, The Meta-language: A Reference Manual, in: {Björner and Jones 78}. Google ScholarDigital Library
- {Kieburtz 81} R Kieburtz, J Shultis, Transformations of FP Program Schemes, in: Invited Papers, Symposium on Functional Languages and Computer Architecture, Chalmers University of Technology, Gothenburg, 1981. Google ScholarDigital Library
- {Kleene 52} S C Kleene, Introduction to Metamathematics, Van Nostrand, New York 1952.Google Scholar
- {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.Google Scholar
- {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.Google Scholar
- {Komorowski 80} H J Komorowski, Qlog --- The Software for Prolog and Logic Programming, in: {Tärnlund 80}.Google Scholar
- {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.Google Scholar
- {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.Google Scholar
- {Kowalski 74} R Kowalski, Predicate Logic as a Programming Language, IFIP 74 Information Processing, North-Holland 1974.Google Scholar
- {Loveman 77} D B Loveman, Program Improvement by Source to Source Transformation, Journal of the ACM, Vol 24, No 1, January 1977. Google ScholarDigital Library
- {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.Google Scholar
- {McCarthy 66} J McCarthy et al, Lisp 1.5 Programmer's Manual, MIT Press, 1966. Google ScholarDigital Library
- {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.Google Scholar
- {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.Google Scholar
- {Pereira 78} L M Pereira et al, User's Guide to DECsystem-10 Prolog, September 1978.Google Scholar
- {Robinson 65} J A Robinson, A Machine-Oriented Logic Based on the Resolution Principle, Journal of ACM Vol 12, No 1, 1965. Google ScholarDigital Library
- {Sandewall 71} E Sandewall, A Programming Tool for Management of a Predicate Calculus-Oriented Data Base, Proceedings of the 2nd IJCAI, London, 1971.Google Scholar
- {Standish 76} T A Standish, An Example of Program Improvement Using Source-to-Source Transformations, Computer Science Conference, Anaheim, February 1976.Google Scholar
- {Stoy 77} J E Stoy, Denotational Semantics: The Scott-Strachey Approach to Programming Language Theory, MIT Press, 1977. Google ScholarDigital Library
- {Sussman 72} G J Sussman, T Winograd, E Charniak, Micro- Planner Reference Manual, Al Memo 203a, Al Lab, MIT, 1971. Google ScholarDigital Library
- {Teitelman 78} W Teitelman, Interlisp Reference Manual, Xerox, PARC, 1978.Google Scholar
- {Tärnlund 80}, S-Å Tärnlund, Proceedings of the Logic Programming Workshop, John von Neumann Society, Debrecen, Hungary, 1980.Google Scholar
- Partial evaluation as a means for inferencing data structures in an applicative language: a theory and implementation in the case of prolog
Recommendations
Practical partial evaluation for high-performance dynamic language runtimes
PLDI 2017: Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and ImplementationMost high-performance dynamic language virtual machines duplicate language semantics in the interpreter, compiler, and runtime system. This violates the principle to not repeat yourself. In contrast, we define languages solely by writing an ...
Comments