By Full Source on GitHub
A complete implementation of the Stoffle programming language is available on GitHub. Feel free to open an issue if you find bugs or have questions.
In this blog post, we will wrap up the series on Stoffle, a toy programming language built entirely in Ruby. You can read more about this project in the first part of this series.
In the last post, we finished implementing Stoffle's interpreter, completing what we intended for this toy language. Some of you may be interested in having resources available to continue your study of programming language design and implementation. Some of you may also be interested in some ideas to continue improving Stoffle on your own. These are the topics we will cover in this post.
Recommended Resources
In this section, I will make some recommendations for you to continue your path in learning programming language implementation and design. I personally found the resources below very helpful while going through my own journey studying the topic.
Crafting Interpreters, by Robert Nystrom
This is my number one recommendation for those interested in programming language design and implementation. The whole book can be read for free at craftinginterpreters.com. For those that prefer, printed versions are also available for purchase.
Robert Nystrom presents the topic of language design and implementation in great detail without boring the reader. In the first part of the book, Nystrom teaches the reader how to build a tree-walk interpreter from scratch (in the same spirit as what we did in this series, although different in implementation). In the second part of the book, one learns how to evolve the project into a compiled language by building, also from zero, a bytecode virtual machine.
The only drawbacks I see are the languages used in each of these parts. In the first part, Nystrom uses the Java programming language. To build the virtual machine, C was chosen. Even if you particularly dislike one or both of these languages, I strongly suggest you put aside your distaste and at least try to see if the book works for you. The contents and style of the book, in my opinion, are reason enough to read it.
Writing an Interpreter in Go, by Thorsten Ball
When studying any topic, I find it very useful to use a variety of resources and experience the same subject of study from different perspectives. If you like doing the same, I would recommend Writing an Interpreter in Go as a nice complement to Robert Nystrom's Crafting Interpreters.
Sometimes, I personally found Writing an Interpreter in Go a bit harder to understand than my first recommendation. However, it is nonetheless a great book. As you may imagine, the language used to implement the toy interpreter is Go. This may or may not be a hindrance, depending on your interest and familiarity with typed languages and Go in particular.
If you happen to like this book, keep in mind that there is also a sequel available. Ball's Writing a Compiler in Go picks up where the first book left off and continues the project by transforming it into a compiled language with its own virtual machine.
A Compiler from Scratch, by Gary Bernhardt
This is a free screencast that is part of Gary Bernhardt's excellent From Scratch series. In this screencast, Bernhardt builds a compiler for a very simple programming language. The technique used here is to transpile the toy language into JavaScript.
This is a quick introduction to programming language design and implementation and not a comprehensive exploration, unlike the previous recommendations. Regardless, I still find this a very interesting resource. If you happened to land on this post before reading the previous ones where we implemented Stoffle, Bernhardt's screencast is a quick way to get you started and inspired about the topic. Even if you already read the previous posts, the screencast is a fun way to be exposed to a different technique: transpilation or source-to-source compilation. The language used to build the compiler is Ruby, which is another reason to take a look at this resource.
Continue Improving Stoffle On Your Own
If you followed along with this series and completed Stoffle's implementation, now you may be thinking about how to continue your programming language design and implementation journey. Besides checking out the resources recommended above, you can also keep learning by making Stoffle better on your own. In this section, I will offer some pointers on ways you can improve Stoffle and continue progressing in the study of language design and implementation.
Syntactic Sugar
As a toy language, Stoffle has a lot of room for improvement in its syntax. By comparing Stoffle to mature languages, you can probably think of a few constructs that the language misses that, if present, would improve its usage experience.
If you find adding a bit of syntactic sugar to Stoffle a compelling exercise, let me offer you a suggestion. The language currently supports nested conditionals, but it does not have a construct, such as Ruby's elsif. To express nested conditionals, here is what is currently necessary:
if false
println("IF block evaluated.")
else
if true
println("ELSE IF block evaluated.")
end
end
A strategy that can be used in this case, as well as to add other types of syntactic sugar, is to make the parser identify the new construct and produce the same abstract syntax tree (AST) generated for code that is semantically equivalent and currently supported. In other words, change the parser in such a way that when it encounters an elsif, it creates the same AST generated for nested conditionals, such as the one in the code snippet above. To be a bit more specific, here are the two changes you have to make:
- Change the
Lexerclass, adding the newelsifkeyword; - Change
Parser#parse_conditional, making it support the newelsifconstruct by following the strategy explained above.
Type Verification for Arithmetic Operators
To make Stoffle a bit more robust, one interesting exercise is to start adding some basic safeguards to the language. One that comes to mind is adding type verification to arithmetic operators. Currently, there is no implemented mechanism to allow the interpreter to gracefully exit and show the user a helpful error message in cases where an illegal operation is performed. Multiplying two strings together, for example, causes a hard crash in the current version of the interpreter. Want to see for yourself? Try running the following Stoffle snippet:
result = "A string " * "and another string"
println(result)
One straightforward way to implement such a check is to change Interpreter#interpret_binary_operator. There, you can add code that verifies the types of the operands before executing the operation and aborts the interpretation of the program when illegal operations are detected. Keep in mind, however, that this exercise is a bit trickier than you might be imagining. Remember that the operands will not always be primitive types, and in some programs, they may be complex expressions. This means that you will first need to evaluate the operands before being able to figure out their types.
Transpile Stoffle to Another High-Level Language
This is a much larger and challenging project than the previous two. After watching Bernhardt's screencast mentioned above, you may be catching yourself asking whether it would be possible to compile Stoffle to another high-level language (i.e., transpilation) instead of interpreting it. The answer is yes. It is out of the scope of this post to provide detailed instructions on how one could do this, but let me at least give you some pointers to help you if you happen to find yourself enamored with the idea.
You probably will not need to touch either the lexer or the parser. The component that needs to be replaced is the interpreter. Instead of traversing and interpreting the AST generated by the parser, you will need to implement a transpiler. Its job will be to traverse the AST and generate a source file in the programming language that you are targeting. Let's say, for example, that you want to target JavaScript. In this case, your transpiler will need to traverse the AST and generate a JS source file that is semantically equivalent (i.e., have the same meaning) to the original Stoffle program. After doing that, you should be able to run the generated JS file using an appropriate tool of your choice (such as Node.js).
Conclusion
In this post, we wrapped up the series on Stoffle, a toy programming language implemented from scratch entirely in Ruby. This was a long and challenging journey, but we were able to make it to the other side!
If you want to tackle implementation challenges before studying deeper and learning about new concepts, the exercises I proposed may be a good start. If you feel you are ready to dive deeper and want to start exploring new and more complex concepts, the resources I recommended in the beginning of this post are definitely a great bet. I really hope this series ignited a passion for programming language implementation and design and that you continue on this exhilarating adventure!
