Building a Domain-Specific Language with Truffle in Java

Truffle is a powerful framework for building self-optimizing interpreters and languages on the Java Virtual Machine. This guide covers how to create your own DSL using Truffle, leveraging its AST interpretation and just-in-time compilation capabilities.

Truffle Architecture Overview

Core Concepts

Truffle Language API: Framework for language implementation
AST Interpreters: Tree-based execution with specialization
Graal Compiler: JIT compiler that optimizes Truffle ASTs
Polyglot Integration: Interoperability between languages

Project Setup

<!-- pom.xml -->
<dependencies>
<dependency>
<groupId>org.graalvm.truffle</groupId>
<artifactId>truffle-api</artifactId>
<version>23.0.0</version>
</dependency>
<dependency>
<groupId>org.graalvm.truffle</groupId>
<artifactId>truffle-dsl-processor</artifactId>
<version>23.0.0</version>
<scope>provided</scope>
</dependency>
</dependencies>

Building a Simple Calculator DSL

1. Language Foundation

// Main language class
@TruffleLanguage.Registration(
id = "calc",
name = "Calculator DSL",
defaultMimeType = "application/x-calc",
characterMimeTypes = "application/x-calc",
contextPolicy = TruffleLanguage.ContextPolicy.SHARED
)
public class CalcLanguage extends TruffleLanguage<CalcContext> {
@Override
protected CalcContext createContext(Env env) {
return new CalcContext();
}
@Override
protected CallTarget parse(ParsingRequest request) throws Exception {
Source source = request.getSource();
CalcParser parser = new CalcParser();
CalcNode expr = parser.parse(source.getCharacters().toString());
return Truffle.getRuntime().createCallTarget(expr);
}
@Override
protected Object getScope(CalcContext context) {
return context.getGlobalScope();
}
}
// Language context
public class CalcContext {
private final Object globalScope;
public CalcContext() {
this.globalScope = new Object();
}
public Object getGlobalScope() {
return globalScope;
}
}

2. Base AST Node Classes

// Base node class
public abstract class CalcNode extends Node {
public abstract Object execute(VirtualFrame frame);
// Helper method for numeric operations
protected Number ensureNumber(Object value) {
if (value instanceof Number) {
return (Number) value;
}
throw new CalcTypeError("Expected number, got: " + value);
}
protected long ensureLong(Object value) {
Number number = ensureNumber(value);
return number.longValue();
}
protected double ensureDouble(Object value) {
Number number = ensureNumber(value);
return number.doubleValue();
}
}
// Node for literal values
public class LiteralNode extends CalcNode {
private final Object value;
public LiteralNode(Object value) {
this.value = value;
}
@Override
public Object execute(VirtualFrame frame) {
return value;
}
}

Implementing Expressions with Specialization

3. Arithmetic Operations with Specialization

// Addition operation with specialization
public abstract class AddNode extends CalcNode {
@Specialization(rewriteOn = ArithmeticException.class)
protected long addLong(long left, long right) {
return Math.addExact(left, right);
}
@Specialization(replaces = "addLong")
protected double addDouble(double left, double right) {
return left + right;
}
@Specialization(guards = {"isString(left)", "isString(right)"})
protected String addString(String left, String right) {
return left + right;
}
@Fallback
protected Object addGeneric(Object left, Object right) {
return String.valueOf(left) + String.valueOf(right);
}
protected static boolean isString(Object value) {
return value instanceof String;
}
// Factory method
public static AddNode create() {
return AddNodeGen.create();
}
}
// Subtraction operation
public abstract class SubtractNode extends CalcNode {
@Specialization(rewriteOn = ArithmeticException.class)
protected long subLong(long left, long right) {
return Math.subtractExact(left, right);
}
@Specialization(replaces = "subLong")
protected double subDouble(double left, double right) {
return left - right;
}
@Fallback
protected Object subGeneric(Object left, Object right) {
throw new CalcTypeError("Cannot subtract: " + left + " - " + right);
}
public static SubtractNode create() {
return SubtractNodeGen.create();
}
}

4. Comparison Operations

// Less than comparison
public abstract class LessThanNode extends CalcNode {
@Specialization
protected boolean compareLong(long left, long right) {
return left < right;
}
@Specialization
protected boolean compareDouble(double left, double right) {
return left < right;
}
@Specialization(guards = {"isString(left)", "isString(right)"})
protected boolean compareString(String left, String right) {
return left.compareTo(right) < 0;
}
@Fallback
protected boolean compareGeneric(Object left, Object right) {
throw new CalcTypeError("Cannot compare: " + left + " < " + right);
}
public static LessThanNode create() {
return LessThanNodeGen.create();
}
}

Control Flow and Variables

5. Variable Support

// Variable read node
public abstract class ReadVariableNode extends CalcNode {
private final String name;
public ReadVariableNode(String name) {
this.name = name;
}
@Specialization
protected Object readVariable(VirtualFrame frame) {
Object[] args = frame.getArguments();
if (args.length > 0 && args[0] instanceof CalcContext) {
CalcContext context = (CalcContext) args[0];
// Look up in context - simplified
return context.getGlobalScope();
}
throw new CalcRuntimeError("Variable not found: " + name);
}
public static ReadVariableNode create(String name) {
return ReadVariableNodeGen.create(name);
}
}
// Variable assignment node
public abstract class AssignVariableNode extends CalcNode {
private final String name;
@Child private CalcNode valueNode;
public AssignVariableNode(String name, CalcNode valueNode) {
this.name = name;
this.valueNode = valueNode;
}
@Specialization
protected Object assign(VirtualFrame frame, Object value) {
// Store in context - simplified implementation
System.out.println("Assigning " + name + " = " + value);
return value;
}
@Override
public Object execute(VirtualFrame frame) {
Object value = valueNode.execute(frame);
return assign(frame, value);
}
public static AssignVariableNode create(String name, CalcNode valueNode) {
return AssignVariableNodeGen.create(name, valueNode);
}
}

6. Control Flow Structures

// If-else statement
public class IfNode extends CalcNode {
@Child private CalcNode condition;
@Child private CalcNode thenBranch;
@Child private CalcNode elseBranch;
public IfNode(CalcNode condition, CalcNode thenBranch, CalcNode elseBranch) {
this.condition = condition;
this.thenBranch = thenBranch;
this.elseBranch = elseBranch;
}
@Override
public Object execute(VirtualFrame frame) {
Object condValue = condition.execute(frame);
if (isTrue(condValue)) {
return thenBranch != null ? thenBranch.execute(frame) : null;
} else {
return elseBranch != null ? elseBranch.execute(frame) : null;
}
}
private boolean isTrue(Object value) {
if (value instanceof Boolean) {
return (Boolean) value;
}
if (value instanceof Number) {
return ((Number) value).doubleValue() != 0.0;
}
return value != null;
}
}
// While loop
public class WhileNode extends CalcNode {
@Child private CalcNode condition;
@Child private CalcNode body;
public WhileNode(CalcNode condition, CalcNode body) {
this.condition = condition;
this.body = body;
}
@Override
public Object execute(VirtualFrame frame) {
Object lastResult = null;
while (isTrue(condition.execute(frame))) {
lastResult = body.execute(frame);
// Allow loop termination
if (Thread.currentThread().isInterrupted()) {
break;
}
}
return lastResult;
}
private boolean isTrue(Object value) {
// Same implementation as in IfNode
return value instanceof Boolean ? (Boolean) value : 
value instanceof Number ? ((Number) value).doubleValue() != 0.0 : 
value != null;
}
}

Parser Implementation

7. Recursive Descent Parser

public class CalcParser {
private String input;
private int position;
private char currentChar;
public CalcNode parse(String input) {
this.input = input;
this.position = 0;
this.currentChar = input.length() > 0 ? input.charAt(0) : '\0';
return parseExpression();
}
private void advance() {
position++;
currentChar = position < input.length() ? input.charAt(position) : '\0';
}
private void skipWhitespace() {
while (currentChar != '\0' && Character.isWhitespace(currentChar)) {
advance();
}
}
private CalcNode parseExpression() {
return parseComparison();
}
private CalcNode parseComparison() {
CalcNode node = parseAddition();
while (true) {
skipWhitespace();
if (currentChar == '<') {
advance();
CalcNode right = parseAddition();
node = LessThanNode.create(node, right);
} else {
break;
}
}
return node;
}
private CalcNode parseAddition() {
CalcNode node = parseMultiplication();
while (true) {
skipWhitespace();
if (currentChar == '+') {
advance();
CalcNode right = parseMultiplication();
node = AddNode.create(node, right);
} else if (currentChar == '-') {
advance();
CalcNode right = parseMultiplication();
node = SubtractNode.create(node, right);
} else {
break;
}
}
return node;
}
private CalcNode parseMultiplication() {
CalcNode node = parsePrimary();
while (true) {
skipWhitespace();
if (currentChar == '*') {
advance();
CalcNode right = parsePrimary();
node = MultiplyNode.create(node, right);
} else if (currentChar == '/') {
advance();
CalcNode right = parsePrimary();
node = DivideNode.create(node, right);
} else {
break;
}
}
return node;
}
private CalcNode parsePrimary() {
skipWhitespace();
if (Character.isDigit(currentChar)) {
return parseNumber();
} else if (currentChar == '(') {
advance(); // consume '('
CalcNode node = parseExpression();
skipWhitespace();
if (currentChar == ')') {
advance(); // consume ')'
} else {
throw new ParseError("Expected ')'");
}
return node;
} else if (Character.isLetter(currentChar)) {
return parseIdentifier();
} else {
throw new ParseError("Unexpected character: " + currentChar);
}
}
private CalcNode parseNumber() {
StringBuilder sb = new StringBuilder();
boolean hasDecimal = false;
while (currentChar != '\0' && 
(Character.isDigit(currentChar) || currentChar == '.')) {
if (currentChar == '.') {
if (hasDecimal) break;
hasDecimal = true;
}
sb.append(currentChar);
advance();
}
String numberStr = sb.toString();
if (hasDecimal) {
return new LiteralNode(Double.parseDouble(numberStr));
} else {
return new LiteralNode(Long.parseLong(numberStr));
}
}
private CalcNode parseIdentifier() {
StringBuilder sb = new StringBuilder();
while (currentChar != '\0' && 
(Character.isLetterOrDigit(currentChar) || currentChar == '_')) {
sb.append(currentChar);
advance();
}
String identifier = sb.toString();
// Check for keywords
if ("if".equals(identifier)) {
return parseIfStatement();
} else {
// Assume it's a variable
return ReadVariableNode.create(identifier);
}
}
private CalcNode parseIfStatement() {
skipWhitespace();
if (currentChar != '(') {
throw new ParseError("Expected '(' after 'if'");
}
advance(); // consume '('
CalcNode condition = parseExpression();
skipWhitespace();
if (currentChar != ')') {
throw new ParseError("Expected ')' after if condition");
}
advance(); // consume ')'
CalcNode thenBranch = parseExpression();
CalcNode elseBranch = null;
skipWhitespace();
if (position + 3 <= input.length() && 
input.substring(position, position + 4).equals("else")) {
position += 4;
currentChar = position < input.length() ? input.charAt(position) : '\0';
elseBranch = parseExpression();
}
return new IfNode(condition, thenBranch, elseBranch);
}
}

Advanced Features

8. Function Support

// Function call node
public abstract class FunctionCallNode extends CalcNode {
private final String functionName;
@Children private final CalcNode[] argumentNodes;
public FunctionCallNode(String functionName, CalcNode[] argumentNodes) {
this.functionName = functionName;
this.argumentNodes = argumentNodes;
}
@Specialization
protected Object callFunction(VirtualFrame frame) {
Object[] args = new Object[argumentNodes.length];
for (int i = 0; i < argumentNodes.length; i++) {
args[i] = argumentNodes[i].execute(frame);
}
// Built-in functions
switch (functionName) {
case "print":
System.out.println(args[0]);
return args[0];
case "sqrt":
return Math.sqrt(ensureDouble(args[0]));
case "pow":
return Math.pow(ensureDouble(args[0]), ensureDouble(args[1]));
default:
throw new CalcRuntimeError("Unknown function: " + functionName);
}
}
public static FunctionCallNode create(String functionName, CalcNode[] argumentNodes) {
return FunctionCallNodeGen.create(functionName, argumentNodes);
}
}

9. Built-in Functions with Specialization

// Built-in print function with specialization
public abstract class PrintNode extends CalcNode {
@Child private CalcNode valueNode;
public PrintNode(CalcNode valueNode) {
this.valueNode = valueNode;
}
@Specialization
protected Object printString(String value) {
System.out.println(value);
return value;
}
@Specialization
protected Object printLong(long value) {
System.out.println(value);
return value;
}
@Specialization
protected Object printDouble(double value) {
System.out.println(value);
return value;
}
@Fallback
protected Object printObject(Object value) {
System.out.println(value);
return value;
}
@Override
public Object execute(VirtualFrame frame) {
Object value = valueNode.execute(frame);
return executePrint(frame, value);
}
protected abstract Object executePrint(VirtualFrame frame, Object value);
public static PrintNode create(CalcNode valueNode) {
return PrintNodeGen.create(valueNode);
}
}

Testing and Execution

10. Running the DSL

public class CalcRunner {
public static Object execute(String code) {
try {
Source source = Source.newBuilder("calc", code, "test.calc").build();
Context context = Context.newBuilder().build();
return context.eval(source);
} catch (Exception e) {
throw new RuntimeException("Execution failed", e);
}
}
public static void main(String[] args) {
// Test expressions
String[] testPrograms = {
"2 + 3 * 4",
"(2 + 3) * 4",
"5 < 10",
"if (5 < 10) 42 else 24",
"print(2 + 3)"
};
for (String program : testPrograms) {
try {
Object result = execute(program);
System.out.println(program + " => " + result);
} catch (Exception e) {
System.err.println("Error in: " + program);
e.printStackTrace();
}
}
}
}

11. Performance Testing

@State(Scope.Benchmark)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
public class CalcBenchmark {
private Context context;
private Source fibonacciSource;
@Setup
public void setup() {
context = Context.newBuilder().build();
String fibCode = 
"let fib = n -> if (n < 2) n else fib(n - 1) + fib(n - 2); " +
"fib(15)";
fibonacciSource = Source.newBuilder("calc", fibCode, "fib.calc").build();
}
@Benchmark
public Object fibonacci() {
return context.eval(fibonacciSource);
}
@Benchmark
public Object arithmetic() {
Source source = Source.newBuilder("calc", 
"let x = 0; while (x < 1000) x = x + 1; x", "loop.calc").build();
return context.eval(source);
}
}

Optimization Techniques

12. Node Rewriting and Caching

// Constant folding optimization
public abstract class ConstantFoldingNode extends CalcNode {
public static CalcNode create(CalcNode left, CalcNode right) {
// Try constant folding
if (left instanceof LiteralNode && right instanceof LiteralNode) {
Object leftVal = ((LiteralNode) left).execute(null);
Object rightVal = ((LiteralNode) right).execute(null);
if (leftVal instanceof Long && rightVal instanceof Long) {
return new LiteralNode(((Long) leftVal) + ((Long) rightVal));
}
}
return AddNode.create(left, right);
}
}
// Caching for expensive operations
public abstract class CachedOperationNode extends CalcNode {
private static final int CACHE_SIZE = 1024;
private final LRUCache<CacheKey, Object> cache = new LRUCache<>(CACHE_SIZE);
@Specialization
protected Object executeCached(VirtualFrame frame, Object left, Object right) {
CacheKey key = new CacheKey(left, right);
Object cached = cache.get(key);
if (cached != null) {
return cached;
}
Object result = compute(left, right);
cache.put(key, result);
return result;
}
protected abstract Object compute(Object left, Object right);
private static class CacheKey {
final Object left, right;
CacheKey(Object left, Object right) {
this.left = left;
this.right = right;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
CacheKey cacheKey = (CacheKey) o;
return Objects.equals(left, cacheKey.left) && 
Objects.equals(right, cacheKey.right);
}
@Override
public int hashCode() {
return Objects.hash(left, right);
}
}
}

Error Handling

13. Custom Exceptions

public class CalcTypeError extends RuntimeException {
public CalcTypeError(String message) {
super(message);
}
}
public class CalcRuntimeError extends RuntimeException {
public CalcRuntimeError(String message) {
super(message);
}
}
public class ParseError extends RuntimeException {
public ParseError(String message) {
super(message);
}
}

Conclusion

Building a DSL with Truffle provides several key advantages:

High Performance: Automatic JIT compilation through Graal
Polyglot Interoperability: Integration with other Truffle languages
Powerful Specialization: Dynamic optimization based on runtime types
Java Ecosystem: Full access to Java libraries and tools

Best Practices:

Use @Specialization for type-specific optimizations
Implement @Fallback for generic cases
Leverage Truffle's node rewriting capabilities
Test performance with realistic workloads
Use the Truffle DSL processor for generated code

This foundation can be extended with more advanced features like:

Custom data types
Object-oriented programming
Module system
Debugger integration
Language server protocol support

Truffle enables building high-performance domain-specific languages that integrate seamlessly with the Java ecosystem while providing optimization capabilities comparable to established languages.