Of course, to "really" solve this problem you'd have to recognize "mutually unused" arguments: foo(a,b) calls foo(b,a) and doesn't otherwise use the arguments. But foo(x,a) which uses x and calls foo(a,x) uses both. Not difficult to solve, and a few seconds' thought puts it in O(m*n) with m recursive calls and n parameters... but probably not worth the trouble.
Sorry, how is this O(m*n)?
Unused Arguments Aren't a Problem When Recursing Right?
11–14 of 14 posts
Hmmm... represent the parameters as nodes in a directed graph. For each of m recursive call sites, process each of n parameters and add edges from formal parameter name to passed argument (i.e., if we have signature foo(a,b,c) and recursive call foo(c,b,c), add edge a->c; self-edges are unimportant). This step is O(mn). Then, assuming we already know what parameters are used outside of function calls, flood-fill the graph from those nodes; this is O(n). O(mn+n)=O(m*n).
Re: Unused Arguments Aren't a Problem When Recursing Right?
#12Just a gut feeling. Properly solving this might require solving the halting problem: you don't know the variable is unused until you actually evaluate the code. Otherwise you can only aim for detecting very trivial cases.
Re: Unused Arguments Aren't a Problem When Recursing Right?
#13Earlier quoted context omitted.
Sorry, how is this O(m*n)?
Hmmm... represent the parameters as nodes in a directed graph. For each of m recursive call sites, process each of n parameters and add edges from formal parameter name to passed argument (i.e., if we have signature foo(a,b,c) and recursive call foo(c,b,c), add edge a->c; self-edges are unimportant). This step is O(m n). Then, assuming we already know what parameters are used outside of function calls, flood-fill the…
> "Then, assuming we already know what parameters are used outside of function calls"
This is something that needs to be done, I guess my confusion was that you already have this information and that should be sufficient to finding the unused parametres.
Re: Unused Arguments Aren't a Problem When Recursing Right?
#14Just a gut feeling. Properly solving this might require solving the halting problem: you don't know the variable is unused until you actually evaluate the code. Otherwise you can only aim for detecting very trivial cases.
Yes. See my comment below. The bug is trivially avoided by adhering to a coding standard that actually makes the code better. See my other comment below.