Trieste: A C++ DSL for Flexible Tree Rewriting (Tool paper)
summary
Trieste is a C++ DSL that implements in-place subtree pattern matching to run multipass compiler pipelines, with each pass checked by dynamic well-formedness checks that act as postconditions and preconditions. Effects are arbitrary C++ so rules can lift nodes, build constraints, and update scopes; well-formedness specs also power random well-formed tree generation for fuzzing. The system reduces visitor boilerplate and is used to ship fully compliant YAML and JSON parsers, a YAML→JSON transpiler, and a C++ Rego compiler/interpreter.
AI-written summary · about
chapters (22)
- 0:00Introduction to Trieste and the speaker
- 0:16What is Trieste and who developed it
- 1:18Problem with multi-pass compiler pipelines
- 3:09How flexible trees work in Trieste
- 4:16Well-formedness specifications explained
- 6:05Overview of the Trieste pipeline
- 7:32Writing a MinML compiler front end in Trieste
- 8:56How parsing works in Trieste
- 11:45Rewriting with Trieste: first example
- 13:32Pattern and effect in rewrite rules
- 14:59Error handling and traversal direction
- 15:44Restructuring let bindings in MinML
- 16:49Rewriting simple expressions and binary operators
- 18:15Type inference with Trieste
- 20:00Order of passes and well-formedness as postconditions
- 21:04Final tree structure after all passes
- 21:48Existing projects using Trieste
- 22:09Summary of Trieste program structure
- 22:30Advantages of flexible trees and minimal boilerplate
- 23:36Q&A: Pattern matching and properties in nodes
- 25:45Q&A: Comparison with Stratego and Stratego/XT
- 27:13Q&A: Modular language evolution in Trieste
related talks
08mCompiling pattern matching to in-place modifications
25mHigh-Fidelity Metaprogramming with Separator Syntax Trees
35mRestaging Domain-Specific Languages: A Flexible Design Pattern for Rapid Development of(…)
01h 01mExpressive Compile Time Parsers
01h 39mHands-on Dotty
44mLet's talk about transpilers
29mMy Little Parser: Tooling is Magic
24mChoice Trees: Representing Nondeterministic, Recursive, and Impure Programs in C...