The Budget System: Thalers, Bytes, and Milliseconds

A Neander program is guaranteed to stop, as we saw last time. But "stops eventually" is not good enough in a real-world scenario, where the program runs inside the host application and consumes its resources while it does.

So on top of a sub-Turing language, Neander features a budget system which places hard upper bounds on a program in six different dimensions. Three of them are budgets in the literal sense: they bound what a running program is allowed to consume. The other three are static caps on the shape of the program itself, checked before it is allowed to run at all. All six are set and enforced by the runtime, never declared, requested or negotiated by an agent or a program. The agent can obtain the current budget limits from the runtime by submitting the empty program (what it would do anyway during a cold start). The meta block of the Reference Response contains the runtime's budget configuration.

It is worth stressing that the budget system is an integral part of the language definition, not merely a bolted-on feature of one particular runtime implementation.

What is runtime-specific are the details of how and in what amount these upper bounds are assigned to a submitted program. The Grotto reference implementation, for example, currently requires a static budget configuration at startup time and applies it to every program submission.

What is normative, however, is the consequence of exceeding one. Either way the program produces a Failure result, but the two kinds of bound fail differently. Overrunning a static cap is a Flaw: the program is rejected outright, before execution. Overspending a budget is an Abort: execution stops immediately. There is exactly one exception to this rule, and we will get to it in a minute.

Computation

Computation is measured in Thalers, Neander's unit of computational work, named after an old silver coin. Every operation that actually computes something costs one Thaler. Things that do not compute are free, e.g. binding a name, returning a value, a literal. The Neander specification contains a complete Thaler Cost Table:

Operation	Cost
Arithmetic op (+, -, *, /, %)	1 Thaler
Comparison (==, !=, >, <, >=, <=)	1 Thaler per base-type comparison
Logical op (and, or, not)	1 Thaler
is type check	1 Thaler
?? null coalescing	1 Thaler
Field access (.field)	1 Thaler
List index ([i])	1 Thaler
Map access (["key"])	1 Thaler
List projection ([*].field)	1 Thaler per element
contains() / indexOf() on list	1 Thaler per element checked
replace() / split() on string	1 Thaler per occurrence found
Other built-in function call	1 Thaler
call (API function)	1 Thaler
each iteration	1 Thaler per iteration (body costs are additional)
repeat iteration	1 Thaler per iteration (body costs are additional)
discover	1 Thaler
if evaluation	0 (the condition's operations already cost Thalers)
let binding	0 (the expression's operations already cost Thalers)
return / throw / yield / skip	0 (the expression's operations already cost Thalers)
Literal value	0
Spread (..) in list or map literal	1 Thaler per element or entry spread

Memory

Memory is measured in whole kilobytes, and the memory budget is a ceiling on peak allocation. API return values, large lists and maps, deep record structures: all of it is charged, and an allocation that would cross the ceiling is refused before it happens.

In contrast to computation costs, which are standardized by the language, memory costs are heavily implementation-dependent. The Neander design gives each runtime implementation the breathing space it needs to account for the memory allocation specifics of its underlying platform. What is standardized is the contract around the number: that the ceiling binds peak allocation, that crossing it stops the program before the allocation happens, and that the figures reported back are whole kilobytes. Thalers are portable across conforming runtimes. Kilobytes are not.

Time

Time is measured in wall-clock milliseconds, and there exist two separate duration budgets. The first limits the overall program execution duration, including in particular all API calls. The second limits the duration of each API call individually, so one slow API cannot quietly eat the whole duration budget on its own.

The per-call timeout is the exception promised above. Exceeding it does not stop the program. Instead, it returns a recoverable runtime error from the API call, and execution continues. The reasoning is that the program's other budgets may well still be within limits. So the runtime hands it back as an ordinary failed call and lets the program decide.

Size

Size is measured in bytes and limits the length of the submitted program as UTF-8-encoded source. The standard mandates that this limit is checked before any source code pre-processing (lexing, parsing, etc.) starts. That pre-processing costs the runtime real work, but it is not covered by the budgets for computation, memory, and time. These budgets only apply to program execution. The size cap is what bounds everything that happens before.

Depth

Depth is a unitless positive integer and limits the longest root-to-leaf path in the program's abstract syntax tree. It protects against stack overflows during parsing, type checking, and execution, which is a separate attack vector independent of program size: a short program can nest very deeply.

Repeat

Repeat is a unitless positive integer and caps the limit literal that every repeat loop must declare. There are two separate limits at play here, and it is important to distinguish between them. The first is part of the repeat syntax itself and acts as a runtime precondition on the actual repeat count:

repeat pageCount limit 20 as i {
  call orders.list(offset: i * 100, limit: 100)
}

If pageCount turned out to be larger than 20 during execution, then a runtime error would prevent the loop from even starting. This construct gives an agent the opportunity to express an expectation and ensure that the loop does not execute if the expectation is not met.

The budget-system repeat limit, on the other hand, is an absolute ceiling on the literal itself, checked at validation time. So limit 1000000000 is valid syntax and per se allowed, but it very likely exceeds the configured cap, and the program would never start running. This prevents an agent from circumventing the bound on loops by declaring an absurdly high number as the limit.

Grotto's take on budgets

Grotto implements a dispatcher-worker pattern where program submission is handled by a dispatcher running in the host thread and the program itself is handled by an isolated worker.

The dispatcher enforces the program size cap upon reception and the overall program execution duration cap by a timeout on the isolated worker followed by worker termination.

The worker does the rest. Parser and validator enforce depth and repeat limits, computation and memory budgets are checked cooperatively at every operation and allocation, and a timeout guards every in-thread API call.

Note the split. Thalers and memory can be counted cooperatively because the interpreter is doing the work and can be trusted to check as it goes. Duration cannot be left to the same mechanism: a program that stops coming back to a checkpoint stops checking its own clock. Grotto does sample the clock inside the worker too, but it does not rely on it. The deadline that actually binds sits on the dispatcher thread, which is a question of isolation rather than budgeting.

Next from the Grotto

That concludes the overview of the Neander budget system, and it ends with a brief visit to Grotto. Since we are here anyway, it makes sense to stay a while and take a closer look under the hood, to better understand how Grotto keeps its embedding host application isolated from the execution of untrusted code.

In the meantime, read the Neander spec, embed Grotto in your own app, and let me know what it cost you.