Abstract
This paper presents a self-applicable partial evaluator for a considerable subset of full Prolog. The partial evaluator is shown to achieve non-trivial specialisation and be effectively self-applied. The attempts to self-apply partial evaluators for logic programs have, of yet, not been all that successful. Compared to earlier attempts, our lix system is practically usable in terms of efficiency and can handle natural logic programming examples with partially static data structures, built-ins, side-effects, and some higher-order and meta-level features such as call and findall. The lix system is derived from the development of the logen compiler generator system. It achieves a similar kind of efficiency and specialisation, but can be used for other applications. Notably, we show first attempts at using the system for deforestation and tupling in an offline fashion. We will demonstrate that, contrary to earlier beliefs, declarativeness and the use of the ground representation is not the best way to achieve self-applicable partial evaluators.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abramov, S.M., Glück, R.: Semantics modifiers: an approach to non-standard semantics of programming languages. In: Sato, M., Toyama, Y. (eds.) Third Fuji International Symposium on Functional and Logic Programming, page to appear. World Scientific, Singapore (1998)
Andersen, L.O.: Program Analysis and Specialization for the C Programming Language. PhD thesis, DIKU, University of Copenhagen (DIKU report 94/19) (May 1994)
Bondorf, A., Frauendorf, F., Richter, M.: An experiment in automatic selfapplicable partial evaluation of Prolog. Technical Report 335, Lehrstuhl Informatik V, University of Dortmund (1990)
Bowers, A.F., Gurr, C.A.: Towards fast and declarative meta-programming. In: Apt, K.R., Turini, F. (eds.) Meta-logics and Logic Programming, pp. 137–166. MIT Press, Cambridge (1995)
De Schreye, D., Glück, R., Jørgensen, J., Leuschel, M., Martens, B., Sørensen, M.H.: Conjunctive partial deduction: Foundations, control, algorithms and experiments. The Journal of Logic Programming 41(2,3), 231–277 (1999)
Fujita, H., Furukawa, K.: A self-applicable partial evaluator and its use in incremental compilation. New Generation Computing 6(2,3), 91–118 (1988)
Futamura, Y.: Partial evaluation of a computation process — an approach to a compiler-compiler. Systems, Computers, Controls 2(5), 45–50 (1971)
Gallagher, J.: A system for specialising logic programs. Technical Report TR-91- 32, University of Bristol (November 1991)
Gallagher, J.: Tutorial on specialisation of logic programs. In: Proceedings of PEPM 1993, pp. 88–98. ACM Press, New York (1993)
Glück, R.: On the generation of specialisers. Journal of Functional Programming 4(4), 499–514 (1994)
Glück, R., Jørgensen, J.: Efficient multi-level generating extensions for program specialization. In: Swierstra, S.D. (ed.) PLILP 1995. LNCS, vol. 982, pp. 259–278. Springer, Heidelberg (1995)
Gurr, C.A.: A Self-Applicable Partial Evaluator for the Logic Programming Language Gödel. PhD thesis, Department of Computer Science, University of Bristol (January 1994)
Gurr, C.A.: Specialising the ground representation in the logic programming language Gödel. In: Deville, Y. (ed.) Proceedings LOPSTR 1993, Workshops in Computing, Louvain-La-Neuve, Belgium, pp. 124–140. Springer, Heidelberg (1994)
Hill, P., Gallagher, J.: Meta-programming in logic programming. In: Gabbay, D.M., Hogger, C.J., Robinson, J.A. (eds.) Handbook of Logic in Artificial Intelligence and Logic Programming, vol. 5, pp. 421–497. Oxford Science Publications, Oxford University Press, Oxford (1998)
Holst, C.K.: Syntactic currying: yet another approach to partial evaluation. Technical report, DIKU, Department of Computer Science, University of Copenhagen (1989)
Jones, N.D., Gomard, C.K., Sestoft, P.: Partial Evaluation and Automatic Program Generation. Prentice-Hall, Englewood Cliffs (1993)
Jørgensen, J., Leuschel, M.: Efficiently generating efficient generating extensions in Prolog. In: Danvy, O., Thiemann, P., Glück, R. (eds.) Dagstuhl Seminar 1996. LNCS, vol. 1110, pp. 238–262. Springer, Heidelberg (1996)
Komorowski, J.: An introduction to partial deduction. In: Pettorossi, A. (ed.) META 1992. LNCS, vol. 649, pp. 49–69. Springer, Heidelberg (1992)
Leuschel, M.: Partial evaluation of the real thing. In: Fribourg, L., Turini, F. (eds.) LOPSTR 1994 and META 1994. LNCS, vol. 883, pp. 122–137. Springer, Heidelberg (1994)
Leuschel, M., De Schreye, D.: Towards creating specialised integrity checks through partial evaluation of meta-interpreters. In: Proceedings PEPM 1995, La Jolla, California, June 1995, pp. 253–263. ACM Press, New York (1995)
Leuschel, M., Jørgensen, J., Vanhoof, W., Bruynooghe, M.: Offline specialisation in Prolog using a hand-written compiler generator. Theory and Practice of Logic Programming 4(1), 139–191 (2004)
Leuschel, M., Martens, B., De Schreye, D.: Controlling generalisation and polyvariance in partial deduction of normal logic programs. ACM Transactions on Programming Languages and Systems 20(1), 208–258 (1998)
Martens, B., De Schreye, D.: Why untyped non-ground meta-programming is not (much of) a problem. The Journal of Logic Programming 22(1), 47–99 (1995)
Mogensen, T., Bondorf, A.: Logimix: A self-applicable partial evaluator for Prolog. In: Lau, K.-K., Clement, T. (eds.) Proceedings of LOPSTR 1992, pp. 214–227. Springer, Heidelberg (1992)
Pettorossi, A., Proietti, M.: Transformation of logic programs: Foundations and techniques. The Journal of Logic Programming 19&20, 261–320 (1994)
Prestwich, S.: The PADDY partial deduction system. Technical Report ECRC- 92-6, ECRC, Munich, Germany (1992)
Sahlin, D.: Mixtus: An automatic partial evaluator for full Prolog. New Generation Computing 12(1), 7–51 (1993)
Taha, W., Sheard, T.: Metaml and multi-stage programming with explicit annotations. Theoretical Computer Science 248, 211–242 (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Craig, SJ., Leuschel, M. (2004). LIX: an Effective Self-applicable Partial Evaluator for Prolog. In: Kameyama, Y., Stuckey, P.J. (eds) Functional and Logic Programming. FLOPS 2004. Lecture Notes in Computer Science, vol 2998. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24754-8_8
Download citation
DOI: https://doi.org/10.1007/978-3-540-24754-8_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-21402-1
Online ISBN: 978-3-540-24754-8
eBook Packages: Springer Book Archive