Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic
 
PerlMonks  

Re^3: Perl is not Dynamically Parseable

by ikegami (Pope)
on Oct 13, 2009 at 00:54 UTC ( #800830=note: print w/ replies, xml ) Need Help??


in reply to Re^2: Perl is not Dynamically Parseable
in thread Perl is not Dynamically Parseable

It is more like two possible syntactic interpretations/parses of the same piece of code,

And what produces those two possible parses? Two parser instances. We're saying the same thing.

Saying "two instances of the parser" produce different things (on the same given code, presumably) makes it sound simply like the parser is non-deterministic or randomized.

Good.


Comment on Re^3: Perl is not Dynamically Parseable
Re^4: Perl is not Dynamically Parseable
by blokhead (Monsignor) on Oct 13, 2009 at 18:15 UTC
    I don't know what the halting problem has to do with non-deterministic or randomized programs. The perl parser is deterministic, and it does not toss random coins. You can certainly insert randomness into a BEGIN block, but that's not what's going on here and it doesn't mean that parsing itself is randomized. Jeffrey's examples & undecidability proofs all involve deterministic BEGIN phases. If you run the parser a billion times on a deterministic program, you will get the same result every time. Different instances of the parser do not give different parses. The only way to get different parses is by having different behavior within the BEGIN block.

    blokhead

      The perl parser is deterministic,

      Parsing is the activity of assigning meaning to code. Since it's impossible to predict the meaning Perl will assign to code in some circumstances, the parser is non-determinisitc.

        it's impossible to predict the meaning Perl will assign to code in some circumstances
        That's what I thought you must have meant. I guess we have different working definitions of what "deterministic" means.

        In this case, one could even argue that it's not really a matter of determining what meaning Perl assigns to some code, but a matter of determining whether Perl will get around to assigning meaning to some code.

        blokhead

      Something I missed:

      Different instances of the parser do not give different parses.

      They do for some program. Did you (incorrectly) think I said it would happen for all programs? I said that once one finds a program where this happens, one can prove the non-parsability of Perl.

        Did you (incorrectly) think I said it would happen for all programs?
        Nope.
        I said that once one finds a program where this happens, one can prove the non-parsability of Perl.
        If this example (from this previous node of yours) proves that perl is unparseable (because it sometimes defines foo, it sometimes doesn't):
        BEGIN { eval "sub foo {}" if rand() < 0.5; } foo();
        then this next example proves that the halting problem is undecidable (because sometimes it halts, sometimes it doesn't):
        if (rand() < 0.5) { 1 while 1; }
        But neither is a proof of the undecidability of anything satisfying. They assume an interpretation/model of programs that employ randomness (and by extension, any external calls) which completely trivializes the halting problem into a meaningless statement. I think this is my main objection with your examples.

        Turing machines are deterministic, so if you want to model things like random choices and externally-obtained data, you model them (without loss of generality) as being provided as input on separate tapes. Indeed, this is exactly what is done in the theory of computation. For this reason, I have a gut reaction against random choices and external data being used to "prove undecidability." Those issues are red herrings and don't speak to undecidability in any meaningful way. From the perspective of undecidability, they should be considered as simply additional, different kinds of input to a program.

        So in the first example above, you can confidently say that whenever the random tape contains such-and-such, the program is syntactic, and otherwise it is not. In the second example, you can confidently say that if the random tape contains such-and-such, then the program halts, and otherwise it does not. You can efficiently solve the parseability problem and the halting problem for classes of programs of this simple form, for the way of modeling a program's random choices that doesn't already trivialize the halting problem. So they are not satisfying demonstrations of undecidability.

        On the other hand, it is impossible to decide the parseability problem (however you want to define it) for the class of programs of the following form:

        BEGIN { my $x = "... arbitrary perl code ..."; eval "sub foo {}" if eval $x; } foo();
        And this does not rely on things like external system calls, or random choices, since the halting problem is still quite meaningful when those things are not used.

        blokhead

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://800830]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (7)
As of 2014-07-31 22:44 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:









    Results (254 votes), past polls