develooper Front page | perl.perl6.meta | Postings from October 2000

Re: compile-time taint checking and the halting problem

Thread Previous | Thread Next
From:
Steve Fink
Date:
October 23, 2000 12:38
Subject:
Re: compile-time taint checking and the halting problem
Message ID:
39F493A2.5CD866DE@digital-integrity.com
Larry Wall wrote:
> 
> 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

Um.... (rereading it again) er... (and yet again)... so you're saying
you know how to solve the halting problem in exponential time? Cool!
Hang on a sec -- I'm going to head over to the other side of this
Moebius strip and shoot my grandpa.

Perhaps you might want to find another shorthand for "takes a long
time"? ;-) Solving the halting problem is not computationally expensive.
No program that does it takes longer than 42 femtoseconds per nybble of
compiler input (43 if it needs to translate from pig latin).

> 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.

Ah, yes. I understand the objection then, and agree. I'm not so sure
about ignoring everything that's not default, though. gcc would be a
much worse tool without the optional -Wall and -g flags. But certainly
that's past the point where language design ends and environment begins.

I'm not sure that measuring the hit in O() notation is meaningful here,
either. If it takes nlog(n) time, that's a good hint that it'll slow
things down too much to have it on by default. But that n is slippery --
it's a lot smaller than the fundamental n of the number of bytes the
tokenizer sees. Even having O(n) additional cost doesn't say much -- if
it runs twice as slowly, we still definitely don't want it. If it adds
10%, then maybe. Big-O notation is a good description of how a problem
grows, but a bad description of user annoyance.

> 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.

Yes, RFC12 changes nothing fundamental in the language, so can be
ignored pretty much completely for now. But I wanted to point it out as
an advantage of not going too crazy with perl's semantics: if a computer
can read your code and extract some meaning without having to actually
run it, then that computer will be able to catch more of your mistakes
earlier. The usual perl trend is to make things as easy as possible for
the programmer and screw the computer, which is a large part of why I
like perl so much. But there's something to be said for making things
easier for the computer, especially since something that's hard for the
computer is often the same thing that screws the users when they start
programming big stuff.

Thread Previous | Thread Next


nntp.perl.org: Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About