nodes

Aggregate dataclass

Bases: LogicTree, LogicExpression

Represents a logical AST statement that reduces arg using op, starting with init. idxs are the dimensions to reduce. May happen in any order. init may be a literal or a tensor expression. The fields of the result are those of arg which are not reduced, followed by the fields of init which are not in arg. init and arg are broadcast over the fields of the result which they lack, as in a MapJoin.

Attributes:

Name	Type	Description
op	Literal	The reduction operation.
init	LogicExpression	The initial value for the reduction.
arg	LogicExpression	The argument to reduce.
idxs	tuple[Field, ...]	The dimensions to reduce.

Source code in src/finch/finch_logic/nodes.py

@dataclass(eq=True, frozen=True)
class Aggregate(LogicTree, LogicExpression):
    """
    Represents a logical AST statement that reduces `arg` using `op`, starting
    with `init`. `idxs` are the dimensions to reduce. May happen in any order.
    `init` may be a literal or a tensor expression. The fields of the result
    are those of `arg` which are not reduced, followed by the fields of `init`
    which are not in `arg`. `init` and `arg` are broadcast over the fields of
    the result which they lack, as in a `MapJoin`.

    Attributes:
        op: The reduction operation.
        init: The initial value for the reduction.
        arg: The argument to reduce.
        idxs: The dimensions to reduce.
    """

    op: Literal
    init: LogicExpression
    arg: LogicExpression
    idxs: tuple[Field, ...]

    @property
    def children(self):
        """Returns the children of the node."""
        return [self.op, self.init, self.arg, *self.idxs]

    def fields(self) -> tuple[Field, ...]:
        """Returns fields of the node."""
        arg_fields = [field for field in self.arg.fields() if field not in self.idxs]
        return tuple(dict.fromkeys([*arg_fields, *self.init.fields()]))

    def dimmap(
        self,
        op: Callable,
        dim_bindings: dict[Alias, tuple[T | None, ...]],
    ) -> tuple[T | None, ...]:
        idxs = self.arg.fields()
        dims = self.arg.dimmap(op, dim_bindings)
        idx_dims = {
            idx: val
            for idx, val in zip(idxs, dims, strict=True)
            if idx not in self.idxs
        }
        init_dims = self.init.dimmap(op, dim_bindings)
        for idx, dim in zip(self.init.fields(), init_dims, strict=True):
            if idx in self.idxs:
                raise ValueError(f"The init of an aggregate can't have reduced {idx}")
            idx_dims[idx] = op(idx_dims[idx], dim) if idx in idx_dims else dim
        return tuple(idx_dims.values())

    def valmap(
        self,
        f: Callable,
        g: Callable,
        h: Callable,
        bindings: dict[Alias, T],
    ) -> T:
        return g(
            self.op.val,
            self.init.valmap(f, g, h, bindings),
            self.arg.valmap(f, g, h, bindings),
        )

    @classmethod
    def from_children(cls, op, init, arg, *idxs):
        return cls(op, init, arg, idxs)

children property

Returns the children of the node.

fields()

Returns fields of the node.

Source code in src/finch/finch_logic/nodes.py

def fields(self) -> tuple[Field, ...]:
    """Returns fields of the node."""
    arg_fields = [field for field in self.arg.fields() if field not in self.idxs]
    return tuple(dict.fromkeys([*arg_fields, *self.init.fields()]))

Alias dataclass

Bases: LogicNode, NamedTerm

Represents a logical AST expression for an alias named name. Aliases are used to refer to tables in the program.

Attributes:

Name	Type	Description
name	str	The name of the alias.

Source code in src/finch/finch_logic/nodes.py

@dataclass(eq=True, frozen=True)
class Alias(LogicNode, NamedTerm):
    """
    Represents a logical AST expression for an alias named `name`. Aliases are used to
    refer to tables in the program.

    Attributes:
        name: The name of the alias.
    """

    name: str

    @property
    def symbol(self) -> str:
        return self.name

    def fields(self) -> tuple[Field, ...]:
        """Returns fields of the node."""
        raise NotImplementedError(
            "Aliases do not have fields because they are tensors not tables!"
        )

    def dimmap(
        self,
        op: Callable,
        dim_bindings: dict[Alias, tuple[T | None, ...]],
    ) -> tuple[T | None, ...]:
        if dim_bindings is None or self not in dim_bindings:
            raise NotImplementedError(f"Cannot resolve dims of Alias {self.name}")
        return dim_bindings[self]

    def valmap(
        self,
        f: Callable,
        g: Callable,
        h: Callable,
        bindings: dict[Alias, T],
    ) -> T:
        if bindings is None or self not in bindings:
            raise NotImplementedError(f"Cannot resolve value of Alias {self.name}")
        return bindings[self]

fields()

Returns fields of the node.

Source code in src/finch/finch_logic/nodes.py

def fields(self) -> tuple[Field, ...]:
    """Returns fields of the node."""
    raise NotImplementedError(
        "Aliases do not have fields because they are tensors not tables!"
    )

Field dataclass

Bases: LogicNode, NamedTerm

Represents a logical AST expression for a field named name. Fields are used to name the dimensions of a tensor. The named tensor is referred to as a "table".

Attributes:

Name	Type	Description
name	str	The name of the field.

Source code in src/finch/finch_logic/nodes.py

@dataclass(eq=True, frozen=True)
class Field(LogicNode, NamedTerm):
    """
    Represents a logical AST expression for a field named `name`.
    Fields are used to name the dimensions of a tensor. The named
    tensor is referred to as a "table".

    Attributes:
        name: The name of the field.
    """

    name: str

    @property
    def symbol(self) -> str:
        return self.name

FillTable dataclass

Bases: LogicTree, LogicExpression

Represents a logical AST expression for the fill value of the tensor tns, as a zero-dimensional tensor. Like a literal, it has no fields, but its value is only known once tns is bound.

Attributes:

Name	Type	Description
tns	Alias	The alias of the tensor whose fill value is taken.

Source code in src/finch/finch_logic/nodes.py

@dataclass(eq=True, frozen=True)
class FillTable(LogicTree, LogicExpression):
    """
    Represents a logical AST expression for the fill value of the tensor `tns`,
    as a zero-dimensional tensor. Like a literal, it has no fields, but its
    value is only known once `tns` is bound.

    Attributes:
        tns: The alias of the tensor whose fill value is taken.
    """

    tns: Alias

    def fields(self) -> tuple[Field, ...]:
        """Returns fields of the node."""
        return ()

    def dimmap(
        self, op: Callable, dim_bindings: dict[Alias, tuple[T | None, ...]]
    ) -> tuple[T | None, ...]:
        return ()

    def valmap(
        self,
        f: Callable,
        g: Callable,
        h: Callable,
        bindings: dict[Alias, T],
    ) -> T:
        # The fill value of a tensor has the element type, fill value and fill
        # format of the tensor.
        return self.tns.valmap(f, g, h, bindings)

    @property
    def children(self):
        """Returns the children of the node."""
        return [self.tns]

    @classmethod
    def from_children(cls, tns):
        return cls(tns)

children property

Returns the children of the node.

fields()

Returns fields of the node.

Source code in src/finch/finch_logic/nodes.py

def fields(self) -> tuple[Field, ...]:
    """Returns fields of the node."""
    return ()

Literal dataclass

Bases: LogicExpression, LiteralTerm, ExpressionTerm

Represents a logical AST expression for the literal value val.

A literal behaves as a zero-dimensional tensor: it has no fields, and its element type and fill value are those of val itself.

Attributes:

Name	Type	Description
val	T	The literal value.

Source code in src/finch/finch_logic/nodes.py

@dataclass(eq=True, frozen=True)
class Literal(LogicExpression, LiteralTerm, ExpressionTerm):
    """
    Represents a logical AST expression for the literal value `val`.

    A literal behaves as a zero-dimensional tensor: it has no fields, and its
    element type and fill value are those of `val` itself.

    Attributes:
        val: The literal value.
    """

    @property
    def result_type(self) -> FType:
        return ftype(self.val)

    def __hash__(self):
        try:
            return hash((type(self.val), self.val))
        except TypeError:
            return hash(id(self.val))

    def __eq__(self, value):
        if not isinstance(value, Literal):
            return False
        if type(self.val) is not type(value.val):
            return False
        # For consistency with __hash__, we fall back to pointer equality
        # when the value is unhashable
        try:
            hash(value.val)
            hash(self.val)
            return self.val == value.val
        except TypeError:
            return id(self.val) == id(value.val)

    def __repr__(self) -> str:
        return literal_repr(type(self).__name__, {"val": self.val})

    def fields(self) -> tuple[Field, ...]:
        """Returns fields of the node."""
        return ()

    def dimmap(
        self,
        op: Callable,
        dim_bindings: dict[Alias, tuple[T | None, ...]],
    ) -> tuple[T | None, ...]:
        return ()

    def valmap(
        self,
        f: Callable,
        g: Callable,
        h: Callable,
        bindings: dict[Alias, T],
    ) -> T:
        # A literal is a scalar, so its fill value is itself.
        return h(StaticFill(self.val))

fields()

Returns fields of the node.

Source code in src/finch/finch_logic/nodes.py

def fields(self) -> tuple[Field, ...]:
    """Returns fields of the node."""
    return ()

LogicExpression dataclass

Bases: LogicNode

Logic AST expression base class.

A Logic expression is a program node which evaluates to a TableValue, a tensor with named dimensions.

Source code in src/finch/finch_logic/nodes.py

class LogicExpression(LogicNode):
    """
    Logic AST expression base class.

    A Logic expression is a program node which evaluates to a TableValue, a
    tensor with named dimensions.
    """

    @abstractmethod
    def fields(self) -> tuple[Field, ...]:
        """Returns fields of the node."""
        ...

    @abstractmethod
    def dimmap(
        self,
        op: Callable,
        dim_bindings: dict[Alias, tuple[T | None, ...]],
    ) -> tuple[T | None, ...]:
        """Compute per-dimension values, combining using `op`. When dimensions
        are expanded, None is used. When dimensions are contracted, the value
        is combined with None."""
        ...

    @abstractmethod
    def valmap(
        self,
        f: Callable,
        g: Callable,
        h: Callable,
        bindings: dict[Alias, T],
    ) -> T:
        """Compute per-tensor values. The value of an alias comes from
        `bindings`, and the value of a literal is `h(fill)` of its fill value.
        `f(op, args)` is used to combine values in mapjoin, and
        `g(op, init, arg)` is used to combine values in aggregation."""
        ...

    def shape_type(
        self,
        dim_bindings: dict[Alias, tuple[FType | None, ...]],
    ) -> tuple[FType | None, ...]:
        """Returns the shape type of the node."""
        return self.dimmap(merge_dim_type, dim_bindings)

    def shape(
        self,
        dim_bindings: dict[Alias, tuple[Any, ...]],
    ) -> tuple[Any, ...]:
        """Returns the shape of the node."""
        return self.dimmap(merge_dim, dim_bindings)

    def element_type(self, bindings: dict[Alias, FType]) -> FType:
        """Returns element type of the node."""
        return self.valmap(
            merge_element_type, reduce_element_type, literal_element_type, bindings
        )

    def fill_value(self, bindings: dict[Alias, AbstractFill]) -> AbstractFill:
        """Returns fill value of the node."""
        return self.valmap(apply_fill, reduce_fill_value, literal_fill_value, bindings)

    def fill_type(self, bindings: dict[Alias, AbstractFillFType]) -> AbstractFillFType:
        """Returns the fill of the node's format."""
        return self.valmap(
            apply_fill_type, reduce_fill_type, literal_fill_type, bindings
        )

dimmap(op, dim_bindings) abstractmethod

Compute per-dimension values, combining using op. When dimensions are expanded, None is used. When dimensions are contracted, the value is combined with None.

Source code in src/finch/finch_logic/nodes.py

@abstractmethod
def dimmap(
    self,
    op: Callable,
    dim_bindings: dict[Alias, tuple[T | None, ...]],
) -> tuple[T | None, ...]:
    """Compute per-dimension values, combining using `op`. When dimensions
    are expanded, None is used. When dimensions are contracted, the value
    is combined with None."""
    ...

element_type(bindings)

Returns element type of the node.

Source code in src/finch/finch_logic/nodes.py

def element_type(self, bindings: dict[Alias, FType]) -> FType:
    """Returns element type of the node."""
    return self.valmap(
        merge_element_type, reduce_element_type, literal_element_type, bindings
    )

fields() abstractmethod

Returns fields of the node.

Source code in src/finch/finch_logic/nodes.py

@abstractmethod
def fields(self) -> tuple[Field, ...]:
    """Returns fields of the node."""
    ...

fill_type(bindings)

Returns the fill of the node's format.

Source code in src/finch/finch_logic/nodes.py

def fill_type(self, bindings: dict[Alias, AbstractFillFType]) -> AbstractFillFType:
    """Returns the fill of the node's format."""
    return self.valmap(
        apply_fill_type, reduce_fill_type, literal_fill_type, bindings
    )

fill_value(bindings)

Returns fill value of the node.

Source code in src/finch/finch_logic/nodes.py

def fill_value(self, bindings: dict[Alias, AbstractFill]) -> AbstractFill:
    """Returns fill value of the node."""
    return self.valmap(apply_fill, reduce_fill_value, literal_fill_value, bindings)

shape(dim_bindings)

Returns the shape of the node.

Source code in src/finch/finch_logic/nodes.py

def shape(
    self,
    dim_bindings: dict[Alias, tuple[Any, ...]],
) -> tuple[Any, ...]:
    """Returns the shape of the node."""
    return self.dimmap(merge_dim, dim_bindings)

shape_type(dim_bindings)

Returns the shape type of the node.

Source code in src/finch/finch_logic/nodes.py

def shape_type(
    self,
    dim_bindings: dict[Alias, tuple[FType | None, ...]],
) -> tuple[FType | None, ...]:
    """Returns the shape type of the node."""
    return self.dimmap(merge_dim_type, dim_bindings)

valmap(f, g, h, bindings) abstractmethod

Compute per-tensor values. The value of an alias comes from bindings, and the value of a literal is h(fill) of its fill value. f(op, args) is used to combine values in mapjoin, and g(op, init, arg) is used to combine values in aggregation.

Source code in src/finch/finch_logic/nodes.py

@abstractmethod
def valmap(
    self,
    f: Callable,
    g: Callable,
    h: Callable,
    bindings: dict[Alias, T],
) -> T:
    """Compute per-tensor values. The value of an alias comes from
    `bindings`, and the value of a literal is `h(fill)` of its fill value.
    `f(op, args)` is used to combine values in mapjoin, and
    `g(op, init, arg)` is used to combine values in aggregation."""
    ...

LogicNode dataclass

Bases: Term, ABC

LogicNode

Represents a Finch Logic IR node. Finch uses a variant of Concrete Field Notation as an intermediate representation.

The LogicNode struct represents many different Finch IR nodes.

Source code in src/finch/finch_logic/nodes.py

@dataclass(eq=True, frozen=True)
class LogicNode(Term, ABC):
    """
    LogicNode

    Represents a Finch Logic IR node. Finch uses a variant of Concrete Field Notation
    as an intermediate representation.

    The LogicNode struct represents many different Finch IR nodes.
    """

    @classmethod
    def head(cls) -> Callable[..., Self]:
        """Returns the head of the node."""
        return cls

    @classmethod
    def make_term(cls, head, *children: Term) -> Self:
        return head.from_children(*children)

    @classmethod
    def from_children(cls, *children: Term) -> Self:
        return cls(*children)

    def __str__(self):
        """Returns a string representation of the node."""
        ctx = LogicPrinterContext()
        res = ctx(self)
        return res if res is not None else ctx.emit()

__str__()

Returns a string representation of the node.

Source code in src/finch/finch_logic/nodes.py

def __str__(self):
    """Returns a string representation of the node."""
    ctx = LogicPrinterContext()
    res = ctx(self)
    return res if res is not None else ctx.emit()

head() classmethod

Returns the head of the node.

Source code in src/finch/finch_logic/nodes.py

@classmethod
def head(cls) -> Callable[..., Self]:
    """Returns the head of the node."""
    return cls

LogicStatement dataclass

Bases: LogicNode

Logic AST statement base class.

A Logic statement may modify the state of the machine by assigning tensors to Aliases.

Logic statements evaluate to a tuple of tensors.

Source code in src/finch/finch_logic/nodes.py

class LogicStatement(LogicNode):
    """
    Logic AST statement base class.

    A Logic statement may modify the state of the machine by assigning tensors
    to Aliases.

    Logic statements evaluate to a tuple of tensors.
    """

    @abstractmethod
    def infer_dimmap(
        self,
        op: Callable,
        dim_bindings: dict[Alias, tuple[T | None, ...]],
    ) -> dict[Alias, tuple[T | None, ...]]:
        """Infers dimmaps for all aliases defined in the statement. The results
        will be stored in the dictionary passed to the method."""
        ...

    @abstractmethod
    def infer_valmap(
        self,
        f: Callable,
        g: Callable,
        h: Callable,
        bindings: dict[Alias, T],
    ) -> dict[Alias, T]:
        """Infers valmaps for all aliases defined in the statement. The results
        will be stored in the dictionary passed to the method."""
        ...

    def infer_shape_type(
        self,
        dim_bindings: dict[Alias, tuple[FType | None, ...]],
    ) -> dict[Alias, tuple[FType | None, ...]]:
        """Infers shape_type for all aliases defined in the statement. The results
        will be stored in the dictionary passed to the method."""
        return self.infer_dimmap(merge_dim_type, dim_bindings)

    def infer_shape(
        self,
        dim_bindings: dict[Alias, tuple[Any, ...]],
    ) -> dict[Alias, tuple[Any, ...]]:
        """Infers shapes for all aliases defined in the statement. The results
        will be stored in the dictionary passed to the method."""
        return self.infer_dimmap(merge_dim, dim_bindings)

    def infer_element_type(self, bindings: dict[Alias, FType]) -> dict[Alias, FType]:
        """Infers element types for all aliases defined in the statement. The results
        will be stored in the dictionary passed to the method."""
        return self.infer_valmap(
            merge_element_type, reduce_element_type, literal_element_type, bindings
        )

    def infer_fill_value(
        self, bindings: dict[Alias, AbstractFill]
    ) -> dict[Alias, AbstractFill]:
        """Infers fill_values for all aliases defined in the statement. The results
        will be stored in the dictionary passed to the method."""
        return self.infer_valmap(
            apply_fill, reduce_fill_value, literal_fill_value, bindings
        )

    def infer_fill_type(
        self, bindings: dict[Alias, AbstractFillFType]
    ) -> dict[Alias, AbstractFillFType]:
        """Infers the fills of the formats of all aliases defined in the
        statement. The results will be stored in the dictionary passed to the
        method."""
        return self.infer_valmap(
            apply_fill_type, reduce_fill_type, literal_fill_type, bindings
        )

infer_dimmap(op, dim_bindings) abstractmethod

Infers dimmaps for all aliases defined in the statement. The results will be stored in the dictionary passed to the method.

Source code in src/finch/finch_logic/nodes.py

@abstractmethod
def infer_dimmap(
    self,
    op: Callable,
    dim_bindings: dict[Alias, tuple[T | None, ...]],
) -> dict[Alias, tuple[T | None, ...]]:
    """Infers dimmaps for all aliases defined in the statement. The results
    will be stored in the dictionary passed to the method."""
    ...

infer_element_type(bindings)

Infers element types for all aliases defined in the statement. The results will be stored in the dictionary passed to the method.

Source code in src/finch/finch_logic/nodes.py

def infer_element_type(self, bindings: dict[Alias, FType]) -> dict[Alias, FType]:
    """Infers element types for all aliases defined in the statement. The results
    will be stored in the dictionary passed to the method."""
    return self.infer_valmap(
        merge_element_type, reduce_element_type, literal_element_type, bindings
    )

infer_fill_type(bindings)

Infers the fills of the formats of all aliases defined in the statement. The results will be stored in the dictionary passed to the method.

Source code in src/finch/finch_logic/nodes.py

def infer_fill_type(
    self, bindings: dict[Alias, AbstractFillFType]
) -> dict[Alias, AbstractFillFType]:
    """Infers the fills of the formats of all aliases defined in the
    statement. The results will be stored in the dictionary passed to the
    method."""
    return self.infer_valmap(
        apply_fill_type, reduce_fill_type, literal_fill_type, bindings
    )

infer_fill_value(bindings)

Infers fill_values for all aliases defined in the statement. The results will be stored in the dictionary passed to the method.

Source code in src/finch/finch_logic/nodes.py

def infer_fill_value(
    self, bindings: dict[Alias, AbstractFill]
) -> dict[Alias, AbstractFill]:
    """Infers fill_values for all aliases defined in the statement. The results
    will be stored in the dictionary passed to the method."""
    return self.infer_valmap(
        apply_fill, reduce_fill_value, literal_fill_value, bindings
    )

infer_shape(dim_bindings)

Infers shapes for all aliases defined in the statement. The results will be stored in the dictionary passed to the method.

Source code in src/finch/finch_logic/nodes.py

def infer_shape(
    self,
    dim_bindings: dict[Alias, tuple[Any, ...]],
) -> dict[Alias, tuple[Any, ...]]:
    """Infers shapes for all aliases defined in the statement. The results
    will be stored in the dictionary passed to the method."""
    return self.infer_dimmap(merge_dim, dim_bindings)

infer_shape_type(dim_bindings)

Infers shape_type for all aliases defined in the statement. The results will be stored in the dictionary passed to the method.

Source code in src/finch/finch_logic/nodes.py

def infer_shape_type(
    self,
    dim_bindings: dict[Alias, tuple[FType | None, ...]],
) -> dict[Alias, tuple[FType | None, ...]]:
    """Infers shape_type for all aliases defined in the statement. The results
    will be stored in the dictionary passed to the method."""
    return self.infer_dimmap(merge_dim_type, dim_bindings)

infer_valmap(f, g, h, bindings) abstractmethod

Infers valmaps for all aliases defined in the statement. The results will be stored in the dictionary passed to the method.

Source code in src/finch/finch_logic/nodes.py

@abstractmethod
def infer_valmap(
    self,
    f: Callable,
    g: Callable,
    h: Callable,
    bindings: dict[Alias, T],
) -> dict[Alias, T]:
    """Infers valmaps for all aliases defined in the statement. The results
    will be stored in the dictionary passed to the method."""
    ...

MapJoin dataclass

Bases: LogicTree, LogicExpression, CallTerm

Represents a logical AST expression for mapping the function op across args.... Dimensions which are not present are broadcasted. Dimensions which are present must match. The order of fields in the mapjoin is unique(vcat(map(getfields, args)...))

Attributes:

Name	Type	Description
op	Literal	The function to map.
args	tuple[LogicExpression, ...]	The arguments to map the function across.

Source code in src/finch/finch_logic/nodes.py

@dataclass(eq=True, frozen=True)
class MapJoin(LogicTree, LogicExpression, CallTerm):
    """
    Represents a logical AST expression for mapping the function `op` across `args...`.
    Dimensions which are not present are broadcasted. Dimensions which are
    present must match.  The order of fields in the mapjoin is
    `unique(vcat(map(getfields, args)...))`

    Attributes:
        op: The function to map.
        args: The arguments to map the function across.
    """

    op: Literal
    args: tuple[LogicExpression, ...]

    @property
    def children(self):
        """Returns the children of the node."""
        return [self.op, *self.args]

    def fields(self) -> tuple[Field, ...]:
        """Returns fields of the node."""
        args_fields = [x.fields() for x in self.args]
        return tuple(dict.fromkeys([f for fs in args_fields for f in fs]))

    def dimmap(
        self,
        op: Callable,
        dim_bindings: dict[Alias, tuple[T | None, ...]],
    ) -> tuple[T | None, ...]:
        arg_dims: dict[Field, T | None] = {}
        for arg in self.args:
            dims = arg.dimmap(op, dim_bindings)
            fields = arg.fields()
            for idx, dim in zip(fields, dims, strict=True):
                if idx in arg_dims:
                    arg_dims[idx] = op(arg_dims[idx], dim)
                else:
                    arg_dims[idx] = dim
        return tuple(arg_dims[f] for f in self.fields())

    def valmap(
        self,
        f: Callable,
        g: Callable,
        h: Callable,
        bindings: dict[Alias, T],
    ) -> T:
        return f(self.op.val, *[arg.valmap(f, g, h, bindings) for arg in self.args])

    @classmethod
    def from_children(cls, op, *args):
        return cls(op, args)

children property

Returns the children of the node.

fields()

Returns fields of the node.

Source code in src/finch/finch_logic/nodes.py

def fields(self) -> tuple[Field, ...]:
    """Returns fields of the node."""
    args_fields = [x.fields() for x in self.args]
    return tuple(dict.fromkeys([f for fs in args_fields for f in fs]))

Plan dataclass

Bases: LogicTree, LogicStatement

Represents a logical AST statement that executes a sequence of statements bodies.... Returns the last statement.

Attributes:

Name	Type	Description
bodies	tuple[LogicStatement, ...]	The sequence of statements to execute.

Source code in src/finch/finch_logic/nodes.py

@dataclass(eq=True, frozen=True)
class Plan(LogicTree, LogicStatement):
    """
    Represents a logical AST statement that executes a sequence of statements
    `bodies...`. Returns the last statement.

    Attributes:
        bodies: The sequence of statements to execute.
    """

    bodies: tuple[LogicStatement, ...] = ()

    def infer_dimmap(
        self,
        op: Callable,
        dim_bindings: dict[Alias, tuple[T | None, ...]],
    ) -> dict[Alias, tuple[T | None, ...]]:
        """Infers dimmaps for all aliases defined in the statement. The results
        will be stored in the dictionary passed to the method."""
        for body in self.bodies:
            body.infer_dimmap(op, dim_bindings)
        return dim_bindings

    def infer_valmap(
        self,
        f: Callable,
        g: Callable,
        h: Callable,
        bindings: dict[Alias, T],
    ) -> dict[Alias, T]:
        """Infers valmaps for all aliases defined in the statement. The results
        will be stored in the dictionary passed to the method."""
        for body in self.bodies:
            body.infer_valmap(f, g, h, bindings)
        return bindings

    @property
    def children(self):
        """Returns the children of the node."""
        return [*self.bodies]

    @classmethod
    def from_children(cls, *bodies):
        return cls(bodies)

children property

Returns the children of the node.

infer_dimmap(op, dim_bindings)

Infers dimmaps for all aliases defined in the statement. The results will be stored in the dictionary passed to the method.

Source code in src/finch/finch_logic/nodes.py

def infer_dimmap(
    self,
    op: Callable,
    dim_bindings: dict[Alias, tuple[T | None, ...]],
) -> dict[Alias, tuple[T | None, ...]]:
    """Infers dimmaps for all aliases defined in the statement. The results
    will be stored in the dictionary passed to the method."""
    for body in self.bodies:
        body.infer_dimmap(op, dim_bindings)
    return dim_bindings

infer_valmap(f, g, h, bindings)

Infers valmaps for all aliases defined in the statement. The results will be stored in the dictionary passed to the method.

Source code in src/finch/finch_logic/nodes.py

def infer_valmap(
    self,
    f: Callable,
    g: Callable,
    h: Callable,
    bindings: dict[Alias, T],
) -> dict[Alias, T]:
    """Infers valmaps for all aliases defined in the statement. The results
    will be stored in the dictionary passed to the method."""
    for body in self.bodies:
        body.infer_valmap(f, g, h, bindings)
    return bindings

Produces dataclass

Bases: LogicTree, LogicStatement

Represents a logical AST statement that returns args... from the current plan. Halts execution of the program.

Attributes:

Name	Type	Description
args	tuple[Alias | LogicExpression, ...]	The arguments to return.

Source code in src/finch/finch_logic/nodes.py

@dataclass(eq=True, frozen=True)
class Produces(LogicTree, LogicStatement):
    """
    Represents a logical AST statement that returns `args...` from the current plan.
    Halts execution of the program.

    Attributes:
        args: The arguments to return.
    """

    args: tuple[Alias | LogicExpression, ...]

    @property
    def children(self):
        """Returns the children of the node."""
        return [*self.args]

    @classmethod
    def from_children(cls, *args):
        return cls(args)

    def infer_dimmap(
        self,
        op: Callable,
        dim_bindings: dict[Alias, tuple[T | None, ...]],
    ) -> dict[Alias, tuple[T | None, ...]]:
        """Infers dimmaps for all aliases defined in the statement. The results
        will be stored in the dictionary passed to the method."""
        return dim_bindings

    def infer_valmap(
        self,
        f: Callable,
        g: Callable,
        h: Callable,
        bindings: dict[Alias, T],
    ) -> dict[Alias, T]:
        """Infers valmaps for all aliases defined in the statement. The results
        will be stored in the dictionary passed to the method."""
        return bindings

children property

Returns the children of the node.

infer_dimmap(op, dim_bindings)

Infers dimmaps for all aliases defined in the statement. The results will be stored in the dictionary passed to the method.

Source code in src/finch/finch_logic/nodes.py

def infer_dimmap(
    self,
    op: Callable,
    dim_bindings: dict[Alias, tuple[T | None, ...]],
) -> dict[Alias, tuple[T | None, ...]]:
    """Infers dimmaps for all aliases defined in the statement. The results
    will be stored in the dictionary passed to the method."""
    return dim_bindings

infer_valmap(f, g, h, bindings)

Infers valmaps for all aliases defined in the statement. The results will be stored in the dictionary passed to the method.

Source code in src/finch/finch_logic/nodes.py

def infer_valmap(
    self,
    f: Callable,
    g: Callable,
    h: Callable,
    bindings: dict[Alias, T],
) -> dict[Alias, T]:
    """Infers valmaps for all aliases defined in the statement. The results
    will be stored in the dictionary passed to the method."""
    return bindings

Query dataclass

Bases: LogicTree, LogicStatement

Represents a logical AST statement that evaluates rhs, storing the result in the table lhs. The alias lhs.tns is bound to a tensor whose dimensions are ordered as lhs.idxs, so a query behaves as though its right-hand side were wrapped in Reorder(rhs, lhs.idxs). A query is not in place: the previous value of lhs.tns is replaced, and is only read if rhs refers to it. See QueryInto for in-place updates.

Attributes:

Name	Type	Description
lhs	Table	The table to write, a Table wrapping an Alias.
rhs	LogicExpression	The right-hand side to evaluate.

Source code in src/finch/finch_logic/nodes.py

@dataclass(eq=True, frozen=True)
class Query(LogicTree, LogicStatement):
    """
    Represents a logical AST statement that evaluates `rhs`, storing the result
    in the table `lhs`. The alias `lhs.tns` is bound to a tensor whose
    dimensions are ordered as `lhs.idxs`, so a query behaves as though its
    right-hand side were wrapped in `Reorder(rhs, lhs.idxs)`. A query is not
    in place: the previous value of `lhs.tns` is replaced, and is only read if
    `rhs` refers to it. See `QueryInto` for in-place updates.

    Attributes:
        lhs: The table to write, a `Table` wrapping an `Alias`.
        rhs: The right-hand side to evaluate.
    """

    lhs: Table
    rhs: LogicExpression

    @property
    def children(self):
        """Returns the children of the node."""
        return [self.lhs, self.rhs]

    def infer_dimmap(
        self,
        op: Callable,
        dim_bindings: dict[Alias, tuple[T | None, ...]],
    ) -> dict[Alias, tuple[T | None, ...]]:
        """Infers dimmaps for all aliases defined in the statement. The results
        will be stored in the dictionary passed to the method."""
        var = self.lhs.tns
        assert isinstance(var, Alias)
        dims = Reorder(self.rhs, self.lhs.idxs).dimmap(op, dim_bindings)
        if var in dim_bindings:
            for dim1, dim2 in zip(dims, dim_bindings[var], strict=True):
                op(dim1, dim2)
        else:
            dim_bindings[var] = dims
        return dim_bindings

    def infer_valmap(
        self,
        f: Callable,
        g: Callable,
        h: Callable,
        bindings: dict[Alias, T],
    ) -> dict[Alias, T]:
        """Infers valmaps for all aliases defined in the statement. The results
        will be stored in the dictionary passed to the method."""
        var = self.lhs.tns
        assert isinstance(var, Alias)
        if var in bindings:
            val = self.rhs.valmap(f, g, h, bindings)
            prev = bindings[var]
            # A dynamic value is compatible with any value of its dtype.
            if not (is_dynamic(val) or is_dynamic(prev)) and val != prev:
                raise ValueError(f"Cannot rebind alias {var} to a different values")
        else:
            bindings[var] = self.rhs.valmap(f, g, h, bindings)
        return bindings

children property

Returns the children of the node.

infer_dimmap(op, dim_bindings)

Infers dimmaps for all aliases defined in the statement. The results will be stored in the dictionary passed to the method.

Source code in src/finch/finch_logic/nodes.py

def infer_dimmap(
    self,
    op: Callable,
    dim_bindings: dict[Alias, tuple[T | None, ...]],
) -> dict[Alias, tuple[T | None, ...]]:
    """Infers dimmaps for all aliases defined in the statement. The results
    will be stored in the dictionary passed to the method."""
    var = self.lhs.tns
    assert isinstance(var, Alias)
    dims = Reorder(self.rhs, self.lhs.idxs).dimmap(op, dim_bindings)
    if var in dim_bindings:
        for dim1, dim2 in zip(dims, dim_bindings[var], strict=True):
            op(dim1, dim2)
    else:
        dim_bindings[var] = dims
    return dim_bindings

infer_valmap(f, g, h, bindings)

Infers valmaps for all aliases defined in the statement. The results will be stored in the dictionary passed to the method.

Source code in src/finch/finch_logic/nodes.py

def infer_valmap(
    self,
    f: Callable,
    g: Callable,
    h: Callable,
    bindings: dict[Alias, T],
) -> dict[Alias, T]:
    """Infers valmaps for all aliases defined in the statement. The results
    will be stored in the dictionary passed to the method."""
    var = self.lhs.tns
    assert isinstance(var, Alias)
    if var in bindings:
        val = self.rhs.valmap(f, g, h, bindings)
        prev = bindings[var]
        # A dynamic value is compatible with any value of its dtype.
        if not (is_dynamic(val) or is_dynamic(prev)) and val != prev:
            raise ValueError(f"Cannot rebind alias {var} to a different values")
    else:
        bindings[var] = self.rhs.valmap(f, g, h, bindings)
    return bindings

QueryInto dataclass

Bases: LogicTree, LogicStatement

Represents a logical AST statement that updates the table lhs in place, using the reduction operator op to fold each element of rhs into the matching element of lhs. The alias lhs.tns must already be bound. The fields of rhs which are not in lhs.idxs are reduced with op, and rhs is broadcast over the fields of lhs which it lacks, so a QueryInto is equivalent to the aggregate which starts from lhs, Query(lhs, Aggregate(op, lhs, rhs, setdiff(rhs.fields(), lhs.idxs))).

Attributes:

Name	Type	Description
lhs	Table	The table to update, a Table wrapping an Alias.
op	Literal	The reduction operator used to combine old and new values.
rhs	LogicExpression	The right-hand side to evaluate.

Source code in src/finch/finch_logic/nodes.py

@dataclass(eq=True, frozen=True)
class QueryInto(LogicTree, LogicStatement):
    """
    Represents a logical AST statement that updates the table `lhs` in place,
    using the reduction operator `op` to fold each element of `rhs` into the
    matching element of `lhs`. The alias `lhs.tns` must already be bound. The
    fields of `rhs` which are not in `lhs.idxs` are reduced with `op`, and `rhs`
    is broadcast over the fields of `lhs` which it lacks, so a `QueryInto` is
    equivalent to the aggregate which starts from `lhs`,
    `Query(lhs, Aggregate(op, lhs, rhs, setdiff(rhs.fields(), lhs.idxs)))`.

    Attributes:
        lhs: The table to update, a `Table` wrapping an `Alias`.
        op: The reduction operator used to combine old and new values.
        rhs: The right-hand side to evaluate.
    """

    lhs: Table
    op: Literal
    rhs: LogicExpression

    @property
    def children(self):
        """Returns the children of the node."""
        return [self.lhs, self.op, self.rhs]

    def as_query(self) -> Query:
        """The equivalent aggregate query, which is not in place."""
        idxs = tuple(idx for idx in self.rhs.fields() if idx not in self.lhs.idxs)
        return Query(self.lhs, Aggregate(self.op, self.lhs, self.rhs, idxs))

    def infer_dimmap(
        self,
        op: Callable,
        dim_bindings: dict[Alias, tuple[T | None, ...]],
    ) -> dict[Alias, tuple[T | None, ...]]:
        """Infers dimmaps for all aliases defined in the statement. The results
        will be stored in the dictionary passed to the method."""
        return self.as_query().infer_dimmap(op, dim_bindings)

    def infer_valmap(
        self,
        f: Callable,
        g: Callable,
        h: Callable,
        bindings: dict[Alias, T],
    ) -> dict[Alias, T]:
        """Infers valmaps for all aliases defined in the statement. The results
        will be stored in the dictionary passed to the method."""
        return self.as_query().infer_valmap(f, g, h, bindings)

children property

Returns the children of the node.

as_query()

The equivalent aggregate query, which is not in place.

Source code in src/finch/finch_logic/nodes.py

def as_query(self) -> Query:
    """The equivalent aggregate query, which is not in place."""
    idxs = tuple(idx for idx in self.rhs.fields() if idx not in self.lhs.idxs)
    return Query(self.lhs, Aggregate(self.op, self.lhs, self.rhs, idxs))

infer_dimmap(op, dim_bindings)

Infers dimmaps for all aliases defined in the statement. The results will be stored in the dictionary passed to the method.

Source code in src/finch/finch_logic/nodes.py

def infer_dimmap(
    self,
    op: Callable,
    dim_bindings: dict[Alias, tuple[T | None, ...]],
) -> dict[Alias, tuple[T | None, ...]]:
    """Infers dimmaps for all aliases defined in the statement. The results
    will be stored in the dictionary passed to the method."""
    return self.as_query().infer_dimmap(op, dim_bindings)

infer_valmap(f, g, h, bindings)

Infers valmaps for all aliases defined in the statement. The results will be stored in the dictionary passed to the method.

Source code in src/finch/finch_logic/nodes.py

def infer_valmap(
    self,
    f: Callable,
    g: Callable,
    h: Callable,
    bindings: dict[Alias, T],
) -> dict[Alias, T]:
    """Infers valmaps for all aliases defined in the statement. The results
    will be stored in the dictionary passed to the method."""
    return self.as_query().infer_valmap(f, g, h, bindings)

Relabel dataclass

Bases: LogicTree, LogicExpression

Represents a logical AST statement that relabels the dimensions of arg to be idxs.... Number of fields of arg and idxs must match.

Attributes:

Name	Type	Description
arg	LogicExpression	The argument to relabel.
idxs	tuple[Field, ...]	The new labels for dimensions.

Source code in src/finch/finch_logic/nodes.py

@dataclass(eq=True, frozen=True)
class Relabel(LogicTree, LogicExpression):
    """
    Represents a logical AST statement that relabels the dimensions of `arg` to be
    `idxs...`. Number of fields of `arg` and `idxs` must match.

    Attributes:
        arg: The argument to relabel.
        idxs: The new labels for dimensions.
    """

    arg: LogicExpression
    idxs: tuple[Field, ...]

    def fields(self) -> tuple[Field, ...]:
        """Returns fields of the node."""
        return self.idxs

    def dimmap(
        self, op: Callable, dim_bindings: dict[Alias, tuple[T | None, ...]]
    ) -> tuple[T | None, ...]:
        return self.arg.dimmap(op, dim_bindings)

    def valmap(
        self,
        f: Callable,
        g: Callable,
        h: Callable,
        bindings: dict[Alias, T],
    ) -> T:
        return self.arg.valmap(f, g, h, bindings)

    @property
    def children(self):
        """Returns the children of the node."""
        return [self.arg, *self.idxs]

    @classmethod
    def from_children(cls, arg, *idxs):
        return cls(arg, idxs)

children property

Returns the children of the node.

fields()

Returns fields of the node.

Source code in src/finch/finch_logic/nodes.py

def fields(self) -> tuple[Field, ...]:
    """Returns fields of the node."""
    return self.idxs

Reorder dataclass

Bases: LogicTree, LogicExpression

Represents a logical AST statement that reorders the dimensions of arg to be idxs.... Dimensions known to be length 1 may be dropped. Dimensions that do not exist in arg may be added.

Attributes:

Name	Type	Description
arg	LogicExpression	The argument to reorder.
idxs	tuple[Field, ...]	The new order of dimensions.

Source code in src/finch/finch_logic/nodes.py

@dataclass(eq=True, frozen=True)
class Reorder(LogicTree, LogicExpression):
    """
    Represents a logical AST statement that reorders the dimensions of `arg` to be
    `idxs...`. Dimensions known to be length 1 may be dropped. Dimensions that do not
    exist in `arg` may be added.

    Attributes:
        arg: The argument to reorder.
        idxs: The new order of dimensions.
    """

    arg: LogicExpression
    idxs: tuple[Field, ...]

    @property
    def children(self):
        """Returns the children of the node."""
        return [self.arg, *self.idxs]

    def fields(self) -> tuple[Field, ...]:
        """Returns fields of the node."""
        return self.idxs

    def dimmap(
        self, op: Callable, dim_bindings: dict[Alias, tuple[T | None, ...]]
    ) -> tuple[T | None, ...]:
        idxs = self.arg.fields()
        dims = self.arg.dimmap(op, dim_bindings)
        idx_dims = dict(zip(idxs, dims, strict=True))
        for idx in idxs:
            if idx not in self.idxs:
                # when squeezing a dimension, we combine with None
                op(idx_dims[idx], None)
        return tuple(idx_dims.get(f) for f in self.idxs)

    def valmap(
        self,
        f: Callable,
        g: Callable,
        h: Callable,
        bindings: dict[Alias, T],
    ) -> T:
        return self.arg.valmap(f, g, h, bindings)

    @classmethod
    def from_children(cls, arg, *idxs):
        return cls(arg, idxs)

children property

Returns the children of the node.

fields()

Returns fields of the node.

Source code in src/finch/finch_logic/nodes.py

def fields(self) -> tuple[Field, ...]:
    """Returns fields of the node."""
    return self.idxs

Table dataclass

Bases: LogicTree, LogicExpression

Represents a logical AST expression for a tensor object tns, indexed by fields idxs.... A table is a tensor with named dimensions.

Attributes:

Name	Type	Description
tns	Literal | Alias	The tensor object.
idxs	tuple[Field, ...]	The fields indexing the tensor.

Source code in src/finch/finch_logic/nodes.py

@dataclass(eq=True, frozen=True)
class Table(LogicTree, LogicExpression):
    """
    Represents a logical AST expression for a tensor object `tns`, indexed by fields
    `idxs...`. A table is a tensor with named dimensions.

    Attributes:
        tns: The tensor object.
        idxs: The fields indexing the tensor.
    """

    tns: Literal | Alias
    idxs: tuple[Field, ...]

    @property
    def children(self):
        """Returns the children of the node."""
        return [self.tns, *self.idxs]

    def fields(self) -> tuple[Field, ...]:
        """Returns fields of the node."""
        return self.idxs

    def dimmap(
        self, op: Callable, dim_bindings: dict[Alias, tuple[T | None, ...]]
    ) -> tuple[T | None, ...]:
        match self.tns:
            case Alias():
                return self.tns.dimmap(op, dim_bindings)
        raise NotImplementedError(f"Cannot resolve dims of {type(self.tns).__name__}")

    def valmap(
        self,
        f: Callable,
        g: Callable,
        h: Callable,
        bindings: dict[Alias, T],
    ) -> T:
        match self.tns:
            case Alias():
                return self.tns.valmap(f, g, h, bindings)
        raise NotImplementedError("Cannot resolve value of Tables")

    @classmethod
    def from_children(cls, tns, *idxs):
        return cls(tns, idxs)

children property

Returns the children of the node.

fields()

Returns fields of the node.

Source code in src/finch/finch_logic/nodes.py

def fields(self) -> tuple[Field, ...]:
    """Returns fields of the node."""
    return self.idxs

Value dataclass

Bases: LogicNode

Represents a logical AST expression for an expression ex of type type, yet to be evaluated.

Attributes:

Name	Type	Description
ex	Any	The expression to be evaluated.
type_	Any	The type of the expression.

Source code in src/finch/finch_logic/nodes.py

@dataclass(eq=True, frozen=True)
class Value(LogicNode):
    """
    Represents a logical AST expression for an expression `ex` of type `type`,
    yet to be evaluated.

    Attributes:
        ex: The expression to be evaluated.
        type_: The type of the expression.
    """

    ex: Any
    type_: Any

fill_expression(ex)

A zero-dimensional expression for the fill value of ex, made of the fill values of the tensors which ex reads.

Source code in src/finch/finch_logic/nodes.py

def fill_expression(ex: LogicExpression) -> LogicExpression:
    """
    A zero-dimensional expression for the fill value of `ex`, made of the fill
    values of the tensors which `ex` reads.
    """
    match ex:
        case Table(Alias() as tns, _):
            return FillTable(tns)
        case Table(Literal(tns), _):
            # The fill value of a literal tensor is compile-time data too.
            return Literal(tns.fill_value)
        case Literal() | FillTable():
            return ex
        case MapJoin(op, args):
            return MapJoin(op, tuple(fill_expression(arg) for arg in args))
        case Reorder(arg, _) | Relabel(arg, _):
            return fill_expression(arg)
        case _:
            raise NotImplementedError(f"No fill expression for {ex}")

is_fill_expression(ex)

Whether ex is made of literals and fill values, as fill_expression.

Source code in src/finch/finch_logic/nodes.py

def is_fill_expression(ex: LogicNode) -> bool:
    """Whether `ex` is made of literals and fill values, as `fill_expression`."""
    match ex:
        case Literal() | FillTable():
            return True
        case MapJoin(Literal(), args):
            return all(is_fill_expression(arg) for arg in args)
        case _:
            return False