Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl-Sensitive Sunglasses

Re^2: Perl is not Dynamically Parseable

by Jeffrey Kegler (Hermit)
on Oct 12, 2009 at 23:54 UTC ( #800821=note: print w/replies, xml ) Need Help??

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

I'd very much look forward to seeing a full write-up of this proof. I suspect that many will prefer it to any of mine. In fact, one of the people who prefer your proof might be me.

It is very common in math to publish new proofs of old results. In any field, the first statement of something is seldom either the clearest or the most elegant.

  • Comment on Re^2: Perl is not Dynamically Parseable

Replies are listed 'Best First'.
Re^3: Perl is not Dynamically Parseable
by ikegami (Pope) on Oct 13, 2009 at 00:47 UTC

    Let's find a program where the prototype is non-deterministic and affects context.

    BEGIN { *call_to_inspect = ( rand() < 0.5 ? sub ($) {} : sub (@) {} ); }

    You can detect some changes in the compile-time state of a prototype by its effect on context.

    BEGIN { *call_to_query = ( rand() < 0.5 ? sub ($) {} : sub (@) {} ); } sub inspector { print wantarray ? 1 : 0, "\n" } call_to_inspect(inspector());

    Let's observe:

    >perl 1 >perl 1 >perl 0 >perl 1

    Therefore, there exists a function call in a program for which two instance of the Perl parser have different prototypes for the named function.

    Therefore, there exists a program for which two instance of the Perl parser produce different output.

    Or for short, Perl cannot be parsed.

      The proof looks like it goes through. One reason mathematicians do multiple proofs (aside from the fact that subsequent ones tend to be better) is that they are rhetorical devices. Different proofs speak to different audiences. Allow me to comment on a trade-off made in this version.

      This proof uses Perl's rand builtin, while my efforts treat Perl as a Turing machine. The rand-based proof could be read as stating "Perl parsing is undecidable if you use rand, time or some other non-deterministic builtin".

      Similarly, you could read the Turing-machine-based proofs as saying "Perl parsing is undecidable if you use Turing-equivalent control constructs." If you allow no transfers of control at all, clearly the compile phase will terminate, and my proofs no longer go through.

      The different proof tactics give the two proofs different rhetorical effect. It's subjective, but subjective matters. A lot depends on whether you see Turing-equivalent control flow constructs or non-deterministic builtins as "core" features.

      One thing you might do, if you're interested, is a reduction of Perl parsing to some form of Goldbach's Conjecture. This would not be a proof of undecidability, unless and until Goldbach's Conjecture is found undecidable. Instead it would amount to proof that Perl parsing is equivalent to a really hard and currently unsolved problem.

        The compile phase not terminating is not a problem, and it doesn't show that Perl cannot be parsed.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://800821]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (15)
As of 2017-05-25 14:30 GMT
Find Nodes?
    Voting Booth?