in reply to Detecting Recursion

This is fairly simple. Represent your program as a graph. Each function is a node in the graph, and there's a directed edge from one node to another if the sub calls the other sub. Given this graph, calculate the transitive closure, and see if the transitive closure has a loop. The program is recursion free, if and only if the transitive closure doesn't have a loop, which is represented as a node having a link to itself.

Luckely, there's a module on CPAN that can help: 

#!/usr/bin/perl

use strict;
use warnings;

use Algorithm::Graphs::TransitiveClosure qw /floyd_warshall/;

my $g;

while (<DATA>) {
    my ($from, $to) = split;
    $g -> {$from} -> {$to} = 1;
}

floyd_warshall $g;

while (my ($key, $value) = each %$g) {
    print "Recursion for function '$key'\n" if exists $g -> {$key} {$k
+ey};
}


__DATA__
aaa bbb
bbb ccc
bbb ddd
ccc ddd
ddd aaa
ddd eee

[download]

Abigail

Replies are listed 'Best First'.
Re: Re: Detecting Recursion
by Anonymous Monk on Nov 26, 2002 at 23:38 UTC
    Sadly, that's not good enough as a general approach. It only works on the static cases, not on ones that only show up dynamically. When you use this approach on some of those, it also rules out non-recursive stuff that has closed loops it will never actually follow. Those are potentially recursive but not actually recursive. Of course, those will also throw a pre-processor, so that is what you really need to detect here - the problem isn't really "recursion detection" at all. And with stack emulation that you might be able to do inside the toy language, you don't need to stay within the limits of the pre-processor anyway. (What is the toy language, by the way?) Here's an example of potential but non-actual recursion I came across once. You have a number of intercepting calls here and there, that drop status information into a sort of error handler. It reports the status, to console or to printer. But what if the anomaly shows up within console driving code or printer driving code? You make the calls have flags that indicate whether to output to console and/or to printer. That way you never get an error call handing its results on to the code that called it, so you avoid actual recursion - but the links between functions look recursive to a static analysis. Oh, my first thought on analysing the graphs was to see if the inverses of related matrices always existed; if there are loops, things related like the Leontiev matrix of economics don't always have inverses. PML.
[reply]
      Well, if you want to determine what can happen at runtime, and rule out the cases that will not happen, all you have to do is solve the halting problem. But you need something more complex than a Turing Machine to do that.

      Abigail

[reply]
        That's what I was getting at - that the problem as stated in the headline was harder than, and different from, what he really needed. But I suspect what you just described may be harder still than what he was describing in his headline. You don't always need a completely general solution, as even one that clears away a few more special cases would help. After all, the real case I outlined is non-recursive, and you don't need an oracle machine to show it. PML.
[reply]

In Section Seekers of Perl Wisdom