Index
Contents
Appendix B

An Effect Checker

Effect Tracking lists five problems a checker for Annotated rows must solve, and concludes that solving them all means rebuilding a type checker. This appendix builds the part that needs no type inference. The checker here reads source text, resolves the calls it can, infers a row for every function, and reports each declared row the body exceeds. It is about 450 lines.

Most of the checker’s pieces come from earlier chapters: a match over syntax-tree nodes, records for the data, a Result for the one operation in the core that can fail, and a pure core with its Effects at the edge. The Checker Checks Itself runs the checker on its own source to confirm that the core is pure.

The Restriction

The checker resolves a call by its name and by the type of its receiver, when the source writes that type out or makes it evident. A call it cannot resolve contributes an Effect named Unknown to the caller’s row, instead of counting as pure. With that rule the tool stays small, and every unresolved call shows in a row or, for a function that declares its row, in the report that the body exceeds the declaration. A row that reads Unknown says the checker could not resolve a call, and where.

Of the roughly 6,800 calls in this book’s chapter listings, nearly four in five resolve by name alone: a built-in, an imported name, or a function or class defined in the same file. The largest remaining group is a method called on a local variable with no annotation. From a Call to a Name recovers part of that group.

The checker follows Koka’s policy. A function with no declared row gets an inferred one. The checker compares a declared row with the function’s body. The function’s callers use the declaration in place of the body. An empty performs() declares that a function is pure.

Effect Names and the Table

An Effect is an empty class, as Ask and Tell are in Effect Tracking. These eight cover the standard library:

# effect_names.py
class Console: ...
class FileSystem: ...
class Network: ...
class Clock: ...
class Random: ...
class Environment: ...
class Process: ...
class Unknown: ...

One question decides whether something gets an Effect name: does a test replace it? A test replaces the clock, the network, and the file system. No test replaces len(). A finer vocabulary makes the rows hard to read and the table in effect_table.py hard to maintain.

Appendix A lists three answers to the question of what untracked code performs: pure, Unknown, or a separate declaration. This checker declares the standard library separately, because pure and Unknown both misdescribe print(). print() writes to the console, and calling it Unknown puts Unknown in nearly every row.

The declaration cannot go on the function. A built-in has no __annotations__ and no __dict__ in which to store one, so print.__annotations__ = {} raises an AttributeError. The declarations therefore go in a table:

# effect_table.py
from fnmatch import fnmatchcase
from typing import Final
from effect_names import (Clock, Console, Environment,
                          FileSystem, Network, Process,
                          Random, Unknown)

type Row = frozenset[str]
type Table = dict[str, Row]

def names(*effects: type) -> Row:
    return frozenset(e.__name__ for e in effects)

PURE: Final[Row] = names()
UNKNOWN: Final[Row] = names(Unknown)
STDLIB: Final[Table] = {
    "builtins.print": names(Console),
    "builtins.input": names(Console),
    "builtins.open": names(FileSystem),
    "builtins.eval": UNKNOWN,
    "builtins.exec": UNKNOWN,
    "builtins.*": PURE,
    "pathlib.Path": PURE,
    "pathlib.Path.with_*": PURE,
    "pathlib.Path.*": names(FileSystem),
    "time.time": names(Clock),
    "time.sleep": names(Clock),
    "time.perf_counter": names(Clock),
    "datetime.datetime.now": names(Clock),
    "random.*": names(Random),
    "os.environ.*": names(Environment),
    "os.getenv": names(Environment),
    "os.path.join": PURE,
    "os.*": names(FileSystem),
    "socket.*": names(Network),
    "urllib.request.*": names(Network),
    "subprocess.*": names(Process),
    "ast.*": PURE,
    "fnmatch.*": PURE,
    "itertools.*": PURE,
    "functools.*": PURE,
    "math.*": PURE,
    "typing.*": PURE,
}

def lookup(name: str, table: Table) -> Row:
    for pattern, row in table.items():
        if fnmatchcase(name, pattern):
            return row
    return UNKNOWN

A key is an fnmatch pattern, the wildcard notation of a shell, in which * matches any run of characters, dots included. lookup() calls fnmatchcase() instead of fnmatch(), because fnmatch() follows the operating system’s rule for file names, and on Windows that rule ignores case. Python names are case-sensitive, so the table’s patterns must be too.

lookup() returns the row of the first pattern that matches. A specific name goes above the glob that would otherwise match it, because a dictionary keeps insertion order. "os.path.join" is pure. The "os.*" below it is FileSystem. Whole modules take one line each, which keeps the table short.

A name that falls through every pattern gets UNKNOWN. Because the table lists pure modules by name, leaving a module out can add an Unknown and cannot hide an Effect.

The key is the name as a programmer imports it, because a function’s own attributes often report a different name. os.remove.__module__ is nt on Windows and posix elsewhere, open.__module__ is _io, and random.random reports None for its module and Random.random for its qualified name. The checker reads source, and in source the name is os.remove.

names() takes classes, so the type checker reports a misspelled Effect in the table. The row names() builds holds the classes’ names, a frozenset[str], because the checker reads the code as text instead of importing it. In source text, performs(Ask) is the name Ask.

The test file confirms that the first matching pattern wins, that a name outside the table gets UNKNOWN, and that names() reads class names:

# test_effect_table.py
import pytest
from effect_table import STDLIB, UNKNOWN, lookup, names

@pytest.mark.parametrize(
    "name, expected",
    [
        ("builtins.print", {"Console"}),
        ("builtins.len", set()),
        ("pathlib.Path.read_text", {"FileSystem"}),
        ("pathlib.Path.with_suffix", set()),
        ("time.time", {"Clock"}),
        ("os.path.join", set()),
        ("os.remove", {"FileSystem"}),
    ],
)
def test_first_matching_pattern_wins(
    name: str, expected: set[str]
) -> None:
    assert lookup(name, STDLIB) == expected

def test_unlisted_name_is_unknown_not_pure() -> None:
    assert lookup("requests.get", STDLIB) == UNKNOWN

def test_names_reads_class_names() -> None:
    class Ask: ...
    assert names(Ask) == {"Ask"}

From a Call to a Name

Every call in a syntax tree has a func expression. Here, callee() turns that expression into a dotted name the table can match:

# call_names.py
import ast
import builtins
from typing import Final
from record import record

type FullName = str

UNRESOLVED: Final[FullName] = "?"
LITERALS: Final[dict[type[ast.expr], FullName]] = {
    ast.List: "builtins.list",
    ast.ListComp: "builtins.list",
    ast.Dict: "builtins.dict",
    ast.DictComp: "builtins.dict",
    ast.Set: "builtins.set",
    ast.SetComp: "builtins.set",
    ast.Tuple: "builtins.tuple",
    ast.JoinedStr: "builtins.str",
}

def top_of(name: str) -> str:
    return name.split(".")[0]

def imports_of(tree: ast.Module) -> dict[str, FullName]:
    found: dict[str, FullName] = {}
    for node in ast.walk(tree):
        match node:
            case ast.Import(names=aliases):
                for a in aliases:
                    top = top_of(a.name)
                    full = a.name if a.asname else top
                    found[a.asname or top] = full
            case ast.ImportFrom(
                module=str(module), names=aliases
            ):
                for a in aliases:
                    full = f"{module}.{a.name}"
                    found[a.asname or a.name] = full
    return found

def dotted(node: ast.expr) -> list[str]:
    match node:
        case ast.Name(id=name):
            return [name]
        case ast.Attribute(value=value, attr=attr):
            head = dotted(value)
            return [*head, attr] if head else []
        case _:
            return []

imports_of() and dotted() match class patterns against ast nodes. Composite and Interpreter notes that the standard library walks these trees with ast.NodeVisitor, in the style of Visitor. ast.NodeVisitor looks up the method for a node by name, visit_ plus the node’s class name, so a walker subclasses ast.NodeVisitor and defines one such method for each node class it handles. A match lists the node classes in its cases, so it chooses the code to run for each node class, the job a walker gives to an ast.NodeVisitor subclass.

dotted() is the smallest of these matches. It is recursive, as the tree is. os.path.join is an Attribute whose value is an Attribute whose value is a Name.

callee() is a method of Scope, in the same file:

# call_names.py (continued)
@record
class Scope:
    module: str
    names: dict[str, FullName]
    defined: frozenset[str]
    types: dict[str, FullName]

    def name(self, name: str) -> FullName:
        if name in self.types:
            return UNRESOLVED
        if name in self.names:
            return self.names[name]
        if name in self.defined:
            return f"{self.module}.{name}"
        if hasattr(builtins, name):
            return f"builtins.{name}"
        return UNRESOLVED

    def annotation(self, node: ast.expr) -> FullName:
        match node:
            case ast.Subscript(value=value, slice=inner):
                outer = self.annotation(value)
                if outer == "typing.Final":
                    return self.annotation(inner)
                return outer
        match dotted(node):
            case [head, *rest]:
                return ".".join([self.name(head), *rest])
            case _:
                return UNRESOLVED

    def type_of(self, node: ast.expr) -> FullName:
        match node:
            case ast.Constant(value=str()):
                return "builtins.str"
            case ast.Name(id=name) if name in self.types:
                return self.types[name]
            case ast.Name(id=name):
                return self.name(name)
            case ast.Call(func=func):
                return self.callee(func)
            case _:
                return LITERALS.get(type(node), UNRESOLVED)

    def callee(self, func: ast.expr) -> FullName:
        match func:
            case ast.Name(id=name):
                return self.name(name)
            case ast.Attribute(value=value, attr=attr):
                if top_of(ast.unparse(func)) in self.names:
                    return self.annotation(func)
                receiver = self.type_of(value)
                if receiver == UNRESOLVED:
                    return UNRESOLVED
                return f"{receiver}.{attr}"
            case _:
                return UNRESOLVED

A Scope holds the names the checker has collected at one point in a file. names maps a local name to its full one, so rm becomes os.remove. defined holds the functions and classes the module defines. types maps a variable to the name of its type.

name() searches from the innermost scope outward, as Python does: variables, then the module’s imports and definitions, then builtins. A name found in types is a variable, and calling a variable calls the value it holds at runtime. The source does not say what that value is, so name() answers UNRESOLVED.

callee() handles the two shapes a resolvable call takes. An attribute is either a path through an import, such as time.sleep, or a method on a receiver. type_of() finds the receiver’s type where the source makes it evident: a string constant, one of the literals in LITERALS, a variable whose type the scope records, a class name such as dict, or a call, which takes its callee’s name as its type. p = Path(name) therefore gives p the type pathlib.Path, and p.read_text() becomes pathlib.Path.read_text, which a pattern in the table matches.

annotation() reads a written type.

The test file confirms that imports_of() maps each local name to its full one, and that callee() resolves each shape of call or answers UNRESOLVED:

# test_call_names.py
import ast
import pytest
from call_names import UNRESOLVED, Scope, imports_of

def test_imports_map_local_names_to_full_names() -> None:
    tree = ast.parse(
        "import os\n"
        "import os.path as p\n"
        "from os import remove as rm\n"
    )
    assert imports_of(tree) == {
        "os": "os",
        "p": "os.path",
        "rm": "os.remove",
    }

def callee(call: str, types: dict[str, str]) -> str:
    names = {"rm": "os.remove", "time": "time"}
    scope = Scope("m", names, frozenset({"local"}), types)
    node = ast.parse(call, mode="eval").body
    assert isinstance(node, ast.Call)
    return scope.callee(node.func)

@pytest.mark.parametrize(
    "call, expected",
    [
        ("rm(x)", "os.remove"),
        ("time.sleep(1)", "time.sleep"),
        ("local()", "m.local"),
        ("print(x)", "builtins.print"),
        ("', '.join(xs)", "builtins.str.join"),
        ("[].append(1)", "builtins.list.append"),
        ("dict.fromkeys(xs)", "builtins.dict.fromkeys"),
        ("p.read_text()", "pathlib.Path.read_text"),
        ("action(x)", UNRESOLVED),
        ("q.anything()", UNRESOLVED),
        ("f()()", UNRESOLVED),
    ],
)
def test_a_call_resolves_to_a_dotted_name(
    call: str, expected: str
) -> None:
    types = {"p": "pathlib.Path", "action": UNRESOLVED}
    assert callee(call, types) == expected

The last three cases are the limits. action(x) calls a parameter, q.anything() has a receiver of no known type, and f()() calls the result of a call.

Facts About a Function

The checker needs three facts about a function: the row it declares, the Effects it hides, and the names it calls.

Hiding needs a marker, and ask() in Effect Tracking shows why. ask() declares Ask and calls input(), which performs Console. Both descriptions are accurate. The declared row holds Ask alone, so The Check shows the checker reporting Console as undeclared. A second piece of metadata names the Effects the function performs and leaves out of its declared row:

# effect_marks.py
from record import record

@record
class Hides:
    effects: frozenset[type]

def hides(*effects: type) -> Hides:
    return Hides(frozenset(effects))

Annotated[str, performs(Ask), hides(Console)] states that ask() is the boundary where Console becomes Ask. The checker removes Console from the body’s row and takes the claim on trust, as the type checker trusts a cast(). hides() is the third line of Appendix A’s rule, “the Effects f handles,” in the weakest form you can write without handlers.

The annotation also puts two pieces of metadata in one Annotated. Under PEP 593, an Annotated can carry any number of metadata objects after its type. row() from Appendix A keeps the Performs objects and passes over the Hides object.

# function_facts.py
import ast
from typing import Literal
from call_names import Scope
from effect_table import PURE, Row
from local_types import (Def, assigned, is_def, is_function,
                         module_scope, parameters)
from record import record
from result import Err, Ok, Result

@record
class Facts:
    name: str
    declared: Row | None
    hidden: Row
    calls: tuple[str, ...]

def marked(
    func: Def, marker: Literal["performs", "hides"]
) -> Row | None:
    match func.returns:
        case ast.Subscript(
            value=ast.Name(id="Annotated"),
            slice=ast.Tuple(elts=[_, *extras]),
        ):
            for extra in extras:
                match extra:
                    case ast.Call(
                        func=ast.Name(id=found), args=args
                    ) if found == marker:
                        return frozenset(
                            a.id
                            for a in args
                            if isinstance(a, ast.Name)
                        )
    return None

In marked(), the guard, if found == marker, compares a captured name with a parameter, which a pattern alone cannot do.

For a function that declares no row, marked(func, "performs") returns None, which means “inferred.” An empty row means “pure,” so None and the empty row must differ. Row | None is an ordinary optional. Each reader tests for None instead of asserting that the row is present.

# function_facts.py (continued)
def calls_in(
    body: list[ast.stmt], scope: Scope
) -> tuple[str, ...]:
    return tuple(
        scope.callee(node.func)
        for stmt in body
        for node in ast.walk(stmt)
        if isinstance(node, ast.Call)
    )

def function_facts(
    func: Def, base: Scope, owner: str
) -> Facts:
    types = (
        base.types
        | parameters(func, base, owner)
        | assigned(func.body, base)
    )
    scope = Scope(
        base.module, base.names, base.defined, types
    )
    return Facts(
        f"{owner or base.module}.{func.name}",
        marked(func, "performs"),
        marked(func, "hides") or PURE,
        calls_in(func.body, scope),
    )

def class_facts(
    node: ast.ClassDef, base: Scope
) -> list[Facts]:
    owner = f"{base.module}.{node.name}"
    methods = [
        function_facts(m, base, owner)
        for m in node.body
        if is_function(m)
    ]
    init = f"{owner}.__init__"
    built = tuple(m.name for m in methods if m.name == init)
    return [*methods, Facts(owner, None, PURE, built)]

def facts_of(module: str, tree: ast.Module) -> list[Facts]:
    base = module_scope(module, tree)
    found: list[Facts] = []
    for node in tree.body:
        if is_function(node):
            found.append(function_facts(node, base, ""))
        elif isinstance(node, ast.ClassDef):
            found += class_facts(node, base)
    top = [node for node in tree.body if not is_def(node)]
    name = f"{module}.<module>"
    calls = calls_in(top, base)
    return [*found, Facts(name, None, PURE, calls)]

calls_in() collects the third fact. ast.walk() descends into a nested function or a lambda, so the calls inside one count toward the function that contains it.

A class’s entry holds a call to its __init__() when the class defines one, so Log() performs what Log.__init__() performs.

The module’s top-level statements become a function named module.<module>. That function is the program’s edge. The checker always infers its row, which says what running the file performs.

# function_facts.py (continued)
def read_module(
    module: str, source: str
) -> Result[list[Facts], str]:
    try:
        tree = ast.parse(source)
    except SyntaxError as e:
        return Err(f"{module}: line {e.lineno}: {e.msg}")
    return Ok(facts_of(module, tree))

read_module() is the one operation here that can fail. It returns a Result, so a parse failure becomes a value the caller must inspect.

The local-type helpers that function_facts.py imports fill a Scope from a function’s own parameters and assignments:

# local_types.py
import ast
from typing import TypeIs
from call_names import (FullName, UNRESOLVED, Scope,
                        imports_of)

type Def = ast.FunctionDef | ast.AsyncFunctionDef

def assigned(
    body: list[ast.stmt], scope: Scope
) -> dict[str, FullName]:
    types: dict[str, FullName] = {}
    written: dict[str, FullName] = {}
    values: dict[ast.AST, FullName] = {}
    nodes = (n for stmt in body for n in ast.walk(stmt))
    for node in nodes:
        match node:
            case ast.AnnAssign(
                target=ast.Name(id=name), annotation=note
            ):
                written[name] = scope.annotation(note)
            case ast.Assign(targets=[target], value=value):
                values[target] = scope.type_of(value)
            case (
                ast.Name(id=name, ctx=ast.Store())
                | ast.MatchAs(name=str(name))
                | ast.MatchStar(name=str(name))
                | ast.ExceptHandler(name=str(name))
                | ast.arg(arg=name)
            ):
                found = values.get(node, UNRESOLVED)
                if types.setdefault(name, found) != found:
                    types[name] = UNRESOLVED
    return types | written

def parameters(
    func: Def, scope: Scope, owner: str
) -> dict[str, FullName]:
    args = func.args
    positional = args.posonlyargs + args.args
    every = positional + args.kwonlyargs
    types = {
        arg.arg: scope.annotation(arg.annotation)
        if arg.annotation
        else UNRESOLVED
        for arg in every
    }
    for packed in (args.vararg, args.kwarg):
        if packed:
            types[packed.arg] = UNRESOLVED
    if owner and positional:
        types[positional[0].arg] = owner
    return types

parameters() and assigned() fill a scope’s types: an annotated parameter, the first parameter of a method (the class), an annotated assignment, and a plain assignment whose right side has an evident type. parameters() gives every other parameter UNRESOLVED, including a *args or **kwargs parameter, whose annotation gives the type of each item and not of the tuple or dictionary. assigned() also records a name a body binds in any of these ways: a loop variable, a with or except target, a walrus target, a name inside a tuple target, a name a capture, as, or star pattern binds, and a parameter of a nested function or a lambda. A name bound in any of those ways gets UNRESOLVED, and so does a name that two assignments give different types. An annotation overrides UNRESOLVED in both cases.

The or-pattern in assigned() matches every one of those binding nodes. Each alternative binds name, as an or-pattern requires. ast.walk() visits an assignment before its target, so values holds the type of the right side when the walk reaches the target’s Name.

# local_types.py (continued)
def is_function(node: ast.stmt) -> TypeIs[Def]:
    kinds = ast.FunctionDef | ast.AsyncFunctionDef
    return isinstance(node, kinds)

def is_def(
    node: ast.stmt,
) -> TypeIs[Def | ast.ClassDef]:
    if isinstance(node, ast.ClassDef):
        return True
    return is_function(node)

def module_scope(module: str, tree: ast.Module) -> Scope:
    defined = frozenset(
        node.name for node in tree.body if is_def(node)
    )
    bare = Scope(module, imports_of(tree), defined, {})
    aliases = {
        node.name.id: bare.annotation(node.value)
        for node in tree.body
        if isinstance(node, ast.TypeAlias)
    }
    named = Scope(module, bare.names | aliases, defined, {})
    top = [
        node
        for node in tree.body
        if not is_def(node)
        and not isinstance(node, ast.TypeAlias)
    ]
    types = assigned(top, named)
    return Scope(module, named.names, defined, types)

module_scope() reads each type statement separately, so a parameter annotated Table resolves to builtins.dict. It also keeps those statements out of assigned(), which would otherwise record an alias’s name as a variable.

Because is_function() and is_def() return TypeIs, a comprehension filtered by one yields nodes whose narrowed type has a name.

The test file confirms that:

# test_function_facts.py
from textwrap import indent
from typing import Final
import pytest
from call_names import UNRESOLVED
from function_facts import Facts, read_module
from result import Err, Ok

SOURCE: Final[str] = '''
from pathlib import Path
from typing import Annotated, Final

type Names = list[str]
LIMIT: Final[dict[str, int]] = {}

class Log:
    def __init__(self) -> None:
        print("open")

    def write(self, text: str) -> None:
        self.flush()

    def flush(self) -> None: ...

def save(
    p: Path, names: Names
) -> Annotated[None, performs(FileSystem), hides(Console)]:
    log = Log()
    log.write(", ".join(names))
    names.sort()
    LIMIT.get("x")
    p.write_text("")
'''

def facts(source: str = SOURCE) -> dict[str, Facts]:
    match read_module("m", source):
        case Ok(found):
            return {f.name: f for f in found}
        case Err(problem):
            raise AssertionError(problem)

def test_every_def_and_the_module_get_facts() -> None:
    assert sorted(facts()) == [
        "m.<module>",
        "m.Log",
        "m.Log.__init__",
        "m.Log.flush",
        "m.Log.write",
        "m.save",
    ]

def test_a_class_calls_its_init() -> None:
    assert facts()["m.Log"].calls == ("m.Log.__init__",)

def test_self_resolves_to_the_class() -> None:
    assert facts()["m.Log.write"].calls == ("m.Log.flush",)

def test_receivers_resolve_five_ways() -> None:
    assert facts()["m.save"].calls == (
        "m.Log",
        "m.Log.write",
        "builtins.str.join",
        "builtins.list.sort",
        "builtins.dict.get",
        "pathlib.Path.write_text",
    )

def test_both_markers_are_read() -> None:
    save = facts()["m.save"]
    assert save.declared == {"FileSystem"}
    assert save.hidden == {"Console"}

@pytest.mark.parametrize(
    "binding",
    [
        "for str in xs: pass",
        "with open(xs) as str: pass",
        "if str := xs.pop(): pass",
        "str, n = xs",
        "match xs:\n  case [str]: pass",
        "match xs:\n  case [*str]: pass",
        "try: pass\nexcept OSError as str: pass",
        "key = lambda str: str",
        "str = 'text'\nstr = list(xs)",
    ],
)
def test_a_binding_shadows_the_builtin(
    binding: str,
) -> None:
    body = indent(f"{binding}\nstr.upper()", "    ")
    calls = facts(f"def f(xs):\n{body}\n")["m.f"].calls
    assert calls[-1] == UNRESOLVED

def test_a_packed_parameter_shadows_the_builtin() -> None:
    source = (
        "def f(*dir, **str):\n"
        "    dir.pop()\n"
        "    str.pop()\n"
    )
    assert facts(source)["m.f"].calls == (
        UNRESOLVED,
        UNRESOLVED,
    )

def test_a_syntax_error_comes_back_as_a_value() -> None:
    result = read_module("bad", "def f(:\n")
    assert isinstance(result, Err)
    assert result.error.startswith("bad: line 1")

test_receivers_resolve_five_ways() shows the receiver rules together. In save(), log gets its type from a constructor call, the string by being a constant, names through a type alias, LIMIT through Final[...], and p by its annotation.

In test_a_binding_shadows_the_builtin(), str.upper() comes back UNRESOLVED after each binding instead of resolving to builtins.str.upper.

Rows to a Fixed Point

The rule in Effect Tracking is recursive. A function’s row needs its callees’ rows, which in turn need their callees’ rows. Two functions that call each other make the recursion circular. The standard answer is to start every row empty and apply the rule until the rows stop changing. Rows that the rule leaves unchanged are a fixed point of the rule:

# infer_rows.py
from effect_table import Row, Table, lookup
from function_facts import Facts

type Rows = dict[str, Row]

def call_row(call: str, rows: Rows, table: Table) -> Row:
    if call in rows:
        return rows[call]
    return lookup(call, table)

def body_row(facts: Facts, rows: Rows, table: Table) -> Row:
    found = (call_row(c, rows, table) for c in facts.calls)
    return frozenset().union(*found)

def step(
    known: dict[str, Facts], rows: Rows, table: Table
) -> Rows:
    return {
        name: facts.declared
        if facts.declared is not None
        else body_row(facts, rows, table)
        for name, facts in known.items()
    }

def infer(known: dict[str, Facts], table: Table) -> Rows:
    rows: Rows = dict.fromkeys(known, frozenset())
    while (new := step(known, rows, table)) != rows:
        rows = new
    return rows

An unresolved call has the name "?", which falls through every pattern, so lookup() answers UNKNOWN.

step() is a pure function from one set of rows to the next. A declared row stays as written, so a caller’s row includes the declaration. Every other function gets the union of what its calls perform.

infer() is the loop. With the walrus operator, the while condition computes the next rows and compares them in one expression. Each step can add members to a row and cannot remove one, and the vocabulary is finite, so the loop ends.

# test_infer_rows.py
from effect_table import PURE, STDLIB
from function_facts import Facts
from infer_rows import infer

def known(*facts: Facts) -> dict[str, Facts]:
    return {f.name: f for f in facts}

def test_rows_propagate_up_the_call_chain() -> None:
    rows = infer(
        known(
            Facts("m.a", None, PURE, ("m.b",)),
            Facts("m.b", None, PURE, ("m.c",)),
            Facts("m.c", None, PURE, ("builtins.print",)),
        ),
        STDLIB,
    )
    assert rows["m.a"] == {"Console"}

def test_circular_calls_reach_a_fixed_point() -> None:
    calls = ("m.even", "time.time")
    rows = infer(
        known(
            Facts("m.even", None, PURE, ("m.odd",)),
            Facts("m.odd", None, PURE, calls),
        ),
        STDLIB,
    )
    assert rows["m.even"] == rows["m.odd"] == {"Clock"}

def test_a_declared_row_is_trusted_by_callers() -> None:
    declared = frozenset({"Ask"})
    calls = ("builtins.input",)
    rows = infer(
        known(
            Facts("m.ask", declared, PURE, calls),
            Facts("m.greet", None, PURE, ("m.ask",)),
        ),
        STDLIB,
    )
    assert rows["m.greet"] == {"Ask"}

infer_rows.py starts from Facts, so each test builds its Facts as a literal instead of writing and parsing a program.

The Check

A finding is an Effect that a function’s body performs, that the function does not hide, and that its declared row omits:

# row_check.py
from effect_table import STDLIB, Table
from function_facts import Facts, read_module
from infer_rows import Rows, body_row, infer
from record import record
from result import Err, Ok

type ModuleName = str

@record
class Undeclared:
    where: str
    effect: str

@record
class Unparsed:
    where: str
    message: str

type Finding = Undeclared | Unparsed

@record
class Report:
    rows: Rows
    findings: list[Finding]

def undeclared(
    facts: Facts, rows: Rows, table: Table
) -> list[Finding]:
    if facts.declared is None:
        return []
    body = body_row(facts, rows, table) - facts.hidden
    return [
        Undeclared(facts.name, effect)
        for effect in sorted(body - facts.declared)
    ]

def check(
    sources: dict[ModuleName, str], table: Table = STDLIB
) -> Report:
    known: dict[str, Facts] = {}
    findings: list[Finding] = []
    for module, source in sources.items():
        match read_module(module, source):
            case Ok(found):
                known |= {f.name: f for f in found}
            case Err(problem):
                findings.append(Unparsed(module, problem))
    rows = infer(known, table)
    for facts in known.values():
        findings += undeclared(facts, rows, table)
    return Report(rows, findings)

Everything check() reads arrives as an argument, and everything it produces leaves in the Report, so a test passes it a string and checks the returned value.

The last two functions turn findings and rows into text:

# row_check.py (continued)
def describe(finding: Finding) -> str:
    match finding:
        case Undeclared(where, effect):
            return f"! {where} undeclared {effect}"
        case Unparsed(where, message):
            return f"! {where} {message}"

def lines(report: Report) -> list[str]:
    rows = [
        f"{name} {sorted(report.rows[name])}"
        for name in report.rows
        if report.rows[name]
    ]
    return rows + [describe(f) for f in report.findings]

Finding is the union of Undeclared and Unparsed, so a caller matches on the kind of finding and reads the fields of that kind: the Effect name of an Undeclared, the parse error of an Unparsed. describe() is one such caller, and turns each kind of finding into a line of text.

lines() returns strings and leaves the printing to the program that runs the checker, so the core stays pure.

Here is the checker on the greeting program from Effect Tracking:

# greeting_check.py
from typing import Final
from row_check import check, lines

GREETING: Final[str] = '''
from typing import Annotated
from effect_rows import performs

class Ask: ...
class Tell: ...

def ask(prompt: str) -> Annotated[str, performs(Ask)]:
    return input(prompt)

def tell(message: str) -> Annotated[None, performs(Tell)]:
    print(message)

def greet() -> Annotated[None, performs(Ask, Tell)]:
    name: str = ask("What is your name? ")
    tell(f"Hello, {name}!")

def shout(message: str) -> None:
    tell(message.upper())

def quiet() -> Annotated[None, performs()]:
    shout("hi")
'''
for line in lines(check({"greeting": GREETING})):
    print(line)
#: greeting.ask ['Ask']
#: greeting.tell ['Tell']
#: greeting.greet ['Ask', 'Tell']
#: greeting.shout ['Tell']
#: ! greeting.ask undeclared Console
#: ! greeting.tell undeclared Console
#: ! greeting.quiet undeclared Tell

Appendix A’s row() reads [] for both shout() and quiet(). The checker infers ['Tell'] for shout() from its call to tell(). quiet() declares itself pure and calls shout(), so the checker reports quiet(), two calls away from the tell() whose declaration supplies the Tell. Computing quiet()’s body row from shout()’s inferred row is propagation, which Appendix A’s tracked_greeting.py cannot do.

Facts About a Function predicts the first two findings. tell() declares Tell and performs Console, the shape that section gives ask(). Adding hides(Console) to ask() and tell() clears both findings.

The test file confirms that:

# test_row_check.py
from typing import Final
from row_check import Finding, Undeclared, Unparsed, check

HEAD: Final[str] = "from typing import Annotated\n"

def findings(source: str) -> list[Finding]:
    return check({"m": HEAD + source}).findings

def test_an_undeclared_effect_is_a_finding() -> None:
    source = (
        "def f() -> Annotated[None, performs()]:\n"
        "    print('hi')\n"
    )
    assert findings(source) == [
        Undeclared("m.f", "Console")
    ]

def test_a_declared_effect_is_no_finding() -> None:
    source = (
        "def f() -> Annotated[None, performs(Console)]:\n"
        "    print('hi')\n"
    )
    assert findings(source) == []

def test_hides_removes_an_effect_from_the_body() -> None:
    source = (
        "def f() -> Annotated[\n"
        "    None, performs(Tell), hides(Console)\n"
        "]:\n"
        "    print('hi')\n"
    )
    assert findings(source) == []

def test_an_unannotated_function_is_inferred() -> None:
    report = check({"m": "def f():\n    print('hi')\n"})
    assert report.findings == []
    assert report.rows["m.f"] == {"Console"}

def test_an_unresolved_call_is_unknown() -> None:
    source = (
        "def f(action) -> Annotated[None, performs()]:\n"
        "    action()\n"
    )
    assert findings(source) == [
        Undeclared("m.f", "Unknown")
    ]

def test_a_broken_module_is_a_finding() -> None:
    [finding] = check({"bad": "def f(:\n"}).findings
    assert isinstance(finding, Unparsed)
    assert finding.where == "bad"

Effects for Code You Don’t Own

The table covers the standard library with patterns. A third-party library gets its declarations from a stub: source text in this appendix’s own notation, passed to check() under the library’s module name.

# third_party_stub.py
from typing import Final
from row_check import check, lines

APP: Final[str] = '''
import requests
from typing import Annotated
from effect_names import Network
from effect_rows import performs

def fetch(url: str) -> Annotated[str, performs(Network)]:
    return requests.get(url).text
'''
STUB: Final[str] = '''
from typing import Annotated
from effect_names import Network
from effect_rows import performs

def get(
    url: str,
) -> Annotated[object, performs(Network)]: ...
'''
for line in lines(check({"app": APP})):
    print(line)
#: app.fetch ['Network']
#: ! app.fetch undeclared Unknown
for line in lines(check({"app": APP, "requests": STUB})):
    print(line)
#: app.fetch ['Network']
#: requests.get ['Network']

With APP alone, the table reads requests.get as Unknown, so the checker reports a finding for fetch(). With the stub, requests.get is a declared function like any other, and the second run prints its row, ['Network']. fetch()’s body row takes the stub’s declared Network. fetch() declares Network too, so the second run accepts fetch(). The stub’s body is the constant ..., so its body row is empty and stays within its declaration. Type checkers solve the same problem the same way, with stub files that declare the types of code they cannot read.

The Checker Checks Itself

Every function in the checker so far is pure. The edge is the program that runs the checker, the one place the checker reads a file or writes to the console. Each function there declares the row it performs:

# check_files.py
from pathlib import Path
from typing import Annotated, Final
from effect_names import Console, FileSystem
from effect_rows import performs
from row_check import ModuleName, Report, check, lines

def read(
    path: Path,
) -> Annotated[str, performs(FileSystem)]:
    return path.read_text(encoding="utf-8")

def load(
    paths: list[Path],
) -> Annotated[dict[ModuleName, str], performs(FileSystem)]:
    return {path.stem: read(path) for path in paths}

def show(
    report: Report,
) -> Annotated[None, performs(Console)]:
    for line in lines(report):
        print(line)

FILES: Final[list[str]] = [
    "effect_table.py",
    "call_names.py",
    "function_facts.py",
    "local_types.py",
    "infer_rows.py",
    "row_check.py",
    "check_files.py",
    "../utils/result.py",
]
show(check(load([Path(name) for name in FILES])))
#: check_files.read ['FileSystem']
#: check_files.load ['FileSystem']
#: check_files.show ['Console']
#: check_files.<module> ['Console', 'FileSystem']
#: result.Ok.bind ['Unknown']

The demo runs the checker on seven of its own source files and on utils/result.py, and prints every nonempty row. Every function in effect_table.py, call_names.py, function_facts.py, local_types.py, infer_rows.py, and row_check.py has an empty row and stays out of the output, so the checker confirms that its core is pure. FileSystem and Console appear in three functions at the edge and in the module that calls them.

Effect Management describes pushing the Effects to the edges: isolating them in a few functions so the rest of the program stays pure. Here a tool verifies that the checker keeps its Effects at its edge.

The one Unknown is Ok.bind(), which calls the function it receives. That call is the callback problem of Effect Tracking, appearing in a class from this book.

Reaching that output took four changes to the checker’s own code. imports_of() in call_names.py called .split() on a.name, an attribute, which the checker cannot type, so top_of() now takes the name as an annotated parameter. body_row() in infer_rows.py called PURE.union(), a method on an imported constant, and now calls frozenset().union(). type_of() in call_names.py called self.types.get(), a method on a record’s field, and now tests name in self.types in a pattern’s guard. load() called path.read_text() inside a comprehension, and now calls read(path).

Each change is small, and two of them improved the code. The tool required all four. You write for it as you write for a type checker, with types where the tool needs them.

What the Checker Resolves, and What It Cannot See

Here, in one place, is what the checker resolves:

Every limit below produces Unknown, so each one appears in a row or, for a function that declares its row, as a finding against the body row:

A name bound in one of those ways is a variable of no known type, including a name that matches a built-in. Here, both functions perform FileSystem:

# binding_check.py
from typing import Final
from row_check import check, lines

SOURCE: Final[str] = '''
from pathlib import Path

def clear(paths: list[Path]) -> None:
    for dir in paths:
        dir.rmdir()

def load() -> str:
    path = "settings.toml"
    path = Path(path)
    return path.read_text()
'''
for line in lines(check({"m": SOURCE})):
    print(line)
#: m.clear ['Unknown']
#: m.load ['Unknown']

The checker cannot resolve the calls that perform that FileSystem, so each row reads Unknown. If assigned() recorded no binding for the loop variable, dir.rmdir() would resolve to builtins.dir.rmdir. If it kept the first assignment’s type, path.read_text() would resolve to builtins.str.read_text. The builtins.* pattern calls both pure, so both rows would be empty.

The limits in this second list are silent. Each one produces a row that looks complete. A production tool must remove each one:

Some of the limits are bookkeeping, such as resolving Annotated through the imports, reading the decorator that marks a staticmethod, and collecting the calls in a class body. Most of the rest, in either list, are pieces of type inference. An operator runs a method that its operands’ types select, and a method on a call’s result needs the type the call returns. A callback needs the Effect variable of Effect Tracking. Appendix A’s argument holds. Removing those limits means writing a type checker.

Much of tracking needs no type inference, though. Name resolution, a table of the standard library, and a fixed point give every function in a program a row. Here they also verify that the core of the program that computes the rows is pure.