The Effekt Compiler

This page gives a brief overview of the Effekt compiler and points you to the research behind it.

Reading one of our papers? Effekt has changed since many of our papers were published. Please see Language Evolution for the differences to each paper. All of our papers, including those on compiling Effekt, are listed on the Research Papers page.

Compiler Pipeline

The compiler pipeline for Effekt, at the time of writing, can be illustrated as follows:

The compilation is divided into the following large phases: parsing, frontend, middleend and backend. As you can see, Effekt supports multiple backends. While the steps in the frontend phase are shared for all backends, some of the middleend steps are specific to some backends.

The source code modeling the pipeline can be found in Compiler.scala.

In the following, we briefly describe the different phases.

Parsing

The first step is to parse the given Effekt program into an AST called Source.

Frontend

On Source there are several steps carried out, mainly:

• Name Resolution
• Typechecking
• Translation to Capability-Passing Style

The ideas behind effects as capabilities are described in our papers on language design.

Middleend

Subsequently, the Source IR is translated step-by-step to different IRs:

• The first translation is to an IR in fine-grain call-by-value, called Core, which corresponds to System Xi in this paper and System C in this paper. Note that Core has changed since these papers, see Language Evolution for details.
• Then we do many optimization passes on Core itself, for example monomorphization (see The Simple Essence of Monomorphization in General Compilation Techniques).
• For the JavaScript backends and the chez-cps backend, we translate Core to an IR in continuation-passing style, called CPS.
• For the LLVM backend, we translate Core to a more low-level IR called Machine, described in Multiple Resumptions and Local Mutable State, Directly (see Compilation of Effect Handlers).

Backend

The final step is the translation to the corresponding backend language. The different backends are targeted from different IRs:

• From Core there are translations to Chez Scheme (the backends chez-callcc and chez-monadic).
• From CPS there are translations to JavaScript (the backends js and js-web) and to Chez Scheme (the backend chez-cps).
• From Machine there is a translation to LLVM (the backend llvm).

Further Reading

• Language Evolution summarizes how Effekt has changed since each of our papers.
• Research Papers lists our papers, including those on compiling effect handlers and on general compilation techniques.
• Lift Inference describes the implementation strategy that Effekt used before version 0.4.0.
• Contributing explains how to build the compiler and how to work on it.