I'm publishing this series ahead of Code BEAM Europe this October, where I'll reveal Bondy, a new declarative language for the BEAM: statically typed, functional, relational and rule-based.

A token bucket rate limiter, as a gen_server. You have written this one, or its cousin:

handle_call({request, Id}, _From, #{buckets := Bs} = State0) ->
    case maps:find(Id, Bs) of
        {ok, #{tokens := T} = B0} when T > 0 ->
            B = B0#{tokens := T - 1},
            State = State0#{buckets := Bs#{Id := B}},
            Reply = {allowed, T - 1},
            {reply, Reply, State};

        {ok, #{tokens := 0}} ->
            {reply, denied, State0};

        error ->
            {reply, {error, no_bucket}, State0}
    end;

handle_call({refill, Id, Amount}, _From, #{buckets := Bs} = State0) ->
    case maps:find(Id, Bs) of
        {ok, #{tokens := T, max := M} = B0} ->
            T1 = min(T + Amount, M),
            B = B0#{tokens := T1},
            Reply = {refilled, T1},
            State = State0#{buckets := Bs#{Id := B}},
            {reply, Reply, State};

        error ->
            {reply, {error, no_bucket}, State0}
    end.

It is short, idiomatic, and it works, but where is the rule? "A request against a bucket that has tokens uses one up and is allowed" is one sentence. In the code it is spread across the message shape, the map lookup, the guard, the bucket update, the state update and the reply tuple. Add a second rule, "premium buckets are never denied", and count the clauses you have to touch. The logic is scattered because the language has no place for a sentence of the form when these things are together, do this to them. It only has functions, so the sentence dissolves into control flow.

A store, and rules over it

The second post said a rule runs when the world makes it true. Here is what that means in practice. The same limiter, in Bondy:

constraint Bucket  = {id: String, tokens: Int, max_tokens: Int}
constraint Request = {id: String}

event Allowed = {id: String, remaining: Int}
event Denied  = {id: String}

rule consume_token =
    on
        Request(id: rid) as req,
        Bucket(id: rid, tokens: t, max_tokens: m) as bucket
    remove
        req, bucket
    when
        t > 0
    tell
        Bucket(id: rid, tokens: t - 1, max_tokens: m),
        Allowed(id: rid, remaining: t - 1)
    end

rule deny_when_empty =
    on
        Bucket(id: rid, tokens: 0),
        Request(id: rid) as req
    remove
        req
    tell
        Denied(id: rid)
    end

The first two lines declare two structural types and put them in the constraint role. So their values live in a store: a collection of facts the rules work on. The next two are events, which leave the store as soon as the rules are done with them.

Then come two rules, and each reads as one sentence. consume_token: on a Request and a Bucket with the same id, remove both when the bucket has tokens, and tell a bucket with one token fewer and an Allowed event. deny_when_empty: on a bucket with no tokens and a request made against it, remove the request and tell Denied.

Nobody calls a rule. You add Request(id: "api-key-1") to the store, and the store looks for rules whose left-hand side now matches, and fires them. It repeats until no rule matches any more. That end state is called the fixed point: the store has settled, and the events produced along the way are what the outside world sees.

Three pieces of syntax carry all of the meaning.

on, as and remove say what happens to the facts a rule matched. on lists the patterns, as names a matched fact, and remove lists the named facts the rule takes out of the store. Every fact it does not remove stays. The bucket in deny_when_empty is kept, because denying a request does not change the bucket. The bucket in consume_token is removed, because a new one with a different count replaces it.

There is no update, only remove and add: tell adds facts. The compiler knows from its declaration whether each is a constraint, which stays in the store, or an event, which leaves once the store settles. This split between kept and removed facts comes from Constraint Handling Rules (CHR), a rule language from the logic programming world that Bondy builds on.

A variable that appears in two patterns is a join. rid appears in both Request and Bucket, so the rule only fires for a request and a bucket with the same id. This is the part a function cannot give you, because a function receives one input. A rule matches a combination of facts, and the engine finds the combination for you. In the Erlang version the join is maps:find(Id, Bs), but here it is a shared name. Matching a pattern like Bucket(id: rid, tokens: 0) against a fact in the store is the same unification the previous post showed on values.

when is a guard, and it must be pure. t > 0 is an ordinary boolean expression over the matched variables, and it can call functions. The compiler checks that every function a guard calls has no side effects, always gives the same answer for the same input, and always returns. Otherwise it rejects the rule. That keeps the choice of which rule fires a question about the store, never about the clock or the network. How the compiler knows what a function does is the subject of the post on effects.

Adding the second rule

"Premium buckets are never denied." In the gen_server this touches the {ok, #{tokens := 0}} clause, adds a field to the bucket map, and changes the guard on the first clause. In the store, it is one more field and one more rule:

constraint Bucket = {
    id: String, 
    tokens: Int, 
    max_tokens: Int, 
    premium?: Bool = false
}

@priority(10)
rule premium_always_allowed =
    on
        Bucket(id: rid, premium: true),
        Request(id: rid) as req
    remove
        req
    tell
        Allowed(id: rid, remaining: -1)
    end

The field defaults to false, so the existing rules, which build a Bucket without it, stay as they are. Without annotations, the engine tries rules in the order they are written. @priority(10) moves this rule ahead of the others, so a premium request never reaches deny_when_empty, wherever the rule sits in the file. What matters is that the new requirement arrived as one new rule next to the old ones, and nothing else changed.

Rules that look at the whole store

A guard can also ask about the store as a whole. Say every allowed request leaves a Spent fact behind, and a bucket is exhausted once there are as many of them as its cap:

constraint Bucket = {id: String, tokens: Int, max_tokens: Int}
constraint Spent  = {id: String, cost: Int}
event Exhausted   = {id: String}

rule exhausted =
    on
        Bucket(id: rid, max_tokens: cap)
    when
        count_if(Spent(id: rid)) >= cap
    tell
        Exhausted(id: rid)
    end

count_if counts every Spent in the store that matches the pattern. There are a few of these aggregates, among them count_if, exists, maxover and findall. They let a rule see the state of the world, not only the facts it matched. The gen_server equivalent is a fold over a map inside a guard, which means a helper function you write, name and test separately.

What the compiler refuses

A rule is a declaration, not a block of control flow, so the compiler can inspect it before it runs. My first version of a spending cap was the obvious one: allow a request while fewer requests than the cap have been spent.

rule allow_under_cap =
    on
        Bucket(id: rid, max_tokens: cap),
        Request(id: rid) as req
    remove
        req
    when
        count_if(Spent(id: rid)) < cap
    tell
        Spent(id: rid),
        Allowed(id: rid)
    end

The compiler refused it:

-- TYPE CHECK FAILED ---------------------------------

I ran into a problem in your code:

type checking failed with 1 error

Guard of rule allow_under_cap is not monotone under store growth (verdict: anti_monotone), which would break confluence. Absence tests and anti-monotone comparators are not supported; encode the absence as a complementary constraint

Here is what it means. Facts can arrive in any order: a request, then another request, then a refill, from different callers at the same time. A rule set is well behaved (the CHR term is confluent) when the store reaches the same state whatever that order was. A guard that can go from true to false as more facts arrive breaks this.

count_if(…) < cap is true while few facts have been spent and becomes false as more arrive, so whether a request is allowed would depend on who got in first. So the compiler requires that once a guard is true, adding facts can't make it false. count_if(P) >= k passes, because more facts only keep it true. count_if(P) < k and count_if(P) == 0 don't.

"Encode the absence as a complementary constraint" is the fix, and you have already seen it. Instead of counting what has been spent and comparing against a cap, keep a count of what is left in the store and let rules change it. That is the tokens field of Bucket, and consume_token is the rule that uses it. The compiler pushed me back to the design that was right from the start.

The compiler does not yet prove that a rule set terminates^[1]. The guard check is the part of that story that ships today, and I would rather say so than have you discover it. It also catches the common mistakes, with errors that name the rule. They are a remove of a name that no pattern binds with as, a name bound or removed twice, and a section written twice or out of order. The order is always on, remove, when, tell, end.

What it replaces

The handle_call at the top of this post is a rule engine written by hand. It has a store (the state map), a set of rules (the clauses), a matcher (the patterns and guards), and an update (the map syntax). Every gen_server whose state is a collection of things that interact is one of these, and in every one of them the rules are dissolved into the plumbing.

A rule store gives you the sentences back. The bucket, the request, the cap and the premium flag are facts. "A request with tokens available is allowed" is a rule. The engine does the matching, the ordering and the settling. What is left to write is the part of the gen_server that was never about the rules: who can add facts to the store, and who hears what comes out. That is a process, and it is the next post.

---

1. It is work in progress and part of the roadmap. ↩︎