Nondeterministic algorithms, flexops, and stuff

[Piers Cawley]

Given an acyclic graph of nodes, where a node has a method C<kids>,
returning a list of all the nodes it points to, is it the case that
the following code:

sub descent($src, $dst) {
when $src == $dst { return $dst }
when !$src.kids { die }
otherwise {
return ( $src, descent(any($src.kids), $dst))
}
}

will return a list of nodes making up a path between the nodes $src
and $dest? Or do I need to replace C<any> and C<die> with an
appropriate implementation of C<choose> and C<fail>?

It'd be really cool if superpositions had this kind of backtracking
behaviour, but I'm *so* not going to be surprised if it doesn't...

--
Piers

"It is a truth universally acknowledged that a language in
possession of a rich syntax must be in need of a rewrite."
-- Jane Austen?

[Jonathan Scott Duff]

On Wed, Oct 30, 2002 at 02:25:02PM +0000, Piers Cawley wrote:
> Given an acyclic graph of nodes, where a node has a method C<kids>,
> returning a list of all the nodes it points to, is it the case that
> the following code:
>
> sub descent($src, $dst) {
> when $src == $dst { return $dst }
> when !$src.kids { die }
> otherwise {
> return ( $src, descent(any($src.kids), $dst))
> }
> }
>
> will return a list of nodes making up a path between the nodes $src
> and $dest? Or do I need to replace C<any> and C<die> with an
> appropriate implementation of C<choose> and C<fail>?
>
> It'd be really cool if superpositions had this kind of backtracking
> behaviour, but I'm *so* not going to be surprised if it doesn't...

Hey, that's neat. Although it looks like it returns the $src when there
isn't a path. You probably want it to return undef or something.

Perhaps where you have "die" there should be something like
$src.collapse or maybe just "return undef".

-Scott
--
Jonathan Scott Duff
du...@cbi.tamucc.edu

[Piers Cawley]

Jonathan Scott Duff <du...@cbi.tamucc.edu> writes:

> On Wed, Oct 30, 2002 at 02:25:02PM +0000, Piers Cawley wrote:
>> Given an acyclic graph of nodes, where a node has a method C<kids>,
>> returning a list of all the nodes it points to, is it the case that
>> the following code:
>>
>> sub descent($src, $dst) {
>> when $src == $dst { return $dst }
>> when !$src.kids { die }
>> otherwise {
>> return ( $src, descent(any($src.kids), $dst))
>> }
>> }
>>
>> will return a list of nodes making up a path between the nodes $src
>> and $dest? Or do I need to replace C<any> and C<die> with an
>> appropriate implementation of C<choose> and C<fail>?
>>
>> It'd be really cool if superpositions had this kind of backtracking
>> behaviour, but I'm *so* not going to be surprised if it doesn't...
>
> Hey, that's neat. Although it looks like it returns the $src when there
> isn't a path. You probably want it to return undef or something.

Nah, it'll die when there isn't a path.

> Perhaps where you have "die" there should be something like
> $src.collapse or maybe just "return undef".

Well, traditionally you have 'fail' there, wants to be some kind of
exception, but I'm not entirely sure of what the semantics should
be.

You'd do C<pick(descent($src, $dst))> to get a path though, hopefully
it'd be resolved lazily. If not, the fact that we have continuations
means that it should be possible to implement a Grahamesque
'choose/fail' pair of funcs, but it'd be so much neater to do it with
superpositions...

[Jonathan Scott Duff]

On Wed, Oct 30, 2002 at 04:03:55PM +0000, Piers Cawley wrote:
> Jonathan Scott Duff <du...@cbi.tamucc.edu> writes:
> > Hey, that's neat. Although it looks like it returns the $src when there
> > isn't a path. You probably want it to return undef or something.
>
> Nah, it'll die when there isn't a path.

duh! Of course. I was too busy thinking about the recursion.

> > Perhaps where you have "die" there should be something like
> > $src.collapse or maybe just "return undef".
>
> Well, traditionally you have 'fail' there, wants to be some kind of
> exception, but I'm not entirely sure of what the semantics should
> be.

In my very-non-exceptional programming, I'd want undef if there wasn't
a path. So, I guess your code is just fine but needs a CATCH block
in there. The superposition collapses when it finds a path or finds
that there is no path, no backtracking would be required.

[Austin Hastings]

Way outside the stuff I "get", Larry mentioned something about a
"transactional model" for flexen.

I keep wanting that to play somewhere in there, but I can't get my
brain around how it should work. Essentially, I keep degenerating into
Prolog. Since I *REALLY* don't wish to change all my perl scripts into
makefiles, that's obviously not the way to go... >:-(

But the idea that the system will constrain prior flexen based on new
data makes me wonder how to provide the new data.

I have this little dental-drill in the back of my head telling me that
your recursion/die (or fail) could be replaced by something like &= and
a while loop, but I can't make it work. Am I barking up the wrong tree?

IOW:
-------------
my $cur = $src;
my @path;
do
{
push @path, $cur;
return undef
unless $cur = any $cur.kids;
}
while ($cur != $dst);

# But now there's all these flexen
# in @path that haven't collapsed, because
# their intermediate values were valid flexen.

my @result;
do
{
unshift @result, $cur;
$cur = pop @path;
$cur &= any $cur.kids == $last;
} while ($cur);
----------------

But that's hideous. Putting the recursion back in:

sub descend($src, $dst)
{
return $dst if $src == $dst;
return undef unless $src.kids;
my @result = descend(any $src.kids, $dst);

# Trying to tie up the flexen. Am I insane?

$src &= any $src.kids == $result[0];
unshift @result, $src;
return @result;
}

=Austin

__________________________________________________
Yahoo! - We Remember
9-11: A tribute to the more than 3,000 lives lost
http://dir.remember.yahoo.com/tribute

[Piers Cawley]

Jonathan Scott Duff <du...@cbi.tamucc.edu> writes:

> On Wed, Oct 30, 2002 at 04:03:55PM +0000, Piers Cawley wrote:
>> Jonathan Scott Duff <du...@cbi.tamucc.edu> writes:
>> > Hey, that's neat. Although it looks like it returns the $src when there
>> > isn't a path. You probably want it to return undef or something.
>>
>> Nah, it'll die when there isn't a path.
>
> duh! Of course. I was too busy thinking about the recursion.
>
>> > Perhaps where you have "die" there should be something like
>> > $src.collapse or maybe just "return undef".
>>
>> Well, traditionally you have 'fail' there, wants to be some kind of
>> exception, but I'm not entirely sure of what the semantics should
>> be.
>
> In my very-non-exceptional programming, I'd want undef if there wasn't
> a path. So, I guess your code is just fine but needs a CATCH block
> in there. The superposition collapses when it finds a path or finds
> that there is no path, no backtracking would be required.

Tell you what, here's a non flexop translation of the Lisp code I
borrowed my example from. Assume for a moment that Perl has
call_with_current_continuation (it should have *something* like it...)

my @paths;

sub choose(*@choices) {
fail unless @choices;
call_with_current_continuation -> $cc {
push @paths, sub { $cc( choose @choices[1..@choices.last] ) };
}
}

sub fail {
return "Exhausted Choices" but false unless @paths;
my $p1 = pop @choices;
$p1.();
}

sub descent($src, $dst) {
when $src == $dst { return $dst }

when !$src.kids { fail }
otherwise { return $src, descent(choose($src.kids), $dst) }
}

Actually, doing things this way allows one to control whether one
searchs depth or breadth first. For breadth first, just change the
'push' in choose to an unshift...