Category: Code
Author/Contact Info Joost Diepenmaat / joost@hortus-mechanicus.net
Description: I was thinking about prolog yesterday, and how I still kinda like backtracking, so I implemented this simple module to add some kind of backtracking mechanism to perl.

Please let me know what you think

Update 1.2:
Added source filter (thanks for the tip educated_foo)

Update 1.3:
Switched Filter::Simple for Filter::Util::Call, to enable optional filtering... You can now choose between filter or import syntax (or mix both).

--
Joost.

 
package Backtracking;

$VERSION = 0.03;

use strict;
use Carp;

sub import {
    while (my $arg = shift) {  # process args
        if ($arg eq 'filter') {
            croak "'filter' option to Backtracking must be specified l
+ast!\n" if @_;

            require Filter::Util::Call;
            import Filter::Util::Call;

            filter_add(
                sub {
                    my ($status, $no_seen, $data);
                    my $count = 0;
                    while ($status = filter_read()) {
                        return $status if $status < 0;
                        if (/\bno\s+Backtracking\s+'filter'\s*;\s*$/) 
+{
                            $no_seen=1;
                            last;
                        }
                        $data .= $_;
                        $_ = "";
                        $count++;
                    }
                    $_ = $data;
                    s/\bgoal([\r\n\s]+)(\w+)([\r\n\s]*\{)/Backtracking
+::goal $1 '$2' => sub $3/g unless $status < 0;
                    $_ .= "no Backtracking 'filter';\n" if $no_seen;

                    $count;
                }
            );
        }
        elsif ($arg eq 'goal') {
            my ($package) = caller;
            no strict 'refs';
            *{$package."::goal"} = \&goal;
        }
    }
}

sub unimport {
     filter_del() if $_[0] eq 'filter';
}


sub goal($&) {
    my ($name,$code) = @_;
    my ($package) = caller;

    no strict 'refs';
    my $btarray = $package.'::BACKTRACK_'.$name;
    push @{$btarray},$code;
    if (@{$btarray} == 2) {
        eval "
sub $package".'::'."$name {
    for (@".$btarray.") {
        my \$rv = \$_->(\@_);
        return \$rv if \$rv;
    }
    return;
}

1;
" or croak $@;
    }
}



1;


__END__

=pod

=head1 NAME

Backtracking

=head1 DESCRIPTION

A very simple backtracking mechanism.

=head1 SYNOPSIS

    use Backtracking qw(goal filter);

    goal is_member {                # filter syntax
        my ($x,$y,@list) = @_;
        return $x eq $y;
    };

    goal is_member => sub {         # goal syntax
        my ($x,undef,@list) = @_;
        return unless @list;
        return is_member($x,@list);
    };


    for (qw(a b c d e f)) {
        if (is_member($_,qw(a b c d e))) {
            print "$_ is a member\n";
        }
        else {
            print "$_ is not a member\n";
        }
    }


    # That should print

    a is a member
    b is a member
    c is a member
    d is a member
    e is a member
    f is not a member

=head1 KNOWN BUGS / CAVEATS

=over 4

=item *

All goals are run in SCALAR context. This might be changed in the futu
+re.

=item *

There is no statement to express a 'cut'.

=item *

If you have the C<Filter> package installed, you can
C<use Backtracking 'filter'> to turn something like:

    goal goal1 {
        ...
    };

into

    goal 'goal1' => sub {
        ....
    };

using the following regex:

    s/\bgoal([\r\n\s]+)(\w+)([\r\n\s]*\{)/Backtracking::goal $1 '$2' =
+> sub $3/g

This might mismatch sometimes.

=back

=head1 SEE ALSO

L<Filter::Util::Call>, L<Filter::Simple>

=head1 AUTHOR

Joost Diepenmaat - joost@hortus-mechanicus.net
Replies are listed 'Best First'.
Re: Backtracking.pm
by educated_foo (Vicar) on May 10, 2002 at 15:17 UTC
    If the code is the first argument, you can use a prototype starting with '&', like this: 
    sub mymap(&@) { ... }

    [download]
    /s
[reply]
[d/l]
      Damn, i want to use it as the second argument....

      guess i'm out of luck then ? 

      -- 
Joost       downtime n. The period during which a system
            is error-free and immune from user input.

      [download]
[reply]
[d/l]
        Yeah. This one has bothered me, too. I suppose you could do something like this (untested): 
        sub is(&) { return $_[0] }
sub goal { ... }

# ...

goal 'foo' is { ... }

        [download]
        but it's not quite as nice. Option 2: write a source filter that takes 
        goal mygoal

        [download]
        and replaces it with 
        goal 'mygoal', sub

        [download]
        That might be a good way to go.

        /s

[reply]
[d/l]
[select]

Back to Code Catacombs