Fun with nondeterministic searches
Piers Cawley
Well, I ported the following Scheme code to PIR. (The PIR is appended
to this message...
;;; Indicate that the computation has failed, and that the program
;;; should try another path. We rebind this variable as needed.
(define fail
(lambda () (error "Program failed")))
;;; Choose an arbitrary value and return it, with backtracking.
;;; You are not expected to understand this.
(define (choose . all-choices)
(let ((old-fail fail))
(call-with-current-continuation
(lambda (continuation)
(define (try choices)
(if (null? choices)
(begin
(set! fail old-fail)
(fail))
(begin
(set! fail
(lambda () (continuation (try (cdr choices)))))
(car choices))))
(try all-choices)))))
;;; Find two numbers with a product of 15.
(let ((x (choose 1 3 5))
(y (choose 1 5 9)))
(for-each display `("Trying " ,x " and " ,y #\newline))
(unless (= (* x y) 15)
(fail))
(for-each display `("Found " ,x " * " ,y " = 15" #\newline)))
Which (as anyone can plainly see) implements a non deterministic
search (and something like it could come in handy when implementing
Perl 6 Junctions).
I think I've tweaked a bug in the GC somewhere because 'parrot -t
choose.imc' and 'parrot -tG choose.imc' fail in different places.
Also, I thought Leo's patches to the stacks meant that RetContinuations
had been done away with, but the trace output implies otherwise, and it
may be that the code is failing because of this difference. The call to
fail *should* return to just after the second call to choose by
invoking the lexically held continuation, but this isn't what happens
Rejigging IMCC to use Continuations instead of RetContinuations (using
a simple minded search & replace) makes things fall over with a Bus
Error.
Enjoy.
Leopold Toetsch
> Remember how Leo wanted an example of how continuations were used?
Great example - I don't understand how it wotks though :) - but I
understand, why the PIR code might fail:
> .sub _choose
[ ... ]
> store_lex 1, "cc", P1
You aren't allowed to do that. While P1 is the return continuation
passed into C<_choose> it's not (or may be not) in P1 during the whole
function body. That's not guranteed. It's guranteed that returning from
the sub will use this continuation, that's all.
You can't assume any fixed PASM register for some PIR item.
WRT RetContinuation vs Continuation - they are still not the same. I'll
try hard to keep the distinction that RetContinuations are only used
once (which your program seems not to do). Having that distinction would
give us more then 50% speed up in plain function (and method) calls.
You can turn off this distinction in src/objects.c:782 with
#define DISBALE_RETC_RECYCLING 1
or pass to _choose a real Continuation PMC in P1.
(the program still fails, but now differently, I'll have a closer look
at it tomorrow)
leo
Piers Cawley
Okay, I fixed it (and slowed it down dramatically) by removing Return
Continuations and getting rid of the stack freelist (you can't stick a
stack frame on the freelist just because you've popped it, there might
be a continuation still looking at it). Honestly, with one item per
chunk, immutable stacks, there really is no point in having a special
case RetContinuation, you just need to maintain a continuation freelist.
I'm going to go through the DOD stuff to see about adding continuation
and stack chunk free lists to the interpreter structure. Then when the
DOD finds dead stack chunks or continuations during the course of its
job, it just shoves 'em onto the appropriate free list and carries on
its way. The new_return_continuation_pmc and new_stack_chunk or
whatever they're called can pull structures off the appropriate free
lists.
Also, if stack chunks get garbage collected, which they should be,
there's little point in having a doubly linked stack (you can't have
'prev' link back to a free stack frame because the stack is actually a
tree).
Piers Cawley
> Piers Cawley <pdca...@bofh.org.uk> wrote:
>
>> Remember how Leo wanted an example of how continuations were used?
>
> Great example - I don't understand how it wotks though :) - but I
> understand, why the PIR code might fail:
Okay, I'll try and explain it.
Every time you call choose, it grabs the current continuation (the
place that this particular call to choose will return to) and stuffs it
in a lexical variable and saves the current fail closure as
'old_fail'. Then it creates a closure called try and sticks that in the
lexical pad too. Finally, it calls try with the list of possible
choices.
Try checks to see if their are any choices left. If there are it pulls
the first item off the list of choices for a return value, and sets up
'fail' so that, when invoked it will simply call 'try' with the
remainder of the choices. Then it uses the saved continuation to return
the first item to the point where choose was called from.
If there *aren't* any choices, it sets fail to be the 'fail' that is
saved in its 'old_fail' and simply calls that.
So, what does that mean when you have:
x = _choose(array1) # cont1
y = _choose(array2) # cont2, cont3
$I0 = x
$I1 = y
$I2 = x * y
if $I2 == 15 goto success
$P0 = find_lex("fail")
$P0() # Why can't we do this? Does $P0.() work any better?
branch the_end
success:
print x
print " * "
print y
print " == 15\n"
the_end:
...
Calling the first choose sets up a try (call it try1), saves 'fail' in
that try's 'old_fail', sets up the new fail to call 'try1(3,5)' and returns
1.
The second choose call sets up a new try (try2), saves the fail that would
call 'try1(3,5)' in its old_fail, sets up the new fail to call 'try2(5,9)' and
returns 1
Obviously, 1 * 1 doesn't equal 15, so fail gets called, which in turn
calls 'try2(5,9)' which sets fail up to call 'try2(9)' and returns 5 to
cont2
y is now 5, but 1 * 5 still doesn't equal 15, so fail calls try2(9),
which sets up fail to call try2() and returns 9 to cont2
9 * 1 doesn't equal 15 either, so we call fail, which calls try2().
try2() doesn't have any choices left, so it reinstates its old_fail and
invokes that, which calls try1(3,5).
try1(3,5) sets up fail to call try1(5) and returns 3 to cont1.
So now we call _choose(1,5,9) again, which makes a new try (try3),
which sets fail up to call try3(5,9) and returns 1 to cont3.
Guess what? 1 * 3 *still* doesn't equal 15, so we fail again, which
calls try3(5,9), which returns 5 to cont3 and does what we expect to
the current fail. And finally, 3 * 5 equals 15, so we announce the glad
tidings and continue on our merry way.
If I weren't such a lazy programmer I'd have implemented a
'reset_searchs' to set fail back to the original 'This search didn't
work!' value, allowing the saved failure 'continuations' to get garbage
collected, and setting things up for new choices.
See, I told you it was easy.
Piers Cawley
> Piers Cawley wrote:
>
>> Leopold Toetsch <l...@toetsch.at> writes:
>>>
>>>Here is a proof of concept patchoid:
>>>
>> Fabulous
>>
>>>1) change to your example code:
>>> $P1 = clone P1
>>> store_lex 1, "cc", $P1
>>>(the clone strips off all recycle flags)
>>>
>> Oh nice, much neater than what I was thinking of involving making a
>> 'real' continuation and copying context info across from the return
>> continuation.
>
> Yep. That was the reason I rewrote the clone code in the first place.
>
>> ... Does this pretty much remove the last distinction between
>> RetContinuation and Continuation?
>
> Pretty much, yes. Continuation still have one relict from COWing times:
> these are warnings and errors flags buffers. But it's very likely, that
> COW copying these buffers is wrong too and a plain copy will do it, as
> it works with all stacks now. When this is removed, RetContinuations and
> Continuations are the same. It looks like the only distinction might be
> the creation of the Continuation:
>
> invokecc # create Continuation for recycling or
> callemthodcc # same
>
> newsub $P1, .Continuation, label # or
> $P1 = clone P1 # recycling disabled
>
> This OTOH means, that a Continuation created with invokecc shall be
> never silently reused. There is currently one protection in the code
> against that: If ever one Continuation is created explicitely,
> RetContinuation recycling is disabled - forever.
When you make a full continuation with clone, can't you chase up its
continuation chain and mark its reachable continuations (and only those
continuations) as non recyclable? (This is one of the reasons I think
that a Continuation should have an explicit copy of the continuation
that was current when it was made, rather than relying on
savetop/pushtopp to capture it.)
Leopold Toetsch
leo
Leopold Toetsch
>> Piers Cawley <pdca...@bofh.org.uk> wrote:
>>
>>> Remember how Leo wanted an example of how continuations were used?
>>
>> Great example - I don't understand how it wotks though :) - but I
>> understand, why the PIR code might fail:
> Okay, I'll try and explain it.
Great thanks. (I was just going through it and sometimes I have a
slight clue how it works (or better I know what's going on but I'm for
sure unable to write such a piece of code from scratch (I'm missing some
experience with this kind of progamming languages (like lisp et al))))
> $P0 = find_lex("fail")
> $P0() # Why can't we do this? Does $P0.() work any better?
It used to give tons of reduce conflicts and wrong code ... wait ... try
again ... now it works ... fixed.
$P0.() would be a method call w/o method, i.e. a parser error.
> See, I told you it was easy.
leo
Piers Cawley
> Piers Cawley <pdca...@bofh.org.uk> wrote:
>> Leopold Toetsch <l...@toetsch.at> writes:
>
>>> Piers Cawley <pdca...@bofh.org.uk> wrote:
>>>
>>>> Remember how Leo wanted an example of how continuations were used?
>>>
>>> Great example - I don't understand how it wotks though :) - but I
>>> understand, why the PIR code might fail:
>
>> Okay, I'll try and explain it.
>
> Great thanks. (I was just going through it and sometimes I have a
> slight clue how it works (or better I know what's going on but I'm for
> sure unable to write such a piece of code from scratch (I'm missing some
> experience with this kind of progamming languages (like lisp et al))))
>
>> $P0 = find_lex("fail")
>> $P0() # Why can't we do this? Does $P0.() work any better?
>
> It used to give tons of reduce conflicts and wrong code ... wait ... try
> again ... now it works ... fixed.
Oh, cool.
> $P0.() would be a method call w/o method, i.e. a parser error.
Yean, I was thinking analogous to Perl 6's proposed syntax $foo.(...)
says to treat $foo as a function reference and call it with appropriate
arguments.
Leopold Toetsch
> Leopold Toetsch <l...@toetsch.at> writes:
>
>>At (1) the continuation is marked with C<dont_cache_retc>. In C<save_context>
>>this flag is propagated to the stacks in the continuation's context. At
>>(2) or any other place, where this stacks are popped off, the stack
>>chunks are not put onto the stack chunk freelist.
>>
>
> That seems to make sense.
And it works (for your code)
Here is a proof of concept patchoid:
1) change to your example code:
$P1 = clone P1
store_lex 1, "cc", $P1
(the clone strips off all recycle flags)
2) Minimal patch (no prototypes, only pmc_reg stack)
--- parrot/classes/retcontinuation.pmc Thu Mar 25 14:37:24 2004
+++ parrot-leo/classes/retcontinuation.pmc Thu Apr 1 17:58:31 2004
@@ -90,6 +90,7 @@
sub = PMC_sub(ret) = mem_sys_allocate(sizeof(struct Parrot_Sub));
memcpy(sub, PMC_sub(SELF), sizeof(struct Parrot_Sub));
PMC_struct_val(ret) = PMC_struct_val(SELF);
+ mark_stack_not_reusable(INTERP, &sub->ctx);
return ret;
}
}
--- parrot/src/objects.c Thu Apr 1 17:11:09 2004
+++ parrot-leo/src/objects.c Thu Apr 1 17:45:25 2004
@@ -783,7 +783,7 @@
/*
* s. also src/stack_common.c:200
*/
-#define DISBALE_RETC_RECYCLING 1
+#define DISBALE_RETC_RECYCLING 0
void add_to_retc_free_list(Parrot_Interp, PMC*);
void disable_retc_free_list(Parrot_Interp);
--- parrot/src/stack_common.c Thu Apr 1 17:11:09 2004
+++ parrot-leo/src/stack_common.c Thu Apr 1 17:48:11 2004
@@ -199,11 +199,12 @@
/*
* turn this off for correct behavior with continuations
*/
-#if 0
+ if (! (PObj_get_FLAGS(chunk) & PObj_private0_FLAG)) {
assert(s < MAX_CACHED_STACKS);
chunk->free_p = e->free_list;
e->free_list = chunk;
-#endif
+ }
+
return STACK_DATAP(chunk);
}
--- parrot/src/sub.c Fri Mar 26 20:10:58 2004
+++ parrot-leo/src/sub.c Thu Apr 1 17:57:51 2004
@@ -327,11 +327,23 @@
*/
+void
+mark_stack_not_reusable(Parrot_Interp interpreter, struct
Parrot_Context *ctx)
+{
+ /*
+ * set continuation context stacks as not to be recycled
+ */
+ PObj_get_FLAGS(ctx->pmc_reg_stack) |= PObj_private0_FLAG;
+ /* ... */
+
+}
+
struct Parrot_Sub *
new_continuation(struct Parrot_Interp *interp)
{
struct Parrot_Sub *cc = new_sub(interp, sizeof(struct Parrot_Sub));
cow_copy_context(interp, &cc->ctx, &interp->ctx);
+ mark_stack_not_reusable(interp, &cc->ctx);
return cc;
}
Chromatic
> --- parrot/src/objects.c Thu Apr 1 17:11:09 2004
> +++ parrot-leo/src/objects.c Thu Apr 1 17:45:25 2004
> @@ -783,7 +783,7 @@
> /*
> * s. also src/stack_common.c:200
> */
> -#define DISBALE_RETC_RECYCLING 1
> +#define DISBALE_RETC_RECYCLING 0
That should likely be DISABLE. Fortunately, it's misspelled
consistently. :)
-- c
Larry Wall
: This OTOH means, that a Continuation created with invokecc shall be
: against that: If ever one Continuation is created explicitely,
: RetContinuation recycling is disabled - forever.
This smells an awful lot like the sawampersand hack of early Perl,
which I now thoroughly regret. We should do all we can to avoid such
"global magical pessimization at a distance". If you put something
like this into Parrot, you will have people hunting down the authors of
modules that use Continuations and doing nasty things to them. This is
healthy neither for the community, nor for the authors in question...
It would be lovely to find some way of punishing the guilty without
punishing the innocent along with them.
Larry
Piers Cawley
> Piers Cawley wrote:
>
>> Leopold Toetsch <l...@toetsch.at> writes:
>>
>>>At (1) the continuation is marked with C<dont_cache_retc>. In C<save_context>
>>>this flag is propagated to the stacks in the continuation's context. At
>>>(2) or any other place, where this stacks are popped off, the stack
>>>chunks are not put onto the stack chunk freelist.
>>>
>> That seems to make sense.
>
> And it works (for your code)
>
> Here is a proof of concept patchoid:
Fabulous
>
> 1) change to your example code:
> $P1 = clone P1
> store_lex 1, "cc", $P1
> (the clone strips off all recycle flags)
Oh nice, much neater than what I was thinking of involving making a
'real' continuation and copying context info across from the return
continuation. Does this pretty much remove the last distinction between
RetContinuation and Continuation?
Chromatic
> > $P0 = find_lex("fail")
> > $P0() # Why can't we do this? Does $P0.() work any better?
>
> It used to give tons of reduce conflicts and wrong code ... wait ... try
> again ... now it works ... fixed.
It works for NCI subs too. *Very* nice!
-- c
Leopold Toetsch
> When you make a full continuation with clone, can't you chase up its
> continuation chain and mark its reachable continuations (and only those
> continuations) as non recyclable? (This is one of the reasons I think
> that a Continuation should have an explicit copy of the continuation
> that was current when it was made, rather than relying on
> savetop/pushtopp to capture it.)
We need getting at the call chain anyway. But storing P1 elsewhere seems
not to be the right thing. OTOH a subroutine using integers only would
preserve it's context just with C<pushtopi>, if P1 is saved elsewhere.
Your proposal smells like: the return continuation is normally hidden
(i.e. not in any register, just in the context). Some opcode like
C<get_current_cont> makes it available for backtracking or such.
leo
Leopold Toetsch
> On Thu, Apr 01, 2004 at 08:00:24PM +0200, Leopold Toetsch wrote:
>: This OTOH means, that a Continuation created with invokecc shall be
>: never silently reused. There is currently one protection in the code
>: against that: If ever one Continuation is created explicitely,
>: RetContinuation recycling is disabled - forever.
> This smells an awful lot like the sawampersand hack of early Perl,
> which I now thoroughly regret. We should do all we can to avoid such
> "global magical pessimization at a distance".
Yes and yes. As said: "There is currently ...". If we disable
continuation and stack chunk recycling just for these continuations that
need it, this ugly hack can go.
The whole scheme is still under development, but there is light on the
horizon.
> Larry
leo
Piers Cawley
That certainly makes sense to me; can anyone think of cases where
having/making an explicit return continuation is a good thing?
Leopold Toetsch
> Well, I ported the following Scheme code to PIR. (The PIR is appended
> to this message...
I've cleaned up the whole freelist handling code now and added your code
as a test, which exposed one more bug: it didn't run with --gc-debug.
That's fixed now too--if a return continuation morph's to a real
continuation, it's context has to be marked. OTOH marking a return
continuation context is wrong (after invokeing it, it's context is
sooner or later outdated and might already point to freed objects).
So it seems that we have to distinguish the two cases anyway, which is
now done with one bit: recyling enabled or not.
thanks for your continuation code,
leo
Dan Sugalski
I'm OK with moving the return continuation out of P1 and into
somewhere else--I can even see throwing it on the control stack. (Or
a special register, I can live with that as well)
Explicitly making the continuation is generally unneccessary--most
calls ought to be callcc type calls, with plain call with
user-supplied continuations for tail call situations or cases where
one wants to do Evil Things. (Which is why it ought always be
available)
--
Dan
--------------------------------------"it's like this"-------------------
Dan Sugalski even samurai
d...@sidhe.org have teddy bears and even
teddy bears get drunk
Luke Palmer
> I'm OK with moving the return continuation out of P1 and into
> somewhere else--I can even see throwing it on the control stack. (Or
> a special register, I can live with that as well)
I'd like to express my vote of confidence for an RC register, which is
put in the context structure. Piers has made it clear that P1 needs
special handling, and I'd rather have special handling in a special
register.
IMCC would probably like it, too.
Luke
Dan Sugalski
It'd probably make caller and other forms of stack walking easier
too, if we do Interesting Things with it, as we'd just walk the chain
of continuations back. Hrm.
Okay, it's still early in the week, so I'm not feeling the pressure
to Just Make A Decision. Discussion for and against is, I think,
warranted before we change, yet again, the calling conventions. :)
(Though in this case it can be supplemental, leaving the retcont in
P1 as a convenience)