{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,19]],"date-time":"2026-01-19T13:19:09Z","timestamp":1768828749185,"version":"3.49.0"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2017,12,27]],"date-time":"2017-12-27T00:00:00Z","timestamp":1514332800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003593","name":"CNPq","doi-asserted-by":"crossref","award":["0"],"award-info":[{"award-number":["0"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>Incomplete source code naturally emerges in software development: during the design phase, while evolving, testing and analyzing programs. Therefore, the ability to understand partial programs is a valuable asset. However, this problem is still unsolved in the C programming language. Difficulties stem from the fact that parsing C requires, not only syntax, but also semantic information. Furthermore, inferring types so that they respect C's type system is a challenging task. In this paper we present a technique that lets us solve these problems. We provide a unification-based type inference capable of dealing with C intricacies. The ideas we present let us reconstruct partial C programs into complete well-typed ones. Such program reconstruction has several applications: enabling static analysis tools in scenarios where software components may be absent; improving static analysis tools that do not rely on build-specifications; allowing stub-generation and testing tools to work on snippets; and assisting programmers on the extraction of reusable data-structures out of the program parts that use them. Our evaluation is performed on source code from a variety of C libraries such as GNU's Coreutils, GNULib, GNOME's GLib, and GDSL; on implementations from Sedgewick's books; and on snippets from popular open-source projects like CPython, FreeBSD, and Git.<\/jats:p>","DOI":"10.1145\/3158117","type":"journal-article","created":{"date-parts":[[2017,12,29]],"date-time":"2017-12-29T14:21:49Z","timestamp":1514557309000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Inference of static semantics for incomplete C programs"],"prefix":"10.1145","volume":"2","author":[{"given":"Leandro T. C.","family":"Melo","sequence":"first","affiliation":[{"name":"Federal University of Minas Gerais, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rodrigo G.","family":"Ribeiro","sequence":"additional","affiliation":[{"name":"Federal University of Ouro Preto, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcus R.","family":"de Ara\u00fajo","sequence":"additional","affiliation":[{"name":"Federal University of Minas Gerais, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fernando Magno Quint\u00e3o","family":"Pereira","sequence":"additional","affiliation":[{"name":"Federal University of Minas Gerais, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,12,27]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"ANSI-Standard. 1989. ANSI X3.159-1989 - The C Programming Language.  ANSI-Standard. 1989. ANSI X3.159-1989 - The C Programming Language."},{"key":"e_1_2_2_2_1","unstructured":"The GDSL Authors. 2017. The Generic Data Structures Library. http:\/\/home.gna.org\/gdsl\/ .  The GDSL Authors. 2017. The Generic Data Structures Library. http:\/\/home.gna.org\/gdsl\/ ."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2837614.2837637"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/157710.157795"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10817-009-9148-3"},{"key":"e_1_2_2_6_1","volume-title":"KLEE: Unassisted and Automatic Generation of High-coverage Tests for Complex Systems Programs. In OSDI. USENIX, 209\u2013224.","author":"Cadar Cristian","year":"2008"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1542476.1542483"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33826-7_16"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1449764.1449790"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3009837.3009882"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2103656.2103719"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/231379.231389"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796802004380"},{"key":"e_1_2_2_14_1","unstructured":"The Free Software Foundation. 2017. Gnulib - The GNU Portability Library. https:\/\/www.gnu.org\/software\/gnulib\/ .  The Free Software Foundation. 2017. Gnulib - The GNU Portability Library. https:\/\/www.gnu.org\/software\/gnulib\/ ."},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2568225.2568273"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065010.1065036"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2737924.2737979"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1111037.1111045"},{"key":"e_1_2_2_19_1","unstructured":"Runtime Verification Inc. 2017. RV-Match. https:\/\/runtimeverification.com\/match\/ .  Runtime Verification Inc. 2017. RV-Match. https:\/\/runtimeverification.com\/match\/ ."},{"key":"e_1_2_2_20_1","unstructured":"ISO-Standard. 1990. ISO\/IEC 9899:1990 - The C Programming Language.  ISO-Standard. 1990. ISO\/IEC 9899:1990 - The C Programming Language."},{"key":"e_1_2_2_21_1","unstructured":"ISO-Standard. 1999. ISO\/IEC 9899:1999 - The C Programming Language.  ISO-Standard. 1999. ISO\/IEC 9899:1999 - The C Programming Language."},{"key":"e_1_2_2_22_1","unstructured":"ISO-Standard. 2011. ISO\/IEC 9899:2011 - The C Programming Language.  ISO-Standard. 2011. ISO\/IEC 9899:2011 - The C Programming Language."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/141471.141540"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/WPC.1999.777750"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-024X(199706)27:6%3C637::AID-SPE99%3E3.0.CO;2-3"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2676724.2693571"},{"key":"e_1_2_2_28_1","volume-title":"USENIX Security Symposium","volume":"32","author":"Larochelle David","year":"2001"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/357084.357090"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/357162.357169"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2908080.2908081"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660193.2660205"},{"key":"e_1_2_2_33_1","volume-title":"Hanne Riis Nielson, and Chris Hankin","author":"Nielson Flemming","year":"2005"},{"key":"e_1_2_2_34_1","doi-asserted-by":"crossref","unstructured":"Kyndylan Nienhuis Kayvan Memarian and Peter Sewell. 2016. An operational semantics for C\/C++11 concurrency. In OOPSLA. 111\u2013128.  Kyndylan Nienhuis Kayvan Memarian and Peter Sewell. 2016. An operational semantics for C\/C++11 concurrency. In OOPSLA. 111\u2013128.","DOI":"10.1145\/3022671.2983997"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2908080.2908119"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00722-4_9"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0920-5489(01)00059-9"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2254064.2254098"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796803004787"},{"key":"e_1_2_2_41_1","volume-title":"ICFP","volume":"41","author":"Jones Simon Peyton","year":"2006"},{"key":"e_1_2_2_42_1","volume-title":"Advanced Topics in Types and Programming Languages, Benjamin C","author":"Pottier Fran\u00e7ois"},{"key":"e_1_2_2_43_1","unstructured":"The GNOME Project. 2017a. The GNOME Library - GLib. https:\/\/developer.gnome.org\/glib .  The GNOME Project. 2017a. The GNOME Library - GLib. https:\/\/developer.gnome.org\/glib ."},{"key":"e_1_2_2_44_1","unstructured":"The Qt Project. 2017b. The Qt Creator IDE. https:\/\/www.qt.io\/ide\/.  The Qt Project. 2017b. The Qt Creator IDE. https:\/\/www.qt.io\/ide\/."},{"key":"e_1_2_2_45_1","unstructured":"Didier R\u00e9my. 2013. Type Systems for Programming Languages.  Didier R\u00e9my. 2013. Type Systems for Programming Languages."},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/321250.321253"},{"key":"e_1_2_2_47_1","volume-title":"Fernando Magno Quintao Pereira, and Victor Hugo Sperle Campos","author":"Rodrigues Raphael Ernani","year":"2013"},{"key":"e_1_2_2_48_1","volume-title":"Algorithms in C","author":"Sedgewick Robert","edition":"3"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6423(94)00020-4"},{"key":"e_1_2_2_50_1","volume-title":"The Art of Prolog","author":"Sterling Leon","edition":"2"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-79124-9_10"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00590-9_1"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/11408901_21"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3158117","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3158117","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:11:30Z","timestamp":1750212690000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3158117"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,27]]},"references-count":51,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1145\/3158117"],"URL":"https:\/\/doi.org\/10.1145\/3158117","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,12,27]]},"assertion":[{"value":"2017-12-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}