nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

Synthesizing Set Functions

verfasst von : Sergio Antoy, Michael Hanus, Finn Teegen

Erschienen in: Functional and Constraint Logic Programming

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Set functions are a feature of functional logic programming to encapsulate all results of a non-deterministic computation in a single data structure. Given a function f of a functional logic program written in Curry, we describe a technique to synthesize the definition of the set function of f. The definition produced by our technique is based on standard Curry constructs. Our approach is interesting for three reasons. It allows reasoning about set functions, it offers an implementation of set functions which can be added to any Curry system, and it has the potential of changing our thinking about the implementation of non-determinism, a notoriously difficult problem.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Enhancing POI Testing Through the Use of Additional Information

Nächstes Kapitel Towards a Constraint Solver for Proving Confluence with Invariant and Equivalence of Realistic CHR Programs

The notion of “plural function” is also used in [22] to define a “plural” semantics for functional logic programs. Although the type of their plural functions is identical to ours, their semantics is quite different.

Actually, this operation is the monadic “bind” operation with flipped arguments if

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-16202-3_6/482311_1_En_6_IEq92_HTML.gif

is an instance of

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-16202-3_6/482311_1_En_6_IEq93_HTML.gif

, as proposed in [13]. Here, we prefer to provide a more direct implementation.

This is a consequence of the fact that

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-16202-3_6/482311_1_En_6_IEq96_HTML.gif

is a functor. A more general treatment of these structures can be found in [6].

Although the current definition of Curry [17] does not include type classes, many implementations of Curry, like PAKCS, KiCS2, or MCC, support them.

The use of

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-16202-3_6/482311_1_En_6_IEq124_HTML.gif

ensures that the

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-16202-3_6/482311_1_En_6_IEq125_HTML.gif

argument is evaluated. Thus, non-determinism and failures in arguments of set functions are not encapsulated, as intended.

Multi-parameter type classes are not yet supported in the Curry systems PAKCS and KiCS2. The code presented here is more elegant, but equivalent, to the actual implementation.

Of course, one can replace such lists by more efficient access structures.

This requires a specific primitive

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-16202-3_6/482311_1_En_6_IEq204_HTML.gif

to catch failures, which is usually supported in Curry implementations to handle exceptions.

https://github.com/finnteegen/synthesizing-set-functions.

Alqaddoumi, A., Antoy, S., Fischer, S., Reck, F.: The pull-tab transformation. In: Proceedings of the Third International Workshop on Graph Computation Models, Enschede, The Netherlands, pp. 127–132 (2010). http://gcm-events.org/gcm2010/pages/gcm2010-preproceedings.pdf

Antoy, S., Echahed, R., Hanus, M.: A needed narrowing strategy. J. ACM 47(4), 776–822 (2000)MathSciNetCrossRef

Antoy, S., Hanus, M.: Overlapping rules and logic variables in functional logic programs. In: Etalle, S., Truszczyński, M. (eds.) ICLP 2006. LNCS, vol. 4079, pp. 87–101. Springer, Heidelberg (2006). https://doi.org/10.1007/11799573_9CrossRefMATH

Antoy, S., Hanus, M.: Set functions for functional logic programming. In: Proceedings of the 11th ACM SIGPLAN International Conference on Principles and Practice of Declarative Programming (PPDP 2009), pp. 73–82. ACM Press (2009)

Antoy, S., Hanus, M.: Functional logic programming. Commun. ACM 53(4), 74–85 (2010)CrossRef

Atkey, R., Johann, P.: Interleaving data and effects. J. Funct. Programm. 25, e20 (2015). https://doi.org/10.1017/S0956796815000209MathSciNetCrossRefMATH

Braßel, B., Fischer, S., Hanus, M., Reck, F.: Transforming functional logic programs into monadic functional programs. In: Mariño, J. (ed.) WFLP 2010. LNCS, vol. 6559, pp. 30–47. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-20775-4_2CrossRefMATH

Braßel, B., Hanus, M., Huch, F.: Encapsulating non-determinism in functional logic computations. J. Funct. Log. Program. 6, 2004 (2004)MathSciNetMATH

Braßel, B., Hanus, M., Peemöller, B., Reck, F.: KiCS2: a new compiler from curry to Haskell. In: Kuchen, H. (ed.) WFLP 2011. LNCS, vol. 6816, pp. 1–18. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22531-4_1CrossRef

10.

Christiansen, J., Hanus, M., Reck, F., Seidel, D.: A semantics for weakly encapsulated search in functional logic programs. In: Proceedings of the 15th International Symposium on Principle and Practice of Declarative Programming (PPDP 2013), pp. 49–60. ACM Press (2013)

11.

de Dios Castro, J., López-Fraguas, F.J.: Extra variables can be eliminated from functional logic programs. Electron. Notes Theor. Comput. Sci. 188, 3–19 (2007)CrossRef

12.

Dijkstra, E.W.: A note on two problems in connexion with graphs. Numer. Math. 1(1), 269–271 (1959)MathSciNetCrossRef

13.

Fischer, S., Kiselyov, O., Shan, C.: Purely functional lazy nondeterministic programming. J. Funct. program. 21(4&5), 413–465 (2011)MathSciNetCrossRef

14.

González-Moreno, J.C., Hortalá-González, M.T., López-Fraguas, F.J., Rodríguez-Artalejo, M.: An approach to declarative programming based on a rewriting logic. J. Log. Program. 40, 47–87 (1999)MathSciNetCrossRef

15.

Hanus, M.: Functional logic programming: from theory to curry. In: Voronkov, A., Weidenbach, C. (eds.) Programming Logics. LNCS, vol. 7797, pp. 123–168. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-37651-1_6CrossRefMATH

16.

Hanus, M., et al.: PAKCS: the Portland Aachen Kiel curry system (2018). http://www.informatik.uni-kiel.de/~pakcs/

17.

Hanus, M. (ed.): Curry: an integrated functional logic language (vers. 0.9.0) (2016). http://www.curry-language.org

18.

Hinze, R.: Prolog’s control constructs in a functional setting - axioms and implementation. Int. J. Found. Comput. Sci. 12(2), 125–170 (2001)CrossRef

19.

Hussmann, H.: Nondeterministic algebraic specifications and nonconfluent term rewriting. J. Log. Program. 12, 237–255 (1992)MathSciNetCrossRef

20.

López-Fraguas, F.J., Rodríguez-Hortalá, J., Sánchez-Hernández, J.: A simple rewrite notion for call-time choice semantics. In: Proceedings of the 9th ACM SIGPLAN International Conference on Principles and Practice of Declarative Programming (PPDP 2007), pp. 197–208. ACM Press (2007)

21.

José Moreno-Navarro, J., Kuchen, H., Loogen, R.: Lazy narrowing in a graph machine. In: Kirchner, H., Wechler, W. (eds.) ALP 1990. LNCS, vol. 463, pp. 298–317. Springer, Heidelberg (1990). https://doi.org/10.1007/3-540-53162-9_47CrossRef

22.

Riesco, A., Rodríguez-Hortalá, J.: Singular and plural functions for functional logic programming. Theory Pract. Log. Program. 14(1), 65–116 (2014)MathSciNetCrossRef

23.

Seres, S., Spivey, M., Hoare, T.: Algebra of logic programming. In: Proceedings of the ICLP 1999, pp. 184–199. MIT Press (1999)

24.

Wadler, P.: How to replace failure by a list of successes a method for exception handling, backtracking, and pattern matching in lazy functional languages. In: Jouannaud, J.-P. (ed.) FPCA 1985. LNCS, vol. 201, pp. 113–128. Springer, Heidelberg (1985). https://doi.org/10.1007/3-540-15975-4_33CrossRef

Titel: Synthesizing Set Functions
verfasst von: Sergio Antoy
Michael Hanus
Finn Teegen
Verlag: Springer International Publishing
Buch: Functional and Constraint Logic Programming
Print ISBN: 978-3-030-16201-6

Electronic ISBN: 978-3-030-16202-3

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-16202-3_6

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"