Rangefunc experiment in Go 1.22

20 February 2024

Bartłomiej Święcki

Backend Developer (behind-the-scenes squad) at Sonatus

About me

Hiding behind the scenes as a backend dev for some time now.

Indeed, I'm sufficiently seasoned to have been jokingly nicknamed 'grandpa' at a previous position

Multilingual: Assembler, C, C++, PHP, SQL, JavaScript, Python, Go (no Java, sorry)

Learning new language brings a new perspective, helps using other languages better.

I've been in love with Go since its beta versions...

... and using it as my primary language now.

It's been 7 years since I wrote my first Go code used in production.

Jealous of: generators in python,

def countdown(n):
    while n > 0:
        yield n     # <--- here's the `magic`
        n -= 1

for value in countdown(5):
    print(value)

Outputs:
5
4
3
2
1

Execution flow jumps between coroutine and the main flow
There is no memory overhead because the process is entirely managed within the execution flow.

generator expressions (also python),

transformed = (
    x * x
    for x in countdown(10)
    if x % 2 == 0
)

print(type(transformed))

for value in transformed:
    print(value)

Output:
<class 'generator'>
100
64
36
16
4

Very expressive syntax
Still no memory overhead

ranges in C++,

int main()
{
    auto even = [](int i) { return 0 == i % 2; };
    auto square = [](int i) { return i * i; };

    // the "pipe" syntax of composing the views:
    for (auto i : std::views::iota(0, 10)
                | std::views::filter(even)
                | std::views::transform(square))
        std::cout << i << std::endl;
}

Outputs:
0
4
16
36
64

Very clean and composable syntax, similar to Unix pipes
All calculated in-place, no memory overhead

functional-style processing in Rust

fn main() {
    let before = Some("body");
    let after = before
        .map(|x| x.to_uppercase())
        .map(|x| x + "!")
        .unwrap_or("default".to_string());
    
    println!("{after}")
}

Output:
BODY!

Similar pattern - no raw loops
Composable transformations

Can we have something similar in Go?

https://github.com/samber/lo - functional style programming in Go.

func main() {
    numbers := []int{1, 2, 3, 4, 5}

    result := lo.Filter(
        lo.Map(
            numbers,
            func(i int, _ int) int { return i * i },
        ),
        func(i int, _ int) bool { return i != 16 },
    )

    for _, i := range result {
        fmt.Println(i)
    }
}

Steps are executed sequentially
Arrays used to store intermediate results
Can not break calculations in the middle (give up after n elements)

How about channels?

func main() {
    ch1 := make(chan int)
    go func() {
        defer close(ch1)
        for i := 1; i <= 5; i++ {
            ch1 <- i
        }
    }()

    ch2 := make(chan int)
    go func() {
        defer close(ch2)
        for i := range ch1 {
            ch2 <- i * i
        }
    }()

    // ... (continued on the next slide)

How about channels (continued)?

    // ... (continued)

    ch3 := make(chan int)
    go func() {
        defer close(ch3)
        for i := range ch2 {
            if i != 16 {
                ch3 <- i
            }
        }
    }()

    for i := range ch3 {
        fmt.Println(i)
    }
}

Not so straightforward - doesn't fit in one slide ;)
Who controls goroutine termination?

Rangefunc experiment

Introduced in Go 1.22:

Go 1.22 includes a preview of a language change we are considering for a future version of Go: range-over-function iterators. Building with GOEXPERIMENT=rangefunc enables this feature.

From the rangefunc's Wiki:

We invite anyone who wants to help us understand the effects of the change to try using GOEXPERIMENT=rangefunc and let us know about any problems or successes encountered.

Basic example

package main

import "fmt"

func iota(
    yield func(int) bool, // Ignoring return value for now
) {
    yield(1)
    yield(2)
    yield(3)
}

func main() {
    for i := range iota {
        fmt.Println(i)
    }
}

Execute with:

export GOEXPERIMENT=rangefunc go run .

Infinite generator + break

func iota(yield func(int) bool) {
    for i := 0; ; i++ {
        if !yield(i) {
            return
        }
    }
}

func main() {
    for i := range iota {
        if i == 1000 {
            break // yield -> return false
        }
        if i%2 == 0 {
            continue // yield -> return true
        }
        fmt.Println(i)
        // yield -> return true
    }
}

Parametrized generator

func iota(yield func(int) bool) {
    for i := 0; ; i++ {
        if !yield(i) {
            return
        }
    }
}

extended to:

func iota(start, end, step int) func(yield func(int) bool) {
    return func(yield func(int) bool) {
        for i := start; i < end; i += step {
            if !yield(i) {
                return
            }
        }
    }
}

Multiplication table

func iota(start, end, step int) func(yield func(int) bool) {
    return func(yield func(int) bool) {
        for i := start; i < end; i += step {
            if !yield(i) {
                return
            }
        }
    }
}

func main() {
    for i := range iota(1, 11, 1) {
        for j := range iota(1, 11, 1) {
            fmt.Printf("%d * %d = %d\n", i, j, i*j)
        }
    }
}

Chaining generators - transform

func transform[T any](
    input iter.Seq[T], // Take some other sequence as an input
    t func(T) T,
) iter.Seq[T] {
    return func(yield func(T) bool) {
        for val := range input {
            transformed := t(val)
            if !yield(transformed) {
                return
            }
        }
    }
}

No godoc yet for iter package, source code to the rescue: https://github.com/golang/go/blob/go1.22.0/src/iter/iter.go

Chaining generators - filter

func filter[T any](
    input iter.Seq[T],
    f func(T) bool,
) iter.Seq[T] {
    return func(yield func(T) bool) {
        for val := range input {
            if f(val) {
                if !yield(val) {
                    return
                }
            }
        }
    }
}

Hope to see such tools in stdlib.

Chaining generators - helpers

func square[T constraints.Integer](v T) T {
    return v * v
}

func without[T constraints.Integer](withoutValue T) func(v T) bool {
    return func(v T) bool { return v != withoutValue }
}

Chaining generators - combining together

func main() {
    for i := range filter(
        transform(
            iota(0, 10, 1),
            square,
        ),
        without(16),
    ) {
        fmt.Println(i)
    }
}

Jay: we've got all calculated in memory!

Nay: the code is not pretty

Simplifying chaining code - first attempt

New combinable wrapper type:

type combinable[T any] iter.Seq[T]

Iota and all transformations return combinable:

func iota(start, end, step int) combinable[int] {

transform and filter are now methods of combinable:

func transform[T any](
    input iter.Seq[T], // Take some other sequence as an input
    t func(T) T,
) iter.Seq[T] {

func (input combinable[T]) transform(
    t func(T) T,
) combinable[T] {

Simplifying chaining code - first attempt - result

func main() {
    for i := range iota(0, 10, 1).
        transform(square).
        filter(without(16)) {
        fmt.Println(i)
    }
}

Jay: Nice looking code - can easily understand and extend

Nay: Can not change type of sequence element

Nay: Limited extendability of the combinable type - all its methods must be in the same package.

Simplifying chaining code - second attempt

Add a concept of converter function:

type converter[TIn, TOut any] func(iter.Seq[TIn]) iter.Seq[TOut]

transform and filter would need one more indirection layer:

func transform[TIn, TOut any](
    t func(TIn) TOut,
) converter[TIn, TOut] {
    return func(input iter.Seq[TIn]) iter.Seq[TOut] {
        return func(yield func(TOut) bool) {
            for val := range input {
                transformed := t(val)
                if !yield(transformed) {
                    return
                }
            }
        }
    }
}

This is getting out of control 🤯 but let's see where this leads us...

Simplifying chaining code 2 - combining converters

Go does not have generic variadic functions, we have to workaround:

func combine2[T1, T2 any](
    in iter.Seq[T1],
    l1 converter[T1, T2],
) iter.Seq[T2] {
    return l1(in)
}

func combine3[T1, T2, T3 any](
    in iter.Seq[T1],
    l1 converter[T1, T2],
    l2 converter[T2, T3],
) iter.Seq[T3] {
    return l2(combine2(in, l1))
}

// ... and so on, up to some number n of different converters

Simplifying chaining code 2 - the result

func main() {
    for i := range combine3(
        iota(0, 10, 1),
        transform(square[int]),
        filter(without(16)),
    ) {
        fmt.Println(i)
    }
}

Ok-ish...

Code is straightforward, easy to read, easy to extend.

Lost some type deduction abilities (square now needs explicit int).

Is it worth the effort?

Simplifying chaining code - birds eye view

It's all about golang's syntax - how to attach new code at the end of the existing one.

method2( method1(), ...)

I could find those methods in Go:

method call (.method1().method2()....) - which does not support generics
combine-like functions - which can be either variadic or generic but not both
... or

Simplifying chaining code - simplicity FTW

... or use intermediate variables:

method2( method1(), ...)

becomes:

result1 := method1()
result2 := method2(result1, ...)

I'm not the first one to end up with similar issues and solutions: https://github.com/golang/go/issues/33361

Simplifying chaining code - variable-based method

func main() {
    for i := range filter(
        transform(
            iota(0, 10, 1),
            square,
        ),
        without(16),
    ) {
        fmt.Println(i)
    }
}