Abstract
Program schemas are known to be useful in different applications such as program synthesis, transformation, analysis, debugging, teaching . . . This paper tackles two complementary aspects of program schemas. We first propose a language for the description of program schemas. It is based on a subset of second-order logic, enhanced with constraints and specific features of program schemas. One of the basic operations on schemas is the semi-unification of a schema with a program. We then express the semi-unification process over schemas as rewriting and reduction rules, using CLP techniques, where constraints are used to guide the semi-unification process.
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
H. Büyükyıldız and P. Flener, Generalized logic program transformation schemas, In: N.E. Fuchs (ed.), Proc. of LOPSTR’97 (this volume)
Y. Deville and K.-K. Lau, Logic program synthesis: A survey, Journal of Logic Programming, 19–20:321–350, May/July 1994
P. Flener, Logic Program Synthesis From Incomplete Information, Kluwer Academic Publishers, 1995
P. Flener and Y. Deville, Logic program transformation through generalization schemata, In: M. Proietti (ed.), Proc. of LOPSTR’95, Springer-Verlag, 1996
P. Flener, K.-K. Lau and M. Ornaghi, On Correct Program Schemas, In: N.E. Fuchs (ed.), Proc. of LOPSTR’97 (this volume)
N.E. Fuchs and M.P.J. Fromherz, Schema-Based Transformations of Logic Programs, In: T.P. Clement, K.-K. Lau (eds.), Proc. of LOPSTR’91, Springer-Verlag, 1992
M.R. Garey and D.S. Johnson, Computers and Intractability. A Guide to the Theory of NP-completeness, W.H. Freeman and Company, 1979
T.S. Gegg-Harrison, Learning Prolog in a Schema-Based Environment, Instructional Science, 20:173–192, 1991
T.S. Gegg-Harrison, Representing Logic Program Schemata in γ Prolog, In: L. Sterling (ed.), Proc. of the 12th International Conference on Logic Programming, Japan, pp. 467–481, The MIT Press, 1995
T.S. Gegg-Harrison, Extensible Logic Program Schemata, In: J. Gallagher (ed.), Proc. of the 6th International Workshop on Logic Program Synthesis and Transformation, Stockholm, Sweden, pp. 256–274, Springer-Verlag, 1996
W.D. Goldfarb, The Undecidability of the second-order unification problem, Theoretical Computer Science, 13:225–230, 1981
J. Hannan and D. Miller, Uses Of Higher-Order Unification For Implementing Program Transformers, In: A. Kowalski, K.A. Bowen (eds.), Proc. of ICLP’88, The MIT Press, 1988
G. Huet, A unification algorithm for lambda calculus, Theoretical Computer Science, 1:27–57, 1975
G. Huet, Résolution d’Équations dans les langages d’ordre 1, 2...ω, PhD thesis, Université Paris VII, 1976
G. Huet and B. Lang, Proving and Applying Program Transformations Expressed with Second-Order Patterns, Acta Informatica 11 (1978), 31–55
I. Kraan, D. Basin and A. Bundy, Middle-Out Reasoning for Logic Program Synthesis, In: D.S. Warren (ed.), Proc. of ICLP’93, The MIT Press, 1993
D. Miller and G. Nadathur, A logic programming approach to manipulating formulas and programs, Proc. of the IEEE Fourth Symposium on Logic Programming, IEEE Press, 1987
A. Martelli and U. Montanari, An Efficient Unification Algorithm, ACM Transactions on Programming Languages and Systems, Vol. 4, No. 2, April 1982, pp.258–282
T. Nipkow, Higher-order critical pairs, In: Proc. 6th IEEE Symp. Logic in Computer Science, pp. 342–349, 1991
J. Richardson and N.E. Fuchs, Development of correct transformation schemata for Prolog programs, In: N.E. Fuchs (e.), Proc. of LOPSTR’97 (this volume).
Z. Somogyi, F. Henderson and T. Conway, The execution algorithm of Mercury:. an efficient purely declarative logic programming language, Journal of Logic Programming, 29(1–3):17–64, October–December 1996
W.W. Vasconcelos and N.E. Fuchs, Enhanced Schema-Based Transformations for. Logic Programs and their Opportunistic Usage in Program Analysis and Optimisation, technical report, Institut für Informatik, Universität Zürich, 1995
W.W. Vasconcelos and N.E. Fuchs, An Opportunistic Approach for Logic Program. Analysis and Optimisation Using Enhanced Schema-Based Transformations, In: M. Proietti (ed.), Proc. of LOPSTR’95, Springer-Verlag, 1996
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chasseur, E., Deville, Y. (1998). Logic Program Schemas, Constraints, and Semi-unification. In: Fuchs, N.E. (eds) Logic Program Synthesis and Transformation. LOPSTR 1997. Lecture Notes in Computer Science, vol 1463. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-49674-2_4
Download citation
DOI: https://doi.org/10.1007/3-540-49674-2_4
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65074-4
Online ISBN: 978-3-540-49674-8
eBook Packages: Springer Book Archive