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 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.
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 UNKNOWNA 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"}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 UNRESOLVEDA 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) == expectedThe 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.
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 NoneIn 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 typesparameters() 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:
__init__().marked() reads both performs() and
hides().assigned() records shadows a built-in of that
name.Err.# 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.
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 rowsAn 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.
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 TellAppendix 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:
hides() removes an Effect from the body’s
row.Unknown.# 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"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.
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.
Here, in one place, is what the checker resolves:
builtinstime.sleep or requests.getFinal[...]), or a parameter or
variable annotated with a type alias defined in the
same moduledict.fromkeys()__init__() performs when it defines
oneEvery 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:
dataclass(frozen=True)(cls)with,
an except, a walrus, a tuple target, a pattern, a
*args or **kwargs parameter, or the
parameters of a nested function or a lambdaX | Y union, or
with a type alias imported from another modulestaticmethod’s first parameter, because the first
parameter of every method gets the class as its typeA 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:
list(map(print, names)) the checker resolves
list() and map(), which the table
calls pure. print is an argument there, so the
checker passes over it.with statement, or a for
loop.Any, object,
Optional[...], Union[...], or
type[...] resolves under typing or
builtins.
p.with_suffix(".bak").write_text(text) resolves to
pathlib.Path.with_suffix.write_text, which the
with_* pattern matches.ast.walk() reaches a nested class or
function, so its calls count toward the enclosing function.def or class statement, or by a
mapping pattern’s **name. assigned()
passes over these bindings, so after
def str(): pass in a body, str.upper()
resolves to builtins.str.upper, which the table
calls pure.__new__(), __post_init__(), or an
inherited __init__().typing.Annotated or an as alias,
because the checker finds Annotated and
performs by those names.hides(), whose claim the checker takes on
trust.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.