Stories
Slash Boxes
Comments
NOTE: use Perl; is on undef hiatus. You can read content, but you can't post it. More info will be forthcoming forthcomingly.

All the Perl that's Practical to Extract and Report

use Perl Log In

Log In

[ Create a new account ]

Ovid (2709)

Ovid
  (email not shown publicly)
http://publius-ovidius.livejournal.com/
AOL IM: ovidperl (Add Buddy, Send Message)

Stuff with the Perl Foundation. A couple of patches in the Perl core. A few CPAN modules. That about sums it up.

Journal of Ovid (2709)

Tuesday February 14, 2006
02:45 PM

Halting problem in Perl

[ #28682 ]

Microsoft has a program called Terminator that basically tries to solve the halting problem. They claim it's helped them root out some bugs in their device drivers. Of course, we know the halting problem is unsolveable, but we also know that Microsoft engineers aren't stupid. So what are they doing? Well, some types of halting problems can be detected and highlighted and even if you don't find all bugs, even automatically finding some bugs is better than finding none.

Though they'll be releasing papers explaining this, I'm not sure how applicable it will be in Perl. Here's a typical example in C:

float x = 0.1;

while (x != 1.1) {
    x = x + 0.1;
    printf("x = %f\n", x);
}

If you translated that to Perl, would it be an infinite loop? There's actually no way to tell just by looking directly at the code:

my $x = 0.1;

while ($x != 1.1) {
    $x += .1;
    print "x = $x\n";
}

Well, that certainly looks like an infinite loop. Why might it not be? Because the following might not be an infinite loop:

print $foo while 1;

We're not even talking source filters here.

#!/usr/bin/perl -l

use strict;
use warnings;

{
    package Arnie;
    use overload '""' => \&to_string;

    sub new { bless {}, shift }

    my $x = 1;
    sub to_string {
        die if 5 == $x;
        return $x++;
    }
}

my $sarah = Arnie->new;
print $sarah while 1;

I suspect this is one of many types of problems which would make such an approach difficult to use for Perl.

The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
 Full
 Abbreviated
 Hidden
More | Login | Reply
Loading... please wait.
  • Let's ignore source filters, because presumably any proof to see if a program halts will necessarily happen on the post-filtered source. (This is regardless of whether you're talking about C+cpp, Lisp + Macros or Perl + Source Filters.) I'm not familiar with any of the formal theories here, but in your (somewhat contrived) example, it should be reasonably easy to tell that the second Perl program terminates. The hard part is when your termination conditions are derived from side effects, like environment
    • This seems similar to the arguments for static typing -- it lets you build a better IDE because you can reason about the code (eg: what methods does this object have?) In a dynamic language like Perl, that's much, much harder. But it does mean that interfaces in Perl tend towards being simpler and not requiring an IDE, unlike Java.

      -Dom

  • I think you're claiming that terminator wouldn't be of use in perl programming because of some obscure edge cases.

    In production code where I'd want to use something like this I work to minimise such edge cases (which simplifies maintainence and debugging), and would rather have to look through false alarms and check them than not have any help with a halting bug or infinite loop.
    --

    @JAPH = qw(Hacker Perl Another Just);
    print reverse @JAPH;