{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,17]],"date-time":"2026-09-17T11:31:21Z","timestamp":1789644681634,"version":"4.0.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"ICFP","license":[{"start":{"date-parts":[[2018,7,30]],"date-time":"2018-07-30T00:00:00Z","timestamp":1532908800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1319880, 1521539"],"award-info":[{"award-number":["1319880, 1521539"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2018,7,30]]},"abstract":"<jats:p>Good tools can bring mechanical verification to programs written in mainstream functional languages. We use &lt;pre&gt;hs-to-coq&lt;\/pre&gt; to translate significant portions of Haskell\u2019s &lt;pre&gt;containers&lt;\/pre&gt; library into Coq, and verify it against specifications that we derive from a variety of sources including type class laws, the library\u2019s test suite, and interfaces from Coq\u2019s standard library. Our work shows that it is feasible to verify mature, widely-used, highly optimized, and unmodified Haskell code. We also learn more about the theory of weight-balanced trees, extend &lt;pre&gt;hs-to-coq&lt;\/pre&gt; to handle partiality, and \u2013 since we found no bugs \u2013 attest to the superb quality of well-tested functional code.<\/jats:p>","DOI":"10.1145\/3236784","type":"journal-article","created":{"date-parts":[[2018,7,31]],"date-time":"2018-07-31T19:41:18Z","timestamp":1533066078000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["Ready, set, verify! applying hs-to-coq to real-world Haskell code (experience report)"],"prefix":"10.1145","volume":"2","author":[{"given":"Joachim","family":"Breitner","sequence":"first","affiliation":[{"name":"University of Pennsylvania, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Antal","family":"Spector-Zabusky","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yao","family":"Li","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christine","family":"Rizkallah","sequence":"additional","affiliation":[{"name":"UNSW, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"John","family":"Wiegley","sequence":"additional","affiliation":[{"name":"BAE Systems, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stephanie","family":"Weirich","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2018,7,30]]},"reference":[{"key":"e_1_2_2_1_1","first-page":"92","article-title":"Implementing sets efficiently in a functional language","author":"Adams Stephen","year":"1992","unstructured":"Stephen Adams . 1992 . Implementing sets efficiently in a functional language ,. Research Report CSTR 92 - 10 . University of Southampton. Stephen Adams. 1992. Implementing sets efficiently in a functional language,. Research Report CSTR 92-10. University of Southampton.","journal-title":"Research Report CSTR"},{"key":"e_1_2_2_2_1","article-title":"Position paper: the science of deep specification","volume":"375","author":"Appel Andrew W.","year":"2017","unstructured":"Andrew W. Appel , Lennart Beringer , Adam Chlipala , Benjamin C. Pierce , Zhong Shao , Stephanie Weirich , and Steve Zdancewic . 2017 . Position paper: the science of deep specification . Philosophical Transactions of the Royal Society of London A: Mathematical, Physical and Engineering Sciences 375 , 2104 (2017). Andrew W. Appel, Lennart Beringer, Adam Chlipala, Benjamin C. Pierce, Zhong Shao, Stephanie Weirich, and Steve Zdancewic. 2017. Position paper: the science of deep specification. Philosophical Transactions of the Royal Society of London A: Mathematical, Physical and Engineering Sciences 375, 2104 (2017).","journal-title":"Philosophical Transactions of the Royal Society of London A: Mathematical, Physical and Engineering Sciences"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03359-9_6"},{"key":"e_1_2_2_4_1","unstructured":"Edwin Brady. 2017. Type-driven Development With Idris. Manning.  Edwin Brady. 2017. Type-driven Development With Idris. Manning."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3236784"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14052-5_15"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/351240.351266"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1111037.1111056"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796811000104"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/11814771_48"},{"key":"e_1_2_2_11_1","volume-title":"Informal proceedings, 7th International Workshop on Satisfiability Modulo Theories at CADE","volume":"22","author":"Kr\u00f6ning Daniel","year":"2009","unstructured":"Daniel Kr\u00f6ning , Philipp R\u00fcmmer , and Georg Weissenbacher . 2009 . A proposal for a theory of finite sets, lists, and maps for the SMT-LIB standard . In Informal proceedings, 7th International Workshop on Satisfiability Modulo Theories at CADE , Vol. 22 . Daniel Kr\u00f6ning, Philipp R\u00fcmmer, and Georg Weissenbacher. 2009. A proposal for a theory of finite sets, lists, and maps for the SMT-LIB standard. In Informal proceedings, 7th International Workshop on Satisfiability Modulo Theories at CADE, Vol. 22."},{"key":"e_1_2_2_12_1","unstructured":"The Coq development team. 2016. The Coq proof assistant reference manual. LogiCal Project. http:\/\/coq.inria.fr Version 8.6.1.  The Coq development team. 2016. The Coq proof assistant reference manual. LogiCal Project. http:\/\/coq.inria.fr Version 8.6.1."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/321479.321481"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/800152.804906"},{"key":"e_1_2_2_15_1","volume-title":"Archive of Formal Proofs (March","author":"Nipkow Tobias","year":"2018","unstructured":"Tobias Nipkow and Stefan Dirix . 2018. Weight-Balanced Trees . Archive of Formal Proofs (March 2018 ). http:\/\/isa-afp.org\/ entries\/Weight_Balanced_Trees.html , Formal proof development. Tobias Nipkow and Stefan Dirix. 2018. Weight-Balanced Trees. Archive of Formal Proofs (March 2018). http:\/\/isa-afp.org\/ entries\/Weight_Balanced_Trees.html , Formal proof development."},{"key":"e_1_2_2_16_1","volume-title":"Lecture Notes in Computer Science","author":"Nipkow Tobias","unstructured":"Tobias Nipkow , Lawrence C. Paulson , and Markus Wenzel . 2002. Isabelle\/ HOL - A Proof Assistant for Higher-Order Logic . Lecture Notes in Computer Science , Vol. 2283 . Springer . Tobias Nipkow, Lawrence C. Paulson, and Markus Wenzel. 2002. Isabelle\/HOL - A Proof Assistant for Higher-Order Logic. Lecture Notes in Computer Science, Vol. 2283. Springer."},{"key":"e_1_2_2_17_1","volume-title":"Purely functional data structures","author":"Okasaki Chris","unstructured":"Chris Okasaki . 1999. Purely functional data structures . Cambridge University Press . Chris Okasaki. 1999. Purely functional data structures. Cambridge University Press."},{"key":"e_1_2_2_18_1","volume-title":"Fast Mergeable Integer Maps. In In Workshop on ML. 77\u201386","author":"Okasaki Chris","year":"1998","unstructured":"Chris Okasaki and Andrew Gill . 1998 . Fast Mergeable Integer Maps. In In Workshop on ML. 77\u201386 . Chris Okasaki and Andrew Gill. 1998. Fast Mergeable Integer Maps. In In Workshop on ML. 77\u201386."},{"key":"e_1_2_2_19_1","volume-title":"Haskell Workshop.","author":"Jones Simon Peyton","year":"2001","unstructured":"Simon Peyton Jones , Andrew Tolmach , and Tony Hoare . 2001 . Playing by the rules: rewriting as a practical optimisation technique in GHC . In Haskell Workshop. Simon Peyton Jones, Andrew Tolmach, and Tony Hoare. 2001. Playing by the rules: rewriting as a practical optimisation technique in GHC. In Haskell Workshop."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3167092"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1863523.1863526"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3122955.3122963"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-37036-6_13"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2628136.2628161"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3158141"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3236784","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3236784","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3236784","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:41:28Z","timestamp":1750282888000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3236784"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,30]]},"references-count":25,"journal-issue":{"issue":"ICFP","published-print":{"date-parts":[[2018,7,30]]}},"alternative-id":["10.1145\/3236784"],"URL":"https:\/\/doi.org\/10.1145\/3236784","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,7,30]]},"assertion":[{"value":"2018-07-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}