[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
research-article
Open access

The Verse Calculus: A Core Calculus for Deterministic Functional Logic Programming

Published: 31 August 2023 Publication History

Abstract

Functional logic languages have a rich literature, but it is tricky to give them a satisfying semantics. In this paper we describe the Verse calculus, VC, a new core calculus for deterministic functional logic programming. Our main contribution is to equip VC with a small-step rewrite semantics, so that we can reason about a VC program in the same way as one does with lambda calculus; that is, by applying successive rewrites to it. We also show that the rewrite system is confluent for well-behaved terms.

References

[1]
Elvira Albert, Michael Hanus, Frank Huch, Javier Oliver, and German Vidal. 2005. Operational semantics for declarative multi-paradigm languages. Journal of Symbolic Computation, 40, 1 (2005), 795–829. issn:0747-7171 https://doi.org/10.1016/j.jsc.2004.01.001 Reduction Strategies in Rewriting and Programming special issue
[2]
Sergio Antoy. 2011. On the Correctness of Pull-Tabbing. Theory and Practice of Logic Programming, 11, 4-5 (2011), July, 713–730. issn:1475-3081 https://doi.org/10.1017/S1471068411000263
[3]
Sergio Antoy, Daniel W. Brown, and Su-Hui Chiang. 2007. Lazy Context Cloning for Non-Deterministic Graph Rewriting. Electronic Notes in Theoretical Computer Science, 176, 1 (2007), May, 3–23. issn:1571-0661 https://doi.org/10.1016/j.entcs.2006.10.026 Proceedings of the Third International Workshop on Term Graph Rewriting (TERMGRAPH 2006)
[4]
Sergio Antoy and Michael Hanus. 2009. Set Functions for Functional Logic Programming. In Proceedings of the 11th ACM SIGPLAN Conference on Principles and Practice of Declarative Programming (PPDP ’09). Association for Computing Machinery, New York, NY, USA. 73–82. isbn:9781605585680 https://doi.org/10.1145/1599410.1599420
[5]
Sergio Antoy and Michael Hanus. 2010. Functional Logic Programming. Commun. ACM, 53, 4 (2010), April, 74–85. issn:0001-0782 https://doi.org/10.1145/1721654.1721675
[6]
Sergio Antoy and Michael Hanus. 2021. Curry: A Tutorial Introduction. Kiel University (Christian-Albrechts-Universität zu Kiel). https://web.archive.org/web/20220121070135/https://www.informatik.uni-kiel.de/~curry/tutorial/tutorial.pdf
[7]
Zena M. Ariola and Stefan Blom. 2002. Skew confluence and the lambda calculus with letrec. Annals of Pure and Applied Logic, 117, 1 (2002), 95–168. issn:0168-0072 https://doi.org/10.1016/S0168-0072(01)00104-X
[8]
Zena M. Ariola and Jan Willem Klop. 1994. Cyclic lambda graph rewriting. In Proceedings of the Ninth Annual IEEE Symposium on Logic in Computer Science (LICS ’94). IEEE, 416–425. isbn:0-8186-6310-3 https://doi.org/10.1109/LICS.1994.316066
[9]
Zena M. Ariola and Jan Willem Klop. 1997. Lambda Calculus with Explicit Recursion. Information and Computation, 139, 2 (1997), Dec., 154–233. issn:0890-5401 https://doi.org/10.1006/inco.1997.2651
[10]
Zena M. Ariola, John Maraist, Martin Odersky, Matthias Felleisen, and Philip Wadler. 1995. A Call-by-Need Lambda Calculus. In Proceedings of the 22nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’95). Association for Computing Machinery, New York, NY, USA. 233246. isbn:0897916921 https://doi.org/10.1145/199448.199507
[11]
Michael Arntzenius and Neelakantan R. Krishnaswami. 2016. Datafun: A Functional Datalog. In Proceedings of the 21st ACM SIGPLAN International Conference on Functional Programming (ICFP 2016). Association for Computing Machinery, New York, NY, USA. 214–227. isbn:9781450342193 https://doi.org/10.1145/2951913.2951948
[12]
Andrea Asperti and Stefano Guerrini. 1999. The Optimal Implementation of Functional Programming Languages. Cambridge University Press.
[13]
Lennart Augustsson, Joachim Breitner, Koen Claessen, Ranjit Jhala, Simon Peyton Jones, Olin Shivers, Guy Steele, and Tim Sweeney. 2023. The Verse Calculus: A Core Calculus for Deterministic Functional Logic Programming. Epic Games. https://simon.peytonjones.org/verse-calculus/
[14]
Pavel Avgustinov, Oege de Moor, Michael Peyton Jones, and Max Schäfer. 2016. QL: Object-oriented Queries on Relational Data. In 30th European Conference on Object-Oriented Programming (ECOOP 2016), Shriram Krishnamurthi and Benjamin S. Lerner (Eds.) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 56). Schloss Dagstuhl—Leibniz-Zentrum für Informatik, Dagstuhl, Germany. 2:1–2:25. isbn:978-3-95977-014-9 issn:1868-8969 https://doi.org/10.4230/LIPIcs.ECOOP.2016.2
[15]
Pablo Barenbaum, Federico Lochbaum, and Mariana Milicich. 2020. Semantics of a Relational λ -Calculus. In Theoretical Aspects of Computing (ICTAC 2020), Violet Ka I Pun, Volker Stolz, and Adenilso Simao (Eds.). Springer International Publishing, Cham. 242–261. isbn:978-3-030-64276-1 https://doi.org/10.1007/978-3-030-64276-1_13
[16]
Pablo Barenbaum, Federico Lochbaum, and Mariana Milicich. 2021. Semantics of a Relational λ -Calculus (Extended Version), version 4. CoRR, abs/2009.10929 (2021), 28 Feb., 51 pages. arXiv:2009.10929. arxiv:2009.10929
[17]
H. P. (Hendrik Pieter) Barendregt. 1984. The Lambda Calculus: Its Syntax and Semantics (revised ed.) (Studies in Logic and the Foundations of Mathematics, Vol. 103). North-Holland (Elsevier Science Publishers), Amsterdam. isbn:0444867481 lccn:84005966
[18]
Aaron Bembenek, Michael Greenberg, and Stephen Chong. 2020. Formulog: Datalog for SMT-Based Static Analysis. Proc. ACM Programming Languages, 4, OOPSLA (2020), Article 141, Nov., 31 pages. https://doi.org/10.1145/3428209
[19]
Bernd Braß el, Michael Hanus, and Frank Huch. 2004. Encapsulating Non-Determinism in Functional Logic Computations [extended journal version]. Journal of Functional and Logic Programming, 2004, 6 (2004), Dec., 28 pages. http://danae.uni-muenster.de/lehre/kuchen/JFLP/articles/2004/S04-01/A2004-06/JFLP-A2004-06.pdf Special Issue 1. Archived at
[20]
Bernd Braß el, Michael Hanus, and Frank Huch. 2004. Encapsulating Non-Determinism in Functional Logic Computations [workshop version]. In 13th International Workshop on Functional and (Constraint) Logic Programming (WFLP’04). 74–90. issn:0935-3232 Full proceedings available at http://www-i2.informatik.rwth-aachen.de/WFLP04/WFLP-proceedings.pdf
[21]
Bernd Braß el and Frank Huch. 2007. On a Tighter Integration of Functional and Logic Programming. In 5th Asian Symposium on Programming Languages and Systems (APLAS 2007), Zhong Shao (Ed.) (LNCS 4807). Springer-Verlag, Berlin, Heidelberg. 122–138. isbn:978-3-540-76637-7 https://doi.org/10.1007/978-3-540-76637-7_9
[22]
Bernd Braß el and Frank Huch. 2009. The Kiel Curry System KiCS. In Applications of Declarative Programming and Knowledge Management, Dietmar Seipel, Michael Hanus, and Armin Wolf (Eds.) (LNAI 5437). Springer-Verlag, Berlin, Heidelberg. 195–205. isbn:978-3-642-00675-3 https://doi.org/10.1007/978-3-642-00675-3_13
[23]
Stefano Ceri, Georg Gottlob, and Letizia Tanca. 1989. What You Always Wanted to Know about Datalog (and Never Dared to Ask). IEEE Transactions on Knowledge and Data Engineering, 1, 1 (1989), March, 146–166. https://doi.org/10.1109/69.43410 A comprehensive survey with an extensive bibliography
[24]
Manuel M.T. Chakravarty, Yike Guo, Martin Köhler, and Hendrik C.R. Lock. 1998. GOFFIN: Higher-order Functions Meet Concurrent Constraints. Science of Computer Programming, 30, 1 (1998), June, 157–199. issn:0167-6423 https://doi.org/10.1016/S0167-6423(97)00010-5
[25]
Koen Claessen and John Hughes. 2000. QuickCheck: A Lightweight Tool for Random Testing of Haskell Programs. In Proceedings of the Fifth ACM SIGPLAN International Conference on Functional Programming (ICFP ’00). Association for Computing Machinery, New York, NY, USA. 268–279. isbn:1581132026 https://doi.org/10.1145/351240.351266
[26]
William F. Clocksin and Christopher S. Mellish. 2003. Programming in Prolog (Using the ISO Standard) (fifth ed.). Springer-Verlag New York Berlin Heidelberg. isbn:0-387-00678-8
[27]
Ugo Dal Lago, Giulio Guerrieri, and Willem Heijltjes. 2020. Decomposing Probabilistic Lambda-Calculi. In Foundations of Software Science and Computation Structures: 23rd International Conference (FoSSaCS’20), Jean Goubault-Larrecq and Barbara König (Eds.) (LNCS 12077). Springer International, 136–156. isbn:978-3-030-45231-5 https://doi.org/10.1007/978-3-030-45231-5_8
[28]
Ugo de’Liguoro and Adolfo Piperno. 1995. Nondeterministic Extensions of Untyped λ -Calculus. Information and Computation, 122, 2 (1995), 149–177. issn:0890-5401 https://doi.org/10.1006/inco.1995.1145
[29]
Matthias Felleisen, Robert Bruce Findler, and Matthew Flatt. 2009. Semantics Engineering with PLT Redex. MIT Press, Cambridge, Massachusetts, USA. isbn:978-0-262-06275-6 https://mitpress.mit.edu/9780262062756/semantics-engineering-with-plt-redex/
[30]
Matthias Felleisen and Daniel P. Friedman. 1986. Control Operators, the SECD Machine, and the λ -Calculus. In Formal Description of Programming Concepts III: Proceedings of the IFIP TC 2/WG 2.2 Working Conference. Elsevier Science Publishers (North-Holland), 193–217. isbn:978-0444702531 https://web.archive.org/web/20220709064643/https://www.cs.tufts.edu/~nr/cs257/archive/matthias-felleisen/cesk.pdf
[31]
Matthias Felleisen, Daniel P. Friedman, Eugene Kohlbecker, and Bruce Duba. 1987. A Syntactic Theory of Sequential Control. Theoretical Computer Science, 52, 3 (1987), 205–237. issn:0304-3975 https://doi.org/10.1016/0304-3975(87)90109-5
[32]
J.C. González-Moreno, M.T. Hortalá-González, F.J. López-Fraguas, and M. Rodríguez-Artalejo. 1999. An approach to declarative programming based on a rewriting logic. The Journal of Logic Programming, 40, 1 (1999), July, 47–87. issn:0743-1066 https://doi.org/10.1016/S0743-1066(98)10029-8
[33]
Ralph E. Griswold. 1979. User’s Manual for the Icon Programming Language. Department of Computer Science, University of Arizona. https://www2.cs.arizona.edu/icon/ftp/doc/tr78_14.pdf
[34]
Ralph E. Griswold and Madge T. Griswold. 1983. The Icon Programming Language. Prentice-Hall, Englewood Cliffs, New Jersey.
[35]
Ralph E. Griswold and Madge T. Griswold. 2002. The Icon Programming Language (third ed.). Peer-to-Peer Communications. https://web.archive.org/web/20040723085807/https://www2.cs.arizona.edu/icon/ftp/doc/lb1up.pdf
[36]
Ralph E. Griswold, David R. Hanson, and John T. Korb. 1979. The Icon Programming Language: An Overview. SIGPLAN Notices, 14, 4 (1979), April, 18–31. issn:0362-1340 https://doi.org/10.1145/988078.988082
[37]
Ralph E. Griswold, David R. Hanson, and John T. Korb. 1981. Generators in Icon. ACM Trans. Programming Languages and Systems, 3, 2 (1981), April, 144–161. issn:0164-0925 https://doi.org/10.1145/357133.357136
[38]
Michael Hanus. 2013. Functional Logic Programming: From Theory to Curry. In Programming Logics: Essays in Memory of Harald Ganzinger, Andrei Voronkov and Christoph Weidenbach (Eds.) (LNCS, Vol. 7797). Springer, Berlin, Heidelberg. 123–168. isbn:978-3-642-37651-1 https://doi.org/10.1007/978-3-642-37651-1_6
[39]
Michael Hanus, Sergio Antoy, Bernd Braß el, Herbert Kuchen, Francisco J. López-Fraguas, Wolfgang Lux, Juan José Moreno Navarro, Björn Peemöller, and Frank Steiner. 2016. Curry: An Integrated Functional Logic Language (Version 0.9.0). University of Kiel. https://web.archive.org/web/20161020144634/https://www-ps.informatik.uni-kiel.de/currywiki/_media/documentation/report.pdf
[40]
J. Roger Hindley. 1964. The Church-Rosser Property and a Result in Combinatory Logic. Ph. D. Dissertation. University of Newcastle-upon-Tyne. United Kingdom.
[41]
Gérard Huet. 1980. Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems. J. ACM, 27, 4 (1980), Oct., 797–821. issn:0004-5411 https://doi.org/10.1145/322217.322230
[42]
1980. Programming Corner from Icon Newsletter 4. https://www2.cs.arizona.edu/icon/progcorn/pc_inl04.htm
[43]
Thomas Johnsson. 1985. Lambda lifting: Transforming programs to recursive equations. In Functional Programming Languages and Computer Architecture, Jean-Pierre Jouannaud (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg. 190–203. isbn:978-3-540-39677-2
[44]
Oleg Kiselyov, Chung-chieh Shan, Daniel P. Friedman, and Amr Sabry. 2005. Backtracking, interleaving, and terminating monad transformers: (functional pearl). In Proceedings of the 10th ACM SIGPLAN International Conference on Functional Programming, ICFP 2005, Tallinn, Estonia, September 26-28, 2005, Olivier Danvy and Benjamin C. Pierce (Eds.). ACM, 192–203. https://doi.org/10.1145/1086365.1086390
[45]
Arne Kutzner and Manfred Schmidt-Schauß. 1998. A Non-Deterministic Call-by-Need Lambda Calculus. In Proceedings of the Third ACM SIGPLAN International Conference on Functional Programming (ICFP ’98). Association for Computing Machinery, New York, NY, USA. 324–335. isbn:1581130244 https://doi.org/10.1145/289423.289462
[46]
John Lamping. 1990. An Algorithm for Optimal Lambda Calculus Reduction. In Proceedings of the 17th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’90). Association for Computing Machinery, New York, NY, USA. 16–30. isbn:0897913434 https://doi.org/10.1145/96709.96711
[47]
John Launchbury. 1993. A Natural Semantics for Lazy Evaluation. In Proceedings of the 20th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’93). Association for Computing Machinery, New York, NY, USA. 144–154. isbn:0897915607 https://doi.org/10.1145/158511.158618
[48]
Jean-Jacques Lévy. 1978. Réductions Correctes et Optimales dans le Lambda-calcul. Ph. D. Dissertation. Université Paris vii. https://web.archive.org/web/20051016053439/http://pauillac.inria.fr/~levy/pubs/78phd.pdf
[49]
John W. Lloyd. 1999. Programming in an Integrated Functional and Logic Language. Journal of Functional and Logic Programming, 1999, 3 (1999), March, issn:1080–5230 http://danae.uni-muenster.de/lehre/kuchen/JFLP//articles/1999/A99-03/JFLP-A99-03.pdf Archived at
[50]
Francisco Javier López-Fraguas, Enrique Martin-Martin, Juan Rodríguez-Hortalá, and Jaime Sánchez-Hernández. 2014. Rewriting and narrowing for constructor systems with call-time choice semantics. Theory and Practice of Logic programming, 14, 2 (2014), March, 165–213. https://doi.org/ Published online on 30 October 2012
[51]
Francisco J. López-Fraguas, Juan Rodríguez-Hortalá, and Jaime Sánchez-Hernández. 2007. 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 ’07). Association for Computing Machinery, New York, NY, USA. 197–208. isbn:9781595937698 https://doi.org/10.1145/1273920.1273947
[52]
Magnus Madsen, Ming-Ho Yee, and Ondřej Lhoták. 2016. From Datalog to Flix: A Declarative Language for Fixed Points on Lattices. In Proceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’16). Association for Computing Machinery, New York, NY, USA. 194–208. isbn:9781450342612 https://doi.org/10.1145/2908080.2908096
[53]
André Pacak and Sebastian Erdweg. 2022. Functional Programming with Datalog. In 36th European Conference on Object-Oriented Programming (ECOOP 2022), Karim Ali and Jan Vitek (Eds.) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 222). Schloss Dagstuhl—Leibniz-Zentrum für Informatik, Dagstuhl, Germany. 7:1–7:28. isbn:978-3-95977-225-9 issn:1868-8969 https://doi.org/10.4230/LIPIcs.ECOOP.2022.7
[54]
Simon L. Peyton Jones. 1992. Implementing Lazy Functional Languages on Stock Hardware: The Spineless Tagless G-machine. Journal of Functional Programming, 2, 2 (1992), April, 127–202. https://doi.org/10.1017/S0956796800000319 Also available at
[55]
John C. Reynolds. 1972. Definitional Interpreters for Higher-Order Programming Languages. In Proceedings of the ACM Annual Conference—Volume 2 (ACM ’72). Association for Computing Machinery, New York, NY, USA. 717–740. isbn:9781450374927 https://doi.org/10.1145/800194.805852
[56]
J. A. Robinson. 1965. A Machine-Oriented Logic Based on the Resolution Principle. J. ACM, 12, 1 (1965), Jan., 23–41. issn:0004-5411 https://doi.org/10.1145/321250.321253
[57]
Amr Sabry and Matthias Felleisen. 1992. Reasoning about Programs in Continuation-Passing Style. In Proceedings of the 1992 ACM Conference on LISP and Functional Programming, LFP ’92. ACM.
[58]
Vijay A. Saraswat and Martin C. Rinard. 1990. Concurrent Constraint Programming. In Proceedings of the 17th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Frances E. Allen (Ed.) (POPL ’90). ACM Press, 232–245. isbn:0897913434 https://doi.org/10.1145/96709.96733
[59]
Klaus E. Schauser and Seth C. Goldstein. 1995. How Much Non-strictness Do Lenient Programs Require? In Proceedings of the Seventh International Conference on Functional Programming Languages and Computer Architecture (FPCA ’95). Association for Computing Machinery, New York, NY, USA. 216–225. isbn:0897917197 https://doi.org/10.1145/224164.224208
[60]
Manfred Schmidt-Schauß and Elena Machkasova. 2008. A Finite Simulation Method in a Non-deterministic Call-by-Need Lambda-Calculus with Letrec, Constructors, and Case. In 19th International Conference on Rewriting Techniques and Applications (RTA ’08) (LNCS 5117). Springer, Berlin, Heidelberg. 321–335. isbn:978-3-540-70590-1 https://doi.org/10.1007/978-3-540-70590-1_22
[61]
Gert Smolka and Prakash Panangaden. 1985. FRESH: A Higher-Order Language with Unification and Multiple Results. Cornell University, Ithaca, New York, USA. https://hdl.handle.net/1813/6525
[62]
Guy Lewis Steele Jr. 1978. Rabbit: A Compiler for Scheme. Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, Massachusetts, USA. https://web.archive.org/web/20211108071621/https://dspace.mit.edu/bitstream/handle/1721.1/6913/AITR-474.pdf Master’s Dissertation
[63]
David H D Warren, Luis M. Pereira, and Fernando Pereira. 1977. Prolog - The Language and Its Implementation Compared with Lisp. In Proceedings of the 1977 Symposium on Artificial Intelligence and Programming Languages. Association for Computing Machinery, New York, NY, USA. 109–115. isbn:9781450378741 https://doi.org/10.1145/800228.806939

Cited By

View all
  • (2024)Making a Curry Interpreter using Effects and HandlersProceedings of the 17th ACM SIGPLAN International Haskell Symposium10.1145/3677999.3678279(68-82)Online publication date: 29-Aug-2024
  • (2024)JavaScript Language Design and Implementation in TandemCommunications of the ACM10.1145/362472367:5(86-95)Online publication date: 1-May-2024

Index Terms

  1. The Verse Calculus: A Core Calculus for Deterministic Functional Logic Programming
          Index terms have been assigned to the content through auto-classification.

          Recommendations

          Comments

          Please enable JavaScript to view thecomments powered by Disqus.

          Information & Contributors

          Information

          Published In

          cover image Proceedings of the ACM on Programming Languages
          Proceedings of the ACM on Programming Languages  Volume 7, Issue ICFP
          August 2023
          981 pages
          EISSN:2475-1421
          DOI:10.1145/3554311
          Issue’s Table of Contents
          This work is licensed under a Creative Commons Attribution 4.0 International License.

          Publisher

          Association for Computing Machinery

          New York, NY, United States

          Publication History

          Published: 31 August 2023
          Published in PACMPL Volume 7, Issue ICFP

          Permissions

          Request permissions for this article.

          Check for updates

          Author Tags

          1. Verse calculus
          2. Verse language
          3. choice operator
          4. confluence
          5. declarative programming
          6. evaluation strategy
          7. even/odd problem
          8. functional programming
          9. lambda calculus
          10. lenient evaluation
          11. logic programming
          12. logical variables
          13. normal forms
          14. rewrite rules
          15. skew confluence
          16. substitution
          17. unification

          Qualifiers

          • Research-article

          Contributors

          Other Metrics

          Bibliometrics & Citations

          Bibliometrics

          Article Metrics

          • Downloads (Last 12 months)921
          • Downloads (Last 6 weeks)101
          Reflects downloads up to 10 Dec 2024

          Other Metrics

          Citations

          Cited By

          View all
          • (2024)Making a Curry Interpreter using Effects and HandlersProceedings of the 17th ACM SIGPLAN International Haskell Symposium10.1145/3677999.3678279(68-82)Online publication date: 29-Aug-2024
          • (2024)JavaScript Language Design and Implementation in TandemCommunications of the ACM10.1145/362472367:5(86-95)Online publication date: 1-May-2024

          View Options

          View options

          PDF

          View or Download as a PDF file.

          PDF

          eReader

          View online with eReader.

          eReader

          Login options

          Full Access

          Media

          Figures

          Other

          Tables

          Share

          Share

          Share this Publication link

          Share on social media