rocks-lang
Rocks is a programming language written in Rust. It is a dynamically typed language with lexical scoping and first-class functions. Rocks is a tree-walk interpreter with a hand-written recursive descent parser. Rocks is a hobby project and is not intended for production use.
Rocks is a dynamically typed language. This means that the type of a variable is determined at runtime. This is in contrast to statically typed languages, where the type of a variable is determined at compile time. Dynamically typed languages are often easier to use but are generally slower than statically typed languages.
Rocks is a tree-walk interpreter. This means that the interpreter walks the abstract syntax tree (AST) and evaluates each node. This is in contrast to a compiler, which would convert the AST into bytecode or machine code. Tree-walk interpreters are generally easier to implement than compilers but are generally slower than compilers.
Rocks is a hobby project and is not intended for production use. The goal of this project is to learn more about programming languages and interpreters. This project is inspired by the Crafting Interpreters book by Bob Nystrom.
You can install the interpreter using the command below.
cargo install rocks-lang
Scanning
The first step in the interpreter is scanning. Scanning is the process of converting a string of
characters into a list of tokens. A token is a single unit of a programming language. For
example, the string 1 + 2
would be converted into the following tokens:
[Number(1), Plus, Number(2)]
The scanner is implemented in the scanner
module as an iterator over the characters
in the source code. It is a simple state machine that returns the next token in the source code
when called.
The scanner reports syntax errors in the source code as a ScanError
.
These errors are trivial problems like an unterminated string literal or an unexpected character.
Scan errors are reported as soon as they are encountered. This means that the scanner will
continue scanning the source code even if it has already encountered a syntax error. This is
useful because it allows the user to fix multiple syntax errors at once.
Parsing
The second step in the interpreter is parsing. Parsing is the process of converting a list of
tokens into an abstract syntax tree (AST). The parser is implemented in the parser
module as a recursive descent parser. The parser transforms the list of tokens into expressions
and statements. Expressions
are pieces of code that produce a value, specifically an
Object
. Objects are an umbrella term for all types of values in Rocks
including literals, functions, classes and instances. Statements
are pieces of code
that do not produce a value but instead perform some action. These actions modify the state of the
program and thus, are called side-effects. For example, a variable declaration or an if clause
would be classified as statements.
For example, the string print 1 + 2;
would be converted into the following AST:
PrintStatement {
BinaryExpression {
left: Number(1),
operator: Plus,
right: Number(2),
}
}
The parser reports syntax errors in the source code as a ParseError
.
Unlike the scanner, the parser catches errors that span multiple tokens. For example, the
following expression is invalid because it is missing the right-hand operand:
1 !=
However, much like the scanner, the parser will continue parsing the source code even if it has already encountered a syntax error using a technique called synchronization. This is useful because it allows the user to fix multiple syntax errors at once.
Resolving
The third step in the interpreter is resolving. Resolving is the process of statically analyzing
the AST to determine the scope of each variable. While this requires a pre-pass of the AST, it
is necessary to construct robust lexical scoping. The resolver is implemented in the
resolver
module as a tree-walk interpreter. The resolver is run after the parser
because it requires the AST to be fully constructed. The resolver reports errors as a
ResolveError
. These errors are syntactically valid but semantically invalid.
and therefore, cannot be caught by the scanner or the parser. For example, the following expression
is valid a valid Rocks syntax but it is semantically invalid because the variable a
is defined
twice in the same scope:
{
var a = 1;
var a = 2;
}
Interpreting
The final step in the interpreter is interpreting. Interpreting is the process of evaluating the
AST. The interpreter is implemented in the interpreter
module as a tree-walk
interpreter. Thanks to all the previous steps, the interpreter is able to evaluate the AST and produce
a result. The interpreter reports errors as a RuntimeError
. While the
scanner, the parser and the resolver try to catch as many errors as possible before running the
code, most errors can only be caught at runtime. For example, the following expression is valid
Rocks syntax but it is semantically invalid because it tries to add a string and a number:
var a = "123";
var b = a + 123;
The interpreter is also responsible for managing the environment. The environment is a mapping of
variable names to their values. The environment is implemented in the environment
module as a stack of hash maps. Each hash map represents a scope in the program. This allows the
interpreter to implement lexical scoping. The interpreter also manages the call stack.
License: MIT