Crafting Interpreters by Nystrom

book tier1 programming compilers craftinginterpretersbook

authors: Robert Nystrom

web links: goodreads, wiki, amazon

reading links: openarchive, gutenberg

pdf links: craftinginterpreters.com/contents.html

Short Description

Reach content directly

https://craftinginterpreters.com/contents.html

• a map of the territory
  

• ch 2: a tree walk interpreter
  

• ch 3: a bytecode virtual machine
  

My notes below:

• A Map of the Territory · Crafting Interpreters (archived)
  

• The Lox Language · Crafting Interpreters (archived)
  

• Scanning · Crafting Interpreters (archived)
  

• Representing Code · Crafting Interpreters (archived)
  

TABLE file.name AS "Filename"
FROM ""
WHERE contains(file.name, "Crafting Interpreters") and contains(file.name, "(archived)")

Other similar:

• Peter Norvig, implementing Lisp-Scheme in Python
  

  • https://norvig.com/lispy.html
    

    • https://github.com/norvig/pytudes/blob/main/py/lis.py
      

  • https://norvig.com/lispy2.html
    

    • https://github.com/norvig/pytudes/blob/main/py/lispy.py
      

    • https://github.com/norvig/pytudes/blob/main/py/lispytest.py
      

• David Beazley (Dabeaz), course of write a compiler
  

  • Dabeaz (David Beazley) Write a Compiler Course Notebook
    

Comments

https://news.ycombinator.com/item?id=30332368

• "This is a book that, if you can afford it, should be bought on general principle. There are very few books that show how recursive descent works and this one is incredibly well done. The fact he gives it away for free is amazing."
  

AI Summary

"Crafting Interpreters" by Robert Nystrom is an excellent book that guides readers through the process of implementing a programming language from scratch. The book covers two primary implementations of an interpreter for the same language, Lox, to demonstrate different approaches to language design and interpretation. Here's a summary with key ideas and bullet points:

Overview

• Objective: Teach readers how to build interpreters for programming languages.
  

• Language: Lox, a simple dynamically-typed language, is used to demonstrate techniques.
  

• Approach: The book is divided into two parts, each covering a different implementation path:
  

  • A tree-walk interpreter written in Java.
    

  • A bytecode virtual machine written in C.
    

Part 1: A Tree-Walk Interpreter

• Introduction to Interpreters: Explain the roles and responsibilities of an interpreter.
  

• Lexical Analysis:
  

  • Tokenization: Breaking down source code into tokens.
    

  • Techniques for writing a lexer (scanner).
    

• Parsing:
  

  • Grammar: Define the syntax of Lox using context-free grammar.
    

  • Recursive Descent Parser: Construct an abstract syntax tree (AST) from tokens.
    

• Evaluating Expressions:
  

  • Visitor Pattern: Use to traverse AST and evaluate expressions.
    

  • Implement simple expression evaluation for mathematical operations.
    

• Statements and State:
  

  • Control Flow: Implement if, while, and for statements.
    

  • Environment and Scope: Understand variable declarations and scope management.
    

• Functions and Closures:
  

  • Function Declarations: Introduce how to parse and interpret functions.
    

  • Closures: Implement closures to handle variable scope in functions.
    

• Classes and Inheritance:
  

  • Object-Oriented Features: Implement classes and inheritance.
    

  • Methods and this: Add support for instance methods and the this keyword.
    

Part 2: A Bytecode Virtual Machine

• Introduction to Virtual Machines: Overview of how a VM runs bytecode efficiently.
  

• Chunk and Bytecode:
  

  • Instruction Encoding: Design a bytecode format.
    

  • Chunk: Implement a data structure to store bytecode instructions.
    

• Stack-Based Execution:
  

  • Virtual Stack Machine: Implement a stack-based execution model.
    

  • Bytecode Interpretation: Build a loop to fetch and execute instructions.
    

• Garbage Collection:
  

  • Memory Management: Implement a simple garbage collector.
    

  • Reference Counting vs. Mark-and-Sweep: Explain different approaches to garbage collection.
    

• Optimizations:
  

  • Constant Folding and Local Variable Caching: Techniques to optimize execution.
    

• Strings, Hash Tables, and Closures:
  

  • Implement support for strings and hash tables.
    

  • Closures in a virtual machine context.
    

• Native Functions and Error Handling:
  

  • Introduce native functions directly written in the host language.
    

  • Exception Handling: Incorporate error handling mechanisms.
    

Key Concepts

• Practical Language Implementation: Start with a high-level understanding and progressively delve into deeper, more efficient techniques.
  

• Performance and Complexity: Balance between ease of implementation, readability, and performance.
  

• Language Features: Understand trade-offs involved in implementing various language constructs.
  

• Broader Understanding: Gain insights into both interpreted languages and virtual machines.
  

Conclusion

• By the end of the book, readers will have built two full-fledged interpreters for a custom programming language.
  

• Encourage further exploration and experimentation in language design and implementation.
  

"Crafting Interpreters" is comprehensive and detailed, making it an excellent resource for anyone interested in language design, compilers, or interpreter construction.

Baris' Notes

Introduction

Little languages (aka domain-specific languages)

language hackers

Lex and Yacc > compiler-compilers,

• takes in a grammar file and produces a source file for a compiler, so it’s sort of like a “compiler” that outputs a compiler
  

Yacc > yet another compiler compiler

self-hosting:

"A compiler reads files in one language, translates them, and outputs files in another language. You can implement a compiler in any language, including the same language it compiles, a process called self-hosting.

bootstrapping:

You can’t compile your compiler using itself yet, but if you have another compiler for your language written in some other language, you use that one to compile your compiler once. Now you can use the compiled version of your own compiler to compile future versions of itself, and you can discard the original one compiled from the other compiler. This is called bootstrapping, from the image of pulling yourself up by your own bootstraps."

A map of the territory

https://craftinginterpreters.com/a-map-of-the-territory.html