11. NPC Policy, Lua, and Script Execution — print chapter

Game Hacking Academy

Chapter 11: NPC Policy, Lua, and Script Execution

00000000  47 61 6D 65 20 48 61 63  6B 69 6E 67 20 41 63 61  |Game Hacking Aca|
00000010  64 65 6D 79                                       |demy|

The title as it sits in memory: one byte per letter, written in hexadecimal.

11 lessons from a book of 155. Printed from mustcodeal.github.io/rust-game-hacking-book, built 2026-10-18.

Grew out of the original Game Hacking Academy by attilathedud (gamehacking.academy). Published under the Apache License 2.0.

This page contains only Chapter 11. The browser’s Print dialog lets you save it as a PDF.

Print this chapter or save as PDFOther print options

Chapter 11 contents

1. 11.1 — How an NPC Sees, Chooses, and Remembers
2. 11.2 — Why Games Use Lua
3. 11.3 — Lua Tables, Functions, and Metatables
4. 11.4 — The Host–Script Boundary
5. 11.5 — Snapshots as a Script Interface
6. 11.6 — State Machines for Lua Automation
7. 11.7 — Script Budgets, Errors, and Recovery
8. 11.8 — What Any Computer Can Compute
9. 11.9 — From Lua Source to a Tiny Virtual Machine
10. 11.10 — Values, Tables, Strings, and Garbage Collection
11. 11.11 — Call Frames, Closures, and Upvalues

Lesson 11.1

How an NPC Sees, Chooses, and Remembers

Lesson 4.10 followed a toy guard through sixteen ticks of sensing, deciding, and acting. This lesson opens up what it described in words: the arithmetic behind the guard’s view cone and line of sight, and two other ways games choose what an NPC does. The earlier lesson is the first-pass behavior model; this is the worked explanation you can return to when a real guard’s choices need closer inspection. The geometry is the two-dimensional case of the vectors in Lesson 4.4.

The three checks in code

One method runs the guard’s three checks in their cheapest-first order. The first two use Vec2, the lab’s pair of x and y coordinates; the last uses the wall list:

fn can_see(&self, target: Vec2, walls: &[Wall]) -> bool {
    let offset = target - self.position;
    if offset.length() > VIEW_DISTANCE {
        return false;
    }
    let Some(direction) = offset.normalized() else {
        return true;
    };
    if direction.dot(self.facing) < VIEW_CONE_COS {
        return false;
    }
    line_of_sight(self.position, target, walls)
}

The return false lines reject a target as soon as a check fails. normalized() returns an optional direction because a zero-length arrow has no direction; the let Some(direction) ... else branch handles that case. The following sections work through each calculation with positions you can draw on a grid.

The guard’s three sight checksThe guard stands at (0, 0) and faces along x, the direction (1, 0). Move the target or add a wall: the first check that fails stops the rest.

Checks in order, then the answer

Three checks, cheapest first

1. Distance ≤ 10

√(4² + 3²) = √25 = 5

pass

2. View cone: dot ≥ 0.5

(0.8, 0.6) · (1, 0) = 0.8about 36.9° from the facing; 0.5 stands for 60°

pass

3. Line of sight

no walls in this example

pass

Result

The guard sees the target

5 ≤ 10 and 0.8 ≥ 0.5 (about 36.9° from the facing), and nothing blocks the line: the guard sees the target.

The first two checks read offset, the arrow from the guard to the target: the target’s position minus the guard’s, the same subtraction as in Lesson 4.4. For a guard at (0, 0) and a player at (4, 3), the offset is (4 − 0, 3 − 0) = (4, 3): 4 units along x and 3 along y. The lab’s Vec2 type stores such a two-number vector, and the guard’s facing is one too.

Distance

The arrow’s length is the distance from Lesson 4.4 with two coordinates, √(x² + y²). For (4, 3), that is √(4² + 3²) = √(16 + 9) = √25 = 5, within VIEW_DISTANCE = 10, so the first check passes. A player at (15, 0) is √(15² + 0²) = 15 away and fails it.

The view cone and the dot product

A unit vector is a vector of length 1, the result of normalizing. It stores a direction and nothing else. The guard keeps facing as a unit vector: (1, 0) means it faces east, along the x axis. The offset (4, 3) has length 5, so its direction is (4 ÷ 5, 3 ÷ 5) = (0.8, 0.6), whose length is √(0.64 + 0.36) = √1 = 1. A target standing exactly on the guard has an offset of length 0 and no direction; the let Some(direction) ... else line counts it as seen.

In two dimensions, the dot product from Lesson 4.4 has two terms:

a · b = a.x × b.x + a.y × b.y

For two unit vectors, the dot product equals the cosine of the angle between them. Picture a circle of radius 1 around the guard. A unit direction at some angle from east ends on that circle, and the cosine of that angle is, by definition, the x-coordinate of that end point. As the angle grows from 0° to 180°, the end point slides around the circle from right to left, so its x falls steadily: 1 at 0°, 0 at 90°, and −1 at 180°. For a guard facing east, the dot product of (1, 0) with a unit direction (x, y) is x × 1 + y × 0 = x, exactly that cosine.

For any other facing, take the two unit vectors a and b and look at the arrow from b’s tip to a’s tip, found the same way as offset: (a.x − b.x, a.y − b.y). Call its length the tip gap. Pythagoras gives the tip gap squared, and multiplying out the brackets regroups the terms:

(a.x − b.x)² + (a.y − b.y)²
  = a.x² − 2 × a.x × b.x + b.x² + a.y² − 2 × a.y × b.y + b.y²
  = (a.x² + a.y²) + (b.x² + b.y²) − 2 × (a.x × b.x + a.y × b.y)

The first two groups are the vectors’ lengths squared, 1 each, and the last bracket is the dot product, so (tip gap)² = 1 + 1 − 2 × (a · b), which rearranges to a · b = 1 − (tip gap)² ÷ 2. Turning the guard swings both arrows together like one rigid shape, which leaves the gap between their tips unchanged, so the dot product cannot change either: what holds facing east holds for every facing. As a check, the arrow between the tips of (1, 0) and (0.8, 0.6) is (1 − 0.8, 0 − 0.6) = (0.2, −0.6), so the tip gap squared is 0.04 + 0.36 = 0.4, and 1 − 0.4 ÷ 2 = 0.8, the same as 1 × 0.8 + 0 × 0.6.

Why does 0.5 mean 60°? A triangle whose three sides are all 1 long has three equal angles, and a triangle’s angles add up to 180°, so each is 180 ÷ 3 = 60°. Two of its sides, starting from the same corner, are unit vectors 60° apart whose tips are 1 apart, so their dot product, the cosine of 60°, is 1 − 1² ÷ 2 = 0.5.

The test direction.dot(self.facing) < VIEW_CONE_COS therefore rejects every direction whose cosine is below 0.5. The cosine falls steadily as the angle grows, so that is every direction more than 60° from the facing, on either side.

0°1.0

37°0.8

60°0.5

90°0.0

120°−0.5

180°−1.0

inside the cone: 0.5 or more

outside the cone

The dot product of the facing and a unit direction at each angle from it. It falls from 1 straight ahead to 0 at a right angle and −1 straight behind. At 120°, 60° past the right angle, the direction's x is the mirror image of the 60° case, −0.5.

For the player at (4, 3), the dot product of (0.8, 0.6) with the facing (1, 0) is 0.8 × 1 + 0.6 × 0 = 0.8, at least 0.5, so the player is inside the cone. (An inverse cosine, the calculator function that turns a cosine back into an angle, puts them about 37° from the facing.) A player at (0, 5) has direction (0 ÷ 5, 5 ÷ 5) = (0, 1) and a dot product of 0 × 1 + 1 × 0 = 0, a full 90° to the side, so the guard does not see them.

Comparing with a cosine worked out once, when the constant was written, costs two multiplications and one addition and never needs the slower inverse cosine, the same saving as the three-dimensional view test in Lesson 4.4.

TL;DR: The guard checks its view cone by comparing a dot product with a number worked out once. It never computes an angle.

Line of sight

The last check, line_of_sight, walks from the guard toward the target in steps of SIGHT_STEP = 0.1 and tests each sample point against the walls. Each wall is an axis-aligned box, meaning its sides run along the x and y axes, stored as two corners, min and max. A point is inside when both of its coordinates lie between the corners.

On tick 8 of Lesson 4.10’s run, the guard stands at (4, 0), the player at (8, 0), and a wall fills the box from (5.5, −1) to (6.5, 1) between them. The samples are (4.0, 0), (4.1, 0), (4.2, 0), and so on. The 16th, (5.5, 0), is the first inside the wall, because 5.5 ≤ 5.5 ≤ 6.5 and −1 ≤ 0 ≤ 1 (a point on the edge counts as inside), so the function returns false long before it reaches the player.

Predict first

Same guard at (4, 0) and player at (8, 0), samples every 0.1: x = 4.0, 4.1, 4.2 and so on. This time a thin wall covers only x from 5.62 to 5.68 (y from −1 to 1).

Does line_of_sight find the thin wall?

Answer: No: every sample misses it, so the guard sees the player. The wall is 5.68 − 5.62 = 0.06 wide, thinner than the 0.1 step. Samples 5.6 and 5.7 land on either side, all 40 samples test clear, and the function returns true. Try the thin-wall example below.

Walk the sight line one sample at a timeThe guard at (4, 0) tests points toward the player at (8, 0). A wall spans y from −1 to 1; set where it starts and ends along x, and the step between samples.

The walk stops at the first sample inside

Samples on y = 0, guard at x 4, player at x 8

Each sample, in order

15 clearx 4.0 to 5.4

x 5.5inside: stop

24 never testedx 5.6 to 7.9

Bounds check at x 5.5

5.5 ≤ 5.5 ≤ 6.5

−1 ≤ 0 ≤ 1

inside

Result

Blocked: line_of_sight returns false

Samples land every 0.1 from x 4.0. The first one inside the wall is x 5.5, so the walk stops after 16 of 40 samples.

Optional reference: the lab's second line-of-sight test

A line can also slip past a wall. From (0, 0) to (4, 3), the line rises 3 for every 4 across, so every point on it has y = 3 ÷ 4 × x = 0.75 × x. A wall from (2, −1) to (3, 1) covers x from 2 to 3, where the line’s y runs from 0.75 × 2 = 1.5 to 0.75 × 3 = 2.25, higher than the wall’s top edge at y = 1. No sample lands inside, and the guard sees the player. The lab’s tests check both cases.

Besides that blind spot for walls thinner than the step, stepping costs more with distance. A check across the full view distance takes 10 ÷ 0.1 = 100 samples, each tested against every wall. Engines instead compute exactly where a ray crosses each collision shape, a ray cast, but the question they answer is the same one.

Choose among actions: utility scoring

A state machine answers “which mode am I in?” Some decisions are better framed as “which of these options is best right now?” Utility AI gives every option a score computed from the situation and runs the highest one. The second demo in the lab from Lesson 4.10 scores three options for a fighter:

fn score(choice: Choice, situation: Situation) -> f32 {
    match choice {
        Choice::Attack if situation.enemy_visible => 0.4 + 0.6 * situation.health,
        Choice::TakeCover if situation.enemy_visible && !situation.in_cover => {
            0.9 - 0.6 * situation.health
        }
        Choice::Heal if situation.potions > 0 => 1.0 - situation.health,
        _ => 0.0,
    }
}

health here is a fraction: 30 health out of 100 is 30 ÷ 100 = 0.3. Each score is a straight line in health, chosen so its meaning is readable. Attack scores 1.0 at full health and falls to 0.4 as health runs out. Taking cover scores 0.3 at full health and rises to 0.9. Healing scores nothing at full health and 1.0 at zero. An option that makes no sense right now, such as healing with no potions, scores 0.

With an enemy in view, no cover, and one potion, the scores at several health levels are:

Health	Attack: 0.4 + 0.6 × h	Take cover: 0.9 − 0.6 × h	Heal: 1.0 − h	Chosen
1.0	0.4 + 0.6 = 1.00	0.9 − 0.6 = 0.30	0.00	Attack
0.75	0.4 + 0.45 = 0.85	0.9 − 0.45 = 0.45	0.25	Attack
0.5	0.4 + 0.3 = 0.70	0.9 − 0.3 = 0.60	0.50	Attack
0.3	0.4 + 0.18 = 0.58	0.9 − 0.18 = 0.72	0.70	Take cover
0.2	0.4 + 0.12 = 0.52	0.9 − 0.12 = 0.78	0.80	Heal
0.1	0.4 + 0.06 = 0.46	0.9 − 0.06 = 0.84	0.90	Heal

The switch points come straight from the formulas. Attack and cover score the same when 0.4 + 0.6h = 0.9 − 0.6h. Adding 0.6h to both sides and taking 0.4 from both gives 1.2h = 0.5, so h = 0.5 ÷ 1.2 ≈ 0.42. Cover and healing tie when 0.9 − 0.6h = 1.0 − h, which rearranges to 0.4h = 0.1, so h = 0.25. Above about 42% health this fighter attacks, between 25% and 42% it takes cover, and below 25% it drinks a potion. Changing one number in a formula moves one of those switch points, and that is how designers tune utility AI.

Alternative: Think of a talent show: every option gets a score for the current situation and the judge picks the highest. Change a score weight or formula and the winner changes.

The lab’s choose function keeps only scores above 0 before it picks the highest. With nobody in view, every option scores 0, so it returns None: nothing on this list is worth doing, and another system, such as the patrol, keeps control.

Optional reference: the demo's five situations

The demo also varies the situation, all at a health of 0.3 except where it says healthy:

Situation	Attack	Take cover	Heal	Chosen
healthy, enemy in view	1.00	0.30	0.00	Attack
hurt, enemy in view, exposed	0.58	0.72	0.70	Take cover
hurt, enemy in view, in cover	0.58	0.00	0.70	Heal
hurt, in cover, no potions left	0.58	0.00	0.00	Attack
healthy, nobody in view	0.00	0.00	0.00	nothing

Once in cover, taking cover scores 0, so the next best option wins. With no potions, healing scores 0 too, and attacking is all that is left.

Utility scoring has its own weak spot. Near a switch point, a tiny change in health can flip the choice back and forth every tick. Games damp this by adding a small bonus to whatever the NPC is already doing, so a rival option has to beat it clearly before the NPC switches. The trade against a state machine is that a state machine lists every transition by hand, so each new state needs arrows to and from the old ones, while utility scoring adds one scoring function per option but hides its behavior in numbers that need tables like the one above to tune.

Behavior trees, briefly

Larger games often organize NPC logic as a behavior tree instead. The lab does not build one, but the idea is a priority checklist whose entries can contain smaller checklists. The leaves are conditions (“is health 25 or less?”) and actions (“flee”). A selector tries its children from left to right and stops at the first one that succeeds. A sequence runs its children in order and stops at the first one that fails. This simplified tree starts at the root each tick.

The guard’s priorities fit in one selector:

Walk through one tick. At 30 health, the first sequence fails its health check, so the selector tries the next one. If the player remains visible for three ticks and is within attack range, that sequence chooses attack; if they are farther away, it chooses chase. At 20 health, the first sequence reaches flee and the selector does not inspect the attack or patrol branches. The diagram shows priority, not the pathfinding or animation code inside an action. In a production tree, a long-running action can also return running so the engine knows it has not succeeded or failed yet; such a tree must define how that state is resumed or checked on the next tick.

Compare it with the guard’s state diagram. The four arrows into Flee, one from each other state, became one child, placed first, because a behavior tree re-checks its priorities from the top every tick. The tree keeps no memory between ticks by itself, though. Values such as seen_for and last_known live beside it, in a shared store that engines call a blackboard. Real games mix all three techniques: a behavior tree for priorities, small state machines inside some of its nodes, and utility scores to choose between similar actions.

This simulation needs JavaScript. The lesson text around it works through the same numbers.

Stored as a C++ structure, the guard’s fields add up to 33 bytes: four 4-byte floats, a 4-byte health, the 1-byte state at offset 0x14, and three more 4-byte values. Each 4-byte field must start at a multiple of 4, so three padding bytes follow the state and the structure takes 36 bytes. A state byte outside 0 to 4, such as 9, can make a compiled switch that indexes its jump table without a range check jump to an unrelated address and crash. These fields, offsets, and padding are worked through in Lesson 14.1, where recovering object layouts is the subject.

The guard can now be read in three ways. Its sensing code tells us which facts it can observe, a state trace tells us which choice it made on each tick, and seen_for and last_known hold what it carried from one tick into the next. None of those alone proves why a particular guard moved. Together they let us check a claim such as “the wall broke line of sight, so Chase became Search” against both behavior and state. The rest of this chapter moves decisions like these into Lua scripts that a game loads and limits.

Lesson 11.2

Why Games Use Lua

Chapter 10 followed game files and mods through their formats, integrity checks, and loading behavior. Some games also offer a supported way to run small scripts inside the game. That changes the first question: instead of asking where a value lives in memory, ask which values and actions the game deliberately gives to a script. Lua is one common language for that boundary.

We will first write small Lua scripts and define the host API that contains them. Once those pieces work, we will open the interpreter itself: source text becomes bytecode, and bytecode runs on a virtual machine with its own values, stack, and object lifetimes.

Compiled engine, flexible script

The native host is normally compiled ahead of time into machine code. Changing its source means building a new executable or library.

Lua is a small programming language commonly embedded inside a larger program. The game owns a Lua interpreter and asks it to run text scripts. A designer can change a quest, unit behavior, or user-interface behavior without rebuilding the whole engine.

Use the host-boundary model:

A host table exposes selected operations. This step-by-step trace needs JavaScript. Here is the code and where the run ends.

read the selected inputs
evaluate each stated condition
combine the required conditions
perform the effect only when accepted
otherwise retain the old state
report the result and its limits

Result: the exported operation runs within its documented host boundary.

Final values: operation = snapshot; exported = true; accepted = true; returned = copied fields.

Read every step of the lesson’s example

1. Step 1, line 1. Start with the selected inputs and follow how the next operation changes the state.

   operation = snapshot.

2. Step 2, line 2. This host deliberately installs snapshot and log; it does not export a raw-memory function.

   operation = snapshot; exported = true.

3. Step 3, line 3. Accept only when the required conditions all hold.

   operation = snapshot; exported = true; accepted = true.

4. Step 4, line 4. The model performs the accepted effect.

   operation = snapshot; exported = true; accepted = true; returned = copied fields.

5. Step 5, line 6. Result: the exported operation runs within its documented host boundary.

   operation = snapshot; exported = true; accepted = true; returned = copied fields.

Watch it happenGive a Lua script specific capabilities

The host installs log, snapshot and request functions in a Lua game table. A log argument reaches the host console, named entity fields are copied into Lua, and a selection request returns for host validation. Process handles and raw memory remain behind the host boundary.

Read the steps

1. The compiled host owns the live entities, process handles, and Lua runtime. An empty game table gives the script no route to those resources.
2. The host installs three function capabilities in game: log, snapshot, and request. These callable values grant specific operations, not unrestricted engine access.
3. The script calls game.log with observer started. That argument travels to the host-supplied log function, which decides where the message appears.
4. game.snapshot asks the host for an observation. The host copies named fields into Lua-owned tables. Those values are separate from live entity storage.
5. A select_entity request travels in the other direction. The host checks the requested ID against the current world before allowing a bounded action.
6. No raw memory function was supplied. Looking for memory.write does not create a capability or open another route through the boundary.

An API is a set of deliberately supplied routes. Copying observations and checking requests keeps ownership with the host.

The engine owns the runtime and decides which values and functions cross the API boundary. A script cannot automatically do everything the engine can do; it sees only the capabilities that the host deliberately exposes.

From a script file to one visible result

The host loads Lua source, checks that it is valid Lua, and asks the Lua runtime to execute it. When the script calls game.log, execution crosses back to a function the host supplied.

Alternative: Embedding Lua is a conversation: the host asks the interpreter to run a script, and a registered callback lets the script ask the host for one service.

The interpreter inside that runtime is also called a Lua virtual machine, or VM: it follows internal instructions made from the script. That is enough to understand why a host can later count script steps. Lesson 11.9 opens the VM and shows the instructions themselves.

We can observe the host crossing without changing any game state:

game.log("observer started")

Here game is a table of functions supplied by our lab host, log is one of those functions, and the quoted text is its argument. The host decides where the message appears. For this first script, we only need to know who runs it and who supplies game.log.

The host runs the script and the script calls backThe script’s game.log("observer started") call sends its argument back through the callback the host supplied.

Native hostLua script

1. 1

   Control Run the script

   Step 1: Native host to Lua script

   The host asks its Lua runtime to execute the script.

2. 2

   Request game.log("observer started")

   Step 2: Lua script to Native host

   game.log was registered by the host, so this call crosses back into native code with the message.

3. 3

   Reply Callback logs it, then returns

   Step 3: Native host to Lua script

   The host decides what logging means (a file, a console or a buffer); then the script continues after the call.

The script’s game.log("observer started") call sends its argument back through the callback the host supplied.

Lua is dynamically typed

The host language knows a variable’s type at compile time:

let health: u32 = 100;

In Lua, a variable can refer to values of different types at different times:

local health = 100
health = "unknown"

That flexibility is convenient for configuration and gameplay behavior. It also moves many mistakes from compile time to runtime. Clear names, validation, tests, and small APIs matter even more.

For these lessons we pin the lab to Lua 5.4 through mlua 0.12. Other games may embed Lua 5.1, LuaJIT, Lua 5.5, or a customized dialect. Check the target’s documentation or version string before assuming features exist.

The values you meet first

These declarations put seven different kinds of value behind local names. Nothing runs merely because the function value is created; decide can be called later, while the other values can be read or changed by later code.

local name = "bot_alpha"       -- string
local health = 100              -- integer number
local distance = 12.5           -- floating-point number
local alive = true              -- boolean
local target = nil              -- no value
local position = { x = 4, y = 9, z = 2 } -- table
local decide = function() end   -- function

Lua also has threads/coroutines and userdata supplied by a host. A table is the main container: it can behave like a list, dictionary, record, namespace, or object.

A table variable refers to one table object. Assigning it to another name copies that reference, so two names can reach the same table:

local first = { health = 100 }
local second = first
second.health = 75
assert(first.health == 75) -- both names reach the same table

second = first copied the reference, the arrow, not the table it points to. There is only one health field, so the write through second is the value read through first.

This shared reference is called aliasing. Lesson 11.3 develops tables and how iteration selects keys; Lesson 11.10 explains how the runtime represents values and eventually reclaims unreachable tables. When a table crosses into a host function, the host must still validate the fields it receives.

Local versus global names

The two assignments below look similar, but only the first declares a name private to its scope. The second writes into Lua’s shared global environment.

local selected = nil -- visible only in this scope ✅
state = "running"   -- creates or replaces a global name ⚠️

Prefer local unless you intentionally publish a value. Accidental globals let separate scripts overwrite each other’s state and make spelling mistakes difficult to find.

Narration: A misspelled global assignment can quietly create shared state. Local names keep that mistake from changing what another script sees.

The host API is the security boundary

A poor host might expose an all-powerful function:

-- ❌ A script can ask for any address, size, and write.
memory.write(address, bytes)

The book’s lab exposes a narrow interface instead:

local entities = game.snapshot()
if entities[2] then
    game.request({ kind = "select_entity", id = entities[2].id })
end

game.snapshot() returns copied sample data. If a second entity exists, the script asks to select its ID; the host can still reject the request if that ID is no longer valid. game.request accepts only a small list of validated actions. The script never receives a process handle, arbitrary pointer, command shell, or raw Windows API.

TL;DR: A script can act only through the host functions it receives; copied observations do not grant arbitrary memory access.

This is capability design: code can do only what the values and functions in its environment allow.

Your first observer

The file lua-labs/scripts/observer.lua contains:

First, game.snapshot() supplies a list of copied entity tables. Lua’s ipairs(entities) then visits list entries in order. In the for line below, _ discards the numeric position and entity names the current entry. The alive and "alive" or "dead" expression chooses one of two words, and string.format fills the %s text slots and %.1f one-decimal number slots. Those pieces turn one copied list into readable output:

local entities = game.snapshot()

for _, entity in ipairs(entities) do
    local state = entity.alive and "alive" or "dead"
    game.log(string.format(
        "%s: %s at (%.1f, %.1f, %.1f)",
        entity.name,
        state,
        entity.position.x,
        entity.position.y,
        entity.position.z
    ))
end

Read it as a sequence:

1. ask for one snapshot;
2. visit each entity in its list order;
3. choose a readable state word;
4. format one message;
5. send that text to the host logger.

Nothing here edits a game. It proves the language, table shape, and host boundary before later automation.

Run the lab

Any computer

From the repository root:

cargo run --manifest-path lua-labs/Cargo.toml -- scripts/observer.lua

The host works on Windows, macOS, and Linux because it uses a simulated snapshot. Later you can connect the same API shape to one of the book’s read-only Windows observers.

Versions and trust differ between games

Games that load Lua mods differ in each of these, and each one changes what a script can do or how its failures show up:

• Lua version or dialect;
• search paths and file names;
• which standard libraries are available;
• host-provided functions and their required argument types and ranges;
• whether scripts are trusted, signed, or user-authored;
• CPU, memory, and action limits;
• how a script error is reported and disabled.

Lua makes behavior easier to change. A well-designed host also makes the boundaries easier to explain.

Lesson 11.3

Lua Tables, Functions, and Metatables

Lua tables represent arrays, records, and maps

A Lua table maps keys to values. These are all tables:

local list = { "sword", "shield", "potion" }
local position = { x = 10.0, y = 5.5, z = 2.0 }
local by_id = { [7] = "archer", [12] = "mage" }

The first table uses integer keys 1, 2, and 3. Lua sequences conventionally start at one, not zero.

local bag = { "sword", "shield", gold = 25 }One table, three key–value pairs.

1. 1 Every entry is a key and a value

   Key → value

   1"sword"

   2"shield"

   "gold"25

   Lua gave the listed items the keys 1 and 2. "gold" is just another key.

2. 2 ipairs and # use only the keys 1, 2, 3, …

   Key

   1visited

   2visited

   3missing: stop

   "gold"skipped

   ipairs stops at the missing key 3 and never sees "gold"; #bag is 2.

One table, three key–value pairs.

A table is not “an array that sometimes has names.” It is one mapping abstraction that accepts several kinds of keys. Sequence operations add conventions on top: positive integer keys beginning at one, usually without holes. The length operator and ipairs are easiest to reason about when the script preserves that shape.

Before crossing the host/Lua boundary, name the promised shape:

entity sequence: keys 1..n, every value is an entity table
entity record: named keys id, alive, and position
lookup map: arbitrary entity IDs mapped to records; order is not promised

The same Lua table implementation can represent all three, but host validation and the choice of iteration method differ.

print(list[1]) -- sword ✅
print(list[0]) -- nil

When the host turns a Vec into a Lua sequence, it must add one to the zero-based index. The implementation in lua-labs/src/main.rs does exactly that.

How a map finds a key

Inside, a Lua table has two parts: an array part for the keys 1, 2, 3, … of a sequence, and a hash part for other keys. The hash part is a hash table. It turns a key into a number, its hash, to choose a starting slot. A lookup checks the key there and, if another key collided with it, follows the collision link until it finds the requested key or proves it absent. Hashing usually narrows a lookup to a small part of the table; it does not promise one comparison every time.

Suppose the hash part has 4 slots, numbered 0 to 3, and the string "y" hashes to 22. Lua keeps the remainder after dividing by the slot count: 22 ÷ 4 is 5 remainder 2, so y goes in slot 2. Slot counts are powers of two, so that remainder is simply the hash’s lowest bits: 22 is 10110 in binary, and its last two bits, 10, are 2.

slot 0z · 2.0

slot 1empty

slot 2y · 5.5

slot 3x · 10.0

22 ÷ 4 leaves 2

A collision-free illustration of the hash part of position with 4 slots, assuming the key y hashes to 22. A real collision can place a key in another slot and link it from its starting slot.

Two things follow. The Lua language promises no useful order from pairs; it does not reproduce the order in which the script wrote fields. Lua 5.4’s implementation traverses its storage, and a table resize can change that order. Two keys can also hash to the same starting slot, a collision; Lua links the displaced key so lookups still work, though long collision chains cost extra comparisons. Lesson 3.10 shows what the same idea looks like in a compiled C++ program.

Iterate according to the shape

Use ipairs for a dense integer sequence:

for index, item in ipairs(list) do
    print(index, item)
end

ipairs starts at key 1 and stops at the first missing key. A hole, a missing key in the middle of a sequence, therefore ends the loop early:

Narration: A missing sequence entry can end an ipairs loop even when later numbered entries exist. Check for holes before blaming the body of the loop.

list[2] = nil -- { "sword", "shield", "potion" } now has a hole at key 2

1sword

2nil

3potion

4nil

visited by ipairs

ipairs stops here

never reached

After list[2] = nil, ipairs never sees potion. The length operator is no safer: #list may return 1 or 3, because each is a border, a key whose value is present while the next key's value is missing, and Lua promises only that # returns some border.

Use pairs when keys are not a simple sequence:

for key, value in pairs(position) do
    print(key, value)
end

Do not rely on a meaningful order from pairs: it follows the hash part’s slot order, as the previous section showed. If order matters, store an explicit sequence or sort the keys.

A sequence hole ends ipairs early. This step-by-step trace needs JavaScript. Here is the code and where the run ends.

items = { [1]="A", [2]="B", [3]="C" }
if selected: items[2] = nil
index = 1
while items[index] exists: visit it
index = index + 1; repeat
stop at the first missing index

Result: visited A, B, C. The next missing key is 4.

Final values: hole = present; visited = A, B, C; index = 4.

Read every step of the lesson’s example

1. Step 1, line 1. Start with the selected inputs. Follow the highlighted operation and the changing state below.

   hole = present.

2. Step 2, line 2. Setting a sequence entry to nil removes that key.

   hole = present; visited = ; index = 1.

   Memory: 1 = A; 2 = B; 3 = C.

3. Step 3, line 4. Visit key1: A.

   hole = present; visited = A; index = 1.

   Memory: 1 = A; 2 = B; 3 = C.

4. Step 4, line 5. Advance to the next numeric key.

   hole = present; visited = A; index = 2.

   Memory: 1 = A; 2 = B; 3 = C.

5. Step 5, line 4. Visit key2: B.

   hole = present; visited = A, B; index = 2.

   Memory: 1 = A; 2 = B; 3 = C.

6. Step 6, line 5. Advance to the next numeric key.

   hole = present; visited = A, B; index = 3.

   Memory: 1 = A; 2 = B; 3 = C.

7. Step 7, line 4. Visit key3: C.

   hole = present; visited = A, B, C; index = 3.

   Memory: 1 = A; 2 = B; 3 = C.

8. Step 8, line 5. Advance to the next numeric key.

   hole = present; visited = A, B, C; index = 4.

   Memory: 1 = A; 2 = B; 3 = C.

9. Step 9, line 6. Result: visited A, B, C. The next missing key is 4.

   hole = present; visited = A, B, C; index = 4.

   Memory: 1 = A; 2 = B; 3 = C.

Functions are values

Suppose a script must rank targets without choosing one yet. The two input tables below are positions. The function subtracts their coordinates and returns squared distance, which preserves the nearest-to-farthest order without calculating a square root. Assigning the function to scoring_rule copies a callable value, so the function can later be passed to other code.

local function squared_distance(a, b)
    local dx = b.x - a.x
    local dy = b.y - a.y
    return dx * dx + dy * dy
end

local scoring_rule = squared_distance
print(scoring_rule({ x = 0, y = 0 }, { x = 3, y = 4 })) -- 25

The points (0, 0) and (3, 4) differ by 3 and 4; 3² + 4² is 25, the printed result. A function can also be stored in a table, passed to another function, and returned. This is why a game can register callbacks such as on_turn_started.

Closures remember surrounding values

An action may need a cooldown that survives between calls without becoming a global variable. make_cooldown takes the wait length and returns a function that remembers its own remaining counter:

local function make_cooldown(required_ticks)
    local remaining = 0

    return function(triggered)
        if remaining > 0 then
            remaining = remaining - 1
            return false
        end
        if triggered then
            remaining = required_ticks
            return true
        end
        return false
    end
end

local ready_once = make_cooldown(3)

The returned function keeps access to remaining after make_cooldown has returned. That remembered environment is a closure.

Alternative: A closure carries a private notebook with its function: later calls read and update the remembered counter without making it global.

The practical payoff is that each call to make_cooldown produces its own private remaining. Two cooldowns created this way count down independently, with no shared global and no counter passed around by hand:

local attack_ready = make_cooldown(3)
local heal_ready = make_cooldown(10)   -- separate remaining, separate countdown

Following attack_ready(true) through five calls in a row shows the private remaining at work. The first call finds remaining at 0, so it fires and sets remaining to 3; each later call finds it above 0, subtracts 1, and refuses, until it is back at 0 and the next call fires again:

call 1fires, 3

call 2blocked, 2

call 3blocked, 1

call 4blocked, 0

call 5fires, 3

The result of each attack_ready(true) call and the value remaining holds afterward. heal_ready owns a different remaining, so none of these calls moves its countdown.

That is why closures suit bot code so well: each piece of timed behavior can own its own state without the rest of the script being able to reach in and disturb it.

The colon supplies self

Lua uses : to pass the table on the left as an extra first argument. The first call below passes bot explicitly, while the second passes Bot because that is the table before the colon. Watch which table receives state = "plan".

local Bot = {}

function Bot:set_state(next_state)
    self.state = next_state
end

local bot = { state = "observe" }
Bot.set_state(bot, "plan") -- dot form: pass bot explicitly
Bot:set_state("plan")      -- colon form: Bot becomes self

Colon syntax is convenient, but the last line above changes the Bot table itself, not bot. To share methods through a prototype, Lua code commonly uses a metatable.

Metatables change fallback behavior

The previous Bot table had a method, but a separate bot record did not inherit it. Here Bot:new attaches Bot as the new record’s metatable. The __index fallback then lets scout:set_state find the method on Bot, leaving scout.state as "plan".

local Bot = {}
Bot.__index = Bot

function Bot:new(name)
    local instance = { name = name, state = "observe" }
    return setmetatable(instance, self)
end

function Bot:set_state(next_state)
    self.state = next_state
end

local scout = Bot:new("scout")
scout:set_state("plan")

The line that confuses nearly everyone is Bot.__index = Bot. Two separate things are happening there, and it helps to state them apart.

A metatable is a table you attach to another table to say what should happen when an ordinary operation on it does not work out — a key that is missing, an addition, a comparison. Lua looks inside it for specially named keys such as __index or __add, and uses whatever it finds there.

Attaching one by itself changes nothing about how keys are looked up. What does the work is the __index key inside that metatable: when a lookup on the original table fails, Lua checks the metatable for __index, and if it finds a table there, repeats the lookup in that table.

So setmetatable(instance, Bot) says “if a key is missing from this instance, ask Bot what to do,” and Bot.__index = Bot says “what to do is: look inside Bot itself.” Compressed into one line it reads as circular; separated into two steps it is ordinary. Forgetting to set __index is the classic beginner mistake — the metatable is attached, every method lookup still returns nil, and nothing in the error explains why.

Drawn out, the whole arrangement is two references. scout’s metatable is Bot, and Bot.__index points back at Bot itself:

set_state appears only in the right-hand box. A lookup that misses in scout follows the metatable arrow, finds __index, and follows the loop to search Bot, where the key exists.

When scout has no set_state key, its metatable’s __index points to Bot, so Lua looks there. This resembles method lookup, but it is not a compiled C++ vtable. It is lookup behavior that scripts can inspect and change.

Read the expression scout:set_state("plan") in two stages. Colon syntax first supplies scout as the hidden first argument. Normal table lookup then searches scout for set_state and follows the __index reference to Bot when the key is absent. Keeping argument passing separate from lookup makes metatable behavior much less mysterious.

The left side of the process chooses the first argument. The right side finds the function value. They cooperate, but they are separate steps.

Validate host-shaped tables

Dynamic types do not remove the need for contracts:

local function require_entity(value)
    assert(type(value) == "table", "entity must be a table")
    assert(type(value.id) == "number", "entity.id must be a number")
    assert(type(value.position) == "table", "entity.position must be a table")
    assert(type(value.alive) == "boolean", "entity.alive must be a boolean")
    return value
end

Validate at the boundary, then let internal code use the checked shape. The host must still validate every value coming back from Lua; a script can mutate its table after validation.

TL;DR: Check tables again when they cross back into the host, because a script can change fields after an earlier check.

Avoid clever metatable surprises

Metamethods such as __index, __newindex, __add, and __call can make expressive APIs. They can also hide control flow.

For beginner-friendly game scripts:

• prefer ordinary fields for data;
• use a small prototype pattern only when shared methods help;
• avoid changing global metatables;
• do not run arbitrary behavior during simple field reads;
• validate tables received from scripts at the host boundary.

Plain tables and plain functions are enough for most observers, mod logic, and state machines. Learn the mechanism, then use only as much magic as the reader can still explain.

Lesson 11.4

The Host–Script Boundary

The host owns the interpreter

mlua creates and controls a Lua virtual machine from the host. The project pins:

[dependencies]
anyhow = "1.0"
mlua = { version = "0.12", features = ["lua54", "vendored", "error-send"] }

lua54 chooses Lua 5.4. vendored builds the matching Lua implementation with the crate, so a learner does not need to find a separate Lua DLL. error-send lets contextual host error-reporting carry a Lua failure through anyhow without discarding its details.

The interpreter is a subsystem with its own state, memory manager, call stack, and error reporting. Embedding does not merge Lua and the host into one language. mlua builds a checked bridge that converts values and controls when execution crosses between them.

Treat each crossing as an interface:

• host-to-Lua inputs need a documented table shape and units;
• Lua-to-host requests need type checks and validation against current game state;
• errors need enough context to identify the script and boundary;
• callbacks need time and resource limits appropriate to the host loop.

The safest design passes snapshots and requests, not borrowed pointers into live game objects.

The host remains in charge even while Lua decides what it would like to do:

Lua plans with owned data; the host decides whether each plan is still valid at commit time.

Load only the libraries you need

The Rust host creates the interpreter and selects three standard-library groups. new_with returns an error if setup fails; ? passes that error to the caller before any script runs.

use mlua::{Lua, LuaOptions, StdLib};

let lua = Lua::new_with(
    StdLib::TABLE | StdLib::STRING | StdLib::MATH,
    LuaOptions::default(),
)?;

This lab needs table helpers, string formatting, and math. It does not load the Lua io, os, debug, or package libraries.

Removing libraries is not a complete hostile-code sandbox. It is still good capability hygiene: a script cannot call a function that does not exist in its environment.

Expose one host function

The script needs a way to report what it observed. This closure accepts one Lua string, prints it with a prefix in the host process, and returns success; registering it under log makes the name callable from Lua.

Optional: practise the named operations and their inputs with a few whole-token blanks.

let log = lua.create_function(|_, message: String| {
    println!("[lua] {message}");
    Ok(())
})?;

lua.globals().set("log", log)?;

create_function converts Lua arguments into the requested host type. Passing a table where a String is required produces a Lua error instead of an unchecked cast.

A string converts to the callback’s StringThe registered callback requires a Rust String. A Lua string converts and reaches the host.

Lua scriptRegistered log callback

1. 1

   Data log("sample")

   Step 1: Lua script to Registered log callback

   The script passes a Lua string.

2. 2

   Alone Convert to String: succeeds

   Step 2: Registered log callback (alone)

   The registered signature asks for a String, and a Lua string can become one.

3. 3

   Reply Host receives "sample"

   Step 3: Registered log callback to Lua script

   The host’s Rust code sees an ordinary String.

The registered callback requires a Rust String. A Lua string converts and reaches the host.

A table fails the callback’s type conversionThe same callback refuses a table with a Lua type error instead of an unchecked cast.

Lua scriptRegistered log callback

1. 1

   Data log({})

   Step 1: Lua script to Registered log callback

   The script passes a table instead.

2. 2

   Alone Convert to String: fails

   Step 2: Registered log callback (alone)

   A table has no conversion to String, and the host never guesses.

3. 3

   Control Lua type error

   Step 3: Registered log callback to Lua script

   The script gets an error it can see. The host’s Rust code never runs on a wrong value.

The same callback refuses a table with a Lua type error instead of an unchecked cast.

The first closure argument is the active Lua handle. It is named _ here because logging does not need to create any Lua values.

Underneath, every call into a host function travels through Lua’s value stack: the caller supplies arguments, and the host function returns results through that stack. The lab’s game.distance(a, b) takes two position tables and returns one number. Take this call, and call its first table p and its second q:

local d = game.distance({ x = 0, y = 0, z = 0 }, { x = 3, y = 4, z = 0 })

The stack passes through three states:

top →table q

table p

game.distance

1. The Lua caller pushes the function value, then the two arguments in order. Each argument slot holds a reference to a table, not a copy of it.

index 2 →table q

index 1 →table p

2. The host function sees only its arguments, numbered from 1. mlua converts index 1 and index 2 into the closure's (Table, Table) parameters. A string or number in either slot fails that conversion and becomes a Lua error before the closure body runs.

top →5.0

3. The closure takes the differences 0 − 3 = −3, 0 − 4 = −4, and 0 − 0 = 0, and returns √((−3)² + (−4)² + 0²) = √(9 + 16 + 0) = √25 = 5.0. mlua pushes that one result and reports a count of 1, and Lua puts it where the function and both arguments used to be.

Prefer a namespace table

The single global log works for a first example, but a host with many functions needs an obvious boundary. Put those functions under one game table, so the next script call spells out who supplied the behavior:

Alternative: The game table is a labelled service counter: grouping callbacks makes it clear which operations come from the host.

let game = lua.create_table()?;
game.set("log", lua.create_function(|_, message: String| {
    println!("[lua] {message}");
    Ok(())
})?)?;
lua.globals().set("game", game)?;

Lua then calls:

game.log("observer started")

The game table becomes the documented boundary between engine and script.

Convert host records into Lua tables

The complete host creates a table for each copied entity:

fn snapshot_table(lua: &Lua, entities: &[EntitySnapshot]) -> mlua::Result<mlua::Table> {
    let result = lua.create_table()?;

    for (index, entity) in entities.iter().enumerate() {
        let item = lua.create_table()?;
        item.set("id", entity.id)?;
        item.set("name", entity.name)?;
        item.set("alive", entity.alive)?;

        let position = lua.create_table()?;
        position.set("x", entity.position[0])?;
        position.set("y", entity.position[1])?;
        position.set("z", entity.position[2])?;
        item.set("position", position)?;

        result.set(index + 1, item)?; // Lua sequences begin at one. 🔢
    }
    Ok(result)
}

Nested tables make the script readable: entity.position.x is clearer than entity[4].

For the lab’s sample data, the conversion produces this shape. Every Rust index moves up by one key, and each entity becomes two tables, one nested in the other:

The entity with id = 0 sits at Lua key 1: the ID is data copied from the game, and the key is only its place in the sequence.

Load a named script with context

script_path is the file the host chose to run. Rust reads its text, gives the Lua chunk that path as a name for errors, and executes it; failure at any step returns to the host through ?.

let source = std::fs::read_to_string(&script_path)?;
lua.load(&source)
    .set_name(script_path.to_string_lossy())
    .exec()?;

Naming the chunk gives errors a useful file label. The complete lab adds anyhow::Context so the host error also says which script failed.

Separate setup, execution, and results

A clear host follows this order:

1. create the Lua state;
2. apply resource limits;
3. construct the host API;
4. load script text;
5. execute it once or register callbacks;
6. collect bounded requested actions;
7. validate those actions in the host;
8. report errors without crashing the engine.

Do not let a script run during partial API construction. Do not hold a mutable game-state lock across script execution. Give Lua a copied snapshot and collect requests for later processing.

Narration: A script can call back into the host while it runs. Keeping an engine lock across that call can make otherwise valid work wait on itself.

This is a two-phase boundary. During planning, Lua reads an immutable snapshot and returns proposed actions. During commit, the host checks that the target, snapshot version, and entity IDs still match, and that the action is permitted in the current state. A plan based on an old snapshot is rejected instead of being applied to a different moment.

A script proposes; the host commits. This step-by-step trace needs JavaScript. Here is the code and where the run ends.

copy snapshot version 17
script prepares one selection request
wait for script execution to finish
check result and current snapshot version
commit only the accepted plan
report actual host changes

Result: one accepted host change. Language conversion alone did not establish action validity.

Final values: outcome = ok; snapshot_version = 17; changes = 1; pending = 0; script_succeeded = true; current_version = 17; accepted = true.

Read every step of the lesson’s example

1. Step 1, line 1. Start with the selected inputs. Follow the highlighted operation and the changing state below.

   outcome = ok.

2. Step 2, line 1. The host supplies copied data, not live game pointers.

   outcome = ok; snapshot_version = 17; changes = 0; pending = 0.

3. Step 3, line 2. Preparing a request is ordinary data construction.

   outcome = ok; snapshot_version = 17; changes = 0; pending = 1.

4. Step 4, line 3. Return to the host before considering effects.

   outcome = ok; snapshot_version = 17; changes = 0; pending = 1; script_succeeded = true.

5. Step 5, line 4. Compare the recorded version with the current owner’s version and require successful execution.

   outcome = ok; snapshot_version = 17; changes = 0; pending = 1; script_succeeded = true; current_version = 17; accepted = true.

6. Step 6, line 5. The host accepts this current request.

   outcome = ok; snapshot_version = 17; changes = 1; pending = 0; script_succeeded = true; current_version = 17; accepted = true.

7. Step 7, line 6. Result: one accepted host change. Language conversion alone did not establish action validity.

   outcome = ok; snapshot_version = 17; changes = 1; pending = 0; script_succeeded = true; current_version = 17; accepted = true.

Run all three useful scripts

Any computer

The observer logs copied entity data. The nearest-entity script measures living candidates and proposes one selection; the state-machine script proposes a marker and then stops. Compare those proposals with the host’s accepted-action output after each run.

cargo run --manifest-path lua-labs/Cargo.toml -- scripts/observer.lua
cargo run --manifest-path lua-labs/Cargo.toml -- scripts/nearest_entity.lua
cargo run --manifest-path lua-labs/Cargo.toml -- scripts/state_machine.lua

The host prints accepted actions after the script returns. That delay is deliberate: Lua proposes data, and the host remains the authority that decides what happens.

TL;DR: Lua proposes data; the host checks and applies the proposal after script execution returns successfully.

Why the host still needs validation

mlua safely converts values at the language boundary, but it cannot decide whether an entity exists or an action is currently allowed. The host must still check:

• entity IDs exist in the current snapshot;
• coordinates are finite and within the map;
• an action is allowed in the current state;
• the script has not exceeded a rate limit;
• the target still matches the verified local build.

Converting a value safely does not prove that the resulting action is allowed. A good host checks both.

Lesson 11.5

Snapshots as a Script Interface

Do not turn Lua into an untyped memory API

After building a memory reader, it is tempting to expose this:

-- ❌ Every version rule, bound, and permission now leaks into every script.
local bytes = memory.read(address, count)
memory.write(address, replacement)

That design gives a typo the power of the process handle. It also couples scripts to exact offsets and makes every mod responsible for pointer validation.

Expose domain meaning instead:

local entities = game.snapshot()
game.request({ kind = "select_entity", id = entities[2].id })

The host owns collection and validation

The Windows layer should:

1. open the target with the least required rights;
2. verify game build and architecture;
3. resolve versioned roots and pointer paths;
4. copy fields with bounds and plausibility checks;
5. create ordinary owned records;
6. close or retain handles according to one clear owner.

Only step 5 crosses into Lua.

The boundary turns unstable bytes into stable meaning, then turns script intent back into checked data:

Addresses stop at the memory reader; Lua receives fields with names, units, and a snapshot version.

TL;DR: Expose named, validated values to Lua, and keep build-specific addresses inside the host observer.

#[derive(Clone, Debug)]
struct EntitySnapshot {
    id: u32,
    name: String,
    position: [f32; 3],
    alive: bool,
}

There are no process addresses in this type. A script cannot keep a stale pointer because it never receives one.

Why avoid raw pointers here? Lua can represent native objects through userdata. Full userdata has Lua-managed storage and a host-defined metatable; light userdata is essentially an unowned pointer value. If a native entity dies while a script retains its raw address, the same address may later belong to a different entity. A copied snapshot avoids that lifetime problem for observation. When a request needs persistent identity, use a validated handle rather than a remembered address.

A handle can pair a numbered slot with a generation counter. Every time a slot is reused for a new entity, its generation changes. Suppose Lua remembers slot 3, generation 6. If that entity dies and slot 3 is reused at generation 7, the host rejects the stale pair rather than acting on the new occupant:

The slot number stays 3, the generation moves from 6 to 7Checking both parts prevents an old handle from naming the new entity that reused its slot.

Lua scriptHost entity table

1. 1

   Reply Handle: slot 3, generation 6

   Step 1: Host entity table to Lua script

   Lua remembers both numbers.

2. 2

   Alone Slot 3 reused as generation 7

   Step 2: Host entity table (alone)

   The host reuses the cheap slot, and bumps the generation to mark it as a new life.

3. 3

   Request Use handle: slot 3, generation 6

   Step 3: Lua script to Host entity table

   The script, unaware, still holds the old handle.

4. 4

   Control Rejected: slot 3 is generation 7, not 6

   Step 4: Host entity table to Lua script

   The slot matches but the generation does not, so the handle names a dead entity. The host refuses instead of acting on whoever lives in slot 3 now.

Checking both parts prevents an old handle from naming the new entity that reused its slot.

Lesson 3.10 developed the same identity rule for a game collection. Here it protects the boundary between a script’s request and a changing game world.

Here is one entity as a hypothetical build lays it out in game memory, and the same entity after the observer has copied it into a snapshot and the host has turned that into a Lua table:

+0x107

+0x304.0

+0x349.0

+0x382.0

+0x3C1

+0x400x1F2A8C40

id, u32

position, three f32

alive byte

name pointer

Game memory, labelled by offset from the start of the object; only the fields the snapshot needs are shown. Each f32 is 4 bytes wide, so x, y, and z sit at 0x30, 0x30 + 4 = 0x34, and 0x34 + 4 = 0x38. The one-byte alive flag at 0x3C is followed by 3 unused bytes, because an 8-byte pointer starts on a multiple of 8 and 0x40 (64 = 8 × 8) is the next one. The name itself is not stored here: the object holds the address of text kept elsewhere, which the observer follows and copies with a length limit.

id7

namearcher

position.x4.0

position.y9.0

position.z2.0

alivetrue

The Lua table the script receives. Every value arrives under a name, the alive byte 1 has become the boolean true, and no offset or pointer survives the copy.

A snapshot has a time and version

Real snapshots should carry metadata:

#[derive(Clone, Debug)]
struct GameSnapshot {
    sequence: u64,
    captured_at_ms: u64,
    profile: String,
    entities: Vec<EntitySnapshot>,
}

Put an abstraction barrier between bytes and game meaning

An abstraction barrier is a rule about who may know a representation. The observer below the barrier knows that one build stores an entity position at a particular pointer path. Lua above the barrier knows only that an entity has an id, name, position, and alive state.

Alternative: The abstraction barrier is a translation desk: scripts ask about entities, while the observer translates those names into one build’s storage layout.

Lua automation
  depends on: snapshot fields and bounded request meanings
---------------- abstraction barrier ----------------
memory observer
  depends on: Windows handles, build profiles, offsets, encodings, and bounds

If a later build moves the position field, only the observer and its target profile should change. Every script should not learn a new offset.

Make the source of snapshots replaceable too:

trait SnapshotSource {
    fn next_snapshot(&mut self) -> anyhow::Result<GameSnapshot>;
}

fn collect_for_lua(source: &mut impl SnapshotSource) -> anyhow::Result<GameSnapshot> {
    let snapshot = source.next_snapshot()?;
    anyhow::ensure!(
        snapshot.entities.len() <= 256,
        "snapshot exceeds the published entity limit"
    );
    Ok(snapshot)
}

A live Windows observer and a replay-file reader can both implement SnapshotSource. The same Lua state machine can then run against recorded data in a test and against the verified game in the lab. That is not just reuse: it lets you test automation without giving the test a process handle.

When Lua requests an action, include the sequence it observed:

game.request({
    kind = "select_entity",
    entity_id = target.id,
    based_on = snapshot.sequence,
})

The host can reject a request based on a snapshot that is too old. This is safer than pretending copied data is live.

The script did nothing wrong: entity 7 really was alive in snapshot 41. The game moved on while the script was deciding, and based_on lets the host see that the request describes a moment that has already passed.

A snapshot does not keep its entity alive. This step-by-step trace needs JavaScript. Here is the code and where the run ends.

read the selected inputs
evaluate each stated condition
combine the required conditions
perform the effect only when accepted
otherwise retain the old state
report the result and its limits

Result: refuse selection of an absent identity. Copying fields never keeps the original object alive.

Final values: id = 7; present = no; snapshot_sequence = 41; current_sequence = 42; entity_found_now = false; accepted = false; selected = none.

Read every step of the lesson’s example

1. Step 1, line 1. Start with the selected inputs and follow how the next operation changes the state.

   id = 7; present = no.

2. Step 2, line 2. The copied archer remains in the script’s old table even when the live entity disappears.

   id = 7; present = no; snapshot_sequence = 41; current_sequence = 42; entity_found_now = false.

3. Step 3, line 3. Accept only when the required conditions all hold.

   id = 7; present = no; snapshot_sequence = 41; current_sequence = 42; entity_found_now = false; accepted = false.

4. Step 4, line 5. The model retains its previous state.

   id = 7; present = no; snapshot_sequence = 41; current_sequence = 42; entity_found_now = false; accepted = false; selected = none.

5. Step 5, line 6. Result: refuse selection of an absent identity. Copying fields never keeps the original object alive.

   id = 7; present = no; snapshot_sequence = 41; current_sequence = 42; entity_found_now = false; accepted = false; selected = none.

Watch it happenKeep the snapshot; refuse the stale action

Entity 7 is an alive archer at (4, 9, 2) in sequence 41. Its copied snapshot moves to Lua. The live archer disappears at sequence 42 while the snapshot stays unchanged. A select_entity request based on 41 returns to the host, which cannot find entity 7 and sends a refusal without taking an action.

Read the steps

1. At sequence 41, entity 7 is a living archer at position (4, 9, 2). The host validates that observation and creates owned snapshot fields.
2. Give Lua snapshot 41. The table keeps its own values; the script does not hold a live reference to the archer in the game world.
3. The world advances to sequence 42 and entity 7 despawns. Remove the live archer. Lua still owns the earlier snapshot, including alive: true.
4. Lua requests select_entity for ID 7 and labels the request based_on 41. The structured request tells the host which observation produced the decision.
5. The host revalidates at action time. Its current sequence is 42, and a lookup in the current world finds no entity 7. The earlier successful copy cannot authorize this action.
6. Return a useful refusal to Lua and keep the host alive. The old snapshot remains a valid historical observation; selecting a missing entity is still refused.

Copying protects the observation from memory reuse. Current-state validation protects the later action.

Requests are data, not commands

Bad interface:

game.execute("select " .. target.id) -- ❌ a command-language injection boundary

Better interface:

game.request({ kind = "select_entity", id = target.id }) -- ✅ structured data

The host matches an explicit enum:

enum RequestedAction {
    SelectEntity(u32),
    PlaceMarker { x: f32, y: f32, z: f32 },
}

Unknown kind values fail. No string becomes PowerShell, a console command, or arbitrary game code.

Validate again at action time

Between snapshot and request processing, an entity may disappear. Check:

• the sequence is recent;
• the entity still exists;
• its current state permits the action;
• all numbers are finite;
• coordinates remain within known map bounds;
• the per-script action budget is not exhausted.

This is a time-of-check/time-of-use issue. Validation during snapshot creation does not guarantee future state.

Narration: A unit can disappear after the snapshot was copied. Rechecking its identity when processing a request prevents acting on an outdated observation.

Keep read and write capabilities separate

Most analysis scripts need only snapshots and logs. Give them an observer API with no request function at all.

When an offline automation lab needs actions, load it with a different capability set:

ObserverScript: snapshot + log
AutomationScript: snapshot + log + two bounded requests
DeveloperScript: extra diagnostics in a disposable test build

Do not decide permissions from a script-provided name. The host chooses the API before executing the script.

Test the boundary without a game

The lua-labs host uses a simulated snapshot. Add tests where Lua requests:

• a missing entity ID;
• 0/0 or infinity as a coordinate;
• an unknown action;
• too many actions;
• an action from an expired sequence.

The host should reject each request with a useful error and remain alive.

This architecture also makes the script portable. The same Lua logic can consume a recorded replay, a simulated world, or a live observer because it depends on the snapshot contract rather than Windows memory details.

Lesson 11.6

State Machines for Lua Automation

Imagine a helper script that selects the next living unit in a local game. It can observe a snapshot, request one selection, and wait for confirmation. If it repeats the request as fast as the interpreter can run, it may never observe the result or respond to a stop signal. Named states give each step a place and a condition for moving on.

Narration: Repeating a selection request before observing its confirmation can flood the host with duplicate intentions instead of advancing the script.

Define the bot’s states and transitions first

This loop is short and dangerous to reason about:

-- ❌ Repeats forever with no state, confirmation, or stop rule.
while true do
    game.request({ kind = "select_entity", id = 1 })
end

A state machine gives each phase a name and defines why the script may move to another phase.

Formally, one update uses the current state plus one input to produce a next state and, sometimes, an output:

Alternative: Read a state machine as a travel itinerary: the current stop and one event determine the next stop, with any requested action recorded separately.

(current state, validated snapshot or event) -> (next state, optional request)

That model separates policy from mechanism. The state machine chooses whether a request is appropriate. The host decides how to deliver it, whether the current target still permits it, and how to report success or failure.

Do not put every game fact into the state name. WAITING_FOR_SELECTION describes the bot’s control phase; the selected entity ID, request sequence, and remaining timeout are data owned by that phase.

The request is confirmed before the budget runs outAfter one selection request the script waits, counting down 20 ticks.

1. 1 Send one request and wait with 20 ticks

   Script state

   Waitstate

   20ticks left

   The script sends a single selection request and enters Wait.

2. 2 Each unconfirmed update uses one tick

   Script state

   Waitstate

   19ticks left

   Updates that do not confirm the request decrement the counter.

3. 3 Confirmation arrives: back to Observe

   Script state

   Observestate

   (not needed)ticks left

   The request worked, so the script returns to watching.

After one selection request the script waits, counting down 20 ticks.

Nothing confirms the request, so the script stopsThe tick budget turns an endless retry into a clear stop.

1. 1 Send one request and wait with 20 ticks

   Script state

   Waitstate

   20ticks left

   The same start as before.

2. 2 Updates keep failing to confirm

   Script state

   Waitstate

   … 3, 2, 1ticks left

   The counter counts down toward zero.

3. 3 Zero reached: Stop

   Script state

   Stopstate

   0ticks left

   The script stops instead of sending the request endlessly.

The tick budget turns an endless retry into a clear stop.

This interactive lab needs JavaScript. The lesson text around it still explains the same idea.

Represent states as strings carefully

The five names below are control phases, not game facts. The bot record holds the current phase and the data needed while waiting: a chosen entity, the sequence number of the request, and a timeout counter.

local State = {
    OBSERVE = "observe",
    CHOOSE = "choose",
    REQUEST = "request",
    WAIT = "wait",
    STOP = "stop",
}

local bot = {
    state = State.OBSERVE,
    selected = nil,
    request_sequence = nil,
    wait_ticks = 0,
}

Lua has no built-in enum. A table of constants reduces spelling mistakes and gives one place to see all states.

One update performs bounded work

Each host call supplies a current snapshot and runs at most one branch. This sketch uses the State table above, the host’s game.request, and the choose_nearest_living helper defined below. The result is false only when the bot has stopped; otherwise the changed bot record says which phase comes next.

local function update(bot, snapshot)
    if bot.state == State.OBSERVE then
        bot.snapshot = snapshot
        bot.state = State.CHOOSE

    elseif bot.state == State.CHOOSE then
        bot.selected = choose_nearest_living(bot.snapshot.entities)
        bot.state = bot.selected and State.REQUEST or State.STOP

    elseif bot.state == State.REQUEST then
        game.request({
            kind = "select_entity",
            id = bot.selected.id,
            based_on = bot.snapshot.sequence,
        })
        bot.request_sequence = bot.snapshot.sequence
        bot.wait_ticks = 20
        bot.state = State.WAIT

    elseif bot.state == State.WAIT then
        if snapshot.selected_id == bot.selected.id then
            bot.state = State.OBSERVE -- confirmed ✅
        elseif bot.wait_ticks == 0 then
            bot.state = State.STOP -- timed out safely
        else
            bot.wait_ticks = bot.wait_ticks - 1
        end

    elseif bot.state == State.STOP then
        return false
    else
        error("unknown bot state: " .. tostring(bot.state))
    end

    return true
end

The host calls update at a controlled rate. The script does not own an infinite loop and cannot flood actions between frames.

TL;DR: One bounded update lets the host keep drawing and handling shutdown between the script’s state transitions.

OBSERVE stores one snapshot. CHOOSE reads that same version, and REQUEST tags its proposed action with the stored sequence number; the host checks the request against current game state before acting. Later WAIT calls use the latest snapshot to see whether selection was confirmed. Keeping those two snapshots distinct is why a stale choice cannot silently become authority.

Bounded work makes scheduling visible. One call performs at most one transition and proposes at most one action. The host can measure it, stop between calls, and prevent a fast script loop from starving rendering or input processing.

Separate choosing from acting

choose_nearest_living should be a pure function:

local function choose_nearest_living(entities)
    local local_player = entities[1]
    local best = nil
    local best_distance = math.huge

    for index = 2, #entities do
        local candidate = entities[index]
        if candidate.alive then
            local distance = game.distance(local_player.position, candidate.position)
            if distance < best_distance then
                best = candidate
                best_distance = distance
            end
        end
    end
    return best
end

It reads input and returns a choice. It does not log, request, sleep, or mutate the snapshot. That makes it easy to test with fixed tables.

Give stop the highest priority

Before every update, the host can check:

• user pressed the stop hotkey;
• game process exited;
• profile no longer matches;
• script exceeded an error limit;
• action request was rejected;
• snapshot has been invalid for too long.

Any of these moves the host to stopped even if Lua wants to continue. The script is a guest, not the authority over shutdown.

Test transitions as a table

Starting state	Input	Expected next state
Observe	valid snapshot	Choose
Choose	living candidate	Request
Choose	no candidate	Stop
Request	accepted request	Wait
Wait	selection confirmed	Observe
Wait	timeout reaches zero	Stop
Any	user cancellation	Stop

Create a test snapshot for every row. Also pass an unknown state and confirm the error contains its name.

The lab’s small example

Run:

cargo run --manifest-path lua-labs/Cargo.toml -- scripts/state_machine.lua

The included script performs a tiny observe → mark → stop path against simulated data. Extend it one transition at a time, keeping every request bounded and visible in the host’s final output.

State machines do not make automation intelligent by themselves. They make its assumptions, wait conditions, and failures readable—which is more important first.

Lesson 11.7

Script Budgets, Errors, and Recovery

Suppose that helper script encounters a missing unit halfway through a turn. The game still needs to draw the next frame and let the player regain control. The script host therefore needs a clear error report, a bound on work, and a safe way to disable the failing script.

A script can fail without being malicious

Common mistakes include:

• an infinite loop;
• a table that grows every update;
• calling a missing function;
• assuming an entity always exists;
• dividing by zero and producing a non-finite value;
• repeatedly requesting an action the host rejects.

An embedded interpreter must treat failure as a normal result. One script error should not crash the game, leak resources, or leave input stuck.

Before setting limits, locate where the failure occurred. A syntax error means the source never became a runnable function. A runtime type error means execution reached unsuitable values. A host-API error means the script called the engine but violated that function’s contract. A gameplay error may raise no exception at all: every layer ran, but the requested action was wrong.

Alternative: Locate the failed layer first: unreadable syntax, unsuitable runtime values, rejected host requests, and wrong gameplay decisions need different repairs.

The first three can produce diagnostic errors; the fourth needs an assertion about expected behavior. Keep that distinction when choosing what to log and what to test.

Budgets describe several resources

“The script is small” does not imply that it is cheap to run. Bound the dimensions separately:

• source and bytecode size;
• Lua-managed memory;
• VM instructions per update;
• call-frame depth;
• host-callback calls and returned data;
• wall-clock deadline for work outside instruction counting;
• queued actions and log output.

Choose whether a budget resets per callback, per frame, or per whole script session. A limit with no time window is ambiguous. Record which budget stopped execution so a learner can distinguish an infinite loop from memory growth or excessive host calls.

TL;DR: A budget needs both a resource and a reset window, so the same limit has one clear meaning across callbacks and frames.

Resource	Guard	Reset window
Source and bytecode	Maximum input bytes	Script load
Lua-managed memory	Allocator limit	Script session
VM instructions	Hook counter	One update
Call frames	Maximum depth	One call chain
Host callbacks	Call and returned-byte caps	One update
Wall-clock work	Host deadline or cancellation	One update
Actions and logs	Queue and output-byte caps	One update

When a limit is crossed, stop that update, discard its uncommitted actions, and report the exact budget. Do not quietly continue with half-produced output.

Limit memory

The lab host applies a four-mebibyte Lua allocation limit. The multiplication converts four mebibytes to bytes before the host sets the limit:

let lua = mlua::Lua::new_with(
    mlua::StdLib::TABLE | mlua::StdLib::STRING | mlua::StdLib::MATH,
    mlua::LuaOptions::default(),
)?;

lua.set_memory_limit(4 * 1024 * 1024)?;

Choose a limit after measuring realistic scripts. Too low prevents normal work; unlimited growth lets one bug consume the process.

The limit covers Lua-managed allocations, not every resource a host callback might allocate. Host functions need their own bounds.

Limit instructions

mlua can call a host hook after a chosen number of VM instructions. The hook may run while Lua is executing, so its counter has to be shared safely with the Rust closure: Arc shares ownership of the counter, and Mutex protects one update to it at a time. The clone shares the same counter; it does not reset the budget.

use std::sync::{Arc, Mutex};
use mlua::{HookTriggers, VmState};

let calls = Arc::new(Mutex::new(0_u32));
let counter = Arc::clone(&calls);

lua.set_hook(
    HookTriggers::new().every_nth_instruction(1_000),
    move |_, _| {
        let mut calls = counter.lock()
            .map_err(|_| mlua::Error::RuntimeError("hook counter failed".into()))?;
        *calls += 1;
        if *calls > 100 {
            return Err(mlua::Error::RuntimeError(
                "script exceeded its instruction budget".into()
            ));
        }
        Ok(VmState::Continue)
    },
)?;

Since the hook fires every 1,000 instructions and allows at most 100 calls, a script gets roughly 100,000 VM instructions per update before this particular budget stops it.

The hook is not a stopwatch. Different instructions cost different amounts of real time, and host callbacks can do work between hooks. It is one defense against runaway Lua bytecode.

The host hook counts one call per 1,000 Lua instructions and raises an error on call 101, so a runaway loop is stopped after roughly 100,000 instructions per update. The interactive version needs JavaScript; the lesson text around it explains the same idea.

Predict first

The hook above fires every 1,000 instructions and raises an error when its count passes 100. Suppose the host never sets the count back to 0, and a well-behaved script runs 30,000 instructions in every update.

In which update does the instruction budget stop the script?

Answer: In update 4. 30,000 ÷ 1,000 = 30 hook calls per update. After three updates the count is 30 + 30 + 30 = 90; in update 4 the 11th call makes it 101, more than 100, so the error fires after 11,000 of that update’s instructions.

One instruction budget, two reset windowsThe hook counts one call per 1,000 Lua instructions and raises an error when the count passes 100. Choose when the host sets the count back to 0.

Hook calls, update by update

Hook calls counted

Calls in update #1, #2, …

30#1

30#2

30#3

11#4

–#5

↓ add to the count

Count (carried over)

30

60

90

101 > 100error

–

Result

Stopped in update 4: instruction budget exceeded

Each update runs 30,000 instructions, so the hook fires 30,000 ÷ 1,000 = 30 times. Never reset, the count carries over: 30, 60, 90. In update 4, call 11 makes the count 101, more than 100, so the error stops the script after 11,000 of that update’s instructions.

Reset the instruction allowance at a controlled host boundary, not from inside the script. If the hook counter is shared across updates, document that as a session budget; if each update gets a fresh allowance, also cap how often updates can be requested.

See the budget fail on purpose

scripts/budget_failure.lua contains:

-- ❌ This intentional failure demonstrates the host's instruction budget.
while true do
end

Run it:

cargo run --manifest-path lua-labs/Cargo.toml -- scripts/budget_failure.lua

Expected result: the host returns a contextual error naming the script and the exceeded budget. If the terminal hangs forever, the limit is not working.

Protect every host callback

A function exposed to Lua should validate:

• argument types and string lengths;
• sequence lengths;
• numeric finiteness and range;
• referenced IDs;
• permissions for the current script;
• rate and action budgets.

Never hold a poisoned mutex or important engine lock while running arbitrary script code. Copy inputs first, execute, then validate collected outputs.

Make errors useful but not secret-leaking

Development builds should report:

• script path or stable identifier;
• line and traceback when available;
• host API function involved;
• which type, range, permission, or action check failed;
• whether the script was disabled or may retry.

Do not dump process memory, account tokens, full private chat logs, or arbitrary host paths into a public error report.

Use a failure policy

One practical policy is:

Do not catch an error and continue from half-mutated host state. Lua requests should be queued and committed only after the script returns successfully.

Narration: A script may fail after preparing several requests. Committing only after successful completion keeps half a plan from altering the host.

Test more than the happy path

Create scripts that:

• request an unknown action;
• omit a required field;
• pass a string where an ID is expected;
• allocate an ever-growing table;
• loop forever;
• throw an error inside a helper function;
• return normally with zero actions;
• submit the maximum allowed valid action list.

For each test, assert the result, action count, error category, and whether the script remains enabled.

Sandboxing is a design, not one switch

No single setting makes arbitrary scripts safe. The useful layers are:

• a limited standard library;
• no arbitrary native module loading;
• a narrow host API;
• copied snapshots;
• structured action requests;
• memory, instruction, time, and rate limits;
• least-privilege Windows handles behind the host boundary;
• clear cancellation and recovery.

Lua is most valuable when it makes small policies easy to change while the host keeps powerful capabilities narrow and testable. 🔒

Lesson 11.8

What Any Computer Can Compute

Your computer can run a game, a web browser, and a program that pretends to be a console from 1985. Nobody built it separately for each job. Why can one machine run all of them? And why can no checker always decide whether an arbitrary program will eventually stop on a given input?

We have seen a host run scripts and limit the work they can do. Before opening the virtual machine that executes them, consider why one program can run another at all—and why a host needs a step budget instead of a perfect test for whether a script will finish.

Both answers come from a model of computing published in 1936, years before anyone built an electronic computer. We will build the model by hand, then connect it to code bytes, program analysis, and bounded interpreters.

A machine small enough to hold in your head

The mathematician Alan Turing wanted to pin down exactly what “following a procedure” means. He imagined the simplest mechanism that could still carry out any step-by-step method a person could follow with pencil and paper:

• a tape divided into cells, each holding one symbol, as long as it needs to be;
• a head that sits over one cell at a time and can read or overwrite it;
• a state, which is a single named setting the machine is in, such as carry or done;
• a transition table, often called a rule table, that says, for every combination of current state and symbol under the head, what to write, which way to move, and which state comes next.

That mechanism is a Turing machine. It runs by repeating one step: look up the table row for the current state and the symbol under the head, write, move one cell left or right or stay put, and switch state. When no row matches, the machine stops. The usual word for stopping is halting.

Here is a complete machine that adds one to a binary number. It starts in state carry with the head on the rightmost digit:

State	Symbol under the head	Write	Move	Next state
carry	1	0	left	carry
carry	0	1	stay	done
carry	blank	1	stay	done

The state done has no matching table rows, so reaching it halts the machine. Put 1011 (eleven) on the tape, with blank cells, drawn _, on either side. The highlighted cell is the one under the head:

_

1

0

1

head1

_

Step 1, state carry. The head reads 1, so it writes 0 and moves left.

_

1

0

head1

0

_

Step 2, state carry. Another 1: write 0 and move left again.

_

1

head0

0

0

_

Step 3, state carry. The head reads 0, so it writes 1, stays put, and switches to done.

_

1

head1

0

0

_

1100, which is twelve

State done has no matching row, so the machine halts.

This is ordinary school addition. Adding one to a 1 gives 0 and carries one to the left; adding the carry to a 0 gives 1 and the carry is used up. The third row handles 111: the carry runs past the leftmost digit into a blank cell, and the machine writes a new leading 1, giving 1000.

Three rows are the whole program, yet they handle a number of any length. Notice also what the machine does not know. Nothing in the table mentions “eleven” or “twelve”. The machine moves symbols around, and the meaning — binary numbers — comes from us. Lesson 1.2 said the same thing about bytes in memory: meaning comes from the code that reads them, not from the bytes.

Carry one through a binary tape. This step-by-step trace needs JavaScript. Here is the code and where the run ends.

state = carry; head = rightmost digit
read the current symbol
if symbol == 1: write 0; move left
if symbol == 0: write 1; state = done
if symbol is blank: write 1; state = done
halt in done; read the resulting number

Result: 11 becomes 12, represented by 1100. Done has no further transition.

Final values: number = 11; state = done; head = 2; tape = _1100; result = 12.

Read every step of the lesson’s example

1. Step 1, line 1. Start with the selected inputs. Follow the highlighted operation and the changing state below.

   number = 11.

2. Step 2, line 1. Start in carry at the rightmost digit.

   number = 11; state = carry; head = 4; tape = _1011.

   Memory: 0 = _; 1 = 1; 2 = 0; 3 = 1; 4 = 1 (head).

3. Step 3, line 2. The head reads 1, so this carry is not finished.

   number = 11; state = carry; head = 4; tape = _1011.

   Memory: 0 = _; 1 = 1; 2 = 0; 3 = 1; 4 = 1 (head).

4. Step 4, line 3. Write 0 and move one cell left with the carry still active.

   number = 11; state = carry; head = 3; tape = _1010.

   Memory: 0 = _; 1 = 1; 2 = 0; 3 = 1 (head); 4 = 0.

5. Step 5, line 2. The head reads 1, so this carry is not finished.

   number = 11; state = carry; head = 3; tape = _1010.

   Memory: 0 = _; 1 = 1; 2 = 0; 3 = 1 (head); 4 = 0.

6. Step 6, line 3. Write 0 and move one cell left with the carry still active.

   number = 11; state = carry; head = 2; tape = _1000.

   Memory: 0 = _; 1 = 1; 2 = 0 (head); 3 = 0; 4 = 0.

7. Step 7, line 4. The head found 0; write 1 and consume the carry.

   number = 11; state = done; head = 2; tape = _1100.

   Memory: 0 = _; 1 = 1; 2 = 1 (head); 3 = 0; 4 = 0.

8. Step 8, line 6. Result: 11 becomes 12, represented by 1100. Done has no further transition.

   number = 11; state = done; head = 2; tape = _1100; result = 12.

   Memory: 0 = _; 1 = 1; 2 = 1 (head); 3 = 0; 4 = 0.

How the model relates to a computer

Line the parts up with the computer you are using now:

Turing machine	Your computer
the tape	memory
where the head is	an address
the current state	the CPU’s registers, including the instruction pointer
the transition table	the program, carried out through the CPU’s instruction set
one step	one instruction

These are analogies, not identical parts. Two differences matter:

A real CPU can jump straight to an address, while the head walks one cell at a time. In the idealized model, that changes speed rather than the set of computations: the head could eventually walk to a reachable cell.

TL;DR: A small computing model separates the essential steps of calculation from the hardware used to perform them.

A real computer also has a fixed amount of memory, while the tape never runs out. That difference does matter to a literal claim about what can be computed: a finite machine eventually runs out of states or memory. The Turing machine tells us what a procedure could compute if it had as much time and storage as it needed. Real computers approximate that model for tasks that fit their resource limits.

The universal machine: programs are data

Turing’s most important idea came next. A transition table is itself only a list of symbols, so it can be written onto a tape like anything else. He then described a single machine, the universal Turing machine, that reads another machine’s transition table from its tape and carries out that machine’s steps one by one. One fixed machine can therefore imitate every other machine. To change what it does, you change what is on the tape, not the machine.

One fixed interpreter applies rule data to a tapeThe three rule rows in the table above are data. The tape starts as 1011 in state carry; each step the interpreter finds the row for its state and the symbol under the head, then does what that row says. ▲ marks the cell under the head.

1. 1 Row 1 matches: write 0, move left

   carry, 1 → write 0, leftrule row 1 · next state carry

   1

   0

   1▲

   0

   carry with a 1 under the head matches row 1: 1011 becomes 1010.

2. 2 Row 1 matches again

   carry, 1 → write 0, leftrule row 1 · next state carry

   1

   0▲

   0

   0

   The next symbol is also 1, so the same row applies: 1010 becomes 1000.

3. 3 Row 2 matches: write 1, done

   carry, 0 → write 1, stayrule row 2 · next state done

   1

   1▲

   0

   0

   carry meets 0: write 1 and stop. 1100 is 1011 plus one. Different rule data would make the same interpreter compute something else.

The three rule rows in the table above are data. The tape starts as 1011 in state carry; each step the interpreter finds the row for its state and the symbol under the head, then does what that row says. ▲ marks the cell under the head.

Alternative: A program can be input to another program. An interpreter reads that input and performs the operations it describes.

The computers and game processes in this book use stored programs: instructions and data are represented as bytes in addressable memory. This arrangement is called a stored-program computer. It lets the tools in this book inspect code bytes as well as game data, subject to memory protections. Here are a few bytes of a running game, part code and part data:

0x004010008B

45

08

0x0040100303

C8

0x0050100064

00

00

00

an instruction: mov eax, [ebp+8]

another: add ecx, eax

data: the u32 100

Nothing in the bytes says which are instructions and which are data. The CPU treats bytes as instructions only when the instruction pointer reaches them.

That has three consequences you will use constantly:

• Code can be read like data. A disassembler reads code bytes and names the instructions they encode. That is how Chapter 2 turned a game’s machine code into readable assembly.
• Code can be written like data. A software breakpoint is a single byte, 0xCC, written over the first byte of an instruction (Lesson 2.4). A code cave is new instructions written into memory, and a patch is old ones overwritten (Lesson 2.9).
• Code can run other code. Lua’s virtual machine in Lesson 11.9 is a program whose data is another program. An emulator, in Lesson 13.9, is a program whose data is the software of an entire other computer.

Here is the second point in bytes. A debugger sets a breakpoint on the first instruction above:

0x00401000CC

45

08

0x0040100303

C8

now int3, then two leftover bytes

One byte changed. When the instruction pointer arrives here, the CPU executes int3 and stops for the debugger instead of loading eax.

If code is just bytes, what stops a program from overwriting its own instructions? Nothing in the model does. The protection comes from outside it: the operating system marks each page of memory as readable, writable, executable, or some combination, and the CPU refuses any access the marks forbid. That is why Lesson 6.5 treats a page that is both writable and executable as worth a second look. It is a place where data can become code.

Turing complete: when a system can compute anything

A system is Turing complete when it can carry out anything a Turing machine can, given enough time and memory. In their idealized forms, general-purpose languages such as Rust, C++, Lua, and assembly qualify. So do some systems nobody designed as computers. Conway’s Game of Life, a grid of cells that live or die according to neighboring live-cell counts, can be arranged to compute anything in this sense. Players have also built working processors inside Minecraft out of redstone circuits; any one build is still limited by the game’s actual resources.

The useful consequence for you concerns what a game loads. A texture or a sound file is data: the game reads it in one fixed way, so the most a strange one can usually do is trip over a bug in the code that reads it. A script is different. A Wesnoth add-on can contain Lua, and a mod that ships a script is shipping a program. A Turing-complete script can compute anything within the resources available to it, and what it is allowed to touch is limited by what its host exposes. That is why the Lua lessons separate the script’s behavior from the game objects and operations its host permits.

Some questions no program can answer

The universal machine raises an obvious hope. If one program can run any other program, perhaps one program could also examine any other program and tell you what it will do. Turing showed in the same 1936 paper that this is impossible. The version below is the standard modern form of his argument, and it is short enough to follow in full.

Take the simplest question you could ask: will this program eventually stop, or run forever? Suppose someone hands you a checker, halts(program, input), that always answers that question correctly. Now write this program and call it contrary:

contrary(program):
    if halts(program, program):     ask what program does when fed itself
        loop forever
    else:
        stop

Now feed contrary to itself:

If the checker says contrary(contrary) halts, contrary loops forever. If the checker says it runs forever, contrary stops at once. Whatever the checker answers, it is wrong, so a checker that is always right cannot exist. This is the halting problem: no program can correctly decide, for every program and every input, whether that program halts.

The same limit reaches other questions about what a program does, such as “Does it ever write to this address?” A question that no single method answers correctly for every possible program is called undecidable. The optional reference below gives the general result.

What that means for the tools in this book

Undecidable does not mean hopeless. It means no tool can be right about every program. Real tools cope by approximating, and every approximation has a known way to be wrong:

• A disassembler has to decide which bytes are instructions and which are data. On x86, instructions have different lengths, so starting one byte too early or too late produces a listing that looks plausible and is completely wrong. Disassemblers use good heuristics and usually get it right. When a listing looks odd, check it against what the program actually executes in a debugger.
• A decompiler rebuilds loops, variables, and types that the compiler threw away. Its output is a well-informed guess, so treat it as one.
• A signature scanner, whether antivirus or anti-cheat, cannot decide what arbitrary code does. It looks for known byte patterns and known behavior instead, so it can miss what it has never seen and occasionally flag something harmless.
• A step budget exists because a host cannot know in advance whether a script will ever finish. All it can decide is how long it is willing to wait: the budget guarantees that the host stops waiting, not that the script would never have finished. Lesson 11.7 sets such a budget for Lua scripts, and the virtual machine in Lesson 11.9 checks one in its loop.

The practical distinction follows directly. Reading code tells you what might happen. Running it under control, on a specific input, tells you what did happen on that input. That is why the lessons pair reading code with running it.

Run the machine yourself

Any computer

The portable lab turing_machine_lab.rs is a short Turing machine simulator. Its transition tables are plain text that the simulator reads when it starts. One fixed program can therefore run different machines described by its input, within the lab’s finite memory and step budget. In the Rust source, machine.rules names the map of transition-table rows. That demonstrates the universal-machine idea without claiming that the lab itself has an unbounded tape.

turing_machine_lab.rs

rust-labs/src/bin/ · Rust, 356 lines

View on GitHub ↗

Show the codeHide the code

//! Turing machine lab for Lesson 1.11.
//!
//! The simulator's "program" is a plain-text rule table, read at run time.
//! That makes the simulator a small universal machine: one fixed program
//! that carries out whatever machine its input describes. It runs a binary
//! incrementer, then a machine that never halts, under a step budget.

use std::collections::{BTreeMap, HashMap};
use std::error::Error;
use std::fmt;

const BLANK: char = '_';

/// Adds one to a binary number. Start on the rightmost digit in `carry`.
const INCREMENTER: &str = "\
carry 1 -> 0 L carry   # 1 plus a carry is 0, and the carry moves left
carry 0 -> 1 S done    # 0 plus a carry is 1, and the carry is used up
carry _ -> 1 S done    # ran off the left end: write a new leading 1
";

/// Writes 1s to the right forever. This machine never halts.
const FILLER: &str = "\
fill _ -> 1 R fill
";

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Move {
    Left,
    Right,
    Stay,
}

impl Move {
    fn delta(self) -> i64 {
        match self {
            Move::Left => -1,
            Move::Right => 1,
            Move::Stay => 0,
        }
    }
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
struct Rule {
    write: char,
    movement: Move,
    next: usize,
}

/// A machine is nothing but a rule table. States are stored as numbers;
/// their names exist only so people can read the table and the output.
#[derive(Debug)]
struct Machine {
    state_names: Vec<String>,
    rules: HashMap<(usize, char), Rule>,
}

#[derive(Debug, PartialEq, Eq)]
enum ParseError {
    WrongFieldCount { line: usize },
    BadSymbol { line: usize },
    BadMove { line: usize },
    DuplicateRule { line: usize },
}

impl fmt::Display for ParseError {
    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            ParseError::WrongFieldCount { line } => {
                write!(
                    formatter,
                    "line {line}: expected `state read -> write move next`"
                )
            }
            ParseError::BadSymbol { line } => {
                write!(
                    formatter,
                    "line {line}: a symbol must be exactly one character"
                )
            }
            ParseError::BadMove { line } => {
                write!(formatter, "line {line}: the move must be L, R, or S")
            }
            ParseError::DuplicateRule { line } => {
                write!(
                    formatter,
                    "line {line}: a rule for this state and symbol already exists"
                )
            }
        }
    }
}

impl Error for ParseError {}

impl Machine {
    /// Parses lines of the form `state read -> write move next`, where `move`
    /// is `L`, `R`, or `S` (stay). Text after `#` is a comment.
    fn parse(source: &str) -> Result<Self, ParseError> {
        let mut machine = Machine {
            state_names: Vec::new(),
            rules: HashMap::new(),
        };

        for (index, raw_line) in source.lines().enumerate() {
            let line = index + 1;
            let text = raw_line.split('#').next().unwrap_or_default().trim();
            if text.is_empty() {
                continue;
            }

            let fields: Vec<&str> = text.split_whitespace().collect();
            let [state, read, arrow, write, movement, next] = fields.as_slice() else {
                return Err(ParseError::WrongFieldCount { line });
            };
            if *arrow != "->" {
                return Err(ParseError::WrongFieldCount { line });
            }

            let read = single_symbol(read).ok_or(ParseError::BadSymbol { line })?;
            let write = single_symbol(write).ok_or(ParseError::BadSymbol { line })?;
            let movement = match *movement {
                "L" => Move::Left,
                "R" => Move::Right,
                "S" => Move::Stay,
                _ => return Err(ParseError::BadMove { line }),
            };

            let state = machine.state_id(state);
            let next = machine.state_id(next);
            let rule = Rule {
                write,
                movement,
                next,
            };
            if machine.rules.insert((state, read), rule).is_some() {
                return Err(ParseError::DuplicateRule { line });
            }
        }

        Ok(machine)
    }

    fn state_id(&mut self, name: &str) -> usize {
        if let Some(id) = self.find_state(name) {
            return id;
        }
        self.state_names.push(name.to_owned());
        self.state_names.len() - 1
    }

    fn find_state(&self, name: &str) -> Option<usize> {
        self.state_names.iter().position(|known| known == name)
    }

    fn name(&self, state: usize) -> &str {
        &self.state_names[state]
    }
}

fn single_symbol(text: &str) -> Option<char> {
    let mut symbols = text.chars();
    let symbol = symbols.next()?;
    symbols.next().is_none().then_some(symbol)
}

/// An unbounded tape. Only non-blank cells are stored, so the tape can grow
/// in either direction without shifting anything.
#[derive(Debug, Default)]
struct Tape {
    cells: BTreeMap<i64, char>,
}

impl Tape {
    fn with_contents(text: &str) -> Self {
        let mut tape = Tape::default();
        for (position, symbol) in (0_i64..).zip(text.chars()) {
            tape.write(position, symbol);
        }
        tape
    }

    fn read(&self, position: i64) -> char {
        self.cells.get(&position).copied().unwrap_or(BLANK)
    }

    fn write(&mut self, position: i64, symbol: char) {
        if symbol == BLANK {
            self.cells.remove(&position);
        } else {
            self.cells.insert(position, symbol);
        }
    }

    /// The stretch of tape from the first to the last non-blank cell.
    fn contents(&self) -> String {
        let (Some((&first, _)), Some((&last, _))) =
            (self.cells.first_key_value(), self.cells.last_key_value())
        else {
            return String::new();
        };
        (first..=last).map(|position| self.read(position)).collect()
    }
}

#[derive(Debug, PartialEq, Eq)]
enum Outcome {
    Halted { state: usize, steps: u64 },
    OutOfBudget { steps: u64 },
}

/// Runs until no rule matches (the machine halts) or the budget is spent.
///
/// The budget is not optional. No simulator can know in advance whether an
/// arbitrary machine will ever halt, so all it can decide is how long it is
/// willing to wait.
fn run(machine: &Machine, tape: &mut Tape, head: i64, state: usize, budget: u64) -> Outcome {
    let mut head = head;
    let mut state = state;
    let mut steps = 0;
    loop {
        let Some(rule) = machine.rules.get(&(state, tape.read(head))) else {
            return Outcome::Halted { state, steps };
        };
        if steps == budget {
            return Outcome::OutOfBudget { steps };
        }
        tape.write(head, rule.write);
        head += rule.movement.delta();
        state = rule.next;
        steps += 1;
    }
}

fn describe(machine: &Machine, outcome: &Outcome) -> String {
    match outcome {
        Outcome::Halted { state, steps } => {
            format!("halted in `{}` after {steps} steps", machine.name(*state))
        }
        Outcome::OutOfBudget { steps } => format!("still running after {steps} steps, gave up"),
    }
}

fn main() -> Result<(), Box<dyn Error>> {
    println!("1. A three-rule program that adds one to a binary number");
    let incrementer = Machine::parse(INCREMENTER)?;
    let carry = incrementer
        .find_state("carry")
        .ok_or("the incrementer has no `carry` state")?;

    for number in ["1011", "111", "0"] {
        let mut tape = Tape::with_contents(number);
        let rightmost = i64::try_from(number.len())? - 1;
        let outcome = run(&incrementer, &mut tape, rightmost, carry, 100);
        let result = tape.contents();
        let before = u64::from_str_radix(number, 2)?;
        let after = u64::from_str_radix(&result, 2)?;
        println!(
            "  {number:>4} ({before:>2}) -> {result:>4} ({after:>2})   {}",
            describe(&incrementer, &outcome)
        );
    }

    println!("\n2. A machine that never halts, stopped by a budget");
    let filler = Machine::parse(FILLER)?;
    let fill = filler
        .find_state("fill")
        .ok_or("the filler has no `fill` state")?;
    let mut tape = Tape::default();
    let outcome = run(&filler, &mut tape, 0, fill, 1_000);
    println!(
        "  {}; the tape now holds {} symbols",
        describe(&filler, &outcome),
        tape.contents().len()
    );

    println!("\n3. The program is data: a malformed table is rejected, not run");
    match Machine::parse("carry 1 -> 0 X carry") {
        Ok(_) => println!("  unexpectedly accepted"),
        Err(error) => println!("  rejected: {error}"),
    }

    Ok(())
}

#[cfg(test)]
mod tests {
    use super::*;

    fn increment(number: &str, budget: u64) -> (String, Outcome) {
        let machine = Machine::parse(INCREMENTER).unwrap();
        let carry = machine.find_state("carry").unwrap();
        let mut tape = Tape::with_contents(number);
        let rightmost = i64::try_from(number.len()).unwrap() - 1;
        let outcome = run(&machine, &mut tape, rightmost, carry, budget);
        (tape.contents(), outcome)
    }

    #[test]
    fn incrementer_adds_one_to_every_small_number() {
        for value in 0_u64..=64 {
            let (result, outcome) = increment(&format!("{value:b}"), 100);
            assert!(
                matches!(outcome, Outcome::Halted { .. }),
                "{value}: {outcome:?}"
            );
            assert_eq!(u64::from_str_radix(&result, 2).unwrap(), value + 1);
        }
    }

    #[test]
    fn carry_can_run_off_the_left_end() {
        let (result, outcome) = increment("111", 100);
        assert_eq!(result, "1000");
        assert!(matches!(outcome, Outcome::Halted { steps: 4, .. }));
    }

    #[test]
    fn halting_on_the_last_budgeted_step_still_counts_as_halting() {
        let (result, outcome) = increment("1011", 3);
        assert_eq!(result, "1100");
        assert!(matches!(outcome, Outcome::Halted { steps: 3, .. }));
    }

    #[test]
    fn a_machine_that_never_halts_runs_out_of_budget() {
        let machine = Machine::parse(FILLER).unwrap();
        let fill = machine.find_state("fill").unwrap();
        let mut tape = Tape::default();
        assert_eq!(
            run(&machine, &mut tape, 0, fill, 50),
            Outcome::OutOfBudget { steps: 50 }
        );
        assert_eq!(tape.contents(), "1".repeat(50));
    }

    #[test]
    fn malformed_rules_are_rejected_with_their_line() {
        assert_eq!(
            Machine::parse("a 1 0 L b").unwrap_err(),
            ParseError::WrongFieldCount { line: 1 }
        );
        assert_eq!(
            Machine::parse("a 1 -> 0 X b").unwrap_err(),
            ParseError::BadMove { line: 1 }
        );
        assert_eq!(
            Machine::parse("a 10 -> 0 L b").unwrap_err(),
            ParseError::BadSymbol { line: 1 }
        );
        assert_eq!(
            Machine::parse("a 1 -> 0 L b\na 1 -> 1 R b").unwrap_err(),
            ParseError::DuplicateRule { line: 2 }
        );
    }
}

carry 1 -> 0 L carry   # 1 plus a carry is 0, and the carry moves left
carry 0 -> 1 S done    # 0 plus a carry is 1, and the carry is used up
carry _ -> 1 S done    # ran off the left end: write a new leading 1

The heart of the simulator is the step loop. It looks up a matching transition row, gives up if the budget is spent, and otherwise writes, moves, and switches state:

fn run(machine: &Machine, tape: &mut Tape, head: i64, state: usize, budget: u64) -> Outcome {
    let mut head = head;
    let mut state = state;
    let mut steps = 0;
    loop {
        let Some(rule) = machine.rules.get(&(state, tape.read(head))) else {
            return Outcome::Halted { state, steps };
        };
        if steps == budget {
            return Outcome::OutOfBudget { steps };
        }
        tape.write(head, rule.write);
        head += rule.movement.delta();
        state = rule.next;
        steps += 1;
    }
}

The order of the two checks matters. A machine that reaches done on its very last budgeted step has halted, and the loop reports it that way rather than calling it a timeout.

Build it, then run it from the rust-labs folder:

cargo run --bin turing_machine_lab

The lab adds one to three numbers, including 111 so you can watch the carry run off the end. Then it runs a machine with one repeating transition that writes 1s forever and stops it with a budget. Finally, it feeds the simulator a malformed transition table to show that a program which is only data still has to be validated before it runs. The tests beside it check every number from 0 to 64 and the budget edge case.

Optional reference: Rice’s theorem and a second machine

Nothing later in the book depends on this reference. It extends the halting result to other questions and gives a second machine to trace by hand.

Optional reference: Rice's theorem and a second machine

Rice’s theorem: questions about what a program does

The damage does not stay with halting. A later result, Rice’s theorem, extends it to essentially every question about what a program does, as opposed to how its text is written. “Does it ever write to this address?” “Does it ever send a network message?” “Is this instruction ever executed?” For each one, no single method answers correctly for every possible program, so each is undecidable.

A second machine: flip every digit

Another small machine could flip every digit of a binary number, turning 1011 into 0100. It needs only two transition rows, because the machine halts when it reaches a blank with no matching table row. Starting at the leftmost digit, it applies four transitions to flip four digits and then stops when the head reaches the blank.

What the model explains

A Turing machine has a tape, a head, a state, and a transition table. Its three-row incrementer carries left until it can turn a 0 into a 1; if the carry runs off the left end, a new 1 is needed. Computer memory, addresses, registers, and instructions play roles analogous to tape, head position, state, and transitions. Stored programs let a debugger place a breakpoint by replacing an instruction byte. A mod with a script is executable behavior, and no general tool can decide whether every possible program halts. Disassemblers, decompilers, scanners, and step budgets therefore provide bounded observations rather than universal answers.

From Lua Source to a Tiny Virtual Machine now follows a short expression from text into executable operations. Its interpreter uses the same practical limit as the simulator here: execute a bounded number of steps and report what happened, without claiming to decide the behavior of every possible program.

Lesson 11.9

From Lua Source to a Tiny Virtual Machine

The earlier Lua lessons used scripts from the outside and defined what the game host would let them do. The computability lesson then showed how one program can execute another—and why no perfect termination checker can replace a work budget. Now look inside the interpreter. The same small expression has to become operations a virtual machine can execute, and those operations still need limits and useful errors.

An interpreter is a pipeline

When Lua reads total = 5 + 2, it does not ask the CPU to execute the characters + and = directly. Several layers turn text into actions:

1. a lexer groups characters into tokens such as name, equals, integer, plus, integer;
2. a parser checks that the token order follows the language grammar;
3. a compiler turns the meaning into compact bytecode instructions;
4. a virtual machine executes those bytecodes using values, a stack, and an instruction pointer.

Real Lua is carefully optimized. Our tiny VM is intentionally smaller so every moving part fits on one page.

These stages are common, but they are not the definition of every interpreter. One interpreter may walk a syntax tree directly; another may compile to bytecode first; a just-in-time compiler may later translate hot bytecode into native machine code. The language’s meaning can stay the same while its implementation changes.

That gives us an important abstraction boundary:

language rule:  `+` adds two numbers and produces a number
implementation: pop two VM values, check their variants, add, push the result
machine work:    host code becomes native instructions executed by the CPU

Do not explain Lua semantics by accident from one current bytecode layout. The source rule is the contract; tokens, syntax trees, bytecodes, stacks, and native instructions are replaceable representations used to carry it out.

The same pipeline can be viewed from the host’s side. Lua 5.4 typically recognizes names and numbers with a lexer, checks expressions and statements with a parser, compiles them to bytecode, and executes those instructions in its VM. The VM maintains Lua values, call frames, and its own program counter; the host supplies functions that may be called during execution:

Some hosts cache bytecode; others compile source each time it loads. LuaJIT may additionally translate hot paths into native machine code. Identify the runtime before assuming its internal representation matches this teaching VM.

Bytecode names small operations

The lab uses an enum instead of raw bytes:

enum Instruction {
    Constant(usize),
    Add,
    GreaterThan,
    JumpIfFalse(usize),
    Jump(usize),
    Print,
    Halt,
}

Constant(2) means “copy constant number two onto the value stack.” Add pops two integers and pushes their sum. JumpIfFalse(9) changes the VM instruction pointer when the popped condition is false.

An enum makes this teaching VM easy to inspect. A full game-scripting interpreter may encode opcodes and operands more densely after profiling shows that bytecode size or dispatch speed matters.

That 9 is not decoration. Jump operands are positions in the bytecode vector, so they only mean anything once you can see the whole program. Here is the lab’s example, if (5 + 2) > 6 then print(1) else print(0), after compilation. The constants are collected into a pool, and the instructions refer to them by index:

05

12

26

31

40

The constant pool for if (5 + 2) > 6 then print(1) else print(0). Instructions refer to these by index, never by value directly.

constant pool:  0:5   1:2   2:6   3:1   4:0

  0  Constant(0)        push 5
  1  Constant(1)        push 2
  2  Add                pop two, push 7
  3  Constant(2)        push 6
  4  GreaterThan        pop two, push true
  5  JumpIfFalse(9)     condition false -> continue at 9
  6  Constant(3)        push 1          <- then branch
  7  Print
  8  Jump(11)           skip the else branch
  9  Constant(4)        push 0          <- else branch
 10  Print
 11  Halt

Now the operands read as addresses within this listing. JumpIfFalse(9) sends a false condition to index 9, which is exactly where the else branch begins. Jump(11) carries the then branch past the else branch to the Halt. The if/else structure you wrote in Lua has become two jumps and a layout — the compiler kept the meaning and threw away the shape.

A stack machine adds 5 and 2Constants push values; Add pops two and pushes their sum. The stack is the working memory.

1. 1 Index 0, Constant(0): push 5

   Stack: older value, then top

   5top

   The stack starts empty; the constant 5 goes on it.

2. 2 Index 1, Constant(1): push 2

   Stack: older value, then top

   5

   2top

   2 goes on top of 5.

3. 3 Index 2, Add: pop both, push 7

   Stack: older value, then top

   7top · popped 2 and 5

   Add takes 2 and 5 off the stack and pushes 5 + 2 = 7.

Constants push values; Add pops two and pushes their sum. The stack is the working memory.

The VM has its own instruction pointer

The CPU has an instruction pointer such as RIP. The VM also needs one, but it points into the bytecode vector:

let instruction = *self.code
    .get(self.instruction_pointer)
    .ok_or_else(|| VmError("instruction pointer left the program".into()))?;
self.instruction_pointer += 1; // 🧭 Default to the next bytecode.

A jump replaces that default next location. Bounds checks prevent corrupt bytecode from jumping outside the program.

Model the VM as state plus one transition function

At any instant, this tiny machine is completely described by a small state:

instruction pointer
bytecode vector
constant pool
value stack
remaining step budget
output produced so far

One interpreter-loop iteration reads the current instruction and changes that state. Constant advances the pointer and grows the stack. Add removes two values and adds one. Jump changes the pointer. Print moves a value to observable output. Halt ends the transition loop.

This state-machine view is more reliable than imagining that the VM “somehow runs Lua.” It lets you state an invariant for every instruction: required stack inputs, resulting stack height, legal jump targets, possible error, and instruction-pointer change.

The value stack carries temporary results

TL;DR: The pool stores fixed constants. The stack stores temporary values. Adding two values removes both and leaves one result.

Indices 0 to 4 of that listing compute (5 + 2) > 6. Watching the stack through those five steps shows where the intermediate values live:

Step	Bytecode	Stack after step
1	constant 5	5
2	constant 2	5, 2
3	add	7
4	constant 6	7, 6
5	greater-than	true

top →2

5

The value stack right after step 2 (Constant(1) pushed 2 on top of the 5 pushed in step 1).

Add pops the right side first because it was pushed last. This last-in, first-out order is the same basic idea as a call stack, although a real VM may use separate regions or registers for different jobs.

A stack operation consumes its operands. This step-by-step trace needs JavaScript. Here is the code and where the run ends.

push a; push b
Add pops right and left, then pushes their sum
push threshold
GreaterThan pops threshold and sum
JumpIfFalse pops the comparison
print 1 on true, otherwise 0; halt

Result: print 1, then halt. Each instruction has a specific stack effect.

Final values: a = 5; b = 2; threshold = 6; stack = []; sum = 7; condition = true; printed = 1.

Read every step of the lesson’s example

1. Step 1, line 1. Start with the selected inputs and follow how the next operation changes the state.

   a = 5; b = 2; threshold = 6.

2. Step 2, line 1. The constant pushes fill the value stack.

   a = 5; b = 2; threshold = 6; stack = [5, 2].

3. Step 3, line 2. Add replaces two operands with one result.

   a = 5; b = 2; threshold = 6; stack = [7]; sum = 7.

4. Step 4, line 3. Push the right-hand comparison operand.

   a = 5; b = 2; threshold = 6; stack = [7, 6]; sum = 7.

5. Step 5, line 4. GreaterThan replaces both numbers with one boolean.

   a = 5; b = 2; threshold = 6; stack = [true]; sum = 7; condition = true.

6. Step 6, line 5. The jump consumes the boolean; the stack is empty again.

   a = 5; b = 2; threshold = 6; stack = []; sum = 7; condition = true.

7. Step 7, line 6. Result: print 1, then halt. Each instruction has a specific stack effect.

   a = 5; b = 2; threshold = 6; stack = []; sum = 7; condition = true; printed = 1.

Watch it happenA value stack evaluating (5 + 2) > 6

A bytecode listing with an instruction pointer, a constant pool of 5, 2, 6, 1 and 0, and a value stack. Constants are pushed from the pool; Add pops 2 and 5 and pushes 7; 6 is pushed; GreaterThan pops 6 and 7 and pushes true; JumpIfFalse pops true and falls through to the then branch, which prints 1 and halts.

Read the steps

1. The VM starts at bytecode 0 with an empty value stack. The constants live in the pool; instructions name them by index.
2. Constant(0): copy pool entry 0, the number 5, onto the stack. The instruction pointer moves to 1.
3. Constant(1): push pool entry 1, the number 2, on top of the 5. Now 2 is the value a pop would remove first.
4. Add: pop the right operand, 2, then the left operand, 5. Both are integers, so push their sum, 7. Two temporary values became one.
5. Constant(2): push pool entry 2, the number 6, above the 7.
6. GreaterThan: pop 6, pop 7, and push the answer to 7 > 6. The stack now holds a condition, not numbers.
7. JumpIfFalse(9) pops true. The condition is not false, so the jump is not taken and execution continues at 6, the then branch.
8. Constant(3) pushes the number 1, Print pops it into the output, and Jump(11) skips the else branch to Halt.

The constant pool and the value stack have different jobs: the pool holds the program’s fixed values, and the stack holds the results in progress.

Keep dynamic types explicit

Alternative: A register-based VM names temporary slots directly. This stack VM instead makes each instruction use the values at the top.

Lua values can have several types. Our tiny subset has two:

enum Value {
    Integer(i64),
    Boolean(bool),
}

pop_integer checks the variant. Adding a Boolean produces a useful VM error rather than reinterpreting its bytes as a number. Dynamic typing means the check happens at run time; it does not mean “types do not exist.”

A larger Lua VM also needs an environment that maps names to values. Functions capture environments through closures, tables hold references to other values, and garbage collection decides when unreachable heap objects can be reclaimed. Those features enlarge the state, but they do not change the basic model: each operation checks its inputs and moves the machine from one valid state to the next.

Separate four kinds of failure

Keeping stages separate produces clearer errors:

Stage	Example failure
Lexing	unfinished quoted string
Parsing	if without the required structure
Bytecode validation	jump target outside the program
Execution	adding a Boolean to an integer or exhausting the budget

If all four become “script failed,” the host cannot tell whether the author wrote invalid Lua, the compiler produced invalid code, or a valid script exceeded the game tool’s resource policy.

Budgets belong inside the execution loop

Every instruction consumes one step:

if self.steps_left == 0 {
    return Err(VmError("instruction budget exhausted".into()));
}
self.steps_left -= 1;

The test program Jump(0) would loop forever without this guard. This miniature rule connects directly to the instruction hook used by the mlua host earlier in the chapter.

Run the original lab

Any computer

The executable’s sample expression takes 5 + 2, compares it with 6, and prints 1 for true. The test command then checks two failure paths: a jump outside the program and a loop that exhausts its instruction budget.

cargo run --manifest-path lua-labs/Cargo.toml --bin mini_vm
cargo test --manifest-path lua-labs/Cargo.toml --bin mini_vm

For a much larger interpreter-building journey, Build a Lua Interpreter in Rust develops tokens, bytecode, values, tables, control flow, functions, and closures over many stages. This book’s VM and wording are original and deliberately smaller; the linked book is useful further reading when you want to build a language implementation rather than embed an existing Lua runtime.

Lesson 11.10

Values, Tables, Strings, and Garbage Collection

Dynamic values still need a representation

The host often knows a value’s type at compile time. Lua decides many operations at run time. An interpreter therefore carries a tag with each value:

Optional: practise the named operations and their inputs with a few whole-token blanks.

enum Value {
    Nil,
    Boolean(bool),
    Integer(i64),
    Float(f64),
    String(StringId),
    Table(TableId),
    Function(FunctionId),
}

The IDs here are handles into VM-owned storage. That keeps interpreter objects under one memory manager instead of handing scripts raw native pointers.

Three stack slots show the idea. Each value carries its tag beside its payload, and an operation reads the tags before it touches any payload:

tagInteger

payload42

tagTable

payloadid 3

tagNil

payloadunused

Value::Integer(42)

Value::Table(TableId(3))

Value::Nil

+ checks both tags first. Two Integer tags let it add the payloads; an Integer beside a Table fails the check, and this VM raises a type error instead of adding a number to a handle (real Lua first looks for an __add metamethod). The Table payload is not a pointer: id 3 is looked up in storage the VM owns.

A Lua table combines array-like and map-like storage

Lua uses tables for sequences, records, dictionaries, objects, and module namespaces. An implementation can optimize common integer keys with an array part while keeping other keys in a hash-map part:

local palette = { "red", "green", "blue", name = "palette", selected = 2 }

1red

2green

3blue

namepalette

selected2

array part: keys 1 to 3, found by position

hash part: found by hashing the key

One table, two conceptual storage areas in Lua 5.4. The three dense integer keys fit the array-like part; named keys use the hash-like part. Exact allocated capacities are implementation details. palette[2] can use an array position; palette.name hashes the name to begin its lookup.

This is an implementation strategy, not two separate Lua values. The language still presents one table. It also explains why pairs promises no meaningful order: it walks the array part first and then the hash nodes in node order, and node order follows the keys’ hash values rather than the order they were written.

When the host converts a Vec to Lua, it writes keys 1, 2, and 3. When it converts a record, it writes named keys such as health and position. The script can use both forms, but the host should document which shape it promises.

Strings need ownership too

Repeated source names and table keys can create many duplicate strings. An interpreter may intern strings: store one canonical copy and let values carry a small ID or shared reference.

Alternative: Interning is a shared dictionary: repeated strings use the same entry ID instead of each keeping another identical copy.

Checking whether two interned strings are equal is then one integer comparison, 0 == 0, however long the text is. Interning makes equality fast, but it adds lifetime work. The interpreter must know when no live value, table key, closure, or compiled function still needs the string.

Reference counting handles sharing, not every cycle

Rc<T> counts strong owners. It frees the value when the count reaches zero. That works for many interpreter objects, but tables can form cycles:

local a = {}
local b = {}
a.friend = b
b.friend = a

If each table strongly owns the other, both counts stay above zero even after the script drops a and b. Follow the arithmetic:

after a = {} and b = {}      table A: 1 (a)             table B: 1 (b)
after a.friend = b           table A: 1                 table B: 2 (b, A.friend)
after b.friend = a           table A: 2 (a, B.friend)   table B: 2
a and b leave scope          table A: 1 (B.friend)      table B: 1 (A.friend)

Both counts settle at one, each held up solely by the other. Nothing in the running program can reach either table any more, yet neither will ever be freed. That is the shape of every reference-counting leak: the objects have become unreachable without becoming unreferenced, and counting alone cannot tell those two conditions apart.

A tracing garbage collector can start from roots—globals, active stacks, and live closures—mark reachable objects, then reclaim unmarked cycles.

Do not assume Rc by itself is a complete Lua garbage collector. A small non-cyclic interpreter can use it while learning, but a general implementation needs a cycle strategy.

Roots answer “what is still reachable?”

Typical roots include:

• the global environment;
• each active function frame;
• values on VM stacks or registers;
• open upvalues captured by closures;
• host references intentionally kept alive.

A tracing collector reclaims an unreachable cycleTable P is held by a global and holds the string s and the closure f. Tables A and B hold only each other. Every reference count is 1.

1. 1 Mark: follow references from the roots

   Heap objects

   Pmarked

   smarked

   fmarked

   Anot reached

   Bnot reached

   From the global the collector reaches P, then s and f. Nothing reachable leads to A or B.

2. 2 Sweep: free every unmarked object

   Heap objects

   Pkept

   skept

   fkept

   Afreed

   Bfreed

   A and B are reclaimed together, although each still had a count of 1.

Table P is held by a global and holds the string s and the closure f. Tables A and B hold only each other. Every reference count is 1.

The cycle keeps both reference counts above zero, but no root reaches either table. A tracing collector can tell the difference because it asks about reachability, not just owner counts.

TL;DR: A tracing collector asks whether roots can reach an object; positive reference counts alone cannot show that a cycle is still useful.

A host API that retains a Lua table may accidentally keep a large graph alive. Resource limits should measure actual interpreter memory, not merely the size of the source file.

Narration: Holding one Lua table in the host can keep everything reachable from it alive. Small source files can still retain large object graphs.

A cycle can keep counts positive without a root. This step-by-step trace needs JavaScript. Here is the code and where the run ends.

root -> A; A -> B; B -> A
count strong references to each table
optionally remove the external root
count references again
trace reachable objects starting from roots
compare reachability with reference counts

Result: both counts are 1, yet neither table is reachable. A tracing collector can reclaim this unreachable cycle.

Final values: root = removed; refs_A = 1; refs_B = 1; reachable_A = false; reachable_B = false; external_roots = 0; reclaimable_by_tracing = true.

Read every step of the lesson’s example

1. Step 1, line 1. Start with the selected inputs. Follow the highlighted operation and the changing state below.

   root = removed.

2. Step 2, line 2. A has a root reference plus B’s reference; B has A’s reference.

   root = removed; refs_A = 2; refs_B = 1; reachable_A = true; reachable_B = true.

3. Step 3, line 3. Remove only the external reference; the cycle remains.

   root = removed; refs_A = 2; refs_B = 1; reachable_A = true; reachable_B = true; external_roots = 0.

4. Step 4, line 4. Neither cycle edge disappears when the root is removed.

   root = removed; refs_A = 1; refs_B = 1; reachable_A = true; reachable_B = true; external_roots = 0.

5. Step 5, line 5. No root reaches either table.

   root = removed; refs_A = 1; refs_B = 1; reachable_A = false; reachable_B = false; external_roots = 0.

6. Step 6, line 6. Result: both counts are 1, yet neither table is reachable. A tracing collector can reclaim this unreachable cycle.

   root = removed; refs_A = 1; refs_B = 1; reachable_A = false; reachable_B = false; external_roots = 0; reclaimable_by_tracing = true.

Tables are capability containers

In our embedded host, the game table contains only selected callbacks. This is more than neat organization:

game.snapshot()
game.distance(a, b)
game.log("ready")

If game.open_process, game.read_any_address, or os.execute never enters the environment, ordinary scripts cannot call it. Table construction becomes part of the security boundary.

Questions to ask while reversing an embedded VM

In a debug build, look for:

• a tagged-value dispatch that checks type before an operation;
• one central table lookup routine;
• a VM instruction pointer separate from the CPU instruction pointer;
• arrays of constants or bytecodes owned by compiled functions;
• root enumeration during garbage collection;
• native host callbacks registered under readable names.

Use these structures to explain tagged values, object reachability, table lookup, and callback dispatch in the scripting system.

Further reading

The Lua 5.4 reference manual is the source of truth for language behavior. Build a Lua Interpreter in Rust provides an extended implementation path through strings, tables, expressions, control structures, functions, and closures. Use both to understand the model, then write and test your own representation for the subset you intend to support.

Lesson 11.11

Call Frames, Closures, and Upvalues

A VM call needs bookkeeping

When one Lua function calls another, the interpreter must remember where the caller continues, where its local values live, which function is running, and where results should go. That record is a call frame.

This is the virtual machine’s version of the call-stack idea from the assembly chapter. The CPU still has a real native stack underneath, but Lua call frames describe Lua execution.

One value stack can hold many frames

A VM can keep values in one vector and let each frame own a range:

struct CallFrame {
    function: FunctionId,
    base: usize,
    return_instruction: usize,
    expected_results: ResultCount,
}

enum ResultCount {
    Exact(usize),
    All,
}

Two call frames share one value stackThe caller keeps a = 10 and b = 3 at base 0, then calls a function that returns x − y.

1. 1 Call: the new frame starts at base 2

   Value stack

   caller: base 0callee: base 2

   10slot 0 · a

   3slot 1 · b

   10slot 2 · x

   3slot 3 · y

   The arguments are copied to slots 2 and 3, so the callee’s local 1 is slot 2 + 1 = 3. The frame records: resume the caller at instruction 5, one result wanted.

2. 2 Return: the result lands in slot 2

   Value stack

   caller: base 0

   10slot 0 · a

   3slot 1 · b

   7slot 2 · result

   freeslot 3

   The callee computes 10 − 3 = 7. The VM stores it in slot 2, removes the callee’s frame and continues the caller at instruction 5.

The caller keeps a = 10 and b = 3 at base 0, then calls a function that returns x − y.

base says where this function’s local area begins. Bytecode operands can refer to base + local_index rather than carrying raw pointers into the vector.

Alternative: A frame’s base is its starting shelf position: local index zero means that frame’s first slot, not the first slot of the entire VM stack.

Lua allows multiple return values, so a caller may request an exact number or accept all produced results. Missing results become nil; unwanted extras can be discarded.

A closure is code plus captured surroundings

Consider:

local function make_counter()
    local count = 0
    return function()
        count = count + 1
        return count
    end
end

The returned function keeps using count after make_counter has returned. count is an upvalue: a captured variable from an enclosing scope.

While the outer frame is active, an upvalue may refer to its live stack slot. Before that frame disappears, the interpreter must move or “close” the value into storage owned by the closure. Otherwise the closure would keep an invalid stack location.

Open and closed upvalues

An implementation can model the two states explicitly:

enum UpvalueLocation {
    Open { stack_index: usize },
    Closed(Value),
}

Several closures may capture the same local, so they must share one upvalue cell. If each closure copies the number independently, updates will disagree and the Lua behavior will be wrong.

TL;DR: Closures that capture the same local need one shared upvalue cell, so changes remain visible through every captured reference.

Follow make_counter through with slot numbers and it stops being abstract. Say its frame gets base = 3, so its single local count lives in stack slot 3:

call make_counter()
  stack slot 3 = 0            <- count, inside the live frame
  inner function created
  upvalue = Open { stack_index: 3 }

make_counter returns
  slot 3 is about to belong to whatever runs next,
  so the interpreter closes the upvalue first:
  upvalue = Closed(0)         <- the 0 now lives in a cell the closure owns

counter()   reads the cell -> 0, writes 1, returns 1
counter()   reads the cell -> 1, writes 2, returns 2

“Open” and “closed” are just those two rows: while the frame lives the upvalue is a slot number, and afterwards it is a value in a cell. The identity never changes — it is the same count throughout — only where it is stored.

That distinction predicts a specific bug. Hand the same count to two closures, then close it by copying the value into each one rather than sharing one cell. Call the first closure twice and the second once, and you get 1, 2, and then 1 again, because the second closure incremented its own private copy. Sharing the cell is what makes the third call return 3, which is the behaviour Lua actually promises.

The captured value changes location without changing its identity:

Both closures keep referring to one shared cell after the original stack frame is gone.

This is a useful ownership lesson: the local starts inside one frame, escapes, becomes shared state, and outlives its original scope.

Two closures must share one captured counter. This step-by-step trace needs JavaScript. Here is the code and where the run ends.

count = 0
make closures A and B capture count
A increments its captured value
A returns that value
B increments its captured value
B returns; compare captured storage

Result: A returned 1; B returned 2. Both closures refer to the same final cell.

Final values: storage = shared; cell_A = 2; cell_B = 2; returned_A = 1; returned_B = 2.

Read every step of the lesson’s example

1. Step 1, line 1. Start with the selected inputs. Follow the highlighted operation and the changing state below.

   storage = shared.

2. Step 2, line 2. Both closures initially observe zero.

   storage = shared; cell_A = 0; cell_B = 0.

3. Step 3, line 3. Closure A increments its cell.

   storage = shared; cell_A = 1; cell_B = 1.

4. Step 4, line 4. Closure A returns 1.

   storage = shared; cell_A = 1; cell_B = 1; returned_A = 1.

5. Step 5, line 5. Closure B sees the already updated shared 1 and increments it to 2.

   storage = shared; cell_A = 2; cell_B = 2; returned_A = 1.

6. Step 6, line 6. Result: A returned 1; B returned 2. Both closures refer to the same final cell.

   storage = shared; cell_A = 2; cell_B = 2; returned_A = 1; returned_B = 2.

Host callbacks look like VM functions at the boundary

When mlua registers game.log, it builds a callable Lua value backed by a host closure. The boundary must:

1. check the Lua argument count and types;
2. convert them to host values;
3. call the host function;
4. convert success values back to Lua;
5. turn host errors into Lua errors with context;
6. avoid letting a panic cross the language boundary.

The callback should be short and bounded. A Lua instruction budget cannot interrupt arbitrary blocking work performed inside native host code.

Narration: Counting Lua instructions does not bound a native callback stuck waiting for disk or a lock. Host callbacks need their own bounded behavior.

The Lua C API makes this boundary concrete with an indexed value stack. A native callback reads arguments from stack slots, validates them, pushes return values, and reports how many it returned. mlua wraps much of that protocol, but stack balance and error conversion still exist underneath:

before call: [function][argument 1][argument 2]
native code: validate arguments, perform bounded work
after call:  [return value 1]

Treat a host callback like a small parser. Specify accepted types and ranges, reject invalid input before side effects, and return an error in the form the runtime expects. A panic or native exception must not cross a C ABI boundary uncontrolled.

Re-entrancy adds nested host and VM call frames

A host callback may call Lua again, which may call another host function. This is re-entrancy. The host needs a clear policy for locks and mutable game state.

Avoid holding a mutable engine lock while executing unknown script code. Give Lua a copied snapshot, collect typed requests, return to the host, and then validate and apply them. That architecture from earlier lessons also prevents complicated nested borrows.

Debug a function call in layers

When a script call behaves incorrectly, record:

• bytecode instruction and VM instruction pointer;
• active function and call-frame base;
• argument slots and their value tags;
• requested result count;
• open upvalues and the stack slots they reference;
• host callback name and converted arguments;
• final Lua error chain.

Do not print secrets or entire game snapshots by default. A debugger can be useful without becoming a data leak.

Build understanding in stages

The original mini_vm lab intentionally stops before functions. Extend a copy in this order:

1. add named local slots;
2. add Call and Return instructions;
3. introduce a CallFrame stack;
4. support an exact result count;
5. add function constants;
6. capture one read-only upvalue;
7. close it when the outer frame returns;
8. share one mutable upvalue between two closures;
9. add recursion and enforce a maximum frame depth.

Each stage should have a failing test before it gets more features. A small verified interpreter teaches more than a large VM whose stack layout and call/return behavior are guesses.

The detailed implementation path in Build a Lua Interpreter in Rust is useful further reading for functions and closure escape. Keep your own code original, compare observable behavior with the official Lua manual, and treat the reference implementation as a guide to questions—not a source to paste from.

The VM explains how a script keeps state and reaches a host callback. It does not decide whether that callback’s requested game action is valid. A copied snapshot can grow stale while Lua runs; another script or input path may reach the same effect. Chapter 11 returns to the Windows process that hosts both the game and its scripts, identifying its build, modules, memory regions, and thread state before later chapters inspect deeper trust boundaries.