SpringerLink
Log in

Towards Substructural Property-Based Testing

  • Conference paper
  • First Online:
Logic-Based Program Synthesis and Transformation (LOPSTR 2021)

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

  • 258 Accesses

Abstract

We propose to extend property-based testing to substructural logics to overcome the current lack of reasoning tools in the field. We take the first step by implementing a property-based testing system for specifications written in the linear logic programming language Lolli. We employ the foundational proof certificates architecture to model various data generation strategies. We validate our approach by encoding a model of a simple imperative programming language and its compilation and by testing its meta-theory via mutation analysis.

This work has been partially supported by the National Group of Computing Science (GNCS-INdAM) within the project “Estensioni del Property-based Testing di e con linguaggi di programmazione dichiarativa”.

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
EUR 29.95
Price includes VAT (Germany)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
EUR 46.00
Price includes VAT (Germany)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
EUR 58.84
Price includes VAT (Germany)
  • 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.

    https://softwarefoundations.cis.upenn.edu/plf-current/References.html.

  2. 2.

    We overload “\(\vdash \)” to denote provability for all the sequent systems in this paper, counting on the structure of antecedent and consequent to disambiguate.

  3. 3.

    softwarefoundations.cis.upenn.edu and concrete-semantics.org.

  4. 4.

    This can be circumvented by switching to a more expressive logic, either by internalizing the continuation as an ordered context [46] or by changing representation via forward chaining (destination-passing style) [29].

  5. 5.

    https://github.com/Tovy97/Towards-Substructural-Property-Based-Testing/tree/master/Lolli/Assembly.

  6. 6.

    https://docs.racket-lang.org/redex/benchmark.html.

References

  1. Baelde, D., et al.: Abella: a system for reasoning about relational specifications. J. Formaliz. Reason. 7(2), 1–89 (2014)

    MathSciNet  MATH  Google Scholar 

  2. Blanchette, J.C., Bulwahn, L., Nipkow, T.: Automatic proof and disproof in Isabelle/HOL. In: Tinelli, C., Sofronie-Stokkermans, V. (eds.) FroCoS 2011. LNCS (LNAI), vol. 6989, pp. 12–27. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-24364-6_2

    Chapter  Google Scholar 

  3. Blanco, R., Chihani, Z., Miller, D.: Translating between implicit and explicit versions of proof. In: de Moura, L. (ed.) CADE 2017. LNCS (LNAI), vol. 10395, pp. 255–273. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63046-5_16

    Chapter  Google Scholar 

  4. Blanco, R., Miller, D., Momigliano, A.: Property-based testing via proof reconstruction. In: PPDP, pp. 5:1–5:13. ACM (2019)

    Google Scholar 

  5. Bulwahn, L.: The new Quickcheck for Isabelle. In: Hawblitzel, C., Miller, D. (eds.) CPP 2012. LNCS, vol. 7679, pp. 92–108. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-35308-6_10

    Chapter  MATH  Google Scholar 

  6. Cervesato, I., Hodas, J.S., Pfenning, F.: Efficient resource management for linear logic proof search. Theor. Comput. Sci. 232(1–2), 133–163 (2000)

    Article  MathSciNet  Google Scholar 

  7. Cervesato, I., Pfenning, F.: A linear logical framework. In: LICS, pp. 264–275. IEEE Computer Society (1996)

    Google Scholar 

  8. Cervesato, I., Pfenning, F., Walker, D., Watkins, K.: A concurrent logical framework ii: examples and applications. Technical report, CMU (2002)

    Google Scholar 

  9. Cheney, J.: Toward a general theory of names: binding and scope. In: MERLIN, pp. 33–40. ACM (2005)

    Google Scholar 

  10. Cheney, J., Momigliano, A.: \(\alpha \)Check: a mechanized metatheory model checker. Theory Pract. Logic Program. 17(3), 311–352 (2017)

    Article  MathSciNet  Google Scholar 

  11. Cheney, J., Momigliano, A., Pessina, M.: Advances in property-based testing for \(\alpha \)Prolog. In: Aichernig, B.K.K., Furia, C.A.A. (eds.) TAP 2016. LNCS, vol. 9762, pp. 37–56. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-41135-4_3

    Chapter  Google Scholar 

  12. Chihani, Z., Miller, D., Renaud, F.: A semantic framework for proof evidence. J. Autom. Reason. 59(3), 287–330 (2017)

    Article  MathSciNet  Google Scholar 

  13. Chirimar, J.: Proof theoretic approach to specification languages. Ph.D. thesis. University of Pennsylvania (1995)

    Google Scholar 

  14. Claessen, K., Hughes, J.: QuickCheck: a lightweight tool for random testing of Haskell programs. In: Proceedings of the 2000 ACM SIGPLAN International Conference on Functional Programming (ICFP 2000), pp. 268–279. ACM (2000)

    Google Scholar 

  15. Dubois, C.: Proving ML type soundness within Coq. In: Aagaard, M., Harrison, J. (eds.) TPHOLs 2000. LNCS, vol. 1869, pp. 126–144. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-44659-1_9

    Chapter  Google Scholar 

  16. Felleisen, M., Findler, R.B., Flatt, M.: Semantics Engineering with PLT Redex. The MIT Press, Cambridge (2009)

    MATH  Google Scholar 

  17. Felty, A.P., Momigliano, A.: Hybrid - a definitional two-level approach to reasoning with higher-order abstract syntax. J. Autom. Reason. 48(1), 43–105 (2012)

    Article  Google Scholar 

  18. Fetscher, B., Claessen, K., Pałka, M., Hughes, J., Findler, R.B.: Making random judgments: automatically generating well-typed terms from the definition of a type-system. In: Vitek, J. (ed.) ESOP 2015. LNCS, vol. 9032, pp. 383–405. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46669-8_16

    Chapter  Google Scholar 

  19. Gacek, A., Miller, D., Nadathur, G.: A two-level logic approach to reasoning about computations. J. Autom. Reason. 49(2), 241–273 (2012)

    Article  MathSciNet  Google Scholar 

  20. Georges, A.L., Murawska, A., Otis, S., Pientka, B.: LINCX: a linear logical framework with first-class contexts. In: Yang, H. (ed.) ESOP 2017. LNCS, vol. 10201, pp. 530–555. Springer, Heidelberg (2017). https://doi.org/10.1007/978-3-662-54434-1_20

    Chapter  Google Scholar 

  21. Girard, J.-Y.: Linear logic. Theor. Comput. Sci. 50(1), 1–102 (1987)

    Article  MathSciNet  Google Scholar 

  22. Hodas, J., Miller, D.: Logic programming in a fragment of intuitionistic linear logic. Inf. Comput. 110(2), 327–365 (1994)

    Article  MathSciNet  Google Scholar 

  23. Hritcu, C., et al.: Testing noninterference, quickly. In: Proceedings of the 18th ACM SIGPLAN International Conference on Functional Programming, ICFP 2013, pp. 455–468. ACM, New York, NY, USA (2013)

    Google Scholar 

  24. Hughes, J.: QuickCheck testing for fun and profit. In: Hanus, M. (ed.) PADL 2007. LNCS, vol. 4354, pp. 1–32. Springer, Heidelberg (2006). https://doi.org/10.1007/978-3-540-69611-7_1

    Chapter  Google Scholar 

  25. Jia, Y., Harman, M.: An analysis and survey of the development of mutation testing. IEEE Trans. Softw. Eng. 37(5), 649–678 (2011)

    Article  Google Scholar 

  26. Klein, C., et al.: Run your research: on the effectiveness of lightweight mechanization. In: Proceedings of the 39th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’12, pp. 285–296. ACM, New York, NY, USA (2012)

    Google Scholar 

  27. Leroy, X.: Mechanized semantics - with applications to program proof and compiler verification. In: Logics and Languages for Reliability and Security, volume 25 of NATO Science for Peace and Security Series - D: Information and Communication Security, pp. 195–224. IOS Press (2010)

    Google Scholar 

  28. Liang, C., Miller, D.: Focusing and polarization in linear, intuitionistic, and classical logics. Theor. Comput. Sci. 410(46), 4747–4768 (2009)

    Article  MathSciNet  Google Scholar 

  29. López, P., Pfenning, F., Polakow, J., Watkins, K.: Monadic concurrent linear logic programming. In: PPDP, pp. 35–46. ACM (2005)

    Google Scholar 

  30. Mahmoud, M.Y., Felty, A.P.: Formalization of metatheory of the quipper quantum programming language in a linear logic. J. Autom. Reason. 63(4), 967–1002 (2019)

    Article  MathSciNet  Google Scholar 

  31. Manighetti, M., Miller, D., Momigliano, A.: Two applications of logic programming to Coq. In: TYPES, volume 188 of LIPIcs, pp. 10:1–10:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

    Google Scholar 

  32. Martin, A.: Reasoning using higher-order abstract syntax in a higher-order logic proof environment: improvements to hybrid and a case study. Ph.D. thesis. University of Ottawa (2010). https://ruor.uottawa.ca/handle/10393/19711

  33. McCreight, A., Schürmann, C.: A meta linear logical framework. Electron. Notes Theor. Comput. Sci. 199, 129–147 (2008)

    Article  MathSciNet  Google Scholar 

  34. McDowell, R., Miller, D.: Reasoning with higher-order abstract syntax in a logical framework. ACM Trans. Comput. Log. 3(1), 80–136 (2002)

    Article  MathSciNet  Google Scholar 

  35. Michaylov, S., Pfenning, F.: Natural semantics and some of its meta-theory in Elf. In: Eriksson, L.-H., Hallnäs, L., Schroeder-Heister, P. (eds.) ELP 1991. LNCS, vol. 596, pp. 299–344. Springer, Heidelberg (1992). https://doi.org/10.1007/BFb0013612

    Chapter  Google Scholar 

  36. Miller, D.: Forum: a multiple-conclusion specification logic. Theor. Comput. Sci. 165(1), 201–232 (1996)

    Article  MathSciNet  Google Scholar 

  37. Miller, D., Nadathur, G., Pfenning, F., Scedrov, A.: Uniform proofs as a foundation for logic programming. Ann. Pure Appl. Log. 51, 125–157 (1991)

    Article  MathSciNet  Google Scholar 

  38. Momigliano, A., Ornaghi, M.: The blame game for property-based testing. In: CILC, volume 2396 of CEUR Workshop Proceedings, pp. 4–13. CEUR-WS.org (2019)

    Google Scholar 

  39. Morrisett, J.G., Walker, D., Crary, K., Glew, N.: From system F to typed assembly language. ACM Trans. Program. Lang. Syst. 21(3), 527–568 (1999)

    Article  Google Scholar 

  40. Nigam, V., Miller, D.: Algorithmic specifications in linear logic with subexponentials. In: PPDP, pp. 129–140. ACM (2009)

    Google Scholar 

  41. Paoli, F.: Substructural Logics: A Primer. Kluwer, Alphen aan den Rijn (2002)

    Google Scholar 

  42. Paraskevopoulou, Z., Hriţcu, C., Dénès, M., Lampropoulos, L., Pierce, B.C.: Foundational property-based testing. In: Urban, C., Zhang, X. (eds.) ITP 2015. LNCS, vol. 9236, pp. 325–343. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-22102-1_22

    Chapter  Google Scholar 

  43. Pfenning, F.: Logical frameworks. In: Robinson, A., Voronkov, A. (eds.), Handbook of Automated Reasoning. Elsevier Science Publishers (1999)

    Google Scholar 

  44. Pfenning, F., Simmons, R.J.: Substructural operational semantics as ordered logic programming. In: LICS, pp. 101–110. IEEE Computer Society (2009)

    Google Scholar 

  45. Pientka, B., Dunfield, J.: Beluga: a framework for programming and reasoning with deductive systems (system description). In: Giesl, J., Hähnle, R. (eds.) IJCAR 2010. LNCS (LNAI), vol. 6173, pp. 15–21. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14203-1_2

    Chapter  MATH  Google Scholar 

  46. Polakow, J.: Linear logic programming with an ordered context. In: PPDP, pp. 68–79. ACM (2000)

    Google Scholar 

  47. Reynolds, J.C.: The discoveries of continuations. LISP Symb. Comput. 6(3–4), 233–248 (1993)

    Google Scholar 

  48. Roberson, M., Harries, M., Darga, P.T., Boyapati, C.: Efficient software model checking of soundness of type systems. In: Harris, G.E. (ed.), OOPSLA, pp. 493–504. ACM (2008)

    Google Scholar 

  49. Schack-Nielsen, A., Schürmann, C.: Celf – a logical framework for deductive and concurrent systems (system description). In: Armando, A., Baumgartner, P., Dowek, G. (eds.) IJCAR 2008. LNCS (LNAI), vol. 5195, pp. 320–326. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-71070-7_28

    Chapter  Google Scholar 

  50. Tarau, P.: A combinatorial testing framework for intuitionistic propositional theorem provers. In: Alferes, J.J., Johansson, M. (eds.) PADL 2019. LNCS, vol. 11372, pp. 115–132. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-05998-9_8

    Chapter  Google Scholar 

  51. Wadler, P.: Linear types can change the world! In: Programming Concepts and Methods, p. 561. North-Holland (1990)

    Google Scholar 

  52. Yardeni, E., Shapiro, E.: A type system for logic programs. J. Log. Program. 10(2), 125–153 (1991)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgments

We are grateful to Dale Miller for many discussions and in particular for suggesting the use of logical continuations. Thanks also to Jeff Polakow for his comments on a draft version of this paper.

Author information

Authors and Affiliations

  1. Dipartimento di Informatica, Università degli Studi di Milano, Milan, Italy

    Marco Mantovani & Alberto Momigliano

Authors
  1. Marco Mantovani
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Alberto Momigliano
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Alberto Momigliano .

Editor information

Editors and Affiliations

  1. IASI-CNR, Rome, Italy

    Emanuele De Angelis

  2. University of Namur, Namur, Belgium

    Wim Vanhoof

Rights and permissions

Reprints and permissions

Copyright information

© 2022 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Mantovani, M., Momigliano, A. (2022). Towards Substructural Property-Based Testing. In: De Angelis, E., Vanhoof, W. (eds) Logic-Based Program Synthesis and Transformation. LOPSTR 2021. Lecture Notes in Computer Science, vol 13290. Springer, Cham. https://doi.org/10.1007/978-3-030-98869-2_6

Download citation

  • DOI: https://doi.org/10.1007/978-3-030-98869-2_6

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-030-98868-5

  • Online ISBN: 978-3-030-98869-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation