Abstract
Functional logic languages are declarative programming languages that integrate the programming paradigms of functional and logic languages within a single framework. They are extensions of functional languages with principles derived from logic programmingNarrowing, the evaluation mechanism of functional logic languages, can be defined as a generalization ofreduction, the evaluation mechanism of purely functional languages. The unidirectional pattern matching, which is used for parameter passing in functional languages, is simply replaced by the bidirectionalunification known from logic programming languages.
We show in this paper, how to extend a reduction machine, that has been designed for the evaluation of purely functional programs to a machine that performs narrowing. The necessary extensions concern the realization of unification and backtracking, for which we fall back upon the methods of Warren’s Prolog engine.21) The narrowing machine embodies an optimized treatment of deterministic computations. A complete specification of the reduction and the narrowing machine and of the translation of a sample language into abstract machine code is given. Comparative results of a C-implementation of the reduction and the narrowing machine show that the time overhead of the more complex narrowing evaluation is, in general, less than 10% of the reduction evaluation.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Balboni, G. P., Bosco, P. G., Cecchi, C., Melen, R., Moiso, C., and Sofi, G., “Implementation of a Parallel Logic Plus Functional Language”, inParallel Computers: Object Oriented, Functional and Logic (P. Treleaven, ed.), Wiley, 1989.
Bellia, M. and Levi, G., “The Relation between Logic and Functional Languages,”Journal of Logic Programming, 3, 1986.
Bosco, P. G., Cecchi, C., and Moiso, C., “An Extension of WAM for K_LEAF: A WAM-Based Compilation of Conditional Narrowing”,Conference on Logic Programming 1989, MIT Press, 1989.
Chakravarty, M. M. T. and Lock, H. C. R., “The Implementation of Lazy Implementation”,Symposium on Programming Language Implementation and Logic Programming 1991, LNCS 528, Springer Verlag, 1991.
DeGroot, D and Lindstrom, G. (eds.),Logic Programming: Functions, Relations, Equations, Prentice Hall, 1986.
Field, A. J. and Harrison, P. G.,Functional Programming, Addison Wesley, 1988.
Giovannetti, E., Levi, G., Moiso, C., and Palamidessi, C., “Kernel LEAF: A Logic plus Functional Language”,Journal of Computer and System Sciences, 42, 2, Academic Press, 1991.
Hanus, M., “Compiling Logic Programs with Equality”,Workshop on Programming Language Implementation and Logic Programming 1990, LNCS 456, Springer Verlag, 1990.
Hanus, M., “Efficient Implementation of Narrowing and Rewriting,”International Workshop on Processing Declarative Knowledge, LNCS 567, Springer Verlag, 1991.
Kuchen, H., Loogen, R., Moreno-Navarro, J. J., and Rodríguez-Artalejo, M., “Graph-Based Implementation of a Functional Logic Language,”European Symposium on Programming 1990, LNCS 432, Springer Verlag, 1990.
Loogen, R., Kuchen, H., Indermark, K., and Damm, W., “Distributed Implementation of Programmed Graph Reduction,”Conference on Parallel Architectures and Languages Europe 1989, LNCS 365, Springer Verlag. 1989.
Loogen, R., “From Reduction Machines to Narrowing Machines”,Colloquium on Combining Paradigms of Software Development—CCPSD, TAPSOFT 1991, LNCS 494, Springer Verlag, 1991.
Loogen, R. and Winkler, St., “Dynamic Detection of Determinism in Functional Logic Languages”,Symposium on Programming Language Implementation and Logic Programming 1991, LNCS 528, Springer Verlag, 1991.
Moreno-Navarro, J. J. and Rodríguez-Artalejo, M., “BABEL: A Functional and Logic Programming Language Based on Constructor Discipline and Narrowing”,Conference on Algebraic and Logic Programming 1988, LNCS 343, Springer Verlag, 1989.
Moreno-Navarro, J. J. and Rodríguez-Artalejo, M., “Logic Programming with Functions and Predicates: The Language BABEL”,Journal of Logic Programming, vol. 12, North Holland 1992.
Moreno-Navarro, J. J., Kuchen, H., Loogen, R., and Rodríguez-Artalejo, M., “Lazy Narrowing in a Graph Machine,”Conference on Algebraic and Logic Programming 1990, LNCS 463, Springer Verlag, 1990.
Peyton-Jones, S. and Salkild, J., “The Spineless Tagless G-Machine”,Conference on Functional Programming Languages and Computer Architecture 1989, ACM Press, 1989.
Reddy, U. S., “Narrowing as the Operational Semantics of Functional Languages”,IEEE Symposium on Logic Programming, IEEE Computer Society Press, 1985.
Reddy, U. S., “Functional Logic Languages, Part I,”Workshop on Graph Reduction, LNCS 279, Springer Verlag, 1987.
Wadler, Ph., “Efficient Compilation of Pattern-Matching,” inThe Implementation of Functional Programming Languages (S. Peyton-Jones), Prentice Hall, 1987.
Warren D. H. D., “An Abstract Prolog Instruction Set”,Technical Note., 309, SRI International, Menlo Park, California, Oct. 1983.
Author information
Authors and Affiliations
Corresponding author
Additional information
This paper is a revised and extended version of Ref. 12). The author has been partially supported by a german-spanish cooperation, funded by the german D. A. A. D and the spanish M. E. C.
Rita Loogen. Dr. rer. nat.: Her current research interests are in the field of declarative programming languages and their implementation on parallel architectures. She is interested in the design of new declarative languages which integrate the well-known paradigms of functional and logic languages in a uniform framework. Furthermore, she takes particular interest in the analysis and implementation of such languages, especially with respect to the exploitation of parallelism and the programming of parallel systems.
About this article
Cite this article
Loogen, R. Relating the implementation techniques of functional and functional logic languages. New Gener Comput 11, 179–215 (1993). https://doi.org/10.1007/BF03037158
Received:
Revised:
Issue date:
DOI: https://doi.org/10.1007/BF03037158
