cottax.core.maths.nesting module

Nesting graph: Graph + nesting forest

check_nesting_ends_bound(g: NestingGraph)

Check the within edge has both nodes in the graph.

W ⊆ N × N

Return type:

Iterator[Violation]

check_nesting_ends_are_problems(g: NestingGraph)

Nesting can only be between problems.

W ⊆ N_P × N_P

Return type:

Iterator[Violation]

check_no_nesting_loops(g: NestingGraph)

Nesting can not be looped: this would imply nesting within itself in some form.

(N_P, W) is a forest

Only the acyclicity is checked here: within is a mapping, so one outer per inner ((n,m), (n,m’) ∊ W ⟹ m = m’) holds by construction, and acyclic with out-degree at most one is a forest.

Return type:

Iterator[Violation]

check_nesting_ends_on_one_cycle(g: NestingGraph)

Both ends of a nesting are on one cycle: the inner lies in the outer’s cycle. The inner’s output is required for the outer’s inputs and vice-versa – otherwise the inner does not depend on the outer’s iterate, or the outer never reads its answer, and it could run outside.

p ~ q in N A(q) ∀ (p, q) ∊ W i.e. p ∊ S_q, the cycle of q

A pair with an end unbound or not a problem is skipped: those are other rules’.

Return type:

Iterator[Violation]

check_blocks_partition(g: NestingGraph, blocks: Iterable[Iterable])

Each block is at least two nodes, and no node is in two.

Return type:

Iterator[Violation]

check_blocks_own_something(g: NestingGraph, blocks: Iterable[Iterable])

A block contracts into a computation, so it owns something.

Return type:

Iterator[Violation]

class NestingGraph[N: Label, V: Place](graph: AbstractGraph[N, V], within: OrderedMap[N, N])

Bases: Frozen, Generic[N, V]

A graph plus nesting decision: within, inner -> outer

graph: AbstractGraph[N, V]

within: OrderedMap[N, N]

checks: PerLevel[tuple[Callable[[Any], object], ...]] = (<function check_nesting_ends_bound>, <function check_no_nesting_loops>, <function check_nesting_ends_are_problems>, <function check_nesting_ends_on_one_cycle>)

Callable [self] -> iterable of violations, which are raised at construction unless skipped (see unchecked).

property definitions: Mapping[N, NodeDefinition[V]]

property nodes: tuple[N, ...]

property problems: tuple[N, ...]

the ends a nesting pair may have.

Type:

The problems, in binding order

property outermost_problems: tuple[N, ...]

Problems that are not nested in any other

enclosing(problem: N)

The problems problem is nested in transitively: A(q), every problem with a path from q in (N_P, W).

Return type:

tuple[N, ...]

cycle_of(problem: N)

The cycle problem is on, and itself: its strongly connected component in the graph with the problems enclosing it taken out, in binding order.

S_p = {k ∊ N A(p) : k ~ p in N A(p)} (~ in the induced subgraph, not in G)

Return type:

tuple[N, ...]

interior(problem: N)

What one iteration of problem runs: its cycle with it taken out.

Return type:

Self

subgraph(keep: Iterable[N])

Keep only those nodes in keep, with their definitions and the edges among them, dropping pairs with one end not kept.

Return type:

Self

contract(blocks: tuple[tuple[N, ...], ...])

Each block of at least two nodes contracted into one Function at its first member’s place: reading what the block reads from outside, owning what it owns. Every pair with an end in a block is dropped, since a box is no problem. A pair outside keeps its cycle, since a contraction only adds paths, so nothing is re-asked.

Return type:

Self

class ProvedGraph[N: Label, V: Place](graph: NestingGraph[N, V])

Bases: Frozen, Generic[N, V]

Wraps a nesting graph and forwards the methods. Additional checks can be put on here.

graph: NestingGraph[N, V]

property definitions: Mapping[N, NodeDefinition[V]]

property nodes: tuple[N, ...]

property within: Mapping[N, N]

property problems: tuple[N, ...]

property outermost_problems: tuple[N, ...]

enclosing(problem: N)

Return type:

tuple[N, ...]

cycle_of(problem: N)

Return type:

tuple[N, ...]

interior(problem: N)

Return type:

NestingGraph[N, V]

subgraph(keep: Iterable[N])

Return type:

NestingGraph[N, V]

class Unbound(inner: Label, outer: Label)

Bases: Violation

inner: Label

outer: Label

template: AbstractClassVar[str] = 'nesting {inner!r} in {outer!r}: an end is not a node of this graph'

e.g. ‘output {place!r} is owned by both {other!r} and {node!r}’

Type:

Wording

class NotAProblem(nodes: tuple[Label, ...])

Bases: Violation

nodes: tuple[Label, ...]

template: AbstractClassVar[str] = '{nodes} determines nothing, so no iteration of it answers anything -- an end of a nesting is a problem: `Determine` it, naming the unknowns it fixes, or `Unnest` it first so the plan says the nesting went'

e.g. ‘output {place!r} is owned by both {other!r} and {node!r}’

Type:

Wording

class Unreachable(inner: Label, outer: Label)

Bases: Violation

inner: Label

outer: Label

template: AbstractClassVar[str] = '{inner!r} and {outer!r} are not on one cycle, so no iteration of the one re-runs the other and there is nothing for the nesting to mean -- `Unnest` it before cutting or rewiring the pair apart'

e.g. ‘output {place!r} is owned by both {other!r} and {node!r}’

Type:

Wording

class SelfNested(inner: Label)

Bases: Violation

inner: Label

template: AbstractClassVar[str] = '{inner!r} inside itself -- an iteration does not answer the problem it is'

e.g. ‘output {place!r} is owned by both {other!r} and {node!r}’

Type:

Wording

class NestingLoop(inner: Label, outer: Label, chain: tuple[Label, ...])

Bases: Violation

inner: Label

outer: Label

chain: tuple[Label, ...]

template: AbstractClassVar[str] = '{outer!r} is already answered inside {inner!r} ({chain}), so nesting the one in the other closes a loop -- nesting is a forest'

e.g. ‘output {place!r} is owned by both {other!r} and {node!r}’

Type:

Wording

class BlockTooSmall(block: tuple[Label, ...])

Bases: Violation

block: tuple[Label, ...]

template: AbstractClassVar[str] = 'block {block} is not two nodes -- a box contracts at least two into one'

e.g. ‘output {place!r} is owned by both {other!r} and {node!r}’

Type:

Wording

class NodeInTwoBlocks(nodes: tuple[Label, ...])

Bases: Violation

nodes: tuple[Label, ...]

template: AbstractClassVar[str] = '{nodes} each in two blocks -- a node is contracted into one box at most'

e.g. ‘output {place!r} is owned by both {other!r} and {node!r}’

Type:

Wording

class BoxOwnsNothing(block: tuple[Label, ...])

Bases: Violation

block: tuple[Label, ...]

template: AbstractClassVar[str] = 'block {block} owns nothing, so as one node it would compute nothing and be unreachable -- a box is a computation, so contract only what produces'

e.g. ‘output {place!r} is owned by both {other!r} and {node!r}’

Type:

Wording