Proposal: Generalized Fat Pointers (a.k.a. type "closures")

The basic idea is to generalize the existing slice functionality in Zig (which is beautiful), to work similarly well for ND arrays and other simply-indexed types.

Currently Following proposal BLAH BLAH, we'll be referring to a slice as *[var]T, rather than []T.

The ideas of this proposal are as follows:

TODO: Add sentinel-terminated strings

Introduction

What is a type-closure? Well, it's equivalent to a fat-pointer.

Specifically, it enables runtime-access to a type based on

stores internally a pointer to a partially runtime-erased type, as well as fields containing the erased parameters:

const ExampleType = struct(N: usize) { // impl. omitted };

const FatPointerExample = struct {
   ptr: *ExampleType(erased)
   N: usize
};

We call this a "type closure" because we are effectively closing over the runtime-erased parameters

If we had the ability to hook into primitive calls such as field access, this might look like:

fn __get_field(self: *FatPointerExample, field_name: []u8) {
   return @cast(self.ptr, *ExampleType(self.N)).__get_field(field_name);
}

Of course, this is garbage since it's a circular description. However, the spirit is correct. This would look of __get_field in ExampleType and then use the

The simpler way is to say that ABI-wise, the parameters are broken out into each method, like implicits basically:

ExampleType.__get_field<N: usize>(self: *Self, field_name: []u8)

// HMMM -> So type parameters automatically give us implicits, huh? // Feels useful...

As noted in the previous proposal, *ExampleType(erased) is an erased type, which must be discharged to an appropriate method to be used.

Type closures expose the same interface/operations* as a pointer to a fully concrete (comptime-determined) type, but they allow the type parameters to be known only at run-time.

Specifically, field and array access within the

Intuition

  • any is comptime-specialized (monomorphizing; input must be comptime-known)
  • var is runtime-parameterized (not monomorphizing; input must be runtime-known)
  • erased is runtime-erased (not monomorphizing; input does not need to be known at all, although debug builds will track it for type checks)

Of course, parameters are runtime-parameters, unless labelled with comptime or inline. Types are completely fixed, or allowed to vary in fixed patterns, as above.

There are some cases where we'd like to have both comptime specialization and runtime parameterization. This is the recommended usage of the inline parameter from TODO: insert proposal number

Extension support var pattern for type parameters

(This would be useful for dynamic dispatch, maybe...)

How do we support this? Is it just a type ID? Can we use the type as a constructor? Almost certainly not! (at least not on the stack)

It seems like this would be enough to support most typecase usage though...

Hmm, we almost always operate on these kind of things via pointers and then just cast the pointer to indicate what we're doing... We can do that in Zig, right?

The only thing missing is the automatic expansion of the type table! for... over an open typeunion (note that we never need this in userland for error, but we do need it for types)

Need to think about how this relates to refinement types, etc., too... But it feels like it should be homogeneous with our existing union/subset types in Zig (errors, especially) -> The subset operation is a refinement of the error/type types -> which is why type(any) is just a pun. It's not a real parameter, it's a pun for the superset

Examples

The basic idea is that a pointer to a type expression containing var metavariables is a fat pointer for the equivalent type.

For existing slices, this means we get a uniform syntax for ND-arrays:

*[var]T           # a slice of T,    i.e. a 1D array with runtime-known dimensions
*[var][var]T      # a 2D-slice of T, i.e. a 2D array with runtime-known dimensions

*[var][5]T        # a slice of [5]T
*[var]*[5]T       # a slice-of-pointers to fixed-size arrays [5]T
*[var]*[var]T     # a slice-of-slices

Here's some cases of incomplete arrays which might be familiar from C:

*[var][5]T        # a pointer to an array of runtime-known outer dimension
*[5][var]T        # a pointer to an array of runtime-known inner dimension 
*[erased][5]T     # a pointer to an array of       unknown outer dimension
*[5][erased]T     # a pointer to an array of       unknown inner dimension  (cannot be accessed anywhere without a cast, except for [0][0])

If we say that *[var]T is shorthand for StridedArray(T, var, 0).

In theory, we could even support arrays with runtime strides.

*StridedArray(T, 5, var)     #

This is useful, for instance, for efficiently accessing data in Array-of-Structs layout without having to make a potentially expensive conversion to Struct-of-Arrays.

Interpretation: Fat Pointers

Note that storage is predictable. A slice and array always store their contained type contiguously.

This is because a slice is a runtime-closure over the array type (i.e. a fat pointer to an object of a comptime-incomplete type).

Extension: Supporting user-defined types

Note: this may not actually be needed, but can be nice, e.g. for threading variables through a user-defined type (including the manually-packed version of the above types)

Most restrictive:

  • memory layout must be totally defined (may only use parameters via a fat pointer, not an inline field)

Less restrictive:

  • memory offsets must be defined, size can be runtime-determined (this is equivalent to C's VLA members) -> SizeOf requires some computation

Least restrictive:

  • Any inline members allowed, including inline type closures (aka dynamically-sized types) -> Computation for field access can become arbitrarily expensive

TODO: Re-phrase from the types that are allowed to the field accesses (and size calculations) that are allowed via a type-closure.

Runtime Tensors

*[[var]usize]T  # an ND-tensor (array with dynamic _number_ of dimensions)
                # (this pun is not perfect)
*[var...]T      # (alternative syntax)

Maybe instead:

TODO: Describe how type-dependencies work here...

As a primitive, StridedTensor would look like this:

const StridedTensor = struct(N: usize, dims: [N]usize, strides: [N]usize) // ...

Note that this also uses type-constraints in its constructor.

This would be the canonical type generated

&arr[..][..].foo.bar

fn(x: *StridedTensor(f32, var N, var dims, var strides)) {
   x[1][5][6]
}

Extension: Runtime type representation in the form of typeid

Hmm what to put here

Comment

It's worth mentioning that the *[var]T syntax for slices also generalizes more consistently to multi-dimensional arrays. For instances, it intuitively distinguishes *[var]*[var]T (a slice of slices of T) and *[var][var]T (an array with 2 runtime-known dimensions, the 2D equivalent of a slice).

In fact, if we view existing slices and arrays as members of a single, general type family:

const Tensor = struct(T: type, N: usize, dims: [N]usize, strides: [N]usize) ...

TODO: How do we parameterize N correctly as inline here?

Then the existing 1D arrays and slices are just comptime-specialized subsets of this type.

Default-packing for tensors: const DefaultTensor = struct(T: type, N: usize, dims: [N]usize) Tensor(T, N, dims, calculate_strides(T, dims));

From a technical point of view, in order to keep unification tractical, these "functions" should be patterns. In which case they allow us to do the straight-forward matching of the kind envisioned here.

Existing slices: *[var]T = *DefaultTensor(T, 1, {var}) Existing arrays: [N]T = DefaultTensor(T, 1, {N})

This means that a generic ndarray is just: *DefaultTensor(T, var, var)

  • Tensor(T, 1, var, default)
  • Tensor(T, 2, var, default)

*Tensor(T, var, var, default)

*Tensor(T, var N, var dims, zero_vector(N)) # This one is always zero, so no strides required - calculated OTF

*Tensor(T, var dims) # This one requires a runtime set of strides (at least N-1 of them)

dims is a [var]usize

*StridedTensor(T, var dims: [var]usize, var strides: [var]usize)

*StridedTensor(T, var N, var dims, var strides) *StridedTensor(T, var N, var, var) This is kind of Tensor(T, var dims): *[[var]]T This is kind of StridedTensor(T, var dims): *[[var]]padding(T)

Hmmm, can the strides of a tensor just be taken to be a parent(U) T, actually? Yes

The only exception is if I also want to include offsets in a dimension (as a view)

such as [1..10][x..y]

In that case, it behaves like *[var] parent([N] parent(U) T) [var] parent(U) T

On the one hand, consistent with the rest of the type system. On the other, so weird...

Is there a "tensor-level" parent that would help?

Yes, actually...

* parent([var][var]U, var offset) [var][var] parent(U) T

So a strided tensor is actually:

* parent([[var]] erased U) [[var]] parent(erased U ++ size U) T

Holy fuck that is obtuse and confusing :(

We either need short-hand, to reduce this to just:

* parent(var) [[var]] parent(var) T

(where the parent variables are completely automatically handled behind-the-scenes,

including their erasure down to a single operation)

Or we need to find another way to go about this...

*[[var]] parent(V) parent(U) T

Still need to get nesting right, though

*[[var]] parent(parent(V) U) T

This shows one major problem: parameter names are not required to match, and can rapidly become ambiguous...

Another problem is that we don't distinguish types at all

Maybe those should be required to be explicit

This actually lets us uniformize with the existing parameter syntax:

x: List(any T: type, any N: usize)

In this way, var really wouldn't be required, it would just be a hole

This is nice, but also very hard to read...

Actually, if omit the var it's not so bad...

*StridedTensor(T: type, dims: [N: usize]usize, strides: [N: usize])

Nvm, it's bad:

fn foo(x: *StridedTensor(T: type,

		   dims: [N: usize]usize, 
		   strides: [N]),
 y: *StridedTensor(T: type, any:[N: usize]usize, any:[N])) *StridedTensor(T: type,
		     						dims: [N: usize]usize, 
		  						strides: [N: usize]))

fn foo(x: *StridedTensor(any T: type, any N: usize))

We should think about alternative ways to relate these "families"...

because having everything depend on this verbose-ass parameterization/constraint system

is really, really, fragile

and if we allow custom strides: *Tensor(T, var N, var dims, var strides)

strides is by default: rev(cumprod(dims)) .* SizeOf(T) {MN, N, 1} We need the strides to be able to do element lookup, but we want the dims to be able to do in-bounds checks (and also know when to stop iterating) -> inline functions mean that the MN should be lifted out of the loop, so it's fine for us to treat these strides as "extra" bytes (padding)

There are additional extensions that appear in other languages, such as:

  • supporting de-structuring of tuples/arrays/structs, or -> this would be required to support variable-length arguments and mixed comptime/var arguments within the same type family (Tensor is a great example)

  • pattern-based type aliases (which are a constrained version of the "inverse" problem presented in XXXX) -> These would allow the creation of "simple aliases" that appear frequently in zig code, such as Array(T) = NDArray(T, 1) -> The basic rule is that each input parameter must make it into the destination function "un-transformed" in at least one parameter location. For example, Example(N) = Example2(N, N * N) is a valid pattern, since N makes it unmodified into the first parameter.

    This allows us to say something like:

    const 2DArray = struct(T:type, N: usize, M: usize) Tensor(T, 2, .{N, M}, .{M * @SizeOf(T), @SizeOf(T)});

    Support for some limited (pattern-based) type aliases + "specialization-transparent" arrays/tuples/structs would enable the following:

    This would allow us to make equational aliases, such as struct 2DArray(T: type, N: usize, M: usize) = Tensor(T, 2, .{N, M}, .{M * @SizeOf(T), @SizeOf(T)})

    Roughly speaking: [var N][var M]T = Tensor(T, 2, .{N, M}, .{M * @SizeOf(T), @SizeOf(T)}) [var N][var M]T = Tensor(T, 2, .{N, M}, .{M * @SizeOf(T), @SizeOf(T)})

    (the syntax, of course, would likely differ)

    -> General pattern-based aliases would prevent us from having to hard-code these aliases just for the array/tensor types.

    -> The other "escape hatch" is to provide user-accessible casting support, maybe?