No code yet. Before any syntax, three words need defining, because the rest of the chapter leans on all three meaning exactly one thing.
A thread is a separate line of execution that the operating system can run at the same time as another one, usually on a different CPU core. Two threads in the same program share the same memory, which is exactly what makes them fast and exactly what makes them dangerous: nothing stops one thread from reading or writing a piece of memory while another thread is doing the same thing.
A race condition is any bug where the program's answer depends on the order two things happen in, and nothing in the source code fixes that order. A data race is the specific, narrower case that concurrency talks about most: two threads touch the same memory at the same time, at least one of them is writing, and nothing makes them take turns. The result depends on timing you do not control, which means the same program, the same input, run twice, can print two different answers, and the bug can disappear the moment you attach a debugger, because a debugger changes the timing.
Most languages that let you write threads hand you the thread and a lock, which is a flag one thread holds so another thread knows to wait its turn, and then trust you to take the lock every single time you touch shared memory, forever, across every file anyone ever adds to the program. Forget it once and you have a data race that might not show up for a year. izvor bets the other way. Instead of handing you the sharp tool and a rule about how to hold it, it refuses to let the unsafe move parse into a program at all. The cost is a much smaller set of things you can express. Here is what that set looks like, up front.
let data = [1, 2, 3, 4, 5, 6, 7, 8];
var total = 0;
parallel for i in 0..8 reduce total {
total = total + data[i];
}
print total;Eight iterations, split across however many threads the machine has, each one adding its own slice of data into its own private copy of total, combined into the real one only after every thread has finished. This prints 36, every time, on every machine, no matter how many cores it has.
parallel {
print fib(30);
print fib(35);
}Two independent branches, one thread each, joined before the statement after the block runs. Neither branch can see or touch anything the other one writes, because step 5 refuses to compile a program where that would even be possible.
Read the first example again and notice what is missing from it. No thread type. No lock. No word anywhere that means "wait here until someone signals you." Just a loop that says what to compute and a keyword that says it is safe to split up, and a compiler that has already checked that claim before generating a single line of C.
Checkpoint
Clean tree, everything passing, before this chapter touches anything.
Still no code. A feature list is honest only if it is also a list of the features that did not make it, said plainly, with the real cost attached instead of hidden.
a thread type you can holdThe moment a program can hold a thread as a value, it can also forget to join it, hand it a pointer into a stack frame that returns before the thread finishes, or start one and lose track of it. Every one of those is a real bug class in every language that exposes threads directly. izvor removes the value instead of writing rules about how to hold it.
locks and mutexesA lock only protects memory if every access to that memory remembers to take it, forever, including the access someone adds in a file they have never seen this one. A compiler cannot check "every access, forever" against a convention that lives only in a comment. It can check a rule that lives in the grammar.
async and awaitThat model needs a scheduler: something that can pause one piece of work, run another, and come back later. Building a scheduler needs the safe unit of concurrent work this chapter is about to define. There is nothing to make asynchronous yet, so this waits for a chapter that does not exist.
futures and promisesA future is a value standing in for "the answer to this, once it's ready." Representing not-done-yet cleanly needs the same missing scheduler as async and await. Same reason, same gap.
channelsSending messages between threads instead of sharing memory is a completely reasonable design, arguably a better one than this chapter's. izvor doesn't have it because there is no long-lived thread on the other end to send a message to. Every parallel thing in this language starts and ends inside the one construct that spawned it.
a thread pool you configureNothing in izvor lets you ask for six workers. Step 10 is about why that decision belongs to the machine the program is running on, not to the programmer who wrote it once on a different one.
Add those up and the honest sentence is this: izvor cannot write a web server, a background job queue, a producer and consumer pipeline, or anything where one part of a program has to wait indefinitely on another part. Every parallel thing in this language starts inside a statement and finishes, with a hard join, before the next statement runs. That is a much smaller language than Go's or Rust's, on purpose, in exchange for a guarantee neither of those languages gives you by default.
The obvious alternative to any of this is a comment: // do not write to total from
inside this block. Comments do not run. Nothing checks that the next person who
edits this file, six months from now, under deadline, reads it before adding a line that
breaks the rule. A rule enforced by a compile error gets checked on every single build,
by everyone, forever, whether they read the comment or not. That gap, between a rule a
person has to remember and a rule the compiler enforces, is the entire subject of this
chapter.
Checkpoint
Four keywords, one new piece of punctuation, and two additions to NodeType.
Both new node kinds, and the union member the second one needs, go into PLAN.md's locked
list alongside this chapter, the same way chapter 11 added its own.
src/lexer.h · inside the typedef enum, before TOK_EOF
TOK_PARALLEL,Starts both forms this chapter adds.
TOK_FOR,Only ever appears right after parallel. izvor has no plain sequential for loop; while already covers that, and adding a second loop keyword that means the same thing while does would be a second way to write one idea, which is exactly what chapter 7 avoided when it made if and while share one bodies-require-braces rule.
TOK_IN,i in 0..8. Reads like English on purpose; this is the one place in the language a loop variable is introduced, and it should not look like an assignment.
TOK_REDUCE,Introduces the one safe way to combine results across threads, built in step 7.
TOK_RANGE,.., two characters, one token. Not built from two TOK_DOTs in a row; the parser should never have to look at two tokens to know it is looking at a range.
src/lexer.c · inside token_type_name, before the TOK_EOF case
case TOK_PARALLEL: return "PARALLEL"; case TOK_FOR: return "FOR"; case TOK_IN: return "IN"; case TOK_REDUCE: return "REDUCE"; case TOK_RANGE: return "RANGE";src/lexer.c · lexer_next's identifier branch, alongside the existing word_is checks
if (word_is(lx, start, "parallel")) return make_token(lx, TOK_PARALLEL, start);Maximal munch, same as every keyword since chapter 4, protects this the same way it protects let from letter: parallelism eats all ten characters, fails the length check in word_is, and comes back as an ordinary name.
if (word_is(lx, start, "for")) return make_token(lx, TOK_FOR, start); if (word_is(lx, start, "in")) return make_token(lx, TOK_IN, start); if (word_is(lx, start, "reduce")) return make_token(lx, TOK_REDUCE, start);src/lexer.c · the switch (c) at the bottom of lexer_next, replacing the existing case '.' from chapter 11
case '.': if (peek(lx) == '.') {This switch runs after advance(lx) has already consumed the first ., so c is that character and peek is looking at whatever comes right after it, still unconsumed.
advance(lx);Consume the second dot too, so the token's length ends up 2 and make_token reads both characters.
return make_token(lx, TOK_RANGE, start); } return make_token(lx, TOK_DOT, start);One dot, no second one: ordinary field access, exactly chapter 11's case, untouched.
src/ast.h · inside the typedef enum for NodeType, after NODE_STORE
NODE_PARALLEL,parallel { ... }. A statement, not an expression: it produces nothing, it runs things.
NODE_PARALLEL_FOR,src/ast.h · inside union as, after the store member
struct { const char *var; int length; Node *start; Node *end; Node *body;NODE_PARALLEL needs no new member at all. Its body is a list of branches to run concurrently, and struct { NodeList stmts; } block; already means exactly "a list of statements," so it reuses block the same way chapter 5 gave NODE_PRINT and NODE_EXPR_STMT one shared stmt member instead of two identical ones. Only parallel for's extra pieces, a loop variable, a range, and an optional reduction, need a member of their own.
bool has_reduce; const char *reduce_name; int reduce_length; } parallel_for;has_reduce is a real flag, not a sentinel on reduce_name, because NULL already means something else in this codebase: an optional child node that is not there. A borrowed name pointer being NULL should mean the same thing everywhere, and here it would just mean "no reduction," which is worth its own bit instead of overloading one that already has a job.
src/ast.h · constructor declarations, after ast_store
Node *ast_parallel(NodeList stmts);Node *ast_parallel_for(const char *var, int length, Node *start, Node *end,
Node *body, bool has_reduce,
const char *reduce_name, int reduce_length);src/ast.c · after ast_store, before ast_free
Node *ast_parallel(NodeList stmts) { Node *node = new_node(NODE_PARALLEL); if (node == NULL) { return NULL; } node->as.block.stmts = stmts;Writing through the block member on a NODE_PARALLEL node. Legal, because the union member is chosen by name, not by the node's own type tag; the type tag is what later code checks before trusting which member is live, exactly the discipline chapter 5's first trap established.
return node;} Node *ast_parallel_for(const char *var, int length, Node *start, Node *end,
Node *body, bool has_reduce,
const char *reduce_name, int reduce_length) { Node *node = new_node(NODE_PARALLEL_FOR); if (node == NULL) { return NULL; } node->as.parallel_for.var = var; node->as.parallel_for.length = length; node->as.parallel_for.start = start; node->as.parallel_for.end = end; node->as.parallel_for.body = body; node->as.parallel_for.has_reduce = has_reduce; node->as.parallel_for.reduce_name = reduce_name; node->as.parallel_for.reduce_length = reduce_length; return node;}src/ast.c · ast_free's switch, after the NODE_STORE case
case NODE_PARALLEL:Frees through block, matching how it was written.
nodelist_free(&node->as.block.stmts); break; case NODE_PARALLEL_FOR:var and reduce_name are both borrowed from the source, like every other name in this compiler since chapter 5. Nothing to free there.
ast_free(node->as.parallel_for.start); ast_free(node->as.parallel_for.end); ast_free(node->as.parallel_for.body); break;Checkpoint
This should fail, listing every switch over NodeType that
has not met these two yet: eval's in main.c, check_node's in
type.c, and resolve_expr's and resolve_stmt's and
always_returns's, all three in sema.c. That is step 4's job.
One parser branch, then five small, mechanical edits elsewhere. None of the five teaches the compiler anything new about concurrency; they only teach it that these two node kinds exist, so every earlier pass keeps its promise of never silently ignoring one.
Here is the grammar both forms follow, for the comment above the code.
statement -> ... | "parallel" "for" IDENT "in" expression ".." expression ( "reduce" IDENT )? block | "parallel" "{" statement* "}"src/parser.c · inside parse_statement, alongside the other keyword-led branches, before the fallback expression-statement case at the bottom
if (parser_check(p, TOK_PARALLEL)) { long offset = p->current.start - p->lexer.src; parser_advance(p); /* 'parallel' */ if (parser_match(p, TOK_FOR)) {Look one token ahead by consuming it: if for follows parallel, this is a parallel for, and every remaining token belongs to that form.
if (!parser_check(p, TOK_IDENT)) { error_at(p, "expected a loop variable after parallel for"); return NULL; } const char *var = p->current.start; int var_length = p->current.length; parser_advance(p); if (!parser_match(p, TOK_IN)) { error_at(p, "expected 'in' after the loop variable"); return NULL; } Node *start = parse_expression(p); if (start == NULL) return NULL; if (!parser_match(p, TOK_RANGE)) { error_at(p, "expected '..' in a parallel for range"); ast_free(start); return NULL; } Node *end = parse_expression(p); if (end == NULL) { ast_free(start); return NULL; } bool has_reduce = false;Defaulted to no reduction. Step 7 is the only thing that turns this on.
const char *reduce_name = NULL; int reduce_length = 0; if (parser_match(p, TOK_REDUCE)) { if (!parser_check(p, TOK_IDENT)) { error_at(p, "expected a variable name after reduce"); ast_free(start); ast_free(end); return NULL; } has_reduce = true; reduce_name = p->current.start; reduce_length = p->current.length; parser_advance(p); } Node *body = parse_block(p);The same block parser if, while and fn bodies already call, unmodified. It consumes the braces itself and hands back a NODE_BLOCK, which is exactly what parallel_for.body expects.
if (body == NULL) { ast_free(start); ast_free(end); return NULL; } return at(ast_parallel_for(var, var_length, start, end, body,
has_reduce, reduce_name, reduce_length), offset); } NodeList stmts;Plain parallel { ... }. Inlined rather than calling parse_block, because parse_block hands back a NODE_BLOCK wrapping the list, and NODE_PARALLEL needs the raw NodeList itself, not a block node wrapped around it. The loop below is the same shape parser_parse's own top-level loop has used since chapter 5.
nodelist_init(&stmts); if (!parser_match(p, TOK_LBRACE)) { error_at(p, "expected '{' after parallel"); return NULL; } while (!parser_check(p, TOK_RBRACE) && !parser_check(p, TOK_EOF)) { Node *stmt = parse_statement(p); if (stmt == NULL) { nodelist_free(&stmts); return NULL; } if (!nodelist_push(&stmts, stmt)) { ast_free(stmt); nodelist_free(&stmts); return NULL; } } if (!parser_match(p, TOK_RBRACE)) { error_at(p, "expected '}'"); nodelist_free(&stmts); return NULL; } return at(ast_parallel(stmts), offset); }
parse_statement reads the token after reduce and stores it. It
does not ask whether a variable by that name is in scope, whether it was declared with
var, or whether anything inside the loop body actually writes to it. That
is not an oversight; it is the same separation chapter 6 drew between grammar and
meaning, applied again. The parser's only job is to recognize the shape
reduce IDENT and remember the name. Whether that name means anything is a
question for a later pass that actually has a symbol table, which the parser has never
had and should not grow one just for this.
Now the five small edits. First, the evaluator, which chapter 11 already taught to refuse
every aggregate node outright rather than grow ExecResult past one
long. A parallel construct gets the same answer, for a related reason: there
is no honest way for a single-threaded tree walker to demonstrate what a multi-threaded
program does, so it does not try.
src/main.c · inside eval's switch, after chapter 11's aggregate-refusal cases
case NODE_PARALLEL: case NODE_PARALLEL_FOR: { diag_error(src, node->offset, "parallel constructs only run through the compiled path"); ExecResult r = { 0, false, false }; return r; }src/type.c · inside check_node's switch, grouped with NODE_PRINT and NODE_EXPR_STMT's plain TYPE_VOID result
case NODE_PARALLEL: case NODE_PARALLEL_FOR: return (Type){ .kind = TYPE_VOID };src/sema.c · inside always_returns's switch, grouped with NODE_LET through NODE_FN's existing return false;
case NODE_PARALLEL: case NODE_PARALLEL_FOR: return false;src/sema.c · inside resolve_expr's switch, grouped with the other statement kinds it can never actually receive
case NODE_PARALLEL: case NODE_PARALLEL_FOR:
Last, resolve_stmt, which is the one edit here that does real work: a
parallel for's range expressions and its loop variable both need the same
undefined-name checking every other expression and binding gets.
src/sema.c · inside resolve_stmt's switch, after the NODE_RETURN case
case NODE_PARALLEL:Each branch resolves against the same scope the parallel statement itself sits in, because branches are siblings running at the same time, not a sequence where one can see what an earlier one declared.
for (int i = 0; i < stmt->as.block.stmts.count; i++) { resolve_stmt(stmt->as.block.stmts.items[i], scope, &stmt->as.block.stmts, i, src); } break; case NODE_PARALLEL_FOR: {The range is checked against the outer scope, before the loop variable exists. The loop variable itself is not reassignable, false here, the same choice chapter 8 already makes for every function parameter and for the same reason: nothing inside the body should be able to change which iteration it is looking at out from under the loop.
resolve_expr(stmt->as.parallel_for.start, scope, stmts, index, src); resolve_expr(stmt->as.parallel_for.end, scope, stmts, index, src); SemaScope inner; scope_init(&inner, scope); scope_define(&inner, stmt->as.parallel_for.var, stmt->as.parallel_for.length, false); resolve_stmt(stmt->as.parallel_for.body, &inner, NULL, 0, src); break; }
Notice what this buys for free. reduce total inside a loop where
total was never declared now gets sema's ordinary 'total' is not
declared message, from code this chapter did not have to write. Chapter 8 already
owns that question; this chapter only had to make sure a parallel for's range
and loop variable are visible to it.
Checkpoint
Both forms parse, every switch over NodeType in the project is complete
again, and undefined names inside a parallel for's range or reduce clause
are already caught. Nothing yet stops the one mistake this chapter exists for: writing
to a variable from outside the construct. That is step 5.
This is the chapter. Everything before this step built the syntax; everything after it builds on the guarantee this step makes true. A new file, a scope chain of its own, and one rule: a write, inside a parallel construct, to a name that scope chain says was declared outside it, is refused.
What counts as a write. izvor has exactly two statement kinds that change a variable
after it is declared: NODE_ASSIGN, x = ...;, from chapter 5, and
NODE_STORE, a[0] = ...; or p.x = ...;, from chapter
11. Nothing else in the language mutates anything. An expression can read a variable as
many times as it wants; only these two node kinds ever write one. That fact is what makes
this pass small: it does not need to walk into a single expression tree looking for
trouble, because no expression can hide a write inside it. It only needs to find every
NODE_ASSIGN and NODE_STORE in a parallel construct's body and
ask, for each one, where the name it targets was declared.
src/conc.h · new file
/* Concurrency safety: refuses a write, inside a parallel construct, to
any variable declared outside it. Runs after sema, before codegen. */#ifndef IZVOR_CONC_H#define IZVOR_CONC_Htypedef struct NodeList NodeList;/* conc_check_program - walk the whole program, and inside every
parallel construct, refuse a write to a name declared outside it.
Returns the number of refusals. Zero means it is safe to hand to
codegen. */Same shape as sema_check_program: a count instead of a bool, so the driver can print every refusal in one file rather than stopping at the first.
int conc_check_program(const NodeList *program, const char *src);#endif
Now the scope chain. It looks like chapter 8's SemaScope, and that is not an
accident; both exist to answer "where was this name declared" without a runtime value
anywhere near them. The one thing this one needs that chapter 8's never did is a depth,
because the rule this pass enforces is entirely about how deep a declaration sits relative
to a parallel construct's boundary.
src/conc.c · new file, top of the file
#include <stdbool.h>#include <stdio.h>#include <string.h>#include "ast.h"#include "conc.h"#include "diag.h" #define MAX_CONC_NAMES 64 typedef struct ConcScope {A different type from SemaScope, in a different file, on purpose. Chapter 8 already made this call once: a second, unrelated meaning bolted onto an existing structure makes every future reader ask which one a given call is about. This pass has its own question to answer, so it gets its own small chain to answer it with.
struct ConcScope *parent; int depth;The one field SemaScope never needed. Zero at the program's top level, one deeper for every scope nested inside that. Step 5's whole rule is a comparison against this number.
struct { const char *name; int length; } items[MAX_CONC_NAMES]; int count;} ConcScope; static void scope_init(ConcScope *scope, ConcScope *parent) { scope->parent = parent; scope->depth = (parent == NULL) ? 0 : parent->depth + 1;Computed once, here, rather than re-walked every time something asks. A scope's depth never changes after it is created, so there is nothing to keep in sync.
scope->count = 0;} static void scope_define(ConcScope *scope, const char *name, int length) { if (scope->count < MAX_CONC_NAMES) { scope->items[scope->count].name = name; scope->items[scope->count].length = length; scope->count++; }} /* scope_depth_of - the depth of the scope that declared this name, or
-1 if this chain never declared it. An undeclared name is chapter
8's problem, already caught by the time this pass runs; this
function just needs to not crash on one. */A program that reached this pass already passed sema_check_program with zero errors, so every name this pass looks up should exist. -1 is defensive, not load bearing.
static int scope_depth_of(ConcScope *scope, const char *name, int length) { for (ConcScope *s = scope; s != NULL; s = s->parent) { for (int i = 0; i < s->count; i++) { if (s->items[i].length == length && memcmp(s->items[i].name, name, (size_t)length) == 0) { return s->depth; } } } return -1;}
One more small helper before the walk itself. A NODE_STORE's target is an
arbitrary expression, a[0] or p.x, and what this pass actually
needs is the variable underneath it: which array, which struct. Chapter 11 never lets an
array hold a struct or a struct hold an array, so a[0]'s array and
p.x's object are always a plain name, never another index or field
expression. This never has to climb more than one level.
src/conc.c · below the scope functions
static Node *lvalue_root(Node *target) { if (target->type == NODE_INDEX) { return target->as.index.array; } if (target->type == NODE_FIELD) { return target->as.field.object; } return target;Anything else, meaning a plain NODE_IDENT, already is the root.
}
Every other function in this compiler that branches on a NodeType does it
with a switch and no default:, so the compiler lists what got
missed. lvalue_root breaks that pattern deliberately. It only ever receives
three kinds of node, guaranteed by the parser: NODE_IDENT,
NODE_INDEX, or NODE_FIELD. A switch covering only those three,
with no default, would force writing out the other nineteen node kinds just to satisfy
-Werror, for a function that can structurally never see them. An if-chain
says the same thing more honestly: check for the two special shapes, and anything else
is already the answer.
Now the walk. It carries a scope, a boundary, and, only when the current construct is a
reducing parallel for, the one name that construct's reduction is allowed to
write.
src/conc.c · below lvalue_root
static int error_count; /* check_write - refuse this write unless it is either a fresh local
created inside the construct, or the one name a reduction may
write. boundary is the scope that existed right before the
enclosing parallel construct began. */Everything this whole chapter is for lives in the four lines after the comment.
static void check_write(const char *name, int length, long offset, ConcScope *scope, ConcScope *boundary, const char *reduce_name, int reduce_length, const char *src) { int depth = scope_depth_of(scope, name, length); if (depth < 0 || depth > boundary->depth) {The whole rule, in one comparison. depth < 0 means chapter 8 already has a name for this problem and it is not this one. depth > boundary->depth means the declaration lives in a scope created after the parallel construct began, a loop variable or a fresh local, private to whichever thread runs this code. Either way, nothing to refuse.
return; } if (reduce_name != NULL && length == reduce_length &&The one exemption. Step 7 is what makes this safe rather than a loophole: the combine step this write feeds into happens once, after every thread has already finished, never while more than one of them is running.
memcmp(name, reduce_name, (size_t)length) == 0) { return; } error_count++; diag_error(src, offset, "'%.*s' is written inside a parallel block, and it was declared outside it", length, name); fprintf(stderr,Step 6 explains why this is a plain fprintf and not a second argument to diag_error.
"note: this write can land on any thread, in any order: a data race\n" "note: three ways out: make it a reduction, declare it inside the\n" " block, or run this part sequentially\n");}And the statement walker that calls it. Reading this top to bottom is reading the entire shape of the language again, from the angle of "can this write to something."
src/conc.c · below check_write
static void walk_stmt(Node *stmt, ConcScope *scope, ConcScope *boundary,boundary is NULL whenever the walk is not currently inside any parallel construct. Writes are none of this pass's business out there; chapter 8 already owns ordinary mutability.
const char *reduce_name, int reduce_length, const char *src) { switch (stmt->type) { case NODE_NUMBER:Ten node kinds that can never actually arrive here, because walk_stmt is only ever called on something sitting in statement position. Listed anyway: the switch cannot tell the difference between "impossible here" and "forgotten," and it should not have to trust a comment over the compiler, the same reasoning chapter 8 gives for the identical situation in resolve_expr.
case NODE_IDENT: case NODE_UNARY: case NODE_BINARY: case NODE_BOOL: case NODE_CALL: case NODE_INDEX: case NODE_FIELD: case NODE_ARRAY: case NODE_STRUCT_LIT: break; case NODE_LET:Declared into scope unconditionally, whether or not a parallel construct is active, because a later sibling statement, possibly its own nested parallel construct, needs an accurate depth for this name regardless.
case NODE_VAR: scope_define(scope, stmt->as.binding.name, stmt->as.binding.length); break; case NODE_ASSIGN: if (boundary != NULL) { check_write(stmt->as.binding.name, stmt->as.binding.length, stmt->offset, scope, boundary, reduce_name, reduce_length, src); } break; case NODE_STORE: { if (boundary != NULL) { Node *root = lvalue_root(stmt->as.store.target); check_write(root->as.ident.name, root->as.ident.length, stmt->offset, scope, boundary, reduce_name, reduce_length, src); } break; } case NODE_PRINT: case NODE_EXPR_STMT: case NODE_RETURN: case NODE_STRUCT_DECL: break; case NODE_BLOCK: { ConcScope inner; scope_init(&inner, scope); for (int i = 0; i < stmt->as.block.stmts.count; i++) { walk_stmt(stmt->as.block.stmts.items[i], &inner, boundary, reduce_name, reduce_length, src); } break; } case NODE_IF:No new scope for the branches themselves; each branch is a NODE_BLOCK, and that case above already pushes one. boundary and the reduction pass straight through unchanged, because an if inside a parallel construct is still the same construct.
walk_stmt(stmt->as.if_stmt.then_branch, scope, boundary, reduce_name, reduce_length, src); if (stmt->as.if_stmt.else_branch != NULL) { walk_stmt(stmt->as.if_stmt.else_branch, scope, boundary, reduce_name, reduce_length, src); } break; case NODE_WHILE: walk_stmt(stmt->as.while_stmt.body, scope, boundary, reduce_name, reduce_length, src); break; case NODE_FN: {A function declaration always sits at the top level, chapter 7's rule, so it is never actually reached with boundary != NULL in practice. Written to reset it to NULL anyway, because a function's body is a fresh scope universe that does not inherit anything from wherever its declaration happens to sit, the identical reasoning chapter 8's own NODE_FN case gives for parenting to global_scope instead of the caller.
ConcScope inner; scope_init(&inner, scope); for (int i = 0; i < stmt->as.fn.params.count; i++) { Node *param = stmt->as.fn.params.items[i]; scope_define(&inner, param->as.ident.name, param->as.ident.length); } walk_stmt(stmt->as.fn.body, &inner, NULL, NULL, 0, src); break; } case NODE_PARALLEL: {The boundary for everything inside this construct is scope, the scope that already existed the moment this statement was reached. Every branch shares one fresh frame, inner, so a let declared as one branch is visible, for this pass's bookkeeping, to the branches after it, even though at run time the branches do not execute in sequence at all. A tighter version would give every branch its own frame; this chapter does not, because the common case is a handful of independent statements with nothing declared between them, and the difference only matters for a program shape this chapter's own examples never produce.
ConcScope inner; scope_init(&inner, scope); for (int i = 0; i < stmt->as.block.stmts.count; i++) { walk_stmt(stmt->as.block.stmts.items[i], &inner, scope, NULL, 0, src); } break; } case NODE_PARALLEL_FOR: {Same idea as NODE_PARALLEL: the boundary is scope, captured before the loop variable's own frame exists. rname/rlen come from the node's own has_reduce flag, so a plain, non-reducing parallel for passes NULL/0 through and every write inside it is refused, exactly like a plain parallel block.
ConcScope inner; scope_init(&inner, scope); scope_define(&inner, stmt->as.parallel_for.var, stmt->as.parallel_for.length); const char *rname = stmt->as.parallel_for.has_reduce ? stmt->as.parallel_for.reduce_name : NULL; int rlen = stmt->as.parallel_for.has_reduce ? stmt->as.parallel_for.reduce_length : 0; walk_stmt(stmt->as.parallel_for.body, &inner, scope, rname, rlen, src); break; } }}src/conc.c · bottom of the file
int conc_check_program(const NodeList *program, const char *src) { error_count = 0; ConcScope root; scope_init(&root, NULL); for (int i = 0; i < program->count; i++) { walk_stmt(program->items[i], &root, NULL, NULL, 0, src); } return error_count;}
Every pass before this one in the course, the type checker, sema, eventually codegen,
spends most of its code recursing into expressions: operands of a binary operator,
arguments of a call, the value being assigned. walk_stmt never does. It
cannot, because there is nothing to find in there: izvor has no expression that performs
a write, only two statement kinds do, and both are handled directly. A function call
buried three levels deep inside an arithmetic expression cannot secretly mutate anything
this pass would need to notice, at least not through syntax this pass can see. Step 8 is
about the part of that sentence doing the most work: through syntax this pass can
see.
Last, wire it into the pipeline, right after the check that already gates codegen.
src/main.c · right after the existing sema_check_program check, before codegen_program is called
if (conc_check_program(&program, src) > 0) { nodelist_free(&program); return 1; }Checkpoint
Clean build. Nothing calls conc_check_program from a test yet, but the pass
itself compiles and the pipeline calls it. Step 6 is what it actually says when it
refuses something.
Every other diagnostic in izvor tells you about a mistake in one statement. This one has to convince someone their instinct, "just add to the shared total from both threads," is wrong, and it has to do that without the person needing to already understand what a data race is.
Here is the program that trips it.
let data = [1, 2, 3, 4, 5, 6, 7, 8];var total = 0;parallel for i in 0..8 {No reduce total here. That is the whole mistake.
total = total + data[i];}
Before the rendered error, the concrete reason this is broken, since "just adding a number"
sounds harmless. total = total + data[i]; is not one indivisible step even
though it looks like one line. It is read total, compute the sum, write
total, three separate actions. Say two threads run it at the same instant.
Both read total as 5. Thread A adds its 2 and writes back 7. Thread B, which
already read the old 5 before A wrote anything, adds its 3 and writes back 8. The final
value is 8. It should be 10. One thread's contribution vanished, silently, and which
thread loses depends on an instant of timing nobody controls and nothing in the source
text records. That is what a data race actually costs you: not a crash, a wrong answer
that looks exactly like a right one.
Here is exactly what compiling that file prints.
diag_error's whole contract, fixed since chapter 3, is one message and one
caret, computed from one offset. It was never built to print anything after the caret
block, and changing that contract now, for one call site in one chapter, would mean
every other caller's output could shift too. So the extra guidance is a second, separate
write to stderr, right after the located error, using a plain
fprintf that owns no location of its own because it does not need one: the
three ways out are true regardless of which line triggered this, so there is nothing for
a caret to point at.
The three ways out, named plainly rather than left for the reader to invent.
parallel for i in 0..8 reduce total { ... }Make it a reduction. Step 7. The right fix whenever what you are actually doing is combining many values into one.
parallel for i in 0..8 { let squared = data[i] * data[i]; print squared; }Declare it inside the block. A name declared fresh, per iteration, never needs combining with anything, because nothing outside the construct is waiting to read it.
var i = 0; while i < 8 { total = total + data[i]; i = i + 1; }Run it sequentially. Sometimes the honest answer is that this part was never going to benefit from more than one thread, and an ordinary while loop is the correct tool.
Checkpoint
You should see the exact block above, word for word.
A reduction combines many values, one produced per thread, into a single final value, using an operation where the order you combine them in does not change the answer. That property is what makes a reduction safe to split across threads in the first place.
izvor supports exactly one combining operation: addition. That is a real restriction, not
a hidden one, and it earns its keep for a specific reason. Addition is associative:
(2 + 3) + 4 equals 2 + (3 + 4), so it does not matter which
partial results get added to which other partial results first, or in what order the
threads finish. Subtraction does not have that property, (10 - 3) - 2 is not
10 - (3 - 2), so a "reducing subtraction" would give a different answer
depending on thread scheduling, which is exactly the bug this whole chapter exists to
rule out. Restricting reductions to an operation that is actually safe to reorder is not a
simplification for this chapter's sake. It is the reason a reduction is allowed to be an
exception to step 5's rule at all.
One operation covers more than it sounds like it should. Summing values is addition, plainly. Counting how many iterations matched something is also addition, of 1, once per match:
let data = [1, 2, 3, 4, 5, 6, 7, 8];
var total = 0;
parallel for i in 0..8 reduce total {
total = total + data[i];
}Sum. 36.
let data = [1, 2, 3, 4, 5, 6, 7, 8];
var count = 0;
parallel for i in 0..8 reduce count {
if data[i] > 4 {
count = count + 1;
}
}Count. 4. A write to count inside an if, still inside the loop's own construct; step 5's NODE_IF case passes reduce_name straight through, so this is still recognized as the reduction, not refused.
Multiplying partials together, keeping a running maximum, appending to a shared list:
those are all real reductions, used constantly in real parallel code, and none of them are
supported here. That is a genuine limitation of this chapter's design, stated plainly
rather than smoothed over. It also means step 5's check_write never actually
verifies that a reduce clause's body has the accumulating shape shown above; it only
checks that the write targets the declared accumulator by name. Writing
reduce total and then setting total = 5; unconditionally inside
the loop would compile, and would just produce a number nobody wanted, not a crash and not
a race. The language trusts the programmer to write a combining expression that actually
combines, the same way it already trusts a reduce clause's target to make
sense; catching a reduction that "compiles but does something silly" is a different, much
fuzzier problem than catching a data race, and this chapter draws the line at the race.
It would be reasonable to expect a ReduceKind enum, REDUCE_SUM
and REDUCE_COUNT, the same way TypeKind lists TYPE_INT
and TYPE_BOOL. There isn't one, because there is only one operation:
addition of two longs. "Count" is not a second thing the compiler needs to
know how to do; it is a name for a particular way of using the first thing. Adding a
second enum value that maps to the exact same generated C as the first one would be a
distinction the compiler carries and the programmer never benefits from.
Checkpoint
Parses, checks, and compiles clean for both examples above. Step 9 is what the generated C for the sum actually looks like.
No code in this step. A safety feature that oversells itself is worse than one that states its edges plainly, because the first kind gets trusted past where it actually reaches.
Step 5's trap already said it once: the check only sees writes through syntax it can see. Two real, unclosed gaps follow directly from that.
calling a function that writes a globalparallel { bump_counter(); bump_counter(); } compiles cleanly, every time, no refusal. walk_stmt sees a call, and a call is one of the ten node kinds it never looks inside; step 5 said plainly that no expression can hide a write, which is true, but a call can hide one, several statements away, inside bump_counter's own body, in a file this pass may never even open. If that function does counter = counter + 1; against some variable declared far outside either branch, both branches racing on it is exactly the bug this chapter exists to prevent, and it sails through untouched.
anything touching the outside worldTwo branches that both print are still racing, in the sense that which line comes out first is unpredictable from one run to the next. The compiler has no way to refuse this, because print does not touch an izvor variable at all; there is nothing in as.stmt.value for check_write to have an opinion about. The same is true of anything else that reaches past the program's own memory: a file, a socket, a shared resource on the machine the program happens to run on.
Put plainly: izvor's guarantee is "no data race the compiler can see in your own variables," not "no data race, full stop." That is a real, useful guarantee, and it is also a smaller one than "concurrency you cannot get wrong" sounds like it might be. Both sentences are true at once. A tool that only states the first one is honest. A tool that lets you believe the second one, without saying so, is not.
Checkpoint
Both forms compile to POSIX threads, pthread_create and
pthread_join, from <pthread.h>. Said plainly, up front:
this ties every binary izvor produces from here on to a platform that has pthreads. Linux
and macOS do. Plain Windows does not, without a compatibility layer. Chapter 10's
run_clang also needs one line added, -lpthread on the link
command, or the generated code will not link at all.
codegen.c gains one file-scope counter, so two parallel constructs in the
same program get two different struct and function names in the generated C rather than
colliding.
src/codegen.c · near the top, alongside any other file-scope state codegen_program resets
static int parallel_site_count;
Start with parallel for, since the reduction makes it the fuller example.
Here is the source again, and the C emit_stmt writes for it.
let data = [1, 2, 3, 4, 5, 6, 7, 8];
var total = 0;
parallel for i in 0..8 reduce total {
total = total + data[i];
}
print total;typedef struct { long *iz_data;A pointer, not a copy. Chapter 11's arrays are already real C arrays, which decay to a pointer the moment they are passed anywhere, so every worker reads the same eight longs the enclosing function already owns. Reading concurrently is always safe; step 5 only ever refused writes.
long start; long end; long partial;This worker's own copy of the accumulator, and only this worker ever touches it. No two threads share a partial, so there is nothing here for a debugger or a sanitizer to ever catch a race on.
} iz_parallel_1_args; static void *iz_parallel_1_thread(void *raw) {The exact signature pthread_create requires: one void * in, one void * out. Everything this thread needs arrives through that one pointer.
iz_parallel_1_args *a = (iz_parallel_1_args *)raw; long iz_total = 0;A fresh local named after the reduction's accumulator. Inside this function, every use of total from the izvor source compiles to this local, never to the real iz_total back in the caller. That substitution is the entire mechanism: the izvor-level rule said only the reduction may write total, and codegen honors that by giving each thread a total of its own to write.
for (long iz_i = a->start; iz_i < a->end; iz_i++) { iz_total = iz_total + a->iz_data[iz_check_index(iz_i, 8)]; } a->partial = iz_total;The only line that writes through the shared args pointer, and it happens exactly once, after this thread's own loop has already finished. Nothing else ever writes a->partial, and nothing reads it until pthread_join below has returned, so there is no window where two threads could touch it together.
return NULL;}{ long iz_data[8] = {1, 2, 3, 4, 5, 6, 7, 8}; long iz_total = 0; int iz__workers = iz_worker_count();Step 10. Decided once, at run time, never a compile-time constant.
pthread_t iz__threads[IZ_MAX_WORKERS];A fixed-size array, not one sized by iz__workers at run time. The trap right after this listing is about exactly this line.
iz_parallel_1_args iz__args[IZ_MAX_WORKERS]; long iz__chunk = (8 + iz__workers - 1) / iz__workers;Ceiling division. Eight iterations split four ways is chunks of two; split three ways, this gives three, three, two, so nobody is left out and no chunk goes past the end.
int iz__spawned = 0; for (int iz__w = 0; iz__w < iz__workers; iz__w++) { long lo = (long)iz__w * iz__chunk; if (lo >= 8) break; long hi = lo + iz__chunk;More workers than there is work for is normal, not an error: eight iterations on a sixty-four core machine leaves most workers with nothing to do, and this loop's own break above is what stops spawning threads once the work runs out, rather than spawning sixty-four threads for eight numbers.
if (hi > 8) hi = 8; iz__args[iz__spawned].iz_data = iz_data; iz__args[iz__spawned].start = lo; iz__args[iz__spawned].end = hi; pthread_create(&iz__threads[iz__spawned], NULL, iz_parallel_1_thread, &iz__args[iz__spawned]); iz__spawned++; } for (int iz__w = 0; iz__w < iz__spawned; iz__w++) {Join every thread before combining anything. Reading iz__args[iz__w].partial before its own thread has finished writing it would be exactly the kind of race this whole language exists to rule out, so codegen never does it: pthread_join on line below is what guarantees the write already happened.
pthread_join(iz__threads[iz__w], NULL); iz_total = iz_total + iz__args[iz__w].partial; } printf("%ld\n", (long)iz_total);}
pthread_t iz__threads[iz__workers];, sized directly by the run-time worker
count, is legal C11: variable-length arrays are a real feature, not a typo for C99. Two
reasons codegen does not use one anyway. First, C11 made VLA support optional, guarded
by __STDC_NO_VLA__; code that depends on one is not something every
conforming C11 compiler is required to accept, and this project has cared about
portability since chapter 2's fuzzer ran on two operating systems. Second, and more in
keeping with the rest of this codebase, an unbounded stack allocation sized by whatever
the hardware happens to report is exactly the kind of honesty-about-limits problem
MAX_SCOPE_NAMES, MAX_STRUCT_FIELDS and
MAX_FUNCTIONS already solved the same way, elsewhere in this compiler. A
fixed cap, checked once, is a smaller commitment than a stack frame that grows with
whoever's CPU the binary happens to run on.
Now the plain parallel block, which is simpler in shape but has to solve a
problem the loop version does not: two branches that read an outer variable, sharing one
captured copy of it, safely, because step 5 already proved neither branch writes it.
let shared = compute_base();
parallel {
print shared + compute_left();
print shared + compute_right();
}typedef struct { long shared; } iz_parallel_2_args; static void *iz_parallel_2_branch_0(void *raw) {One function per branch statement, not one per parallel block. "One thread per branch," from step 1, means literally this: N statements in the block become N functions and N threads.
iz_parallel_2_args *a = (iz_parallel_2_args *)raw; printf("%ld\n", (long)(a->shared + iz_compute_left())); return NULL;} static void *iz_parallel_2_branch_1(void *raw) { iz_parallel_2_args *a = (iz_parallel_2_args *)raw; printf("%ld\n", (long)(a->shared + iz_compute_right())); return NULL;}{ long iz_shared = iz_compute_base(); iz_parallel_2_args iz__args = { iz_shared };One struct, shared by both threads, both holding only a pointer to it. Safe with no lock, because shared is read-only here: neither branch's own statement is a write, and step 5 already checked that before codegen ever ran.
pthread_t iz__t0, iz__t1; pthread_create(&iz__t0, NULL, iz_parallel_2_branch_0, &iz__args); pthread_create(&iz__t1, NULL, iz_parallel_2_branch_1, &iz__args); pthread_join(iz__t0, NULL); pthread_join(iz__t1, NULL);}Checkpoint
--keep-c is chapter 10's flag; this is exactly the file it should leave
behind. Reading it back should look like a program a person wrote, the same claim
chapter 9 made for every generated file before this one.
Nowhere in this chapter does the compiler pick a number of threads. It could not pick a good one if it tried: the number of cores on the machine that eventually runs the binary is not knowable at compile time, and baking in a guess bakes in a guess that is wrong on every machine except the one it was tuned for.
src/codegen.c · emitted once, only into a generated file that actually contains a parallel construct, alongside iz_check_index
#include <pthread.h>#include <unistd.h>For sysconf. Both includes only ever appear in a generated file that uses parallel or parallel for somewhere; a program with neither still compiles to exactly the dependency-light C chapter 9 promised.
#define IZ_MAX_WORKERS 64 static int iz_worker_count(void) {Asks the operating system, at the moment this binary actually starts running, rather than trusting a number the compiler wrote down weeks or months earlier on a different machine.
long n = sysconf(_SC_NPROCESSORS_ONLN); if (n < 1) n = 1;sysconf can return -1 if the query fails. One worker, running everything itself, is always a correct fallback; it just does the work sequentially inside the thread machinery instead of skipping it, which is why nothing about this chapter's guarantee depends on more than one thread ever actually running.
if (n > IZ_MAX_WORKERS) n = IZ_MAX_WORKERS; return (int)n;}
_SC_NPROCESSORS_ONLN is POSIX, not C11, and POSIX is exactly what
<pthread.h> already committed this generated code to back in step 9. This
function does not add a new platform limitation on top of that one; it is the same
limitation, paid for once, showing up again in a second header.
src/main.c · wherever run_clang builds its argument list, chapter 10
"-lpthread"Added to the clang invocation only when codegen_program reports that the file it just wrote used at least one parallel construct, the same kind of "only when needed" call chapter 11 already made for emitting iz_check_index once per file rather than always.
Checkpoint
Two different kinds of test, because this chapter makes two different kinds of promise. One says a parallel program computes the right answer. The other says a broken one gets refused, in exactly the words step 6 fixed.
Chapter 9 turned the tree-walking evaluator into an oracle: run a program both ways,
through eval and through the compiled C, and fail the test if they disagree.
That trick does not reach this chapter, because step 4 made eval refuse
every NODE_PARALLEL and NODE_PARALLEL_FOR outright. There is no
second, in-process way to compute what a parallel program should print. So the oracle
here is a second program instead of a second code path: the same computation,
written once with parallel for and once with an ordinary while
loop, both compiled through chapter 10's real pipeline, both run as native binaries, and
their stdout diffed byte for byte.
tests/fixtures/sum_parallel.iz and tests/fixtures/sum_sequential.iz · new files, same computation
// sum_parallel.iz
let data = [1, 2, 3, 4, 5, 6, 7, 8];
var total = 0;
parallel for i in 0..8 reduce total {
total = total + data[i];
}
print total;// sum_sequential.iz
let data = [1, 2, 3, 4, 5, 6, 7, 8];
var total = 0;
var i = 0;
while i < 8 {
total = total + data[i];
i = i + 1;
}
print total;tests/test_conc_1.c · new file
What it does, in order, shaped like every other test file in this project:
compile both fixtures through the real chapter 10 pipelineNot the evaluator. The actual clang invocation, into two temporary native binaries.
run the sequential binary once, capture its stdoutrun the parallel binary fifty times, capture each run's stdoutOnce would only prove one particular scheduling of the threads happened to work. Fifty is not a proof either, but a codegen bug in the chunk-boundary arithmetic from step 9, an off-by-one in lo or hi, is far more likely to surface across fifty runs than one.
assert every one of the fifty matches the sequential run, exactlyByte for byte. Any disagreement, even once in fifty, is a real bug: either in this chapter's codegen, or, if it somehow traced back to program logic, in step 5's check for having let something through it should not have.
Now the refusal side, a golden test, the same mechanism chapter 3 built for
tests/golden/unclosed-paren.iz.
tests/golden/parallel-write.iz · already written in step 6
Checkpoint
Twelve chapters. No code in this one, and it is the last step of the course, so it should say plainly what got built and what did not, instead of dressing either one up.
izvor reads a source file, checks that every name it uses exists and every type it combines makes sense, refuses several real classes of mistake before running a single instruction, and compiles to a native binary through real, readable C. It has variables, functions, control flow, fixed-size arrays and structs, and now one deliberately narrow form of parallelism where the one mistake that actually matters, a shared variable written from more than one thread, cannot make it past the compiler. Every one of those sentences is backed by a chapter that built it in front of you, not a claim taken on faith.
It also never became several things a longer-lived language would need. No memory
allocator and no ownership story, which is why every array and every struct has been
fixed size since chapter 11 and will stay that way until something forces the question.
No modules, so every program is still one file. No generics, so a function written for
Int cannot also serve Bool without a second, separate function.
And, this chapter's whole subject, no user-visible thread, no lock, no channel, nothing
that would let a program hold a piece of concurrency and pass it around like a value.
Every one of those is a real gap, not an oversight; each one showed up honestly, in its
own chapter, as the cost of something else that chapter bought.
If I kept going, the allocator is where I would go next, not because parallelism needs it,
but because it is the one gap sitting underneath the most other decisions in the second
half of this course. Fixed-size arrays, fixed-size structs, a reduction restricted to one
associative operation on a single long: all three trace back to the same
missing piece, a way to ask the operating system for memory whose size is not known until
the program is already running, and a rule for who is responsible for giving it back. That
is a much bigger chapter than any of the twelve here, and it deserves one of its own rather
than an ending tacked onto this one.
What this course actually argued, from chapter 1 to here: a small language, built one honest constraint at a time, can make a real guarantee about a real class of bug, and can show you, in C, exactly how that guarantee is enforced rather than asking you to trust that it is. That was always the point of writing the compiler yourself instead of reading about one.
Checkpoint
Twelve chapters, one clean build.