Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number

Re^3: Unparseability is A Good Thing

by Zen (Deacon)
on Aug 26, 2009 at 19:51 UTC ( #791429=note: print w/replies, xml ) Need Help??

in reply to Re^2: Unparseability is A Good Thing
in thread Unparseability is A Good Thing

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.

Replies are listed 'Best First'.
Re^4: Unparseability is A Good Thing
by blokhead (Monsignor) on Aug 28, 2009 at 14:01 UTC
    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.


Re^4: Unparseability is A Good Thing
by ikegami (Pope) on Aug 27, 2009 at 21:45 UTC

    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.

      You have pasted an algorithm that is flexible in the final result set. Perl never has any question about ordering of what to do next here. Any wiggle room for this program would be in the flexibility of the algorithm, but when it runs it runs as a DFA. Please keep reading about non-determinism. You will come across the fact that every NFA has an equivalent DFA. It's just how it is. The fact of machines is that they aren't random- ever- and there is zero non-determinism at any given time.

      I thought you were saying perl was not parsable. Now you do not know how to define it. By definition, it can be parsed. It's just a lot of work.

      The whole bit about the halting problem is this. You cannot write an algorithm to understand a program's output for all possible input without running it. Parsability involves being able to read perl code; I do not see how this person's project has spiraled into declarations that it cannot be parsed. What they should say is, you cannot be a fortune teller of the output of such a program, and we all know that. Any language has that feature. It is neither mystical, magical, nor special to perl, and I believe this statement reinforces the commonly held belief that perl is hard to read.

        Parsability involves being able to read perl code;

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

        Even if you don't buy the conclusion, it's the premise that's interesting, and the problem faced by those who recently posted on p5p (if that's the project to which you were referring).

        I'll have to get back to you on the first paragraph. The 5 minutes I have aren't enough

        Please keep reading about non-determinism.

        Any suggested reference?

        I thought you were saying perl was not parsable.

        I never said that. I know that Perl cannot be parsed without executing arbitrary Perl code, but I never even said that I believed that. I just answered your questions.

Re^4: Unparseability is A Good Thing
by ikegami (Pope) on Aug 26, 2009 at 22:18 UTC

    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.

      My paragraph addresses unparsability. I'm guessing you agree in some way, as you are now qualifying the statement. I'd need you to expand on "executing arbitrary Perl code" to answer whether or not it applies to what I wrote.

        I'm guessing you agree in some way,

        Hold on. Not understanding something does not imply agreement.

        All I did was to state the problem which was of interest to us.

        I'd need you to expand on "executing arbitrary Perl code"

        I'm not sure what you're looking for, so I hope the following helps:

        To determine the meaning of a token, the parser needs to be able to execute any Perl program, including shelling out to execute any binary. The algorithms executed may be non-deterministic.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://791429]
[Corion]: Is anybody aware of what makes Android Oreo better than Android Nougat? I'm not sure if the architectural changes (etc) are there already that make upgrading an Oreo-kernel phone to a newer Android userland (Lineage OS) version feasible
[Corion]: Yeah, CryTek got blindsided (or whatever) by Unity and Unreal Engine being zero cost, and the CryTek documentation being bad/nonexistent I think
[Corion]: "zero monetary cost", because of course, it's gratis only if your time has no value :)
[marto]: I used to keep up to date with my android ROMs, updating to the nightly every other day
[marto]: in my experience the jump in major releases has been painless, and performed better
[marto]: Corion if your device has an official Oreo ROM I'd do a nandroid backup and give it a shot

How do I use this? | Other CB clients
Other Users?
Others musing on the Monastery: (4)
As of 2017-12-14 10:41 GMT
Find Nodes?
    Voting Booth?
    What programming language do you hate the most?

    Results (389 votes). Check out past polls.