Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

proposal: Go 2: allow self-referencing closures #33167

Open
pjebs opened this issue Jul 18, 2019 · 41 comments

Comments

@pjebs
Copy link

commented Jul 18, 2019

	inspect := func(chain []ChainModel, insert bool) {

		for i := range chain {
			cm := &chain[i]
			...
			inspect(cm.Parents, insert)   <------- error here
		}
	}

Has to be changed to:

	var inspect func([]ChainModel, bool)
	inspect = func(chain []ChainModel, insert bool) {

		for i := range chain {
			cm := &chain[i]
			...
			inspect(cm.Parents, insert)   <------- allowed
		}
	}

@gopherbot gopherbot added this to the Proposal milestone Jul 18, 2019

@gopherbot gopherbot added the Proposal label Jul 18, 2019

@pjebs

This comment has been minimized.

Copy link
Author

commented Jul 18, 2019

I think for recursive functions, this is a hassle and should be made "as an exception".

I admit it should not be high-priority, if accepted.

@av86743

This comment has been minimized.

Copy link

commented Jul 18, 2019

Even if implemented, this still won't work with mutual recursion.

@carlmjohnson

This comment has been minimized.

Copy link
Contributor

commented Jul 18, 2019

Block scope rules are already very complicated. I don't think there needs to be a new exception.

@bcmills

This comment has been minimized.

Copy link
Member

commented Jul 18, 2019

This proposal needs more detail. If := brings the declared variables in scope for a function declaration, should it also bring them in scope for other declarations? If not, why not?

Consider the following related examples:

https://play.golang.org/p/qJQRGcCHjAU:

	if err, ok := err.(net.Error); ok {
		fmt.Println(err)
	}

https://play.golang.org/p/yoQSNsSDRJZ:

	for i := range s[:len(s)-1] {
		i := i + 1
		fmt.Printf("%c", s[i])
	}

https://golang.org/doc/faq#closures_and_goroutines:

    for _, v := range values {
        v := v // create a new 'v'.
        go func() {
            fmt.Println(v)
            done <- true
        }()
    }
@bcmills

This comment has been minimized.

Copy link
Member

commented Jul 18, 2019

To be clear: I sympathize with the underlying problem. I just think it would be clearer to try to make func […] declarations work within a function body than to try to change the behavior of :=.

func […] {
	[…]
	func inspect(chain []ChainModel, insert bool) {
		for i := range chain {
			cm := &chain[i]
			...
			inspect(cm.Parents, insert)
		}
	}
	[…]
}
@av86743

This comment has been minimized.

Copy link

commented Jul 18, 2019

@bcmills

Without going radically with nested func-s, you could substitute redundant closure type automatically, via trivial AST rewrite or an equivalent, in cases like

func f() {
    // ...
    var g func(int) (bool, error) = func(x int) (bool, error) {
        return x == x, nil
    }
    // ...
}

This simple language extension (relaxation) is easy not only to implement, but also to describe.

Conveniently, const g func ... is failed because (I quote):

...: const initializer func literal is not a constant

Ah well. Variable func literal it is. Cannot make an exact equivalent of nested func in terms of a source language.

@wpalmer

This comment has been minimized.

Copy link

commented Jul 18, 2019

To be clear: I sympathize with the underlying problem. I just think it would be clearer to try to make func […] declarations work within a function body than to try to change the behavior of :=.

While I think that making func ... declarations work within non-global scopes would be beneficial (perhaps with some rules such as lowercase-only), I believe that is a separate concern and should not pollute this proposal.

Having := impact any scope which "begins" on that statement make so much sense, that I would go so far as to say that any exception to this rule is extremely unintuitive, and arguably goes against the current spec (after all, := does define a variable within the enclosing function)

@carlmjohnson

This comment has been minimized.

Copy link
Contributor

commented Jul 18, 2019

...: const initializer func literal is not a constant

I think I made an issue to complain about that before. My use case is const MyHandler http.HandlerFunc = func(w http.ResponseWriter, r *http.Request) { ... }

@ianlancetaylor

This comment has been minimized.

Copy link
Contributor

commented Jul 18, 2019

All our previous attempts to address this foundered on the need to support mutually recursive functions while preserving a clear declaration scope.

@bcmills

This comment has been minimized.

Copy link
Member

commented Jul 18, 2019

@ianlancetaylor, do you happen to have links for previous attempts?

My knee-jerk suggestion is to allow a locally-scoped func declaration to refer to any other func declaration that is not separated by a statement or non-constant expression. (That is: the two func declarations could have any number of intervening func or const declarations, and perhaps var declarations with constant initializers.)

@av86743

This comment has been minimized.

Copy link

commented Jul 18, 2019

@bcmills

the two func declarations could have any number of intervening func or const declarations, and perhaps var declarations with constant initializers.

What's the point in this contrived restriction? Allow to refer from any point in the code to any function in this and all enclosing function bodies, as well as to top-level functions. Like in many well-known languages that entirely liberated themselves from the concept of variable.

@alanfo

This comment has been minimized.

Copy link

commented Jul 18, 2019

I don't know how often people write recursive closures (I wrote a couple earlier this week) though I don't think the current situation is all that bad.

Sure, there's duplication but at least it's clear what's happening and it can cater for mutually recursive functions.

@bcmills

This comment has been minimized.

Copy link
Member

commented Jul 18, 2019

What's the point in this contrived restriction?

In general in Go, a variable in a local scope does not exist until its point of declaration. (See https://play.golang.org/p/szHNxwcSjwL.)

It would be confusing to allow a local func to close over a variable that does not yet exist — especially if it does so by invoking a different function that has closed over that variable. What value would the function observe for that variable if invoked before the variable declaration is evaluated? (The answer is especially unclear if the variable has a non-zero initial value.)

@ianlancetaylor

This comment has been minimized.

Copy link
Contributor

commented Jul 18, 2019

@bcmills I don't have any links. We discussed it quite a bit in the pre-open-source days.

@av86743

This comment has been minimized.

Copy link

commented Jul 18, 2019

@bcmills

It would be confusing to allow a local func to close over a variable that does not yet exist — especially if it does so by invoking a different function that has closed over that variable. What value would the function observe for that variable if invoked before the variable declaration is evaluated? (The answer is especially unclear if the variable has a non-zero initial value.)

You are mixing up things. Initialization of variables in a given scope is a non-related aspect of language semantics. Each function can access (or closure may be bound to) part of the variables from its body, from enclosing function bodies, and from the top (package) scope. Whereas initialization of all variables in all enclosing scopes is hoisted within corresponding scope (to put it simplistically) and precedes any invocation of function/closure which may use it. It is obvious if you consider allocation and initialization of variables in generated code.

@ianlancetaylor

This comment has been minimized.

Copy link
Contributor

commented Jul 18, 2019

@av86743 You're not wrong, but I think you are not considering shadowing. Consider https://play.golang.org/p/SxLl2NwMt9D .

@bcmills

This comment has been minimized.

Copy link
Member

commented Jul 18, 2019

@av86743, consider the following example:

	func f1() int {
		return f2()
	}

	x := f1()

	func f2() int {
		return x
	}

Without restrictions on declaration order, that example would be admitted — but now the value of the variable x depends upon itself!

The simple way to break that initialization cycle is to prohibit f1 from calling f2, since the variable x enters the scope in between the two function declarations.

@bcmills

This comment has been minimized.

Copy link
Member

commented Jul 18, 2019

Note that the compiler rejects the package-level equivalent of the above example today (https://play.golang.org/p/TVXlSYqrp9H).

But variable declarations within a function today do not have a compiler-determined initialization order as package-level variables do: instead, variable initializers within a function body execute in program order.

I think that changing function-local variables to use the more complex package initialization order would be a mistake: it would make the behavior of functions much more difficult to reason about.

@av86743

This comment has been minimized.

Copy link

commented Jul 18, 2019

@ianlancetaylor

Consider rewriting body of for in your example (or any other kind of scope that I have not mentioned earlier) as an invocation of an anonymous function. With this transformation, you also need to take care of multiple inter-scope level exits, however this is again a separate aspect of language semantics and this is clearly doable.

If this construction seems to be too complicated, in my earlier reply extend the set of scopes with every other kind of scope that is present in the language. This does not affect the line of reasoning: it is all right to use every function/closure in a given scope and enclosing scopes, including those defined later in the corresponding scope.

Granted, the analysis on closure dependencies has to take into account forward references to closures, which may affect hoisting of variable initializations.

@av86743

This comment has been minimized.

Copy link

commented Jul 18, 2019

@bcmills

Without restrictions on declaration order, that example would be admitted — but now the value of the variable x depends upon itself!

Note that the compiler rejects the package-level equivalent of the above example today (https://play.golang.org/p/TVXlSYqrp9H).

Yours is an example of diverging computation. In this case, compiler detected this - nice catch! However, nothing in this example precludes it from being successfully compiled and then executed - indefinitely or perhaps until stack overflows. There are also simpler ways to do the same. And there apparently should be ways to do this in golang today so that compiler will not recognize this - if you are familiar with halting problem.

Compiler fails your example because it, practically, does not make sense. How about something meaningful using forward function/closure references? If this is doable at the top level, same holds for nested scopes as well. Granted, it may not be a fast path - but only in presence of forward references. You will likely need topo sort and cutting cycles of mutual references which will be pretty much a no-op (O(1) if you wish) on fast path.

But variable declarations within a function today do not have a compiler-determined initialization order as package-level variables do: instead, variable initializers within a function body execute in program order.

"... execute in program order" is a simplistic way to describe something which becomes more complicated and more difficult to describe precisely in the presence of forward function/closure references. Nothing, though, that would be contrary to "idiom" that every variable is initialized before it is ever used.

@bcmills

This comment has been minimized.

Copy link
Member

commented Jul 18, 2019

@av86743, there are certainly languages in which it makes sense to have loosely-defined initialization and control flow. (Haskell and Prolog in particular come to mind.)

However, Go today is a very mutative, very procedural language. I think applying that style of programming to Go would be too much of an impedance mismatch with the rest of the language.

@av86743

This comment has been minimized.

Copy link

commented Jul 18, 2019

However, Go today is a very mutative, very procedural language. I think applying that style of programming to Go would be too much of an impedance mismatch with the rest of the language.

I support that. Simple and by extension efficient in compilation and execution - that's golang that we want.

@loren-osborn

This comment has been minimized.

Copy link

commented Jul 24, 2019

Making the := operator accept function values like this reminds me of how Go handles the untyped-ness of literal constants. A numeric literal can’t have an in-memory representation until it has a type (to give it at least a bit-width, for instance). := should only need the type of the RHS function in order to have the LHS variable declared with its correct type. The “value” of the function needn’t be evaluated until the variable has been declared from the type inference. I think this is at least rationalization that this is not a special case for function values.

I’m interested to hear any opinions on this. Am I off in left field on this? Can the function be parsed properly into an AST, to get type information, then be evaluated and validated in a separate step of compilation?

@ianlancetaylor

This comment has been minimized.

Copy link
Contributor

commented Jul 24, 2019

@loren-osborn If I understand you correctly, then you are correct: the function does not need to be evaluated to determine the type of the variable. But that's not the issue here. The issue here is scoping: in a variable declaration, when does the variable itself come into scope? And when doing mutual recursion of function closures, how does scoping work so that the closures can refer to each other?

The current scoping rules are, in my opinion, simple and clear. I don't see how to change them without making them less simple and less clear. And that seems like a bad tradeoff for a case that rarely arises in practice, and that can be done today, when it does arise, in a slightly more awkward manner.

@pjebs

This comment has been minimized.

Copy link
Author

commented Jul 25, 2019

Let me reframe the perspective of the issue. I can see that people are discussing it from the angle of Go's scope laws that will need to be adjusted to accomodate the proposal.

I wrote that an exception should be made for closures for this reason:

Let's assume you created a closure for calculating the factorial of a number:

var factorial func(x uint) uint = func(x uint) uint {
	if x == 0 {
		return 1
	}
	
	return x * factorial(x-1)  <-------- recursion
}

My proposal is really about expanding the current capabilities of closures to include common mathematical concepts like recursion.

Currently a closure can't be used with recursion. You have to rewrite it as a Func Declaration to make use of recursion.

This is especially the case if you define a closure as a package level variable - where you can't use the "trick" of first declaring a func variable and then defining the func body in the next statement.

You can see with this code snippet: https://play.golang.org/p/GQHtC-2v8Ep

The compiler produces this error:

./prog.go:7:5: initialization loop:
	prog.go:7:5 factorial refers to
	prog.go:7:5 factorial
@carlmjohnson

This comment has been minimized.

Copy link
Contributor

commented Jul 25, 2019

If it’s at the package level, you can recurse by using a non-variable declaration. I can’t think of why you’d need to write a recursing variable function at package level, but if it comes up, you can use an init func.

@ianlancetaylor

This comment has been minimized.

Copy link
Contributor

commented Jul 25, 2019

@pjebs How, precisely, do you propose to expand the current capabilities of closures?

And will your proposal support mutually recursive nested functions?

@pjebs

This comment has been minimized.

Copy link
Author

commented Jul 25, 2019

can you give me an example of a "mutually recursive nested functions"?

@ianlancetaylor

This comment has been minimized.

Copy link
Contributor

commented Jul 25, 2019

func F() int {
	var f1, f2 func(int) int
	f1 = func(i int) int {
		if i <= 0 {
			return 0
		}
		return i + f2(i - 1)
	}
	f2 = func(i  int) int {
		return i + f1(i - 1)
	}
	return f2(1)
}
@loren-osborn

This comment has been minimized.

Copy link

commented Jul 25, 2019

This is rather verbose, but here is a package variable initialized to a truly recursive closure: https://play.golang.org/p/fNtifzRLjDt

UPDATED: By this I mean the function the package variable is initialized to will not change its recursive behavior if the package variable later changes. (This would require making a copy of the package variable value to test.) The point being that it’s self-contained. ... and no, I didn’t say it was pretty.

@av86743

This comment has been minimized.

Copy link

commented Jul 25, 2019

https://play.golang.org/p/fNtifzRLjDt :

// ...
var factorial = (func() func(x uint) uint {
// ...
@loren-osborn

This comment has been minimized.

Copy link

commented Jul 27, 2019

For completeness, here’s the code I was linking to:

package main

import (
	"fmt"
)

var factorial func(x uint) uint = (func() func(x uint) uint {
	var inner func(x uint) uint
	inner = func(x uint) uint {
		if x == 0 {
			return 1
		}

		return x * inner(x-1)
	}
	return inner
})()

func main() {

	fmt.Println(factorial(3))
}
@pjebs

This comment has been minimized.

Copy link
Author

commented Jul 30, 2019

@ianlancetaylor

If a func literal is set to a variable, that variable is available within the func literal for the function to refer to itself.
As always, the function's body's statements represent a new scope so it can always be overwritten. I don't think there will be backward compatibility issues.

If the func literal is not set to a variable, the function does not have the ability to be recursive under this proposal. However for an ancillary proposal, for self-invoking func literals, a possibility is the ability to use _() to call itself. This would apply whether the func literal is set to a variable or not.

mutually recursive nested functions

func F() int {
	var f1, f2 func(int) int
	f1 = func(i int) int {
		if i <= 0 {
			return 0
		}
		return i + f2(i - 1)
	}
	f2 = func(i  int) int {
		return i + f1(i - 1)
	}
	return f2(1)
}

Mutually recursive nested functions would not be permitted. This proposal is a "special case" and is limited to a function referring to only itself - in essence I am proclaiming that ALL functions (whether it's a func literal or func declaration) are AWARE of itself.

For mutually recursive functions the current way (as in your example) is sufficient.

The underlying idea of this proposal is that the concept of self-recursion is an important mathematical concept which is worthy of respect - irrespective of how uncommon it is in practice or how convenient the workaround is.

@ianlancetaylor

This comment has been minimized.

Copy link
Contributor

commented Jul 30, 2019

In my personal opinion, the language does not need another special case that only works for self-recursive functions. Mutually recursive functions are a real thing that we should not neglect.

That said, if I understand you correctly, you are suggesting that we implement _(args) in a function literal to mean to call the literal itself recursively. That would be a very different meaning for _ compared to its usual meaning. Even if we agree to add a special case, I do not think that would be a good syntax to use.

@pjebs

This comment has been minimized.

Copy link
Author

commented Jul 30, 2019

I chose _ because you can argue the function was set to "_" (discard)

@loren-osborn

This comment has been minimized.

Copy link

commented Aug 12, 2019

While i’m not advocating for the _(arg1, ...) proposal (as it is inconsistent with the primary meaning of _), I do like that this does allow an inline recursive function to be easily passed as a function argument. Perhaps another symbol is more appropriate, (I’m not suggesting one.) If so (using @ as a placeholder symbol) something like @{non-negative integer}(arg1, ...) could refer to nesting parent function definitions to support multiple levels of indirect function recursion, such that @{1}(arg1, ...) would call the function definition enclosing the current function definition, and so on. @{0}(arg1, ...) would be synonymous with @(arg1, ...) making zero the default.

@pjebs

This comment has been minimized.

Copy link
Author

commented Aug 14, 2019

maybe using a variant of the keyword func is acceptable. So inside a function, when referring to itself, perhaps func_(x). (note the discard character)

@carlmjohnson

This comment has been minimized.

Copy link
Contributor

commented Aug 14, 2019

Changing the language means everyone who learns Go has to learn the new syntax. I've run into this problem maybe twice in 5 years of writing Go. It was easy enough to solve by just declaring the function before use. It looked a little ugly to have the same function declaration twice in a row, but it was easy to write and not confusing to read. I don't think this problem is worth adding new language features for.

@ianlancetaylor

This comment has been minimized.

Copy link
Contributor

commented Aug 27, 2019

If a func literal is set to a variable, that variable is available within the func literal for the function to refer to itself.

It's important to note that this is not backward compatible. If the variable shadows another variable defined in an enclosing block, the reference inside the function literal would silently change from the outer variable to the inner variable. This silent change in language semantics would not be permitted by the language transition rules (https://github.com/golang/proposal/blob/master/design/28221-go2-transitions.md).

@pjebs

This comment has been minimized.

Copy link
Author

commented Aug 27, 2019

I will amend proposal since you are correct

@pjebs

This comment has been minimized.

Copy link
Author

commented Aug 27, 2019

Perhaps ^()?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
9 participants
You can’t perform that action at this time.