Logic programming without using the RE engine as a crutch

diotalevi has asked for the wisdom of the Perl Monks concerning the following question:

I assume many of you are used to doing logic programming in perl but this is new to me. I wrote up a simple optree-recursing (this won't work in practice because of NULL nodes) expression which finds a given node in a tree and returns the path required to reach it. Is there a common way to write a more plausible implementation of $ROOT->(parent|sibling)* $target that doesn't require a regex to handle all the bookkeeping of tracking successes, failures and to-do work?

sub path_to_op
{
    my ( $root, $tgt ) = @_;

    local $op = $root;
    local @path;

    '' =~
        /(?:
            (?(?{ my $name = $op->oldname;
                  local $op = $op->parent;
                  local @path = ( @path, "$name/" ); })(?=)|(?!))
            |
            (?(?{ my $name = $op->oldname;
                  local $op = $op->sibling;
                  local @path = ( @path, "...," ); })(?=)|(?!))
         ) *

         (?(?{ $$op == $$tgt })(?=)|(?!)) /x;

    @path;
}
[download]

Comment on Logic programming without using the RE engine as a crutch Select or Download Code

Replies are listed 'Best First'.
Re: Logic programming without using the RE engine as a crutch by demerphq (Chancellor) on Jun 30, 2004 at 17:36 UTC
Maybe im totally missing the point, but the following will traverse a tree composed of hashes and return the path. `sub path_to_op { my ($node,$tgt,$path)=@_; $path\|\|=''; return $path if $node==$tgt; foreach my $key (keys %$node) { my $path=path_to_op($node->{$key},$tgt,"$path{$key}"); return $path if $path; } return '' }` [download] But this seems so blindingly obvious to me that I'm having trouble believing I understand the question. After all I know you are very competent programmer so im at a loss to accept that I understand the question correctly.... --- demerphq _{First they ignore you, then they laugh at you, then they fight you, then you win. -- Gandhi}	[reply] [d/l]
Re^2: Logic programming without using the RE engine as a crutch by diotalevi (Canon) on Jun 30, 2004 at 17:38 UTC
Oh uh. Yeah. Heh.	[reply]
Re^3: Logic programming without using the RE engine as a crutch by demerphq (Chancellor) on Jun 30, 2004 at 17:48 UTC
Sounds like you got yourself stuck in something that I believe psychologistics call "functional fixidity" you were preconditioned (probably by reading too many nodes by abigail-ii ;-) that you forgot that tree traversal is a simple thing. Anyway I offer this little perspective to maybe help you avoid such things in the future. You can metally model most perl regexes as representing a tree, a tree whose job is to see if there is a path in a given string that can traverse the tree to a legal "accepting" terminal node. So in a sense using a regex to find a path toa given node is almost the opposite of what you really want. BTW, this is only really true of an NFA based regex engine. A DFA based regex engine would traverse all the branches of the equivelent NFA engine simultaneously, arriving at the same point, but without ever backtracking. --- demerphq _{First they ignore you, then they laugh at you, then they fight you, then you win. -- Gandhi}	[reply]
Re^2: Logic programming without using the RE engine as a crutch by Anonymous Monk on Jul 02, 2004 at 15:20 UTC
http://search.cpan.org/search?m=all&q=prolog&s=1&n=50 Might help some.	[reply]
Re^3: Logic programming without using the RE engine as a crutch by Anonymous Monk on Jul 02, 2004 at 15:23 UTC
Prolog cpan search Might help.	[reply]
Re: Logic programming without using the RE engine as a crutch by Zaxo (Archbishop) on Jun 30, 2004 at 17:42 UTC
The task doesn't seem too different from that done by File::Find or any other treewalking program. How about keeping partial solutions on a stack? Backtrack with pop, go forward with push. You could implement that with recursive calls and let the stack be local and mainly implicit in the return conditions. I don't know if that could be called functional programming. It is pretty much how functional languages work under the hood. After Compline, Zaxo	[reply]


Welcome to the Monastery
	PerlMonks