Singular and plural functions for functional logic programming
From MaRDI portal
Abstract: Functional logic programming (FLP) languages use non-terminating and non-confluent constructor systems (CS's) as programs in order to define non-strict non-determi-nistic functions. Two semantic alternatives have been usually considered for parameter passing with this kind of functions: call-time choice and run-time choice. While the former is the standard choice of modern FLP languages, the latter lacks some properties---mainly compositionality---that have prevented its use in practical FLP systems. Traditionally it has been considered that call-time choice induces a singular denotational semantics, while run-time choice induces a plural semantics. We have discovered that this latter identification is wrong when pattern matching is involved, and thus we propose two novel compositional plural semantics for CS's that are different from run-time choice. We study the basic properties of our plural semantics---compositionality, polarity, monotonicity for substitutions, and a restricted form of the bubbling property for constructor systems---and the relation between them and to previous proposals, concluding that these semantics form a hierarchy in the sense of set inclusion of the set of computed values. We have also identified a class of programs characterized by a syntactic criterion for which the proposed plural semantics behave the same, and a program transformation that can be used to simulate one of them by term rewriting. At the practical level, we study how to use the expressive capabilities of these semantics for improving the declarative flavour of programs. We also propose a language which combines call-time choice and our plural semantics, that we have implemented in Maude. The resulting interpreter is employed to test several significant examples showing the capabilities of the combined semantics. To appear in Theory and Practice of Logic Programming (TPLP)
Recommendations
- FPL : Functional plus logic programming an integration of the FP and Prolog languages
- Equivalence of two formal semantics for functional logic programs
- Singular and Plural Nondeterministic Parameters
- A hierarchy of semantics for non-deterministic term rewriting systems
- scientific article; zbMATH DE number 4043306
Cites work
- An approach to declarative programming based on a rewriting logic
- An overview of Ciao and its design philosophy
- Computer programming and formal systems
- Functional and constraint logic programming. 20th international workshop, WFLP 2011, Odense, Denmark, July 19th. Proceedings
- Functional and logic programming. 7th international symposium, FLOPS 2004, Nara, Japan, April 7--9, 2004. Proceedings.
- scientific article; zbMATH DE number 3978351 (Why is no real title available?)
- scientific article; zbMATH DE number 108369 (Why is no real title available?)
- scientific article; zbMATH DE number 1889386 (Why is no real title available?)
- scientific article; zbMATH DE number 1437942 (Why is no real title available?)
- Improving the efficiency of non-deterministic computations
- Operational semantics for declarative multi-paradigm languages
- Purely functional lazy non-deterministic programming
- Term Rewriting and All That
Cited in
(5)- A hierarchy of semantics for non-deterministic term rewriting systems
- Singular and Plural Nondeterministic Parameters
- FUNCTIONAL PEARL Concurrent distinct choices
- Fraktal and Differential Properties of the Inversor of Digits of Q s-Representation of Real Number
- Rewriting and Call-Time Choice: The HO Case
This page was built for publication: Singular and plural functions for functional logic programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5410261)
