| Note: these documents may be out of date. Do not use as reference! |
To see what is currently happening visit http://www.perl6.org/
Backtracking
Maintainer: iVAN Georgiev <raptor@unacs.bg> Date: 14 Aug 2000 Mailing List: perl6-language@perl.org Number: 104 Version: 1 Status: Developing
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.
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 } 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.
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};
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 ?!!
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)....
perldoc perlre
The Prolog Language: www.sics.se
Coroutining facilities: www.sics.se