📄 Page
1
(This page has no text content)
📄 Page
2
Building Programming Language Interpreters A bottom-up approach to runtimes, execution, and implementation in C++ Daniel Ruoso
📄 Page
3
Building Programming Language Interpreters Copyright © 2026 Packt Publishing All rights reserved. No part of this book may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, without the prior written permission of the publisher, except in the case of brief quotations embedded in critical articles or reviews. Every effort has been made in the preparation of this book to ensure the accuracy of the information presented. However, the information contained in this book is sold without warranty, either express or implied. Neither the author, nor Packt Publishing or its dealers and distributors, will be held liable for any damages caused or alleged to have been caused directly or indirectly by this book. Packt Publishing has endeavored to provide trademark information about all of the companies and products mentioned in this book by the appropriate use of capitals. However, Packt Publishing cannot guarantee the accuracy of this information. Portfolio Director: Kunal Chaudhari Relationship Lead: Dhruv J. Kataria Project Manager: K. Loganathan Content Engineer: Richa Singh Technical Editor: Irfa Ansari Copy Editor: Safis Editing Indexer: Hemangini Bari Proofreader: Richa Singh Production Designer: Prashant Ghare Growth Lead: Vinishka Kalra First published: January 2026 Production reference: 1130126 Published by Packt Publishing Ltd. Grosvenor House 11 St Paul’s Square Birmingham B3 1RB, UK. ISBN 978-1-83763-807-9 www.packtpub.com
📄 Page
4
In the mid-2000s, I was fortunate enough to get involved in the development of the Perl 6 language. This was probably the steepest learning period in my life as a software developer. The long conversations on IRC with fantastic folks such as Audrey Tang, Flávio Glock, Jonathan Worthington, Larry Wall, Moritz Lenz, Nelson Ferraz, Paweł Murias, Yuval Kogman, and many others have given me the starting point of my understanding of programming languages and interpreter design. Without them, I would likely not have gotten interested in this area at all. —Daniel Ruoso
📄 Page
5
Contributors About the author Daniel Ruoso has more than 20 years of experience in software development. He has contributed to various projects over the years, specializing in build tooling, static analysis, and automated code refactoring. He was a contributor to the early development of the Raku programming language and of the Debian project. More recently, he contributed to the tooling study group of the ISO C++ working group. Daniel has also presented talks at the LLVM Developers’ Meeting, C++Now, and CppCon. Thanks to my parents, Karin and Sérgio, who provided me with access to technology at an early age and the space to experiment at a time when this was not at all common in the small town of Iguatu; my older brother, Leonardo, who nudged me in all the right ways to kickstart my career; my wife, Arêtha, for supporting me in every risk I took in my journey to get where I am today; and my kids, Tito and Yann, for motivating me to keep learning.
📄 Page
6
About the reviewers Tony Varghese is a compiler engineer and engineering tech lead with extensive hands-on expe- rience in LLVM and MLIR frameworks. He has contributed multiple patches to the upstream LLVM project, including contributions to the PowerPC backend and optimization passes, and actively participates in the compiler development community through technical forums and mentoring. His work focuses on compiler optimizations, language tooling, and building robust infrastructure for complex systems. Tony is passionate about problem-solving and enjoys tackling challenging compiler and interpreter implementation issues. His open source contributions can be found at https://github.com/tonykuttai/. When not working on compilers, he enjoys spending time with his daughter and playing badminton. I would like to thank my family for their support and encouragement during the technical review of this book. Nikhil Kapoor has over 16 years of experience in the fields of AI and machine learning (ML), where he has designed and implemented advanced models, intelligent platforms, and data-driven solutions at scale. His expertise extends to architecting end-to-end platforms and distributed applications at a leading cloud service provider, integrating AI/ML capabilities with cloud-native technologies to drive innovation. He has applied these skills across diverse sectors—including finance, investment management, audit, and telecom R&D—delivering intelligent, scalable, and production-ready systems. In addition to his technical depth, he has led teams through the full software development life cycle.
📄 Page
7
Join us on Discord! Read this book alongside other users, developers, experts, and the author himself. Ask questions, provide solutions to other readers, chat with the authors via Ask Me Anything sessions, and much more. Scan the QR or visit the link to join the community. https://packt.link/deep-engineering-cpp
📄 Page
8
Table of Contents Preface xv Free Benefits with Your Book ������������������������������������������������������������������������������������������ xxii Part 1: Modeling the Programming Language Runtime Environment Chapter 1: Defining the Scope 3 Technical requirements ������������������������������������������������������������������������������������������������������ 4 Why do we keep creating new languages? ��������������������������������������������������������������������������� 4 Domain-specific languages ������������������������������������������������������������������������������������������������� 6 Compilers and interpreters ������������������������������������������������������������������������������������������������� 6 The exercise we will complete in this book ������������������������������������������������������������������������� 7 How will the interpreter be integrated? ������������������������������������������������������������������������������ 9 Summary ��������������������������������������������������������������������������������������������������������������������������� 13 Chapter 2: The Blurred Lines Between Native Code, Virtual Machines, and Interpreters 15 Modern ISAs are virtual machines of sorts ������������������������������������������������������������������������ 16 Native programming languages also have a virtual machine model • 20 Interpreters as virtual machines ���������������������������������������������������������������������������������������� 21 Abstraction of complexity versus execution overhead ������������������������������������������������������� 22 How JIT compilers change the performance calculation ��������������������������������������������������� 25
📄 Page
9
Table of Contentsviii Deciding which model our language will use �������������������������������������������������������������������� 26 Summary �������������������������������������������������������������������������������������������������������������������������� 27 Chapter 3: Instructions, Concurrency, Inputs, and Outputs 29 Instructions as building blocks ����������������������������������������������������������������������������������������� 30 Operator stack versus registers ������������������������������������������������������������������������������������������ 31 Interpreter stack versus language stack ���������������������������������������������������������������������������� 33 Interruptions to the control flow �������������������������������������������������������������������������������������� 36 Continuations across native and interpreted code ������������������������������������������������������������ 37 Concurrency model ����������������������������������������������������������������������������������������������������������� 39 Deciding on the execution model �������������������������������������������������������������������������������������� 42 Summary �������������������������������������������������������������������������������������������������������������������������� 43 Chapter 4: Native Types, User Types, and Extension Points 45 Different types of type systems ����������������������������������������������������������������������������������������� 45 Static typing versus dynamic typing • 46 Strong typing versus weak typing • 49 Language types versus user-defined types ������������������������������������������������������������������������ 50 Nominal typing versus structural typing • 51 Duck typing • 53 Approaches to modeling the type system �������������������������������������������������������������������������� 55 The native types for your language • 55 How the users will declare their own types • 58 Interaction with native extensions ����������������������������������������������������������������������������������� 58 Summary �������������������������������������������������������������������������������������������������������������������������� 60 Chapter 5: Putting It All Together: Making Trade-Off Decisions 63 Designing the execution model ����������������������������������������������������������������������������������������� 63 Interacting with inputs and outputs • 64 Identifying continuations that are ready to execute • 65
📄 Page
10
Table of Contents ix Performing interpreted operations • 66 Making native callbacks • 67 Concurrency in an embedded language ���������������������������������������������������������������������������� 68 Memory management ������������������������������������������������������������������������������������������������������� 70 Memory access patterns • 70 Managing mutability • 71 Data ownership • 73 Life cycle management • 74 Finalizing my design • 74 Summary �������������������������������������������������������������������������������������������������������������������������� 75 Part 2: Modeling the Programming Language Syntax Chapter 6: Review of Programming Language Paradigms 79 Imperative programming ������������������������������������������������������������������������������������������������� 80 Functional programming �������������������������������������������������������������������������������������������������� 81 Declarative programming ������������������������������������������������������������������������������������������������� 84 Logic programming ���������������������������������������������������������������������������������������������������������� 86 Choosing a paradigm for our language ����������������������������������������������������������������������������� 89 Summary �������������������������������������������������������������������������������������������������������������������������� 90 Chapter 7: Values, Containers, and the Language Meta-Model 93 Variables and values ���������������������������������������������������������������������������������������������������������� 93 Values and containers ������������������������������������������������������������������������������������������������������� 95 Mutability ������������������������������������������������������������������������������������������������������������������������� 97 Copies, references, and shared values ������������������������������������������������������������������������������� 98 The language meta-model ������������������������������������������������������������������������������������������������ 99 Summary ������������������������������������������������������������������������������������������������������������������������� 101
📄 Page
11
Table of Contentsx Chapter 8: Lexical Scopes 103 The lexical pad ���������������������������������������������������������������������������������������������������������������� 103 Function lexical scopes ��������������������������������������������������������������������������������������������������� 104 Block lexical scopes ��������������������������������������������������������������������������������������������������������� 105 Closure lexical scopes ����������������������������������������������������������������������������������������������������� 106 Global lexical scopes �������������������������������������������������������������������������������������������������������� 107 Summary ������������������������������������������������������������������������������������������������������������������������ 108 Chapter 9: Putting It All Together and Creating a Coherent Vision 111 The shape of a declarative language ���������������������������������������������������������������������������������� 111 Specifying the empty program • 112 Hello World! • 113 Hello who? • 115 Immutability, containers, and values ������������������������������������������������������������������������������� 116 Value types • 118 Container types • 119 Variables and references �������������������������������������������������������������������������������������������������� 120 The final language design ������������������������������������������������������������������������������������������������ 121 Summary ������������������������������������������������������������������������������������������������������������������������� 126 Part 3: Implementing the Interpreter Runtime Chapter 10: Initialization and Entry Point 129 The scaffolding ���������������������������������������������������������������������������������������������������������������� 129 The global interpreter state ��������������������������������������������������������������������������������������������� 130 The interpreted program and the interpreter • 130 The operation tree and the mutable interpreter state • 131 Executing the operations in the tree • 135 Making it friendly to be embedded ��������������������������������������������������������������������������������� 140 Refactoring for multiple types of operations ������������������������������������������������������������������� 144
📄 Page
12
Table of Contents xi Designing the interface for I/O ���������������������������������������������������������������������������������������� 148 Summary ������������������������������������������������������������������������������������������������������������������������� 151 Chapter 11: Execution Frames, the Stack, and Continuations 153 Code as a value ����������������������������������������������������������������������������������������������������������������� 154 Invoking a callable value �������������������������������������������������������������������������������������������������� 157 Making a function ������������������������������������������������������������������������������������������������������������ 161 Calling a function ������������������������������������������������������������������������������������������������������������ 170 The end-to-end example �������������������������������������������������������������������������������������������������� 173 Summary ������������������������������������������������������������������������������������������������������������������������� 175 Chapter 12: Running and Testing Language Operators 177 Identifying and implementing operators ������������������������������������������������������������������������ 183 I/O operators • 184 List operators • 190 Testing the operators ������������������������������������������������������������������������������������������������������ 196 Finalizing the integration ���������������������������������������������������������������������������������������������� 200 Summary ������������������������������������������������������������������������������������������������������������������������� 214 Part 4: Interpreting Source Code Chapter 13: Lexing: Turning Text into a Stream of Tokens 219 Identifying token types and their data structures ����������������������������������������������������������� 220 Specifying the rules of the lexer �������������������������������������������������������������������������������������� 223 Evaluating different lexer libraries ���������������������������������������������������������������������������������� 224 Getting a stream of tokens ���������������������������������������������������������������������������������������������� 225 Testing the tokenizer • 228 Summary ������������������������������������������������������������������������������������������������������������������������ 229
📄 Page
13
Table of Contentsxii Chapter 14: Parsing: Turning a Stream of Tokens into a Parse Tree 231 Types of parse nodes and their data structures ��������������������������������������������������������������� 232 Specifying the grammar for the parser ���������������������������������������������������������������������������� 234 Evaluating different parser libraries ������������������������������������������������������������������������������� 236 Building a grammar engine in C++ ���������������������������������������������������������������������������������� 238 Getting the parse tree ������������������������������������������������������������������������������������������������������ 247 Summary ������������������������������������������������������������������������������������������������������������������������� 251 Chapter 15: Analyzing: Turning a Parse Tree into an Abstract Syntax Tree 253 Difference between a parse tree and an abstract syntax tree ������������������������������������������� 254 Modeling the node types and their data structures ��������������������������������������������������������� 254 Transforming one tree into another ��������������������������������������������������������������������������������� 261 Summary ������������������������������������������������������������������������������������������������������������������������ 273 Chapter 16: Generating: Turning an Abstract Syntax Tree into Instructions 275 Matching AST nodes to interpreter operations ��������������������������������������������������������������� 276 Introducing the TransitionLookAhead operation • 276 Introducing StateMachineOperation • 281 Generating the code for StateMachineOperation • 289 Generating the entire program ���������������������������������������������������������������������������������������� 296 Integrating into the interpreter �������������������������������������������������������������������������������������� 303 Executing code in our programming language for the first time ������������������������������������� 305 Summary ������������������������������������������������������������������������������������������������������������������������ 307 Chapter 17: Proving That It Works 309 Revisiting our goals ��������������������������������������������������������������������������������������������������������� 309 Domain-specific language (DSL) for specifying network protocols • 310 Synchronous request–response protocols • 310 Transfer of control at multiple points • 310 Transferring values to the native language • 311 Using captured values within the protocol • 311
📄 Page
14
Table of Contents xiii Checking our acceptance criteria ������������������������������������������������������������������������������������� 312 Initialize the interpreter once • 312 Make the interpreter drive the interaction with the network • 312 Transfer control at specific points • 313 Working through an example ������������������������������������������������������������������������������������������ 313 Understanding SMTP • 314 Expressing SMTP in the DSL • 315 Implementing an SMTP server • 322 Implementing callbacks • 326 Was it worth it? ��������������������������������������������������������������������������������������������������������������� 330 Summary ������������������������������������������������������������������������������������������������������������������������� 331 Chapter 18: Unlock Your Exclusive Benefits 333 Other Books You May Enjoy 339 Index 343
📄 Page
15
(This page has no text content)
📄 Page
16
Preface I grew up experimenting with BASIC on an MSX computer in Brazil. That was a time when the computer would come with a printed manual that had little games and exercises with the code listings, and you would have to type it out to see what happened. When my family got a 486 PC, I transitioned to QBASIC. I still remember the first time I built an entire game with animations and everything from scratch. Later, I transitioned to Delphi, where I would help my older brother in some of his projects, and eventually presented a small educational application at my school that I built with a colleague to explore the periodic table. At that time, I was also transitioning to using GNU/Linux and ex- ploring with C programming. I only became a “real” software developer once I learned Perl. This was 1998, and my older brother bought the Learning Perl and Programming Perl books. I still spoke “baby Perl,” as Larry Wall would say, and it would be a few years until I was confident enough to ship my first module to CPAN. I became an avid advocate for the Perl language and started publishing various CPAN modules and participating in conferences. I remember all the hours I spent on perlmonks.org, and the moment my name finally showed up on the Saints in Our Book page. But while at the turn of the century, Perl was “the duct tape of the internet,” by the turn of the 2010s, there was a very strong sentiment against it in the industry. I had to accept that I couldn’t just be a Perl developer; I had to be an “anything developer.” This has led me to take a very different perspective when looking at programming language and interpreter design. To look beyond the what and start asking the why. Why did Python choose to use a Global Interpreter Lock? Why did Perl have a share-nothing approach for multi-threading? Why does the C++ language have entirely different systems for programming and meta-programming?
📄 Page
17
Prefacexvi Meanwhile, my formal education was in social sciences, which made me look at all of this from an anthropological perspective. At the end of the day, we’re talking about human communica- tion; there’s no stick we can use to measure whether one language is better than another. You have different languages and people with different levels of fluency. You have ecosystems and communities that build a specific culture around those languages. It is with this perspective that I arrived at the premise of this book, which is that we will never stop creating new programming languages, for as long as we have to write code. But this doesn’t need to be just a matter of aesthetic preference. Some niche problems require niche solutions, and building programming language interpreters is a way to introduce novel solutions to existing problems. At the same time, a programming language is heavily influenced by the runtime environment it targets, but it’s also possible to build custom runtime environments that target a specific pro- gramming language. The existing literature tends to treat those areas as fundamentally independent, while I feel that there is a lot left behind by not considering the design and implementation of the programming language and of the runtime environment it targets as a coherent set. That is why it was important to me to choose a bottom-up approach when working on this book. I want you to look at the entire problem of both programming language and interpreter design and implementation as a single unit. By the end of this book, I hope that you find yourself as fascinated as I am by all the technical and non-technical aspects that are connected to programming language and interpreter design and implementation. Who this book is for This book is tailored for intermediate to advanced software developers, particularly those inter- ested in language design and implementation. It’s ideal for programmers seeking to expand their skill set and tackle complex problems efficiently. Professionals working in roles such as software engineers, language designers, or system architects will benefit from the practical insights and hands-on experience provided in the book. A good understanding of C++ programming and a basic grasp of language design concepts are recommended to fully grasp the content.
📄 Page
18
Preface xvii What this book covers Chapter 1, Defining the Scope, starts with a reflection on why we keep introducing new programming languages and what benefits they can introduce, and then sets the problem statement for the programming language we will use for the exercise in this book, with the goals and acceptance criteria for the minimum viable product of that language. Chapter 2, The Blurred Lines Between Native Code, Virtual Machines, and Interpreters, discusses how modern hardware architectures can no longer be thought of in the same way as historical archi- tectures, and how an interpreter has a lot of similarities with hardware in terms of how we think about its capabilities. Chapter 3, Instructions, Concurrency, Inputs, and Outputs, works through the decision of the gen- eral architecture of the interpreter that will be built in the book, discussing various alternative approaches used by other interpreters. Chapter 4, Native Types, User Types, and Extension Points, explores how the choice of the type system of the runtime affects the programming language, how choices in the language affect the runtime, and how those choices come together to guide the design. Chapter 5, Putting It All Together: Making Trade-Off Decisions, completes the overall design process for the interpreter and language runtime, contrasting the consequences of specific choices and how they affect the interpreter. Chapter 6, Review of Programming Language Paradigms, goes over the various ways in which dif- ferent programming languages make it easier or harder to solve specific problems, how some paradigms help in specific scenarios, and which approach makes the most sense for the language being designed and implemented in this book. Chapter 7, Values, Containers, and the Language Meta-Model, discusses how various programming languages have different approaches for handling values, variables, and containers, and how they interact with runtime type information, copies, and references. Chapter 8, Lexical Scopes, covers how the language handles names, how they get resolved to vari- ables, how other languages approach that problem, and the trade-offs that we will focus on for our language. Chapter 9, Putting It All Together and Creating a Coherent Vision, brings together all the various aspects discussed of how to make the programming language design into a coherent design.
📄 Page
19
Prefacexviii Chapter 10, Initialization and Entry Point, covers the overall structure of the interpreter project, starting with the skeleton CMake project, then explaining how to drive development with tests, how the operation tree is implemented, and how the interpreter steps through it. Chapter 11, Execution Frames, the Stack, and Continuations, covers how the programming language needs to handle higher-level concepts than the simple operation tree in the stack, including the execution of functions. Chapter 12, Running and Testing Language Operators, brings together how operators are imple- mented, tested, and executed, getting to the point where the interpreter can parse and write an entire message. Chapter 13, Lexing: Turning Text into a Stream of Tokens, starts the transition into the ability to actually run code in the programming language, starting with the lexer, which breaks down the characters in the source into a sequence of tokens. Chapter 14, Parsing: Turning a Stream of Tokens into a Parse Tree, works through the definition of a grammar for the language, and how that is implemented in C++, including a custom grammar engine using modern C++ features. Chapter 15, Analyzing: Turning a Parse Tree into an Abstract Syntax Tree, highlights how the parse tree is focused on the shape of the source code itself, while a language may have a different ab- stract structure, and how the abstract syntax tree needs to represent that higher-level structure. Chapter 16, Generating: Turning an Abstract Syntax Tree into Instructions, closes the gap between the abstract syntax tree and the operations supported by the interpreter, concluding with a test that exercises the interpreter end to end. Chapter 17, Proving That It Works, implements the code that a user of the interpreter would write to exercise the end-to-end experience and validate that we achieved the goals we set at the be- ginning of the exercise.
📄 Page
20
Preface xix To get the most out of this book The first two parts are mostly theoretical, but when we get to the implementation, you will benefit from being able to play along with the implementation. Software/hardware covered in the book Operating system requirements CMake Windows, macOS, or Linux GCC, at least version 12, or Clang, at least version 17 Make sure you are able to use an interactive debugger. Even better if it is integrated into your editor. Download the example code files The code bundle for the book is hosted on GitHub at https://github.com/PacktPublishing/ Building-Programming-Language-Interpreters. We also have other code bundles from our rich catalog of books and videos available at https://github.com/PacktPublishing. Check them out! Download the color images We also provide a PDF file that has color images of the screenshots/diagrams used in this book. You can download it here: https://packt.link/gbp/9781837638079. Conventions used There are a number of text conventions used throughout this book. CodeInText: Indicates code words in text, database table names, folder names, filenames, file extensions, pathnames, dummy URLs, user input, and Twitter handles. For example: “The C++ language offers a way to handle that case in a type-safe way by using std::variant.” A block of code is set as follows: template <typename OT> concept OperationConcept = requires(OT op, OT::Arguments args) { { std::tuple_size<typename OT::Arguments>::value } -> std::convertible_to<std::size_t>; { op(args) } -> std::convertible_to<Value>; };