Proposal to improve the ergonomics and precision of type inference in generic functions

Problem

Generic functions, as currently supported in Zig have the form

fn eql(x: anytype, y: @TypeOf(x)) bool {
    return x == y;
}

This works well enough in general, but also has some problems and limitations:

1. Aesthetics

Besides the controversial keyword (#5893), the @TypeOf pattern is a bit of a hack, even though everybody is used to it by now. It somewhat obscures the fact that eql takes two arguments of the same type. It also leads to unnecessary verbosity in some cases:

fn foo(x: anytype, y: @TypeOf(x)) Container(@TypeOf(x)) {
    const T = @TypeOf(x);
    ...
}

2. Type signatures

The type of a simple function like same(x: i32, y: i32) bool {...}, is fn(i32, i32) bool. For the generic function eql, the intended type is something like fn<T>(T,T) bool. But the actual type inferred by the compiler seems to be fn(anytype,anytype) anytype. In my limited testing, I found that the compiler essentially considers all generic and parametric functions to have the same type. Only the number of arguments is checked. E.g., the following code compiles:

const eq: fn(anytype, f32) i32 = eql; // should have failed
assert(eq(1, 1));

It seems that the type check automatically simplifies to const eq: any_generic_function = eql;, which then succeeds. Maybe this is a limitation of the compiler that can be fixed independently, but then only in part. For example, the fact that both arguments of eql should have the same type is simply not expressible in the current system, since parameter names are not part of the type: fn(anytype, @TypeOf(?)) bool.

This state of affairs reduces the precision of type checks, and also discards valuable information that could be used by documentation generators, mataprogrammed interfaces and error messages.

3. Order dependence

Another minor nit is that generic functions constrain the order of function parameters in some cases. This, for example, is not possible:

fn find(haystack: ArrayList(@TypeOf(needle)), needle: anytype) usize {...} // error

The arguments need to be the other way round, although logically they can be in any order. This is an arbitrary, albeit minor, limitation.

Proposed solution

Change the fn(x: anytype) syntax to fn(x: infer T), which infers the type of x and binds it to T. Example:

// before:
fn eql(x: anytype, y: @TypeOf(x)) bool {...}
// after:
fn eql(x: infer T, y: T) bool {...}

// before:
fn find(needle: anytype, haystack: ArrayList(@TypeOf(needle))) usize {...}
// after:
fn find(needle: infer T, haystack: ArrayList(T)) usize {...}

This makes the intent much clearer, IMO. More importantly, the naming of inferred types allows us to talk about the types of generic functions with much greater precision:

// before:
eql: fn(anytype, anytype) anytype
// after:
eql: fn(infer T, T) bool

// before:
find: fn(anytype, anytype) anytype
// after:
find: fn(infer T, ArrayList(T)) usize

This forms the bare bones of the proposal, but there are additional possibilities that could be easily layered on top of it:

// Make type name optional:
fn wrapper(x: infer _) void { other_generic_function(x, 0); }

// Unrestrict order of inferred parameters:
fn find(haystack: ArrayList(T), needle: infer T) usize {...}
// Note: T can still only be inferred once, and only at a particular location, but it
// can be referred to before that. The procedure would be to resolve all infers first,
// and then use them in a second pass to finalize the types of the remaining arguments.

// Structural pattern matching on simple types:
fn foo(bar: ?*infer T, baz: []const T) bool {...}

// However, note that structural inference across custom types is not possible
// and will probably never be possible, because type constructors in Zig can be
// arbitrarily complex. 
fn convert(x: ArrayList(infer T)) HashSet(T) {...} // No can do. Use this instead:
fn convert(comptime T: type, x: ArrayList(T)) HashSet(T) {...}

Peer type resolution

Another straight-forward possibility is to allow peer type resolution, as suggested by @mlugg in this comment. Peer type resolution is enabled by using an infer with the same label more than once:

fn max(x: infer T, y: infer T) T {
    return if (x > y) x else y;
}

This allows us to call max(@as(u8, 5), @as(u16, 3)) and get a u16 as a result. If the function were instead declared as fn max(x: infer T, y: T) T { ... }, then a call with different argument types would be an error.

Nearly the same thing could be achieved by declaring fn max(x: infer _, y: infer _) @TypeOf(x, y) { ... }, but this is less nice syntactically. It may also lead to over-instantiation in some cases: max(u8, u16), max(u16, u8) and max(u16, u16) would produce separate instances. This can be avoided if the peer type resolution happens at the argument level and is not deferred to the return type calculation.

Similar proposals

This proposal is an improved (I hope) version of something suggested by @YohananDiamond here: #5893 (comment). Towards the end of the comment, the following is proposed:

fn max(generic a: T, b: T) T {
    return if (a > b) a else b;
}

In the same comment it is pointed out that this makes it somewhat unclear that T is being declared here. The present proposal addresses this shortcoming and generally makes it clear what and where exactly is inferred. It also leads to a more natural representation of the type of a generic function, but is otherwise only a minor reshuffling of keywords.

Edit: There's also the proposal #6997, which provides a partial solution to the type signature imprecision problem.

Summary

Advantages over status quo:

• Preserve more type information for docgen, metaprogramming and error messages
• Reduce visual noise and unintuitive keyword naming
• Express intent more clearly

Optionally also:

• Remove constraints on order of arguments
• Allow structural pattern matching without std.meta in simple cases

It should also be mentioned that inference remains simple and fully deterministic and does not open the door to template metaprogamming or some such.

[jedisct1]

This is a nice proposal, and indeed, having to systematically use @TypeOf() for this use case is a little bit cumbersome.

There wouldn't be a clear difference between anytype and infer, though. The only difference is that with infer, the type has a name, while with anytype, it doesn't.

So, I'm wondering if, instead of introducing a new keyword, we couldn't have anytype (perhaps renamed to infer if this improves clarity) require a name, which could be _ to discard it.

There wouldn't be a clear difference between anytype and infer, though. The only difference is that with infer, the type has a name, while with anytype, it doesn't.

So, I'm wondering if, instead of introducing a new keyword, we couldn't have anytype (perhaps renamed to infer if this improves clarity) require a name, which could be _ to discard it.

That's actually how I intended it. With this change anytype would no longer be allowed in function declarations. In principle, it's not even necessary to rename the keyword, as you say. The proposal could be changed to fn(x: anytype T, ...), but I thought if we are already changing syntax, then we can also change the keyword to something more appropriate.

[zigazeljko]

There wouldn't be a clear difference between anytype and infer, though. The only difference is that with infer, the type has a name, while with anytype, it doesn't.

There would be a difference. Since infer could be used inside a more complex type, it would allow pattern matching and creating type constraints.

[marler8997]

// However, note that structural inference across custom types is not possible
// and will probably never be possible, because type constructors in Zig can be
// arbitrarily complex and impure.

Oh it's definitely possible. All you need is a way to reverse the operation from a custom type to its input parameters. The compiler could maintain this mapping internally. Note this would only work for "custom types" though. This wouldn't work with non-custom types and would probably be mostly useless for them anyway:

fn foo(x: IgnoreTGiveMeU32(infer T)) void { }

fn IgnoreTGiveMeU32(comptime T: type) type { return u32; }

It's impossible to do this in the general case, unless all your functions are bijective mappings. Whether it's desirable is another question which I would have to ponder on. Some things to think about.

[SpexGuy]

This doesn't work for most actual cases though, because things like std.ArrayList are just wrappers for more complex types like std.ArrayListAligned. Determining whether a function like std.ArrayList could return a given type for some input is undecidable in the general case.

[marler8997]

Yes the general case meaning all functions is undecidable, but it's very much possible for bijective functions. In the case of std.ArrayList, it's a very simple bijective function, so this "actual case" is quite simple if you use the table I mentioned. Let's say we have an ArrayList(u32). In this case, the compiler's "inverse table" would look like this:

ArrayList
    (u32) -> ArrayListAligned(u32, null)
    (Foo) -> ArrayListAligned(Foo, null)

So when the compiler tries to pattern match ArrayList(infer T), and receives an instance of ArrayListAligned(u32, null) (aka ArrayList(u32)), all it needs to do is look in the ArrayList table for an output type that matches ArrayListAligned(u32, null), and assign the infer T to the corresponding input parameter u32.

This only breaks down when we have non-bijective functions. For example:

fn IgnoreTGiveMeU32(comptime T: type) type { return u32; }

In this case our inverse table looks like this:

IgnoreTGiveMeU32
    (u32) -> u32
    (Foo) -> u32

So now when we try to pattern match IgnoreTGiveMeU32(infer T) with an instance of u32, we will find multiple entries that match the output type u32, which means we cannot determine the input parameter and thus the problem becomes "undecidable" as you say.

The concept of bijective functions is well-understood, and that is the exact criteria that would determine whether or not a function could support infer T.

P.S. I think that determining whether a function is actually bijective is very difficult. Determining whether the subset of input of all instantiations is bijective is very easy. Relying on these imperfect tables to determine whether a function is bijective would cause cascading errors when a conflict is instantiated. I'm not sure of an easy way to solve this, so the compiler would only know when this is violated when a conflict happens to be instantiated.

@marler8997
You're making a good point about the reverse lookup table. To ask the question "given a particular instance of ArrayList, what type T was used to construct it?", we need to have already constructed said instance, meaning that the mapping T -> ArrayList(T) must already be in the cache, and performing the reverse operation is possible. So for custom types that play nice inference is a lot easier than I thought.

Non-bijective functions would be a problem, of course. Especially in libraries, where unambiguous inference needs to be ensured for all possible child types, and not only instances currently used in the project. There are also other failure modes that should not occur in good code, but are still possible in principle, like ArrayList(T) doing something funny on April 1.

So, if we had an annotation for well-behaved type constructors (callconv(.InvertibleTypeConstructor)?), then structural pattern matching on custom types would become feasible, and maybe not even difficult. But without it, trying to infer things would be a rather adventurous undertaking.

[ikskuh]

@zzyxyzz i don't think all of this is worth the benefit in the end, especially as ArrayList(T) aliases with ArrayListAligned(T, null) already and a lot of comptime functions just configure other types. Or you have functions like this:

pub fn BitBuffer(comptime size: usize) type {
    return [(size + 7)/8]u8;
}

where BitBuffer(1) and BitBuffer(8) are the same type

@MasterQ32
Just to be clear, pattern matching on custom types is not part of the proposal. I think it's an intriguing possibility to keep in mind, especially now that a workable implementation idea has been suggested. But whether it can really be made to work and at what cost, and whether we want it in the first place, has to be decided separately.

As it stands, the most ambitious variant of this proposal only allows pattern matching against built-in types, such as pointers, optionals and slices, which should not pose any problems.

BTW, BitBuffer is a nice example of a non-invertible type constructor, thanks for that. I also forgot about type aliases. They would further compound the difficulties with general type inference.

[marler8997]

@MasterQ32 yes your example BitBuffer is a non-bijective function so it's not reversible. We could create a bijective function that wraps it like this:

pub fn BitBufferBijective(comptime size: usize) type {
    std.debug.assert(size % 8 == 0); // Blocks inputs in order to create a 1 to 1 mapping
    return BitBuffer(size);
}

This example doesn't really apply to this infer T proposal because BitBuffer takes a usize instead of a type, so there's no type to infer, but the same concept applies to functions that do accept types as input parameters. This mechanism of defining wrapper functions to make type functions bijective could be used to extract the input types from any type function.

pub fn Foo(comptime T: type) type {
    // black box, that is not bijective, this Foo is a stand-in for any type funciton.
}

pub fn bar(x: Foo(infer T) void {...}
// compile error: cannot use 'infer T' with 'Foo' because it is not bijective, the input types x and y both map to z

pub fn FooBijective(comptime T: type) type {
    std.debug.assert( limitInputsToRemoveConflicts(T) );
    return Foo(T);
}

pub fn bar(x: FooBijective(infer T) void {...}
// now it will work, T will become whatever type was passed to the caller's Foo(T) instance

I thought alot about this stuff years ago when I was thinking about how D implemented pattern matching and what the challenges and potential solutions were with it. I determined it is feasible and actually not too difficult to implement and I'd be happy to help come up with a design if we want to go this route. And to re-iterate, I'm not advocating that we do implement it, just sharing exactly what a solution would look so we can make informed decisions.

[windows-h8r]

On a comment on #5893, I suggested an alternative. If we add support for default parameters, and make default parameters go first, we can do something like this:

const std = @import("std");

fn square(comptime T: type = any, n: T) T {
    return n * n;
}

fn main() void {
    const x: u32 = 5;
    std.debug.print(
         "{} = {}\n",
         square(u32, x),
         square(x)
    );
}

[SpexGuy]

The reverse lookup table doesn't work, because the outer function may never have been called.

fn foo(x: std.ArrayList(infer T)) { }
test {
  const T = std.ArrayListAligned(u32, null);
  var v: T = undefined;
  // assert(T == std.ArrayList(u32))
  foo(v);
}

std.ArrayList has never run in the above example, but the type being passed to foo is indeed a valid possible return value for it.

[marler8997]

@SpexGuy Shoot you're right. I can't think of a way to get around this without having a way to generally reverse code evaluation.

Shoot you're right. I can't think of a way to get around this without having a way to generally reverse code evaluation.

There are some ways. E.g. the compiler could automatically expand trivial type constructors like ArrayList, or we could make the system operate in What You Write Is What You Get fashion and simply refuse to match ArrayList(T) against ArrayListAligned(T, null). The non-injectivity issue is also both fairly rare and can be caught automatically in most cases (you have to check, recursively, that none of the return paths discards the input type). So I still think general inference could be made to work in almost all non-pathological cases. But if someone were to argue that this creates complexity way beyond what is acceptable in Zig, I wouldn't disagree 😄.

[zigazeljko]

There is a simpler and more powerful way that does not depend on memoization or other type constructor shenanigans.

Given a parameter declaration such as haystack: ArrayList(infer T), the compiler expands the type constructor into the actual type, in this case haystack: struct { items: []infer T, capacity: usize, allocator: *Allocator }. Treating that as an equation, we get const T = @typeInfo(@TypeOf(haystack.items)).Pointer.child;.

For example, the function fn find(haystack: ArrayList(infer T), needle: T) usize {...} would behave like this:

fn find(haystack: anytype, needle: anytype) usize {
    const T = @typeInfo(@TypeOf(haystack.items)).Pointer.child;
    return findImpl(T, haystack, needle);
}

fn findImpl(comptime T: type, haystack: ArrayList(T), needle: T) usize {...}

This method also allows infer T to be used more that once per function declaration.

For example, the declaration fn max(a: infer T, b: infer T) T would mean this:

fn max(a: anytype, b: anytype) anytype {
    const T = @TypeOf(a, b);
    return maxImpl(T, a, b);
}

fn maxImpl(comptime T: type, a: T, b: T) T {...}

Furthermore, this method allows using anonymous initializers for generic parameters:

fn Vec3(comptime T: type) type {
    return struct { x: T, y: T, z: T };
}

comptime {
    const a: f32 = 2;
    _ = length(.{ .x = a, .y = 3, .z = 6 });
}

fn length(v: Vec3(infer T)) T {
    // T == f32
    // @TypeOf(v) == Vec3(f32)
    return @sqrt(v.x * v.x + v.y * v.y + v.z * v.z);
}