The DOI matches its Crossref record; 11 of the 11 references it cites were found in a registry or an index; 1 of the 9 sources its claims cite were checked for support.
Efficient Specialisation in Prolog Using the Hand-Written Compiler Generator LOGEN
Open accessAbstract
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.
Overview
AI snapshot
Written from the paper’s full text.
TL;DR
The paper presents LOGEN, a hand-written compiler generator (cogen) for efficient specialisation of Prolog programs, extending the cogen approach with binding types for partially instantiated structures and support for many Prolog features. Benchmarks show LOGEN is very fast and produces specialised programs competitive with or surpassing mixtus and ecce on several tasks, though it cannot pass the KMP-test and relies on hand-performed binding-type analysis.
Key findings
- LOGEN is reported as by far the fastest specialisation system overall, running up to almost 3 orders of magnitude faster than existing online systems; for example, on `ex depth` the LOGEN cogen took 1.5 ms and the generating extension 7.2 ms, versus 200 ms for mixtus and 190 ms for ecce without file writing.
- The specialised programs are competitive: LOGEN surpasses both mixtus and ecce for `ex depth`, `grammar`, `regexp:r1`, and `regexp:r2`; e.g. `grammar` speedups are 15.16 for LOGEN, 14.40 for mixtus, and 9.60 for ecce, and `regexp:r1` speedups are 6.35, 6.23, and 4.26 respectively.
- The improved cogen can deal with all benchmarks in the dppd suite and a new non-declarative benchmark specialising non-ground unification with occurs-check; ecce could not be applied to `ng unify`, where LOGEN ran in 430 ms with speedup 3.72 and mixtus ran in 360 ms with speedup 4.44.
- LOGEN cannot pass the KMP-test: for `match.kmp`, LOGEN took 3260 ms with speedup 1.15, compared with mixtus at 2570 ms/speedup 1.46 and ecce at 1940 ms/speedup 1.93.
Methods
- Design: a hand-written compiler generator (cogen) for Prolog partial deduction, using a binding-type analysis with static, dynamic, and nonvar types for partially static structures; it supports extra-logical features, side effects, `call/1`, negation, disjunction, and if-then-else, and generates generating extensions incorporating an unfolding predicate `p_u` for each predicate `p`.
- Data: benchmarks from the dppd suite plus a new non-declarative benchmark for non-ground unification with occurs-check; comparisons are against mixtus 0.3.6 and ecce, run under SICStus Prolog 3.7.1 on a Sun Ultra E450 server with 256Mb RAM under SunOS 5.6.
- Analysis: measured specialisation times for the cogen and generating extensions, and runtimes/speedups of the specialised programs; the binding-type analysis was carried out by hand.
Limitations
- Paper states that the binding-type analysis was carried out by hand; in a fully automatic system the cogen runtimes would need to be increased by the time needed for binding-type analysis, and further work is needed to derive binding-type classifications automatically while still ensuring termination.
- Paper states that, being a pure offline system, LOGEN cannot pass the KMP-test; more sophisticated local control would be required.
- Evident from the text: full formal and technical details are omitted due to space restrictions and are said to be in a technical report; the paper presents only an overview and benchmark summary.
Model-written summary. Check it against the paper before relying on it.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
1 of 9 cited sources checked · 0 supported · 0 flagged · accuracy not yet measured
- Findingreasoning
The improved cogen of this paper can now deal with all the benchmarks in [6].
“The improved cogen of this paper can now deal with all the benchmarks in 6].”
Quote in the paperSubstantial claim0 of 1 sources checked- cites [6] M. Leuschel. The ecce partial deduction system and the dppd library of benchmarks. Obtainable via http://www.ecs.soton.ac.uk/~mal, 1996.
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Findingnone given
The cogen directly supports a large part of Prolog's declarative and non-declarative features.
“We also extend cogen to directly support a large part of Prolog's declarative and non-declarative features”
Quote in the paperSubstantial claim - Findingown data
Semi-online specialisation can be efficiently integrated into cogen.
“how semi-online specialisation can be e ciently integrated”
Quote in the paperSubstantial claim - Findingown data
Generating extensions rival existing online systems.
“even rivalling existing online systems.”
Quote in the paperSubstantial claim - Findingown data
The resulting cogen generates very efficient generating extensions.
“generates very e cient generating extensions”
Quote in the paperSubstantial claim
- Findingown data
Generating extensions perform very good and non-trivial specialisation.
“which in turn perform very good and non-trivial specialisation”
Quote in the paperSubstantial claim - Findingown data
Generating extensions execute up to several orders of magnitude faster than current online systems.
“(executing up to several orders of magnitude faster than current online systems)”
Quote in the paperSubstantial claim - Findingown data
The resulting cogen is very efficient.
“Benchmarks show that the resulting cogen is very e cient”
Quote in the paperSubstantial claim - Findingown data
The specialisation performed by the LOGEN system is not very far off the one obtained by mixtus and ecce.
“Table 2, the specialisation performed by the logen system is not very far o the one obtained by mixtus and ecce”
Quote in the paperSubstantial claim - Findingown data
For ex depth, grammar, regexp:r1, and regexp:r2, LOGEN's runtimes surpass both mixtus and ecce.
“times logen even surpasses both of them (for ex depth, grammar, regexp:r1 and regexp:r2)!”
Quote in the paperSubstantial claim - Findingown data
In Table 1, logen is by far the fastest specialisation system overall.
“logen is by far the fastest specialisation system overall”
Quote in the paperSubstantial claim - Findingown data
Logen runs up to almost 3 orders of magnitude faster than the existing online systems.
“running up to almost 3 orders of magnitude faster than the existing online systems.”
Quote in the paperSubstantial claim - Findingown data
LOGEN cannot pass the KMP-test, as seen in the timings for match:kmp in Table 2.
“Being a pure oine system, logen cannot pass the KMP-test, which can be seen in the timings for match:kmp in Table 2.”
Quote in the paperNot a substantial claim - Interpretationnone given
The cogen and the compilers it generates can use all features of the implementation language.
“the cogen and the compilers it generates can use all features of the implementation language.”
Quote in the paperNot a substantial claim - Interpretationnone given
A refined treatment of the call/1 predicate has been developed, allowing improved specialisation of higher-order programs.
“A re ned treatment of the call/1 predicate has also been developed, allowing improved specialisation of higher-order programs.”
Quote in the paperNot a substantial claim - Interpretationreasoning
The initial approach in [5] was often too weak for logic programs.
“which w as often too weak for logic programs”
Quote in the paperSubstantial claim0 of 1 sources checked- cites [5] Jørgensen, 1996, Efficiently generating efficient generating extensions in Prolog source
- Rests on an assumption: Partially instantiated data structures appear naturally in logic programs even at runtime.
- Premisecitation
Due to the limitations of the initial cogen, only very few realistic benchmarks could be run.
“However, due to the limitations of the initial cogen only very few realistic benchmarks could be run.”
Quote in the paperSubstantial claim0 of 1 sources checked- cites [5] Jørgensen, 1996, Efficiently generating efficient generating extensions in Prolog source
- Interpretationnone given
The cogen provides a way to handle extra-logical features such as var/1 or if-then-else and side-effects such as print/1.
“a way to handle both extra-logical features (such a s var/1 or the if-thenelse) and side-eects (such a s print/1) within the cogen .”
Quote in the paperSubstantial claim - Interpretationnone given
The binding-type analysis and the cogen have to be run only once for every program and division.
“However, the binding-type analysis and the cogen have t o b e r u n only once for every program and division.”
Quote in the paperSubstantial claim - Premisecitation
Most of the benchmarks of the dppd suite [6] could not be used because they require the treatment of partially instantiated data.
“In particular, most of the benchmarks of the dppd suite 6] could not be used because they require the treatment of partially instantiated data.”
Quote in the paperSubstantial claim0 of 1 sources checked- cites [6] M. Leuschel. The ecce partial deduction system and the dppd library of benchmarks. Obtainable via http://www.ecs.soton.ac.uk/~mal, 1996.
Couldn’t be matched to a paper in Crossref, so it can’t be checked.
- Probably not a substantial claim. 12
- It may state two separate claims as one. 6
Probably not a substantial claim. The paper’s conclusions may not depend on it. It may state two separate claims as one.
PremisecitationEcce can only handle declarative programs and therefore could not be applied on the ng unify benchmark.
“Note that ecce can only handle declarative programs, and could therefore not be applied on the ng unify benchmark.”
Quote in the paperNot a substantial claim1 of 2 sources checked- cites [8] Leuschel, 1998, Controlling generalisation and polyvariance in partial deduction of normal logic programs, ACM Transactions on Programming Languages and Systems source
Section 5.1 (Systems; page not provided) says ECCE assumes its supported Prolog built-ins are declarative, which supports a narrower version of the claimed restriction. Our copy does not say ECCE can handle only declarative programs or identify an “ng unify” benchmark that it could not handle. Its reported experiments instead include ground-unification benchmarks (Section 5.3). (LLM, conf=0.78)
Experimental — accuracy not yet measured - cites [3] De Schreye, 1999, Conjunctive partial deduction: Foundations, control, algorithms and experiments, The Journal of Logic Programming source
Probably not a substantial claim. The paper’s conclusions may not depend on it.
Findingnone givenThe generating extension produced for regexp:r1 was re-used without modification for regexp:r2 and regexp:r2.
“the generating extension produced for regexp:r1 w as re-used without modi cation for regexp:r2 a n d regexp:r2”
Quote in the paperNot a substantial claimProbably not a substantial claim. The paper’s conclusions may not depend on it.
Findingnone givenThe generating extension produced for map:rev was re-used for map:reduce.
“the one produced for map:rev was re-used for map:reduce.”
Quote in the paperNot a substantial claimIt may state two separate claims as one.
Findingown dataThe benchmark results show the efficiency of the cogen, the generating extensions and the specialised programs.
“extensive b e n c hmark results showing the e ciency of the cogen , the generating extensions but also of the specialised programs.”
Quote in the paperSubstantial claimProbably not a substantial claim. The paper may give no reason why it holds.
InterpretationreasoningThis leads to extremely efficient compilers and compiler generators.
“this leads to extremely e cient compilers and compiler generators.”
Quote in the paperNot a substantial claimProbably not a substantial claim.
InterpretationreasoningThe more features one uses in writing the specialiser, the more complex the specialisation process becomes, because the specialiser then has to handle these features as well.
“the more features one uses in writing the specialiser the more complex the specialisation process becomes, because the specialiser then has to handle these features as well.”
Quote in the paperSubstantial claimIt may state two separate claims as one.
InterpretationcitationCompared with [5], points 3, 4, 5 and the partially static structures of point 1 are new.
“Compared with 5], the points 3, 4, 5 as well as the partially static structures of point 1 are new”
Quote in the paperSubstantial claim0 of 1 sources checked- cites [5] Jørgensen, 1996, Efficiently generating efficient generating extensions in Prolog source
Probably not a substantial claim. The paper’s conclusions may not depend on it.
PremisecitationThe first cogen for logic programming languages was developed in [5].
“The rst cogen for logic programming languages was developed in 5].”
Quote in the paperNot a substantial claim0 of 1 sources checked- cites [5] Jørgensen, 1996, Efficiently generating efficient generating extensions in Prolog source
Probably not a substantial claim.
Premisenone givenIn earlier work, the authors showed that the cogen approach is applicable to partial evaluation of logic programming languages (partial deduction).
“In earlier work we h a ve shown that this approach is also applicable to partial evaluation of logic programming languages, also called partial deduction.”
Quote in the paperSubstantial claimIt may state two separate claims as one.
InterpretationreasoningNo restrictions due to self-application have to be imposed (the compiler and the compiler generator do not have to be self-applied).
“no restrictions due to self-application have to be imposed (the compiler and the compiler generator do not have to be self-applied)!”
Quote in the paperSubstantial claimIt may state two separate claims as one.
InterpretationreasoningThe new features lead to a much more powerful, practical and viable cogen.
“leading to a much more powerful, practical and viable cogen .”
Quote in the paperNot a substantial claim- Rests on an assumption: The selected benchmarks from [6] are representative of realistic logic programming applications.
- Rests on an assumption: The time needed for automatic binding-type analysis will not eliminate logen's efficiency advantage.
Probably not a substantial claim. It may be too vague to check against evidence.
InterpretationreasoningWriting an effectively self-applicable specialiser is a non-trivial task.
“However writing an eectively self-applicable specialiser is a non-trivial task”
Quote in the paperNot a substantial claimProbably not a substantial claim.
PremisecitationTo pass the KMP-test, more sophisticated local control would be required.
“(To b e a b l e t o pass the KMP-test, more sophisticated local control would be required, see 9].)”
Quote in the paperSubstantial claim0 of 1 sources checked- cites [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. source
Probably not a substantial claim.
Study design and conductnone givenThe binding-type analysis was carried out by hand.
“the binding-type analysis was carried out by hand.”
Quote in the paperSubstantial claimProbably not a substantial claim. The authors may not put it forward as true. The paper may give no reason why it holds.
Interpretationnone givenThe cogen handles negation, disjunction and the if-then-else conditional.
“how to handle negation, disjunction and the if-then-else conditional in the cogen .”
Quote in the paperNot a substantial claimIt may state two separate claims as one.
Interpretationown dataThe LOGEN system is surprisingly fast and produces surprisingly good specialised programs.
“Nonetheless, the logen system is surprisingly fast and produces surprisingly good specialised programs.”
Quote in the paperSubstantial claimProbably not a substantial claim. The paper’s conclusions may not depend on it.
InterpretationreasoningIn a fully automatic system, the cogen runtimes will have to be increased by the time needed for the binding-type analysis.
“In a fully automatic system thus, the column with the cogen runtimes will have to be increased by the time needed for the binding-type analysis.”
Quote in the paperNot a substantial claim
The paper relies on this without support.
The selected benchmarks from [6] are representative of realistic logic programming applications.
“We t h us ran our system on a selection of benchmarks from 6].”
The paper relies on this without support.
The time needed for automatic binding-type analysis will not eliminate logen's efficiency advantage.
“In a fully automatic system thus, the column with the cogen runtimes will have to be increased by the time needed for the binding-type analysis.”
The paper relies on this without support.
Partially instantiated data structures appear naturally in logic programs even at runtime.
“where partially instantiated datastructures appear naturally even at runtime”
The paper relies on this without support.
Both ecce and mixtus are fully automatic systems guaranteeing termination.
“both ecce and mixtus are fully automatic systems guaranteeing termination”
Citations
Cites
Sterling, L., Shapiro, E., & Garrett, R. (1987) · IEEE Expert · doi:10.1109/mex.1987.4307074 · Cited by 1,101
Conjunctive partial deduction: foundations, control, algorithms, and experiments
De Schreye, D., Glück, R., Jørgensen, J., Leuschel, M., Martens, B., & Sørensen, M. H. (1999) · The Journal of Logic Programming · doi:10.1016/s0743-1066(99)00030-8 · Cited by 96
Self-citationControlling generalization and polyvariance in partial deduction of normal logic programs
Leuschel, M., Martens, B., & De Schreye, D. (1998) · ACM Transactions on Programming Languages and Systems · doi:10.1145/271510.271525 · Cited by 88
Self-citationMixtus: An automatic partial evaluator for full Prolog
Sahlin, D. (1993) · New Generation Computing · doi:10.1007/bf03038271 · Cited by 76
Efficiently generating efficient generating extensions in prolog
Jørgensen, J., & Leuschel, M. (1996) · Lecture Notes in Computer Science · doi:10.1007/3-540-61580-6_12 · Cited by 26
Self-citationA polyvariant binding-time analysis for off-line partial deduction
Bruynooghe, M., Leuschel, M., & Sagonas, K. (1998) · Lecture notes in computer science · doi:10.1007/bfb0053561 · Cited by 23
Self-citationLogic programming : proceedings of the 1990 North American conference
Debray, S., & Hermenegildo, M. V. (1990) · Medical Entomology and Zoology · Cited by 19
Martin, J., & Leuschel, M. (2000) · Lecture Notes in Computer Science · doi:10.1007/3-540-46562-6_9 · Cited by 12
Self-citationLogic Programming Proceedings of the North American Conference, 1989
Lusk, E. L., & Overbeek, R. (1989) · Medical Entomology and Zoology · Cited by 8
Schreye, D. D., Glück, R., Jørgensen, J., et al. (2000) · The Journal of Logic Programming · doi:10.1016/s0743-1066(99)00070-9 · Cited by 2
Self-citationEfficient Specialisation in Prolog Using a Hand-Written Compiler Generator
Leuschel, M., Jørgensen, J., & Leuschel, M. (1999) · ePrints Soton (University of Southampton) · Cited by 1
Self-citation
Flagged first, then by citations
Cited by
Sorted by citations
Logic program specialisation through partial deduction: Control issues
Leuschel, M., & Bruynooghe, M. (2002) · Theory and Practice of Logic Programming · doi:10.1017/s147106840200145x · Cited by 77
Self-citationAbstract Interpretation of PIC Programs through Logic Programming
Henriksen, K. S., & Gallagher, J. P. (2006) · IEEE International Workshop on Source Code Analysis and Manipulation (SCAM) · doi:10.1109/scam.2006.1 · Cited by 46
“For the specialisation step we use an off-line partial evaluator for Prolog, called Logen [18].”
MethodAbstract Domains Based on Regular Types
Gallagher, J. P., & Henriksen, K. S. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-27775-0_3 · Cited by 23
“Types for Binding Time Analysis Binding time analysis (BTA) for offline partial evaluation in Logen [11] distinguishes between various kinds of term instantiations.”
MethodInfluentialAnalysis of Linear Hybrid Systems in CLP
Banda, G., & Gallagher, J. P. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-00515-2_5 · Cited by 22
“In step PE−→ the partial evaluator Logen [29] is applied in order to unfold the definitions of all the predicates except the state predicate rstate (or variations such as qstate or dqstate).”
MethodInfluentialIs there a fourth Futamura projection?
Glück, R. (2009) · ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation (PEPM) · doi:10.1145/1480945.1480954 · Cited by 12
“Based on this experience, the modern approach to the specialization of programs is to write compiler generators directly instead of writing self-applicable specializers (e.g., [2, 3, 6, 9, 21, 27, 36 , 41, 44, 45]).”
BackgroundFrom Big-Step to Small-Step Semantics and Back with Interpreter Specialisation
Gallagher, J. P., Hermenegildo, M. V., Kafle, B., et al. (2020) · Electronic Proceedings in Theoretical Computer Science · doi:10.4204/eptcs.320.4 · Cited by 7
“The specialised interpreter produced by Logen contains predicates of the form solve__n(...) .”
InfluentialAnalysis and specialisation of a PIC processor
Henriksen, K. S., & Gallagher, J. P. (2005) · Conference proceedings/Conference proceedings - IEEE International Conference on Systems, Man, and Cybernetics · doi:10.1109/icsmc.2004.1399774 · Cited by 6
Automatic verification of counter systems via domain-specific multi-result supercompilation
Klimov, A. V., Klyuchnikov, I. G., & Romanenko, S. A. (2012) · Cited by 5
A Logic Programming Based Approach to Applying Abstract Interpretation to Embedded Software
Henriksen, K. S. (2007) · RUCforsk (Roskilde University) · Cited by 3
Modelling and Analysis of Real Time Systems with Logic Programming and Constraints
Banda, G. (2010) · University of Southern Denmark Research Portal (University of Southern Denmark) · Cited by 2
Bootstrapping Compiler Generators from Partial Evaluators
Glück, R. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-29709-0_13 · Cited by 1
Metadata
- Authors
- Leuschel, M., & Jørgensen, J.
- Venue
- Electronic Notes in Theoretical Computer Science
- Publisher
- Elsevier BV
- Published
- 2000
- Volume
- 30
- Issue
- 2
- Pages
- 157-162
- ISSN
- 1571-0661 (ISSN-L)
- OpenAlex
- W2042965083
- Semantic Scholar
- 332a1719d201a2948d28147e56012d70dd7a11dc
- Cited by
- 11
- References
- 10
- Citations by year
- 2020: 1 · 2012: 2
- FWCI
- 0.41
- Type
- journal article
- Language
- en
- Open access
- diamond
- doi.org
- Licence
- Locations
- Electronic Notes in Theoretical Computer Science (publishedVersion, cc-by-nc-nd)
- ePrints Soton (University of Southampton) (submittedVersion)
- Topics
- Physical Sciences › Computer Science › Software › Logic, programming, and type systems
- Physical Sciences › Computer Science › Information Systems › Advanced Database Systems and Queries
- Physical Sciences › Computer Science › Hardware and Architecture › Parallel Computing and Optimization Techniques
- Keywords
- program specialization, partial evaluation, partial deduction, logic programming, Prolog, compiler generators
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
A language model drew the claims from the paper on 2026-10-19, under version 3 of the claim definition (model deepseek-v4.1-flash, prompt extract-v3).
A second model labelled each claim on 2026-10-19 (model jev-1.13-20260917, definition revision gold-guideline-v0.2).
Cited sources are checked with a language model’s help (gpt-6-sol).
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
