Skip to content
Search

Zig NEWS

Akhil
Akhil

Posted on

Learning interfaces by implementing iterator in zig

#learn #interfaces #iterator

Zig currently doesn't have specific semantics to declare interfaces. There were many proposals for the same but were rejected.

I believe interfaces are one of the important language constructs and helps to define implementation for a custom type to have a particular behavior. Surprisingly, there are few implementations in zig std library that allow a custom type to behave in a certain way. Any custom type can get the behavior of a Reader by implementing it's blueprint. (a new type will be created that has Reader's behavior and custom type as the context). I might use blueprint and interface interchangeably please bear with me.

// Reader's blueprint
pub fn GenericReader(
    comptime Context: type,
    comptime ReadError: type,
    comptime readFn: fn (context: Context, buffer: []u8) ReadError!usize,
) type {
    return struct {
        context: Context,
...
Enter fullscreen mode Exit fullscreen mode

Context, ReadError, readFn are the elements of the blueprint that need to be implemented for any custom type to behave like a Reader. File is one of the type that implements Reader's blueprint to become FileReader type.

pub const Reader = io.Reader(File, ReadError, read);
Enter fullscreen mode Exit fullscreen mode

FileReader object can simply be created by instantiating through file object. For convenience file object has a method to create FileReader object:

pub fn reader(file: File) Reader {
    return .{ .context = file };
}
Enter fullscreen mode Exit fullscreen mode

It can be observed that with existing syntax we can have interfaces and their implementation in zig.

With this observation let's build an Iterator interface that can do map, filter and reduce operations on any custom type that implements it's blueprint.

pub fn Iterator(
comptime T: type, 
comptime Context: type, 
comptime next: fn (context: *Context) ?T) 
type {
    return struct {
        context: *Context,
Enter fullscreen mode Exit fullscreen mode

The iterator needs to know the element type that it will iterate over (T), the custom type that it operates on (Context), the way to move to next value(next).

Now Iterator can have map, filter, reduce composite methods that are implemented based on next function.

// map method

pub fn map(self: Self, comptime B: type, comptime MapContext: type, comptime f: Map(MapContext, T, B)) _map(B, MapContext, f) {
    return .{ .context = self.context };
}

fn _map(comptime B: type, comptime MapContext: type, comptime f: Map(MapContext, T, B)) type {
    return Iterator(B, Context, struct {
        fn inext(context: *Context) ?B {
            if (next(context)) |value| {
                return f.map(value);
            }
            return null;
        }
    }.inext);
}

pub fn Map(comptime Context: type, comptime i: type, comptime o: type) type {
    return struct {
        c: Context,
        m: *const fn (context: Context, in: i) o,
        fn map(self: @This(), in: i) o {
            return self.m(self.c, in);
        }
    };
}
Enter fullscreen mode Exit fullscreen mode

For reduce, filter scroll down to the bottom that has complete code. For now, let's continue digging more on the map method.

map method expects an object (of type created by calling Map comptime function) instead of function. Generally map in other languages receives a closure that gets called on each element but zig doesn't support closures. A closure is the combination of a function bundled together (enclosed) with references to its surrounding state (the lexical environment) according Mozilla documentation. As we can't tie the surrounding state by referring the variables, we need to send the function (nothing but the closure) along with the MapContext(nothing but the surrounding state), food for thought simply think how can we use an allocator inside the function. Note that return type of map function is also an Iterator.

Let's create an ArrayList iterator using the Iterator interface we created earlier and perform filter operation


// Iterates arraylist from backwards
fn next(context: *std.ArrayList(usize)) ?usize {
    return context.popOrNull();
}

// Filters even values
fn filter(_: void, i: usize) bool {
    return i % 2 == 0;
}

pub fn main() !void {
    ...
    // Create ArrayListIterator 
    var si = Iterator(usize, std.ArrayList(usize), next){ .context = &arr };
    ...
    // Create Filter
    const filters = Filter(void, usize){ .c = {}, .f = &filter };
    ...
    // Apply the filter
    const arra = si.filter(void, filters)
    ...
Enter fullscreen mode Exit fullscreen mode

Vola! we were able to achieve Iterator behavior for Arraylist and applied filter for it.

Below is the complete code with comments on Iterator in zig and implementing for ArrayList:

// src/main.zig

const std = @import("std");
const iterator = @import("iterator.zig");
const Iterator = iterator.Iterator;
const Map = iterator.Map;
const Filter = iterator.Filter;
const Reduce = iterator.Reduce;

fn next(context: *std.ArrayList(usize)) ?usize {
    return context.popOrNull();
}

fn map(context: std.mem.Allocator, in: u64) []const u8 {
    return std.fmt.allocPrint(context, "{d}", .{in}) catch @panic("cannot convert");
}

fn filter(_: void, i: usize) bool {
    return i % 2 == 0;
}

fn reduce(context: std.mem.Allocator, lhs: []const u8, rhs: []const u8) []const u8 {
    return std.mem.join(context, "--", &.{ lhs, rhs }) catch @panic("reduce error");
}

pub fn main() !void {
    // Initialize a type.
    // Example:ArrayList is initialized with a sequence of 10 numbers
    var arr = try std.ArrayList(usize).initCapacity(std.heap.page_allocator, 5);
    for (0..10) |v| {
        try arr.append(v);
    }

    // Create an Iterator from the type and the way to iterate to next value followed by initialization of Iterator.
    // Example: next function iterates through array in reverse order and iterator is initialized by ArrayList value
    var si = Iterator(usize, std.ArrayList(usize), next){ .context = &arr };

    // Create mapper, filter and reducer with context for the type
    // Example: Refer to map + filter + reduce functions that operate on ArrayList type and context will be Allocator for map and reduce.
    const mapper = Map(std.mem.Allocator, usize, []const u8){ .c = std.heap.page_allocator, .m = &map };
    const filters = Filter(void, usize){ .c = {}, .f = &filter };
    const reducer = Reduce(std.mem.Allocator, []const u8){ .c = std.heap.page_allocator, .r = &reduce };

    // Chain the functions and pass the mapper, filter and reducer to operate on the intialized value
    // Example: filter: filters even numbers, map: converts to string i.e, []const u8 and concatenates rest of the array by -- with a starting token.
    const arra = si.filter(void, filters).map([]const u8, std.mem.Allocator, mapper).reduce(std.mem.Allocator, reducer, "<start>");

    // Print the value post all operations.
    std.debug.print("{s}", .{arra});
}


// src/iterator.zig

const std = @import("std");
pub fn Iterator(comptime T: type, comptime Context: type, comptime next: fn (context: *Context) ?T) type {
    return struct {
        context: *Context,
        const Self = @This();
        pub fn len(self: Self) usize {
            var counter: usize = 0;
            while (next(self.context)) |_| : (counter += 1) {}
            return counter;
        }
        fn _map(comptime B: type, comptime MapContext: type, comptime f: Map(MapContext, T, B)) type {
            return Iterator(B, Context, struct {
                fn inext(context: *Context) ?B {
                    if (next(context)) |value| {
                        return f.map(value);
                    }
                    return null;
                }
            }.inext);
        }
        pub fn map(self: Self, comptime B: type, comptime MapContext: type, comptime f: Map(MapContext, T, B)) _map(B, MapContext, f) {
            return .{ .context = self.context };
        }
        fn _filter(comptime FilterContext: type, comptime f: Filter(FilterContext, T)) type {
            return Iterator(T, Context, struct {
                fn inext(context: *Context) ?T {
                    if (next(context)) |value| {
                        if (f.filter(value)) {
                            return inext(context);
                        }
                        return value;
                    }
                    return null;
                }
            }.inext);
        }
        pub fn filter(self: Self, comptime FilterContext: type, comptime f: Filter(FilterContext, T)) _filter(FilterContext, f) {
            return .{ .context = self.context };
        }

        pub fn reduce(self: Self, comptime ReduceContext: type, comptime r: Reduce(ReduceContext, T), initial: T) T {
            var temp: T = initial;
            while (next(self.context)) |val| {
                temp = r.reduce(temp, val);
            }
            return temp;
        }
        pub fn toArray(self: Self, allocator: std.mem.Allocator) !std.ArrayList(T) {
            var arr = std.ArrayList(T).init(allocator);
            while (next(self.context)) |value| {
                try arr.append(value);
            }
            return arr;
        }
    };
}

pub fn Map(comptime Context: type, comptime i: type, comptime o: type) type {
    return struct {
        c: Context,
        m: *const fn (context: Context, in: i) o,
        fn map(self: @This(), in: i) o {
            return self.m(self.c, in);
        }
    };
}

pub fn Filter(comptime Context: type, comptime i: type) type {
    return struct {
        c: Context,
        f: *const fn (context: Context, in: i) bool,
        fn filter(self: @This(), in: i) bool {
            return self.f(self.c, in);
        }
    };
}

pub fn Reduce(comptime Context: type, comptime i: type) type {
    return struct {
        c: Context,
        r: *const fn (context: Context, lhs: i, rhs: i) i,
        fn reduce(self: @This(), lhs: i, rhs: i) i {
            return self.r(self.c, lhs, rhs);
        }
    };
}
Enter fullscreen mode Exit fullscreen mode

By the way, I hate anytype in zig.

Backstory on how I fallen love with Zig.

I'm a fan of zig because of it's simplicity, fastness and best user experience to take control of the cpu and memory. Earlier I used to code in Rust for my side projects and one of the major one is podcast summarizer. I don't know if I was biased but I started liking Rust because the whole developer community was embracing it, like following the herd. But one thing that got my attention were traits. This is one of the nicest feature's in Rust to build interfaces. Liked the tooling for the language: cargo, rustup and rust-analyzer making dev's job easy to manage projects. Slowly, rust became complicated because of heavy abstractions, low visibility in internal implementations and biggest realization after coding in zig is that I was trying to fit my ideas within framework of rust giving me headaches to mold them to keep compiler happy. Zig powered me to implement my ideas as I think. This is where I had fallen love with zig. Currently I'm working on a cuda library for zig applications. Show some love by starring the repo: https://github.com/akhildevelops/cudaz

Latest comments (5)

Collapse
 
spacifici profile image
Stefano Pacifici •

Hey, I'm learning some Zig and found your post when looking for iterators. Do you have any particular reason why your implementation has the nextFn in the type constructor (if that is the correct name)?
I mean the following code:

pub fn Iterator(comptime T: type, comptime Context: type, comptime next: fn (context: *Context) ?T) type {
    return struct {
        // ...
    };
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
akhildevelops profile image
Akhil • • Edited

If it becomes part of struct field i.e,

pub fn Iterator(comptime T: type, comptime Context: type) type {
    return struct {
       next: fn (context: *Context) ?T,
        // ...
    };
}
Enter fullscreen mode Exit fullscreen mode

then there's no way to build _map, _filter types during comptime as next function is not visible while building them.

Collapse
 
spacifici profile image
Stefano Pacifici •

I see, it is because _map and _filter are types.
Well, actually I did my own implementation of the Iterator, the inspiration came from other languages like Scala or Kotlin. By using the idea that an iterator can wrap another iterator, I came up with the following solution:

fn Iterator(comptime T: type, comptime Context: type) type {
    return struct {
        context: Context,
        inext: *const fn (*Context) ?T,

        const Self = @This();

        fn next(self: *Self) ?T {
            return self.inext(&self.context);
        }

        fn filter(self: *Self, comptime predicate: *const fn (T) bool) Iterator(T, *Self) {
            const nx = struct {
                fn next(ctx: **Self) ?T {
                    const context_ptr = ctx.*;
                    while (context_ptr.next()) |value| {
                        if (predicate(value)) {
                            return value;
                        }
                    }
                    return null;
                }
            }.next;
            return Iterator(T, *Iterator(T, Context)){
                .context = self,
                .inext = nx,
            };
        }

        fn map(self: *Self, comptime U: type, comptime f: *const fn (T) U) Iterator(U, *Self) {
            const nx = struct {
                fn next(ctx: **Self) ?U {
                    const context_ptr = ctx.*;
                    return if (context_ptr.next()) |value| f(value) else null;
                }
            }.next;
            return .{
                .context = self,
                .inext = nx,
            };
        }
    };
}
Enter fullscreen mode Exit fullscreen mode

I would like to get rid of the comptime clause for the filter predicate and the map function, but that's out of my knowledge level at the moment.

Thread Thread
 
akhildevelops profile image
Akhil •

The implementation looks neat, but it doesn't send surrounding context to map/filter predicates. Ex: I can't use an allocator inside the map predicate, one way is to hardcode inside the predicate's body but it's not desirable. There should be a way that the predicate can access the surrounding context. Should wait until zig supports closures for this to happen.

Thread Thread
 
spacifici profile image
Stefano Pacifici • • Edited

Taking your allocator example, I can do that without full fledged closures: because the predicate is comptime, one can convert its type to anytype, use type inspection (@typeInfo(@TypeOf(f)) to figure out if it is a function or a struct, and, finally generate a proper compile time closure that calls the function, as above, or the struct pub fn apply(self: *Self, value: T) U.

Read next

aryaelfren profile image

Methods

Arya-Elfren -

edyu profile image

Zig If -- WTF is !?bool

Ed Yu -

perky profile image

Anytype Antics

Luke -

karchnu profile image

Feedback on Zig: real-life example through libIPC

karchnu -