craftinginterpreters

Repository for the book "Crafting Interpreters"

8,803

1,034

8,803

118

View on GitHub

Top Related Projects

awesome-compilers

8,814

:sunglasses: Curated list of awesome resources on Compilers, Interpreters and Runtimes

the-super-tiny-compiler

27,832

:snowman: Possibly the smallest compiler ever

Quick Overview

"Crafting Interpreters" is an open-source book and accompanying code repository that guides readers through implementing two interpreters for a programming language called Lox. The project, created by Bob Nystrom, offers a hands-on approach to understanding interpreter design and implementation, with code examples in Java and C.

Pros

Comprehensive and detailed explanation of interpreter concepts
Practical, hands-on approach with complete code implementations
Clear, well-written content suitable for both beginners and experienced programmers
Free and open-source, making it accessible to all

Cons

Focuses on a single, custom language (Lox) rather than a widely-used one
May be too in-depth for those seeking a quick overview of interpreter design
Requires significant time investment to work through the entire book and implementations

Code Examples

This repository is not a code library but rather a collection of code implementations for educational purposes. Therefore, code examples are not applicable in the traditional sense. However, here are a few snippets from the Lox language implementation:

// Example of a simple Lox program
print "Hello, world!";

// Example of a function definition in Lox
fun fibonacci(n) {
  if (n <= 1) return n;
  return fibonacci(n - 2) + fibonacci(n - 1);
}

print fibonacci(10);

// Example of the C implementation of the Lox VM's stack
typedef struct {
  Value* stack;
  Value* stackTop;
  int capacity;
} Stack;

void initStack(Stack* stack) {
  stack->capacity = STACK_MAX;
  stack->stack = (Value*)malloc(sizeof(Value) * stack->capacity);
  stack->stackTop = stack->stack;
}

Getting Started

As this is not a traditional code library, there's no quick start guide. Instead, to get started with the project:

Clone the repository: git clone https://github.com/munificent/craftinginterpreters.git
Read the book online at craftinginterpreters.com
Follow along with the implementations in Java (for the tree-walk interpreter) and C (for the bytecode virtual machine)
Experiment with the provided Lox language implementations and try extending them

Competitor Comparisons

mal

9,998

mal - Make a Lisp

Pros of mal

Implements a Lisp-like language in multiple programming languages, offering a broader perspective on language implementation across different paradigms
Provides a step-by-step guide for incremental interpreter development, allowing learners to build the interpreter in manageable stages
Includes a comprehensive test suite for each implementation step, ensuring consistency across languages

Cons of mal

Focuses on a simpler Lisp-like language, which may not cover as many advanced language features as Craftinginterpreters
Less in-depth explanations of language design concepts and implementation details compared to Craftinginterpreters
May be more challenging for beginners due to the variety of programming languages used

Code Comparison

Craftinginterpreters (Java):

private void statement() {
  if (match(PRINT)) {
    printStatement();
  } else {
    expressionStatement();
  }
}

mal (Python):

def READ(str):
    return reader.read_str(str)

def EVAL(ast, env):
    if type(ast) != list: return eval_ast(ast, env)
    # apply/call
    return ast[0](*eval_ast(ast[1:], env))

awesome-compilers

8,814

:sunglasses: Curated list of awesome resources on Compilers, Interpreters and Runtimes

Pros of awesome-compilers

Comprehensive resource collection covering various aspects of compiler design and implementation
Regularly updated with new resources and community contributions
Includes links to books, courses, tutorials, and tools for different programming languages

Cons of awesome-compilers

Lacks hands-on, step-by-step guidance for building a complete interpreter or compiler
May be overwhelming for beginners due to the vast amount of information
Does not provide a cohesive learning path or structured curriculum

Code comparison

Not applicable, as awesome-compilers is a curated list of resources and does not contain code examples. Crafting Interpreters, on the other hand, provides complete source code for building interpreters in Java and C.

Summary

awesome-compilers serves as an extensive collection of resources for compiler enthusiasts, while Crafting Interpreters offers a structured, hands-on approach to building interpreters. The former is ideal for those seeking a wide range of references and tools, while the latter is better suited for learners who prefer a guided, practical experience in interpreter construction.

the-super-tiny-compiler

27,832

:snowman: Possibly the smallest compiler ever

Pros of The Super Tiny Compiler

Extremely concise and focused, making it easier to understand the core concepts quickly
Designed for educational purposes, with clear comments explaining each step
Can be read and understood in a single sitting

Cons of The Super Tiny Compiler

Limited in scope, covering only basic compiler concepts
Lacks implementation of more advanced features and optimizations
Not suitable for building production-ready compilers

Code Comparison

The Super Tiny Compiler:

function tokenizer(input) {
  let current = 0;
  let tokens = [];
  // ... (tokenization logic)
  return tokens;
}

Crafting Interpreters:

class Scanner {
  private final String source;
  private final List<Token> tokens = new ArrayList<>();
  // ... (more complex scanner implementation)
}

The Super Tiny Compiler focuses on simplicity and readability, using a single function for tokenization. Crafting Interpreters takes a more structured, object-oriented approach with a dedicated Scanner class, preparing for a more comprehensive implementation.

Crafting Interpreters provides a more in-depth exploration of interpreter and compiler construction, covering a wider range of topics and implementing a full-featured language. It's better suited for those seeking a deeper understanding of language implementation, while The Super Tiny Compiler serves as an excellent quick introduction to basic compiler concepts.

Convert designs to code with AI

Introducing Visual Copilot: A new AI model to turn Figma designs to high quality code using your components.

Try Visual Copilot

README

This is the repo used for the in-progress book "Crafting Interpreters". It contains the Markdown text of the book, full implementations of both interpreters, as well as the build system to weave the two together into the final site.

If you find an error or have a suggestion, please do file an issue here. Thank you!

Contributing

One of the absolute best things about writing a book online and putting it out there before it's done is that people like you have been kind enough to give me feedback, point out typos, and find other errors or unclear text.

If you'd like to do that, great! You can just file bugs here on the repo, or send a pull request if you're so inclined. If you want to send a pull request, but don't want to get the build system set up to regenerate the HTML too, don't worry about it. I'll do that when I pull it in.

Ports and implementations

Another way to get involved is by sharing your own implementation of Lox. Ports to other languages are particularly useful since not every reader likes Java and C. Feel free to add your Lox port or implementation to the wiki:

Lox implementations

Building Stuff

I am a terribly forgetful, error-prone mammal, so I automated as much as I could.

Prerequisites

I develop on an OS X machine, but any POSIX system should work too. With a little extra effort, you should be able to get this working on Windows as well, though I can't help you out much.

Most of the work is orchestrated by make. The build scripts, test runner, and other utilities are all written in Dart. Instructions to install Dart are here. Once you have Dart installed and on your path, run:

$ make get

This downloads all of the packages used by the build and test scripts.

In order to compile the two interpreters, you also need a C compiler on your path as well as javac.

Building

Once you've got that setup, try:

$ make

If everything is working, that will generate the site for the book as well as compiling the two interpreters clox and jlox. You can run either interpreter right from the root of the repo:

$ ./clox
$ ./jlox

Hacking on the book

The Markdown and snippets of source code are woven together into the final HTML using a hand-written static site generator that started out as a single tiny Python script for my first book and somehow grew into something approximating a real program.

The generated HTML is committed in the repo under site/. It is built from a combination of Markdown for prose, which lives in book/, and snippets of code that are weaved in from the Java and C implementations in java/ and c/. (All of those funny looking comments in the source code are how it knows which snippet goes where.)

The script that does all the magic is tool/bin/build.dart. You can run that directly, or run:

$ make book

That generates the entire site in one batch. If you are incrementally working on it, you'll want to run the development server:

$ make serve

This runs a little HTTP server on localhost rooted at the site/ directory. Any time you request a page, it regenerates any files whose sources have been changed, including Markdown files, interpreter source files, templates, and assets. Just let that keep running, edit files locally, and refresh your browser to see the changes.

Building the interpreters

You can build each interpreter like so:

$ make clox
$ make jlox

This builds the final version of each interpreter as it appears at the end of its part in the book.

You can also see what the interpreters look like at the end of each chapter. (I use this to make sure they are working even in the middle of the book.) This is driven by a script, tool/bin/split_chapters.dart that uses the same comment markers for the code snippets to determine which chunks of code are present in each chapter. It takes only the snippets that have been seen by the end of each chapter and produces a new copy of the source in gen/, one directory for each chapter's code. (These are also an easier way to view the source code since they have all of the distracting marker comments stripped out.)

Then, each of those can be built separately. Run:

$ make c_chapters

And in the build/ directory, you'll get an executable for each chapter, like chap14_chunks, etc. Likewise:

$ make java_chapters

This compiles the Java code to classfiles in build/gen/ in a subdirectory for each chapter.

Testing

I have a full Lox test suite that I use to ensure the interpreters in the book do what they're supposed to do. The test cases live in test/. The Dart program tool/bin/test.dart is a test runner that runs each of those test files on a Lox interpreter, parses the result, and validates that that the test does what it's expected to do.

There are various interpreters you can run the tests against:

$ make test       # The final versions of clox and jlox.
$ make test_clox  # The final version of clox.
$ make test_jlox  # The final version of jlox.
$ make test_c     # Every chapter's version of clox.
$ make test_java  # Every chapter's version of jlox.
$ make test_all   # All of the above.

Testing your implementation

You are welcome to use the test suite and the test runner to test your own Lox implementation. The test runner is at tool/bin/test.dart and can be given a custom interpreter executable to run using --interpreter. For example, if you had an interpreter executable at my_code/boblox, you could test it like:

$ dart tool/bin/test.dart clox --interpreter my_code/boblox

You still need to tell it which suite of tests to run because that determines the test expectations. If your interpreter should behave like jlox, use "jlox" as the suite name. If it behaves like clox, use "clox". If your interpreter is only complete up to the end of one of the chapters in the book, you can use that chapter as the suite, like "chap10_functions". See the Makefile for the names of all of the chapters.

If your interpreter needs other command line arguments passed to use, pass them to the test runner using --arguments and it will forward to your interpreter.

Repository Layout

asset/ â Sass files and jinja2 templates used to generate the site.
book/ - Markdown files for the text of each chapter.
build/ - Intermediate files and other build output (except for the site itself) go here. Not committed to Git.
c/ â Source code of clox, the interpreter written in C. Also contains an XCode project, if that's your thing.
gen/ â Java source files generated by GenerateAst.java go here. Not committed.
java/ â Source code of jlox, the interpreter written in Java.
note/ â Various research, notes, TODOs, and other miscellanea.
note/answers â Sample answers for the challenges. No cheating!
site/ â The final generated site. The contents of this directory directly mirror craftinginterpreters.com. Most content here is generated by build.py, but fonts, images, and JS only live here. Everything is committed, even the generated content.
test/ â Test cases for the Lox implementations.
tool/ â Dart package containing the build, test, and other scripts.

Top Related Projects

Convert designs to code with AI

Introducing Visual Copilot: A new AI model to turn Figma designs to high quality code using your components.

Try Visual Copilot