Implement Concurrency Primitives

[spy16]

Depends on #12 and #14.

Requirements to be decided.

[lthibault]

Just quick brainstorm ... I'm really not sure if the following is a good idea... 😅

Nevertheless, #17 introduces the notion of a goroutine into Parens via the GoExpr type, and we still need to determine how goroutine management and synchronization should be done in Parens-flavored lisps. The simplest and most straightforward approach resembles native Go: don't help the user with anything. Memory is shared, race conditions are possible, goroutines can leak, synchronization must be explicit, and the runtime assumes nothing.

But it occurs to me that Lisp is not Go, and that there might be an opportunity for a bit of constructive hand-holding ... maybe.

Let us start with the observation that our GoExpr semantics differ slightly from the semantics of the native go statement. Whereas go func() { ... } represents calling a function in a separate thread of execution, GoExpr represents evaluating an expression in a separate thread. This distinction is largely meaningless, save for one fact: all lisp expressions return exactly one value. All go functions do not. They may return an arbitrary number of values, including zero.

Why does this matter? Because some bare-bones synchronization might be relatively easy when we don't have to handle arbitrary arities. It should be pretty easy to pass that return value back to the calling thread. Right now GoExpr throws away the result of evaluation:

func (ge GoExpr) Eval(ctx *Context) (value.Any, error) {
	child := ctx.fork()
	go func() {
		_, _ = child.Eval(ge.Value)
	}()
	return nil, nil
}

This means that if we want to recover the a value from a separate goroutine, we have to wrap the expression of interest in e.g. a second function invocation:

;; pseudocode
(let [ch make-chan]
    (go (my-expensive-func ch))
    (print (<- ch)))

But what if we allow users to recover the value of the expression they've evaluated in a separate thread? We could make GoExpr return a Promise type, which is invokable, and which blocks until a response is available when invoked.

type Promise struct{
    // both channels are buffered (len=1)
    val chan value.Any
    err chan error
}

(p Promise) Eval(ctx *Context) (value.Any, err) {    return p, nil    }

(p Promise) Invoke(ctx *Context, args ...value.Any) (val value.Any, err error) {
    select {
    case val = <-p.val
    case err = <-p.err
    }
    return
}

GoExpr could then be rewritten thusly:

type GoExpr struct {
	Value value.Any
}

// Eval forks the given context to get a child context and launches goroutine
// with the child context to evaluate the Value.
func (ge GoExpr) Eval(ctx *Context) (value.Any, error) {
	child := ctx.fork()

        p := Promise{
                val: make(chan value.Any, 1)
                err: make(chan error, 1)
        }

	go func() {
                // N.B.:  we don't need to close any of the channels (see note below).
		if val, err := child.Eval(ge.Value); err != nil {
                    p.err <- err  // non-blocking due to buffer
                } else {
                    p.val <- val
                }
	}()
	return nil, nil
}

The initial lisp code can now be rewritten as:

(print ((go my-expensive-func)))

A quick note on performance. Note that because we never have to close the channel, we can recycle these using a clever mix of runtime.SetFinalizer and sync.Pool.

Just to reiterate, I'm not sure this is a good idea. My gut says that Go's concurrency semantics won't map onto a functional language perfectly, and that we'll have to find some new ways of expressing familiar concepts like go or <-ch. On the other hand, I'm not 100% sold on this particular approach. Moreover, I'm very much attached to Go's "hands-off" approach to concurrency, so all of these things need to be weighed against each other.

In any case, this has been nagging me for a few days, so I wanted to get your thoughts. 🙂

[spy16]

Oooh this is interesting. I will think about the concurrency part itself a bit more before commenting.

But I am thinking forcing the promise for value shouldn't be done through invokable just because it might be confusing. We could use the Clojure approach may be? (deliver promise) or @promise

[lthibault]

But I am thinking forcing the promise for value shouldn't be done through invokable just because it might be confusing

Agreed.

We could use the Clojure approach may be? (deliver promise) or @promise

How about a method on promise? (.resolve p), or something similar?

One of my major gripes with Clojure that the default namespace too cluttered. I'd rather not add any globals if we can avoid it. The @ notation is alright, but I'm also wary of introducing too much special notation, lest our lisp engine devolve into an outright lisp implementation.

I will think about the concurrency part itself a bit more before commenting.

👍 Yeah, I'm still mulling this over on my end as well. I agree we should take the time to do it right.

Addendum:

Whatever solution we go for, it should also support a SelectExpr!