Type Inference in the Standard Library

[marler8997]

The question being posed here is:

When should the standard library make use of type inference for function parameters?

This concept can be applied to many functions in the standard library. Let's look at 2 functions in mem.zig as examples. The functions set and secureZero currently require the caller to provide the element type of the arrays being passed. However, this type information could be inferred from the arrays that are also being provided by the caller. i.e.

var buf : []u8 = ...;

// Current API
mem.set(u8, buf, 0);
mem.secureZero(u8, buf);

// API using type inference
mem.set(buf, 0);
mem.secureZero(buf);

The benefit of this revised API is that it removes a burden on the caller. In simple cases where the element type is static and/or "contains few characters" the burden is negligible. It's only when these types become dynamic and/or "contain many characters" that the burden becomes noticeable:

mem.set(!?Foo(Bar(u8[MySize("key")])), buf, value);
// vs 
mem.set(buf, value);

Or consider a case where you're inside generic code that calls one of these functions in a common branch.

mem.set(buf, value);
if (@typeInfo(buf).Pointer.child == ...) {
    ...
}  else {
    ...
}

This should work fine with the revised API, but in some cases the current API would likely require a separate call to the function in each code branch:

if (@typeInfo(buf).Pointer.child == ...) {
    mem.set(Type1, buf, value);
    ...
}  else {
    mem.set(Type2, buf, value);
    ...
}

Another point to consider is whether the reasons for the current API would also apply to other concepts. For example, if we want to explicitly specify the element type in cases where arrays/pointers are accepted, should we also do the same for for loops? Or what about the ArrayList Member functions?

var myslice : []const u8 = "foo";
for (u8, myslice) |c| { ...}

var al = ArrayList(u8).init(u8);
al.toSlice(u8);
al.at(u8, 0);
al.set(u8, 0, 'a');

@andrewrk identified that functions using type inference cause a certain amount of "bloat" in the LLVM IR (see https://github.com/ziglang/zig/pull/2636#issuecomment-509453512). Because of this, I proposed that the original explicitly typed functions remain and that we only create inline wrapper functions that infer the types and forward the call to the explicit function. For example,

// Current implementation
pub fn set(comptime T: type, dest: []T, value: T) void {
    for (dest) |*d|
        d.* = value;
}

// Implementation using Type Inference
pub fn setExplicit(comptime T: type, dest: []T, value: T) void {
    for (dest) |*d|
        d.* = value;
}
pub fn set(dest: var, value: var) void {
    setExplicit(@typeOf(dest).Child, dest, value);
}

This allows the caller to use either ABI, i.e.

mem.set(buf, 42);
mem.setExplicit(u8, buf, 42);

Note that this technique could be used for many other functions in the standard library as well. This Issue is being opened to discuss the pros/cons of this API design and/or alternatives/improvements to it.

Another variation would be to provide the explicit/implicit functions in different modules, i.e.

mem.set(u8, buf, 0);
meminfer.set(buf, 0);

Related PR: "deduce type for mem.set and mem.secureZero" https://github.com/ziglang/zig/pull/2636

[marler8997]

One thought I had was that if we want functions in the standard library that take generic pointer/array types to include not only the pointer/array argument itself but also have its element passed in separately as another argument, should we do that for everything? For example, should we also apply this to for loops?

var s : []u8 = ...;

std.mem.set(u8, s, 0);

for (u8, s) |c| {
    // ...
}

I've updated the description to mention this.

[JesseRMeyer]

Why is Zig outputting bloated IR in this standard case (comp time known values) in the first place?

And why is that a factor of the Standard Library specification?

A common C-ism for this usage case is to replace a function call like:

struct_kind *MyStruct = push_struct(&allocator, sizeof(struct_kind));

With

struct_kind *MyStruct = push_struct(&allocator, struct_kind);

by providing a Macro:

void *_push_size(allocator *Allocator, size_t StructSize) { ... }
#define push_struct(allocator, structure) ((structure *))_push_size((allocator), (sizeof(structure)))

All this effort just to provide the compiler information that it already has. If the compiler is not outputting more optimal IR, then the solution is not the burden the users, it's to improve the compiler. Enforcing the type specification here is not adding clarity of intent -- it's just forcing busy work -- the kind I am tired of from C.

[DaseinPhaos]

Why is Zig outputting bloated IR in this standard case (comp time known values) in the first place?

The bloated IR example AFAIK is not the fault of zig compiler per se.

Literal "abcd" and "lmnopqrs" have different types (respectively, [4] u8 and [8] u8 ), thus the compiler generates two different IR for them. This is exactly the behavior we want from it. Why WOULD it behave differently in the first place?

To prevent code bloating in this example without passing in the extra type parameter, we'd need some type inference magic that allows function declaration to specify a parameter foo: []const T without explictly specifying T: type first. I don't know zig well enough to tell if it's possible as of now..

[JesseRMeyer]

The types are only superficially different in these instances. They are comp-time known arrays of the same 'base' type that undergo the same transformation. The only reason I would expect for a compiler to generate different IR for these cases is if an optimization opportunity presents itself, ie, if the comp time known length was an even divisor of the vector length of the instruction set supported by the processor target for auto-vectorization. So the issue stems directly from the compiler, unless the backend optimizer folds these together.

For --Release-fast, I am largely willing to trade code size for execution speed, however, for --Release-small, I would want only one function generated, using the more general []u8 storage instead of the exact specifics. I think that is an achievable, actionable goal for this specific proposal.

Yes, generally speaking, Zig would need to learn how to infer types in a more systematic and intelligent way to fully enable 'debloating' in this manner, and I think it should.

As a guiding principle, I think if the compiler has information at its disposal, it should both be able to act on it, or let us tell it how to.

[vmgolovin]

I am new to Zig and don't know the implementation details of its metaprogramming capabilities, but as a programmer, I find the necessity to write max(i32, a, b) instead of max(a, b) ridiculous (just an example, of course). Even in C it is unnecessary (with a macro). Does this implementation of max impose any problem?

pub fn max(a: anytype, b: anytype) @TypeOf(a + b) {
    return if (a > b) a else b;
}

[matklad]

Couple of thoughts:

I've recently had an opposite problem when I was using asBytes function which employs anytype trick to do type inference. This makes the call-site unclear and potentially hides a bug:

// One of these is buggy
fn f(s: S) void {
    const slice: []const u8 = std.mem.asBytes(&s);
    _ = slice ;
}

fn g(s: *const S) void {
    const slice: []const u8 = std.mem.asBytes(&s);
    _ = slice;
}

The "please pass the type" API would turn this bug into a compile-time error:

const slice: []const u8 = std.mem.asBytes(S, &s);

[matklad]

The inference problem goes away when using method syntax, because the argument we dispatch on carries the type. Hypothetical API:

pub fn Slice(comptime T: type) type {
    return struct {
        ptr: *T,
        len: usize,

        pub fn set(self: @This(), value: T) void {
            for (self) |*slot| slot.* = value;
        }
    };
}