zbMATH — the first resource for mathematics

Efficient specialisation in Prolog using the hand-written compiler generator LOGEN. (English) Zbl 0958.68036
Leuschel, Michael (ed.), WOID ’99. Workshop on optimization and implementation of declarative programs. Las Cruces, NM, USA, December 2-3, 1999. Amsterdam: Elsevier, Electronic Notes in Theoretical Computer Science. 30,2, 6 p., electronic only (1999).
Summary: The so called “COGEN approach” to program specialisation, writing a compiler generator instead of a specialiser, has been used with considerable success in partial evaluation of both functional and imperative languages. In earlier work we have shown that this approach is also applicable to partial evaluation of logic programming languages, also called partial deduction. In this paper we extend upon this by allowing partially instantiated datastructures (via binding types), which are especially important in the context of logic programming. We also extend COGEN to directly support a large part of Prolog’s declarative and non-declarative features and how semi-online specialisation can be efficiently integrated. Benchmarks show that the resulting COGEN is very efficient, generates very efficient generating extensions (executing up to several orders of magnitude faster than current online systems) which in turn perform very good and non-trivial specialisation, even rivalling existing online systems.
For the entire collection see [Zbl 0942.00050].

68N17 Logic programming
68N20 Theory of compilers and interpreters
COGEN approach
Full Text: Link
[1] Bruynooghe, M.; Leuschel, M.; Sagonas, K.: A polyvariant binding-time analysis for off-line partial deduction. Proceedings of the European symposium on programming (ESOP’98), LNCS 1381, 27-41 (April 1998)
[2] Chen, W.; Kifer, M.; Warren, D. S.: A first-order semantics of higher-order logic programming constructs. Logic programming: Proceedings of the north American conference, 1090-1114 (1989)
[3] 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, No. 2 & 3, 231-277 (November 1999) · Zbl 0944.68025
[4] C. K. Holst. Syntactic currying: yet another approach to partial evaluation. Technical report, DIKU, Department of Computer Science, University of Copenhagen, 1989.
[5] Jørgensen, J.; Leuschel, M.: Efficiently generating efficient generating extensions in prolog. Proceedings of the 1996 Dagstuhl seminar on partial evaluation, LNCS 1110, 238-262 (1996)
[6] M. Leuschel. The ecce partial deduction system and the dppd library of benchmarks. Obtainable via http://www.ecs.soton.ac.uk/ mal, 1996.
[7] Leuschel, M.; Jørgensen, J.: Efficient specialisation in prolog using a handwritten compiler generator. Technical report DSSE-TR-99-6, department of electronics and computer science, university of Southampton (September 1999) · Zbl 1085.68020
[8] 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, No. 1, 208-258 (January 1998)
[9] J. Martin and M. Leuschel. Sonic partial deduction. In Proceedings of the Third International Ershov Conference on Perspectives of System Informatics, LNCS 1755, Novosibirsk, Russia, 1999. Springer-Verlag. To appear. · Zbl 0970.68680
[10] Sahlin, D.: Mixtus: an automatic partial evaluator for full prolog. New generation computing 12, No. 1, 7-51 (1993) · Zbl 0942.68516
[11] Sterling, L.; Shapiro, E.: The art of prolog. (1986) · Zbl 0605.68002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.