algebra

AbstractFill

Bases: FTyped[AbstractFillFType], ABC

A tensor's fill value. Its ftype says whether kernels may specialize on it.

Source code in src/finch/algebra/fill.py

class AbstractFill(FTyped[AbstractFillFType], ABC):
    """A tensor's fill value. Its ftype says whether kernels may specialize on it."""

    @property
    @abstractmethod
    def ftype(self) -> AbstractFillFType:
        """The fill of the format which this fill belongs to."""
        ...

    @property
    def element_type(self) -> FType:
        """The element type of the fill value, always known."""
        return self.ftype.element_type

    @property
    @abstractmethod
    def value(self) -> Any:
        """The fill value itself, always known."""
        ...

    def as_dynamic(self) -> DynamicFill:
        """This fill, marked so that kernels will not specialize on its value."""
        return DynamicFill(self.value, self.element_type)

    @abstractmethod
    def astype(self, element_type: FType) -> AbstractFill:
        """This fill, with its value converted to `element_type`."""
        ...

element_type property

The element type of the fill value, always known.

ftype abstractmethod property

The fill of the format which this fill belongs to.

value abstractmethod property

The fill value itself, always known.

as_dynamic()

This fill, marked so that kernels will not specialize on its value.

Source code in src/finch/algebra/fill.py

def as_dynamic(self) -> DynamicFill:
    """This fill, marked so that kernels will not specialize on its value."""
    return DynamicFill(self.value, self.element_type)

astype(element_type) abstractmethod

This fill, with its value converted to element_type.

Source code in src/finch/algebra/fill.py

@abstractmethod
def astype(self, element_type: FType) -> AbstractFill:
    """This fill, with its value converted to `element_type`."""
    ...

AbstractFillFType

Bases: FType, ABC

The fill of a format: the element type of its fill, and whether kernels may specialize on the value of the fill.

Source code in src/finch/algebra/fill.py

class AbstractFillFType(FType, ABC):
    """
    The fill of a format: the element type of its fill, and whether kernels may
    specialize on the value of the fill.
    """

    @property
    @abstractmethod
    def element_type(self) -> FType:
        """The element type of the fill, always known."""
        ...

    def as_dynamic(self) -> DynamicFillFType:
        """This fill, marked so that kernels will not specialize on its value."""
        return DynamicFillFType(self.element_type)

    @abstractmethod
    def astype(self, element_type: FType) -> AbstractFillFType:
        """This fill, with its value converted to `element_type`."""
        ...

element_type abstractmethod property

The element type of the fill, always known.

as_dynamic()

This fill, marked so that kernels will not specialize on its value.

Source code in src/finch/algebra/fill.py

def as_dynamic(self) -> DynamicFillFType:
    """This fill, marked so that kernels will not specialize on its value."""
    return DynamicFillFType(self.element_type)

astype(element_type) abstractmethod

This fill, with its value converted to element_type.

Source code in src/finch/algebra/fill.py

@abstractmethod
def astype(self, element_type: FType) -> AbstractFillFType:
    """This fill, with its value converted to `element_type`."""
    ...

DynamicFill

Bases: AbstractFill

A fill value which kernels must not specialize on. The value is known and is bound to the kernel at call time.

Equality and hashing are by element type only, i.e. two equal DynamicFills may have different .value's.

Source code in src/finch/algebra/fill.py

class DynamicFill(AbstractFill):
    """
    A fill value which kernels must not specialize on. The value is known and is
    bound to the kernel at call time.

    Equality and hashing are by element type *only*, i.e. two equal
    `DynamicFill`s may have different `.value`'s.
    """

    def __init__(self, value: Any, element_type: Any | None = None) -> None:
        if isinstance(value, AbstractFill):
            self._value = value.value
        else:
            self._value = value
        self._element_type = (
            ftype(self._value) if element_type is None else ftype(element_type)
        )

    @property
    def ftype(self) -> DynamicFillFType:
        return DynamicFillFType(self._element_type)

    @property
    def element_type(self) -> FType:
        return self._element_type

    @property
    def value(self) -> Any:
        return self._value

    def as_dynamic(self) -> DynamicFill:
        return self

    def astype(self, element_type: FType) -> DynamicFill:
        return DynamicFill(element_type(self._value), element_type)

    def __eq__(self, other):
        return isinstance(other, DynamicFill) and self.ftype == other.ftype

    def __hash__(self):
        return hash((DynamicFill, self.ftype))

    def __same__(self, other):
        return self == other

    def __rsame__(self, other):
        return self == other

    def __repr__(self):
        return f"DynamicFill({self._value!r}, {self._element_type!r})"

DynamicFillError

Bases: Exception

Raised when a fill value must be specialized on at compile time but the fill is Dynamic. Callers may catch this to fall back to value-specialized compilation.

Source code in src/finch/algebra/fill.py

class DynamicFillError(Exception):
    """
    Raised when a fill value must be specialized on at compile time but the fill
    is Dynamic. Callers may catch this to fall back to value-specialized
    compilation.
    """

DynamicFillFType

Bases: AbstractFillFType

The fill of a format which kernels must not specialize on, so only its element type is part of the format. Each tensor holds its own fill value, which is bound to the kernel at call time.

Source code in src/finch/algebra/fill.py

class DynamicFillFType(AbstractFillFType):
    """
    The fill of a format which kernels must not specialize on, so only its
    element type is part of the format. Each tensor holds its own fill value,
    which is bound to the kernel at call time.
    """

    def __init__(self, element_type: Any) -> None:
        self._element_type = ftype(element_type)

    @property
    def element_type(self) -> FType:
        return self._element_type

    def as_dynamic(self) -> DynamicFillFType:
        return self

    def astype(self, element_type: FType) -> DynamicFillFType:
        return DynamicFillFType(element_type)

    def __call__(self, val: Any) -> DynamicFill:
        return DynamicFill(self._element_type(val), self._element_type)

    def __eq__(self, other):
        return (
            isinstance(other, DynamicFillFType)
            and self._element_type == other._element_type
        )

    def __hash__(self):
        return hash((DynamicFillFType, self._element_type))

    def __repr__(self):
        return f"DynamicFillFType({self._element_type!r})"

FType

Bases: ABC

Source code in src/finch/algebra/ftypes.py

class FType(ABC):
    @abstractmethod
    def __eq__(self, other) -> builtins.bool: ...

    @abstractmethod
    def __hash__(self) -> builtins.int: ...

    @abstractmethod
    def __call__(self, val: Any) -> Any:
        """
        Perform type conversion or construction with the given value.

        For numeric/scalar types, this converts the value to this type.
        For composite types, this may construct an instance of this type.

        Args:
            val: The value to convert or use for construction

        Returns:
            The converted/constructed value
        """
        ...

    def fisinstance(self, other) -> builtins.bool:
        """
        Check if `other` is an instance of this ftype.
        """
        return ftype(other) == self

__call__(val) abstractmethod

Perform type conversion or construction with the given value.

For numeric/scalar types, this converts the value to this type. For composite types, this may construct an instance of this type.

Parameters:

Name	Type	Description	Default
val	Any	The value to convert or use for construction	required

Returns:

Type	Description
Any	The converted/constructed value

Source code in src/finch/algebra/ftypes.py

@abstractmethod
def __call__(self, val: Any) -> Any:
    """
    Perform type conversion or construction with the given value.

    For numeric/scalar types, this converts the value to this type.
    For composite types, this may construct an instance of this type.

    Args:
        val: The value to convert or use for construction

    Returns:
        The converted/constructed value
    """
    ...

fisinstance(other)

Check if other is an instance of this ftype.

Source code in src/finch/algebra/ftypes.py

def fisinstance(self, other) -> builtins.bool:
    """
    Check if `other` is an instance of this ftype.
    """
    return ftype(other) == self

FTyped

Bases: Generic[FT]

Abstract base class for objects that can be formatted.

Source code in src/finch/algebra/ftypes.py

class FTyped(Generic[FT]):
    """
    Abstract base class for objects that can be formatted.
    """

    @property
    @abstractmethod
    def ftype(self) -> FT:
        """
        The ftype of the object.
        """
        ...

ftype abstractmethod property

The ftype of the object.

SingletonOperatorFType

Bases: ImmutableStructFType, FinchOperatorFType

A stateless callable type with one canonical operator value.

Source code in src/finch/algebra/algebra.py

class SingletonOperatorFType(ImmutableStructFType, FinchOperatorFType):
    """A stateless callable type with one canonical operator value."""

    @property
    @abstractmethod
    def operator(self) -> FinchOperator: ...

    @property
    def struct_name(self):
        return type(self).__name__.removeprefix("_").removesuffix("FType")

    @property
    def struct_fields(self):
        return []

    def from_fields(self):
        return self.operator

    def __call__(self, value):
        if ftype(value) == self:
            return value
        raise TypeError(f"Expected an operator of type {self}")

StaticFill

Bases: AbstractFill

A fill value which kernels may specialize on. Equality and hashing are by value, matching StaticFillFType.

Source code in src/finch/algebra/fill.py

class StaticFill(AbstractFill):
    """
    A fill value which kernels may specialize on. Equality and hashing are by
    value, matching `StaticFillFType`.
    """

    def __init__(self, value: Any) -> None:
        if isinstance(value, AbstractFill):
            self._value = value.value
        else:
            self._value = value

    @property
    def ftype(self) -> StaticFillFType:
        return StaticFillFType(self._value)

    @property
    def value(self) -> Any:
        return self._value

    def astype(self, element_type: FType) -> StaticFill:
        return StaticFill(element_type(self._value))

    def __eq__(self, other):
        return isinstance(other, StaticFill) and self.ftype == other.ftype

    def __hash__(self):
        return hash((StaticFill, self.ftype))

    def __same__(self, other):
        return self == other

    def __rsame__(self, other):
        return self == other

    def __repr__(self):
        return f"StaticFill({self._value!r})"

StaticFillFType

Bases: AbstractFillFType

The fill of a format which kernels may specialize on, so its value is part of the format. Equality and hashing are by element type and value, so formats with different static fills are distinct and get distinct kernels.

Source code in src/finch/algebra/fill.py

class StaticFillFType(AbstractFillFType):
    """
    The fill of a format which kernels may specialize on, so its value is part
    of the format. Equality and hashing are by element type and value, so
    formats with different static fills are distinct and get distinct kernels.
    """

    def __init__(self, value: Any) -> None:
        self._value = value

    @property
    def value(self) -> Any:
        return self._value

    @property
    def element_type(self) -> FType:
        return ftype(self._value)

    def astype(self, element_type: FType) -> StaticFillFType:
        return StaticFillFType(element_type(self._value))

    def __call__(self, val: Any) -> StaticFill:
        fill = StaticFill(self.element_type(val))
        if fill.ftype != self:
            raise ValueError(f"{val!r} is not the static fill {self._value!r}")
        return fill

    def __eq__(self, other):
        # Values are compared with `same` rather than `==` because of NaN.
        # ftypes filled with NaN must compare equal or they get separate
        # kernels and fail each other's type checks. Imported lazily: `ffuncs`
        # depends on this module.
        from .ffuncs import same

        return (
            isinstance(other, StaticFillFType)
            and self.element_type == other.element_type
            and bool(same(self._value, other._value))
        )

    def __hash__(self):
        from .ffuncs import canonical

        return hash((StaticFillFType, self.element_type, canonical(self._value)))

    def __repr__(self):
        return f"StaticFillFType({self._value!r})"

StructFType

Bases: FType, ABC

Source code in src/finch/algebra/ftypes.py

class StructFType(FType, ABC):
    def __eq__(self, other):
        return (
            type(other) is type(self)
            and self.struct_name == other.struct_name
            and self.struct_fields == other.struct_fields
        )

    def __hash__(self):
        return hash((type(self), self.struct_name, tuple(self.struct_fields)))

    def __repr__(self):
        fields_str = ", ".join(f"{name}: {type_}" for name, type_ in self.struct_fields)
        return f"{self.struct_name}({fields_str})"

    def __call__(self, *args, **kwargs):
        """
        Construct a struct instance from the given fields.

        Can be called with positional arguments matching struct_fields order,
        or keyword arguments matching field names.
        """
        if args and kwargs:
            raise TypeError("Cannot use both positional and keyword arguments")
        if args:
            return self.from_fields(*args)
        if kwargs:
            # Convert kwargs to positional args in field order
            field_values = [kwargs[name] for name, _ in self.struct_fields]
            return self.from_fields(*field_values)
        raise TypeError("__call__ requires at least one argument")

    @property
    @abstractmethod
    def struct_name(self) -> str: ...

    @property
    @abstractmethod
    def struct_fields(self) -> list[tuple[str, FType]]: ...

    @abstractmethod
    def from_fields(self, *args): ...

    @property
    @abstractmethod
    def is_mutable(self) -> builtins.bool: ...

    def struct_getattr(self, obj, attr) -> Any:
        return getattr(obj, attr)

    def struct_setattr(self, obj, attr, value) -> None:
        setattr(obj, attr, value)
        return

    @property
    def struct_fieldnames(self) -> list[str]:
        return [name for (name, _) in self.struct_fields]

    @property
    def struct_fieldtypes(self) -> list[FType]:
        return [type_ for (_, type_) in self.struct_fields]

    def struct_hasattr(self, attr: str) -> builtins.bool:
        return attr in dict(self.struct_fields)

    def struct_attrtype(self, attr: str) -> FType:
        return dict(self.struct_fields)[attr]

__call__(*args, **kwargs)

Construct a struct instance from the given fields.

Can be called with positional arguments matching struct_fields order, or keyword arguments matching field names.

Source code in src/finch/algebra/ftypes.py

def __call__(self, *args, **kwargs):
    """
    Construct a struct instance from the given fields.

    Can be called with positional arguments matching struct_fields order,
    or keyword arguments matching field names.
    """
    if args and kwargs:
        raise TypeError("Cannot use both positional and keyword arguments")
    if args:
        return self.from_fields(*args)
    if kwargs:
        # Convert kwargs to positional args in field order
        field_values = [kwargs[name] for name, _ in self.struct_fields]
        return self.from_fields(*field_values)
    raise TypeError("__call__ requires at least one argument")

Tensor

Bases: FTyped[TensorFType[FT]], ABC

Abstract base class for tensor-like data structures. Tensors are multi-dimensional arrays that can be used to represent data in various formats. They support operations such as indexing, slicing, and reshaping, and can be used in mathematical computations. This class provides the basic interface for tensors to be used with lazy ops in Finch, though more advanced interfaces may be required for different backends.

Source code in src/finch/algebra/tensor.py

class Tensor(FTyped[TensorFType[FT]], ABC):
    """
    Abstract base class for tensor-like data structures. Tensors are
    multi-dimensional arrays that can be used to represent data in various
    formats. They support operations such as indexing, slicing, and reshaping,
    and can be used in mathematical computations. This class provides the basic
    interface for tensors to be used with lazy ops in Finch, though more
    advanced interfaces may be required for different backends.
    """

    @property
    def ndim(self) -> int:
        """Number of dimensions of the tensor."""
        return int(self.ftype.ndim)

    @property
    def size(self):
        size = 1
        for dim in self.shape:
            size *= int(dim)
        return size

    @property
    @abstractmethod
    def ftype(self) -> TensorFType[FT]:
        """FType of the tensor, which may include metadata about the tensor."""
        ...

    @property
    def fill_value(self) -> Any:
        """The fill value for the tensor.  The fill value is the
        default value for a tensor when it is created with a given shape and dtype,
        as well as the background value for sparse tensors.
        Note: this is the raw value NOT the AbstractFill. A tensor whose fill is
        dynamic holds its own fill value.
        """
        fill_type = self.ftype.fill_type
        if is_static(fill_type):
            return fill_type.value
        raise NotImplementedError(
            f"{type(self).__name__} must hold its dynamic fill value"
        )

    @property
    def fill(self) -> AbstractFill:
        """
        The fill of the tensor: its fill value, and whether kernels may
        specialize on it. Its ftype is the fill of the tensor's format.
        """
        fill_type = self.ftype.fill_type
        if is_static(fill_type):
            return StaticFill(fill_type.value)
        return DynamicFill(self.fill_value, fill_type.element_type)

    def with_fill(self, fill_value: AbstractFill) -> Tensor:
        """
        An equivalent tensor carrying `fill_value` as its fill.
        """
        raise NotImplementedError(
            f"{type(self).__name__} cannot replace its fill value"
        )

    @property
    def element_type(self) -> FT:
        """The element type of the tensor.  The element type is the scalar type of
        the elements in a tensor, which may be different from the data type of the
        tensor.
        """
        return self.ftype.element_type

    @property
    def dtype(self):
        return self.element_type

    @property
    def device(self):
        return getattr(self, "_device", self.ftype.device)

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

    def to_device(self, device, /, *, stream=None):
        if stream is not None:
            raise ValueError(f"stream argument is not supported; got {stream!r}")
        device = normalize_device(device)
        if device == self.device:
            return self
        raise ValueError(f"device argument is not supported; got {device!r}")

    @property
    def shape_type(self) -> tuple[FType, ...]:
        """Shape type of the tensor. The shape type is a tuple of the index
        types in the tensor. It's the type of each element in tns.shape. It
        should be an actual tuple, rather than a tupleftype, so that it can hold
        e.g. dtypes, formats, or types, and so that we can easily index it."""
        return self.ftype.shape_type

    @property
    @abstractmethod
    def shape(self) -> tuple[np.intp, ...]:
        """Shape of the tensor."""
        ...

    @abstractmethod
    def item(self):
        """
        Return the Python scalar stored in a zero-dimensional tensor.

        Indexing tensor objects must keep returning tensor-like values, including for
        zero-dimensional results. `item()` is the explicit escape hatch for code that
        needs the underlying Python scalar value. Implementations should raise
        `ValueError` when called on a non-scalar tensor.
        """
        ...

    @abstractmethod
    def to_numpy(self):
        """Convert the tensor to a NumPy representation."""
        ...

    @abstractmethod
    def to_scipy(self):
        """Convert the tensor to a SciPy sparse representation."""
        ...

element_type property

The element type of the tensor. The element type is the scalar type of the elements in a tensor, which may be different from the data type of the tensor.

fill property

The fill of the tensor: its fill value, and whether kernels may specialize on it. Its ftype is the fill of the tensor's format.

fill_value property

The fill value for the tensor. The fill value is the default value for a tensor when it is created with a given shape and dtype, as well as the background value for sparse tensors. Note: this is the raw value NOT the AbstractFill. A tensor whose fill is dynamic holds its own fill value.

ftype abstractmethod property

FType of the tensor, which may include metadata about the tensor.

ndim property

Number of dimensions of the tensor.

shape abstractmethod property

Shape of the tensor.

shape_type property

Shape type of the tensor. The shape type is a tuple of the index types in the tensor. It's the type of each element in tns.shape. It should be an actual tuple, rather than a tupleftype, so that it can hold e.g. dtypes, formats, or types, and so that we can easily index it.

item() abstractmethod

Return the Python scalar stored in a zero-dimensional tensor.

Indexing tensor objects must keep returning tensor-like values, including for zero-dimensional results. item() is the explicit escape hatch for code that needs the underlying Python scalar value. Implementations should raise ValueError when called on a non-scalar tensor.

Source code in src/finch/algebra/tensor.py

@abstractmethod
def item(self):
    """
    Return the Python scalar stored in a zero-dimensional tensor.

    Indexing tensor objects must keep returning tensor-like values, including for
    zero-dimensional results. `item()` is the explicit escape hatch for code that
    needs the underlying Python scalar value. Implementations should raise
    `ValueError` when called on a non-scalar tensor.
    """
    ...

to_numpy() abstractmethod

Convert the tensor to a NumPy representation.

Source code in src/finch/algebra/tensor.py

@abstractmethod
def to_numpy(self):
    """Convert the tensor to a NumPy representation."""
    ...

to_scipy() abstractmethod

Convert the tensor to a SciPy sparse representation.

Source code in src/finch/algebra/tensor.py

@abstractmethod
def to_scipy(self):
    """Convert the tensor to a SciPy sparse representation."""
    ...

with_fill(fill_value)

An equivalent tensor carrying fill_value as its fill.

Source code in src/finch/algebra/tensor.py

def with_fill(self, fill_value: AbstractFill) -> Tensor:
    """
    An equivalent tensor carrying `fill_value` as its fill.
    """
    raise NotImplementedError(
        f"{type(self).__name__} cannot replace its fill value"
    )

TensorFType

Bases: FType, ABC, Generic[FT]

Source code in src/finch/algebra/tensor.py

class TensorFType(FType, ABC, Generic[FT]):
    @property
    def ndim(self) -> int:
        """Number of dimensions of the tensor."""
        return len(self.shape_type)

    @property
    def shape(self) -> tuple[int, ...]:
        raise TypeError("TensorFType does not have a shape.")

    @property
    def size(self) -> int:
        return functools.reduce(lambda x, y: x * int(y), self.shape, 1)

    @property
    @abstractmethod
    def fill_type(self) -> AbstractFillFType:
        """The fill of the format, either static or dynamic."""
        ...

    def with_fill(self, fill_type: AbstractFillFType) -> TensorFType:
        """
        This ftype carrying `fill_type` as its fill.
        """
        raise NotImplementedError(
            f"{type(self).__name__} cannot replace its fill value"
        )

    @property
    @abstractmethod
    def element_type(self) -> FT:
        """Data type of the tensor elements."""
        ...

    @property
    def dtype(self):
        return self.element_type

    @property
    def device(self):
        return serial()

    @property
    def device_type(self) -> FType:
        return self.device.ftype

    @property
    @abstractmethod
    def shape_type(self) -> tuple[FType, ...]:
        """Shape type of the tensor. The shape type is a tuple of the index
        types in the tensor. It's the type of each element in tns.shape. It
        should be an actual tuple, rather than a tuple type, so that it can hold
        e.g. dtypes, formats, or types, and so that we can easily index it."""
        ...

    @abstractmethod
    def construct(self, shape: tuple) -> Tensor:
        """
        Create a tensor instance with the given shape.

        Args:
            shape: The shape of the tensor to create.
        Returns:
            A tensor instance with the specified shape.
        """
        ...

    @abstractmethod
    def from_numpy(self, arr: np.ndarray) -> Tensor: ...

element_type abstractmethod property

Data type of the tensor elements.

fill_type abstractmethod property

The fill of the format, either static or dynamic.

ndim property

Number of dimensions of the tensor.

shape_type abstractmethod property

Shape type of the tensor. The shape type is a tuple of the index types in the tensor. It's the type of each element in tns.shape. It should be an actual tuple, rather than a tuple type, so that it can hold e.g. dtypes, formats, or types, and so that we can easily index it.

construct(shape) abstractmethod

Create a tensor instance with the given shape.

Parameters:

Name	Type	Description	Default
shape	tuple	The shape of the tensor to create.	required

Returns: A tensor instance with the specified shape.

Source code in src/finch/algebra/tensor.py

@abstractmethod
def construct(self, shape: tuple) -> Tensor:
    """
    Create a tensor instance with the given shape.

    Args:
        shape: The shape of the tensor to create.
    Returns:
        A tensor instance with the specified shape.
    """
    ...

with_fill(fill_type)

This ftype carrying fill_type as its fill.

Source code in src/finch/algebra/tensor.py

def with_fill(self, fill_type: AbstractFillFType) -> TensorFType:
    """
    This ftype carrying `fill_type` as its fill.
    """
    raise NotImplementedError(
        f"{type(self).__name__} cannot replace its fill value"
    )

TupleFType

Bases: ImmutableStructFType, FDType

FType for Python tuples, with a struct-compatible interface.

Source code in src/finch/algebra/ftypes.py

class TupleFType(ImmutableStructFType, FDType):
    """FType for Python tuples, with a struct-compatible interface."""

    def __init__(self, struct_types):
        self._struct_types = struct_types

    @property
    def dtype(self) -> np.dtype:
        return np.dtype(
            [(name, np_dtype(field_type)) for name, field_type in self.struct_fields]
        )

    def __repr__(self):
        return f"TupleFType(({', '.join(map(repr, self._struct_types))},))"

    def __str__(self):
        fields_str = ", ".join(f"{name}: {type_}" for name, type_ in self.struct_fields)
        return f"{self.struct_name}({fields_str})"

    @property
    def struct_name(self):
        return "tuple"

    @property
    def struct_fields(self):
        return [(f"element_{i}", fmt) for i, fmt in enumerate(self._struct_types)]

    @property
    def struct_fieldnames(self) -> list[str]:
        return [name for (name, _) in self.struct_fields]

    @property
    def struct_fieldtypes(self) -> list[Any]:
        return [type_ for (_, type_) in self.struct_fields]

    def __promote__(self, other):
        if not isinstance(other, TupleFType):
            return None
        if len(self.struct_fieldtypes) != len(other.struct_fieldtypes):
            raise TypeError("Tuple operands must have the same length.")
        return TupleFType.from_tuple(
            tuple(
                promote_type(type_, other_type)
                for type_, other_type in zip(
                    self.struct_fieldtypes,
                    other.struct_fieldtypes,
                    strict=True,
                )
            )
        )

    def struct_hasattr(self, attr: str) -> builtins.bool:
        return attr in dict(self.struct_fields)

    def struct_attrtype(self, attr: str) -> Any:
        return dict(self.struct_fields)[attr]

    def struct_getattr(self, obj, attr):
        index = list(self.struct_fieldnames).index(attr)
        field_type = self.struct_fieldtypes[index]
        return field_type(obj[index])

    def struct_setattr(self, obj, attr, value):
        index = list(self.struct_fieldnames).index(attr)
        obj[index] = value

    def fisinstance(self, other):
        if not isinstance(other, tuple) or len(other) != len(self.struct_fieldtypes):
            return False
        return all(
            fisinstance(elt, fmt)
            for elt, fmt in zip(other, self.struct_fieldtypes, strict=False)
        )

    def from_fields(self, *args):
        assert all(
            fisinstance(a, f)
            for a, f in zip(args, self.struct_fieldtypes, strict=False)
        )
        return tuple(args)

    def __call__(self, arg):
        return tuple([T(x) for T, x in zip(self._struct_types, arg, strict=False)])

    @staticmethod
    @lru_cache
    def from_tuple(types: tuple[FType, ...]) -> TupleFType:
        if not isinstance(types, tuple):
            raise TypeError("TupleFType.from_tuple expects tuple[FType, ...]")
        if not all(isinstance(type_, FType) for type_ in types):
            raise TypeError("TupleFType.from_tuple expects tuple[FType, ...]")
        return TupleFType(types)

apply_fill(op, *fills)

Compute the fill value of mapping op over tensors with fills fills.

A fill stays static only while its value is one the algebra can act on. Combining static fills computes an arbitrary value -- adding 1 repeatedly walks a fill through 1, 2, 3, ... -- and a static fill is compared by value, so keeping those static would key a kernel per distinct value and make a loop cost a compilation per iteration.

Source code in src/finch/algebra/fill.py

def apply_fill(op: FinchOperator, *fills: AbstractFill) -> AbstractFill:
    """
    Compute the fill value of mapping `op` over tensors with fills `fills`.

    A fill stays static only while its value is one the algebra can act on.
    Combining static fills computes an arbitrary value -- adding 1 repeatedly
    walks a fill through 1, 2, 3, ... -- and a static fill is compared by
    value, so keeping those static would key a kernel per distinct value and
    make a loop cost a compilation per iteration.
    """
    # Imported lazily: `algebra` depends on this module.
    from .algebra import is_specializable_value

    values = [f.value for f in fills]
    if not any(is_dynamic(f) for f in fills):
        result = op(*values)
        if is_specializable_value(result):
            return StaticFill(result)
        return DynamicFill(result)
    for f in fills:
        if not is_dynamic(f) and op.ftype.is_annihilator(f.value):
            result_type = op.ftype.return_type(*(g.element_type for g in fills))
            return f.astype(result_type)
    element_type = op.ftype.return_type(*(f.element_type for f in fills))
    return DynamicFill(op(*values), element_type)

apply_fill_type(op, *fill_types)

The fill of the format which results from mapping op over tensors whose formats have the fills fill_types. This is the format of apply_fill.

Source code in src/finch/algebra/fill.py

def apply_fill_type(
    op: FinchOperator, *fill_types: AbstractFillFType
) -> AbstractFillFType:
    """
    The fill of the format which results from mapping `op` over tensors whose
    formats have the fills `fill_types`. This is the format of `apply_fill`.
    """
    from .algebra import is_specializable_value

    statics = [f for f in fill_types if is_static(f)]
    if len(statics) == len(fill_types):
        result = op(*(f.value for f in statics))
        if is_specializable_value(result):
            return StaticFillFType(result)
        return DynamicFillFType(ftype(result))
    element_type = op.ftype.return_type(*(f.element_type for f in fill_types))
    for f in statics:
        if op.ftype.is_annihilator(f.value):
            return f.astype(element_type)
    return DynamicFillFType(element_type)

as_fill(fill)

as_fill(fill: AF) -> AF

as_fill(fill: Any) -> StaticFill

Normalize a raw value to a StaticFill, passing an AbstractFill through.

Source code in src/finch/algebra/fill.py

def as_fill(fill: Any) -> AbstractFill:
    """Normalize a raw value to a `StaticFill`, passing an `AbstractFill` through."""
    if isinstance(fill, AbstractFill):
        return fill
    return StaticFill(fill)

cansplitpush(op)

Whether a reduction can split-push through the same operator expression.

Source code in src/finch/algebra/algebra.py

def cansplitpush(op: FinchOperatorFType) -> bool:
    """Whether a reduction can split-push through the same operator expression."""
    return repeat_operator(op) is not None and is_commutative(op) and is_associative(op)

fisinstance(x, f)

Check if x is an instance of f.

Source code in src/finch/algebra/ftypes.py

def fisinstance(x, f: FType):
    """
    Check if `x` is an instance of `f`.
    """
    return f.fisinstance(x)

fixpoint_type(op, z, t)

Determines the fixpoint type after repeated calling the given operation.

Parameters:

Name	Type	Description	Default
op	CallableFType	The operation to evaluate.	required
z	AbstractFillFType	The fill format of the initial value.	required
t	FType	The type to evaluate against.	required

Returns:

Type	Description
FType	The fixpoint type.

Source code in src/finch/algebra/algebra.py

def fixpoint_type(op: CallableFType, z: AbstractFillFType, t: FType) -> FType:
    """
    Determines the fixpoint type after repeated calling the given operation.

    Args:
        op: The operation to evaluate.
        z: The fill format of the initial value.
        t: The type to evaluate against.

    Returns:
        The fixpoint type.
    """
    s = set()
    r = z.element_type
    while r not in s:
        s.add(r)
        r = return_type(op, r, t)
    return r

ftype(x)

ftype(x: FinchOperator) -> FinchOperatorFType

ftype(x: Tensor) -> TensorFType

ftype(x: tuple) -> TupleFType

ftype(x: NumpyBuffer) -> NumpyBufferFType

ftype(x: np.integer) -> FDTypeInteger

ftype(x: FT) -> FT

ftype(x: FTyped[FT]) -> FT

ftype(x: Any) -> FType

Return the corresponding FType for a given object. Recognizes numpy, Python builtins, and Python tuples. Sometimes recognizes types. Override .ftype to customize the ftype of an object.

Source code in src/finch/algebra/ftypes.py

def ftype(x: Any) -> FType:
    """Return the corresponding FType for a given object.  Recognizes numpy,
    Python builtins, and Python tuples.  Sometimes recognizes types.
    Override .ftype to customize the ftype of an object.
    """
    if isinstance(x, FType):
        return x
    if isinstance(x, FTyped):
        return x.ftype
    dtype: Any = None
    if isinstance(x, np.dtype):
        if x.fields is not None:
            assert x.names is not None
            return TupleFType.from_tuple(
                tuple(ftype(x.fields[name][0]) for name in x.names)
            )
        dtype = x
    elif isinstance(x, np.void) and x.dtype.fields is not None:
        assert x.dtype.names is not None
        return TupleFType.from_tuple(
            tuple(ftype(x.dtype.fields[name][0]) for name in x.dtype.names)
        )
    elif isinstance(x, np.generic):
        dtype = x.dtype
    elif isinstance(x, type) and issubclass(x, np.generic):
        dtype = np.dtype(x)
    if dtype is not None:
        if dtype == np.dtype(np.bool_):
            return bool
        if dtype == np.dtype(np.int8):
            return int8
        if dtype == np.dtype(np.int16):
            return int16
        if dtype == np.dtype(np.int32):
            return int32
        if dtype == np.dtype(np.int64):
            return int64
        if dtype == np.dtype(np.uint8):
            return uint8
        if dtype == np.dtype(np.uint16):
            return uint16
        if dtype == np.dtype(np.uint32):
            return uint32
        if dtype == np.dtype(np.uint64):
            return uint64
        if dtype == np.dtype(np.float16):
            return float16
        if dtype == np.dtype(np.float32):
            return float32
        if dtype == np.dtype(np.float64):
            return float64
        if dtype == np.dtype(np.complex64):
            return complex64
        if dtype == np.dtype(np.complex128):
            return complex128
        raise NotImplementedError
    if type(x) is builtins.bool or x is builtins.bool:
        return bool_
    if type(x) is builtins.int or x is builtins.int:
        return int_
    if type(x) is builtins.float or x is builtins.float:
        return float_
    if type(x) is builtins.complex or x is builtins.complex:
        return complex_
    if type(x) is builtins.str or x is builtins.str:
        return str_
    if x is None:
        return none_
    if isinstance(x, tuple):
        T = type(x)
        if hasattr(T, "_fields") and all(isinstance(field, str) for field in T._fields):
            return NamedTupleFType(
                T.__name__,
                [(fieldname, ftype(getattr(x, fieldname))) for fieldname in T._fields],
            )
        return TupleFType.from_tuple(tuple(ftype(elem) for elem in x))
    raise NotImplementedError

is_specializable_value(val)

A constant is only worth specializing on if some operator's identity or annihilator rule can fire against it; see SPECIALIZABLE_VALUES.

Source code in src/finch/algebra/algebra.py

def is_specializable_value(val: Any) -> bool:
    """
    A constant is only worth specializing on if some operator's identity or
    annihilator rule can fire against it; see `SPECIALIZABLE_VALUES`.
    """
    try:
        return any(bool(val == candidate) for candidate in SPECIALIZABLE_VALUES)
    except (TypeError, ValueError):
        return False

isdtype(dtype, kind)

Check if a dtype belongs to an Array API dtype kind.

Source code in src/finch/algebra/ftypes.py

def isdtype(dtype, kind):
    """
    Check if a dtype belongs to an Array API dtype kind.
    """
    dtype = ftype(dtype)
    if isinstance(kind, tuple):
        return any(isdtype(dtype, k) for k in kind)
    if isinstance(kind, str):
        match kind:
            case "bool":
                return builtins.bool(dtype == bool)
            case "signed integer":
                return isinstance(dtype, FDTypeSignedInteger)
            case "unsigned integer":
                return isinstance(dtype, FDTypeUnsignedInteger)
            case "integral":
                return isinstance(dtype, FDTypeInteger)
            case "real floating":
                return isinstance(dtype, FDTypeFloat) and not isinstance(
                    dtype, FDTypeComplex
                )
            case "complex floating":
                return isinstance(dtype, FDTypeComplex)
            case "numeric":
                return isinstance(dtype, FDTypeNumeric)
            case _:
                raise ValueError(f"Unrecognized dtype kind: {kind!r}")
    return builtins.bool(dtype == ftype(kind))

promote_type(T1, T2)

Returns the data type with the smallest size and smallest scalar kind to which both type1 and type2 may be safely cast.

Parameters:

Name	Type	Description	Default
T1	FDType	The first type to promote.	required
T2	FDType	The second type to promote.	required

Returns:

Type	Description
FDType	The common type of the given arguments.

Source code in src/finch/algebra/ftypes.py

def promote_type(T1: FDType, T2: FDType) -> FDType:
    """
    Returns the data type with the smallest size and smallest scalar kind to
    which both type1 and type2 may be safely cast.

    Args:
        T1: The first type to promote.
        T2: The second type to promote.

    Returns:
        The common type of the given arguments.
    """
    if T1 == T2:
        return T1
    S1 = T1.__promote__(T2)
    S2 = T2.__promote__(T1)
    if S1 is not None:
        assert S1 == S2, f"Promotion of {T1} and {T2} is not consistent: {S1} vs {S2}"
        return S1
    if S2 is not None:
        return S2
    raise TypeError(f"Cannot promote types {T1} and {T2}")

repeat_operator(op)

If there exists an operator g such that f(x, x, ..., x) (n times) is equal to g(x, n), then return g.

Source code in src/finch/algebra/algebra.py

def repeat_operator(op: FinchOperatorFType):
    """
    If there exists an operator g such that
    f(x, x, ..., x)  (n times)  is equal to g(x, n),
    then return g.
    """
    return op.repeat_operator()

resolve_fill(fill_type, fill=None)

The fill of a new tensor of a format whose fill is fill_type. A given fill takes the element type of the format, and decides whether the fill of the new tensor is dynamic. Otherwise the fill of the format must be static.

Source code in src/finch/algebra/fill.py

def resolve_fill(
    fill_type: AbstractFillFType, fill: AbstractFill | None = None
) -> AbstractFill:
    """
    The fill of a new tensor of a format whose fill is `fill_type`. A given
    `fill` takes the element type of the format, and decides whether the fill of
    the new tensor is dynamic. Otherwise the fill of the format must be static.
    """
    if fill is None:
        if is_static(fill_type):
            return StaticFill(fill_type.value)
        raise DynamicFillError("A tensor with a dynamic fill needs a fill value")
    value = fill_type.element_type(fill.value)
    if is_dynamic(fill):
        return DynamicFill(value, fill_type.element_type)
    return StaticFill(value)