Article

Self-tuning resource aware specialisation for prolog

Authors:

Stephen-John Craig,

Michael LeuschelAuthors Info & Claims

PPDP '05: Proceedings of the 7th ACM SIGPLAN international conference on Principles and practice of declarative programming

Pages 23 - 34

https://doi.org/10.1145/1069774.1069777

Published: 11 July 2005 Publication History

Abstract

The paper develops a self-tuning resource aware partial evaluation technique for Prolog programs, which derives its own control strategies tuned for the underlying computer architecture and Prolog compiler using a genetic algorithm approach. The algorithm is based on mutating the annotations of offline partial evaluation. Using a set of representative sample queries it decides upon the fitness of annotations, controlling the trade-off between code explosion, speedup gained and specialisation time. The user can specify the importance of each of these factors in determining the quality of the produced code, tailoring the specialisation to the particular problem at hand. We present experimental results for our implemented technique on a series of benchmarks. The results are compared against the aggressive termination based binding-time analysis and optimised using different measures for the quality of code. We also show that our technique avoids some classical pitfalls of partial evaluation.

References

[1]

E. Albert, S. Antoy, and G. Vidal. Measuring the Effectiveness of Partial Evaluation in Functional Logic Languages. In Proc. of 10th Int'l Workshop on Logic-based Program Synthesis and Transformation (LOPSTR'2000), pages 103--124. Springer LNCS 2042, 2001.]]

Digital Library

[2]

E. Albert and G. Vidal. Symbolic profiling for multi-paradigm declarative languages. In Logic-Based Program Synthesis and Transformation (Proc. of LOPSTR'01), pages 148--167. Springer LNCS 2372, 2002.]]

Digital Library

[3]

A. F. Bowers and C. A. Gurr. Towards fast and declarative meta-programming. In K. R. Apt and F. Turini, editors, Meta-logics and Logic Programming, pages 137--166. MIT Press, 1995.]]

Digital Library

[4]

B. Brassel, M. Hanus, F. Huch, J. Silva, and G. Vidal. Runtime Profiling of Functional Logic Programs. In Proc. of the 14th Int'l Symp. on Logic-based Program Synthesis and Transformation (LOPSTR'04), pages 178--189, 2004.]]

Digital Library

[5]

S.-J. Craig, M. Leuschel, J. Gallagher, and K. Henriksen. Fully automatic Binding Time Analysis for Prolog. In S. Etalle, editor, Logic Based Program Synthesis and Transformation, 14th International Workshop, pages 61--70, 2004.]]

Digital Library

[6]

A. Eiben and J. Smith. Introduction to Evolutionary Computing. Springer-Verlag, 2003.]]

[7]

J. Gallagher. A system for specialising logic programs. Technical Report TR-91-32, University of Bristol, November 1991.]]

[8]

J. Gallagher and M. Bruynooghe. The derivation of an algorithm for program specialisation. New Generation Computing, 9(3 & 4):305--333, 1991.]]

[9]

J. P. Gallagher. Tutorial on specialisation of logic programs. In Proceedings of the 1993 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, pages 88--98. ACM Press, 1993.]]

Digital Library

[10]

C. A. Gurr. A Self-Applicable Partial Evaluator for the Logic Programming Language Gödel. PhD thesis, Department of Computer Science, University of Bristol, January 1994.]]

[11]

C. A. Gurr. Specialising the ground representation in the logic programming language Gödel. In Y. Deville, editor, Logic Program Synthesis and Transformation. Proceedings of LOPSTR'93, Workshops in Computing, pages 124--140, Louvain-La-Neuve, Belgium, 1994. Springer-Verlag.]]

[12]

J. Jørgensen, M. Leuschel, and B. Martens. Conjunctive partial deduction in practice. In J. Gallagher, editor, Logic Program Synthesis and Transformation. Proceedings of LOPSTR'96, LNCS 1207, pages 59--82, Stockholm, Sweden, August 1996. Springer-Verlag.]]

Digital Library

[13]

M. Leuschel. The ecce partial deduction system and the dppd library of benchmarks. Obtainable via http://www.ecs.soton.ac.uk/~mal, 1996-2004.]]

[14]

M. Leuschel and M. Bruynooghe. Logic program specialisation through partial deduction: Control issues. Theory and Practice of Logic Programming, 2(4 & 5):461--515, July & September 2002.]]

Digital Library

[15]

M. Leuschel, J. Jørgensen, W. Vanhoof, and M. Bruynooghe. Offline specialisation in Prolog using a hand-written compiler generator. Theory and Practice of Logic Programming, 4(1):139--191, 2004.]]

Digital Library

[16]

M. Leuschel, B. Martens, and D. De Schreye. Controlling generalisation and polyvariance in partial deduction of normal logic programs. ACM Transactions on Programming Languages and Systems, 20(1):208--258, January 1998.]]

Digital Library

[17]

J. W. Lloyd. Foundations of Logic Programming. Springer-Verlag, 1987.]]

[18]

J. W. Lloyd and J. C. Shepherdson. Partial evaluation in logic programming. The Journal of Logic Programming, 11(3&4):217--242, 1991.]]

Digital Library

[19]

B. Martens and J. Gallagher. Ensuring global termination of partial deduction while allowing exible polyvariance. In L. Sterling, editor, Proceedings ICLP'95, pages 597--613. MIT Press, June 1995.]]

[20]

S. Prestwich. The PADDY partial deduction system. Technical Report ECRC-92-6, ECRC, Munich, Germany, 1992.]]

[21]

D. Sahlin. Mixtus: An automatic partial evaluator for full Prolog. New Generation Computing, 12(1):7--51, 1993.]]

Digital Library

[22]

M. Sperber, P. Thiemann, and H. Klaeren. Distributed partial evaluation. In Proceedings of the second international symposium on Parallel symbolic computation, pages 80--87. ACM Press, 1997.]]

Digital Library

[23]

R. Venken and B. Demoen. A partial evaluation system for Prolog: Theoretical and practical considerations. New Generation Computing, 6(2 & 3):279--290, 1988.]]

Digital Library

[24]

G. Vidal. Cost-Augmented Partial Evaluation of Functional Logic Programs. Higher-Order and Symbolic Computation, 17(1-2):7--46, 2004.]]

Digital Library

[25]

R. Whaley, A. Petitet, and J. Dongarra. Automated empirical optimizations of software and the atlas project. Parallel Computing, 27(1--2):3--35, 2001.]]

Cited By

Albert EArenas PGenaim SPuebla G(2015)A practical comparator of cost functions and its applicationsScience of Computer Programming10.1016/j.scico.2014.12.001111:P3(483-504)Online publication date: 1-Nov-2015
https://dl.acm.org/doi/10.1016/j.scico.2014.12.001
Albert EArenas PGenaim SPuebla G(2011)Closed-Form Upper Bounds in Static Cost AnalysisJournal of Automated Reasoning10.1007/s10817-010-9174-146:2(161-203)Online publication date: 1-Feb-2011
https://dl.acm.org/doi/10.1007/s10817-010-9174-1
Ochoa CPuebla G(2008)Oracle-Based Partial EvaluationElectronic Notes in Theoretical Computer Science (ENTCS)10.1016/j.entcs.2008.11.024220:3(145-161)Online publication date: 1-Dec-2008
https://dl.acm.org/doi/10.1016/j.entcs.2008.11.024
Show More Cited By

Index Terms

Self-tuning resource aware specialisation for prolog
1. Computing methodologies
  1. Artificial intelligence
    1. Knowledge representation and reasoning
      1. Logic programming and answer set programming
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Constraint and logic languages

Recommendations

Self-Tuning PI and PID Controllers
Design and Realization of Fuzzy Self-tuning PID Water Temperature Controller Based on PLC
IHMSC '12: Proceedings of the 2012 4th International Conference on Intelligent Human-Machine Systems and Cybernetics - Volume 02

Temperature Control System has the characteristics of nonlinear, strong delay and inertia, and it is difficult to build the accurate mathematical models of the system. Conventional PID controller can not achieve precise control because its control ...
Offline specialisation in Prolog using a hand-written compiler generator

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. This paper demonstrates that the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PPDP '05: Proceedings of the 7th ACM SIGPLAN international conference on Principles and practice of declarative programming

July 2005

260 pages

ISBN:1595930906

DOI:10.1145/1069774

General Chair:
Pedro Barahona
Universidade Nova de Lisboa, Portugal
,
Program Chair:
Amy Felty
University of Ottawa, Canada

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 July 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PPDP05

Sponsor:

PPDP05: Principles and Practice of Declarative Programming 2005

July 11 - 13, 2005

Lisbon, Portugal

Acceptance Rates

Overall Acceptance Rate 230 of 486 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
118
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Albert EArenas PGenaim SPuebla G(2015)A practical comparator of cost functions and its applicationsScience of Computer Programming10.1016/j.scico.2014.12.001111:P3(483-504)Online publication date: 1-Nov-2015
https://dl.acm.org/doi/10.1016/j.scico.2014.12.001
Albert EArenas PGenaim SPuebla G(2011)Closed-Form Upper Bounds in Static Cost AnalysisJournal of Automated Reasoning10.1007/s10817-010-9174-146:2(161-203)Online publication date: 1-Feb-2011
https://dl.acm.org/doi/10.1007/s10817-010-9174-1
Ochoa CPuebla G(2008)Oracle-Based Partial EvaluationElectronic Notes in Theoretical Computer Science (ENTCS)10.1016/j.entcs.2008.11.024220:3(145-161)Online publication date: 1-Dec-2008
https://dl.acm.org/doi/10.1016/j.entcs.2008.11.024
Ochoa CPuebla G(2007)A Study on the Practicality of Poly-Controlled Partial EvaluationElectronic Notes in Theoretical Computer Science (ENTCS)10.1016/j.entcs.2007.01.008177(137-151)Online publication date: 1-Jun-2007
https://dl.acm.org/doi/10.1016/j.entcs.2007.01.008
Navas JMera ELópez-García PHermenegildo M(2007)User-Definable Resource Bounds Analysis for Logic ProgramsLogic Programming10.1007/978-3-540-74610-2_24(348-363)Online publication date: 2007
https://doi.org/10.1007/978-3-540-74610-2_24

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents