Proposal: Support function parameter type constraints/wildcards

[topolarity]

Motivation

The goals of this proposal are to:

1. Make generic function prototypes more self-documenting
2. Encourage the enforcement of simple type constraints at compile-time
3. Make the use of runtime and comptime polymorphism more symmetric, in terms of safety and syntax

The key mechanism I propose is a limited, predictable form of pattern matching for types in function parameters, which is intended to allow straightforward enforcement of type constraints at compile-time and run-time.

Proposal

Part A: Introduce any T as a type constructor wildcard

Pattern matching at compile-time amounts to constrained comptime polymorphism. This can make it easier to infer function behavior from its prototype alone.

Compare the monomorphic version of a basic append function versus its generic counterparts:

// Monomorphic
fn       u8_append(l: ArrayList(u8), x: u8) // <- Fully-monorphized, clear types

// Compile-time Polymorphic
fn generic_append1(l: anytype, x: anytype)  // <- Option 1: Have to guess or read implementation
fn generic_append2(comptime T: type, l: *ArrayList(T), x: T)  // <- Option 2: Better, but this is _less_ convenient
                                                              //    at the call-site, discouraging use!

These functions are intended to generalize u8_append by allowing variance over the inner type parameter u8. However, the programmer must make a difficult choice: Either they write generic_append1, providing an uninformative function signature which support convenient type inference, or they write generic_append2 with an informative function signature and automatically-enforced constraints, but which requires explicitly passing in the correct type separately.

Wouldn't it be nice if we could just express this variance directly? We'd ideally like to be able to write functions like:

fn append(l: *ArrayList(any), x: any) void      // More readable
fn append(l: *ArrayList(any T), x: any T) void  // Even better, fully constrained!

As you can see, by allowing implicit equality constraints between wildcards, this also provides a simple declarative syntax for expressing certain parameter type requirements, such as when two types must agree, and allows expressing some parameter-dependent return types more directly (avoiding complex @TypeInfo(TypeOf(param)) expressions in some cases).

fn foo(a: any T, b: any T, c: any U, d: any U) Tuple(.{T,U})  // a & b must share type, c & d must share type

Changes required

At first glance, this inference appears to be a basic unification problem. However, the proposal above is incompatible with Zig’s existing fn(…) type type constructors, since multiple functions may return instances of the same struct {…} definition and also perform non-invertible transformations on their parameters.

So naively adding pattern matching like this for fn(…) type is undecidable for the compiler, and even if it weren’t, it would be confusing and unpredictable to the user, given multiple overlapping “interfaces” to one underlying type.

The problem here is that type objects have no canonical constructor function, whose parameters we could associate with the type and use for unification. To enable this, we take inspiration from #1717 and borrow the fn syntax for struct.

A struct block can now take its own set of parameters:

const FixedArray = struct(T: type, N: usize) {
  contents: [N]T
};
var x: FixedArray(u8, 5) =  ... 

FixedArray is called a type constructor function (a type(...)), distinguishing these from fully-constructed types (e.g. FixedArray(u8, 5) or u8) and existing function-returning types (fn(…) type).

The key restriction that makes this proposal possible is that we only allow inferring parameters to type(...) functions, not to fn(...) type functions. In the compiler, a constructed type saves the parameters provided to its type(...) function, so that these can be used for inference at the call site to a function as above.

In general, a type(A,B,C) can be used like a fn(A,B,C) type, except that it supports type inference. With this restriction, the inference problem is decidable for the compiler - it becomes “word matching”, with the input type containing no metavariables. It’s also intended to be easy to understand for the user (feedback welcome, of course).

Extending to union

For completeness, union will need the same treatment as struct, but we already have a union(tag) syntax for tagged unions.

Thankfully, the existing syntax isn't incompatible with a naive solution, although it is a bit awkward:

// Tagged
const Result = union(enum)(T: type) {
    ok: T,
    not_ok: void,
};
// Untagged
const SpecialEnum = union(T: type) {
    default: T,
    int: u32,
    float: f32,
};

Any suggestions to improve this syntax are more than welcome.

Backwards compatibility

Existing usage of fn(...) type would be backwards-compatible with this change, but these type objects are not type(...) functions, so they cannot be used for inference. To support inference, the module author has to expose a type(...) function, either by defining it at the top-level or, less commonly, returning one from a function unevaluated.

Part B: Runtime-Erasure via erased T

As an extension to this proposal, we can support erased T to indicate an inferred parameter that should be constrained but not used to specialize the function. Note that this is the typical pattern used for runtime polymorphism.

To put some familiar examples in the new terminology:

• C’s use of void * as a run-time polymorphic type is really a * erased T
• Arrays of unknown size, instead of being written [*]T, can be viewed as *[erased]T.

In each of these cases, the types pass through a function which “forgets” a certain part of the concrete type it operates on, and then delegates to other functions implemented on the concrete (fully-specified) type.

Mechanics

When erased T is used as a wildcard pattern for a function parameter, any constraints on T are still enforced statically at the call-site, as usual. However, T is not allowed to be used inside the function, and the function is not compile-time specialized (i.e. monomorphized) on T.

This feature is useful, for example, for ensuring at compile-time that multiple parameters are type-compatible, without specializing a function at comptime:

fn accumulate(a: *LinkedList(erased T), b: *fn(*erased T) u64) u64

This can also be used to make sure that a method dispatch table (i.e. vtable) is compatible with an object it is used with. It also makes the use of run-time vs. comptime polymorphism more symmetric.

Here’s an example, where the “vtable” is a single function pointer:

// run-time polymorphic
fn accumulate(a: *LinkedList(erased T), b: *fn(*erased T) u64) u64
// comptime polymorphic
fn accumulate(a: *LinkedList(any T), comptime b: fn(any T) u64) u64

As you’d expect with run-time polymorphic interfaces, erased types live behind pointers since their sizes are unknown. Such a pointer must be cast to a non-erased type before being dereferenced.

Note: In theory, it may be possible to dereference and use an erased type for a limited set of accesses/operations, provided that the operation is solely a function of its non-erased parameters. However, such behavior is considered out-of-scope for this proposal.

Debug Safety

I believe this opens the door to additional run-time safety in debug builds: For instrumentation, the compiler should be able to replace an erased pointer with a fat pointer describing its erased parameters. Then, when a specialized function fn(x: *A) is cast to an erased function pointer *fn(x: * erased T), it can be wrapped in a check that inspects the fat pointer information to make sure that the underlying type is A.

Appendix: Type constructor functions as variables ("Sandwich" Inference)

"Sandwich" inference is when one of the type constructor functions in the signature is a metavariable to be inferred.

The sandwich part refers to the fact that the variables can appear in-between constant terms, rather than just at the top-most level of parameters. This can lead to pretty strange and complex patterns:

fn(x: any L(any T, any N), x: T[N]) u32
fn(x: any T(u32, u8)) u32 
fn(x: ArrayList(any T(u32, u8))) u32 

This inference is perfectly decidable as a unification problem, but these patterns often feel more confusing than helpful. For that reason, it may be preferable to forbid sandwich inference, at least until a clear use case arises.

Appendix: Syntax and keywords

In order to disambiguate between inferred parts of a term versus constants, we should require erased/any for every appearance of a metavariable T. Of course, a metavariable T should never shadow a constant.

The remaining details of the syntax are much more debatable, in particular the usage of erased/any. There are other variations we might consider, as well:

                       Option 1       Option 2        Option 3     Option 4
Comptime specialized:      any T | comptime any T |       any T |    var T
Run-time      erased:   erased T |          any T | undefined T | erased T

I've been preferring Option 1 on the grounds that Option 2 is too verbose and Option 4 is misleading by labelling comptime specialization with the var keyword. Option 3 is a good candidate as well, since it doesn't require introducing a new keyword, but it seems unintuitive to have a potentially-constrained metavariable labelled with undefined, even if it's true that you're not allowed to use it within the function.

Of course, this discussion is closely related to #5893

If this proposal is accepted, we might also want to consider an alternative slice syntax such as *[var]T, since many newcomers to the language seem to be suprised that []T is actually a reference type.

Appendix: @TypeInfo/@type

@TypeInfo/@Type would be supported exactly as they are today. In particular, they would not support creating a type(...) function.

There are places in the standard library (e.g. enums.zig, mem.zig, meta.zig) that use @Type today. These use cases would benefit from a built-in @TypeFunction() which converts a fn(...) TypeInfo function into a type(...) function, if inference is desired for these families of reified types.

[ghost]

Over in #9260, there was a lot of discussion about how to make something like ArrayList(any T) work within the current language semantics. The best insight was that, with comptime functions being memoized and structs being named after the function they are returned from, the job is almost done for us. An ArrayList(i32) should have exactly that as its @typeName, and matching it against ArrayList(any T) should be trivial. Except that ArrayList(T) is implemented as an alias of ArrayListAligned(T, null), which is its actual type name, and matching that against ArrayList(T) remains a hard problem in the general case. So far nobody seems to have figured out a complete solution to this.

Introducing proper parametric types is a possible way out, but then we have two different systems for generic types: One can still return anonymous types from comptime functions, which gives introspection, reification and custom @compileErrors, but no inference. Or one can use the new parametric types, which support inference and type constraints, but no complex logic. We end up with two mutually incompatible solutions that each solve half of the problem. That is not a good place to be in, IMHO.

[topolarity]

Over in #9260, there was a lot of discussion about how to make something like ArrayList(any T) work within the current language semantics.

Thanks for the reference! I hadn't seen that issue yet. Reading through it was informative for the challenges of supporting this kind of inference without explicitly separating type constructor functions syntactically.

One "automatic" equivalent for this proposal would be to enable type-inference only for the inner-most function including a @Type or struct { ... } expression. This would be functionally the same without needing to introduce struct(...). I left this alternative out of the proposal, thinking it was too implicit/incomplete to be intuitive, but perhaps it's worth considering

Introducing proper parametric types is a possible way out, but then we have two different systems for generic types: One can still return anonymous types from comptime functions, which gives introspection, reification and custom @compileErrors, but no inference. Or one can use the new parametric types, which support inference and type constraints, but no complex logic. We end up with two mutually incompatible solutions that each solve half of the problem. That is not a good place to be in, IMHO.

I definitely agree that adding type(A,B,C) as an alternative to fn(A,B,C) type is a syntactic/conceptual overhead that comes with a significant cost.

On the other hand, I'm not sure that I agree that there's a feature gap between fn(...) type and type(...), outside of parameter inference. Fully-concrete types are still just type, supporting introspection, reification, etc. Meanwhile, parametric families of types (type(A,B,C) and fn(A,B,C) type) do not support introspection, but do support unrestricted usage/processing of their parameters (since functions can be used inside a type(...) body), as well as reification if we include @TypeFunction.

Can you spot a counter-example of something that's supported by fn(...) type and not type(...)?

[ghost]

Can you spot a counter-example of something that's supported by fn(...) type and not type(...)?

I was thinking along the lines of additional constraints and comptime checks on the type parameter. But you're right, those can be implemented with helper functions, or even inline:

const Foo = struct(T: type) {
    value: if (meta.trait.isNumber(T)) T else @compileError("Not a number!"),
};

One thing you can't do with parametric structs is add or omit fields depending on the inputs, but I don't think this is used much anyway. There might be more, but I can't think of anything right now.

---

I'm now sort of in favor of this proposal. The idea to build a generic type system from first-class types and compile-time code execution is both clever and powerful, but it creates a lot of dark corners semantically, and makes many things that work very simply in other languages either difficult or impossible. From a usability perspective, having a simple parametric type system, and maybe interfaces, would remove all magic from 95% of the use cases. Personally, I think that would be an appropriate power-complexity tradeoff for a language that aims to be a C replacement. But this is also a fairly significant change, which may have ripple effects throughout the type system. I'm not sure whether it isn't too late for that.

[topolarity]

Thanks for the input so far!

To continue fleshing things out, I wanted to add another potential extension to this proposal.

Part C: Generalized "Fat" Pointers

The main idea here is that *T(var, ...) represents a "fat" pointer to an object of underlying type T(N, ...), where N is not compile-time known. This allows us to be runtime-polymorphic with respect to this type parameter.

This entails a syntax for slices: Since [N]T is really just syntax sugar for a type like Array(T, N), a slice is really just *[var]T or *Array(T, var).

With that connection in mind, we can generalize this to lots of other fat pointer types, as follows:

Extending slices to multi-dimensional arrays

With the explicit * in the new slice syntax, slices smoothly generalize to higher dimensions. In particular, they behave as patterns, just like the type patterns discussed above, and can even include partially-fixed dimensions.

Example	New Syntax	Old Syntax
1D Slice	*[var]T	[]T
2D Slice	*[var][var]T	No equivalent
Slice-of-slices	*[var]*[var]T	[][]T
Partially-fixed 2D Slice	*[var][4]T	[][4]T
Partially-fixed 2D Slice	*[4][var]T	No equivalent

This can even be generalized to tensor types by introducing a most general n-dimensional array type:

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

Notice that this "parent" type can parameterize all of the above types. Furthermore, it permits us to have slice types with a dynamic number of dimensions:

Example	New Syntax	Old Syntax
N-D Slice	*Tensor(T, var, var)	No equivalent
Strided N-D Slice	*StridedTensor(T, var, var, var)	No equivalent

N-D slices are useful for certain varieties of scientific computation and statistical computation (for instance, computing the variance along an axis, performing a generalized matrix mult./sum, or dynamically re-shaping structured data)

Strided N-D slices support "views" of N-D slices. Such a type would be generated when slicing n-dimensional arrays (e.g. &x[3..5][1..2]) or when referencing array-of-struct (AoS) members through such a view (e.g. &x[..].foo).

As one would expect, these behave as one big parameterized type "family". StridedTensor is the "true" underlying type, and more specific types, such as [N]T or [M][N]T, are all patterns specified over this most general type. This means that [N]T can be passed to a function accepting a StridedTensor, for instance.

The above type aliases for arrays/tensors would all be "built-in" to Zig, but it's reasonable to ask how similar "aliases" can be defined for user-defined types. Here's a gist with some details

Fat pointers to user-defined types

This also provides a method to support C-style "flexible array members" in a safe way (see #173):

const FlexibleType = struct(N: usize) {
    foo: f32,
    bar: [10]u32,
    flex: [N]f32,
};

const foo = fn(x: *FlexibleType(var)) void {
   // impl...
}

or to enforce invariants between arrays/slices within a type:

const ConstrainedArrays = struct(N: usize, M: usize, K: usize) {
    M1: *[N][M]u32,
    M2: *[M][K]f32,
};

The ABI implications for supporting runtime type parameters like this are very significant, in particular because it can mean that offset/size calculations require computation, slowing down field access significantly.

In order to control this, it seems reasonable to enforce:

1. Only usize type parameters can be made var when declaring fat pointers, *T(var)
2. T must be an extern struct
3. Within the struct definition:
   1. The var'd parameter may only impact the size of the last field in the struct definition
   2. The var'd parameter can be passed to any number of other fields whose size is invariant to the parameter (i.e. fat pointers)
   3. The var'd parameter cannot be passed through any user-defined functions

Just as with slices/arrays, a raw T(var) cannot be created on the stack. A fully comptime-known T(N) can be stack-allocated, while allocation on the heap can give us a *T(var). Here's how casting/calling works:

Function Type	Permitted Inputs
fn(*T(var)) ...	*T(N), *T(var)
fn(*T(N)) ...	*T(N), *T(var)†
fn(*T(any N)) ...	*T(N)

† The cast from *T(var) to *T(N) is debug-checked at run-time

Note that these are the same rules that would be used for casting slices/arrays, as well.

Other Extensions

It might make sense to consider expanding var to support non-usize data, in particular a run-time representation of a type. For instance * var T would provide "typeid"-equivalent behavior, similar to C++'s std::any.

This still needs more careful thought before it’s ready to be considered as a proper proposal, though. Furthermore, if we do expand var to include non-usize type parameters, I'm a bit unhappy with the fact that the proposed syntax doesn't make it easy to infer types of the var "holes”.

Are these generalizations worth it?

Generalized slices

Multi-dimensional slice types, partially-constrained arrays, and n-dimensional tensors appear to bring high value for structured computation, esp. smoother inter-op with heterogeneous targets (including SIMD, GPU, etc.).

For these types, the syntax change is relatively small and intuitive. Furthermore, there is a clear boundary to the syntax/feature: "var in a type means dynamic array type"

Fat pointers to user-defined types

On the other hand, expanding this to user-defined fat pointers seems comparatively limited in value, at least without a use case on hand. I left it included here for completeness, particularly w.r.t. C inter-op, but it's unlikely to meet Zig's standards for complexity/power.

typeid-like functionality seems like it could have its use cases for message passing or interpreters, but I'll allow others to comment on the importance of that.

On the optimistic side of things, any ideas that allow a user to explicitly opt-in to a broader range of fat-pointers, with predictable performance trade-offs, may make this feature more appealing (perhaps a re-parameterization of @field or a dedicated @dynfield, when the offset is not statically known). Please contribute if you have any ideas!

[topolarity]

Since there are quite a few concepts in play now, here's a quick glossary in plain English.

Any "hole" in a type pattern has 3 different "ABI modes" that affect casting and specialization:

	Meaning
any	This function needs to read/discriminate this value/type. Please specialize (monomorphize) the function on this value/type.
var	This function needs to read/discriminate this value/type. However, please don't specialize (monomorphize) it on this parameter. Pass it in at run-time instead.
erased	This function does not need to read/discriminate this value/type. However, please add a debug check to make sure I pass it around correctly to functions who do care.

In some sense, var's behavior is dual to comptime. It takes a typically-comptime value and lifts it to run-time, while comptime takes what would be a run-time value and lowers it to comptime.

Meanwhile, erased is an optimization for when we actually don't need to use the parameter at all. Some of C's most famous features which don't currently have Zig equivalents (void * polymorphism and flexible array members) are examples of this, as well as Zig's own @fieldParentPtr pattern. All of these are very dangerous without debug checks, of course.

Together, these form the 3 primary "type powers" of Zig: type generics (any), type erasure (erased), and type closure* (var).

Note: inline as proposed in #7772 is a hybrid of var and any, requesting specialization whenever possible with a fall-back to run-time parameterization when the datum is not comptime-known.

* *T(var) is a type closure in the same way that a fat function pointer is a function closure, where the stored run-time variables take the role of what would otherwise be a reified context.

[topolarity]

This proposal provides some insight to a problematic anytype example, as shared by @SpexGuy:

const Any = struct { v: anytype };
comptime {
    var a = Any{ .v = @as(f32, 4) };
    const pf: *f32 = &a.v; // this should probably work, right?
    const pa = &a.v; // is this the same as pf?  Or can it change the type of a.v?
    a.v = @as(u32, 10);
    const wtf = pf.*; // what does this do?
}

To support this use-case, we can allow the “type patterns” above in the place of the usual type for a declared variable. We say that comptime var x: T(any) means that the compiler guarantees that it knows at compile-time what fills the any "hole", at any particular point in the program.

The crucial anytype behavior is that the concrete type of x is allowed to vary across the comptime program. For example, the above program could be:

comptime {
    // `any` in a type means that there's some comptime-known substitution
    //            and that this may _change_ across the flow of the program
    
    // We start with a concrete type (f32), but it's allowed to change
    var a: any = @as(f32, 4);
    const pf: *any = &a;   // pf is allowed to point at any number of types
                           // (the compiler will track the active type)
    const pa = &a;         // This could be inferred as `*any` or `*f32`
    a = @as(u32, 10);      // This changes the underlying type of the comptime variable
                           // If pa is `*f32`, compile error now or upon de-referencing/observing pa
    const wtf = pf.*;      // This de-references `pf` based on its current "concrete" type, which is `*u32`
}

or if we still want to use a struct:

const Wrapper = struct(T: type) { v: T };
comptime {    
    // We start with a concrete type == Wrapper(f32), but it's allowed to change
    var a: Wrapper(any) = Wrapper(f32){.v = @as(f32, 4)};
    const pf: *Wrapper(any) = &a.v;
    const pa = &a.v;          // This could be inferred as `*Wrapper(any)` or `*Wrapper(f32)`
    a.v = @as(u32, 10);       // This changes the underlying type of the comptime variable
                              // If pa is `*Wrapper(f32)`, compile error now or upon de-referencing/observing pa
    const wtf = pf.*;         // This de-references `pf` based on its current "concrete" type, which is `*Wrapper(u32)`
}

I'm not sure if I'm sold on these dynamically-typed behaviors in general. Nonetheless, this was a quick demonstration of what they might look like in combination with this proposal.

[sina-devel]

Do you think the cpp solution can be useful?

template <typename T>
concept Addable = requires(T x)
{
    x + x;
};

template <Addable T>
T sum(T a, T b)
{
    return a + b;
}

template <typename T> requires Addable<T>
T add5(T a)
{
    return a + 5;
}