2. Basic Interpreter

To use truffle in your project, you need to install GraalVM. You can download it from the official website or use the following command to install it using SDKMAN:

sdk install java 21-graalce
sdk use java 21-graalce

And then define the following dependencies in your pom.xml file:

<dependency>
    <groupId>org.graalvm.truffle</groupId>
    <artifactId>truffle-api</artifactId>
    <version>24.0.2</version> <!-- or any later version -->
</dependency>
<dependency>
    <groupId>org.graalvm.truffle</groupId>
    <artifactId>truffle-dsl-processor</artifactId>
    <version>24.0.2</version>
    <scope>provided</scope>
</dependency>

Truffle provides two ways to define a language: AST-based and Bytecode-based. In this article, we will focus on the AST-based approach and build an interpreter for a functional language called Nix. The AST-based approach is more flexible and easier to use, while the Bytecode-based approach is more efficient. GraalPy, TruffleRuby, and GraalJS are examples of languages that use the AST-based approach. You can go to their GitHub repositories to see how they are implemented when you are stuck.

I assume you have some knowledge of compilation principles and how interpreters work, since we are going to build an interpreter. If you don’t, I recommend reading the Crafting Interpreters book. You can safely skip the parts about the scanning (lexing), parsing, and optimization, since Truffle will take care of them for you.

A node in the Truffle Abstract Syntax Tree (AST) must extend the Node class from the com.oracle.truffle.api.nodes package. It’s an abstract class, you can define your own methods in your node classes. As a convention, we define methods that start with execute to define the behavior of the node. The execute methods usually receive a VirtualFrame object as its first parameter, which is used to access the variables in the current scope. The execute methods can return any type of object, but it’s recommended to return the truffle primitive types, such as int, long, double, boolean, and TruffleObject.

Let’s start by defining a simple language that can add two numbers. We will define a node for each operation: IntLiteralNode, AddNode.

import com.oracle.truffle.api.frame.VirtualFrame;
import com.oracle.truffle.api.nodes.Node;
 
public abstract class NixNode extends Node {
    public abstract int executeInt(VirtualFrame frame);
}

import com.oracle.truffle.api.frame.VirtualFrame;
 
public final class IntLiteralNode extends NixNode {
    private final int value;
 
    public IntLiteralNode(int value) {
        this.value = value;
    }
 
    @Override
    public int executeInt(VirtualFrame frame) {
        return this.value;
    }
}

import com.oracle.truffle.api.frame.VirtualFrame;
 
public final class AddNode extends NixNode {
    @Child private NixNode left;
    @Child private NixNode right;
 
    public AddNode(NixNode left, NixNode right) {
        this.left = left;
        this.right = right;
    }
 
    @Override
    public int executeInt(VirtualFrame frame) {
        return left.executeInt(frame) + right.executeInt(frame);
    }
}

The Node in Truffle is a bidirectional tree, which means that you can access the parent node from a child node. @Child is an annotation that tells Truffle that the field is a child node. Truffle will take care of the parent-child relationships for you.

@Child and @CompilationFinal

Interestingly, the NixNode fields are not final, it’s because Truffle needs to rewrite parts of the AST to optimize the execution. Instead, @Child annotation derives another annotation called @CompilationFinal, which is used to mark fields should be considered as final during the compilation. You can mark @CompilationFinal on a field if you are sure that the field won’t (or extremely rare) change during the execution. @CompilationFinal has a parameter called dimensions, which is used to specify how many dimensions of the array should be considered as final. For example, if you have a field that is an array of arrays, you can mark @CompilationFinal(dimensions = 1) to tell Truffle that the outer array is final, but the inner arrays are not. For node arrays, you can mark @Children annotation instead of @Child to tell Truffle that the field is an array of child nodes, which derives @CompilationFinal(dimensions = 1).

If you need to change the value of a @CompilationFinal field, you should always call CompilerDirectives.transferToInterpreterAndInvalidate() to invalidate the compiled code that caches the value, and Truffle will recompile the code with the new value automatically.

After we construct the AST, we need to create a RootNode that represents the entry point of an AST. The RootNode is a special node that doesn’t have a parent node. It’s used to start the execution of the AST.

import com.oracle.truffle.api.frame.VirtualFrame;
import com.oracle.truffle.api.nodes.RootNode;
 
public final class NixRootNode extends RootNode {
  @Child private NixNode rootNode;
 
  public NixRootNode(NixNode rootNode) {
    super(null);
    this.rootNode = rootNode;
  }
 
  @Override
  public Object execute(VirtualFrame frame) {
    return this.rootNode.executeInt(frame);
  }
}

RootNode is the minimal unit of compilation in Truffle, but with sufficient budget, Truffle can inline a RootNode into another RootNode to optimize the execution.

RootNode.execute should never be called directly, instead, you should call RootNode.getCallTarget() and CallTarget.call(Object...) to execute it. CallTarget is a wrapper for the target of a “call”. This indirection allows Truffle to profile the call and optimize it.

import com.oracle.truffle.api.Truffle;
 
public class Main {
    public static void main(String[] args) {
        NixNode rootNode = new AddNode(new IntLiteralNode(1), new IntLiteralNode(2));
        NixRootNode root = new NixRootNode(rootNode);
        CallTarget callTarget = root.getCallTarget();
        System.out.println(callTarget.call());
    }
}