I have been really enjoying the new async/await system added into zig 0.16.0; The most interesting aspect of it to me is how it has been implemented entirely within the standard library without needing to introduce any syntax. The focus of this article however, is an alternative interface to the async/await constructs inspired by functional programming languages such as Haskell. Why? No reason at all. Let us begin.
A Functional Perspective
A core tenet of functional programming is the notion of referential transparency. In a functional programming language, a function called with the same input will always return the same output. This quickly becomes an issue though, since many functions of our program may rely on values external to it. We can see this below when generating a random number:
const std = @import("std");
/// Generate a random number and return it
fn random(io: std.Io) std.Io.RandomSecureError!u32 {
var result: u32 = undefined;
try io.randomSecure(@ptrCast(&result));
return result;
}
pub fn main(init: std.process.Init) !void {
for (0..5) |_| {
std.debug.print("{x:08}\n", .{try random(init.io)});
}
}$ zig run ex_random.zig
f95b7fcb
a021349f
cf019603
8de341f5
42a6107d
We called random with the same arguments but got different results! So there is no referential transparency here. The result of random() is no longer dependent on solely on what is passed into it, but also on external state out of our control. Additionally, since random() does not have referential transparency, and main() calls random(), main() also does not have any referential transparency. Running main() more than once may produce different results. From now on we are going to be calling functions with referential transparency pure, and those without impure. The rest of this article explores how we can avoid impure functions using a structure called Monad. But first, an exploration on the new async/await in zig 0.16.0
Futures
First let us explore a new structure introduced in zig 0.16.0: std.Io.Future(Result). Here is the abridged definition as it appears in the standard library:
pub fn Future(Result: type) type {
return struct {
any_future: ?*AnyFuture,
result: Result,
// "cancel: fn (*@This(), Io) Result" excluded for brevity
/// Idempotent. Not threadsafe.
pub fn await(f: *@This(), io: Io) Result {
const any_future = f.any_future orelse return f.result;
io.vtable.await(
io.userdata,
any_future,
@ptrCast(&f.result),
.of(Result),
);
f.any_future = null;
return f.result;
}
};
}
The type function for std.Io.Future(Result) takes another type as an argument. This is the type of value which the Future represents. A instance of std.Io.Future(Result) has two fields: a field of type Result and a field of type ?*AnyFuture. The magic of std.Io.Future(Result) is that the result contained within may not be known yet. If the result is unknown, the any_future field is non-null and the result field is undefined. Once the result becomes known, the any_future field becomes null, and result contains a value.
To get the value out of the future, whether it has been computed yet or not, we can call the future.await() member function. Firstly, future.await() checks if any_future is null. If it is null, that means the result field already contains a value, so we just return it. If any_future is non-null, result is undefined and we must pass any_future into io.vtable.await() in order to receive that value. Since io.vtable.await() sets the result field itself, the instance of std.Io.Future(Result) must be mutable and passed as a pointer. Now that result is set, any_future is set to null which makes any future calls to future.await() simply read the result again.
Something important to keep in mind with Future is that since any_future is a pointer, it is pointing to external state. A value of type *AnyFuture must only be used as an argument to io.vtable.await() once. Calling await with the same *AnyFuture a second time is undefined behavior. Since the pointer is part of the std.Io.Future(Result) struct, we must be careful about ever making a copy of a std.Io.Future(Result) instance. If any_future is null, this operation is safe, as there is no *AnyFuture, so no risk of re-use. If however any_future is non-null, calling future.await() will invalidate any other copies of the Future. Since there is always the possibility of copies being invalidated, the code must make clear whenever making a copy that the old instance of future must not be used.
A question that arises now, is how do we get a value of type *AnyFuture? As we saw inside of future.await(), we use a std.Io instance to get the result out of an *AnyFuture. To create a future, we also use a std.Io instance, this time calling io.vtable.async(). The best way to show how io.vtable.async() is used, is to see how it is used in the standard library. Below is the annotated source code for io.async():
pub fn async(
/// an instance of io
io: Io,
/// The function to run
function: anytype,
/// The arguments to function as a Tuple
/// (https://ziglang.org/documentation/master/#Tuples)
args: std.meta.ArgsTuple(@TypeOf(function)),
) Future(@typeInfo(@TypeOf(function)).@"fn".return_type.?) {
const Result = @typeInfo(@TypeOf(function)).@"fn".return_type.?;
const Args = @TypeOf(args);
// In zig, this is a pattern which allows us to create a
// anonymous function within a closure. We create a struct
// called "TypeErased" with a member function called "start".
// When we want to run start, we can use TypeErased.start().
// A useful aspect of closures is that we can access comptime
// values from the containing scope. For this particular
// function we are using "Result", "Args", and "function".
const TypeErased = struct {
fn start(context: *const anyopaque, result: *anyopaque) void {
// Cast context and result to *const Args and *Result
// respectively
const args_casted: *const Args = @ptrCast(@alignCast(context));
const result_casted: *Result = @ptrCast(@alignCast(result));
// Run the passed function using the @call builtin
result_casted.* = @call(.auto, function, args_casted.*);
}
};
// Since io.vtable.async wants a pointer to future.result
// we define a variable for it.
var future: Future(Result) = undefined;
// io.vtable.async() returns an *AnyFuture
future.any_future = io.vtable.async(
io.userdata,
// In case the io implementation is single-threaded,
// we specify a pointer to the above result variable
// for when a value is immediately available.
@ptrCast(&future.result),
.of(Result),
// This pointer to the "args" parameter is passed
// as the "context" field of TypeErased.start
@ptrCast(&args),
.of(Args),
// Finally, we specify TypeErased.start
TypeErased.start,
);
return future;
}
Now that we know how std.Io.Future(Result) and io.async() work, we can finally try to tackle the problem of referential transparency. If it is still unclear why Future does not have referential transparency, look no further than future.await(). Since future.await() ultimately gets its value from a function passed into io.async(), then if said function is impure, then any code which calls future.await() must also be impure!
A New Future
The main change to make, and one which will inspire the rest, is forbidding external calls to future.await(). An effective way to do that is to remove the pub keyword from the method. We could remove it entirely but we will need it later for internal use. The change is so small that the code is not included here, so look above if you want a refresher of what std.Io.Future(Result) and future.await() look like.
You may wonder what the purpose of Future is now that we have dis-incentivized awaiting its value. However what we have done is taken the first step towards transitioning std.Io.Future(Result) into a new structure called Monad(T). Next up is adding two new methods and making sure they obey a few rules.
Monads
To turn Future into a Monad, we need to implement only two member functions:
/// Lift a value into a monad.
const @"return" = fn(a: T, io: Io) Monad(T);
/// Apply a function to a monad, returning a new monad with the result.
const bind = fn(
m: Monad(T),
function: fn(T) Monad(V),
io: Io,
) Monad(V);
The first function, return, is the simplest to understand. Think of it like the opposite of await. Instead of getting a value out of a future, return is for placing a value inside of one. You may notice that in the above signature, @"return"() is surrounded by @"". This is because return is a keyword, but by using this syntax zig lets us use that name anyways. Calls to @"return"() need this syntax as well. We could avoid this by calling this function something else, but as this is an introduction to Monads specifically, we are using the de-facto name for this function. Nearly all resources in the wild call this return, so to make things easier to understand if you inevidably do your own follow-up research, we will be calling it return from now on.
Anyways, here is an implementation of @"return"():
pub fn @"return"(val: T) Monad(T) {
return .{
.any_future = null,
.val = val,
};
}
Recalling the earlier discussion of std.Io.Future(Result), this code should already be self-explanatory. We already have the value, so we set any_future to null and val to be the passed in argument. If await() were still available, a call to it would return the same value back.
Next up we have monad.bind(). Let us talk about it for a bit before looking at how to implement it code. The main purpose of monad.bind() is to apply a function to the contents of a Monad(T), then return a new Monad containing the result. To illustrate, we will remake the random() example, this time using monad.bind():
const std = @import("std");
// Monad.zig is attached at the bottom of this blog post,
// and includes a working implementation of everything
// this article covers
const Monad = @import("monad.zig").Monad;
/// Generate a random number
fn random(io: std.Io) Monad(u32) {
var result: u32 = undefined;
io.randomSecure(@ptrCast(&result)) catch unreachable;
return Monad(u32).@"return"(result);
}
/// Print a number
fn print(value: u32) Monad(void) {
std.debug.print("{x:08}\n", .{value});
return .@"return"({});
}
fn randPrint(io: std.Io) Monad(void) {
return Monad(std.Io)
.@"return"(io)
.bind(random, io)
.bind(print, io);
}
/// main() uses a new member functions which
/// allow us to use Monads in a imperative context.
/// They are elaborated on below.
pub fn main(init: std.process.Init) !void {
for (0..5) |_| {
randPrint(init.io).yield(init.io);
}
}
ex_bind($link.asset(‘ex_bind.zig’).attrs(‘download’))
Running it:$ zig run ex_bind.zig
64d78fe5
c8636181
e3216f64
593268b1
b0aa1327
You may notice that main() uses a new member function named monad.yield(). Since the focus is on monad.bind() right now, we will hold of on covering it. For now, focus on the implementation of randPrint(). randPrint() uses monad.bind() to run two functions: random() which generates the random number, and print() which prints out whichever number is passed into it. Notice how both functions themselves return a Monad(T). Just like with a future, the result represents a future value of T, which allows bound functions to not just return a value, but also whole computations.
As a brief aside here is the function signature for the implementation of monad.bind() used above:
const bind = fn(
m: Monad(T),
transform: anytype,
io: std.Io
) Monad(ReturnType(@TypeOf(transform)));
Here the function argument uses the anytype keyword, which will allow us to pass a value of any type as the transform parameter. anytype is not really a type on its own but will instead implicitly create a variant of the function for each type used for it. As an example, when we passed random as the transform parameter, the function signature effectively looked like this:
const bind = fn(
m: Monad(T),
transform: fn (std.Io) Monad(u32),
io: std.Io
) Monad(ReturnType(fn (std.Io) Monad(u32)));
The arguments of monad.bind() are fairly self explanatory, but the return type needs some clarification. Firstly, ReturnType() is a function we provide that takes a function type and will return the type of Monad it returns. For random(), since it returns Monad(u32), ReturnType() will return u32; ReturnType() also does some sanity checking for the function you pass in:
/// This function verifies transform is a valid function, then gives us its return
/// type sans Monad
fn ReturnType(Transform: type) type {
if (@typeInfo(Transform) != .@"fn")
@compileError("transform must be a function.");
const function = @typeInfo(Transform).@"fn";
// Whenever a type is a Monad(T), it is common practice to add an M to the end
// of the name
const ResultM = function.return_type.?;
// Ensure result is a monad
if (@typeInfo(ResultM) != .@"struct" or !@hasField(ResultM, "val"))
@compileError("transform does not return a Monad type");
// Determine monad type
const Result = @FieldType(ResultM, "val");
if (ResultM != Monad(Result))
@compileError("transform does not return a Monad type");
return Result;
}
Now that the signature is well known, on to the definition. Below is the full definition. It is very similar to the definition to io.async() from above, with some new annotations highlighting the differences:
pub fn bind(
m: Monad(T),
transform: anytype,
io: std.Io,
) Monad(ReturnType(@TypeOf(transform))) {
const Result = ReturnType(@TypeOf(transform));
const Context = struct { m: Monad(T), io: std.Io };
const TypeErased = struct {
fn start(context_: *const anyopaque, result_: *anyopaque) void {
const context_casted: *const Context =
@ptrCast(@alignCast(context_));
const result_casted: *ReturnType(@TypeOf(transform)) =
@ptrCast(@alignCast(result_));
// Firstly, await the monad value, so we can pass it to the
// function
const arg = context_casted.m.await(context_casted.io);
// This is an additional feature which this bind()
// function supports. If the monad contains a Tuple
// (https://ziglang.org/documentation/master/#Tuples),
// pass it in as the argument tuple, otherwise
// wrap it in a new tuple.
const arg_tuple =
if (@typeInfo(T) == .@"struct" and @typeInfo(T).@"struct".is_tuple)
arg
else
.{arg};
// Get the new monad from the function
const result =
@call(
.always_inline,
transform,
arg_tuple,
);
// Finally, await the returned monad. This value will ultimately be
// the value represented by the Monad(T) returned from bind()
result_casted.* = result.await(context_casted.io);
}
};
var result: Monad(ReturnType(@TypeOf(transform))) = undefined;
result.any_future = io.vtable.async(
io.userdata,
@ptrCast(&result.val),
.of(Result),
@ptrCast(&Context{ .m = m, .io = io }),
.of(Context),
TypeErased.start,
);
return result;
}
yield()
Now to cover what is happening in main(). This uses one new member function: monad.yield(), which is used to ensure any computations started by a monad finish before continuing. If it were not included, the program could close before it finished printing out everything! The implementation is fairly simple, it just checks if monad.any_future is non-null and passes it into io.vtable.await() if it is not:
pub fn yield(self: @This(), io: std.Io) void {
if (self.any_future) |any_future| {
var result: T = undefined;
io.vtable.await(io.userdata, any_future, @ptrCast(&result), .of(T));
}
}
Monad Laws
As a final section, lets take a brief look at the monad laws. For the two member functions added to Monad(T), these three laws must be obeyed. First some notation:
- m.bind is written as m >>= g where m is a Monad and g is the function.
- Function calls are in the form f g where f is the function and g is the argument.
- Function definitions are in the form (\x -> expression) where x is the function argument and replaces all instances of x within expression.
- Both sides of the ≡ character are functionally identical
Here are the laws written using the above notation:
Left identity: (return a) >>= h ≡ h a
Right identity: (m ) >>= return ≡ m
Associativity: (m >>= g ) >>= h ≡ m >>= (\x -> g x >>= h)
Working unit tests are implemented in test.zig for reference. Below are brief descriptions of each law:
Left Identity:
(return a) >>= h ≡ h a
> a is a value which is *not* inside of a monad. If we
> place it within a monad using return then bind the new
> monad to function h, it should be identical to if we
> simply called h with a as its argument.
Right Identity:
m >>= return ≡ m
> If Monad m is bound to the return function, the monad
> should stay the same.
Associativity:
(m >>= g) >>= h ≡ m >>= (\x -> g x >>= h)
> Finally, associativity. If Monad m is bound to function g,
> then the resulting monad is bound to function h, it should
> be the same as if a monad produced by the function g was
> bound to h, then Monad m is bound to that.
These three laws can take a little bit to get your head around but should make sense with enough patience.
More info on the Monad laws may be found at https://wiki.haskell.org/Monad_laws