Nothing Special   »   [go: up one dir, main page]
Skip to main content
SpringerLink
Log in

Embedding Functional Logic Programming in Haskell via a Compiler Plugin

  • Conference paper
  • First Online:
Practical Aspects of Declarative Languages (PADL 2023)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 13880))

Included in the following conference series:

Abstract

We present a technique to embed a functional logic language in Haskell using a GHC plugin. Our approach is based on a monadic lifting that models the functional logic semantics explicitly. Using a GHC plugin, we get many language extensions that GHC provides for free in the embedded language. As a result, we obtain a seamless embedding of a functional logic language, without having to implement a full compiler. We briefly show that our approach can be used to embed other domain-specific languages as well. Furthermore, we can use such a plugin to build a full blown compiler for our language.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 64.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 84.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Available at https://github.com/cau-placc/ghc-language-plugin.

  2. 2.

    We plan to change this; see GHC issue 22401 [30].

  3. 3.

    Using Template Haskell, we also provide an arity-independent wrapper function where one can specify a search strategy as well.

  4. 4.

    The version presented in [16] has a more general type.

  5. 5.

    The transformed version of \( Int \) is called \( Int \) as well.

  6. 6.

    The operator \((\sim )\) denotes homogeneous (both kinds are the same) equality of types.

  7. 7.

    Use this advice at your own risk.

  8. 8.

    It is similar to the type class \( Convertible \) from [16].

  9. 9.

    See README file in the linked repository from Footnote 3.

References

  1. Abel, A., Benke, M., Bove, A., Hughes, J., Norell, U.: Verifying Haskell programs using constructive type theory. In: Proceedings of the 2005 ACM SIGPLAN Workshop on Haskell, pp. 62–73. ACM Press, New York (2005). https://doi.org/10.1145/1088348.1088355

  2. Antoy, S., Hanus, M.: Functional logic programming. Commun. ACM 53(4), 74 (2010). https://doi.org/10.1145/1721654.1721675

    Article  Google Scholar 

  3. Atkey, R., Johann, P.: Interleaving data and effects. J. Funct. Program. 25 (2015). https://doi.org/10.1017/S0956796815000209

  4. Barzilay, E., Clements, J.: Laziness without all the hard work: combining lazy and strict languages for teaching. In: Proceedings of the 2005 Workshop on Functional and Declarative Programming in Education, FDPE 2005, Tallinn, Estonia, p. 9. ACM Press (2005). https://doi.org/10.1145/1085114.1085118

  5. Bernardy, J.P., Boespflug, M., Newton, R.R., Jones, S.P., Spiwack, A.: Linear Haskell: practical linearity in a higher-order polymorphic language. Proc. ACM Program. Lang. 2(POPL), 1–29 (2018). https://doi.org/10.1145/3158093

  6. Bottu, G.J., Karachalias, G., Schrijvers, T., Oliveira, B.C.D.S., Wadler, P.: Quantified class constraints. In: Proceedings of the 10th ACM SIGPLAN International Symposium on Haskell, Haskell 2017, pp. 148–161. Association for Computing Machinery, New York (2017). https://doi.org/10.1145/3122955.3122967

  7. 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_1

    Chapter  Google Scholar 

  8. Breitner, J.: A promise checked is a promise kept: inspection testing. In: Proceedings of the 11th ACM SIGPLAN International Symposium on Haskell, Haskell 2018, pp. 14–25. Association for Computing Machinery, New York (2018). https://doi.org/10.1145/3242744.3242748

  9. Breitner, J.: GHC Extensions stats (2020). https://gist.github.com/nomeata/3d1a75f8ab8980f944fc8c845d6fb9a9

  10. Breitner, J.: [GHC-steering-committee] Prelimary GHC extensions stats (2020). https://mail.haskell.org/pipermail/ghc-steering-committee/2020-November/001876.html

  11. Di Napoli, A., Jhala, R., Löh, A., Vazou, N.: Liquid Haskell as a GHC Plugin - Haskell implementors workshop 2020 (2020). https://icfp20.sigplan.org/details/hiw-2020-papers/1/Liquid-Haskell-as-a-GHC-Plugin

  12. Diatchki, I.S.: Improving Haskell types with SMT. In: Proceedings of the 2015 ACM SIGPLAN Symposium on Haskell, Haskell 2015, pp. 1–10. Association for Computing Machinery, New York (2015). https://doi.org/10.1145/2804302.2804307

  13. Elliott, C.: Compiling to categories. Proc. ACM Program. Lang. 1(ICFP) (2017). https://doi.org/10.1145/3110271

  14. Erwig, M., Peyton Jones, S.: Pattern guards and transformational patterns. Electron. Notes Theor. Comput. Sci. 41(1), 3 (2001). https://doi.org/10.1016/S1571-0661(05)80540-7

    Article  Google Scholar 

  15. Felleisen, M., et al.: A programmable programming language. Commun. ACM 61(3), 62–71 (2018). https://doi.org/10.1145/3127323

    Article  Google Scholar 

  16. Fischer, S., Kiselyov, O., Shan, C.C.: Purely functional lazy nondeterministic programming. J. Funct. Program. 21(4–5), 413–465 (2011). https://doi.org/10.1017/S0956796811000189

    Article  MathSciNet  MATH  Google Scholar 

  17. Flatt, M.: Composable and compilable macros: you want it when? In: Proceedings of the Seventh ACM SIGPLAN International Conference on Functional Programming, ICFP 2002, pp. 72–83. Association for Computing Machinery, New York (2002). https://doi.org/10.1145/581478.581486

  18. Gundry, A.: A typechecker plugin for units of measure: domain-specific constraint solving in GHC Haskell. In: Proceedings of the 2015 ACM SIGPLAN Symposium on Haskell, Haskell 2015, pp. 11–22. Association for Computing Machinery, New York (2015). https://doi.org/10.1145/2804302.2804305

  19. Hanus, M., Kuchen, H., Moreno-Navarro, J.: Curry: a truly functional logic language. In: Proceedings of the ILPS 1995 Workshop on Visions for the Future of Logic Programming, pp. 95–107 (1995)

    Google Scholar 

  20. Hanus, M., Prott, K.O., Teegen, F.: A monadic implementation of functional logic programs. In: Proceedings of the 24th International Symposium on Principles and Practice of Declarative Programming, PPDP 2022. Association for Computing Machinery, New York (2022). https://doi.org/10.1145/3551357.3551370

  21. Hemann, J., Friedman, D.P., Byrd, W.E., Might, M.: A small embedding of logic programming with a simple complete search. In: Proceedings of the 12th Symposium on Dynamic Languages, DLS 2016, pp. 96–107. Association for Computing Machinery, New York (2016). https://doi.org/10.1145/2989225.2989230

  22. Hussmann, H.: Nondeterministic algebraic specifications and nonconfluent term rewriting. J. Log. Program. 12, 237–255 (1992). https://doi.org/10.1016/0743-1066(92)90026-Y

    Article  MathSciNet  MATH  Google Scholar 

  23. Jones, M.P.: A system of constructor classes: overloading and implicit higher-order polymorphism. In: Proceedings of the Conference on Functional Programming Languages and Computer Architecture - FPCA 1993, Copenhagen, Denmark, pp. 52–61. ACM Press (1993). https://doi.org/10.1145/165180.165190

  24. Jones, M.P.: Type classes with functional dependencies. In: Smolka, G. (ed.) ESOP 2000. LNCS, vol. 1782, pp. 230–244. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-46425-5_15

    Chapter  Google Scholar 

  25. Krüger, L.E.: Extending Curry with multi parameter type classes (in German). Master’s thesis, Christian-Albrechts-Universität zu Kiel, Kiel, Germany (2021). https://www.informatik.uni-kiel.de/mh/lehre/abschlussarbeiten/msc/Krueger_Leif_Erik.pdf

  26. Magalhães, J.P., Dijkstra, A., Jeuring, J., Löh, A.: A generic deriving mechanism for Haskell. In: Proceedings of the Third ACM Haskell Symposium on Haskell, Haskell 2010, pp. 37–48. Association for Computing Machinery, New York (2010). https://doi.org/10.1145/1863523.1863529

  27. Petricek, T.: Evaluation strategies for monadic computations. In: Proceedings of Mathematically Structured Functional Programming, vol. 76, pp. 68–89 (2012). https://doi.org/10.4204/EPTCS.76.7

  28. Peyton Jones, S., Shields, M., Launchbury, J., Tolmach, A.: Bridging the gulf: a common intermediate language for ML and Haskell. In: Proceedings of the 25th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 1998, pp. 49–61. Association for Computing Machinery, New York (1998). https://doi.org/10.1145/268946.268951

  29. Pickering, M., Wu, N., Németh, B.: Working with source plugins. In: Proceedings of the 12th ACM SIGPLAN International Symposium on Haskell, Haskell 2019, Berlin, Germany, pp. 85–97. ACM Press (2019). https://doi.org/10.1145/3331545.3342599

  30. Prott, K.O.: Plugin-swappable parser (2022). https://gitlab.haskell.org/ghc/ghc/-/issues/22401

  31. Serrano, A., Hage, J., Peyton Jones, S., Vytiniotis, D.: A quick look at impredicativity. Proc. ACM Program. Lang. 4(ICFP), 1–29 (2020). https://doi.org/10.1145/3408971

  32. Sheard, T., Jones, S.P.: Template meta-programming for Haskell. In: Proceedings of the 2002 ACM SIGPLAN Workshop on Haskell, Haskell 2002, pp. 1–16. Association for Computing Machinery, New York (2002). https://doi.org/10.1145/581690.581691

  33. Siek, J., Taha, W.: Gradual typing for functional languages. In: Proceedings of the 2006 Scheme and Functional Programming Workshop, pp. 81–92 (2006)

    Google Scholar 

  34. Teegen, F.: Extending Curry with type classes and type constructor classes (in German). Master’s thesis, Christian-Albrechts-Universität zu Kiel, Kiel, Germany (2016). https://www.informatik.uni-kiel.de/mh/lehre/abschlussarbeiten/msc/Teegen.pdf

  35. Teegen, F., Prott, K.O., Bunkenburg, N.: Haskell\(^{-1}\): automatic function inversion in Haskell. In: Proceedings of the 14th ACM SIGPLAN International Symposium on Haskell, Haskell 2021, pp. 41–55. Association for Computing Machinery, New York (2021). https://doi.org/10.1145/3471874.3472982

  36. Vytiniotis, D., Jones, S.P., Schrijvers, T., Sulzmann, M.: OutsideIn(X) Modular type inference with local assumptions. J. Funct. Program. 21(4–5), 333–412 (2011). https://doi.org/10.1017/S0956796811000098

    Article  MathSciNet  MATH  Google Scholar 

  37. Wadler, P.: Views: a way for pattern matching to cohabit with data abstraction. In: Proceedings of the 14th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, POPL 1987, Munich, West Germany, pp. 307–313. ACM Press (1987). https://doi.org/10.1145/41625.41653

  38. Wadler, P., Blott, S.: How to make ad-hoc polymorphism less ad hoc. In: Proceedings of the 16th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 1989, Austin, Texas, USA, pp. 60–76. ACM Press (1989). https://doi.org/10.1145/75277.75283

  39. Wadler, P.: Efficient compilation of pattern-matching. In: Jones, S.L.P. (ed.) The Implementation of Functional Programming Languages, pp. 78–103. Prentice-Hall (1987). https://doi.org/10.1016/0141-9331(87)90510-2

Download references

Acknowledgements

We thank our anonymous reviewers and Michael Hanus for their helpful comments and fruitful discussions.

Author information

Authors and Affiliations

  1. Kiel University, Kiel, Germany

    Kai-Oliver Prott & Finn Teegen

  2. Flensburg University of Applied Sciences, Flensburg, Germany

    Jan Christiansen

Authors
  1. Kai-Oliver Prott
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Finn Teegen
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jan Christiansen
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Kai-Oliver Prott .

Editor information

Editors and Affiliations

  1. University of Kiel, Kiel, Germany

    Michael Hanus

  2. Miami University, Oxford, OH, USA

    Daniela Inclezan

Rights and permissions

Reprints and permissions

Copyright information

© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Prott, KO., Teegen, F., Christiansen, J. (2023). Embedding Functional Logic Programming in Haskell via a Compiler Plugin. In: Hanus, M., Inclezan, D. (eds) Practical Aspects of Declarative Languages. PADL 2023. Lecture Notes in Computer Science, vol 13880. Springer, Cham. https://doi.org/10.1007/978-3-031-24841-2_3

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-24841-2_3

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-24840-5

  • Online ISBN: 978-3-031-24841-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation