Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change
 
PerlMonks  

Re: Unparseability is A Good Thing

by zby (Vicar)
on Aug 23, 2009 at 13:30 UTC ( #790665=note: print w/ replies, xml ) Need Help??


in reply to Unparseability is A Good Thing

Hmm - but isn't there any way to have both "the ability to use the full power of the language at parse time" and still be parseable? If we removed just subroutine prototypes rom the language the proof would not hold any more. So the question is is there a more general proof that does not rely on prototypes?


Comment on Re: Unparseability is A Good Thing
Re^2: Unparseability is A Good Thing
by blokhead (Monsignor) on Aug 23, 2009 at 15:06 UTC
    The entire language is available at compile time (via BEGIN blocks). I think that this fact makes any distinction between "parsing perl" and "executing perl" a little artificial & disingenuous in the context of this undecidability proof.

    Anyway, since the entire language is available in BEGIN blocks, the proof does not crucially rely on subroutine prototypes. They just provide a convenient "parsing property" (clearly, determining the prototype of a sub is something that should result from "parsing") in which to effect the result. Any aspect of the language that you want to call a "parsing property" can be used. One that comes to mind is whether a loaded module returns a true value or not (and therefore whether the "parse" succeeds) -- this is something that happens during BEGIN phase.

    blokhead

Re^2: Unparseability is A Good Thing
by ikegami (Pope) on Aug 23, 2009 at 15:46 UTC

    If we removed just subroutine prototypes rom the language the proof would not hold any more. So the question is is there a more general proof that does not rely on prototypes?

    Yes:

    BEGIN { eval "sub foo {}" if rand() < 0.5; } foo 'x';
    >perl -c test.pl test.pl syntax OK >perl -c test.pl String found where operator expected at test.pl line 5, near "foo 'x'" (Do you need to predeclare foo?) syntax error at test.pl line 5, near "foo 'x'" test.pl had compilation errors.

    Execution is required to decide whether foo is a subroutine call or a bareword.

Re^2: Unparseability is A Good Thing
by ikegami (Pope) on Aug 23, 2009 at 15:53 UTC
    Yet another proof:
    BEGIN { my ($add_ts) = @ARGV; eval 'use subs qw( die )' if $add_ts; } sub die { my $ts = '[' . localtime() . '] '; my $msg = join '', @_; $msg =~ s/^/$ts/mg; CORE::die($msg); } die("foo\n");
    >perl test.pl 1 [Sun Aug 23 11:52:55 2009] foo >perl test.pl 0 foo

    Execution is required to decide whether die is a subroutine call or an operator.

      I don't agree with this one. An interpreted language can be parsed, by definition. To say something cannot be 'parsed' is to say the program itself is non-deterministic in its syntax (not its outcome).

      If I remember where this bandwagon came from, it was someone's project who realized the project was too hard to write perl to run perl. It was not proven that it cannot be done, however often touted.

        To say something cannot be 'parsed'

        We're actually saying "It cannot be parsed without executing arbitrary Perl code".

        Are you saying that's not the case? I have no idea what your first paragraph means.

        I did some studying on non-determinism.

        An example of a non-deterministic algorithm is mergesort.

        use sort '_mergesort'; my @sorted = sort { substr($a, 0, 1) cmp substr($b, 0, 1) } qw( foo bar baz );

        It is guarantees that the results will the sorted, but the relative ordering of baz and bar is not specified. Therefore, mergesort is non-deterministic.


        Let's see if we can replicate the same situation with the parser.

        The goals of Perl's parser include the production of functions.

        package Mod; BEGIN { my ($sub) = map "sub { $_ }", join ' ', map "$_();", sort { substr($a, 0, 1) cmp substr($b, 0, 1) } qw( foo bar baz ); } sub foo { print "$foo\n" }; sub bar { print "$bar\n" }; sub baz { print "$baz\n" }; 1;

        The parser produces a function that calls foo(), bar() and baz(), but the order in which the calls are organized is not specified. Therefore, the parser is non-deterministic.


        I don't know what that means wrt Perl's parsability, since I don't know I don't know how that's defined.

        I agree with you that the definition of "parsing" is not well-defined in the context of this thread. As I have mentioned elsewhere in the thread, in Perl the line between "parsing" and "execution" is fuzzy and in my opinion artificial. The distinction is influenced from the way other, more conventional programming languages are executed, which doesn't apply well to Perl.

        The OP has convincingly proving that it is undecidable to determine the prototype of a given sub in a given piece of code. The choice of problem is because (now this is an appeal to intuition, not a formal statement) however you define "parsing", determining the prototype of a sub is something that by all sensibilities should result from "parsing". (Update: the prototype of a sub can also be made to affect whether a "/" is interpreted by the compiler as a division operator or the start of a regex match). Elsewhere I listed the example of determining whether a module loads successfully or not (i.e., whether the module returns a true value) as another thing you might imagine as being an outcome of "parsing".

        So I can see where the OP is coming from, but of course it is a bit moot if you reject the artificial distinction between parsing and execution in a language like Perl, which allows arbitrary execution to be freely mixed with "parsing" phases. When you rephrase it more realistically as (for instance) "the BEGIN phase of Perl is Turing-complete", the whole exercise is trivial and loses much of its shock value.

        blokhead

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (6)
As of 2014-08-23 21:00 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The best computer themed movie is:











    Results (178 votes), past polls