ISBN: 978-981-11-3671-9 DOI: 10.18178/wcse.2017.06.037
An analysis of computer programs using λ-calculus
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.