David L. Nicol writes:
: Steve Fink wrote (and I edited slightly):
:
: > <groan> I can't figure out why so many people misinterpret my RFC12
: > as requiring a solution to the halting problem.
:
: a large class of incompletely expressed
: suggestions appear to get grouped into
:
: "This requires solving the halting problem!"
:
: without providing further explanation.
Well, in my case, I wasn't actually meaning it strictly. Sorry for the
imprecision--it's hard to squeeze everything into a talk. To me the
saying is just shorthand for "potentially sufficiently computationally
expensive that I don't want to worry about it for the default case".
In other words, I was lumping polynomial in with exponential, and RFC12
feels polynomial to me. And it's not that I'm against the availability
of polynomial algorithms in the parser, or the use of polynomial
algorithms in general--I just think the default compile-and-run parser
should avoid them. I'm not even sure that O(n * log(n)) is practical
in the parser unless it's something essential. Warnings don't fall
into the essential category, in my estimation.
On the other hand, if, after we cover the essentials, the warning turns
out to be O(n) in additional cost, we could certainly look at it again.
But if that's the case, it will be easy to add without having designed
it in first, especially if we've designed in the proper hooks for the
optimizers.
Note that I'm discussing RFC12 here. Taint checking at compile time
provides a different set of issues.
Larry
