Thesis Details
Just-in-Time Compilation of Dependently-Typed Lambda Calculus
A number of programming languages have managed to greatly improve their performance by replacing their custom runtime system with general platforms that use just-in-time optimizing compilers like GraalVM or RPython. This thesis evaluates whether such a transition would also benefit dependently-typed programming languages or theorem provers.
This thesis introduces the type-theoretic notion of dependent types and the algorithms involved in working with them, specifies a minimal dependently-typed language on the -calculus, and presents the implementation two interpreters for this language: a simple interpreter written in Kotlin, and a second interpreter, also written in Kotlin, that uses the Truffle language implementation framework on the GraalVM platform, which is a partial evaluation-based just-in-time compiler based on the Java Virtual Machine. The performance of these two interpreters is then compared on a number of normalization and elaboration tasks.The results are strongly negative, however, the influence of JIT compilation is not noticeable given the large overhead of the JVM platform. This thesis concludes with a number of alternative projects that would use the capabilities of Truffle better.
Truffle, Java Virtual Machine, just-in-time compilation, compiler construction, dependent types
Hradiš Michal, Ing., Ph.D. (DCGM FIT BUT), člen
Janoušek Vladimír, doc. Ing., Ph.D. (DITS FIT BUT), člen
Peringer Petr, Dr. Ing. (DITS FIT BUT), člen
Smrčka Aleš, Ing., Ph.D. (DITS FIT BUT), člen
@mastersthesis{FITMT24198,
author = "Jakub Z\'{a}rybnick\'{y}",
type = "Master's thesis",
title = "Just-in-Time Compilation of Dependently-Typed Lambda Calculus",
school = "Brno University of Technology, Faculty of Information Technology",
year = 2021,
location = "Brno, CZ",
language = "english",
url = "https://www.fit.vut.cz/study/thesis/24198/"
}