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.*