FAQ

On 2013/06/10 20:44:22, rsc wrote:
I would like to avoid quadratic algorithms in general. I don't
understand this
well enough yet to say whether it's okay here.
As I said in the other CL, I might just not remember enough of this code to
understand what's going on.
Why do functions have to be revisited? I would hope that checking foo
would find
the cycle shown in your first message, without having to reset for the checking
of matchAnyFn.
Functions are allowed to refer to themselves in cycles. So to accept
this and avoid infintie recursion we don't go through the same function
body twice.

You arrive through a function F1, reach a variable V, that refers to F1:
should you visit F1 again? Should you complain for an init cycle? why?

Actually, you can already complain by looking at the initlist: when I
encounter a function I have already seen
- if it is in the initlist stack, then there should be no variable
appearing in between (otherwise the variable is referring to itself),
otherwise it is safe to ignore (it's just mutually recursive functions).
- if it is not on my stack, it was visited through another path,
everything referenced by it has been visited, so skipping it is safe.

The problem we need to solve is: check that in the graph of variables
and functions, any cycle must consist exclusively of functions.

https://codereview.appspot.com/9663047/

--

---
You received this message because you are subscribed to the Google Groups "golang-dev" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

Search Discussions

  • Russ Cox at Jun 21, 2013 at 7:43 pm
    Thanks for the description - I understand the problem now.
    Isn't there some sub-quadratic way to do this?

    Russ

    --

    ---
    You received this message because you are subscribed to the Google Groups "golang-dev" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-dev+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/groups/opt_out.

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
groupgolang-dev @
categoriesgo
postedJun 11, '13 at 6:01a
activeJun 21, '13 at 7:43p
posts2
users2
websitegolang.org

2 users in discussion

Russ Cox: 1 post Remyoudompheng: 1 post

People

Translate

site design / logo © 2022 Grokbase