# Introduction This artifact accompanies the PLDI 2026 submission "Virtualized Continuation". It is built on top of the existing Lexa language compiler, with support for an alternative compilation strategy using "virtual handler IDs" for more expressivity in multishot resumptions with small overhead. We refer to the original Lexa compiler as *Base Lexa* and the new compiler as *Multi Lexa*. Programmers can specify whether to use the Base Lexa or Multi Lexa compiler using a compiler flag. The compiler implementation consists of the following components: - **Compiler Driver**: `lexa` is the main entry point for the compiler, which orchestrates the compilation process. - **Frontend**: The frontend typechecks the source code and translates it into C. This is implemented in OCaml and is located in `./src/sl`, `./src/lib`, and `./src/bin`. - **Backend**: Clang is used to compile the generated C code into an executable. Several LLVM passes are used during this process, and they are located in `./passes`. - **Runtime**: The semantics of effect handlers are implemented via stack switching, using assembly trampolines defined in `./src/stacktrek/stacktrek.h` (described in detail in a prior OOPSLA'24 publication). The changes made for the new Multi Lexa strategy are contained in `./src/stacktrek/stacktrek.h` and `./src/stacktrek/stack_pool.h`. ## Claims We made the following claims in the PLDI 2026 submission: ### Claim 1 > For benchmarks that Base Lexa can handle, Multi Lexa introduces only small overhead compared to Base Lexa. ### Claim 2 > For benchmarks where multishot resumptions are embarrassingly parallel, Multi Lexa enables significant speedups by enabling the parallel execution of multishot resumptions. # Hardware Dependencies * Supported platform: x86-64 (ARM is not supported) * 16GB of RAM & 4 CPU cores (or more) * Linux operating system # Getting Started (30 min) 1. **Run Docker Container**: - Install Docker on your system. - `docker pull hflsmax/lexa-lang:PLDI26`: Pull the Docker image. - **alternatively, download the image tar from Zenodo and load it**: `docker load -i ./lexa-PLDI26.tar`: - `docker run -it hflsmax/lexa-lang:PLDI26`: Run the container interactively. 2. **Do a Quick Run**: - `cd /WorkDir/scripts; python bench.py --systems lexa lexam --benchmarks product_early --quick`: Build and bench a single benchmark program. - `cat ./runtimes.csv`: Check the results in `runtimes.csv`. - You should see something like this: ``` bash-5.2# cat runtimes.csv ,mean_mili,mean_mili,std_mili,std_mili platform,lexa,lexam,lexa,lexam benchmark,,,, product_early,100.0,100.0,1.0,2.0 ``` # Step-by-Step Instructions (30 min) 1. **Set up the environment**: Repeat the steps from the "Getting Started" section to run the Docker container. 2. **Reproduce Claim 1**: - `cd /WorkDir/scripts/PLDI26; python table.py --singleshot-benchmarks --multishot-benchmarks --overhead --extra-systems effekt koka_named`: Run all benchmarks present in table 1. - `cat ./table.csv`: Check the results in `table.csv`. - The overhead column (fourth column) should roughly match the one in Table 1. Most overhead should be near 0%, and the ones deviating from 0% have explanations in the paper. 3. **Reproduce Claim 2**: - `cd /WorkDir/scripts/PLDI26; python table_parallel.py`: Run the sequential and parallel benchmarks in Table 2. - `cat ./table_parallel.csv`: Check the results in `table_parallel.csv`. - The table should show a notable speedup for the parallel setting (third column) compared to the sequential setting (second column). # Reusability Guide (30 min) Reusing this artifact means that you can use the Lexa compiler to compile code that you write. The surface syntax of Lexa should be familiar to programmers who have experience with functional programming languages such as OCaml or Koka. To get familiar with Lexa, we recommend studying the following two short programs. For each example, we highlight the relevant syntax. - `/WorkDir/test/lexa_snippets/flip/flip.lx`: A benchmark program that uses a multishot handler to simulate flipping a coin. - Line 1: the effect is declared using the `effect` keyword. - Line 15: the handler is defined using the `hdl_s` keyword, signifying that it is a multishot handler. The extra parameter `k` is the resumption representing the rest of the computation after raising the effect. - Line 16, 17: the resumption is invoked *twice*: first using the `resume` keyword, which creates a copy of the resumption before jumping into it; then using the `resume_final` keyword, which *destructively* invokes the resumption without copying. - `/WorkDir/test/lexa_snippets/flip_parallel/flip_parallel.lx`: A benchmark program that simulates flipping a coin *in parallel*. - Line 16: the `par-val` expression is used to invoke the same resumption in two different threads. The expression ``` par-val x = e1, y = e2; ``` evaluates `e1` and `e2` in parallel, binding their results to `x` and `y`, respectively. ### Compiling and Running the Sample Code To compile and run a Lexa program: - `lexa /WorkDir/test/lexa_snippets/flip_parallel/flip_parallel.lx -o main --multi --pthread` - `./main` ### Writing Your Own Code We now invite you to write your own Lexa code. Your goal is to examine and rewrite the program `flip_bool`, located at `/WorkDir/test/lexa_snippets/flip_bool/flip_bool.lx`, which uses multishot resumption to count the number of truth assignments that satisfy `predicate`. Rewrite the code so that the resumptions are invoked in parallel. We provide a sample solution `solution.lx` under the same directory. Follow these steps to write and compile your own Lexa code: 1. **Write your code**: - The Docker image has `vim` and `emacs` installed. - `cd /WorkDir/test/lexa_snippets/flip_bool`: Navigate to the code snippet directory. - `vim flip_bool.lx`: Edit `flip_bool.lx`. *Hint: Do not use `resume_final` to resume destructively, as it can introduce race conditions between parallel branches.* 2. **Compile your code**: - `lexa flip_bool.lx -o main --multi --pthread`: This will compile your code `flip_bool.lx` into an executable named `main`. 3. **Run your code**: - `./main`: This will run your compiled code. If your code is correct, you should see the result `2`. 4. **Check sample solution**: - `cat solution.lx`: Check the sample solution provided. You can compare it with your code to see if there are any differences.