Beefy Boxes and Bandwidth Generously Provided by pair Networks
Your skill will accomplish
what the force of many cannot

Re^4: Unparseability is A Good Thing

by ikegami (Patriarch)
on Aug 27, 2009 at 21:45 UTC ( #791755=note: print w/replies, xml ) Need Help??

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

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.

Replies are listed 'Best First'.
Re^5: Unparseability is A Good Thing
by Zen (Deacon) on Aug 28, 2009 at 13:31 UTC
    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.

        This is true of any language, though. Consider a function pointer in C. You can prototype all day long, but what if your prototype leads to a function pointer that gets borked partway through and you get a dump? What about NullPointerException in Java? This is all halting problem material, too. This isn't a perl issue. Part of the turing machine in models of computation is the tape and the read head; nowhere does it say that the Turing machine is omniscient of the entire input stream.

        Am I the only one unimpressed?

        As for reference material, I often wrongly assume everyone went through comp sci. I did undergrad and grad modcomp from two different- but now out of print- textbooks. There are different books now, such as the one by Michael Sipser (Introduction to the Theory of Computation) that should cover computability theory, turing machines, and automata.

        If it matters any, I remember /facepalm'ing many times through both of those courses at how obvious and unimpressive it was, just formalizations and proofs of what you already (probably) know.

Log In?

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

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (3)
As of 2022-01-23 02:23 GMT
Find Nodes?
    Voting Booth?
    In 2022, my preferred method to securely store passwords is:

    Results (63 votes). Check out past polls.