SpringerLink
Log in

Memoized Pull-Tabbing for Functional Logic Programming

  • Conference paper
  • First Online:
Functional and Constraint Logic Programming (WFLP 2020)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 12560))

Included in the following conference series:

  • 170 Accesses

Abstract

Pull-tabbing is an evaluation technique for functional logic programs which computes all non-deterministic results in a single graph structure. Pull-tab steps are local graph transformations to move non-deterministic choices towards the root of an expression. Pull-tabbing is independent of a search strategy so that different strategies (depth-first, breadth-first, parallel) can be used to extract the results of a computation. It has been used to compile functional logic languages into imperative or purely functional target languages. Pull-tab steps might duplicate choices in case of shared subexpressions. This could result in a dramatic increase of execution time compared to a backtracking implementation. In this paper we propose a refinement which avoids this efficiency problem while kee** all the good properties of pull-tabbing. We evaluate a first implementation of this improved technique in the Julia programming 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
EUR 32.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 (Canada)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (Canada)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (Canada)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** 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.

    Variables and function names usually start with lowercase letters and the names of type and data constructors start with an uppercase letter. The application of f to e is denoted by juxtaposition (“f e”).

  2. 2.

    https://julialang.org/.

  3. 3.

    Available at https://github.com/cau-placc/julia-curry.

  4. 4.

    All benchmarks were executed on a Linux machine running Ubuntu 18.04 with an Intel Core i7-85550U (1.8 GHz) processor.

  5. 5.

    The actual programs are available with the implementation described in Sect. 5.

References

  1. Albert, E., Hanus, M., Huch, F., Oliver, J., Vidal, G.: Operational semantics for declarative multi-paradigm languages. J. Symb. Comput. 40(1), 795–829 (2005)

    Article  MathSciNet  Google Scholar 

  2. 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://gcm2010.imag.fr/pages/gcm2010-preproceedings.pdf

  3. Antoy, S.: On the correctness of pull-tabbing. Theory Pract. Logic Program. 11(4–5), 713–730 (2011)

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  5. Antoy, S., Hanus, M.: Compiling multi-paradigm declarative programs into prolog. In: Kirchner, H., Ringeissen, C. (eds.) FroCoS 2000. LNCS (LNAI), vol. 1794, pp. 171–185. Springer, Heidelberg (2000). https://doi.org/10.1007/10720084_12

    Chapter  Google Scholar 

  6. Antoy, S., Hanus, M.: Overlap** 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_9

    Chapter  MATH  Google Scholar 

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

    Article  Google Scholar 

  8. Antoy, S., Hanus, M.: Contracts and specifications for functional logic programming. In: Russo, C., Zhou, N.-F. (eds.) PADL 2012. LNCS, vol. 7149, pp. 33–47. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-27694-1_4

    Chapter  Google Scholar 

  9. Antoy, S., Hanus, M., Jost, A., Libby, S.: ICurry. In: Hofstedt, P., Abreu, S., John, U., Kuchen, H., Seipel, D. (eds.) INAP/WLP/WFLP -2019. LNCS (LNAI), vol. 12057, pp. 286–307. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-46714-2_18

    Chapter  Google Scholar 

  10. Antoy, S., Hanus, M., Liu, J., Tolmach, A.: A virtual machine for functional logic computations. In: Grelck, C., Huch, F., Michaelson, G.J., Trinder, P. (eds.) IFL 2004. LNCS, vol. 3474, pp. 108–125. Springer, Heidelberg (2005). https://doi.org/10.1007/11431664_7

    Chapter  MATH  Google Scholar 

  11. Antoy, S., Jost, A.: A new functional-logic compiler for curry: Sprite. In: Hermenegildo, M.V., Lopez-Garcia, P. (eds.) LOPSTR 2016. LNCS, vol. 10184, pp. 97–113. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63139-4_6

    Chapter  MATH  Google Scholar 

  12. Antoy, S., Peters, A.: Compiling a functional logic language: the basic scheme. In: Schrijvers, T., Thiemann, P. (eds.) FLOPS 2012. LNCS, vol. 7294, pp. 17–31. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29822-6_5

    Chapter  Google Scholar 

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

  14. Braßel, B., Hanus, M., Peemöller, B., Reck, F.: Implementing equational constraints in a functional language. In: Sagonas, K. (ed.) PADL 2013. LNCS, vol. 7752, pp. 125–140. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-45284-0_9

    Chapter  Google Scholar 

  15. Braßel, B., Huch, F.: On a tighter integration of functional and logic programming. In: Shao, Z. (ed.) APLAS 2007. LNCS, vol. 4807, pp. 122–138. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-76637-7_9

    Chapter  MATH  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  17. 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)

    Article  MathSciNet  Google Scholar 

  18. Hanus, M.: Improving lazy non-deterministic computations by demand analysis. In: Technical Communications of the 28th International Conference on Logic Programming, vol. 17, pp. 130–143. Leibniz International Proceedings in Informatics (LIPIcs) (2012)

    Google Scholar 

  19. Hanus, M., et al.: PAKCS: The Portland Aachen Kiel Curry System (2018). http://www.informatik.uni-kiel.de/~pakcs/

  20. Hanus, M., Peemöller, B., Reck, F.: Search strategies for functional logic programming. In: Proceedings of the 5th Working Conference on Programming Languages (ATPS 2012). LNI, vol. 199, pp. 61–74. Springer (2012). https://dl.gi.de/20.500.12116/18376

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

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

    Article  MathSciNet  Google Scholar 

  23. Launchbury, J.: A natural semantics for lazy evaluation. In: Proceedings of the 20th ACM Symposium on Principles of Programming Languages (POPL 1993), pp. 144–154. ACM Press (1993)

    Google Scholar 

  24. Loogen, R., Fraguas, F.L., Artalejo, M.R.: A demand driven computation strategy for lazy narrowing. In: Bruynooghe, M., Penjam, J. (eds.) PLILP 1993. LNCS, vol. 714, pp. 184–200. Springer, Heidelberg (1993). https://doi.org/10.1007/3-540-57186-8_79

    Chapter  Google Scholar 

  25. López Fraguas, F.J., Sánchez Hernández, J.: TOY: a multiparadigm declarative system. In: Narendran, P., Rusinowitch, M. (eds.) RTA 1999. LNCS, vol. 1631, pp. 244–247. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48685-2_19

    Chapter  Google Scholar 

  26. Partain, W.: The nofib benchmark suite of Haskell programs. In: Launchbury, J., Sansom, P. (eds.) Functional Programming, Glasgow 1992. Workshops in Computing, pp. 195–202. Springer, London (1993). https://doi.org/10.1007/978-1-4471-3215-8_17

    Chapter  Google Scholar 

  27. Peyton Jones, S. (ed.): Haskell 98 Language and Libraries-The Revised Report. Cambridge University Press (2003)

    Google Scholar 

  28. Plump, D.: Term graph rewriting. In: Ehrig, H., Engels, G., Kreowski, H.-J., Rozenberg, G. (eds.) Handbook of Graph Grammars and Computing by Graph Transformation, Applications, Languages and Tools, vol. 2, pp. 3–61. World Scientific (1999)

    Google Scholar 

  29. Warren, D.H.D.: An abstract Prolog instruction set. Technical note 309, SRI International, Stanford (1983)

    Google Scholar 

  30. Wittorf, M.A.: Generic translation of Curry programs into imperative programs (in German). Master’s thesis, Kiel University (2018)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut für Informatik, CAU Kiel, 24098, Kiel, Germany

    Michael Hanus & Finn Teegen

Authors
  1. Michael Hanus
    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

Corresponding author

Correspondence to Michael Hanus .

Editor information

Editors and Affiliations

  1. Kiel University, Kiel, Germany

    Michael Hanus

  2. University of Bologna, Bologna, Italy

    Claudio Sacerdoti Coen

Rights and permissions

Reprints and permissions

Copyright information

© 2021 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Hanus, M., Teegen, F. (2021). Memoized Pull-Tabbing for Functional Logic Programming. In: Hanus, M., Sacerdoti Coen, C. (eds) Functional and Constraint Logic Programming. WFLP 2020. Lecture Notes in Computer Science(), vol 12560. Springer, Cham. https://doi.org/10.1007/978-3-030-75333-7_4

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-75333-7_4

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-75332-0

  • Online ISBN: 978-3-030-75333-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation