HaskellFL: A Tool for Detecting Logical Errors in Haskell

Authors: Vanessa Vasconcelos, Mariza A. S. Bigonha

Abstract:

Understanding and using the functional paradigm is a challenge for many programmers. Looking for logical errors in code may take a lot of a developer’s time when a program grows in size. In order to facilitate both processes, this paper presents HaskellFL, a tool that uses fault localization techniques to locate a logical error in Haskell code. The Haskell subset used in this work is sufficiently expressive for those studying Functional Programming to get immediate help debugging their code and to answer questions about key concepts associated with the functional paradigm. HaskellFL was tested against Functional Programming assignments submitted by students enrolled at the Functional Programming class at the Federal University of Minas Gerais and against exercises from the Exercism Haskell track that are publicly available in GitHub. This work also evaluated the effectiveness of two fault localization techniques, Tarantula and Ochiai, in the Haskell context. Furthermore, the EXAM score was chosen to evaluate the tool’s effectiveness, and results showed that HaskellFL reduced the effort needed to locate an error for all tested scenarios. The results also showed that the Ochiai method was more effective than Tarantula.

Keywords: Debug, fault localization, functional programming, Haskell.

References:

[1] Rui Abreu, Peter Zoeteweij, Rob Golsteijn, and Arjan JC Van Gemund. A practical evaluation of spectrum-based fault localization. Journal of Systems and Software, 82(11):1780–1792, 2009.
[2] Rui Abreu, Peter Zoeteweij, and Arjan JC Van Gemund. Spectrum-based multiple fault localization. In 2009 IEEE/ACM International Conference on Automated Software Engineering, pages 88–99. IEEE, 2009.
[3] Thomas Ball, Mayur Naik, and Sriram K Rajamani. From symptom to cause: localizing errors in counterexample traces. In ACM SIGPLAN Notices, volume 38, pages 97–105. ACM, 2003.
[4] Brett A Becker, Graham Glanville, Ricardo Iwashima, Claire McDonnell, Kyle Goslin, and Catherine Mooney. Effective compiler error message enhancement for novice programming students. Computer Science Education, 26(2-3):148–175, 2016.
[5] Richard Bird. Thinking functionally with Haskell. Cambridge University Press, 2014.
[6] Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth. Occam’s razor. Information processing letters, 24(6):377–380, 1987.
[7] Arthur Chargu´eraud. Improving type error messages in ocaml. Electronic Proceedings in Theoretical Computer Science, 198:80–97, Dec 2015.
[8] Ophelia C Chesley, Xiaoxia Ren, Barbara G Ryder, and Frank Tip. Crisp–a fault localization tool for java programs. In 29th International Conference on Software Engineering (ICSE’07), pages 775–779. IEEE, 2007.
[9] Valentin Dallmeier, Christian Lindig, and Andreas Zeller. Lightweight defect localization for java. In European conference on object-oriented programming, pages 528–550. Springer, 2005.
[10] Chris Done. Try haskell, November 2018. Online; accessed 21-November-2018.
[11] Joao Fernandes. Generalized lr parsing in haskell. Informal Proceedings of the Summer School on Advanced Functional Programming, students’ presentation, pages 24–37, 2004.
[12] F# Software Foundation. About f#, January 2021. Online; accessed 06-January-2021.
[13] Kotlin Foundation. Learn kotlin, January 2021. Online; accessed 06-January-2021.
[14] Alex Gerdes, Bastiaan Heeren, Johan Jeuring, and L Thomas van Binsbergen. Ask-elle: an adaptable programming tutor for haskell giving automated feedback. International Journal of Artificial Intelligence in Education, 27(1):65–100, 2017.
[15] Rahul Gopinath, Carlos Jensen, and Alex Groce. Mutations: How close are they to real faults? In 2014 IEEE 25th International Symposium on Software Reliability Engineering, pages 189–200. IEEE, 2014.
[16] Alex Groce, Sagar Chaki, Daniel Kroening, and Ofer Strichman. Error explanation with distance metrics. International Journal on Software Tools for Technology Transfer, 8(3):229–247, 2006.
[17] Martin Handley and Graham Hutton. Improving haskell. In Michal H. Palka and Magnus O. Myreen, editors, Trends in Functional Programming - 19th International Symposium, TFP 2018, volume 11457 of Lecture Notes in Computer Science, pages 114–135, Gothenburg, Sweden, June 11-13, 2018. Springer.
[18] Bastiaan Heeren, Daan Leijen, and Arjan van IJzendoorn. Helium, for learning haskell. In Proceedings HW03: Haskell Workshop 2003, pages 62–71, Co-Located with ICFP 2003 and PPDP 2003 Conferences) Uppsala, Sweden August, 2003. ACM.
[19] Bastiaan J Heeren. Top quality type error messages. Utrecht University, 2005.
[20] Tim AD Henderson. How to evaluate statistical fault localization. 2018.
[21] James A Jones and Mary Jean Harrold. Empirical evaluation of the tarantula automatic fault-localization technique. In Proceedings of the 20th IEEE/ACM international Conference on Automated software engineering, pages 273–282, 2005.
[22] James A Jones, Mary Jean Harrold, and John Stasko. Visualization of test information to assist fault localization. In Software Engineering, 2002. ICSE 2002. Proceedings of the 24rd International Conference on, pages 467–477. IEEE, 2002.
[23] SL Peyton Jones, Cordy Hall, Kevin Hammond, Will Partain, and Philip Wadler. The glasgow haskell compiler: a technical overview. In Proc. UK Joint Framework for Information Technology (JFIT) Technical Conference, volume 93, 1993.
[24] Manu Jose and Rupak Majumdar. Cause clue clauses: error localization using maximum satisfiability. ACM SIGPLAN Notices, 46(6):437–446, 2011.
[25] Ren´e Just, Darioush Jalali, and Michael D Ernst. Defects4j: A database of existing faults to enable controlled testing studies for java programs. In Proceedings of the 2014 International Symposium on Software Testing and Analysis, pages 437–440, 2014.
[26] Etienne Kneuss, Manos Koukoutos, and Viktor Kuncak. Deductive program repair. In Lecture Notes in Computer Science, 9207, 217-233. Presented at: 27th International Conference on Computer-Aided Verificationn, pages 217–233, San Francisco, CA, USA, July 18-24, 2015. Springer.
[27] Duc Le, Mohammad Amin Alipour, Rahul Gopinath, and Alex Groce. Mucheck: An extensible tool for mutation testing of haskell programs. In Proceedings of the 2014 international symposium on software testing and analysis, pages 429–432, 2014.
[28] Duc Le, Mohammad Amin Alipour, Rahul Gopinath, and Alex Groce. Mutation testing of functional programming languages. Oregon State University, Tech. Rep, 2014.
[29] Junho Lee, Dowon Song, Sunbeom So, and Hakjoo Oh. Automatic diagnosis and correction of logical errors for functional programming assignments. Proceedings of the ACM on Programming Languages, 2(OOPSLA):158, 2018.
[30] Zijie Li, Long Zhang, Zhenyu Zhang, and Bo Jiang. Mcfl: Improving fault localization by differentiating missing code and other faults. In 2020 IEEE 44th Annual Computers, Software, and Applications Conference (COMPSAC), pages 943–952. IEEE, 2020.
[31] Hai Liu, Neal Glew, Leaf Petersen, and Todd A Anderson. The intel labs haskell research compiler. In ACM SIGPLAN Notices, volume 48, pages 105–116. ACM, 2013.
[32] Lee Naish, Hua Jie Lee, and Kotagiri Ramamohanarao. A model for spectra-based software diagnosis. ACM Transactions on software engineering and methodology (TOSEM), 20(3):1–32, 2011.
[33] Redac¸ ˜ao Nubank. O que ´e clojure? o que isso tem a ver com o nubank?, January 2021. Online; accessed 06-January-2021.
[34] OCaml. Ocaml, November 2018. Online; accessed 21-November-2018.
[35] Mike Papadakis and Yves Le Traon. Metallaxis-fl: mutation-based fault localization. Software Testing, Verification and Reliability, 25(5-7):605–628, 2015.
[36] Spencer Pearson, Jos´e Campos, Ren´e Just, Gordon Fraser, Rui Abreu, Michael D Ernst, Deric Pang, and Benjamin Keller. Evaluating & improving fault localization techniques. University of Washington Department of Computer Science and Engineering, Seattle, WA, USA, Tech. Rep. UW-CSE-16-08-03, 2016.
[37] Simon L Peyton Jones. The implementation of functional programming languages (prentice-hall international series in computer science). Prentice-Hall, Inc., 1987.
[38] Iustin Pop. Experience report: Haskell as a reagent. In ACM SIGPLAN International Conference on Funtional Programming. Citeseer, 2010.
[39] Ranjith Purushothaman and Dewayne E Perry. Toward understanding the rhetoric of small source code changes. IEEE Transactions on Software Engineering, 31(6):511–526, 2005.
[40] Peifeng Rao, Zheng Zheng, Tsong Yueh Chen, Nan Wang, and Kaiyuan Cai. Impacts of test suite’s class imbalance on spectrum-based fault localization techniques. In 2013 13th International Conference on Quality Software, pages 260–267. IEEE, 2013.
[41] Georgios Sakkas, Madeline Endres, Benjamin Cosman, Westley Weimer, and Ranjit Jhala. Type error feedback via analytic program repair. In Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation, pages 16–30, 2020.
[42] Jeremy Singer and Blair Archibald. Functional baby talk: Analysis of code fragments from novice haskell programmers. arXiv preprint arXiv:1805.05126, 2018.
[43] George Thompson and Allison K Sullivan. Profl: a fault localization framework for prolog. In Proceedings of the 29th ACM SIGSOFT International Symposium on Software Testing and Analysis, pages 561–564, 2020.
[44] S. Thompson. Haskell: The Craft of Functional Programming. Icss Series. Addison Wesley, 2011.
[45] Anish Tondwalkar. Finding and Fixing Bugs in Liquid Haskell. PhD thesis, University of Virginia, 2016.
[46] Haskell Wiki. The haskell programming language, November 2018. Online; accessed 21-November-2018.
[47] Eric Wong, Tingting Wei, Yu Qi, and Lei Zhao. A crosstab-based statistical method for effective fault localization. In 2008 1st international conference on software testing, verification, and validation, pages 42–51. IEEE, 2008.
[48] W Eric Wong, Vidroha Debroy, Ruizhi Gao, and Yihao Li. The dstar method for effective software fault localization. IEEE Transactions on Reliability, 63(1):290–308, 2013.
[49] W Eric Wong, Ruizhi Gao, Yihao Li, Rui Abreu, and Franz Wotawa. A survey on software fault localization. IEEE Transactions on Software Engineering, 42(8):707–740, 2016.
[50] Danfeng Zhang, Andrew C Myers, Dimitrios Vytiniotis, and Simon Peyton-Jones. Diagnosing haskell type errors. Technical report, Technical Report http://hdl. handle. net/1813/39907, Cornell University, 2015.