proposal: spec: lazy values

[ianlancetaylor]

This is just a thought. I'm interested in what people think.

Background:

Go has two short circuit binary operators, && and ||, that only evaluate their second operand under certain conditions. There are periodic requests for additional short circuit expressions, often but not only the ?: ternary operator found originally in C; for example: #20774, #23248, #31659, #32860, #33171, #36303, #37165.

There are also uses for short circuit operation in cases like conditional logging, in which the operands to a logging function are only evaluated if the function will actually log something. For example, calls like

    log.Verbose("graph depth %d", GraphDepth(g))

where log.Verbose only logs a message if some command line flag is specified, and GraphDepth is an expensive operation.

To be clear, all short circuit operations can be expressed using if statements (or occasionally && or || operators). But this expression is inevitably more verbose, and can on occasion overwhelm more important elements of the code.

    if log.VerboseLogging() {
        log.Verbose("graph depth %d", GraphDepth(g))
    }

In this proposal I consider a general mechanism for short circuiting.

Discussion:

Short circuiting means delaying the evaluation of an expression until and unless the value of that expression is needed. If the value of the expression is never needed, then the expression is never evaluated.

(In this discussion it is important to clearly understand the distinction that Go draws between expressions (https://golang.org/ref/spec#Expressions) and statements (https://golang.org/ref/spec#Statements). I'm not going to elaborate on that here but be aware that when I write "expression" I definitely do not mean "statement".)

In practice the only case where we are interested in delaying the evaluation of an expression is if the expression is a function call. All expressions other than function calls complete in small bounded time and have no side effects (other than memory allocation and panicking). While it may occasionally be nice to skip the evaluation of such an expression, it will rarely make a difference in program behavior and will rarely take a noticeable amount of time. It's not worth changing the language to short circuit the evaluation of any expression other than a function call.

Similarly, in practice the only case where we are interested in delaying the evaluation of an expression is when passing that expression to a function. In all other cases the expression is evaluated in the course of executing the statement or larger expression in which it appears (other than, of course, the && and || operators). There is no point to delaying the evaluation of expression when it is going to be evaluated very shortly in any case. (Here I am intentionally ignoring the possibility of adding additional short circuit operators, like ?:, to the language; the language does not have those operators today, and we could add them without affecting this proposal.)

So we are only interested in the ability to delay the evaluation of a function call that is being passed as an argument to some other function.

In order for the language to remain comprehensible to the reader, it is essential that any delay in evaluation be clearly marked at the call site. One could in principle permit extending function declarations so that some or all arguments are evaluated lazily, but that would not be clear to the reader when calling the function. It would mean that when reading a call like Lazy(F()) the reader would have to be aware of the declaration of Lazy to know whether the call F() would be evaluated. That would be a recipe for confusion.

But at the same time the fact that Go is a compiled type safe language means that the function declaration has to be aware that it will receive an expression that will be evaluated lazily. If a function takes an bool argument, we can't pass in a lazily evaluated function call. That can't be expressed as a bool, and there would be no way for the function to request evaluation at the appropriate time.

So what we are talking about is something akin to C++ std::future with std::launch::deferred or Rust futures::future::lazy.

In Go this kind of thing can be done using a function literal. The function that wants a lazy expression takes an argument of type func() T for some type T, and when it needs the value it calls the function literal. At the call site people write func() T { return F() } to delay the evaluation of F until the point where it is needed.

So we can already do what we want. But it's unsatisfactory because it's verbose. At the call site it's painful to have to write a function literal each time. It's especially painful if some calls require lazy evaluation and some do not, as the function literal must be written out either way. In the function that takes the lazy expression, it's annoying to have to explicitly invoke the function, especially if all you want to do is pass the value on to something like fmt.Sprintf.

Proposal:

We introduce a new kind of type, a lazy type, represented as lazy T. This type has a single method Eval() that returns a value of type T. It is not comparable, except to nil. The only supported operation, other than operations like assignment or unary & that apply to all types, is to call the Eval method. This has some similarities to the type

interface {
    Eval() T
}

but it is not the same as regards type conversion.

A value v of type T may be implicitly converted to the type lazy T. This produces a value whose Eval() method returns v. A value v of type T1 may be implicitly converted to the type lazy T2 if T1 may be implicitly converted to T2. In this case the Eval() method returns T2(v). Similarly, a value v of type lazy T1 may be implicitly converted to the type lazy T2 if T1 may be implicitly converted to T2. In this case the Eval() method returns T2(v.Eval()).

We introduce a new kind of expression, lazy E. This expression does not evaluate E. Instead, it returns a value of type lazy T that, when the Eval method is first called, evaluates E and returns the value to which it evaluates. If evaluation of E panics, then the panic occurs when the Eval method is first called. Subsequent calls of the Eval method return the same value, without evaluating the expression again.

For convenience, if the various fmt functions see a value of type lazy T, they will call the Eval method and handle the value as though it has type T.

Some additions will be needed to the reflect package. Those are not yet specified.

The builtin functions panic, print, and println, will not call the Eval method of a value of type lazy T. If a value of type lazy T is passed to panic, any relevant recover will return a value of that type.

That is the entire proposal.

Examples:

This permits writing

package log
func Verbose(format string, a ...lazy interface{}) {
    if verboseFlag {
        log.Info(format, a...)
    }
}

Calls to the function will look like

    log.Verbose("graph depth %d", lazy GraphDepth(g))

The GraphDepth function will only be called if verboseFlag is true.

Note that it is also fine to write

    log.Verbose("step %d", step)

without having to write lazy step, using the implicit conversion to lazy T.

If we adopt some form of generics, this will permit writing (edited original proposal to use current syntax):

func Cond[T any](cond bool, v1 lazy T, v2 lazy T) T {
    if cond {
        return v1.Eval()
    }
    return v2.Eval()
}

This will be called as

    v := cond(useTls, lazy FetchCertificate(), nil)

In other words, this is a variant of the ?: operator, albeit one that requires explicit annotation for values that should be lazily evaluated.

Note:

This idea is related to the idea of a promise as found in languages like Scheme, Java, Python, C++, etc. A promise would look like this (edited original proposal to use current syntax):

func Promise[T any](v lazy T) chan T {
    c := make(chan T, 1)
    go func() { c <- v.Eval() }()
    return c
}

A promise would be created like this:

    F(promise.Promise(lazy F())

and used like this:

func F(c chan T) {
    // do stuff
    v := <-c
    // do more stuff
}

[randall77]

In the implementation of Verbose, don't you need to call Eval on the elements of a before passing them to log.Info? Or are you assuming log.Info will do that? (Does log.Info bottom out at the fmt package at some point?)

[jimmyfrasche]

Is it safe to Eval from multiple threads simultaneously?

If Eval panics on the first call do future calls panic with the same value?

Since the result of t := lazy v is essentially a function, instead of an Eval method could evaluation be written t()?

Would the Verbose example provided need the lazy declaration? The thunks have to be evaluated somewhere, presumably within fmt, but until then the lazy T would fit in an interface same as any other value.

[zigo101]

related: #36497

I believe what @jimmyfrasche means is: lazy expression with lifetime bound is prone to cause careless subtle concurrency bugs. An example:

func foo(z bool) {
	c := make(chan struct{})
	a, b = 1, 2
	
	go func() {
		<-c
		a, b = 8, 9
	}()
	
	f := func(b bool, x lazy int) {
		close(c)
		if b {
			println(x.Eval())
		}
	}
	
	f(z, lazy a + b)
}

It looks it should be the duty of programmers to avoid data races.

BTW, is it good to reuse the defer keyword as lazy?

[ianlancetaylor]

@randall77

I'm assuming that log.Info bottoms out in the fmt package, yes. That is true of the log package in the standard library (although there it is log.Print rather than log.Info).

@jimmyfrasche

Yes, it should be safe to call Eval concurrently from multiple goroutines.

I hadn't thought about calling Eval a second time if the first time panics; I'm not sure what the right approach is. It could panic again, or it could return the zero value.

Yes, for many uses we could use t() rather than t.Eval(). The main advantage of t.Eval() is that the fmt package can apply it automatically. But I suppose that if lazy types show up in reflection, then the fmt package can handle them automatically anyhow. So maybe t() is better. It does have the advantage of not adding a method to the language spec.

You are probably right that the Verbose example would work without using lazy in the function declaration.

@go101

Using defer rather than introducing a new keyword is a good idea. Thanks.

[alanfo]

There are a number of areas where 'lazy' techniques are beneficial and anything which makes such techniques easier for the Go programmer to use (as this proposal would) is therefore welcome.

As far as passing lazy arguments at the call site is concerned, you make two practical points both of which I agree with:

1. We're only normally interested in deferred evaluation of function calls as other expressions are usually cheap and quick to evaluate anyway.

2. Readability is improved enormously if there's some visual indication that such a call will be evaluated lazily.

Despite (2), lazy could be omitted because of the implicit conversion from T to lazy T and one could envisage 'lazy' programmers (pun intended) doing this, even from function calls, though tools could try to enforce best practice in this area.

Rather than rely on tools, I'd like to make a suggestion:

1. The use of lazy would be obligatory where expressions consisting of or involving function calls were passed as arguments to functions with lazy parameter types. Only the function calls themselves would need to be decorated with lazy, not the rest of the expression (if any). So, for example, you'd pass 1 + lazy f() rather than lazy (1 + f()). This would also seem more natural if defer were used in place of lazy to avoid creating a new keyword.

2. In all other cases, lazy would not be allowed at all at the call site which I think would reflect what people would prefer to do in practice anyway.

[beoran]

Once we have generics, I think it would probably be easy to have a generic Lazy function that does lazy evaluation. So, while this seems interesting, I would rather have generics first and then see if we can solve the problem with them instead.

[fzipp]

Shouldn't eval be a built-in function rather than a method? Go's built-in types don't have methods so far. It's "len(slice)", not "slice.Len()", so I'd expect "eval(v)".

@beoran Generics don't simplify lazy evaluation. You still have to write a function literal somewhere.

[fzipp]

Why not let "lazy E" simply be of type "func() T"?

func Cond(type T)(cond bool, v1 func() T, v2 func() T) T {
    if cond {
        return v1()
    }
    return v2()
}

v := cond(useTls, lazy FetchCertificate(), nil)

Less characters on the use-site (+2 for for each "()" in the parameter list and -5 for each ".Eval" in the body), and it does not require a new type. "lazy E" would just be a shorthand for "func() T { return E }".

And then why not introduce short lambda syntax:

v := cond(useTls, {FetchCertificate()}, nil)
v := cond(useTls, func FetchCertificate(), nil)

or similar. (In this specific example we can write

v := cond(useTls, FetchCertificate, nil)

anyway)

[urandom]

@fzipp, while I would personally welcome a shorthand syntax for function literals, and thing it would greatly improve the language itself, it itself will not help create easy-to-use lazy values.

A lazy value would, once invoked, compute the actual value once, store it somewhere in memory, and then provide it. And subsequent invocations will only result in fetching that same computed value.

Yours is but a function call. There is nothing in your syntax that would tell me or the compiler that whatever the function produces will be returned on subsequent calls without computing it again.

@ianlancetaylor, your Promise snippet doesn't really illustrate a promise that well. Once someone reads the promise channel, that promise can no longer be used, which isn't exaclty how promises work. Rather, Go would have to support something like go func() { close(c, v.Eval()) }() so that any reader of that channel will get the value.

[jimmyfrasche]

I hadn't thought about calling Eval a second time if the first time panics; I'm not sure what the right approach is. It could panic again, or it could return the zero value.

I would argue that one is interested in the result of evaluating the function which is either the return or the panic. I imagine it could be hard to debug if you sent a lazy value to a dozen places and it panic'd in one of them but not the others, especially if concurrency is involved. It would also mean that you'd get the panic if you eval'd in a debugger even if it had been eval'd before and the panic had been recovered and discarded making it hard to see what's gone wrong.

Also, it should be possible to convert a defer T to a func() T for interoperability with older code. This was possible with a method since you could do f((defer g(x, y)).Eval). If this were another implicit conversion you could use f(defer g(x, y)) even when f expects a func() T. I'm not a fan of implicit conversions in general but all the ones here seem appropriate since it's all sugar.

If I write the expression defer f(g()) presumably g is evaluated immediately and the thunk is f(value returned by g) so if you want both to be deferred, you need to write defer func() T { return f(g()) }(). If a func() T could also be implicitly converted to a defer T you could just write func() T { return f(g()) } but then you lose the guarantee that the same result is always returned and that f(g()) is evaluated at most once and is safe to evaluate in parallel, so that seems like a bad idea.

[fzipp]

@urandom Right, Ian proposed cached lazy values. The question is if the caching is really needed, certainly not by the given examples. With generics (as @beoran suggested) a cached lazy value implementation could look like this:

package lazy

func Of(type T)(f func() T) Val(T) {
	return &val{f: f}
}

type Val(type T) interface {
	Eval() T
}

type val(type T) struct {
	f      func() T
	value  T
}

func (v *val(T)) Eval() T {
	if v.f != nil {
		v.value = v.f()
		v.f = nil
	}
	return v.value
}

A function with lazy parameters:

func Cond(type T)(cond bool, v1, v2 lazy.Val(T)) T {
	if cond {
		return v1.Eval()
	}
	return v2.Eval()
}

Usage:

v := Cond(useTls, lazy.Of(func() *Certificate { return FetchCertificate(x) }), nil)

The issue is still mainly the verbosity of the function literal:

But it's unsatisfactory because it's verbose. At the call site it's painful to have to write a function literal each time.

With some kind of lambda expression syntax:

v := Cond(useTls, lazy.Of({FetchCertificate(x)}), nil)
v := Cond(useTls, lazy.Of(func FetchCertificate(x)), nil)