×

zbMATH — the first resource for mathematics

Transforming Boolean equalities into constraints. (English) Zbl 1362.68034
Summary: Although functional as well as logic languages use equality to discriminate between logically different cases, the operational meaning of equality is different in such languages. Functional languages reduce equational expressions to their Boolean values, True or False, logic languages use unification to check the validity only and fail otherwise. Consequently, the language Curry, which amalgamates functional and logic programming features, offers two kinds of equational expressions so that the programmer has to distinguish between these uses. We show that this distinction can be avoided by providing an analysis and transformation method that automatically selects the appropriate operation. Without this distinction in source programs, the language design can be simplified and the execution of programs can be optimized. As a consequence, we show that one kind of equational expressions is sufficient and unification is nothing else than an optimization of Boolean equality.
MSC:
68N17 Logic programming
68N18 Functional programming and lambda calculus
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alpuente M, Comini M, Escobar S, Falaschi M, Lucas S (2002) Abstract diagnosis of functional programs. In: Proceedings of the 12th int’l workshop on logic-based program synthesis and transformation (LOPSTR 2002), LNCS 2664. Springer, Berlin, pp 1-16 · Zbl 1278.68056
[2] Antoy, S; Echahed, R; Hanus, M, A needed narrowing strategy, J ACM, 47, 776-822, (2000) · Zbl 1327.68141
[3] Antoy, S; Hanus, M, Functional logic programming, Commun ACM, 53, 74-85, (2010)
[4] Antoy S, Hanus M (2012) Contracts and specifications for functional logic programming. In: Proceedings of the 14th international symposium on practical aspects of declarative languages (PADL 2012), LNCS 7149. Springer, Berlin, pp 33-47
[5] Antoy S, Hanus M (2014) Curry without success. In: Proceedings of the 23rd international workshop on functional and (constraint) logic programming (WFLP 2014). CEUR workshop proceedings, vol 1335. CEUR-WS.org, pp 140-154
[6] Albert, E; Hanus, M; Huch, F; Oliver, J; Vidal, G, Operational semantics for declarative multi-paradigm languages, J Symb Comput, 40, 795-829, (2005) · Zbl 1129.68042
[7] Antoy S (2001) Constructor-based conditional narrowing. In: Proceedings of the 3rd international ACM SIGPLAN conference on principles and practice of declarative programming (PPDP 2001). ACM Press, New York, pp 199-206
[8] Antoy, S, Programming with narrowing, J Symbol Comput, 45, 501-522, (2010) · Zbl 1192.68135
[9] Arenas-Sánchez P, Gil-Luezas A, López-Fraguas FJ (1994) Combining lazy narrowing with disequality constraints. In: Proceedings of the 6th international symposium on programming language implementation and logic programming, LNCS 844. Springer, Berlin, pp 385-399
[10] Bert D, Echahed R (1995) Abstraction of conditional term rewriting systems. In: Proceedings of the 1995 international logic programming symposium. MIT Press, Massachusetts, pp 147-161 · Zbl 0877.68015
[11] Bert D, Echahed R, Østvold M (1993) Abstract rewriting. In: Proceedings of third international workshop on static analysis, LNCS 724. Springer, Berlin, pp 178-192
[12] Braßel B, Hanus M, Peemöller B, Reck F (2011) KiCS2: a new compiler from Curry to Haskell. In: Proceedings of the 20th international workshop on functional and (constraint) logic programming (WFLP 2011), LNCS 6816. Springer, Berlin, pp 1-18
[13] Braßel B, Hanus M, Peemöller B, Reck F (2013) Implementing equational constraints in a functional language. In: Proceedings of the 15th international symposium on practical aspects of declarative languages (PADL 2013), LNCS 7752. Springer, Berlin, pp 125-140
[14] Cousot P, Cousot R (1977) Abstract interpretation: a unified lattice model for static analysis of programs by construction of approximation of fixpoints. In: Proceedings of the 4th ACM symposium on principles of programming languages, pp 238-252
[15] Cousot P (1997) Types as abstract interpretations. In: Proceedings of the 24th ACM symposium on principles of programming languages (Paris), pp 316-331
[16] Damas L, Milner R (1982) Principal type-schemes for functional programs. In: Proceedings of the 9th annual symposium on principles of programming languages, pp 207-212
[17] Hanus M, Antoy S, Braßel B, Engelke M, Höppner K, Koj J, Niederau P, Sadre R, Steiner F (2016) PAKCS: the Portland Aachen Kiel Curry system. http://www.informatik.uni-kiel.de/ pakcs/
[18] Hanus M (1997) Teaching functional and logic programming with a single computation model. In: Proceedings of the ninth international symposium on programming languages, implementations, logics, and programs (PLILP’97), LNCS 1292. Springer, Berlin, pp 335-350
[19] Hanus M (2001) High-level server side web scripting in Curry. In: Proceedings of the third international symposium on practical aspects of declarative languages (PADL’01), LNCS 1990. Springer, Berlin, pp 76-92
[20] Hanus M (2007) Putting declarative programming into the web: translating Curry to JavaScript. In: Proceedings of the 9th ACM SIGPLAN international conference on principles and practice of declarative programming (PPDP’07). ACM Press, New York, pp 155-166 · Zbl 0296.68092
[21] Hanus M (2008) Call pattern analysis for functional logic programs. In: Proceedings of the 10th ACM SIGPLAN international conference on principles and practice of declarative programming (PPDP’08). ACM Press, New York, pp 67-78 · Zbl 1327.68141
[22] Hanus M (ed) (2012) Curry: an integrated functional logic language (vers. 0.8.3). http://www.curry-language.org
[23] Hanus M (2013) Functional logic programming: from theory to Curry. In: Programming logics—essays in memory of Harald Ganzinger, LNCS 7797. Springer, Berlin, pp 123-168 · Zbl 1383.68017
[24] Hanus M (ed) (2016) Curry: an integrated functional logic language (vers. 0.9.0). http://www.curry-language.org · Zbl 1129.68042
[25] Hanus M, Skrlac F (2014) A modular and generic analysis server system for functional logic programs. In: Proceedings of the ACM SIGPLAN 2014 workshop on partial evaluation and program manipulation (PEPM’14). ACM Press, New York, pp 181-188
[26] Kuchen H, López-Fraguas FJ, Moreno-Navarro JJ, Rodríguez-Artalejo M (1992) Implementing a lazy functional logic language with disequality constraints. In: Proceedings of the 1992 joint international conference and symposium on logic programming. MIT Press, Cambridge
[27] Mitchell N, Runciman C (2007) A static checker for safe pattern matching in Haskell. In: Trends in functional programming, vol 6. Intellect, New York, pp 15-30
[28] Mycroft A (1980) The theory and practice of transforming call-by-need into call-by-value. In: Proceedings of the international symposium on programming, LNCS 83. Springer, Berlin, pp 269-281 · Zbl 0435.68015
[29] Overton D, Somogyi Z, Stuckey PJ (2002) Constraint-based mode analysis of mercury. In: Proceedings of the 4th ACM SIGPLAN international conference on principles and practice of declarative programming (PPDP’02). ACM Press, Berlin, pp 109-120 · Zbl 0296.68092
[30] Peyton Jones S (ed) (2003) Haskell 98 language and libraries—the revised report. Cambridge University Press, Cambridge · Zbl 1067.68041
[31] Reddy US (1985) Narrowing as the operational semantics of functional languages. In: Proceedings of the IEEE internat. symposium on logic programming, Boston, pp 138-151
[32] Reynolds JC (1972) Definitional interpreters for higher-order programming languages. In: Proceedings of the ACM annual conference, pp 717-740. ACM Press, New York
[33] Robinson, JA, A machine-oriented logic based on the resolution principle, J. ACM, 12, 23-41, (1965) · Zbl 0139.12303
[34] Somogyi, Z; Henderson, F; Conway, T, The execution algorithm of Mercury, an efficient purely declarative logic programming language, J Logic Program, 29, 17-64, (1996) · Zbl 0877.68015
[35] Slagle, JR, Automated theorem-proving for theories with simplifiers, commutativity, and associativity, J ACM, 21, 622-642, (1974) · Zbl 0296.68092
[36] Bezem M, Klop JW, de Vrijer R (eds) (2003) Term rewriting systems. Cambridge University Press, Cambridge · Zbl 0139.12303
[37] Warren DHD (1982) Higher-order extensions to prolog: are they needed? In: Machine intelligence, vol 10, pp 441-454
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.