Beefy Boxes and Bandwidth Generously Provided by pair Networks
Don't ask to ask, just ask
 
PerlMonks  

Re: Perl Cannot Be Parsed: A Formal Proof

by Anonymous Monk
on Aug 13, 2009 at 22:26 UTC ( #788460=note: print w/ replies, xml ) Need Help??


in reply to Perl Cannot Be Parsed: A Formal Proof

I'm confused by this proof and I don't buy it, especially since the definitions, including that of "parsing," are too imprecise to warrant some reduction proof. You also don't need reduction to show the existence of an example, which is what you're essentially trying to do. You seem to be making the claim that when you have code

BEGIN { x(); sub foo { } }

then foo() will be declared only when x() terminates.

But that's like writing this Java code

for(;;) { } int x;

and asking whether "x" will ever be declared, which says absolutely nothing about how this program is parsed (and it's parsed fine).

Cheers.


Comment on Re: Perl Cannot Be Parsed: A Formal Proof
Select or Download Code
Re^2: Perl Cannot Be Parsed: A Formal Proof
by chromatic (Archbishop) on Aug 14, 2009 at 02:31 UTC

    You seem to be making the claim that when you have code

    BEGIN { x(); sub foo { } }

    then foo() will be declared only when x() terminates.

    That particular example has a flaw, but it's easy to demonstrate that the argument holds:

    use Modern::Perl; sub x { say "In x!" } BEGIN { x() } sub foo!bar { say 'In foo!bar!' } BEGIN { foo!bar() }

    For extra fun, run it through B::Deparse.

Re^2: Perl Cannot Be Parsed: A Formal Proof
by Jeffrey Kegler (Friar) on Aug 15, 2009 at 01:53 UTC

    In a series of three articles in The Perl Review, now available online, I laid this proof out much more carefully, in three different versions. The most bullet-proof version derives the result directly from Rice's Theorem.

    You are right that the proof would not go through if the only way of establishing a prototype for a Perl function was via a function definition. As I said in Perl Review (4.3, p. 28):

    I must show that I can use Turing-complete Perl code to determine the prototype of the dunno subroutine at compile time. A function definition wonít work.

    Summarizing from that article, there are at least two ways that the prototype of a subroutine can be established using Turing-complete Perl code. One is with symbol table manipulation, for example:

    BEGIN { *dunno = sub () { 3 } }
    A second way is to put the function definition into a string which is eval'd in a BEGIN block. I believe clever monks will be able to think of others.

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (9)
As of 2014-09-02 22:57 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite cookbook is:










    Results (32 votes), past polls