Lambda the Ultimate

Assuming you are being serious, the act of running a program only determines whether or not a given set of inputs may halt. And as the running program itself might not halt, thus failing to yield (in finite time) the answer to the question "does this halt"?, you might not learn anything.

Should we call Perl an example of "dynamic syntax"?

No, we shouldn't, because then somebody will think "dynamic means good, right?", and start imitating Perl syntax.

The static structure of some Perl 5 programs cannot be determined.

If the behavior of the Exporter module is well known (which it is), and the export lists can be proven to be static, then the effect on the symbol table of the consuming module can be statically determined, and hence the remaining source code can be parsed statically.

This proof applies to the fact that you *can* put nondeterministic behavior in code that runs at compile time and therefore affects parsing, but most code doesn't actually do that.

That aside, statically parsing Perl is still very difficult ;-)

However, if you want to write a refactoring tool, you really want it to work for all legal code—otherwise, people just aren't going to trust it.

At best, you could refuse to make any changes when the code isn't statically parseable.

On a side note: Perl supports code that overrides the parser for the rest of the file, right? Does that get used much, for EDSLs and what-not? (I used Perl heavily in 2000-2001, but very little since then.) That would throw static parsing right out the window.

The "dynamic syntax" cannot be determined for the same reason. The halting problem cannot be magically solved by invoking the Perl interpreter.

Otherwise I'm a bit confused that no one here on LtU argues against the claim of the formality of the proof since the parsing operation is nowhere defined. Hand waving is o.k. when things get clarified in the comments part but otherwise...

BTW not too long ago I responded to the article in a blog posting.

Does a given Perl program even have a consistent "parse" during a single run? Or can the same source text be parsed different ways at different times? I don't know enough Perl to answer, but my guess from the nature of the comments here that the latter is the case. If so, it makes me wonder what is supposed to have been proven here.

There are only a few means by which you can change the way Perl 5 will parse a line of code, and there are only a few types of syntactic constructs where the parse can change.

The only way a given Perl 5 program could parse differently between runs is if executing the compile-time declaration of the whatever sub from the example in the linked proof depended on indeterminate input.

No one writing serious Perl 5 code would write such code -- given a random number or user input or the last digit of the position of the moon at the time of launching this program, potentially declare a whatever sub with zero arity.

My point is basically that once you formalize what the parser does you can see its limitations.

An ambiguous parse creates at least two trees T1, T2 and a context sensitive analysis might be applied to decide which tree is used ( in C one tracks typedefs and builds a symbol table ). In Perl there are situations where this decision making process always fails no matter when it gets processed. But this doesn't have to bother Perls parser. The parser can create a third node T3(T1, T2) which represents a switch executed at runtime. Instead of reducing (T1, T2) to either T1 or T2 the final parse tree is a little expanded and contains T1 and T2.

This might not be appropriate for every language and has the disadvantage that the parse tree grows exponentially ( in theory ) and not linearly with the number of token but it works in Perls case and keeps the parser simpler as one might expect initially.

Although it is not made abundantly clear, presumably the decision problem here is the membership problem for Perl programs.

Unfortunately I too have very little idea about Perl, but I think the author is arguing that the syntax of a given Perl program depends on the execution of arbitrary Perl and, importantly, the execution of the Perl sometimes results in a syntactic construction that is a member of the class of Perl programs and sometimes results in a construction that is not. Hence, the membership problem for the class of Perl programs is undecidable.

Having some kind of additional construction in the parse tree, as suggested elsewhere in this thread, would be useful for static analysis, but it would not rescue the situation. It is impossible, if we believe this proof, to decide the validity of (the syntax of) a Perl program.

Yes, that would make more sense to me. I don't know if that's what the author has in mind, though, considering statements like this:

To prove Kennedy's Lemma, we assume that we can parse Perl. In particular this means we can take the following devilish snippet of code, concocted by Randal Schwartz, and determine the correct parse for it:...

Lisp is famous for simple syntax, but it's useful (in part) because of its flexible syntax. If that means one or more compile phases can't be proven to terminate, so be it.

The "Turing Complete" nature of templates in C++ doesn't mean that the C++ language can't be statically parsed.

and have more than a few ambiguities-resolved-by-fiat; it brackets well. One of the key "difficulties" of C++ (and C as well) is that correct parse for certain constructs depends on whether a given symbol corresponds to an in-scope typename or not. This complicates parsing, as the parser has to consult the symbol table while generating a parse tree.

However, the set of valid symbols and their kinds, at a given point in a C++ program is always statically known; as the language doesn't support things like dynamic scoping, mutable reflection, etc, which might make the symbol table dependent on the program's execution.

Macros may be another issue together; though the behavior of a C/C++ macro doesn't depend on program input.

There's definitely a parallel here. Although C++ can definitely be parsed, parsing is only a small piece of the puzzle from a tooling perspective - refactoring, browsing, complexity analysis. To enable those things, you need to finish the compilation process, where we finally figure out the definition of every type in the program and the static type of every variable. And that is undecidable in C++, because the means by which types are assembled during compilation is itself a Turing complete dynamically-typed interpreted language.

C's typedef ambiguity is not the same. If your parser has access to a source file and all the appropriate headers then it can solve the typedef ambiguity without executing the C program. The analysis may be more complex than a simple LR(k) parse or whatever, but it's still doable with just statically available information.

The original article is about an ambiguity in Perl where the syntactic class of code following a "/" depends on the value dynamically computed for the expression on the left. In his example some following code can be a comment under one range of values and be a non-comment given another set of values. In short you must run a Perl program to "parse" it at all. Unlike the case with C, no amount of static analysis can resolve this.

I'm not an expert on Forth, but AFAIK it's very easily parsed. Its just that the parse tree can't carry very much information beyond distinguishing between comments, various literal types, and identifiers.

And even running the program just gives you one possible syntax tree. If the program does I/O, then it can even "parse" differently when run a second time.

is to write perl scripts which execute their own output. :)

Aw, heck. If we can tolerate the fun of parsing perl, lets just dispense with the restricted levels Chomsky hierarchy altogether and design programming languages with Type 0 grammars.

I didn't say it was the same, I said there are similarities, and the similarity I was pointing out is that the parsing is much more complicated than it should have been. I'm well aware of the particular behavior in Perl, and that it's different (much worse), but both are examples of the language semantics leaking into the syntax and making parsing harder.

Secondly, forth is very easily parsed into a series of words, but that is just a list of non whitespace strings, it wouldn't tell you much about what the forth program does. Anything more involves execution of immediate words such as the ; word which terminates compilation of another word. In that sense it's just as bad as Perl, except that most Perl code found in the real world doesn't actually exhibit this behavior whereas in Forth such practices are pretty standard.

The parsing does not depend on the value of the expression; the parsing is fixed at compile time. The parsing of this expression is always unambiguous when Perl 5 executes the parse tree.

The parsing does depend on any compile-time declarations which change the arity of the whatever sub, but only the parser cares about those. By run time, that information is no longer relevant in this case. Thus the behavior of this code has nothing to do with the value to which the expression whatever evaluates; it only depends on the syntactic category into which the parser places it.

In the face of non-deterministic branching which could designate the arity of this sub one way or another, you cannot completely predict how it will parse without running code -- but that's the difficulty here.

In other words, at runtime, a subroutine in Perl is passed not a definite set of arguments, but the remainder of the program text, to do with as it pleases.

That is not how Perl works.

It's possible to change the arity of functions as Perl 5 parses a program. That will change how the parser handles bareword functions where it might have to guess at the expected arity. (Even the word "guess" is a misnomer, as the combination of greedy variable-length parameter lists and operator precedence produces a deterministic heuristic.)

Changing the arity of a function for the parse affects only code the parser has yet to parse. It doesn't change previously parsed code.

The parser produces a parse tree and discards, as you say, the remainder of the program text. There is no reparsing to resolve an ambiguous parse at runtime; the parser resolves any ambiguity during the initial compilation phase.

See On Parsing Perl 5 for more.

Ah, that's much clearer. In essence, you can tweak the parsing rules while they are being used to parse your code, just as in C++ you can meddle with type definitions while the type definitions are being figured out.

(It's not that I like the language. I just use it.)

Using a branching strategy to enable static parsing of Perl looks like a promising approach.

The main problem with parsing Perl ... one of the main problems with parsing Perl ... one of the very many problems with parsing Perl ... is the meta-parsing concept of "contexts." (For those that don't know Perl, an expression can be evaluated in scalar, list, or -- as in this case -- void context.) There is no syntactic support for disambiguating between contexts. Indeed, the quoted fragment demonstrates that Perl is quite capable of going out of its way to remove syntactic disambiguation: either an enforceable prototype, or the requirement for a pair of parentheses, would make it obvious that "whatever" is nullary or not.

Given Larry Wall's predilection for throwing infix operators at a problem, I'm surprised that he hasn't considered smileys as a solution to this one. Scalar context could be considered default. :( might represent void context for the following closure. ;) might represent list context for the following closure. There are probably other contexts out there I'm not aware of: I'm sure a blessed context would come in handy.

Of course, the big problem with parsing Perl is that there is absolutely no reference implementation whatsoever. I'm being unfair here: at any given time, there's a reference implementation for 5.8.1.21, or whatever ... but woe betide anyone who writes a nice, clean, static parser -- now with extra gleaming branching! -- for that.

It's never gonna work for 5.8.1.22.

Personally, the entire Perl language makes me cringe. But the breadth and scope of CPAN is amazing, and Perl 6 looks like it will be much cleaner and a substantial improvement over Perl 5.

I find that syntax itself does not carry much cognitive load once you are accustomed to it; typically I can get accustomed to most any syntax within a week. My experience has been that semantics of the language typically imposes the ongoing cognitive burden, one that becomes lighter more gradually.

Syntax is not unimportant, but you should read the first page or two of the first chapter of PLAI.

I suspect that many people here are not big fans of Perl, although I'm also sure there are more than a few Perl lovers around LtU. :-)