This and other RFCs are available on the web at
http://dev.perl.org/rfc/
=head1 TITLE
Backtracking
=head1 VERSION
Maintainer: iVAN Georgiev <[EMAIL PROTECTED]>
Date: 14 Aug 2000
Version: 1
Mailing List: [EMAIL PROTECTED]
Number: 104
=head1 ABSTRACT
Backtraking mechanism is core functionality of languages like PROLOG.
Perl-regex engine has this ability too.
Adding this mechanism to our programming arsenal will bring alot of
new functionality. Will help us solve problems that otherwise cost us
alot of time and effort (laziness).
A new paradigm to Perl - DECLARATIVE programming.
=head1 DESCRIPTION
The whole gang-bang can be done with only two new operators: andthen, orthen.
They behave similarly like &&, ||, and, or operator with one main
distinction they "backtrack" for example:
{ block1 } B<andthen> { block2 };
mean this:
if "block1" return true(1) "block2" is evaluated then
if "block2" return true(1) the end result is true(1)
if "block2" return false(0)
we evaluate "block1" again i.e start from the beginning.
but if "block1" return false(0) the end result is false(0)
or to be more clear this is the Perl equivalent/example:
my $res = 0;
{
my $ex1;
{ $l = (rand() > 0.3) ? 1:0;print "block1=$l\n"; $ex1=$l};
if ($ex1)
{
my $ex2;
{ $r = (rand() > 0.7) ? 1:0;print "block2=$r\n"; $ex2=$r};
if ($ex2) { $res = 1 } else { redo }
};
};
print "The result is : $res\n";
Similarly "orthen":
{ block1 } B<orthen> { block2 };
mean this:
if "block1" return true(1) the end result is true(1)
but if "block1" return false(0) "block2" is evaluated then
if "block2" return true(1) the end result is true(1)
if "block2" return false(0)
we evaluate "block1" again i.e start from the beginning.
OR this:
if "block1" return true(1)
we evaluate "block2" and return true(1)
w/o taking in consideration the result of "block2" evaluation.
but if "block1" return false(0) "block2" is evaluated then
if "block2" return true(1) the end result is true(1)
if "block2" return false(0)
we evaluate "block1" again i.e start from the beginning.
=head2 USAGE
Good candidates for "backtracking" are XML processors,
analytical "permutations!", expert systems and many more...
Cycle:
my $i = 0;
{$i++; $i <= 10 } andthen {print $i};
equivalent to:
for (my $i=1;$i++;$i<=10) {print $i};
=head2 FURTHER WORK
As you saw I tried to propose as small change to the perl
core/language as possible, which can be easily implemented.
What else we can expect?
One good addition that can we thought about is implementing
the Perl BLOCK's as forth-state BLACKBOX structure not as
it is now i.e. two states, what I mean ?
Currently AFAIK we have "entering" and "leaving" the block.
We can have "direction" i.e. with "backtrack" mechanism we
can enter the block from previous block or from the next one -
the four "states" are - enter(->),leave(->),reevaluate(<-),fall(<-),
we will need also to count how many times the block has been
in all of these states. We can leave the old behaviour as
default(in the name of speed) and only when the Perl programmer
need these states to use "state" pragma.
use state "2";
use state "4";
BUT this will be alot of work, so for now andthen, orthen
are enough. If backtracking is made as more general algorithm
it can be used both by Perl itself and regex engine ?!!
=head1 IMPLEMENTATION
There is many possible implementations one of them you saw
in DESCRIPTION section, it can also be implemented as
while, until cycle...
If I was perl-core hacker you now will be reading
and applying the patch :"), I believe that this can be very
easily implemented as just adding several lines in perly.y
(please excuse my ignorance if this is not the case)....
=head1 REFERENCES
perldoc perlre
The Prolog Language:
http://www.sics.se/SICS-reports/SICS-T--93-01--SE/report_10.html
Coroutining facilities:
http://www.sics.se/SICS-reports/SICS-T--93-01--SE/report_8.html
