Google Go (golang) Concurrency abstractions (futures and promises)

Martin Sulzmann

Programming language abstractions

Hide implementation details
Capture recurring programming patterns
Close(r) to the problem domain
Examples:
- System-level programming in C
- Business applications in Java
Not every abstraction fits every purpose
Need a rich tool box of abstractions
Abstractions are either built into the language (e.g. OO in Java) or can be provided as libraries/design patterns
Abstractions emerge by looking at examples and recognize recurring patterns
In essence, we require a new 'little' (domain-specific) language which enriches our host language by providing additional combinators (API functionality)

Motivation

Typical use case:

Asynchronous computation
Result, once available, shall be available many times

Example

Inform friends about some booking request.

First try

    ch := make(chan Comp)
    go func() {
        r, s := booking()
        ch <- Comp{r, s}
    }()

    // friend 1
    go func() {
        v := <-ch
        fmt.Printf("\n %d %b", v.val, v.status)
    }()

    // friend 2
    go func() {
        v := <-ch
        fmt.Printf("\n %d %b", v.val, v.status)
    }()

Channel to communicate result.
Asynchronous (non-blocking) computation of booking by using a separate thread.

Issue?

Only one of the friends obtains the result.

How to fix?

Server guarantees that result can be obtained multiple times.
Client guarantees that other clients can obtain the (same) result.

Server tries

    ch := make(chan Comp)
    go func() {
        r, s := booking()
        for {
            ch <- Comp{r, s}
        }
    }()

    // friend 1
    go func() {
        v := <-ch
        fmt.Printf("\n %d %b", v.val, v.status)
    }()

    // friend 2
    go func() {
        v := <-ch
        fmt.Printf("\n %d %b", v.val, v.status)
    }()

Client tries

    ch := make(chan Comp)
    go func() {
        r, s := booking()
        ch <- Comp{r, s}
    }()

    // friend 1
    go func() {
        v := <-ch
        go func() {
            ch <- v
        }()
        fmt.Printf("\n %d %b", v.val, v.status)

    }()

    // friend 2
    go func() {
        v := <-ch
        go func() {
            ch <- v
        }()
        fmt.Printf("\n %d %b", v.val, v.status)
    }()

Summary

Something "simple" gets complicated.
Design choice hard coded.
User code hard to read and to maintain.
Need proper (programming language) abstraction to hide implementation details.

Futures

Requirements + Abstraction

Asynchronous computation
Result, once available, shall be available many times

Interface:

type Future

func future(func() (int,bool)) Future

func (Future) get() (int,bool)

Use case:

var f Future

f = future(booking)  // non-blocking


// non-blocking access
go fun() {
     r,s := f.get()
   }()

// blocking access
r,s := f.get()

Think of a future as an initially empty program variable.
Once a value is supplied, the same value can be retrieved an arbibrary number of times.

Sample implementation

type Future chan Comp

func future(f func() (int, bool)) Future {
    ch := make(chan Comp)
    go func() {
        r, s := f()
        v := Comp{r, s}
        for {
            ch <- v
        }
    }()
    return ch

}

func (f Future) get() (int, bool) {
    v := <-f
    return v.val, v.status
}

"Server" variant.
Design choices + implementation details hidden.
Still some technical issue ("infinite loop), to be solved later.

Examples

    f := future(booking)

    // friend 1
    go func() {
        r, s := f.get()
        fmt.Printf("\n %d %b", r, s)
    }()

    // friend 2
    go func() {
        r, s := f.get()
        fmt.Printf("\n %d %b", r, s)
    }()

Easy to read and understand!
"Future" programming pattern useful in other situations as well.

Extensions

Choice among multiple bookings

Suppose we might try two alternative bookings and wish to inform our friends about the first available one.

    f1 := future(booking)
    f2 := future(booking2)
    f := f1.alt(f2)

    // friend 1
    go func() {
        r, s := f.get()
        fmt.Printf("\n %d %b", r, s)
    }()

    // friend 2
    go func() {
        r, s := f.get()
        fmt.Printf("\n %d %b", r, s)
    }()

alt is a new combinator.
Chooses among the first available future.
Result is again a future.

`alt` implementation - first try

func (f1 Future) alt(f2 Future) Future {
    return future(func() (int, bool) {
        ch := make(chan Comp)
        go func() {
            r, s := f1.get()
            ch <- Comp{r, s}
        }()

        go func() {
            r, s := f2.get()
            ch <- Comp{r, s}
        }()
        v := <-ch
        return v.val, v.status
    })
}

Helper threads start race to retrieve the first avaiable "future" result.
Pro: Doesn't require any fancy language extension, just channels + goroutines.
Cons: We end up with some "dead code" (dormant, blocked thread)
- A smart run-time might detect that there's no alive reference to this piece of code. Unlikely that Go implements this (expensive) garbage collection strategy.

`alt` implementation - second try

Problem goes away if we use select.

func (f1 Future) alt(f2 Future) Future {
    return future(func() (int, bool) {
        var r int
        var s bool
        select {
        case v := <-f1:
            r = v.val
            s = v.status
        case v := <-f2:
            r = v.val
            s = v.status
        }
        return r, s
    })
}

Closing a future

type Future struct {
    comm chan Comp
    cl   chan bool
}

func future(f func() (int, bool)) Future {
    ch := make(chan Comp)
    c := make(chan bool)
    go func() {
        r, s := f()
        v := Comp{r, s}
        done := false
        for !done {
            select {
            case <-c:
                done = true
            default:
                ch <- v
            }
        }
    }()
    return Future{ch, c}

}

func (f Future) close() {
    close(f.cl)
}

func (f Future) get() (int, bool) {
    v := <-f.comm
    return v.val, v.status
}

func (f1 Future) alt(f2 Future) Future {
    return future(func() (int, bool) {
        var r int
        var s bool
        select {
        case v := <-f1.comm:
            r = v.val
            s = v.status
        case v := <-f2.comm:
            r = v.val
            s = v.status
        }
        return r, s
    })
}

Correct usage of close in the hands of the user.
Multiple close calls lead to failure.

Further examples

Holiday planning

We ask our bank for the current exchange range, e.g. 100Euros to Dollar.
The bank will need to consult some traders to tell us the exchange rate. This may take some time.
There's no point waiting for the answer, there are still lots of other things we need to do for planning our holiday.
Once, the exchange rate becomes available eventually, we wish to be informed.
In computer science terms, the above can be expressed as follows

f:= future(ask bank for exchange rate 100Euros to Dollar)

f.onSuccess(func(rate in) () {
    inform me about the rate
  })

Short summary

A future represents an an initially unknown/incomplete computation.
The main thread of execution continues.
Once the computation is successfully completed completed, we wish to retrieve the result.
In the above, we assume that onSuccess is like future an asynchronous operation. The callback function (argument of onSuccss) will be executed once the future computation is completed successfully.

Details - holiday planning

Suppose, we consider either a holiday to the USA or Switzerland. We are given some primitives to query the exchange rate and request some (hotel) room.

func rateEuroToDollar(x int) (int, bool) 
func rateEuroToFranc(x int) (int, bool) 

// Input amount in dollar/franc
// Output: reference to some room
func bookUS(x int) (int, bool) 
func bookSwiss(x int) (int, bool)

Each of the above primitives returns a pair (int, bool) where the first component contains the result and the second component indicates exceptional behavior. For example, say bookUS(70) yields (34,false) then the room request could not be processed successfuly.

First attempt

Here is a possible implementation of our holiday planning exercise.

    d, d_ok := rateEuroToDollar(100)
    r, r_ok := bookUS(d)

    if d_ok && r_ok {
        fmt.Printf("Going to the US %d", r)
    } else {
        f, f_ok := rateEuroToSwiss(100)
        r, r_ok := bookSwiss(f)

        if f_ok && r_ok {
            fmt.Printf("Going to Switzerland %d", r)
        }

    }

Discuss the pros/cons

What if the US booking finally 'fails'?
How to take advantage of additional processor resources (cores)?
The above implies that we give preference to the US booking. What if we're happy to get any booking at all?

Second attempt

Suppose the sub-computations "us booking" and "swiss booking" are represented by

func usa() (int, bool)
func swiss() (int, bool)

Let's use some Go concepts we have just learnt to improve our holiday planning example.

var chan (int, bool)   // pairs used for convenience
ch = make(chan (int, bool))

// carry out both booking requsts asynchronously
go func() {
    ch <- usa()
}

go func() {
    ch <- swiss()
}


// query the result
x, r := <- ch
if !r {
  x, r := <- ch
  if r {
    // success
  }

} else {
 // success
}

What if we favor the USA over Switzerland?

We need to introduce another channel where we give preference to the "US" channel.

var chan1 (int, bool)   // pairs used for convenience
ch1 = make(chan (int, bool))
var chan2 (int, bool)   
ch2 = make(chan (int, bool))

// carry out both booking requsts asynchronously
go func() {
    ch1 <- usa()
}

go func() {
    ch2 <- swiss()
}


// query the result
x, r := <- ch1
if !r {
  x, r := <- ch2
  if r {
    // success
  }

} else {
 // success
}

In the above, we query the result "synchronously". Typically, we will do something useful while waiting for the result of the booking request. Here is the "asynchronous" variant.

var chan1 (int, bool)   // pairs used for convenience
ch1 = make(chan (int, bool))
var chan2 (int, bool)   
ch2 = make(chan (int, bool))

// carry out both booking requsts asynchronously
go func() {
    ch1 <- usa()
}

go func() {
    ch2 <- swiss()
}

// Asynchronously
go func() {
   // query the result
   x, r := <- ch1
   if !r {
     x, r := <- ch2
     if r {
       // success
     }

  } else {
    // success
  }
}

Erh, there's a lot of boiler-plate code required (helper threads + channels).

The actual program logic of our holiday planning example becomes harder to "interpret" from the program text alone.

We wish to focus on the problem domain specific aspects and hide as much as possible implementation details (threads, channels, etc).

Let's look closer. Isn't there a recurring program pattern? Yes, this program pattern is known as a future.

Final attempt using futures and some combinators.

Note: Some 'white lies'. The actual implementation is slightly more verbose.

    f1 := future(rateEuroToDollar(100))
    f2 := f1.then(bookUS)

    f3 := future(rateEuroToFranc(100))
    f4 := f3.then(bookSwiss)

    f5 := f2.orElse(f4)

    f5.onSuccess(func(x int) { fmt.Print("Holiday") })

As much as possible, all computations are carried out asynchronously (non-blocking).
Observe that all of the above Future API functions/methods (future, then, etc) are non-blocking.
It becomes much easier to adapt/maintain our program.
For example, suppose we demand that (1) the dollar amount must be at least 40, and (2) any of the two alternatives will do (we no longer favor the US over Switzerland).
We can carry out the above by simply changing two lines in our program.

    f0 := future(rateEuroToDollar(100))
        f1 := f0.when(func(x int) bool { return x >= 40 }) // (1)
    f2 := f1.then(bookUS)

    f3 := future(rateEuroToFranc(100))
    f4 := f3.then(bookSwiss)

    f5 := f2.any(f4)  // (2)

    f5.onSuccess(func(x int) { fmt.Print("Holiday") })

Here's the actual implementation where we make use of a generic interface. Recall that interface{} represents the any type (see Object in java).

    f1 := future(func() (interface{}, bool) { return rateEuroToDollar(100) })
    f2 := f1.then(func(x interface{}) (interface{}, bool) {
        i := x.(int)
        return bookUS(i)
    })

    f3 := future(func() (interface{}, bool) { return rateEuroToFranc(100) })
    f4 := f3.then(func(x interface{}) (interface{}, bool) {
        i := x.(int)
        return bookSwiss(i)
    })

    f5 := f2.orElse(f4)

    f5.onSuccess(func(x interface{}) { fmt.Print("Holiday") })

Recall that the function call rateEuroToDollar(100) immediately computes the result. However, the future combinator assumes that we supply as an argument a parameter-less function which when called yields the result.

Futures - success and failure

Future API with "generic" interface.

Interface

func future(f func() (interface{}, bool)) Future
func (ft Future) get() (interface{}, bool)
func (ft Future) onSuccess(cb func(interface{}))
func (ft Future) onFailure(cb func())

The additional boolean value shall represent success and failure
Method syntax:

ft.onSuccess(func(x interface{}) { ...})

Callback function applied if the future ft is successfull (yields some result and the boolean value true).

Sample implementation

// Sadly, pairs are not first-class, so we require this wrapper struct
type Comp struct {
    value interface{}
    ok    bool
}

// A future, once available, will be transmitted via a channel.
type Future chan Comp

func future(f func() (interface{}, bool)) Future {

    future := make(chan Comp)

    go func() {
        v, o := f()
        c := Comp{value: v, ok: o}
        for {
            future <- c
        }
    }()

    return future

}

Computation runs in a separate thread
Result communicated via channel
Sadly, pairs are not first-class, so we require a 'wrapper' structure
Recall that a future can be read many times. Hence, we repeatidly write the computed value into the channel by using a for loop which never terminates.

func (ft Future) get() (interface{}, bool) {
    c := <-ft
    return c.value, c.ok

}

Retrieve value by reading from channel
Aside:
- Several reads/gets shouldn't interfere with each other
- That is, it should be possible to concurrently execute several gets
- Possible in our implementation?

func (ft Future) onSuccess(cb func(interface{})) {
    go func() {
        v, o := ft.get()
        if o {
            cb(v)
        }
    }()

}

func (ft Future) onFailure(cb func()) {
    go func() {
        _, o := ft.get()
        if !o {
            cb()
        }
    }()

}

Non-blocking get variants for either success or failure

Futures - orElse

Suppose, we plan a holiday. We query the exchange rate (e.g. 100 Euro to Dollar) by consulting bank1.

Querying the exchange rate can be done asynchronously via a future.

rate1 := future( ...)

What if bank1 doesn't get back to us? Well, then we consult bank2.

rate2 := future( ...)

How can we compose both futures in a neat way such that we only rely on rate2 if rate1 fails?

rate := rate1.orElse(rate2)

orElse is a new combinator (method) which combines two futures to obtain a new future. We obtain the left future if successful. Otherwise, we obtain the right future.

func (ft Future) orElse(ft2 Future) Future {

    return future(func() (interface{}, bool) {
        v, o := ft.get()
        if o {
            return v, o
        }
        v2, o2 := ft2.get()
        if o2 {
            return v2, o2
        }
        // if both fail, yield first one
        return v, o
    })

}

Futures - when

The future result shall only be used if it satisfies a guard condition.

Let's consider our running example.

rate := (rate1.when(func(x interface{}) bool { return x.(int) >= 40})).orElse(rate2)

We require that the rate given by bank1 satisfies a guard condition.
Here, must obtain at least 40 Dollars for our 100 Euros.
If the guard condition is not satisfied, the future fails.

Short-version

rate := rate1.when(func(x interface{}) bool { return x.(int) > 40}).orElse(rate2)

when is a new combinator which imposes a condition on the future result. If the condition is not satisfied, we fail. Otherwise, we pass on the future result.

func (ft Future) when(guard func(interface{}) bool) Future {
    return future(func() (interface{}, bool) {
        v, o := ft.get()
        if o && guard(v) {
            return v, o
        }
        return v, false
    })

}

Futures - then

If we get a proper exchange, then we can go ahead with our booking.

rate := rate1.when(func(x interface{}) bool { return x.(int) > 40}).orElse(rate2)

booking := rate.then(func(dollars interface{}) (interface{}, bool) {
             // book a single room in hotel in local currency
             return 1, true
})

then is a combinator (method) which takes a future and a transformer function. If the future result becomes available, we create a new future computation. Otherwise, we fail.

func (ft Future) then(f func(interface{}) (interface{}, bool)) Future {
    return future(func() (interface{}, bool) {
        v, o := ft.get()
        if o {
            v2, o2 := f(v)
            return v2, o2
        }
        return v, false

    })

}

Futures - any

Sometimes we are happy to get any exchange rate.

rate1 := ...
rate2 := ...
rate := rate1.any(rate2)

The difference to orElse is that we don't impose any specific order.
- rate1 and rate will be executed asynchronously.
- Whichever computation succeeds first will be chosen.
- In contrast, rate1.orElse(rate2) strictly favors rate1.

func (ft Future) any(ft2 Future) Future {

    return future(func() (interface{}, bool) {

        var v interface{}
        var o bool

        // check for any result to become available
        select {
        case x := <-ft:
            if x.ok {
                v = x.value
                o = x.ok
            } else {
                v, o = ft2.get()
            }

        case x2 := <-ft2:
            if x2.ok {
                v = x2.value
                o = x2.ok
            } else {
                v, o = ft.get()
            }
        }

        return v, o
    })
}

Futures - Summary of combinators

future
- asynchronous execution of some computation
onSuccess onFailure
- eventually query the result
orElse
- choose among two future computations, preference given to the first one
when
- some guard/side conditions must be fulfilled to be successful
then
- essentially wait for a future computation to become successful and then proceed with a new computation
any
- choose among two future computations (arbitrary choice)

Exercise Futures

Create a small application where you asynchronously execute 3 http requests to different pages and pick the first one which sends a response. Print the header to console.

Hints:


func req() {
...
response, err := http.Get("www.someUrl.com")    --- Http request
response.Header                                 --- Get the header
..
}

Example solution


func getSite(url string, timeout time.Duration) Future {
    return future(func() (interface{}, bool) {
        resp, err := http.Get(url)
        time.Sleep(timeout)
        if err == nil {
            return resp, true
        }
        return err, false
    })
}

func main() {
    spiegel := getSite("http://www.spiegel.de", 0 * time.Second)
    stern := getSite("http://www.stern.de", 0 * time.Second)
    welt := getSite("http://www.welt.com", 0 * time.Second)
    first := spiegel.any(stern).any(welt)

    result, succeed := first.get()
    if succeed {
        response := result.(*http.Response)
        fmt.Println(response.Request.URL)
        header := response.Header
        fmt.Println(header)
        date := header.Get("Date")
        fmt.Println(date)
    }
}

Promises

The story so far:

Futures represent asynchronous computations
Futures are read-only and their result can be queried many times (once the result becomes available)

Is this enough for typical (concurrent) programming tasks?

Think about the classic producer-consumer pattern?

Currently, we lack an abstraction to complete a future at a specific program point.

Promises:

a write-once data container
initially empty
yields a future
can be completed (data value set) at a specific program point.

Producer-Consumer Example

func producer(p Promise) Future {
    return future(func() (interface{}, bool) {
        // (1) do something
        // (2) fulfill promise
        p.success(3)
        // do something else
        return 1, true
    })

}

func consumer(p Promise) Future {
    return future(func() (interface{}, bool) {
        // (1) do something
        p.future().onSuccess(
            func(x interface{}) {
                // do something with result x
            })

        return 1, true
    })

}

Promises - Basics

A promise yields a future
A promise shall be fulfilled (written) only once where full indicates the status (fulfilled yet or not)
Must protect access to full via a lock

type Promise struct {
    lock chan int
    ft   Future
    full bool
}

Create a promise

func promise() Promise {
    return Promise{full: false, ft: make(chan Comp), lock: make(chan int, 1)}
}

Obtaining the future from a promise is easy

func (pr Promise) future() Future {
    return pr.ft
}

Let's first consider a "try" Variant

func (pr *Promise) trySuccess(val interface{}) {
    pr.lock <- 1
    if !pr.full {
        pr.full = true
        go func() {
            for {
                pr.ft <- Comp{value: val, ok: true}
            }
        }()
    }

    <-pr.lock
}
// pr *Promise means that pr is passed by 'reference'
// necessary cause we might change the full status

Try to fulfill if not already fulfilled (no operation in this case then)
Useful in case we wait for competing results (answers from different sources but only care about at most one answer)
We can also fail a promise

func (pr *Promise) tryFail() {
    pr.lock <- 1
    if !pr.full {
        pr.full = true
        go func() {
            for {
            pr.ft <- Comp{ok: false}
                    }
        }()
    }

    <-pr.lock

}

What about success?
- Similar to trySuccess but in case there are multiple success calls we should raise an error (e.g. by throwing an exception).
Another handy combinator.

func (p *Promise) tryCompleteWith(f Future) {
    go func() {
        v, o := f.get()
        if o {
            p.trySuccess(v)
        } else {
            p.tryFail()
        }
    }()
}

Promises - first

Recall the implementation of any for futures.
With promises this can be implemented as follows.

func first(f1 Future, f2 Future) Future {
    p := promise()

    p.tryCompleteWith(f1)
    p.tryCompleteWith(f2)

    return p.future()

}

`first` versus `any`

There is a subtle semantic difference.

Consider the case where

f1 yields a failing value (i.e. boolean flag yields false)
f2 is not available yet

Then, we can observe the following:

`first(f1,f2) yields a with future with failing value
- In first the call p.tryCompleteWith(f1) encounters an empty promise.
- This then leads to the subsequent call p.tryFail()
f1.any(f2) yieldsf2`
- In any the first select case is available (f1 is available)
- Because f1 yields a failing value, f2 is returned.

Exercise Promises

Try to solve the same problem as before with the Promises Api.

Example solution


func getSite(url string, timeout time.Duration) Future {
    return future(func() (interface{}, bool) {
        resp, err := http.Get(url)
        time.Sleep(timeout)
        if err == nil {
            return resp, true
        }
        return err, false
    })
}

func main() {
    spiegel := querySite("http://www.spiegel.de", 0 * time.Second)
    stern := querySite("http://www.stern.de", 0 * time.Second)
    welt := querySite("http://www.welt.com", 0 * time.Second)

    first := first(spiegel, stern, welt)

    result, succeed := first.get()
    if succeed {
        response := result.(*http.Response)
        fmt.Println(response.Request.URL)
        header := response.Header
        fmt.Println(header)
        date := header.Get("Date")
        fmt.Println(date)
    }
}

Conclusion

Futures are read-only and their result can be queried many times (once the result becomes available)
Promises are a write-once data container.
We can query the future result of a promise
We can fulfill/fail a promise at a specific program point
Powerful combinators (any, ...)

What we have done.

Future and promises library in GoLang

Exercises

Coordination

Below is a list of (concurrent) programming exercises which involve some classic coordination/synchronization tasks.
Implement as many as possible in Go.
If possible make use of futures and promises.
Futures and promises might not always the best fit. Part of the exercise is to find out how useful and versatile futures and promises are in practice.

Dining philosoper

It's a classic. Everybody knows this one, so details are omitted.

Sleeping barber

Consider a barber shop where there is only one barber. When there are no customers the barber sleeps. When a customer arrives he awakes and cuts the customer's hair. In case of several customers arriving the barber chooses one randomly.

Variations:

There are n waiting chairs. If the barber is busy, the customer takes a seat. If there are no seats left, the customer leaves (and tries again after a certain amount of time)
There are several barbers serving customers

Santa claus

Santa repeatedly sleeps until wakened by either all of his nine reindeer, back from their holidays, or by a group of three of his ten elves. If awakened by the reindeer, he harnesses each of them to his sleigh, delivers toys with them and finally unharnesses them (allowing them to go off on holiday). If awakened by a group of elves, he shows each of the group into his study, consults with them on toy R&D and finally shows them each out (allowing them to go back to work).

Variations:

Santa gives priority to the reindeer in the case that there is both a group of elves and a group of reindeer waiting

Gossiping girls

There n girls, each of whom knows a unique piece of initial information. They communicate by telephone calls, and whenever two speak they share all the gossip that they know. The goal is to determine the minimum number of calls necessary for all of the girls to learn all of the initial information.

From futures/promises to GoLang

We have seen that futures/promises can be expressed in terms of goroutines, synchronous channels and select.

An interesting question is, can goroutines, synchronous channels and select be expressed in terms of futures/promises?

Appendix - Summary of futures and promises

package main

import "fmt"
import "time"

// Sadly, pairs are not first-class, so we require this wrapper struct
type Comp struct {
    value interface{}
    ok    bool
}

// A future, once available, will be transmitted via a channel.
type Future chan Comp

func future(f func() (interface{}, bool)) Future {

    future := make(chan Comp)

    go func() {
        v, o := f()
        c := Comp{value: v, ok: o}
        for {
            future <- c
        }
    }()

    return future

}

func (ft Future) get() (interface{}, bool) {
    c := <-ft
    return c.value, c.ok

}

func (ft Future) onSuccess(cb func(interface{})) {
    go func() {
        v, o := ft.get()
        if o {
            cb(v)
        }
    }()

}

func (ft Future) onFailure(cb func()) {
    go func() {
        _, o := ft.get()
        if !o {
            cb()
        }
    }()

}

func (ft Future) then(f func(interface{}) (interface{}, bool)) Future {
    return future(func() (interface{}, bool) {
        v, o := ft.get()
        if o {
            v2, o2 := f(v)
            return v2, o2
        }
        return v, false

    })

}

func (ft Future) orElse(ft2 Future) Future {

    return future(func() (interface{}, bool) {
        v, o := ft.get()
        if o {
            return v, o
        }
        v2, o2 := ft2.get()
        if o2 {
            return v2, o2
        }
        // if both fail, yield first one
        return v, o
    })

}

func (ft Future) any(ft2 Future) Future {

    return future(func() (interface{}, bool) {

        var v interface{}
        var o bool

        // check for any result to become available
        select {
        case x := <-ft:
            if x.ok {
                v = x.value
                o = x.ok
            } else {
                v, o = ft2.get()
            }

        case x2 := <-ft2:
            if x2.ok {
                v = x2.value
                o = x2.ok
            } else {
                v, o = ft2.get()
            }
        }

        return v, o
    })
}

func (ft Future) when(guard func(interface{}) bool) Future {
    return future(func() (interface{}, bool) {
        v, o := ft.get()
        if o && guard(v) {
            return v, o
        }
        return v, false
    })

}

type Promise struct {
    lock chan int
    ft   Future
    full bool
}

func promise() Promise {
    return Promise{full: false, ft: make(chan Comp), lock: make(chan int, 1)}
}

func (pr Promise) future() Future {
    return pr.ft
}

// success has single-assignment semantics.
// Currently, we simply ignore multiple assignments.
// Hence, we refer to the method as 'trySuccess'.
// That is, in case of several attemps, only the first will succeed.
func (pr *Promise) trySuccess(val interface{}) {
    pr.lock <- 1
    if !pr.full {
        pr.full = true
        go func() {
            for {
                pr.ft <- Comp{value: val, ok: true}
            }
        }()
    }

    <-pr.lock
}

func (pr *Promise) success(val interface{}) {
    pr.trySuccess(val)
}

// See trySuccess
func (pr *Promise) tryFail() {
    pr.lock <- 1
    if !pr.full {
        pr.full = true
        go func() {
            for {
                pr.ft <- Comp{ok: false}
            }
        }()
    }

    <-pr.lock

}

func (p *Promise) tryCompleteWith(f Future) {
    go func() {
        v, o := f.get()
        if o {
            p.trySuccess(v)
        } else {
            p.tryFail()
        }
    }()
}

func first(f1 Future, f2 Future) Future {
    p := promise()

    p.tryCompleteWith(f1)
    p.tryCompleteWith(f2)

    return p.future()

}

func rateEuroToDollar(x int) (int, bool) {
    return x * 2, true
}

func rateEuroToFranc(x int) (int, bool) {
    return x * 3, true
}

func rateEuroToSwiss(x int) (int, bool) {
    return x * 1, true
}

func bookUS(x int) (int, bool) {
    return 1, true
}

func bookSwiss(x int) (int, bool) {
    return 1, true
}

func naiveHolidayPlanning() {
    d, d_ok := rateEuroToDollar(100)
    r, r_ok := bookUS(d)

    if d_ok && r_ok {
        fmt.Printf("Going to the US %d", r)
    } else {
        f, f_ok := rateEuroToSwiss(100)
        r, r_ok := bookSwiss(f)

        if f_ok && r_ok {
            fmt.Printf("Going to Switzerland %d", r)
        }

    }

}

func futureHolidayPlanning() {
    f1 := future(func() (interface{}, bool) { return rateEuroToDollar(100) })
    //  f2 := f1.then(bookUS)
    f2 := f1.then(func(x interface{}) (interface{}, bool) {
        i := x.(int)
        return bookUS(i)
    })

    f3 := future(func() (interface{}, bool) { return rateEuroToFranc(100) })
    f4 := f3.then(func(x interface{}) (interface{}, bool) {
        i := x.(int)
        return bookSwiss(i)
    })

    f5 := f2.orElse(f4)

    f5.onSuccess(func(x interface{}) { fmt.Print("Holiday") })

}

func main() {


    futureHolidayPlanning()
    // wait a bit, so we get to see some results
    time.Sleep(2 * 1e9)

}

Sample solutions

We consider sample solutions for

sleeping barber,
santa claus, and
dining philosphers.

There are well-known solutions which make use of message-based primitives such as send/receive.

Our goal is to consider solutions which employ futures and promises. In the following, we discuss each of the above examples.

We briefly summarize some general insights we gained:

The examples inspire new functionality
- Santa Claus (firstSucc, collectN)
- Dining philosopher (atomic trySuccess of several promises)
Sleeping barber:
- Appears to be the least elegant solution.
- We lack a queuing mechanism and a failed customer has to retry
Dining philosophers:
- Solution has issues which could be solved assuming there is support to atomically trySuccess several promises,
Santa claus:
- Appears to be the most convincing solution
Futures/promises are highly useful for expressing high-level coordination tasks
But they are not a silver bullet (which is no surprise)

Sample solution - Sleeping barber

Some helper function

func sleep(x int, y int) {
    var z time.Duration
    z = (time.Duration)((rand.Int()%x + y) * 10)
    time.Sleep(z * time.Millisecond)
}

/////////////////////////////
// Hair salon
// 
// Each round
// - customer start race for barber
// - barber waits for customer
// - new round starts once a customer gets a hair cut
//
// Effectively, an application of the 'producer-consumer' pattern.
// Cons:
//   - no queuing mechanism
//   - a failed customer simply has to retry
// Observations:
//   - we have to ensure that the id of the customer is in the correct scope
//   - customers are chosen randomly as expected

func salon() {

    for {
        barber := promise()
        done := promise()
        // barber
        barber.future().onSuccess(func(x interface{}) {
            fmt.Printf("Customer %d gets a hair cut \n", x.(int))
            time.Sleep(1 * 1e9)
            done.trySuccess(1)
        })

        for i := 0; i < 5; i++ {
            // customer i. we create a future here, to add a bit of 'randomess' to trySuccess.
            // Because we don't know when the execution of the future starts we have to use an additional variable (id)
            // to store the information about the current user. If we use i as closure the result will always be 5.
            // The reason therefore is that i is not in the correct execution scope so we don't get a "snapshot" of the value.
            id := i
            future(func() (interface{}, bool) {
                sleep(5,5)
                barber.trySuccess(id)
                return 1, true
            })
        }

        done.future().get()

    }

}

Sample solution - Santa claus

The main concern of futures and promises is to deal/coordinate asynchronous computations whose result will only be available somewhen in the future. In our case, we waint for a deer or elf to become "ready". We will use a fairly simplistic model to check for the "ready" result.

func sleep(x int, y int) {
    var z time.Duration
    z = (time.Duration)((rand.Int()%x + y) * 10)
    time.Sleep(z * time.Millisecond)


func elfReady() int {
    sleep(3, 3)
    fmt.Print("elf ready \n")
    return 1
}

func deerReady() int {
    sleep(3, 2)
    fmt.Print("deer ready \n")
    return 1
}

We simply start a timer and then report after some time that a deer and elf is ready. We don't care which deer/elf is ready. The above functions simply yield a integer number after a fixed time period.

Given that deers/elves are not instantly ready, we use a future to perform the "ready" computations.

func elf() Future {
    return future(func() (int, bool) {
        return elfReady(), true
    })

}

func deer() Future {
    return future(func() (int, bool) {
        return deerReady(), true
    })

}

Now, it starts getting more interesting. We require either a group of three elves or nine deers. So, we start three elf future computations and nine deer future computations. How can we check that within each group all computations have succeeded? We require yet another combinator to achieve this.

func (ft Future) collect(ft2 Future) Future {
    return future(func() (int, bool) {
        v, o := ft.get()
        v2, o2 := ft2.get()
        if o && o2 {
            return v + v2, true
        }
        dummy := 1
        return dummy, false 
    })

}

The above collect combinator waits for the result of two futures. In our simplistic model, we combine results by simply adding up the resulting integer values. [Aside: In a more realistic implementation, we should indicate which future has failed and for example give preference to the first failed future]

So, santa simply needs to collect three elf futures and nine deer futures.

    elves := collectN(3, elf)
    deers := collectN(9, deer)

where

func collectN(x int, f func() Future) Future {
    var y Future
    if x == 1 {
        y = f()
    } else { // no check if below 1
        y = f().collect(collectN(x-1, f))
    }
    return y

}

What remains is to check for the first successful group via the following combinator

func firstSucc(f1 Future, f2 Future) Future {
    p := promise()

    p.trySuccCompleteWith(f1)
    p.trySuccCompleteWith(f2)

    return p.future()

}

where

func (p *Promise) trySuccCompleteWith(f Future) {
    go func() {
        v, o := f.get()
        if o {
            p.trySuccess(v)
        }
    }()
}

Note that the difference to tryCompleteWith is that we only try in case the future is successful.

Finally, here comes our santa claus.

func santaLoop() {

    for {

        elves := collectN(3, elf)
        deers := collectN(9, deer)
        group := firstSucc(elves, deers).when(santaSleeping)

        x, _ := group.get()
        santaSleeps = false
        if x == 3 {
            fmt.Print("R&D \n")
        }
        if x == 9 {
            fmt.Print("Deliver toys \n")
        }
        time.Sleep(1 * 1e9)
        santaSleeps = true

    }
}

In the above, we use a simply test to check if santa is back and sleeping

func santaSleeping(x int) bool {
    return santaSleeps

}

where

var santaSleeps bool

is some global variable.

Discussion

New features/combinators

The Santa Claus example lead us to enricht the set of combinators

collectN which resembles a form of a barrier
firstSucc which is a variant of any but only cares about the first successful future

Priority

We have not enforced the priority rule:

Santa gives priority to the reindeer in the case that there is both a group of elves and a group of reindeer waiting.

This seems rather tricky to achieve with futures and promises. The problem lies in the definiton of firstSucc. In case both futures are successful, one of the two will be randomly choosen.

Recall

func firstSucc(f1 Future, f2 Future) Future {
    p := promise()

    p.trySuccCompleteWith(f1)
    p.trySuccCompleteWith(f2)

    return p.future()

}

Given that our futures are implemented via channels, we might give an alternative implementation which employs a form of 'nested' select statements to give priority to the first future.

Avoid complete group retry

Consider the following scenario. Two elves are ready but there's no third elf in sight. Nine deers are ready and santa is sleeping. Hence, we select the group of nine deers and santa delivers toys. Meanwhile, a third elf arrives.

In our current implementation, in each round we perform a complete retry for each group even if that group has not been selected. Recall

func santaLoop() {

    for {

        elves := collectN(3, elf)
        deers := collectN(9, deer)
        group := firstSucc(elves, deers).when(santaSleeping)
               ...
       }
}

It seems wasteful to start three elf futures where we haven't used them yet. It would be much smarter to reuse parts of the computations of the previous round.

Idea: Restart collection of three elf or nine deer futures only if necessary. We will make use of promises to achieve this.

Second santa solution making use of promises

We signal successful assembly of a group via a promise

func colElves(p Promise) {
    p.tryCompleteWith(collectN(3, elf))
}

func colDeers(p Promise) {
    p.tryCompleteWith(collectN(9, deer))
}

Santa creates a promise for each group. We reuse the old promise if the promise hasn't been used yet.

func santa2() {

    var pE Promise
    var pD Promise

    pE = promise()
    pD = promise()
    colElves(pE)
    colDeers(pD)

    for {

        group := firstSucc(pE.future(), pD.future()).when(santaSleeping)

        x, _ := group.get()
        santaSleeps = false

        if x == 3 {
            fmt.Print("R&D \n")
            time.Sleep(1 * 1e9)
            santaSleeps = true
            pE = promise()
            colElves(pE)

        }
        if x == 9 {
            fmt.Print("Deliver toys \n")
            time.Sleep(1 * 1e9)
            santaSleeps = true
            pD = promise()
            colDeers(pD)
        }

    }

}

In the above, consider the case that a group of three elves becomes available.

        if x == 3 {
            fmt.Print("R&D \n")
            time.Sleep(1 * 1e9)
            santaSleeps = true
            pE = promise()
            colElves(pE)

        }

We create a new promise for elves but reuse the existing promise for deers. After all, meanwhile a group of nine deers may have assembled successfully.

Sample solution - dining philosopher


/////////////////////////////
// Dining philosopher
// 
// Idea:
// - forks represented by promises
// - philos race for two forks (left and right)
// There's an issue:
// - Say we only obtain one fork but not the other!
// - Then we fail to eat.
// - So there could be the scenario that each philospher only gets one fork
// - There's no deadlock as we start a new round (race)
// 
// What we would like to express is that
// trying to succeed two promises is performed atomically.
// That is:
//
// atomically {
//  left.trySuccess(id)
//  right.trySuccess(id)
// }
//
// We either can successfuly set both promises or none of the two is set.

func philo(id int, left *Promise, right *Promise) Future {
    var f Future

    fmt.Printf("Philo %d start race \n", id)

    // race for two forks
    left.trySuccess(id)
    right.trySuccess(id)

    fmt.Printf("race done \n")

    // check if successful
    f = future(func() (interface{}, bool) {
        v1, o1 := left.future().get()
        v2, o2 := right.future().get()

        if o1 && o2 && v1.(int) == id && v2.(int) == id {
            return id, true
        }
        return id, false

    })
    return f
}

func main() {

    for {

        fmt.Printf("new round \n")

        var f1 Promise
        var f2 Promise
        var f3 Promise

        f1 = promise()
        f2 = promise()
        f3 = promise()

        p1 := philo(1, &f1, &f2)
        p2 := philo(2, &f2, &f3)
        p3 := philo(3, &f3, &f1)

        p1.onSuccess(func(x interface{}) {
            fmt.Printf("Philo 1 eats \n")
        })

        p1.onFailure(func() {
            fmt.Printf("Philo 1 cannot eat \n")
        })

        p2.onSuccess(func(x interface{}) {
            fmt.Printf("Philo 2 eats \n")
        })
        p2.onFailure(func() {
            fmt.Printf("Philo 2 cannot eat \n")
        })

        p3.onSuccess(func(x interface{}) {
            fmt.Printf("Philo 3 eats \n")
        })
        p3.onFailure(func() {
            fmt.Printf("Philo 3 cannot eat \n")
        })

        time.Sleep(1 * 1e9)

    }

}

Google Go (golang) Concurrency abstractions (futures and promises)

Programming language abstractions

Motivation

Example

First try

Server tries

Client tries

Summary

Futures

Requirements + Abstraction

Sample implementation

Examples

Extensions

Choice among multiple bookings

alt implementation - first try

alt implementation - second try

Closing a future

Further examples

Holiday planning

Short summary

Details - holiday planning

First attempt

Second attempt

Final attempt using futures and some combinators.

Futures - success and failure

Interface

Sample implementation

Futures - orElse

Futures - when

Futures - then

Futures - any

Futures - Summary of combinators

Exercise Futures

Example solution

Promises

Producer-Consumer Example

Promises - Basics

Promises - first

first versus any

Exercise Promises

Example solution

Conclusion

Exercises

Coordination

Dining philosoper

Sleeping barber

Santa claus

Gossiping girls

From futures/promises to GoLang

Appendix - Summary of futures and promises

Sample solutions

Sample solution - Sleeping barber

Sample solution - Santa claus

Discussion

New features/combinators

Priority

Avoid complete group retry

Second santa solution making use of promises

Sample solution - dining philosopher

`alt` implementation - first try

`alt` implementation - second try

`first` versus `any`