After all, perl scripts are converted to machine code...

Not really. They're compiled to an intermediate format known as an optree. Perl runs programs by traversing this optree.

It is surprising that there is no reasonably satisfactory solution till now.

It's a surprisingly difficult problem. You'd need something like PyPy and Futamura projections to get close.

Why not have the possibility of compiling to optree and then "executing" the optree over and over again? A bit like java source to jar.

Have you considered not using Apache and mod_perl? I converted my personal website to lighttpd this week and I couldn't be happier. Now I am using FastCGI with perl and php scripts. Frameworks like Mojolicious and Dancer (and surely others) may benefit from using the built-in web servers and then using a reverse proxy to access them.

I'm not against a perl compiler per-se, but I don't think your current issue is with the lack of compiled perl code. You may want to also investigate PAR::Packer and Perl2exe from IndigoStar.

Because to write a compiler that can parse and compile all legal Perl source code, including all edge cases, is to solve the Halting Problem.

I'm not sure I understand why. Are you saying that a Perl interpreter is possible, but not a compiler? If so, why?

Yes, that's what I'm saying. I think the links I provided in my first post do a better job of explaining the challenge than I could. There is also this: Wikipedia article on Perl, "Implementation" section.

Your The OP's misunderstanding is that perl, the interpreter, compiles Perl (the language) to machine code. It's not nearly that simple. Perl's compilation phase allows for the execution of Perl code. Virtually every part of the language that is available at runtime is available at compiletime as well. Furthermore, Perl's runtime is able to invoke the compilation phase, so the full power of the Perl interpreter is available to the runtime. This blurred distinction makes C++'s most vexing parse look like a fly on a camel's back. And the fact that string eval is given full access to the symbol table, as well as current lexical scopes, makes it so that even perl, the interpreter, doesn't always know what's going to happen until it happens.

To pre-compile Perl, one needs to either solve the Halting Problem, or one needs to be satisfied with being able to compile only those parts of Perl that don't rise to that level of difficulty. This strategy is known as avoiding the halting problem. In other words, you need to create a compiler that compiles the subset of Perl that can be compiled. That's not quite Perl, though. It's along the lines of what Will_the_Chill has been working on; defining a subset of Perl that can be compiled, and energizing the community to work on a compiler does only that, while integrating as seamlessly as possible with code that cannot be pre-compiled.

This MJD talk doesn't directly address the issue of a Perl compiler, but discusses why a Perl-to-C translator would essentially amount to reimplementing Perl, which brings you back to square one.

I'm not saying that such projects are pointless. I'm saying that until the person defining the scope of the project understands the limitations, a lot of time will be wasted chasing a spec that is impossible to reach. That causes people to lose respect or interest in a project before it gets too far along, which is a shame. It's best to know what the limitations are, create a compiler that does everything possible within the confines of those limitations, and then start innovating to push the envelope outward. You never will reach 100% of Perl, but you might reach a very useful majority. Unfortunately, a useful majority is useless to you in practical terms if it is unable to deal with the modules your code requires to run, so you have to be very clear in documenting what cannot be done, and to get anyone to use it, you'll have to be proactive in also identifying what common modules can be used.

C++ actually sort of did the first part of that. There's old C++89 or whatever it was. It didn't have templates, and consequently lacked the capability of implementing most of what people refer to as the STL. Then someone figured out how to push the envelope a little by adding templates. The 1998 "standard" added features to the compiler that facilitated template metaprogramming. Language features that seemed impossible a few years earlier started to become possible (such as the STL, among other things). Over the years templates have become even more powerful. C++11 found additional areas where the envelope could be pushed outward by improving the compiler. But none of the problems solved by templates or C++11 attempted to solve the halting problem. They just found ways that hadn't been previously considered to do things that are extremely useful, though they still fall short of solving the halting problem. And look how long it's taken to get there... how many man-hours, etc. Yet C++ still isn't able to give full language semantics to the compiletime phase, nor full compiletime semantics to the runtime.

Parsing and compiling 100% of Perl rises to that level. Parsing and compiling a well chosen subset doesn't. But isn't as useful, and isn't full Perl. Finding ways to get closer is a big job, and with enough work progress can be made. But you're not going to parse and compile 100% of Perl.

Your The OP's question earlier was "what's the big deal." My post was to simply explain that it sort of is a big deal. We would all love for someone in some corner of the Computer Science world to solve the halting problem, because that solution would generalize to being able to solve all other equivalent problems (including, we suppose, parsing and compiling Perl). But Turing's proof has stood up for almost seventy years.

Update: Some additional interesting reading I found, which is loosely related: Perl contains the Lambda Calculus (MJD), and Wikipedia on Lambda Calculus # Anonymous Functions: "Compiled languages, such as C++, permit run-time selection (i.e., binding) of a variety of already-compiled functions, which is utilized in lieu of compiling additional machine-code instructions, which is what would be needed by compiled languages to achieve full-fledged run-time creation of new functions." Perl supports full run-time creation of new functions. Even C++11's "lambda functions" are, behind the scenes, templated classes with an overloaded () operator. There's no provision in that language for runtime creation and compilation of code that can be executed natively within the same runtime environment as the creator. I would love to have more than my limited understanding of the Lambda Calculus, and if I did, I could probably draw parallels between the Undecidability of Equivalence problem, and some of how Perl works. And I might be able to back up the assertion that due to Perl's sloppy (but useful) distinction between what constitutes runtime and compiletime, the reducibility of Perl code falls into the "all bets are off" category. ;)




Dave

OK, I'll bite. Please explain how a compiler can deal with this:

while (my $line = <>) {
  print eval $line;
}
[download]

-- FloydATC

Time flies when you don't know what you're doing

OK, I'll bite. Please explain how a compiler can deal with this:

By not dealing with it, see Perl 5 Optimizing Compiler, Part 9: RPerl.org & The Low-Magic Perl Commandments

I am sure RPerl is a significant improvement. My understanding / guess is that it works for almost all production use perl scripts - bad luck for a few esoteric ones. My questions: Why is there no buzz about this solution? Is it too good to be true? Is the RPerl development team not sufficiently large? Are there any factors preventing the widespread adoption of this differently conceptualised solution? Any attitude / "religious" / not-done-like-this-here biases? Or, it is not worthwhile to implement & too much of a hassle to explain why? RPerl seems to a better tool. Why is the world not beating a road to Will the Chill's door?

My understanding / guess is that it works for almost all production use perl scripts - bad luck for a few esoteric ones.

My understanding is pretty much the reverse - it works for a few tightly-constrained scripts but not for the majority of general-purpose code that I would use on a daily basis.

Why is there no buzz about this solution? Is it too good to be true?

See above. The constraints just now are too heavy for most users to get a benefit from it. That said, I think there is a buzz, just not a huge one. I've not attended one of Will's talks yet but (at least some of) those who have say they have been well received. It seems very likely that the more interest it generates, the more people will work with it and then on it and so the pace of development will pick up and more constraints will be lifted resulting in wider use - a spiral of win.

You might consider the similar low levels of adoption of Perl6* at present. There is a lot of buzz about that language too but I'm not yet convinced that it will break through. If I had plenty of free time to devote to either project it would be RPerl rather than Perl6* which would get the attention.

Other opinions are available :-)

* 2019 note: now called Raku

Also, “a Perl compiler” probably wouldn’t actually “speed it up” nearly as much as you might think.   Perl, as a language system, is actually very small in size ... and very, very fast.   (There is voodoo in those perlguts.)   Like every interpreted language that is designed to be interpreted, the source-code is compiled in a split-second, not to executable machine code, but to an optree that is then traversed by the runtime system.   A single optree node can pack a tremendous punch, or it can do very little, but it is always small.   The overhead of navigating through that structure and calling the proper handlers is inconsequential.   The key advantage of the optree is that it expresses the purpose of the program, the actions that are to be taken, and that it does it all indirectly.   The code that implements each opcode is already ferociously optimized:   you’ve got access to some top-notch code without so much as lifting a finger.

If your program is “slow,” then it is your program that is slow, and compiling that program into an assemblage of native instructions would not make it faster.   Instead, profile your program to find the hot-spots ... do not “guess” where they are, and do expect to be surprised.   80% of the program’s runtime is generally spent in 20% of the code.   Correctly and objectively identifying those troubled areas, and creating highly-targeted improvements based on actual measures, will yield dramatic performance improvement.