Contents

Crafting Interpreter Day0

Start following the book of CRAFTING INTERPRETERS in this series. Book always includes large number of information and context. Hope this series of reading notes can help me to review easily in some days. CRAFTING is implementation, I hope I can build up an interpreter with this series. In this book, two interpreters will be created: jlox in Java and clox in C. The programming language to be implemented is Lox (self-defined).

A journey of Implementation

  1. Scanning Scanner (lexer) takes linear stream of characters into tokens.
  2. Parsing Parser takes sequence of tokens and builds a tree structure as AST. Also, report syntax errors.
  3. Static analysis binding or resolution for each identifier, find scope to check the declaration, then figure out the type (or type error). However, Lox is dynamically typed, so type checking would be in runtime.
  4. IR
  5. Optimization We already understand semantics in the third part, so we can switch program more efficiently to the one which has the same semantics.
  6. Code generation machine code or bytecode. Machine code can run on CPU directly. Bytecode needs to be translated to machine code, e.g. Java bytecode is translated by JVM.
  7. Virtual machine we can also write a program which emulates a chip supporting virtual architecture and run the bytecode.
  8. Runtime

Virtual machine can be separted to a lot of types. The one we are familiar with is system VM which even simulate the hardware environment. The one mentioned here is language VM or process VM.

There are also stories of single-pass compilers, tree-walk interpreters, transpilers (source-to-source compiler), and just-in-time compilation.
For transpilers, it is not translated to a low-level languages. Languages would be translated to a same-level languages, so transpilers are also called as source-to-source compilers. For example, many source-to-source compilers use C as their output language, and it makes sense that C can run efficiently on a lot of architectures. For another example, imagine web browsers as “machine”, then the “machine code” would be Javascript or WebAssembly. We can also use these two languages as output for transpilers if we want to run our code on browsers.

Compiler v.s. Interpreter

I love the way by which the book describe the difference. It is just like the relationship between the term fruit and vegetable. There are some overlapped between two domains, but also something exclusive.
Compiler, which will translate the source code, but won’t execute it (e.g. gcc, clang). While interpreter, which will take in source code and execute immediately (e.g. old version of ruby). What’s interesting is that most of the scripting languages today are both compiler and interpreter. For example, V8 is a javascript engine which uses both compiler and interpreter and follows JIT compilation.
https://v8.dev/_img/ignition-interpreter/ignition-pipeline.png
Ignition is the interpreter, and Turbofan is the compiler. They would communicate with each other to generate optimized code. This is not the focus of this series, we only need to know many language implementations take both interpreter and compiler.

Lox’s universe

Lox is the language we want to implement in this series.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
// Comment start from two slashes
print "Some literal just like python";

// Lox is dynamically typed

// boolean
var a = true;
var a = false;

// null is equal to Nil in Lox
var a;
// a would be default to be Nil

add + me
subtract - me

if (cond) {

}else {

}

while (cond) {

}

// you don't need to specify type of function in declaration
fun funcname(a, b, c) {
   print a + b + c;
}

// some interest use of fun
fun retFunc() {
   var outside = "outside";

   // we even can define another function inside
   fun inner() {
      print outside;
   }

   return inner;
}
var fn = retFunc();
fn();

// Lox is object oriented
class Breakfast {
   var bread;
   // init() can work as constructor
   init(bread) {
      this.bread = bread;
   }
   // don't need keyword of fun in class
   cook() {
      print "I want to cook bread";
   }

   serve() {
      // access field of current object
      print "Enjoy your " + this.bread;
   }
}
// how to new the class
var breakfast = new Breakfast("green onion bread");
breakfast.bread = "French toast";

// if there is a class, then there is also an inheritance with  <
class Brunch < Breakfast {
   drink() {
      print "How about a juice";
   }
}
var benedict = Brunch("muffin");
benedict.serve();

The author also made some terminology clear in this part. An argument is an actual value to be passed to a function, while a parameter is a variable which would hold the value of the argument.

Next

Finally, we have figured out the stuff and its features we want to implement. On next day, I would start implementing scanner with java.

Reference