[Relay][RFC] Resolve cyclic dependency in Closure

[MarisaKirisame]

see #4139 .
Currently, relay evaluate a function to a closure. It contain both the code of the function, and a mapping of every free variable inside that function, to the value of the free variable. when a closure is invoked, that mapping is used for the free variable. This is needed because the default approach, looking up the value from the environment (also known as dynamic binding), is buggy and will cause incorrect evaluation.
However, when a recursive closure is created, the mapping will contain value of every free variable - including the recursive function, and, subsequently, the closure itself!
I propose to add the following value, a RecValue, and a RecTable.
A RecValue is a shared_ptr of a RecTable, and a size_t index.
A RecTable is a vector of Closure.
Additionally, every closure will now have a Map<Variable, size_t> mapping, which store value of mutually recursive variable

[MarisaKirisame]

I also think that we should employ a cycle detector in tvm - this method can only eliminate a certain class of cycle, but there will be more as relay program grow more complex. #3423

[tqchen]

@MarisaKirisame thanks for taking a stab at this. I can understand the problem, but it would be great if you could give some examples about the solution so that everyone is on the same page

Ideally we want a simple enough solution that can remain stable for a while/

[MarisaKirisame]

@tqchen it is fixed in #4155 , and it is a small change that is readable.
In case of mutual recursion, the Closure clos; line at 129 will be replaced with tvm::Array<Closure> clos; size_t idx;

[tqchen]

i can see the code, but still it would be great if you can add an example explaining the data structure, and how it could fix the problem :)

It would also be great to discuss if we need to specifically produce different types of closure in runtime and if we could canonicalize so we only need one runtime closure

[MarisaKirisame]

I am confused. Coming from a PL perspective, this is obvious. I am not bragging, but everyone have different perspective, and from my perspective I suffer from curse of knowledge.

We can only keep RecClosure and have its binding = nullptr for non recursive one.
However, it get more complicate at mutual recursion, so I want to have them seperate.

[tqchen]

Of course it is not a curse :)It is gives you merit to educate others and makes these ideas more accessible :)

I can understand what is going on in the code(via indirection) but it is also worthwhile to discuss if we can keep the closure design as minimum and discuss the choices(multiple variations of closure or the more generic one, which is more complex ), especially when it comes to the recursive support.

[MarisaKirisame]

@tqchen it is possible to merge the two in one and use nullptr, however the design of mutual recursion will require each recclosure to keep both a vector of closure, and index (so it cannot be merged). Hence, I think they should be seprated.

It is indeed ugly, but the principled approach to dealing with this is to employ a cycle detector alongside the shared_ptr.

[joshpoll]

Coming from a PL perspective, this is obvious.

The solution is in fact not obvious even from a PL perspective. Xavier Leroy, famous for his work on OCaml, outlines multiple closure representations including their handling of recursive and mutually recursive functions.

[masahi]

I assume this is no longer active.