Fibonacci implementation in Go

Question

At the end of the Day 1 Go Course slides (pdf) there is an exercise stated as follows (NOTE: the course in the linked presentation is considered obsolete. If you are looking to learn Go the suggested route is first via http://tour.golang.org):

You all know what the Fibonacci series is. Write a package to implement it. There should be a function to get the next value. (You don't have structs yet; can you find a way to save state without globals?) But instead of addition, make the operation settable by a function provided by the user. Integers? Floats? Strings? Up to you.

How does the following solution rate with respect to its 'Go'-iness?

package fib

type BinOp func (uint64, uint64) uint64

func fib_intern(a, b uint64, op BinOp) uint64 {
    Fib = func(opnew BinOp) uint64 {
        return fib_intern(b, op(a,b), opnew)
    }
    return a
}

var Fib = func(op BinOp) uint64 {
    return fib_intern(0,1,op)
}

Which can then be called like:

package main

import (
    "./fib"
    "fmt"
)

func add(a, b uint64) uint64 {
    return a+b
}

func main() {
    for i := 0; i < 20; i++ {
        fmt.Println(fib.Fib(add))
    }
}

Answer 1

The link is dead and the code doesn't compile, but there is still an obvious issue to critique: Part of the challenge was to not save state with "global variables." In Go, package variables of the package main are typically considered "global variables". However, only a single instance of any package ever exists at run time, so package variables of all packages are essentially global variables as well. The code here uses a package variable fib.Fib, thus the code is failing the exercise from the start, working or not.

Edit: Thank you Anthony for tracking down the archived course and updating the question. It helps to have the full context. It also helps to have code working with a current version of Go, which is pretty easy:

package fib

type BinOp func(uint64, uint64) uint64

var Fib func(op BinOp) uint64

func init() {
    Fib = func(op BinOp) uint64 {
        return fib_intern(0, 1, op)
    }
}

func fib_intern(a, b uint64, op BinOp) uint64 {
    Fib = func(opnew BinOp) uint64 {
        return fib_intern(b, op(a, b), opnew)
    }
    return a
}

Go now has stricter checking of static dependencies and reports "initialization loop" with the old code. My update of your code works by moving the initial assignment of Fib to an init function, which runs at program startup.

I'll abandon this answer now and add another answer where I try to stick to your request for a review of the 'Go'-iness.

Answer 2

With working code it's fun to instrument it and watch it work. Each call to fib.Fib computes a new value in the sequence and also replaces itself with a new function literal to hold the new vaue. It's computationally efficient but it does keep allocating and discarding function literals, creating garbage on each call. A better solution would be one that avoided this memory churn. Having a sense for this isn't an idiom, but I think it counts for Go style, to be aware of your use of memory, and to find memory-efficient algorithms.

A purely stylistic issue is the name of the function fib_intern. Go style is to use camel-case as in fibIntern. But even this is redundant. Lower case always means non-exported, so simply 'fib' is enough. There's nothing wrong with having both Fib and fib. Go programmers understand that one is exported, one isn't, and that they are two different things. Perhaps you wanted a more descriptive name than just fib, but fib_intern isn't it. That tells your reader nothing that isn't obvious already.

Finally, the use of a relative import path, "./fib" is okay for a small exercise like this, but it's not a habit you want to form. Relative import paths have historically been problematic, and I think it's fine to do little experiments like this right on your GOPATH.

Answer 3

How about using channels to do it?

func fib(f func(int, int) int) chan int {

    ch := make(chan int)
    a, b := 0, 1
    go func() {
        for {
            a, b = b, f(a, b)
            ch <- a
        }
    }()
    return ch
}

This takes a function which returns an integer given two others, and returns a channel which will supply each term.

You can then run it by doing something like:

func add(a, b int) int {
    return a + b
}

func main() {

    ch := fib(add)
    for i := 0; i < 10; i++ {
        fmt.Println(<-ch)
    }
}

I'm still just getting used to go, so not sure how idiomatic this solution is. You would certainly need to ensure you stopped the goroutine by passing it a 'done' channel or something, but for quick jobs, this is a quick and easy solution.