WCSE 2017
ISBN: 978-981-11-3671-9 DOI: 10.18178/wcse.2017.06.037

An analysis of computer programs using λ-calculus

Kittiphon Phalakarn, Athasit Surarerks

Abstract— We propose that λ-calculus can be a mathematical model for analysing programs. The λ-calculus representation in this work includes numbers, Booleans, arithmetic operations, lists, functions, recursions, and loops. Moreover, we discuss whether a program can have a representation using simply typed λ-calculus. Since simply typed λ-calculus is not Turing complete, only some portions of a program can be represented. The automated λ-term evaluation process using its expression tree is also studied. For λ-term analysis, we propose an algorithm to maximize the number of parallel β-reductions done in each step, and review some literatures on methods to understand the semantics and flows of programs using their λ-terms. We believe that our results can be useful for analysing how a program can perform in parallel manner.

Index Terms— analysis of computer programs, lambda calculus, simply typed lambda calculus, parallel

Kittiphon Phalakarn, Athasit Surarerks
Department of Computer Engineering, Faculty of Engineering, Chulalongkorn University, THAILAND


Cite: Kittiphon Phalakarn, Athasit Surarerks, "An analysis of computer programs using λ-calculus," Proceedings of 2017 the 7th International Workshop on Computer Science and Engineering, pp. 214-218, Beijing, 25-27 June, 2017.