4 · Advanced¶

Advanced features and patterns

Note

This page is auto-generated from the examples in examples/4_advanced/. Want to play with these examples yourself? Try them in the online playground.

`generic_types.spy`¶

Things to notice:

A generic type is defined with parameters between []: class Pair[T].
Under the hood, Pair is a @blue.generic type factory: Pair[i32] and Pair[str] are two distinct concrete types, resolved at redshift time.
Generic methods work just like regular methods: T is in scope as a type.
Generic types can be nested: Pair[Pair[i32]] is valid.
Structs are passed by value (copied); for reference semantics, use a gc_ptr (see myarray.spy).

examples/4_advanced/generic_types.spy

@struct
class Pair[T]:
    first: T
    second: T

    # Self is the name of the concrete type
    def swap(self) -> Self:
        return Self(self.second, self.first)

    def __repr__(self) -> str:
        return "Pair[" + repr(self.first) + ", " + repr(self.second) + "]"


# This generic class is just syntactic sugar for


@blue.generic
def PairWOSyntacticSugar(T):
    @struct
    class Self:
        first: T
        second: T

        # Self is the name of the concrete type
        def swap(self) -> Self:
            return Self(self.second, self.first)

        def __repr__(self) -> str:
            return (
                "PairWOSyntacticSugar["
                + repr(self.first)
                + ", "
                + repr(self.second)
                + "]"
            )

    return Self


def main() -> None:
    p = Pair[i32](1, 2)
    print(p)

    p2 = PairWOSyntacticSugar[i32](1, 2)
    print(p2)

    q = p.swap()
    print(q)

    s = Pair[str]("hello", "world")
    print(s)

    # nested generic types
    p_of_p = Pair[Pair[i32]](p, q)
    print(p_of_p)

Output:

Pair[1, 2]
PairWOSyntacticSugar[1, 2]
Pair[2, 1]
Pair['hello', 'world']
Pair[Pair[1, 2], Pair[2, 1]]

`myarray.spy`¶

This is one of the most advanced examples of SPy so far. It implements the basics of a generic array type using the low-level primitives introduced in the previous examples.

Things to notice:

Array1d[DTYPE] is a generic struct — see generic_types.spy for an introduction to generic types.
Array1d is a value type (passed by copy), but it holds a gc_ptr to ArrayData which lives on the heap — so copying an Array1d is cheap (just a pointer copy).
This is the current SPy idiom for objects that behave like references: wrap the mutable heap-allocated data in a struct that holds a pointer to it.
__new__ and __make__ are the low-level constructor protocol for structs (see point.spy and smallpoint.spy).
ptr_setbytes and ptr_copy are used for efficient bulk memory operations.

examples/4_advanced/myarray.spy

from unsafe import gc_alloc, gc_ptr, ptr_setbytes, ptr_copy

# Remember that these generic types are just @blue.generic type factories
# parametrized with DTYPE.
# Note that the name of the concrete type is always "Self".


@struct
class ArrayData[DTYPE]:
    length: i32
    capacity: i32
    items: gc_ptr[DTYPE]


@struct
class Array1d[DTYPE]:
    # this struct is a thin zero-cost wrapper around the "__ll__" pointer. The actual data is heap-allocated.
    __ll__: gc_ptr[ArrayData[DTYPE]]

    # note: here, Self corresponds to the concrete type Array1d[DTYPE].

    def __new__(length: i32) -> Self:
        # a pointer towards the array data
        ll = gc_alloc[ArrayData[DTYPE]](1)
        ll.length = length
        ll.capacity = length
        ll.items = gc_alloc[DTYPE](length)
        ptr_setbytes(ll.items, 0, length)
        return Self.__make__(ll)

    def append(self, value: DTYPE) -> None:
        ll = self.__ll__
        if ll.length >= ll.capacity:
            # resize needed - double the capacity
            new_capacity = ll.capacity * 2
            if new_capacity == 0:
                new_capacity = 1
            new_items = gc_alloc[DTYPE](new_capacity)
            # copy existing items
            ptr_copy(new_items, ll.items, ll.length)
            ll.items = new_items
            ll.capacity = new_capacity

        ll.items[ll.length] = value
        ll.length = ll.length + 1

    def __getitem__(self, i: i32) -> DTYPE:
        ll = self.__ll__
        if i >= ll.length:
            raise IndexError
        return ll.items[i]

    def __setitem__(self, i: i32, v: DTYPE) -> None:
        ll = self.__ll__
        if i >= ll.length:
            raise IndexError
        ll.items[i] = v


def main() -> None:
    a_floats = Array1d[f64](10)
    a_ints = Array1d[i32](4)
    a_ints[0] = 1
    a_ints[1] = 2
    a_ints[2] = 3
    a_ints[3] = 4
    a_ints.append(5)
    a_ints.append(6)
    for i in range(6):
        print(a_ints[i])

Output:

`convert.spy`¶

Things to notice:

__convert_from__ is a metafunc that SPy calls automatically as a static method when a value is used where a different type is expected (implicit conversion).
It receives three MetaArgs: the expected type, the actual type, and the value.
It returns an OpSpec describing the conversion function to call.
OpSpec.NULL signals that this conversion is not supported for the given types; SPy will then raise a type error at redshift time.
This mechanism allows user-defined types to integrate with SPy's type system without any built-in support.

examples/4_advanced/convert.spy

from operator import OpSpec


@struct
class CursedStr:
    """
    A str which can be implicitly converted to/from int
    """

    value: str

    @blue.metafunc
    def __convert_to__(m_expT, m_gotT, m_x):
        expT = m_expT.blueval  # expected type
        if expT == int:

            def conv(x: CursedStr) -> int:
                return int(x.value)

            return OpSpec(conv, [m_x])

        return OpSpec.NULL

    @blue.metafunc
    def __convert_from__(m_expT, m_gotT, m_x):
        gotT = m_gotT.blueval  # got type
        if gotT == int:

            def conv(x: int) -> CursedStr:
                return CursedStr(str(x))

            return OpSpec(conv, [m_x])

        return OpSpec.NULL


def inc(x: int) -> int:
    return x + 1


def main() -> None:
    s = CursedStr("41")
    print(inc(s))

    s2: CursedStr = 123
    print("Hello " + s2.value)

Output:

42
Hello 123

`mytuple_contains.spy`¶

Implement in for heterogeneous tuple-like structs, specialized at compile time.

mytuple is a @blue.generic factory: mytuple[str, i32, str] creates a concrete @struct with fields _item0, _item1, _item2. Its __contains__ is a blue.metafunc, so it runs at redshift time and can specialize on the static type of the searched value:

it looks at m_v.static_type, the static type of the left operand of in;
has_match (blue recursion) checks whether ANY tuple field has that type; if none does, the result could never be True, so we raise a compile-time TypeError instead of silently returning False;
build (blue recursion again) unrolls a chain of comparison functions, one per field whose type matches; fields of a different type are skipped entirely, they don't even exist in the generated code.

For example, given t: mytuple[str, i32, str], after redshift:

42 in t         # i32: only _item1 has type i32, so this is just
                #   t._item1 == 42

"world" in t    # str: _item0 and _item2 match, so this becomes
                #   t._item0 == "world" or t._item2 == "world"

with no loop, no type dispatch and no boxing left at runtime.

Run spy redshift examples/4_advanced/mytuple_contains.spy to see the generated code.

examples/4_advanced/mytuple_contains.spy

from operator import OpSpec


@blue.generic
def mytuple(*items_T):
    @blue
    def get_fields():
        """
        Return a dict like {
            "_item0": int,
            "_item1": int,
        }
        """
        fields: dict[str, type] = {}
        for i in range(len(items_T)):
            fname = "_item" + str(i)
            T = items_T[i]
            fields[fname] = T
        return fields

    @struct
    class _tup:
        __extra_fields__ = get_fields()

        @blue.metafunc
        def __contains__(m_self, m_v):
            T = m_v.static_type

            @blue
            def has_match(idx):
                if idx == len(items_T):
                    return False
                if items_T[idx] == T:
                    return True
                return has_match(idx + 1)

            if not has_match(0):
                raise TypeError(
                    "argument is not of any of the tuple's element types"
                )

            # build the runtime comparison chain recursively for each field
            # that matches the type
            @blue
            def build(idx):
                if idx == len(items_T):
                    def check_none(self: _tup, v: T) -> bool:
                        return False
                    return check_none

                rest = build(idx + 1)

                if items_T[idx] == T:
                    attr = "_item" + str(idx)

                    def check_or_rest(self: _tup, v: T) -> bool:
                        if getattr(self, attr) == v:
                            return True
                        return rest(self, v)
                    return check_or_rest

                return rest

            return OpSpec(build(0), [m_self, m_v])

    return _tup


def main() -> None:
    t = mytuple[str, i32, str]("hello", 42, "world")
    print("world" in t)
    print("foo" in t)
    print(42 in t)
    print(43 in t)
    # `3.14 in t` would not even compile: no field has type f64

Output:

True
False
True
False

`type_name_and_fqn.spy`¶

Things to notice:

SPy types carry several name attributes at different levels of qualification
__full_fqn__ includes the module path; __fqn__ and __qualname__ are shorter; __name__ follows Python conventions
For generic types, the type argument is part of the name (e.g. Foo[i32]).
This is useful for debugging, error messages, and metaprogramming.

examples/4_advanced/type_name_and_fqn.spy

@struct
class Foo[T]:
    pass


def main() -> None:
    print("__full_fqn__ ", Foo[i32].__full_fqn__)
    print("__fqn__      ", Foo[i32].__fqn__)
    print("__qualname__ ", Foo[i32].__qualname__)
    print("__name__     ", Foo[i32].__name__)

Output:

__full_fqn__  type_name_and_fqn::Foo[i32]::Self
__fqn__       type_name_and_fqn::Foo[i32]
__qualname__  type_name_and_fqn::Foo[i32]
__name__      Foo[i32]

`annotated.spy`¶

Things to notice:

Annotated is a generic blue value (not a type) that wraps a type plus metadata.
_extra is captured as a blue interp_tuple — a tuple known entirely at redshift time.
__convert_to__ is a metafunc that fires when the value is used where a type is expected.
This pattern shows how SPy can implement PEP 593-style annotations as a library, without any built-in support.

examples/4_advanced/annotated.spy

from operator import OpSpec
from __spy__ import interp_tuple


@blue.generic
def Annotated(_T: type, *_extra):
    @struct
    class Ann:
        @property
        def T(self) -> type:
            return _T

        @property
        def extra(self) -> interp_tuple:
            return _extra

        @blue.metafunc
        def __convert_to__(m_expT, m_gotT, m_x):
            expT = m_expT.blueval  # expected type
            if expT == type:

                def get_T() -> type:
                    return _T

                return OpSpec(get_T, [])

            return OpSpec.NULL

    return Ann()


MyInt = Annotated[int, "hello"]


def main() -> None:
    print("MyInt.T, MyInt.extra:")
    print(MyInt.T)
    print(MyInt.extra)
    print("")

    # convert MyInt to type
    print("converting MyInt to type:")
    T: type = MyInt
    print(T)

    # the following currently doesn't work because we do a hard-check that `type(MyInt)
    # is type`. We could modify the code to check that MyInt can be CONVERTED to `type`
    # x: MyInt = 5

Output:

MyInt.T, MyInt.extra:
<spy type 'i32'>
<spy `__spy__::interp_tuple` object at <ADDR>>

converting MyInt to type:
<spy type 'i32'>

`unroll_nested_loops.spy`¶

Programmatically generate a nested loop of arbitrary depth.

Given a SHAPE tuple of length N (known at compile time), we want to iterate over all the N-dimensional indices it describes, e.g. for SHAPE == (3, 2) the indices are (0,0), (0,1), (1,0), (1,1), (2,0), (2,1).

The tricky part is that N is not fixed: we want to write the code once and let the compiler specialize it to a specific SHAPE. This example demonstrates how to do that in SPy by combining two features:

@blue.generic for compile-time specialization on blue arguments;
@force_inline so that doppler physically inlines each level of recursion into the caller, leaving a flat nest of real for loops with no residual function calls.

The blue recursion in nested_loop terminates when we reach k == len(shape) and return inner.

Run spy redshift examples/unroll_nested_loops.spy to see the generated code.

For SHAPE == (3, 2) is equivalent to:

    def ndindex() -> None:
        idx = []
        for i0 in range(3):
            idx0 = idx + [i0]
            for i1 in range(2):
                idx1 = idx0 + [i1]
                print_idx(idx1)

The actual output is pretty ugly though. The following is a manually edited version to underline the important part, i.e. the two nested while loops:

❯ spy rs --linearize examples/unroll_nested_loops.spy

def ndindex() -> None:
    idx: ... = `_list::list[i32]::new`()
    [...]
    _$iter0$0: ... = `_range::range::__fastiter__`($v2)
    while `_range::range_iterator::__continue_iteration__`(_$iter0$0):
        [...]
        _$iter0$0$0: ... = `_range::range::__fastiter__`($v9)
        while `_range::range_iterator::__continue_iteration__`(_$iter0$0$0):
            [...]
            `unroll_nested_loops::print_idx`(idx$0$0$0)

examples/4_advanced/unroll_nested_loops.spy

from __spy__ import force_inline


SHAPE = (3, 2)


def print_idx(idx: list[int]) -> None:
    """
    Just a workaround because we cannot do print(*idx) yet
    """
    s = ""
    first = True
    for i in idx:
        if first:
            s = str(i)
            first = False
        else:
            s = s + " " + str(i)
    print(s)


@blue.generic
def nested_loop(shape, k):
    """
    Generate the body of the k-th level of the loop nest.

    When k == len(shape) we hit the base case and emit the loop body.
    Otherwise we emit a `for` loop over range(shape[k]) whose body recursively
    calls `nested_loop[shape, k+1]` -- which, being blue, is resolved at
    compile time into the next level.
    """
    if k == len(shape):

        @force_inline
        def inner(idx: list[int]) -> None:
            # here we should do something with the given element. Just print the indices
            # for demo purposes
            print_idx(idx)

        return inner

    else:

        @force_inline
        def loop(idx: list[int]) -> None:
            for i in range(shape[k]):
                nested_loop[shape, k + 1](idx + [i])

        return loop


def ndindex() -> None:
    idx: list[int] = []
    nested_loop[SHAPE, 0](idx)


def main() -> None:
    ndindex()

Output:

4 · Advanced¶

generic_types.spy¶

myarray.spy¶

convert.spy¶

mytuple_contains.spy¶

type_name_and_fqn.spy¶

annotated.spy¶

unroll_nested_loops.spy¶

`generic_types.spy`¶

`myarray.spy`¶

`convert.spy`¶

`mytuple_contains.spy`¶

`type_name_and_fqn.spy`¶

`annotated.spy`¶

`unroll_nested_loops.spy`¶