{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,18]],"date-time":"2026-07-18T02:36:53Z","timestamp":1784342213804,"version":"3.55.0"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,8,17]],"date-time":"2017-08-17T00:00:00Z","timestamp":1502928000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-0964409 and CCF-1566411"],"award-info":[{"award-number":["CCF-0964409 and CCF-1566411"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"crossref","award":["N00014-13-1-0089"],"award-info":[{"award-number":["N00014-13-1-0089"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"crossref","award":["FA9550-12-1-0400"],"award-info":[{"award-number":["FA9550-12-1-0400"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Program. Lang. Syst."],"published-print":{"date-parts":[[2017,12,31]]},"abstract":"<jats:p>We introduce a general way to locate programmer mistakes that are detected by static analyses. The program analysis is expressed in a general constraint language that is powerful enough to model type checking, information flow analysis, dataflow analysis, and points-to analysis. Mistakes in program analysis result in unsatisfiable constraints. Given an unsatisfiable system of constraints, both satisfiable and unsatisfiable constraints are analyzed to identify the program expressions most likely to be the cause of unsatisfiability. The likelihood of different error explanations is evaluated under the assumption that the programmer\u2019s code is mostly correct, so the simplest explanations are chosen, following Bayesian principles. For analyses that rely on programmer-stated assumptions, the diagnosis also identifies assumptions likely to have been omitted. The new error diagnosis approach has been implemented as a tool called SHErrLoc, which is applied to three very different program analyses, such as type inference for a highly expressive type system implemented by the Glasgow Haskell Compiler\u2014including type classes, Generalized Algebraic Data Types (GADTs), and type families. The effectiveness of the approach is evaluated using previously collected programs containing errors. The results show that when compared to existing compilers and other tools, SHErrLoc consistently identifies the location of programmer errors significantly more accurately, without any language-specific heuristics.<\/jats:p>","DOI":"10.1145\/3121137","type":"journal-article","created":{"date-parts":[[2017,8,24]],"date-time":"2017-08-24T11:49:04Z","timestamp":1503575344000},"page":"1-47","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["SHErrLoc"],"prefix":"10.1145","volume":"39","author":[{"given":"Danfeng","family":"Zhang","sequence":"first","affiliation":[{"name":"Pennsylvania State University, PA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrew C.","family":"Myers","sequence":"additional","affiliation":[{"name":"Cornell University, NY, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dimitrios","family":"Vytiniotis","sequence":"additional","affiliation":[{"name":"Microsoft Research Cambridge, Cambridge, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Simon","family":"Peyton-Jones","sequence":"additional","affiliation":[{"name":"Microsoft Research Cambridge, Cambridge, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,8,17]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6423(99)00007-6"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/165180.165188"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2012.22"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/604131.604140"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798337716"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2462188"},{"key":"e_1_2_1_8_1","unstructured":"Shen Chen. 2014. Accuracy of CF-Typing. Private communication. (2014)."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535838.2535863"},{"key":"e_1_2_1_11_1","volume-title":"Haynes","author":"Choppella Venkatesh","year":"1995","unstructured":"Venkatesh Choppella and Christopher T. Haynes. 1995. Diagnosis of Ill-typed Programs. Technical Report. Indiana University."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/360051.360056"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2254064.2254087"},{"key":"e_1_2_1_15_1","unstructured":"EasyOCaml. 2009. EasyOCaml. Retrieved from http:\/\/easyocaml.forge.ocamlcore.org."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1186632.1186635"},{"key":"e_1_2_1_18_1","volume-title":"Rubin","author":"Gelman Andrew","year":"2004","unstructured":"Andrew Gelman, John B. Carlin, Hal S. Stern, and Donald B. Rubin. 2004. Bayesian Data Analysis (2nd ed.). Chapman 8 Hall\/CRC."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2004.01.004"},{"key":"e_1_2_1_20_1","unstructured":"Jurriaan Hage. 2014. Helium benchmark programs (2002--2005). Private communication. (2014)."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/1757028.1757040"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSSC.1968.300136"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/871895.871902"},{"key":"e_1_2_1_25_1","unstructured":"Helium 1.8(2014) 2014. Helium (ver. 1.8). Retrieved from https:\/\/hackage.haskell.org\/package\/helium."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/130697.130699"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/512644.512649"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1453101.1453135"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/1298455.1298471"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/291891.291892"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250734.1250783"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065010.1065014"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1542476.1542485"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","unstructured":"Calvin Loncaric Satish Chandra Cole Schlesinger and Manu Sridharan. 2016. A practical framework for type inference error explanation. 781--799. 10.1145\/2983990.2983994","DOI":"10.1145\/2983990.2983994"},{"key":"e_1_2_1_35_1","unstructured":"Simon Marlow and Simon Peyton-Jones. 1993. The Glasgow Haskell Compiler. Retrieved from http:\/\/www.aosabook.org\/en\/ghc.html."},{"key":"e_1_2_1_36_1","unstructured":"Bruce James McAdam. 1998. On the unification of substitutions in type inference. In Implementation of Functional Languages. 139--154."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00049-9"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/575336"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/268998.266669"},{"key":"e_1_2_1_41_1","volume-title":"Java Information Flow. Software release, www.cs.cornell.edu\/jif. (July","author":"Myers Andrew C.","year":"2006","unstructured":"Andrew C. Myers, Lantian Zheng, Steve Zdancewic, Stephen Chong, and Nathaniel Nystrom. 2006. Jif 3.0: Java Information Flow. Software release, www.cs.cornell.edu\/jif. (July 2006)."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/548904"},{"key":"e_1_2_1_43_1","unstructured":"OCaml. 2016. OCaml programming language. Retrieved from http:\/\/ocaml.org."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1096-9942(199901\/03)5:1%3C35::AID-TAPO4%3E3.0.CO;2-4"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660193.2660230"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796806006034"},{"key":"e_1_2_1_47_1","volume-title":"Advanced Topics in Types and Programming Languages, Benjamin C","author":"Pottier Francois","unstructured":"Francois Pottier and Didier R\u00e9my. 2005. The essence of ML type inference. In Advanced Topics in Types and Programming Languages, Benjamin C. Pierce (Ed.). MIT Press, 389--489."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0950-5849(98)00093-7"},{"key":"e_1_2_1_50_1","unstructured":"SHErrLoc. 2014. SHErrLoc (Static Holistic Error Locator) Tool Release (ver 1.0). Retrieved from http:\/\/www.cs.cornell.edu\/projects\/sherrloc."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/237721.237727"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/366378.366379"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796811000098"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1708016.1708023"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/512644.512648"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.3233\/FI-1987-10202"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/2426890.2426894"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535838.2535870"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/2737924.2738009"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/1143844.1143983"}],"container-title":["ACM Transactions on Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3121137","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3121137","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3121137","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:39:24Z","timestamp":1750217964000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3121137"}},"subtitle":["A Static Holistic Error Locator"],"short-title":[],"issued":{"date-parts":[[2017,8,17]]},"references-count":53,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,12,31]]}},"alternative-id":["10.1145\/3121137"],"URL":"https:\/\/doi.org\/10.1145\/3121137","relation":{},"ISSN":["0164-0925","1558-4593"],"issn-type":[{"value":"0164-0925","type":"print"},{"value":"1558-4593","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,8,17]]},"assertion":[{"value":"2016-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-08-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}