All the code for this book is available on GitHub: https://github.com/PacktPublishing/Building-Programming-Language-Interpreters.

I suppose it is tempting, if the only tool you have is a hammer, to treat everything as if it were a nail.

—Abraham Maslow, 1966, The Psychology of Science

We tend to underestimate how the programming languages we use define the way we write code and the way we handle the problems that are presented to us as software developers. The shape of our solutions is influenced by the tools we have when we’re working on them.

The environments and ecosystems of the programming languages we use shape us as developers. We can sometimes recognize the accent a developer has when they move from one programming language to another, and it takes a certain amount of effort and code review to become familiar with another language and to start talking like a native.

While it’s true that you can solve any computable problem in any Turing-complete language, it’s also true that some problem spaces are better addressed by certain languages, and those tend to become used persistently, even when they’re no longer in fashion.

Fortran is a very good example of that. It has seen an important resurgence in the scientific computing community. It has straightforward semantics, very good support for numerical types, and a lot of efficiency when it comes to computing lots of numerical operations. Those characteristics make it extremely useful in that context, and it doesn’t matter that Fortran is quite literally the oldest programming language still in use.

The ecosystem also defines a lot regarding how problems are solved. C++ has a significant deficiency in how code reuse is managed, particularly across projects. It still has no uniform package management, even though it is probably the language that needs the most amount of support from outside the language for its build to work properly. Header-only libraries in C++ were developers’ response to this deficiency in the ecosystem, and it became a defining aspect of how libraries are made in the language.

Of course, sometimes we also just want to express aesthetic preferences on how we write our code. Programming is not a mathematical exercise; it is much closer to telling a story—a story you tell the computer, of course, but it’s also a story you tell other developers. And it’s easy to underestimate how strongly software developers feel about the choices that are made to solve programming problems.

Those choices are not always made based on empirical evidence—more often than not, they’re derived from the culture that is built around a given community. The Perl community, for instance, was heavily informed by the “There is more than one way to do it” principle of the language itself. This could also be seen in how libraries were designed, with more flexible interfaces and the idea that the goal was to make it easier to solve problems.

This ended up becoming the fuel for a lot of the detraction from Perl, and opposition to it became a driving force in the design of Python, where “There should be one—and preferably only one—obvious way to do it.”

You may have read the previous paragraphs thinking that I would present you with a definitive way to talk about the most important aspects of programming language design and give you the answer to the question: “What is the best and worst programming language?” But I’m going to go in quite the opposite direction.

Instead of trying to find the one ultimate language, our goal should be to use the programming language that best fits the specific problem we’re trying to solve. Sometimes, we may have strong opinions regarding that programming language, but if it allows us to solve the problem more easily (maybe there’s a library in that ecosystem that fits our problem), then we should prioritize solving the problem, independent of our opinions about that particular programming language.

Sometimes, disruption comes from unexpected places, and a language that takes a different approach will allow developers to create better solutions to existing problems. That can create a turning point and attract a lot of people to bootstrap an entirely new community. We’ve seen how fast Rust is gaining popularity, and how its memory management model changes the way people solve problems in that language.

Other times, disruptions occur without us having to replace any existing language. Focusing on niche use cases can create entirely new ways of solving problems. In the next section, we will focus on scenarios like that.

Some use cases benefit from an entirely separate language focused on that particular problem. We call those domain-specific languages (DSLs). They solve specific types of problems that don’t fit well with the existing programming languages. They eliminate the need to express things that are not part of the problem and allow us to focus on the problem itself.

A great example of a language that is used a lot, but that most people wouldn’t consider using in situations other than the one it’s already used, is SQL. It is a language that focuses on expressing complicated relational algebra in a way that is intuitive and where you don’t have to specify unrelated operations to the problem you’re solving, meaning that there is less opportunity for bugs in the code.

A tool that is extremely powerful and that has become an integral feature of most programming languages is regular expressions. Specifying how to match a string against complex rules would be massively error prone if the developer didn’t have access to that specific language.

The two examples provided happen to be languages that often belong to entirely different paradigms than the one the developer is using to write the broader application code, and this is not a coincidence. The declarative nature of regular expressions makes them very different from the imperative nature of the language usually surrounding their use. And it’s that ability to easily go from being imperative to declarative that is the greatest power of DSLs. In Chapter 6, Review of Programming Language Paradigms, I will discuss the various programming language paradigms.

Before jumping into the programming language that we’ll be designing in this book, it is important to take a step back and think about how our code will run.

Compilers and interpreters were roughly developed at the same time most programmers were expected to write native code for their target architecture. In general, a compiler will translate higher-level programming language code into native code that’s executed by the CPU. On the other hand, an interpreter will translate the programming language into a series of abstract operations that will be executed by the interpreter indirectly. Some problem spaces required minimal overhead, something that a direct translation to native code could provide, while other spaces could afford that overhead and prioritized the easier iteration between writing code and having it executed.

In Chapter 2, The Blurred Lines Between Native Code, Virtual Machines, and Interpreters, I will discuss how this distinction has become increasingly fragile over time. However, the principle still stands: when we make the distinction between compiled and interpreted languages, we still think in terms of whether the execution is done directly, by the native architecture, or whether there is a user-level abstraction that will execute the code in terms of abstract operations.

One of the biggest advantages of working with an interpreter is that you get to define all the characteristics of the runtime for your programming language. This allows for much quicker iteration when developing the programming language since you don’t need to worry about low-level machine behavior. And, more importantly, this does not prevent you from eventually generating native code from it.

Even if the problem space is one where the lower overhead of a compiler will be desirable in the end, the freedom afforded by starting with an interpreter will allow you to get to a working prototype faster.

In the next section, we will reflect on what we covered in the previous sections to define the use case that we will implement in this book.

This book will take you through the journey of creating a custom programming language and interpreter. This journey will be segmented into four parts:

• In the first part, I will discuss runtime environments, how they impact language design, and what trade-offs are available
• In the second part, I will discuss programming language design, and how that influences different kinds of problem-solving approaches
• In the third part, I will focus on the implementation of the interpreter runtime, getting it to a point where the interpreter can run a program
• In the fourth part, I will focus on processing the syntax of the language, leading to a functional interpreter

This bottom-up approach intends to give you a broad understanding of the entire problem space instead of just parsing code. I believe reflecting on these deeper aspects of how to build an interpreter will give you a stronger perspective when you start implementing your own interpreter and programming language.

To make this a fruitful exercise, we’ll create a custom language that solves a real-world problem and can be used in future projects.

Note that whenever you are considering writing a custom language and interpreter, you should start from the same point I’m starting now and contemplate the following questions:

• What goal do you have for that language?
• What is going to be in the first release?
• What will be outside the scope at the start?

It’s important to take these questions into account because writing a custom programming language and interpreter is easily something that gives way to scope creep and endless redesigning. My suggestion is that you resist that urge and stay focused on delivering what you set out to be your first release. Once you’ve done that, you will be able to use your custom language in the real world to inform the direction of its next releases—it’s likely that the use case you’ve been thinking about won’t be needed until much later.

With that said, let’s start looking at the exercise we will complete in this book. I want to focus on the following problem space: writing code that interacts with a network protocol, which is very error prone. Bugs in managing the state machines required to implement more complex network protocols are common. This is because, in general, programming languages do not provide high-level enough abstractions to deal with those.

The challenge I’m putting forth for myself in writing this book is to come up with a DSL for specifying network protocols. The interpreter will perform the necessary operations and manage all the state machines required to implement the protocol correctly, whereas the language will specify in which parts of the protocol the control flow is meant to be transferred between the DSL and the native language.

I don’t expect that the interpreter we’ll create will be a complete solution that can handle any network protocol, as that would make it really difficult to finish this book. Instead, we will focus on a few basic requirements and specify acceptance criteria for a minimum viable product (MVP) for this new, custom programming language.

This interpreter will need to have the following characteristics:

• Be able to support synchronous request–response protocols, such as HTTP/1.1.
• Allow control to be transferred to the outside language at multiple points so that a request can be rejected before it’s processed. As an example, a request could be rejected due to the path given in an HTTP request not existing.
• Allow values to be captured and communicated to the outside language.
• Allow captured values to be used to define aspects of the communication itself, such as the Content-Length header in HTTP, which specifies how long the body should be.

Likewise, some aspects will be intentionally left out:

• Support for protocols that utilize concurrent messages and asynchronous states, such as HTTP/2
• Support for continuation across network interruptions
• Support for general-purpose computation in the language
• Support for using more than one thread for each connection

This is not to say that those are never going to become features of the language and the interpreter, but the goal is to prevent scope creep from becoming part of the first release of the language.

The acceptance criteria for this first version of the language will be as follows:

• It must be able to start the interpreter by providing a source file when a daemon is initialized
• It must give a connected socket to the interpreter for it to drive the network protocol
• It must have the interpreter return control so that specific functions can be executed at the points defined in the interpreted program

In the next section, we will discuss how this interpreter will interact with existing ecosystems and how we can make it as useful as possible.

A custom programming language that handles network protocols is not going to be very useful if you can’t connect it to whatever code is already handling input/output (I/O) as you might be using different libraries and approaches to implement concurrency.

To make this custom language useful, the design for the interpreter needs to be considered with care. The way input and output are handled and the way concurrency needs to be supported will have a direct impact on the situations in which the interpreter can be used.

In our case, the crucial integration point is going to be the I/O layer since the language focuses on how a socket communicates. Other languages will likely have other, more dominant aspects. Here are some other scenarios that illustrate how different languages may have very different focus points for integration:

• A language focused on large mathematical computations would have to largely focus on concurrent processing and how to transfer values efficiently
• A language focused on message passing would need a fine-tuned scheduler that reduces the amount of time that’s spent on managing message queues
• A language focused on real-time processing would need tight control over all the operations that could introduce unplanned latency to the execution

When you’re starting the design process for your language, you must understand the runtime characteristics. This will be the dominating aspect, particularly if it is a DSL that is meant to be embedded into existing systems. This is because runtime characteristics will heavily influence how your interpreter needs to be designed and how it will be integrated.

Trying to cover more than one scenario would likely make this book much larger, so I will only focus on proposing one language. Following this design journey will give you a good perspective on the process and allow you to think about the important aspects of your language.

As I stated previously, the crucial aspect of the language we’ll be developing is how it will integrate the I/O layer. At the time of writing, the ecosystem around processing I/O events is very fragmented. Many independent libraries and frameworks are used in different situations, and committing to just one would significantly limit where this interpreter could be used.

For instance, if you perform a plain read operation on a socket, that will block until bytes are received. On the other hand, if you use non-blocking reads, you still need to be able to know when something is there to be read.

Another example we could consider is Node.js, which uses libuv to implement its I/O operations. If you try to embed Node.js into a process that primarily uses Boost.Asio, you will face a lot of challenges when integrating the two since their approaches to I/O are fundamentally different.

One way to bypass this problem is by utilizing the sans I/O approach. In this approach, instead of supporting a specific concurrency and set of I/O primitives, an API can be built that can be glued to any existing framework, maximizing code reuse.

In practice, this means that the interpreter will not perform any direct read or write operation and instead offer mechanisms so that the integration layer knows that the interpreter is trying to read or write.

Of course, anyone using libuv, for instance, will need to write the glue between it and the interpreter. However, the important point here is that the interpreter itself does not presume that a particular integration should be used; instead, it has an interface that allows any of those frameworks to be integrated.

The other aspect that I defined in the acceptance criteria is that the language will have callback points that will deliver control flow back to the outside language. This highlights an important aspect regarding concurrency and memory management for our interpreter.

There are two possibilities here: the first is that the callback is done entirely within the interpreter loop, meaning it will remain on the native call stack, while the second is that the callbacks are returned so that they can be started by an external scheduler.

This has a significant impact on how memory is managed. If the callback is executed from within the interpreter loop, then the interpreter can use the stack to store some of its state, which simplifies memory management. If the callback is executed outside the interpreter loop, the execution of the callback can be separated into a different thread from where the interpreter itself runs.

Figure 1.1 compares two different ways the callbacks can be integrated with the native code’s call stack. The left-hand side of Figure 1.1 demonstrates that if we just use the native stack to switch between the native code and the interpreter, each of those layers will be completely enclosed, which will limit how the native code can be integrated. On the other hand, the right-hand side of the figure demonstrates that we can execute each step, but instead of calling the next step internally, the system returns information about where the execution has to continue. This will allow the execution to be continued, interrupted, or reordered without constraints from the native stack:

Figure 1.1: Comparing approaches on how to integrate with the native call stack

In this case, my goal is to maximize the flexibility of where this interpreter can be used, so our design will delegate to the outside language as much as possible. Making callbacks from within the interpreter will likely limit its usage, particularly if more complex operations are handled by code. Therefore, I will make the callbacks run from outside the frames processing the protocol itself.

Since I’ve limited our scope to a synchronous protocol for this first version, I only need to support one thread of execution for each socket. However, since we are executing callbacks from outside of the interpreter, they will be able to dispatch additional asynchronous work.

Additionally, there may be many sockets running different instances of the interpreter so that multiple concurrent requests can be handled. To avoid having to parse the code multiple times, we need to create a bootstrap environment that can only be initialized once and can be reused for each connection.

This is very far from a complete design of how the interpreter will work, but it gives us a good starting point regarding the constraints and requirements that must be set. This also illustrates how much complexity goes into building an interpreter.

Programming languages are an integral part of our culture as software engineers and developers—they define how we look at the problems we want to solve. Significant changes to that culture are sometimes driven by the introduction of entirely new general-purpose programming languages, but it’s often the case that DSLs focused on very limited use cases have a much deeper impact on how problems are solved across a variety of programming languages.

Designing and implementing a new programming language requires careful consideration of what needs to be supported in the first version and what can be deferred to future implementations. In this book, we will be narrowing the focus to a DSL that focuses on implementing network protocols, with the first version limited to synchronous request–response protocols such as HTTP/1.1.

Beyond defining the scope, we also have to define some more concrete guidelines, such as how we’re going to use the sans I/O approach to allow the programming language to be used in more scenarios.

Likewise, we will avoid coupling the execution of the interpreted code with the native stack, which will give whoever uses the interpreter various options regarding how to handle concurrency, callbacks, and execution.

In the next chapter, we will focus on the importance of the various levels of abstraction that programming languages use to make specific kinds of problems easier to solve.