Tail Call Elimination and Data Representation for Functional Languages on the Java Virtual Machine

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review


  • Magnus Madsen
  • Ramin Zarifi, University of Waterloo
  • ,
  • Ondrej Lhoták, University of Waterloo

The Java Virtual Machine (JVM) offers an attractive runtime environment for programming language implementors. The JVM has a simple bytecode format, excellent performance, multiple state-of-the art garbage collectors, robust backwards compatibility, and it runs on almost all platforms. Further, the Java ecosystem grants access to a plethora of libraries and tooling, including debuggers and profilers. Yet, the JVM was originally designed for Java, and its representation of code and data may cause difficulties for other languages. In this paper, we discuss how to efficiently implement functional languages on the JVM. We focus on two overall challenges: (a) how to efficiently represent algebraic data types in the presence of tags and tuples, option types, newtypes, and parametric polymorphism, and (b) how to support full tail call elimination on the JVM. We present two technical contributions: A fused representation of tags and tuples and a full tail call elimination strategy that is thread-safe. We implement these techniques in the Flix language and evaluate their performance.

Original languageEnglish
Title of host publicationCC 2018 - Proceedings of the 27th International Conference on Compiler Construction, Co-located with CGO 2018
EditorsJingling Xue, Christophe Dubach
Number of pages12
Place of publicationNew York, NY, USA
PublisherAssociation for Computing Machinery
Publication year24 Feb 2018
ISBN (print)978-1-4503-5644-2
ISBN (Electronic)9781450356442
Publication statusPublished - 24 Feb 2018
Externally publishedYes
EventInternational Conference on Compiler Construction - Vienna, Austria
Duration: 24 Feb 201825 Feb 2018
Conference number: 27


ConferenceInternational Conference on Compiler Construction
SeriesCC 2018

    Research areas

  • Java, Jvm, Tag tuple fusion, Tail call elimination

See relations at Aarhus University Citationformats

ID: 138357788