×

zbMATH — the first resource for mathematics

Singular and plural functions for functional logic programming. (English) Zbl 1286.68057
Summary: Modern functional logic programming (FLP) languages use non-terminating and non-confluent constructor systems (CSs) as programs in order to define non-strict and non-deterministic 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 basic 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 in this paper we propose two novel compositional plural semantics for CSs that are different from run-time choice.
We investigate the basic properties of our plural semantics – compositionality, polarity, and monotonicity for substitutions, and a restricted form of the bubbling property for CSs – 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 values computed by them.
Besides, we have identified a class of programs characterized by a simple syntactic criterion for which the proposed plural semantics behave the same, and a program transformation that can be used to simulate one of the proposed plural semantics by term rewriting. At the practical level, we study how to use the new expressive capabilities of these semantics for improving the declarative flavor of programs. As call-time choice is the standard semantics for FLP, it still remains the best option for many common programming patterns. Therefore, we propose a language that combines call-time choice and our plural semantics, which we have implemented in the Maude system. The resulting interpreter is then employed to develop and test several significant examples showing the capabilities of the combined semantics.

MSC:
68N17 Logic programming
68N18 Functional programming and lambda calculus
68Q55 Semantics in the theory of computing
68Q42 Grammars and rewriting systems
Software:
Maude; TOY
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Journal of Functional and Logic Programming 1998 1 pp 1– (1998)
[2] All About Maude: A High-Performance Logical Framework (2007)
[3] Proceedings of the Rewriting Techniques and Applications, RTA 1999 pp 244– (1999)
[4] Kirchner, Proceedings of the Second International Workshop on Rewriting Logic and Its Applications, WRLA’98, Pont-à-Mousson, France, September 1–4 pp 329– (1998)
[5] Term Rewriting and All That (1998) · Zbl 0948.68098 · doi:10.1017/CBO9781139172752
[6] Proceedings of the 2009 ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation, PEPM 2009 pp 91– (2009)
[7] Proceedings of 22nd Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, POPL 1995 pp 233– (1995)
[8] DOI: 10.1016/S1571-0661(04)80347-5 · Zbl 1268.68058 · doi:10.1016/S1571-0661(04)80347-5
[9] Proceedings of the 20th International Conference on Rewriting Techniques and Applications, RTA 2009 pp 320– (2009)
[10] Communications of ACM 53 pp 74– (2010)
[11] Proceedings of the 9th International Symposium on Functional and Logic Programming, FLOPS 2008 pp 147– (2008)
[12] Hu, FLOPS pp 67– (2002)
[13] Proceedings of the Principles and Practice of Declarative Programming pp 197– (2007)
[14] Electronic Notes in Theoretical Computer Science – ENTCS 176 pp 61– (2007)
[15] DOI: 10.1016/j.jsc.2004.01.001 · Zbl 1129.68042 · doi:10.1016/j.jsc.2004.01.001
[16] Proceedings of the ACM Symposium on Principles of Programming Languages, POPL 1993 pp 144– (1993)
[17] Non-Determinism in Algebraic Specifications and Algebraic Programs (1993)
[18] Proceedings of the 1989 Glasgow Workshop on Functional Programming pp 308– (1990)
[19] DOI: 10.1017/S1471068411000457 · Zbl 1244.68019 · doi:10.1017/S1471068411000457
[20] Hayes, Machine Intelligence 10 pp 441– (1982)
[21] Proceedings of the International Conference on Logic Programming, ICLP 2007 pp 45– (2007)
[22] Proceedings of the 16th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages pp 60– (1989)
[23] Proceedings of the Functional Programming and Computer Architecture pp 113– (1985)
[24] Functional Logic Programming: From Theory to Curry (2005)
[25] The Mercury Language Reference Manual, Version 11.07.1 (2012)
[26] Proceedings of the International Conference on Logic Programming, ICLP 1997 pp 153– (1997)
[27] Term Rewriting Systems (2003) · Zbl 1030.68053
[28] DOI: 10.1016/S0743-1066(98)10029-8 · Zbl 0942.68060 · doi:10.1016/S0743-1066(98)10029-8
[29] The Art of Prolog (1986) · Zbl 0605.68002
[30] Proceedings of the European Symposium on Programming, ESOP 1996 pp 156– (1996)
[31] The Computer Journal 35 5 pp 514– (1992) · doi:10.1093/comjnl/35.5.514
[32] CafeOBJ Report (1998)
[33] Acta Informatica 27 6 pp 505– (1990)
[34] Proceedings of the 2010 ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation, PEPM 2010 pp 83– (2010)
[35] Journal of Functional and Logic Programming 2003 pp 23– (2003)
[36] Ekman, Proceedings of the 9th Workshop on Language Descriptions, Tools, and Applications, LDTA 2009 pp 165– (2010)
[37] Shao, APLAS pp 122– (2007)
[38] Handbook of Graph Grammars and Computing by Graph Transformation, vol. 2: Applications, Languages, and Tools pp 3– (1999) · Zbl 0951.68049
[39] Kuchen, Proceedings of the 20th International Conference on Functional and Constraint Logic Programming, WFLP 2011 pp 1– (2011) · Zbl 1218.68021
[40] Functional Programming and Parallel Graph Rewriting (1993) · Zbl 0788.68023
[41] Mariño, WFLP pp 30– (2010)
[42] Braffort, Computer Programming and Formal Systems pp 33– (1963) · Zbl 0108.13402
[43] Concepts, Techniques, and Models of Computer Programming (2004)
[44] DOI: 10.1145/1596550.1596556 · Zbl 1302.68058 · doi:10.1145/1596550.1596556
[45] Kameyama, Proceedings of the 7th International Symposium on Functional and Logic Programming, FLOPS 2004 pp 147– (2004) · Zbl 1048.68005
[46] DOI: 10.1016/j.entcs.2008.03.080 · doi:10.1016/j.entcs.2008.03.080
[47] Proceedings of the 1998 Joint International Conference and Symposium on Logic Programming pp 325– (1998)
[48] A Discipline of Programming (1997)
[49] Logic Programming, Functions, Relations, and Equations (1986)
[50] Hanus, ALP/HOA pp 129– (1997)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.