Multi-pass execution of functional logic programs
Pages 361 - 374
Abstract
An operational semantics for functional logic programs is presented. In such programs functional terms provide for reduction of expressions, provided that they ground. The semantics is based on multi-pass evaluation techniques originally developed for attribute grammars. Program execution is divided into two phases: (1) construction of an incomplete proof tree, and (2) its decoration into a complete proof tree. The construction phase applies a modified SLD-resolution scheme, and the decoration phase a partial (multi-pass) traversal over the tree. The phase partition is generated by static analysis where data dependencies are extracted for the functional elements of the program. The method guarantees that all the functional terms of a program can be evaluated, and no dynamic groundness checks are needed.
References
[1]
Alblas H.: Attribute Evaluation Methods. in: Proc. Int. Summer School on Attribute Grammars, Applications and Systems, Prague, 1991. LNCS 545, Springer-Verlag, 1991, 48-113.
[2]
A{t-Kaci H., Lincoln P., Nasr R.: Le Fun: Logic, Equations and Functions. In: Proc. 1987 Symposium on Logic Programming, San Francisco. IEEE Computer Society Press, 1987, 17-23.
[3]
Apt K.R., Pellegrini A.: Why the Occur-check is Not a Problem. In: Proc.,~th Int. Symposium on Programming Language Implementation and Logic Programming, Leuven, 1992. LNCS 631, Springer-Verlag, 1992, 69-86.
[4]
Attali I., Chazarain J.: Functional Evaluation of Strongly Non Circular TYPOL Specifications. In: Proc. Int. Conference on Attribute Grammars and Their Applications, Paris, 1990. LNCS 461, Springer-Verlag, 1990, 157-176.
[5]
Attali I., Franchi-Zannettacci P.: Unification- Free Execution of TYPOL Programs by Semantic Attribute Evaluation. In: Proc. 5th Int. Con- ~erence and Symposium on Logic Programming, Washington, Seattle (Kowalski R.A., Bowen K.A., eds.). The MIT Press, 1988, 160-177.
[6]
Bochmann G.V.: Semantic Evaluation from Left to Right. CA CM 19, 2, 1976, 55-62.
[7]
Bouquard J.-L.: t~tude des Rapports Entre Grammaires Attribu6es et Programmation Logique: Application au Test d'Occurence et l'Analyse Statique. PhD Thesis, University of Tours, 1992.
[8]
Boye J.: S-SLD-resolution - An Operational Semantics for Logic Programs with External Procedures. In: Proc. 3rd Int. Symposium on Programming Language Implementation and Logic Programming, Passau, 1991. LNCS 528, Springer- Verlag, 1991, 383-393.
[9]
Boye J.: Avoiding Dynamic Delays in Functional Logic Programs. In: Proc. 5th Int. Symposium on Programming Language Implementation and Logic Programming, Tallinn, 1993. LNCS 714, Springer-Verlag, 1993, 12-27.
[10]
Boye J., Paakki J., Ma~uszyfiski J.: Dependency- Based Groundness Analysis of Functional Logic Programs. Research Report LiTH-IDA-R-93-20, Department of Computer and Information Science, Linkfping University, 1993.
[11]
Boye J., Paakki J., Ma~uszyrlski J.: Synthesis of Directionality Information for Functional Logic Programs. In: Proc. 3rd Int. Workshop on Static Analysis, Padova, 1993. LNCS 724, Springer- Verlag, 1993, 165-177.
[12]
Deransart P., Matuszyfiski J.: Relating Logic Programs and Attribute Grammars. Journal o/ Logic Programming 2, 1985, 119-156.
[13]
Deransart P., Matuszyfiski J.: A Grammatical View on Logic Programming. The MIT Press, 1993 (To appear).
[14]
Deransart P., Ferrand G., T~guia M.: NSTO Programs (Not Subject To Occur-check). In: Proc. Int. Symposium on Logic Programming (Saraswat V., Ueda K., eds.), San Diego, 1991. The MIT Press, 1991, 533-547.
[15]
Deransart P., Jourdan M., Lorho B.: Attribute Grammars - Definitions, Systems and Bibliography. LNCS 323, Springer-Verlag, 1988.
[16]
Drabent W.: Do Logic Programs Resemble Programs in Conventional Languages? In: Proc. 1987 Symposium on Logic Programming, San Francisco. IEEE Computer Society Press, 1987, 389-396.
[17]
Earley J.: Art Efficient Context-Free Parsing Algorithm. CACM 13, 2, 1970, 94-102.
[18]
Fribourg L.: SLOG: A Logic Programming Interpreter Based on Clausal Superposition and Rewriting. In. Proc. 1985 Symposium on Logic Programming, Boston. IEEE Computer Society Press, 1985, 172-184.
[19]
GrSnholm C.: Metainterpretation in Logic Programming. MSc Thesis (in Finnish), Department of Computer Science, University of Helsinld, 1993 (To appear).
[20]
Hanus M.: On the Completeness of Residuation. In: Proc. Joint Int. Conference and Symposium on Logic Programming (Apt K., ed.), Washington, 1992. The MIT Press, 1992, 192-206.
[21]
Jazayeri M., Odgen W.F., Rounds W.C.: The Intrinsically Exponential Complexity of the Circularity Problem for Attribute Grammars. CA CM 18, 1975, 679-706.
[22]
Kennedy K., Warren S.K.: Automatic Generation of Efficient Evatuators for Attribute Grammars. in: Conf. Record of the 3rd A CM Symposium on Principles of Programming Languages, Atlanta, 1976, 32-49.
[23]
Knuth D.: Semantics of Context-Free Languages. Mathematical Systems Theory 2, 1968, 127-145.
[24]
Lloyd J.W.: Logic Programming, 2nd ed. Springer-VeEag, 1987.
[25]
Lewis P.M., Rosenkrantz D.J., Stearns R.E.: Attributed Translations. Journal of Computer and System Sciences 9, 1974, 279-307.
[26]
Ma~uszyfiski J.: Attribute Grammars and Logic Programs: A Comparison of Concepts. In: Proc. Int. Summer School on Attribute Grammars, Applications and Systems, Prague, 1991. LNCS 545, Springer-Verlag, 1991, 330-357.
[27]
Maiuszy~sld J., Bonnier S., Boye J., Klu~niak F., Kggedal A., Nilsson U.: Logic Programs with External Procedures. In: Logic Programming Languages- Constraints, Functions, and Objects (Apt K.IZ., de Bakker J.W., Rutten J.j.M.M., eds.). The MIT Press, 1993, 21-48.
[28]
Moreno-Navarro J., Rodriquez-Artalejo M.: Logic Programming with Functions and Predicates: The Language BABEL. Journal of Logic Programming 12, 1992, 191-223.
[29]
Naish L.: Adding Equations to NU-Prolog. In: Proc. 3rd Int. Symposium on Programming Language Implementation and Logic Programming, Passau, 1991. LNCS 528, Springer-Verl~g, 1991, 15-26.
[30]
Paakld :l: PROFIT - A System Integrating Attribute Grammars and Logic Programming. In: Proc. 3rd Int. Symposium on Programming Language Implementation and Logic Programming, Passau, 1991. LNCS 528, Springe>Verlag, 1991, 243-254.
[31]
Paakki J.: Multi-Pass Evaluation of Functional Logic Programs. Research Report LiTH-IDA-R- 93-02, Department of Computer and Information Science, LinkSping University, 1993.
[32]
Paakki J., Gyim6thy T., Horv6.th T.: An Integrated Method for Algorithmic Debugging of Logic Programs. Submitted for publication, 1993.
[33]
Pliimer L.: Termination Proofs for Logic Programs. Lecture Notes in Artificial Intelligence 446, Springer-Verlag, 1990.
[34]
Reddy U.S.: Transformation of Logic Programs into Functional Programs. In: Proc. 198~ Symposium on I~ogic Programming. IEEE Computer Society Press, 1984, 187-197.
[35]
Reps T., Teitelbaum T.: The Synthesizer Generator. Springer-Verlag, 1989.
[36]
Sterling L., Shapiro E.: The Art of Prolog. The MIT Press, 1986.
Index Terms
- Multi-pass execution of functional logic programs
Recommendations
Proving Failure in Functional Logic Programs
CL '00: Proceedings of the First International Conference on Computational LogicHow to extract negative information from programs is an important issue in logic programming. Here we address the problem for functional logic programs, from a proof-theoretic perspective. The starting point of our work is CRWL (Constructor based ...
The completeness of functional logic
AbstractA new first-order logic, functional logic, was proposed recently by Staples, Robinson and Hazel. The logic provides a formal means of describing and reasoning about dependence on an implicit parameter, a prime motivation being the unification of ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
February 1994
492 pages
Copyright © 1994 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: 01 February 1994
Check for updates
Qualifiers
- Article
Conference
POPL94: 21st ACM SIGPLAN/SIGACT Symposium on Principles of Programming Languages
January 16 - 19, 1994
Oregon, Portland, USA
Acceptance Rates
POPL '94 Paper Acceptance Rate 39 of 173 submissions, 23%;
Overall Acceptance Rate 824 of 4,130 submissions, 20%
Upcoming Conference
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 242Total Downloads
- Downloads (Last 12 months)32
- Downloads (Last 6 weeks)8
Reflects downloads up to 14 Nov 2024
Other Metrics
Citations
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.
Sign in