Trees and Spaces

Trees

Tree dataclass

Bases: Generic[N, P, T]

Strategy Trees.

A strategy tree can be obtained by reifying a strategy computation (see reify). Its type parameters are: a type signature N, an associated inner policy type P, and a return type T.

Trees are immutable.

Attributes:

Name	Type	Description
node	N | Success[T]	The current node of the tree, which is either a success leaf or a node of type compatible with signature N.
child	Callable[[Value], Tree[N, P, T]]	A function that maps an action (i.e., a local value) to a child tree.
ref	GlobalNodePath	A global reference to the node.

Locality Invariant

Only local values can be used as actions (passed to child) or as arguments of parametric local spaces. A local value consists in an assembly of elements of local spaces (see Value). This invariant is enforced at runtime and it guarantees that a policy can always make progress at any given node without being provided additional context. It is also a key assumption for establishing the completeness of the demonstration language (i.e., a demonstration with a single run | success test can always be extracted from a successful run of an oracular program).

Source code in src/delphyne/core/trees.py

@dataclass(frozen=True)
class Tree(Generic[N, P, T]):
    """
    Strategy Trees.

    A strategy tree can be obtained by reifying a strategy computation
    (see `reify`). Its type parameters are: a type signature `N`, an
    associated inner policy type `P`, and a return type `T`.

    Trees are **immutable**.

    Attributes:
        node: The current node of the tree, which is either a success
            leaf or a node of type compatible with signature `N`.
        child: A function that maps an action (i.e., a local value) to a
            child tree.
        ref: A global reference to the node.

    !!! info "Locality Invariant"
        Only *local values* can be used as actions (passed to `child`)
        or as arguments of parametric local spaces. A *local value*
        consists in an assembly of elements of local spaces (see
        `Value`). This invariant is enforced at runtime and it
        guarantees that a policy can always make progress at any given
        node without being provided additional context. It is also a key
        assumption for establishing the completeness of the
        demonstration language (i.e., a demonstration with a single `run
        | success` test can always be extracted from a successful run of
        an oracular program).
    """

    node: "N | Success[T]"
    child: "Callable[[Value], Tree[N, P, T]]"
    ref: GlobalNodePath

    def transform[M: Node](
        self,
        node: "M | Success[T]",
        transformer: "AbstractTreeTransformer[N, M]",
    ) -> "Tree[M, P, T]":
        """
        Recursively apply a function to all embedded trees and subtrees
        of a tree.

        This is a pure method that does not modify its arguments. It is
        useful to implement tree transformers such as `elim_compute`.
        """

        def child(action: Value) -> Tree[M, P, T]:
            return transformer(self.child(action))

        node = node.map_embedded(transformer)
        return Tree(node, child, self.ref)

transform

transform(
    node: M | Success[T], transformer: AbstractTreeTransformer[N, M]
) -> Tree[M, P, T]

Recursively apply a function to all embedded trees and subtrees of a tree.

This is a pure method that does not modify its arguments. It is useful to implement tree transformers such as elim_compute.

Source code in src/delphyne/core/trees.py

def transform[M: Node](
    self,
    node: "M | Success[T]",
    transformer: "AbstractTreeTransformer[N, M]",
) -> "Tree[M, P, T]":
    """
    Recursively apply a function to all embedded trees and subtrees
    of a tree.

    This is a pure method that does not modify its arguments. It is
    useful to implement tree transformers such as `elim_compute`.
    """

    def child(action: Value) -> Tree[M, P, T]:
        return transformer(self.child(action))

    node = node.map_embedded(transformer)
    return Tree(node, child, self.ref)

Success dataclass

A success leaf, carrying a tracked value.

Implementation Note

Although it largely implements the same interface via duck typing, Success does not inherit Node. The reason is that Tree[N, P, T].node has type Success[T] | N. If Success inherited Node, it would be possible for N to include a value of type Success[T2] for some T2 != T, which we want to rule out.

Source code in src/delphyne/core/trees.py

@dataclass(frozen=True)
class Success[T]:
    """
    A success leaf, carrying a tracked value.

    ??? note "Implementation Note"
        Although it largely implements the same interface via duck
        typing, `Success` does not inherit `Node`. The reason is that
        `Tree[N, P, T].node` has type `Success[T] | N`. If `Success`
        inherited `Node`, it would be possible for `N` to include a
        value of type `Success[T2]` for some `T2 != T`, which we want to
        rule out.
    """

    success: Tracked[T]

    def leaf_node(self) -> bool:
        return True

    def valid_action(self, action: object) -> bool:
        return False

    def navigate(self) -> Navigation:
        assert False

    def summary_message(self) -> str | None:
        return None

    def primary_space(self) -> None:
        return None

    def primary_space_ref(self) -> None:
        return None

    def effect_name(self) -> str:
        return self.__class__.__name__

    def get_tags(self) -> Sequence[Tag]:
        return ()

    def nested_space(
        self, name: refs.SpaceName, args: tuple[Value, ...]
    ) -> Space[Any] | None:
        return None

    def map_embedded(
        self, trans: "AbstractTreeTransformer[Any, Any]"
    ) -> "Success[T]":
        return self

Node

Bases: ABC

Abstract type for a tree node.

New effects can be added to the strategy language by subclassing Node and then defining a triggering function that calls the spawn class method (manually defining such a wrapper allows providing users with precise type annotations: i.e., branch for Branch).

Methods to override:

• The navigate method must be overriden for all node types.
• The leaf_node method must be overriden for all leaf nodes.
• The following methods are also frequently overriden: summary_message, valid_action, primary_space, and get_extra_tags.

Other methods are implemented via inspection and are not typically overriden.

On the absence of type parameters

In order to precisely type the fields of node subclasses (e.g. Branch), Node would need to have type parameters standing for the surrounding inner policy type, the action type, etc. However, Python's type system is not expressive enough to properly constrain such type parameters in the definition of trees since it lacks GADTs and higher-kinded types. In particular, the way we express signatures as unions of subtypes of Node would not work if Node were parametric.

As a result, types such as inner policy types and action types must be represented using Any in the definition of nodes (e.g. Branch) and the type safety of search policy implementations (e.g. dfs) cannot be fully enforced statically. However, effect triggering functions such as branch can typically be typed precisely, providing static type safety for strategy writers.

Source code in src/delphyne/core/trees.py

class Node(ABC):
    """
    Abstract type for a tree node.

    New effects can be added to the strategy language by subclassing
    `Node` and then defining a triggering function that calls the
    `spawn` class method (manually defining such a wrapper allows
    providing users with precise type annotations: i.e., `branch` for
    `Branch`).

    **Methods to override:**

    - The `navigate` method must be overriden for all node types.
    - The `leaf_node` method must be overriden for all leaf nodes.
    - The following methods are also frequently overriden:
        `summary_message`, `valid_action`, `primary_space`, and
        `get_extra_tags`.

    Other methods are implemented via inspection and are not typically
    overriden.

    ??? note "On the absence of type parameters"
        In order to precisely type the fields of node subclasses (e.g.
        `Branch`), `Node` would need to have type parameters standing
        for the surrounding inner policy type, the action type, etc.
        However, Python's type system is not expressive enough to
        properly constrain such type parameters in the definition of
        trees since it lacks GADTs and higher-kinded types. In
        particular, the way we express signatures as unions of subtypes
        of `Node` would not work if `Node` were parametric.

        As a result, types such as inner policy types and action types
        must be represented using `Any` in the definition of nodes (e.g.
        `Branch`) and the type safety of search policy implementations
        (e.g. `dfs`) cannot be fully enforced statically. However,
        effect *triggering functions* such as `branch` can typically be
        typed precisely, providing static type safety for strategy
        writers.
    """

    # Methods that **must** be overriden

    @abstractmethod
    def navigate(self) -> "Navigation":
        """
        The navigation method, to be defined for each node type.

        It should only be called when `self.leaf_node()` returns False.

        See `Navigation` for details.
        """
        pass

    # Methods that are _sometimes_ overriden

    def summary_message(self) -> str | None:
        """
        Return an optional summary message for the node, to be
        displayed in the Delphyne extension's Tree View.
        """
        return None

    def leaf_node(self) -> bool:
        """
        Return True if the node is a leaf node (e.g., `Fail`) and False
        otherwise.

        Leaf nodes do not have to define `navigate` and are treated
        specially by the demonstration interpreter.
        """
        return False

    def valid_action(self, action: object) -> bool:
        """
        Return whether an action is valid.

        This method is used to dynamically check actions passed to
        `Tree.child`, **after** the `Tracked` wrapper is removed. By
        default, it always returns `True` (unless the node is a leaf
        node, in which case it returns `False`).
        """
        return False if self.leaf_node() else True

    def primary_space(self) -> "Space[object] | None":
        """
        Optionally return the node's primary space.

        Primary spaces are useful to shorten space references,
        especially when writing demonstration tests. For example, if
        `cands` is the primary space of the current node, then
        `compare([cands{''}, cands{'foo bar'}])` can be abbreviated into
        `compare(['', 'foo bar'])`.

        By default, all tags of a node's primary space are also
        inherited by this node (see `get_tags` method).
        """
        return None

    def get_extra_tags(self) -> Sequence[Tag]:
        """
        Return the extra tags associated with the node, in addition to
        the default ones inherited from the primary space (see
        `get_tags` method).
        """
        return []

    # Inspecting the kinds of node fields

    @classmethod
    def fields(cls) -> NodeFields:
        """
        Return a dictionary mapping each field of the node to some
        metadata (e.g., whether the field denotes a local space).

        Such metadata is useful in particular to implement `spawn`.

        The default implementation uses inspection, via
        `detect_node_structure`. See the
        [`node_fields`][delphyne.core.node_fields] module for details.
        """
        f = detect_node_structure(
            cls, embedded_class=EmbeddedTree, space_class=Space
        )
        if f is None:
            msg = f"Impossible to autodetect the structure of {cls}"
            assert False, msg
        return f

    # Methods with a sensible default behavior that are _rarely_ overriden

    def effect_name(self) -> str:
        """
        Name of the associated effect.

        Used for generating message errors and in the VSCode extension.
        """
        return self.__class__.__name__

    def get_tags(self) -> Sequence[Tag]:
        """
        Return all tags attached to the node.

        Tags are leveraged by the demonstration language to identify
        nodes (e.g., `at` test command).

        By default, this method returns all tags from the primary space
        (if any), along with any additional tag returned by
        `get_extra_tags`.
        """
        if (primary := self.primary_space()) is not None:
            return [*primary.tags(), *self.get_extra_tags()]
        return self.get_extra_tags()

    # Methods that should not be overriden

    @final
    def primary_space_ref(self) -> refs.SpaceRef | None:
        """
        Convenience method for returning a reference to the node's
        primary space, if it is defined.
        """
        space = self.primary_space()
        if space is None:
            return None
        return space.source().ref[1]

    @final
    def nested_space(
        self, name: refs.SpaceName, args: tuple[Value, ...]
    ) -> Space[Any] | None:
        """
        Dynamically retrieve a local space given its name and
        parameters.

        For nonparametric spaces, `args` should be the empty tuple.

        This method is used by the demonstration interpreter.
        """
        try:
            f: Any = getattr(self, name.name)
            for i in name.indices:
                f = f[i]
            if not args:
                # TODO: we could check that the field is not supposed to be
                # parametric
                assert isinstance(f, Space)
                return cast(Space[Any], f)
            else:
                assert isinstance(f, Callable)
                f = cast(Callable[..., Space[Any]], f)
                return f(*args)
        except (TypeError, AttributeError):
            return None

    @final
    @classmethod
    def spawn(cls, spawner: "AbstractBuilderExecutor", **args: Any):
        """
        Spawn an instance of the node type, using a dictionary of
        arguments to populate its fields.

        Arguments are processed according to their kind (see
        [delphyne.core.node_fields][]). For example opaque space
        builders (`Opaque`) are turned into opaque spaces
        (`OpaqueSpace`) and strategy computations (`StrategyComp`) are
        turned into embedded trees (`EmbeddedTree`).
        """

        def convert(
            name: refs.SpaceName, field: nf.FieldKind, obj: Any
        ) -> Any:
            match field:
                case nf.SpaceF():
                    return spawner.nonparametric(name, obj)
                case nf.ParametricF(nf.SpaceF()):
                    return spawner.parametric(name, obj)
                case nf.EmbeddedF():
                    builder = EmbeddedTree.builder(obj)
                    return spawner.nonparametric(name, builder)
                case nf.ParametricF(nf.EmbeddedF()):
                    parametric_builder = EmbeddedTree.parametric_builder(obj)
                    return spawner.parametric(name, parametric_builder)
                case nf.DataF():
                    return obj
                case nf.SequenceF(f):
                    return [convert(name[i], f, x) for i, x in enumerate(obj)]
                case nf.OptionalF(f):
                    assert convert(name, f, obj) if obj is not None else None
                case _:
                    assert False

        args_new = {
            fname: convert(refs.SpaceName(fname, ()), fkind, args[fname])
            for fname, fkind in cls.fields().items()
        }
        return cls(**args_new)

    @final
    def map_embedded[N: Node](
        self: N, trans: "AbstractTreeTransformer[Any, Any]"
    ) -> N:
        """
        Apply a function to all embedded trees.

        This is a pure method that returns an updated node. It is useful
        for implementing `Tree.transform`, which in turn is useful for
        implementing standard tree transformers such as `elim_join` and
        `elim_compute`.
        """

        def convert_embedded(
            emb: EmbeddedTree[Any, Any, Any],
        ) -> EmbeddedTree[Any, Any, Any]:
            assert isinstance(emb, EmbeddedTree), (
                f"Expected an EmbeddedTree, got {type(emb)}"
            )
            nested = NestedTree(
                strategy=emb.nested.strategy,
                ref=emb.nested.ref,
                spawn_tree=lambda: trans(emb.nested.spawn_tree()),
            )
            return EmbeddedTree(nested, _tags=emb.tags())

        def convert_parametric_embedded(obj: Any) -> Callable[[Any], Any]:
            return lambda arg: convert_embedded(obj(arg))

        def convert(field: nf.FieldKind, obj: Any) -> Any:
            match field:
                case nf.SpaceF() | nf.ParametricF(nf.SpaceF()) | nf.DataF():
                    return obj
                case nf.EmbeddedF():
                    return convert_embedded(obj)
                case nf.ParametricF(nf.EmbeddedF()):
                    return convert_parametric_embedded(obj)
                case nf.SequenceF(f):
                    return [convert(f, x) for x in obj]
                case nf.OptionalF(f):
                    return convert(f, obj) if obj is not None else None
                case _:
                    assert False

        args_new = {
            fname: convert(fkind, getattr(self, fname))
            for fname, fkind in self.fields().items()
        }
        return type(self)(**args_new)

navigate abstractmethod

navigate() -> Navigation

The navigation method, to be defined for each node type.

It should only be called when self.leaf_node() returns False.

See Navigation for details.

Source code in src/delphyne/core/trees.py

@abstractmethod
def navigate(self) -> "Navigation":
    """
    The navigation method, to be defined for each node type.

    It should only be called when `self.leaf_node()` returns False.

    See `Navigation` for details.
    """
    pass

summary_message

summary_message() -> str | None

Return an optional summary message for the node, to be displayed in the Delphyne extension's Tree View.

Source code in src/delphyne/core/trees.py

def summary_message(self) -> str | None:
    """
    Return an optional summary message for the node, to be
    displayed in the Delphyne extension's Tree View.
    """
    return None

leaf_node

leaf_node() -> bool

Return True if the node is a leaf node (e.g., Fail) and False otherwise.

Leaf nodes do not have to define navigate and are treated specially by the demonstration interpreter.

Source code in src/delphyne/core/trees.py

def leaf_node(self) -> bool:
    """
    Return True if the node is a leaf node (e.g., `Fail`) and False
    otherwise.

    Leaf nodes do not have to define `navigate` and are treated
    specially by the demonstration interpreter.
    """
    return False

valid_action

valid_action(action: object) -> bool

Return whether an action is valid.

This method is used to dynamically check actions passed to Tree.child, after the Tracked wrapper is removed. By default, it always returns True (unless the node is a leaf node, in which case it returns False).

Source code in src/delphyne/core/trees.py

def valid_action(self, action: object) -> bool:
    """
    Return whether an action is valid.

    This method is used to dynamically check actions passed to
    `Tree.child`, **after** the `Tracked` wrapper is removed. By
    default, it always returns `True` (unless the node is a leaf
    node, in which case it returns `False`).
    """
    return False if self.leaf_node() else True

primary_space

primary_space() -> Space[object] | None

Optionally return the node's primary space.

Primary spaces are useful to shorten space references, especially when writing demonstration tests. For example, if cands is the primary space of the current node, then compare([cands{''}, cands{'foo bar'}]) can be abbreviated into compare(['', 'foo bar']).

By default, all tags of a node's primary space are also inherited by this node (see get_tags method).

Source code in src/delphyne/core/trees.py

def primary_space(self) -> "Space[object] | None":
    """
    Optionally return the node's primary space.

    Primary spaces are useful to shorten space references,
    especially when writing demonstration tests. For example, if
    `cands` is the primary space of the current node, then
    `compare([cands{''}, cands{'foo bar'}])` can be abbreviated into
    `compare(['', 'foo bar'])`.

    By default, all tags of a node's primary space are also
    inherited by this node (see `get_tags` method).
    """
    return None

get_extra_tags

get_extra_tags() -> Sequence[Tag]

Return the extra tags associated with the node, in addition to the default ones inherited from the primary space (see get_tags method).

Source code in src/delphyne/core/trees.py

def get_extra_tags(self) -> Sequence[Tag]:
    """
    Return the extra tags associated with the node, in addition to
    the default ones inherited from the primary space (see
    `get_tags` method).
    """
    return []

fields classmethod

fields() -> NodeFields

Return a dictionary mapping each field of the node to some metadata (e.g., whether the field denotes a local space).

Such metadata is useful in particular to implement spawn.

The default implementation uses inspection, via detect_node_structure. See the node_fields module for details.

Source code in src/delphyne/core/trees.py

@classmethod
def fields(cls) -> NodeFields:
    """
    Return a dictionary mapping each field of the node to some
    metadata (e.g., whether the field denotes a local space).

    Such metadata is useful in particular to implement `spawn`.

    The default implementation uses inspection, via
    `detect_node_structure`. See the
    [`node_fields`][delphyne.core.node_fields] module for details.
    """
    f = detect_node_structure(
        cls, embedded_class=EmbeddedTree, space_class=Space
    )
    if f is None:
        msg = f"Impossible to autodetect the structure of {cls}"
        assert False, msg
    return f

effect_name

effect_name() -> str

Name of the associated effect.

Used for generating message errors and in the VSCode extension.

Source code in src/delphyne/core/trees.py

def effect_name(self) -> str:
    """
    Name of the associated effect.

    Used for generating message errors and in the VSCode extension.
    """
    return self.__class__.__name__

get_tags

get_tags() -> Sequence[Tag]

Return all tags attached to the node.

Tags are leveraged by the demonstration language to identify nodes (e.g., at test command).

By default, this method returns all tags from the primary space (if any), along with any additional tag returned by get_extra_tags.

Source code in src/delphyne/core/trees.py

def get_tags(self) -> Sequence[Tag]:
    """
    Return all tags attached to the node.

    Tags are leveraged by the demonstration language to identify
    nodes (e.g., `at` test command).

    By default, this method returns all tags from the primary space
    (if any), along with any additional tag returned by
    `get_extra_tags`.
    """
    if (primary := self.primary_space()) is not None:
        return [*primary.tags(), *self.get_extra_tags()]
    return self.get_extra_tags()

primary_space_ref

primary_space_ref() -> SpaceRef | None

Convenience method for returning a reference to the node's primary space, if it is defined.

Source code in src/delphyne/core/trees.py

@final
def primary_space_ref(self) -> refs.SpaceRef | None:
    """
    Convenience method for returning a reference to the node's
    primary space, if it is defined.
    """
    space = self.primary_space()
    if space is None:
        return None
    return space.source().ref[1]

nested_space

nested_space(name: SpaceName, args: tuple[Value, ...]) -> Space[Any] | None

Dynamically retrieve a local space given its name and parameters.

For nonparametric spaces, args should be the empty tuple.

This method is used by the demonstration interpreter.

Source code in src/delphyne/core/trees.py

@final
def nested_space(
    self, name: refs.SpaceName, args: tuple[Value, ...]
) -> Space[Any] | None:
    """
    Dynamically retrieve a local space given its name and
    parameters.

    For nonparametric spaces, `args` should be the empty tuple.

    This method is used by the demonstration interpreter.
    """
    try:
        f: Any = getattr(self, name.name)
        for i in name.indices:
            f = f[i]
        if not args:
            # TODO: we could check that the field is not supposed to be
            # parametric
            assert isinstance(f, Space)
            return cast(Space[Any], f)
        else:
            assert isinstance(f, Callable)
            f = cast(Callable[..., Space[Any]], f)
            return f(*args)
    except (TypeError, AttributeError):
        return None

spawn classmethod

spawn(spawner: AbstractBuilderExecutor, **args: Any)

Spawn an instance of the node type, using a dictionary of arguments to populate its fields.

Arguments are processed according to their kind (see delphyne.core.node_fields). For example opaque space builders (Opaque) are turned into opaque spaces (OpaqueSpace) and strategy computations (StrategyComp) are turned into embedded trees (EmbeddedTree).

Source code in src/delphyne/core/trees.py

@final
@classmethod
def spawn(cls, spawner: "AbstractBuilderExecutor", **args: Any):
    """
    Spawn an instance of the node type, using a dictionary of
    arguments to populate its fields.

    Arguments are processed according to their kind (see
    [delphyne.core.node_fields][]). For example opaque space
    builders (`Opaque`) are turned into opaque spaces
    (`OpaqueSpace`) and strategy computations (`StrategyComp`) are
    turned into embedded trees (`EmbeddedTree`).
    """

    def convert(
        name: refs.SpaceName, field: nf.FieldKind, obj: Any
    ) -> Any:
        match field:
            case nf.SpaceF():
                return spawner.nonparametric(name, obj)
            case nf.ParametricF(nf.SpaceF()):
                return spawner.parametric(name, obj)
            case nf.EmbeddedF():
                builder = EmbeddedTree.builder(obj)
                return spawner.nonparametric(name, builder)
            case nf.ParametricF(nf.EmbeddedF()):
                parametric_builder = EmbeddedTree.parametric_builder(obj)
                return spawner.parametric(name, parametric_builder)
            case nf.DataF():
                return obj
            case nf.SequenceF(f):
                return [convert(name[i], f, x) for i, x in enumerate(obj)]
            case nf.OptionalF(f):
                assert convert(name, f, obj) if obj is not None else None
            case _:
                assert False

    args_new = {
        fname: convert(refs.SpaceName(fname, ()), fkind, args[fname])
        for fname, fkind in cls.fields().items()
    }
    return cls(**args_new)

map_embedded

map_embedded(trans: AbstractTreeTransformer[Any, Any]) -> N

Apply a function to all embedded trees.

This is a pure method that returns an updated node. It is useful for implementing Tree.transform, which in turn is useful for implementing standard tree transformers such as elim_join and elim_compute.

Source code in src/delphyne/core/trees.py

@final
def map_embedded[N: Node](
    self: N, trans: "AbstractTreeTransformer[Any, Any]"
) -> N:
    """
    Apply a function to all embedded trees.

    This is a pure method that returns an updated node. It is useful
    for implementing `Tree.transform`, which in turn is useful for
    implementing standard tree transformers such as `elim_join` and
    `elim_compute`.
    """

    def convert_embedded(
        emb: EmbeddedTree[Any, Any, Any],
    ) -> EmbeddedTree[Any, Any, Any]:
        assert isinstance(emb, EmbeddedTree), (
            f"Expected an EmbeddedTree, got {type(emb)}"
        )
        nested = NestedTree(
            strategy=emb.nested.strategy,
            ref=emb.nested.ref,
            spawn_tree=lambda: trans(emb.nested.spawn_tree()),
        )
        return EmbeddedTree(nested, _tags=emb.tags())

    def convert_parametric_embedded(obj: Any) -> Callable[[Any], Any]:
        return lambda arg: convert_embedded(obj(arg))

    def convert(field: nf.FieldKind, obj: Any) -> Any:
        match field:
            case nf.SpaceF() | nf.ParametricF(nf.SpaceF()) | nf.DataF():
                return obj
            case nf.EmbeddedF():
                return convert_embedded(obj)
            case nf.ParametricF(nf.EmbeddedF()):
                return convert_parametric_embedded(obj)
            case nf.SequenceF(f):
                return [convert(f, x) for x in obj]
            case nf.OptionalF(f):
                return convert(f, obj) if obj is not None else None
            case _:
                assert False

    args_new = {
        fname: convert(fkind, getattr(self, fname))
        for fname, fkind in self.fields().items()
    }
    return type(self)(**args_new)

Navigation

Navigation: Generator[Space[Any], Tracked[Any], Value]

A navigation generator.

A navigation generator is returned by the navigate method of non-leaf nodes. It yields local spaces and receives corresponding elements until an action is generated and returned.

NavigationError dataclass

Bases: Exception

Exception raised when an error occurs during navigation.

For internal errors that should not occur within normal use, assertions shoule be used instead. This exception is meant to represent errors that can occur during normal use, and reported in the user interface. For an example, see Abduction.

Attributes:

Name	Type	Description
message	str	A human-readable error message.

Source code in src/delphyne/core/trees.py

@dataclass(frozen=True)
class NavigationError(Exception):
    """
    Exception raised when an error occurs during navigation.

    For internal errors that should not occur within normal use,
    assertions shoule be used instead. This exception is meant to
    represent errors that can occur during normal use, and reported in
    the user interface. For an example, see `Abduction`.

    Attributes:
        message: A human-readable error message.
    """

    message: str

Node Fields

delphyne.core.node_fields

Classifying and inferring different kinds of node fields.

When spawning a node via Tree.spawn, different field arguments must be processed differently. For example, an opaque space builder (Opaque) must be turned into an opaque space (OpaqueSpace) by providing an appropriate space reference. Other fields such as data fields must not be processed.

This module defines a type for classifying node fields (FieldType) along with a utility function to automatically classify the fields of a custom node via inspection (detect_node_structure).

NodeFields

NodeFields: dict[str, FieldKind]

A dictionary mapping each field name to its kind.

FieldKind

FieldKind: LeafFieldKind | SequenceF | OptionalF

Kind of a node field.

A node field can be an embedded tree, another local space, a parametric embedded tree or space, a sequence of such elements or an optional element.

FieldKind

FieldKind: LeafFieldKind | SequenceF | OptionalF

Kind of a node field.

A node field can be an embedded tree, another local space, a parametric embedded tree or space, a sequence of such elements or an optional element.

LeafFieldKind

LeafFieldKind: SpaceF | EmbeddedF | DataF | ParametricF

SpaceF dataclass

A space field that does not correspond to an embedded nested tree.

Source code in src/delphyne/core/node_fields.py

@dataclass
class SpaceF:
    """
    A space field that does not correspond to an embedded nested tree.
    """

EmbeddedF dataclass

A field corresponding to a nested embedded space.

Recognizing this particular case is useful so that triggering functions can directly accept strategy computations as arguments (StrategyComp) instead of space builders (SpaceBuilder).

Source code in src/delphyne/core/node_fields.py

@dataclass
class EmbeddedF:
    """
    A field corresponding to a nested embedded space.

    Recognizing this particular case is useful so that triggering
    functions can directly accept strategy computations as arguments
    (`StrategyComp`) instead of space builders (`SpaceBuilder`).
    """

ParametricF dataclass

A field corresponding to a parametric space.

Attributes:

Name	Type	Description
res	SpaceF | EmbeddedF	kind of the result space.

Source code in src/delphyne/core/node_fields.py

@dataclass
class ParametricF:
    """
    A field corresponding to a parametric space.

    Attributes:
        res: kind of the result space.
    """

    res: SpaceF | EmbeddedF

DataF dataclass

A field that corresponds to some other kind of data.

Source code in src/delphyne/core/node_fields.py

@dataclass
class DataF:
    """
    A field that corresponds to some other kind of data.
    """

SequenceF dataclass

A field corresponding to a sequence of spaces.

Source code in src/delphyne/core/node_fields.py

@dataclass
class SequenceF:
    """
    A field corresponding to a sequence of spaces.
    """

    element: "FieldKind"

OptionalF dataclass

A field corresponding to a sequence of spaces.

Source code in src/delphyne/core/node_fields.py

@dataclass
class OptionalF:
    """
    A field corresponding to a sequence of spaces.
    """

    element: "FieldKind"

Spaces

Space

Bases: ABC

Abstract type for a space.

Tree nodes feature local spaces (possibly parametric), that are backed by either queries or nested trees. Examples of spaces include EmbeddedTree, OpaqueSpace and TransparentQuery.

Source code in src/delphyne/core/trees.py

class Space[T](ABC):
    """
    Abstract type for a space.

    Tree nodes feature local spaces (possibly parametric), that are
    backed by either queries or nested trees. Examples of spaces
    include `EmbeddedTree`, `OpaqueSpace` and `TransparentQuery`.
    """

    @abstractmethod
    def tags(self) -> Sequence[Tag]:
        """
        Return the tags associated with the space.
        """
        pass

    @abstractmethod
    def source(self) -> "NestedTree[Any, Any, T] | AttachedQuery[T]":
        """
        Return the source of the space, which is either a nested tree
        or an attached query.

        This method is mostly useful to the demonstration interpreter.
        It is not typically used in policies since it breaks
        abstraction (e.g., whether or not an opaque space is defined via
        a query or a strategy is irrelevant).
        """
        pass

tags abstractmethod

tags() -> Sequence[Tag]

Return the tags associated with the space.

Source code in src/delphyne/core/trees.py

@abstractmethod
def tags(self) -> Sequence[Tag]:
    """
    Return the tags associated with the space.
    """
    pass

source abstractmethod

source() -> NestedTree[Any, Any, T] | AttachedQuery[T]

Return the source of the space, which is either a nested tree or an attached query.

This method is mostly useful to the demonstration interpreter. It is not typically used in policies since it breaks abstraction (e.g., whether or not an opaque space is defined via a query or a strategy is irrelevant).

Source code in src/delphyne/core/trees.py

@abstractmethod
def source(self) -> "NestedTree[Any, Any, T] | AttachedQuery[T]":
    """
    Return the source of the space, which is either a nested tree
    or an attached query.

    This method is mostly useful to the demonstration interpreter.
    It is not typically used in policies since it breaks
    abstraction (e.g., whether or not an opaque space is defined via
    a query or a strategy is irrelevant).
    """
    pass

Tag

Tag: str

String tags for nodes and spaces.

Nodes and spaces can be assigned string identifiers, which may be referenced in demonstration tests or when defining inner policies (e.g., IPDict). Tags should contain only alphanumeric characters, underscores, dots, and dashes.

AttachedQuery dataclass

Wrapper for a query attached to a specific space.

Attributes:

Name	Type	Description
query	AbstractQuery[T]	The wrapped query.
ref	GlobalSpacePath	A global reference to the space to which the query is attached.
parse_answer	Callable[[Answer], Tracked[T] | ParseError]	A wrapper around self.query.parse_answer, which attaches proper tracking information to answers.

Source code in src/delphyne/core/trees.py

@dataclass(frozen=True)
class AttachedQuery[T]:
    """
    Wrapper for a query attached to a specific space.

    Attributes:
        query: The wrapped query.
        ref: A global reference to the space to which the query is
            attached.
        parse_answer: A wrapper around `self.query.parse_answer`,
            which attaches proper tracking information to answers.
    """

    query: AbstractQuery[T]
    ref: refs.GlobalSpacePath
    parse_answer: Callable[[refs.Answer], Tracked[T] | ParseError]

NestedTree dataclass

Wrapper for a tree attached to a particular node.

The AttachedQuery type plays an equivalent role for queries.

Note

One cannot count on the strategy field having the same node type as spawn_tree since nested trees can be applied tree transformers (see Node.map_embedded).

Source code in src/delphyne/core/trees.py

@dataclass(frozen=True)
class NestedTree[N: Node, P, T]:
    """
    Wrapper for a tree attached to a particular node.

    The `AttachedQuery` type plays an equivalent role for queries.

    !!! note
        One cannot count on the `strategy` field having the same node
        type as `spawn_tree` since nested trees can be applied tree
        transformers (see `Node.map_embedded`).
    """

    strategy: StrategyComp[Node, P, T]
    ref: refs.GlobalSpacePath
    spawn_tree: "Callable[[], Tree[N, P, T]]"

TransparentQuery dataclass

Bases: Space[T]

A space that is defined by a single, transparent query.

As opposed to OpaqueSpace, the query is meant to be directly exposed to policies. This is used to define Compute and Flag nodes for example.

Source code in src/delphyne/core/trees.py

@dataclass(frozen=True)
class TransparentQuery[T](Space[T]):
    """
    A space that is defined by a single, *transparent* query.

    As opposed to `OpaqueSpace`, the query is meant to be directly
    exposed to policies. This is used to define `Compute` and `Flag`
    nodes for example.
    """

    attached: AttachedQuery[T]
    _tags: "Sequence[Tag]"

    @override
    def source(self) -> AttachedQuery[T]:
        return self.attached

    @override
    def tags(self) -> Sequence[Tag]:
        return self._tags

    @staticmethod
    def build[T1](
        query: AbstractQuery[T1],
    ) -> "SpaceBuilder[TransparentQuery[T1]]":
        return SpaceBuilder(
            build=lambda _, spawner, tags: TransparentQuery(
                spawner(query), tags
            ),
            tags=query.default_tags(),
        )

EmbeddedTree dataclass

Bases: Space[T]

Space defined by a nested tree with the same signature and inner policy as its surrounding tree.

This is useful to define effects such as Join.

Source code in src/delphyne/core/trees.py

@dataclass(frozen=True)
class EmbeddedTree[N: Node, P, T](Space[T]):
    """
    Space defined by a nested tree with the same signature and inner
    policy as its surrounding tree.

    This is useful to define effects such as `Join`.
    """

    nested: NestedTree[N, P, T]
    _tags: Sequence[Tag]

    @staticmethod
    def builder[N1: Node, P1, T1](
        strategy: StrategyComp[N1, P1, T1],
    ) -> "SpaceBuilder[EmbeddedTree[N1, P1, T1]]":
        return SpaceBuilder[EmbeddedTree[N1, P1, T1]](
            build=lambda spawn, _, tags: EmbeddedTree(spawn(strategy), tags),
            tags=strategy.default_tags(),
        )

    @staticmethod
    def parametric_builder[A, N1: Node, P1, T1](
        parametric_strategy: Callable[[A], StrategyComp[N1, P1, T1]],
    ) -> "Callable[[A], SpaceBuilder[EmbeddedTree[N1, P1, T1]]]":
        return lambda arg: EmbeddedTree.builder(parametric_strategy(arg))

    def source(self) -> "NestedTree[Any, Any, T]":
        return self.nested

    def tags(self) -> Sequence[Tag]:
        return self._tags

    def spawn_tree(self) -> "Tree[N, P, T]":
        return self.nested.spawn_tree()

SpaceBuilder dataclass

Wrapper for a function that builds a space, given the ability to spawn nested trees and attached queries.

Effect triggering functions such as branch do not directly take spaces as their arguments but space builders instead.

Space builders are also equipped with modifiable tags, to be ultimately passed to the resulting space.

Attributes:

Name	Type	Description
build	Callable[[NestedTreeSpawner, QuerySpawner, Sequence[Tag]], S]	Wrapped builder function
tags	Sequence[Tag]	Tags to be assocaited to the space.

Source code in src/delphyne/core/trees.py

@dataclass(frozen=True)
class SpaceBuilder[S]:
    """
    Wrapper for a function that builds a space, given the ability to
    spawn nested trees and attached queries.

    Effect triggering functions such as `branch` do not directly take
    spaces as their arguments but space builders instead.

    Space builders are also equipped with modifiable tags, to be
    ultimately passed to the resulting space.

    Attributes:
        build: Wrapped builder function
        tags: Tags to be assocaited to the space.
    """

    build: Callable[[NestedTreeSpawner, QuerySpawner, Sequence[Tag]], S]
    tags: Sequence[Tag]

    def tagged(self, *tags: Tag) -> "SpaceBuilder[S]":
        """
        Add new tags to the space builder.
        """
        return replace(self, tags=(*self.tags, *tags))

    def __call__(
        self, spawner: NestedTreeSpawner, query_spawner: QuerySpawner
    ) -> S:
        """
        Build a space, given the provided capabilities along with the
        current set of tags.
        """
        return self.build(spawner, query_spawner, self.tags)

tagged

tagged(*tags: Tag) -> SpaceBuilder[S]

Add new tags to the space builder.

Source code in src/delphyne/core/trees.py

def tagged(self, *tags: Tag) -> "SpaceBuilder[S]":
    """
    Add new tags to the space builder.
    """
    return replace(self, tags=(*self.tags, *tags))

__call__

__call__(spawner: NestedTreeSpawner, query_spawner: QuerySpawner) -> S

Build a space, given the provided capabilities along with the current set of tags.

Source code in src/delphyne/core/trees.py

def __call__(
    self, spawner: NestedTreeSpawner, query_spawner: QuerySpawner
) -> S:
    """
    Build a space, given the provided capabilities along with the
    current set of tags.
    """
    return self.build(spawner, query_spawner, self.tags)

Miscellaneous

ComputationNode

Bases: Node

Abstract type for computation nodes.

A computation node has an additional method that can be called to compute an answer. The demonstration interpreter uses this information to navigate computation nodes while accumulating implicit answers.

The standard Compute node inherits this class.

Source code in src/delphyne/core/trees.py

class ComputationNode(Node):
    """
    Abstract type for computation nodes.

    A computation node has an additional method that can be called to
    compute an _answer_. The demonstration interpreter uses this
    information to navigate computation nodes while accumulating
    implicit answers.

    The standard `Compute` node inherits this class.
    """

    @abstractmethod
    def run_computation(self) -> str:
        pass

AbstractTreeTransformer

Bases: Protocol

A function that transforms any tree with signature N into a tree with signature M, preserving its inner policy type and return type.

Source code in src/delphyne/core/trees.py

class AbstractTreeTransformer[N: Node, M: Node](Protocol):
    """
    A function that transforms any tree with signature N into a tree
    with signature M, preserving its inner policy type and return type.
    """

    def __call__[T, P](self, tree: "Tree[N, P, T]") -> "Tree[M, P, T]": ...