Abstract
We present the latest version of the logen partial evaluation system for logic programs. In particular we present new binding-types, and show how they can be used to effectively specialise a wide variety of interpreters. We show how to achieve Jones-optimality in a systematic way for several interpreters. Finally, we present and specialise a non-trivial interpreter for a small functional programming language. Experimental results are also presented, highlighting that the logen system can be a good basis for generating compilers for high-level languages.
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
Andersen, L.O.: Program Analysis and Specialization for the C Programming Language. PhD thesis, DIKU, University of Copenhagen (DIKU report 94/19) (May 1994)
Apt, K.R., Marchiori, E.: Reasoning about Prolog programs: from modes through types to assertions. Formal Aspects of Computing 6(6A), 743–765 (1994)
Apt, K.R., Turini, F.: Meta-logics and Logic Programming. MIT Press, Cambridge (1995)
Birkedal, L., Welinder, M.: Hand-writing program generator generators. In: Penjam, J. (ed.) PLILP 1994. LNCS, vol. 844, pp. 198–214. Springer, Heidelberg (1994)
Bowers, 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)
Bruynooghe, M., Leuschel, M., Sagonas, K.: A polyvariant binding-time analysis for off-line partial deduction. In: Hankin, C. (ed.) ESOP 1998. M. Bruynooghe, M. Leuschel, and K. Sagonas, vol. 1381, pp. 27–41. Springer, Heidelberg (1998)
Cosmadopoulos, Y., Sergot, M., Southwick, R.W.: Data-driven transformation of meta-interpreters: A sketch. In: Boley, H., Richter, M.M. (eds.) PDK 1991. LNCS (LNAI), vol. 567, pp. 301–308. Springer, Heidelberg (1991)
Craig, S., Leuschel, M.: Lix: An effective self-applicable partial evaluator for Prolog. In: Kameyama, Y., Stuckey, P.J. (eds.) FLOPS 2004. LNCS, vol. 2998, pp. 85–99. Springer, Heidelberg (2004) (to appear)
De Niel, A., Bevers, E., De Vlaminck, K.: Partial evaluation of polymorphically typed functional languages: The representation problem. In: Billaud, M., et al. (eds.) Analyse Statique en Programmation Équationelle, Fonctionelle, et Logique, October 1991. Bigre, vol. 74, pp. 90–97 (1991)
Futamura, Y.: Partial evaluation of a computation process — an approach to a compiler-compiler. Systems, Computers, Controls 2(5), 45–50 (1971)
Gallagher, J.: Tutorial on specialisation of logic programs. In: Proceedings of PEPM 1993, the ACM Sigplan Symposium on Partial Evaluation and Semantics- Based Program Manipulation, pp. 88–98. ACM Press, New York (1993)
Gallagher, J., Bruynooghe, M.: Some low-level transformations for logic programs. In: Bruynooghe, M. (ed.) Proceedings of Meta90 Workshop on Meta Programming in Logic, Leuven, Belgium, pp. 229–244 (1990)
Glück, R.: Jones optimality, binding-time improvements, and the strength of program specializers. In: Proceedings of the ASIAN symposium on Partial evaluation and semantics-based program manipulation, pp. 9–19. ACM Press, New York (2002)
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)
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 (1998)
Holst, C.K.: Syntactic currying: yet another approach to partial evaluation.Technical report, DIKU, Department of Computer Science, University of Copenhagen (1989)
Holst, C.K., Launchbury, J.: Handwriting cogen to avoid problems with static typing. In: Draft Proceedings, Fourth Annual Glasgow Workshop on Functional Programming, Skye, Scotland, pp. 210–218. Glasgow University (1991)
Jones, N.D.: Partial evaluation, self-application and types. In: Paterson, M. (ed.) ICALP 1990. LNCS, vol. 443, pp. 639–659. Springer, Heidelberg (1990)
Jones, N.D.: What not to do when writing an interpreter for specialisation. In: Danvy, O., Thiemann, P., Glück, R. (eds.) Dagstuhl Seminar 1996. LNCS, vol. 1110, pp. 216–237. Springer, Heidelberg (1996)
Jones, N.D., Gomard, C.K., Sestoft, P.: Partial Evaluation and Automatic Program Generation. Prentice-Hall, Englewood Cliffs (1993)
Jones, N.D., Sestoft, P., Søndergaard, H.: An experiment in partial evaluation: The generation of a compiler generator. In: Jouannaud, J.-P. (ed.) RTA 1985. LNCS, vol. 202, pp. 124–140. Springer, Heidelberg (1985)
Jones, N.D., Sestoft, P., Søndergaard, H.: Mix: a self-applicable partial evaluator for experiments in compiler generation. LISP and Symbolic Computation 2(1), 9–50 (1989)
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)
Lakhotia, A., Sterling, L.: How to control unfolding when specializing interpreters. New Generation Computing 8, 61–70 (1990)
Leuschel, M.: The ecce partial deduction system and the dppd library of benchmarks (1996-2002), Obtainable via http://www.ecs.soton.ac.uk/~mal
Leuschel, M.: Homeomorphic embedding for online termination of symbolic methods. In: Mogensen, T.Æ., Schmidt, D.A., Sudborough, I.H. (eds.) The Essence of Computation. LNCS, vol. 2566, pp. 379–403. Springer, Heidelberg (2002)
Leuschel, M., Bruynooghe, M.: Logic program specialisation through partial deduction: Control issues. Theory and Practice of Logic Programming 2(4 & 5), 461–515 (2002)
Leuschel, M., Butler, M.: ProB: A model checker for B. In: Araki, K., Gnesi, S., Mandrioli, D. (eds.) FME 2003. LNCS, vol. 2805, pp. 855–874. Springer, Heidelberg (2003)
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)
Leuschel, M., Sørensen, M.H.: Redundant argument filtering of logic programs. In: Gallagher, J.P. (ed.) LOPSTR 1996. LNCS, vol. 1207, pp. 83–103. Springer, Heidelberg (1997)
Lloyd, J.W.: Foundations of Logic Programming. Springer, Heidelberg (1987)
Lloyd, J.W., Topor, R.W.: Making Prolog more expressive. Journal of Logic Programming 1(3), 225–240 (1984)
Makholm, H.: On Jones-optimal specialization for strongly typed languages. In: Taha, W. (ed.) SAIG 2000. LNCS, vol. 1924, pp. 129–148. Springer, Heidelberg (2000)
Martens, B.: On the Semantics of Meta-Programming and the Control of Partial Deduction in Logic Programming. PhD thesis, K.U. Leuven (February 1994)
Martens, B., Gallagher, J.: Ensuring global termination of partial deduction while allowing flexible polyvariance. In: Sterling, L. (ed.) Proceedings ICLP 1995, Kanagawa, Japan, June 1995, pp. 597–613. MIT Press, Cambridge (1995)
Mogensen, T., Bondorf, A.: Logimix: A self-applicable partial evaluator for Prolog. In: Lau, K.-K., Clement, T. (eds.) Logic Program Synthesis and Transformation. Proceedings of LOPSTR 1992, pp. 214–227. Springer, Heidelberg (1992)
Mogensen, T. Æ.: Separating binding times in language specifications.In Proceedings of FPCA 1989, pp. 12–25. ACM press, New York (1989)
Prestwich, S.: An unfold rule for full Prolog. In: Lau, K.-K., Clement, T. (eds.) Logic Program Synthesis and Transformation. Proceedings of LOPSTR 1992, Workshops in Computing, University of Manchester, pp. 199–213. Springer, Heidelberg (1992)
Safra, S., Shapiro, E.: Meta interpreters for real. In: Kugler, H.-J. (ed.) Proceedings of IFIP 1986, pp. 271–278 (1986)
Sahlin, D.: Mixtus: An automatic partial evaluator for full Prolog. New Generation Computing 12(1), 7–51 (1993)
Sterling, L., Beer, R.D.: Metainterpreters for expert system construction. The Journal of Logic Programming 6(1 & 2), 163–178 (1989)
Sterling, L., Shapiro, E.: The Art of Prolog. MIT Press, Cambridge (1986)
Taha, W., Makholm, H., Hughes, J.: Tag elimination and Jones-optimality. In: Danvy, O., Filinski, A. (eds.) PADO 2001. LNCS, vol. 2053, pp. 257–275. Springer, Heidelberg (2001)
Takeuchi, A., Furukawa, K.: Partial evaluation of Prolog programs and its application to meta programming. In: Kugler, H.-J. (ed.) Information Processing, vol. 86, pp. 415–420 (1986)
Thiemann, P.: Cogen in six lines. In: International Conference on Functional Programming, pp. 180–189. ACM Press, New York (1996)
Vanhoof, W., Bruynooghe, M., Leuschel, M.: Binding-time analysis for Mercury. In: Bruynooghe, M., Lau, K.-K. (eds.) Program Development in Computational Logic. LNCS, vol. 3049, pp. 189–232. Springer, Heidelberg (2004)
Vanhoof, W., Martens, B.: To parse or not to parse. In: Fuchs, N.E. (ed.) LOPSTR 1997. LNCS, vol. 1463, pp. 322–342. Springer, Heidelberg (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Leuschel, M., Craig, S.J., Bruynooghe, M., Vanhoof, W. (2004). Specialising Interpreters Using Offline Partial Deduction. In: Bruynooghe, M., Lau, KK. (eds) Program Development in Computational Logic. Lecture Notes in Computer Science, vol 3049. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-25951-0_11
Download citation
DOI: https://doi.org/10.1007/978-3-540-25951-0_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22152-4
Online ISBN: 978-3-540-25951-0
eBook Packages: Springer Book Archive