Most programming language tutorials end the moment the language can print "hello world." That was never interesting to me. I wanted to understand the whole chain: from a string of source code to a running program, and then from a running program to a deployed service that other people could actually use.
So I built Blan, a Turing-complete interpreted language written from scratch in C++17, with a live playground at blan-playground.vercel.app. This post is about how it works, what C++17 features made it correct, and what it took to go from "the language evaluates expressions" to "the language runs in a browser."
What I Wanted to Build
Not a toy. The definition I used for "not a toy" was: does it have all the things you'd need to write a real algorithm?
That meant:
- Variables with assignment
- Arithmetic, comparison, and logical operators with proper precedence
if/elsewith proper nestingwhileloops- Functions with recursion
- Short-circuit evaluation (
&&and||) - String and integer types
Turing-completeness (the ability to compute anything computable) follows from having conditionals and loops. But those features alone also give you enough to write things like Fibonacci, sorting algorithms, and tree traversals, which is what I care about.
Phase 1: The Lexer
The lexer's job is to turn a raw string of source code into a flat list of typed tokens. Characters go in, tokens come out.
A token has a type and (sometimes) a value:
enum class TokenType {
NUMBER, STRING, IDENTIFIER,
PLUS, MINUS, STAR, SLASH,
EQUAL, EQUAL_EQUAL, BANG, BANG_EQUAL,
LESS, LESS_EQUAL, GREATER, GREATER_EQUAL,
AND, OR,
IF, ELSE, WHILE, FUN, RETURN, VAR,
LEFT_PAREN, RIGHT_PAREN, LEFT_BRACE, RIGHT_BRACE,
SEMICOLON, COMMA,
TRUE_LIT, FALSE_LIT, NIL,
END_OF_FILE
};
struct Token {
TokenType type;
std::string lexeme;
int line;
};
The lexer scans character by character. Whitespace and comments are discarded. Numbers collect digits until a non-digit is encountered. Identifiers collect alphanumerics, then check if they match a keyword. Two-character operators (==, !=, <=, >=) peek ahead one character.
Token Lexer::scanToken() {
char c = advance();
switch (c) {
case '+': return makeToken(TokenType::PLUS);
case '-': return makeToken(TokenType::MINUS);
case '*': return makeToken(TokenType::STAR);
case '/': return makeToken(TokenType::SLASH);
case '=':
return makeToken(match('=') ? TokenType::EQUAL_EQUAL : TokenType::EQUAL);
case '!':
return makeToken(match('=') ? TokenType::BANG_EQUAL : TokenType::BANG);
case '<':
return makeToken(match('=') ? TokenType::LESS_EQUAL : TokenType::LESS);
case '>':
return makeToken(match('=') ? TokenType::GREATER_EQUAL : TokenType::GREATER);
// ...
}
}
Nothing surprising here. The lexer is the least intellectually interesting part of a compiler; it's mostly pattern matching. But get it wrong and everything downstream breaks in confusing ways.
Phase 2: The Parser and AST
The parser takes the token list and builds an Abstract Syntax Tree: a tree where each node represents a syntactic construct, and the structure encodes the meaning of the program.
This is where C++17 starts to matter.
The Node Representation Problem
An AST has heterogeneous node types. A BinaryExpression has a left operand, an operator, and a right operand. A VariableDeclaration has a name and an initializer. A WhileStatement has a condition and a body. These are fundamentally different types.
The classical C++ approach is a base class with virtual methods:
struct Expr {
virtual ~Expr() = default;
virtual Value evaluate(Environment& env) = 0;
};
struct BinaryExpr : Expr {
std::unique_ptr<Expr> left;
std::unique_ptr<Expr> right;
Token op;
Value evaluate(Environment& env) override { /* ... */ }
};
This works, but has problems: vtable overhead on every node, dynamic_cast when you need to downcast, and the "forgot to override this virtual method" class of bugs.
C++17 gives a better option: std::variant.
std::variant for Type-Safe Heterogeneous Nodes
struct NumberLiteral { double value; };
struct StringLiteral { std::string value; };
struct BoolLiteral { bool value; };
struct NilLiteral {};
struct BinaryExpr;
struct UnaryExpr;
struct VariableExpr;
struct AssignExpr;
struct CallExpr;
struct LogicalExpr;
using Expr = std::variant<
NumberLiteral,
StringLiteral,
BoolLiteral,
NilLiteral,
std::unique_ptr<BinaryExpr>,
std::unique_ptr<UnaryExpr>,
std::unique_ptr<VariableExpr>,
std::unique_ptr<AssignExpr>,
std::unique_ptr<CallExpr>,
std::unique_ptr<LogicalExpr>
>;
std::variant is a type-safe tagged union. It holds exactly one of its listed types at any time and knows which type it currently holds. Combined with std::visit, it gives pattern-matching-style dispatch:
Value evaluate(const Expr& expr, Environment& env) {
return std::visit([&](const auto& node) -> Value {
return evaluateNode(node, env);
}, expr);
}
The auto& in the lambda is deduced to each variant type in turn. The compiler generates a dispatch table at compile time. If I add a new variant type and forget to add a corresponding evaluateNode overload, I get a compile error, not a runtime crash. This is the key advantage over the virtual method approach.
std::unique_ptr for Ownership
The nodes that contain child expressions use std::unique_ptr:
struct BinaryExpr {
std::unique_ptr<Expr> left;
std::unique_ptr<Expr> right;
Token op;
};
struct IfStmt {
std::unique_ptr<Expr> condition;
std::unique_ptr<Stmt> thenBranch;
std::unique_ptr<Stmt> elseBranch; // nullptr if no else
};
std::unique_ptr expresses single ownership. When a node is destroyed, its children are automatically destroyed: no manual delete, no memory leaks. In a parser that may throw exceptions on syntax errors mid-tree, this is essential. With raw pointers you'd leak every node allocated before the exception. With unique_ptr, the stack unwinds cleanly.
Recursive Descent Parsing
The parser is a collection of functions, one per grammar rule. Each function parses one level of precedence and calls lower-precedence parsers for its operands. This encodes precedence directly in the call stack.
expression → assignment
assignment → logical_or ("=" assignment)?
logical_or → logical_and ("||" logical_and)*
logical_and → equality ("&&" equality)*
equality → comparison (("==" | "!=") comparison)*
comparison → term (("<" | "<=" | ">" | ">=") term)*
term → factor (("+" | "-") factor)*
factor → unary (("*" | "/") unary)*
unary → ("!" | "-") unary | call
call → primary ("(" arguments? ")")*
primary → NUMBER | STRING | "true" | "false" | "nil" | IDENTIFIER | "(" expression ")"
In code:
std::unique_ptr<Expr> Parser::parseEquality() {
auto left = parseComparison();
while (match({TokenType::EQUAL_EQUAL, TokenType::BANG_EQUAL})) {
Token op = previous();
auto right = parseComparison();
left = std::make_unique<Expr>(
std::make_unique<BinaryExpr>(std::move(left), std::move(right), op)
);
}
return left;
}
Each function either produces a node or throws a parse error. The match() helper checks if the current token is one of the given types and advances if so. previous() returns the token that was just consumed.
The call hierarchy directly encodes precedence: parseEquality calls parseComparison, which calls parseTerm, which calls parseFactor, which calls parseUnary, and so on. A + is parsed deeper in the tree than a ==, which means it binds more tightly, which is exactly what we want.
Phase 3: The Tree-Walking Evaluator
The evaluator traverses the AST and computes values. It maintains an environment, a chain of scopes for variable binding.
class Environment {
std::unordered_map<std::string, Value> values;
std::shared_ptr<Environment> enclosing;
public:
Environment(std::shared_ptr<Environment> enclosing = nullptr)
: enclosing(enclosing) {}
void define(const std::string& name, Value value) {
values[name] = std::move(value);
}
Value& get(const std::string& name) {
if (values.count(name)) return values[name];
if (enclosing) return enclosing->get(name);
throw RuntimeError("Undefined variable: " + name);
}
};
When we enter a block ({}), we create a new Environment with a pointer to the enclosing one. When the block exits, the inner environment is destroyed. Variable lookups walk the chain: local scope first, then enclosing scope, then enclosing's enclosing, and so on.
Short-Circuit Evaluation
&& and || require special handling. For a && b, if a is false, b must not be evaluated (it might have side effects, or it might crash). This can't be handled by the standard evaluateNode dispatch that evaluates both operands before applying the operator.
Value evaluateNode(const std::unique_ptr<LogicalExpr>& expr, Environment& env) {
Value left = evaluate(*expr->left, env);
if (expr->op.type == TokenType::OR) {
if (isTruthy(left)) return left; // short-circuit: left is truthy, return it
} else { // AND
if (!isTruthy(left)) return left; // short-circuit: left is falsy, return it
}
return evaluate(*expr->right, env); // only evaluate right if needed
}
LogicalExpr is a separate variant type from BinaryExpr precisely because it needs this special evaluation order. BinaryExpr always evaluates both sides.
Functions and Return Values
Functions are first-class values. A function definition creates a closure: it captures the environment at the point of definition, which enables closures.
struct BlanFunction {
FunctionStmt* declaration;
std::shared_ptr<Environment> closure;
Value call(Interpreter& interp, std::vector<Value> args) {
auto env = std::make_shared<Environment>(closure);
for (size_t i = 0; i < declaration->params.size(); i++) {
env->define(declaration->params[i].lexeme, args[i]);
}
try {
interp.executeBlock(declaration->body, env);
} catch (ReturnValue& ret) {
return ret.value;
}
return nullptr;
}
};
ReturnValue is a C++ exception used as a control-flow mechanism. When a return statement is evaluated, it throws ReturnValue containing the return value. The call() function catches it and extracts the value. This is idiomatic for tree-walking interpreters: it unwinds the call stack cleanly without threading a return value through every evaluator function.
Recursion works automatically: each call to call() creates a new Environment scope, so recursive calls don't interfere with each other's variables.
Phase 4: Deploying It
A Turing-complete language that only runs locally is a local tool. I wanted Blan to be usable in a browser, which meant building around the compiler.
The Go Backend
The compiler binary is a command-line tool that reads source from stdin, executes it, and writes output to stdout. The Go backend wraps this:
func executeCode(source string) (string, error) {
ctx, cancel := context.WithTimeout(context.Background(), 5*time.Second)
defer cancel()
cmd := exec.CommandContext(ctx, "./blan-compiler")
cmd.Stdin = strings.NewReader(source)
var out, stderr bytes.Buffer
cmd.Stdout = &out
cmd.Stderr = &stderr
if err := cmd.Run(); err != nil {
if ctx.Err() == context.DeadlineExceeded {
return "", errors.New("execution timeout")
}
return stderr.String(), nil // compiler error messages go to stderr
}
return out.String(), nil
}
A 5-second timeout prevents infinite loops from hanging the server. The compiler binary runs in a subprocess, so a crash in the interpreter doesn't take down the Go server.
Execution Caching with StrataKV
Blan programs are deterministic: the same source code always produces the same output. Executing the same snippet twice is wasteful. I hash the source with SHA-256 and check a cache before executing:
func handleExecute(w http.ResponseWriter, r *http.Request) {
source := extractSource(r)
hash := sha256Hex(source)
if cached, found := cache.GetCachedOutput(hash); found {
json.NewEncoder(w).Encode(Response{Output: cached, Cached: true})
return
}
output, err := executeCode(source)
if err != nil {
http.Error(w, err.Error(), http.StatusInternalServerError)
return
}
cache.SaveCacheOutput(hash, output)
json.NewEncoder(w).Encode(Response{Output: output, Cached: false})
}
The cache is StrataKV, the LSM-tree storage engine I built for this purpose (see the StrataKV post). It runs embedded in the same process, no network hop, WAL-backed durability across restarts. Cache hits return in microseconds instead of the 50-500ms a compiler execution takes.
Worker Pool
The backend runs multiple compiler processes concurrently, bounded by a worker pool:
type WorkerPool struct {
sem chan struct{}
}
func NewWorkerPool(size int) *WorkerPool {
return &WorkerPool{sem: make(chan struct{}, size)}
}
func (p *WorkerPool) Submit(fn func()) {
p.sem <- struct{}{}
go func() {
defer func() { <-p.sem }()
fn()
}()
}
A buffered channel of capacity size acts as a semaphore. When all slots are occupied, Submit blocks until one is released. This prevents the server from spawning unbounded compiler processes under load.
What Blan Can Do
// Fibonacci
fun fib(n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
print fib(10); // 55
// Closures
fun makeCounter() {
var count = 0;
fun increment() {
count = count + 1;
return count;
}
return increment;
}
var counter = makeCounter();
print counter(); // 1
print counter(); // 2
// Short-circuit evaluation
var x = nil;
if (x != nil && x > 0) {
print "this won't crash";
}
All of that works. Closures, recursion, proper short-circuit evaluation, nested control flow.
What's Still Missing
A bytecode VM instead of tree-walking. A tree-walking interpreter is the simplest correct implementation, but it's slow: every evaluation traverses the tree. A bytecode compiler would first compile the AST to a flat sequence of instructions (like JVM bytecode), and a VM would execute those instructions directly. No tree traversal, better cache locality, significantly faster execution. This is the natural next step.
An error recovery parser. My parser throws on the first syntax error and stops. A good parser continues after errors, reports multiple errors in one pass, and produces a partial AST for the valid portions. This is hard to implement correctly but dramatically improves the user experience.
Static type checking. Blan is dynamically typed, so type errors are discovered at runtime. Adding a type checker pass between parsing and evaluation would catch type errors earlier and open the door to typed language features.
A proper REPL. The current interface is a Monaco editor with a run button. A true REPL with persistent state between evaluations, tab completion, and error highlighting would make Blan more usable for interactive exploration.
The Difference Between Using a Language and Building One
Building a language from scratch means you can't hide from any of it. Every abstraction you normally take for granted (variable scoping, operator precedence, function calls, closures) you have to build yourself. When you finish, you don't just know how these things work. You know why the design decisions were made.
Why does && evaluate left-to-right and short-circuit? Because the alternative requires evaluating both operands, which has observable side effects. Why are closures represented with a captured environment rather than by value? Because functions need to observe mutations to variables in their enclosing scope.
These aren't just academic questions. They're the design constraints that explain why every language you've used works the way it does.
The code is on GitHub and the playground is live at blan-playground.vercel.app. Write some Blan.