undo()?

1262 views
Skip to first unread message

Michele Dondi

unread,
Jun 29, 2004, 11:48:58 AM6/29/04
to perl6-l...@perl.org
I must say I've still not read all apocalypses, and OTOH I suspect that
this could be done more or less easily with a custom function (provided
that variables will have a method to keep track of their history, or, more
reasonably, will be *allowed* to have it), but I wonder if Perl6 may
include a builtin undo() function to recover values prior, say, to the
last assignement (or push() or, etc. etc.[*])

For optimization reasons track of a variable's "history" may be kept only
upon explicit appearance of undo()...


[*] To be definite, any atomic value-changing expression or statement, for
a choice of "atomic" to be decided upon.


Just my 2 cents,
Michele
--
: I've actually fixed the security glitches now
Bullshit. Security is designed into a product. Your design is inherently
insecure. This is not something you can fix by pecking in a few more lines
of code.
- Jay Tilton in clpmisc, "Re: free source for bbs"

Rafael Garcia-Suarez

unread,
Jun 29, 2004, 11:57:22 AM6/29/04
to perl6-l...@perl.org
Michele Dondi wrote:
> I must say I've still not read all apocalypses, and OTOH I suspect that
> this could be done more or less easily with a custom function (provided
> that variables will have a method to keep track of their history, or, more
> reasonably, will be *allowed* to have it), but I wonder if Perl6 may
> include a builtin undo() function to recover values prior, say, to the
> last assignement (or push() or, etc. etc.[*])

Difficulties: define "history" of a function w.r.t. threads; closures;
and system side-effects (writing to files, locking them etc.)

In other words, if you want a transaction/rollback mechanism, use a
suitable transaction library that fits your needs, not a half-baked
kludge built into the base language.

Mark A. Biggar

unread,
Jun 29, 2004, 12:07:39 PM6/29/04
to Rafael Garcia-Suarez, perl6-l...@perl.org
Rafael Garcia-Suarez wrote:

Besides we already have MTOWTDI with local() and hypotheticals.

--
ma...@biggar.org
mark.a...@comcast.net

Juerd

unread,
Jun 29, 2004, 12:36:19 PM6/29/04
to Mark A. Biggar, perl6-l...@perl.org
Mark A. Biggar skribis 2004-06-29 9:07 (-0700):

> Besides we already have MTOWTDI with local() and hypotheticals.

I thought temp replaced local. If not, how do they differ? (is temp for
lexicals, local for globals (and why would that make sense?))


Juerd

Mark A Biggar

unread,
Jun 29, 2004, 1:28:36 PM6/29/04
to Juerd, Mark A. Biggar, perl6-l...@perl.org
Sorry I did mean temp.


--
Mark Biggar
mark.a...@comcast.net

Michele Dondi

unread,
Jun 29, 2004, 2:26:23 PM6/29/04
to Rafael Garcia-Suarez, Mark A. Biggar, perl6-l...@perl.org
On Tue, 29 Jun 2004, Rafael Garcia-Suarez wrote:


> Difficulties: define "history" of a function w.r.t. threads; closures;
> and system side-effects (writing to files, locking them etc.)


On Tue, 29 Jun 2004, Mark A. Biggar wrote:

> Besides we already have MTOWTDI with local() and hypotheticals.

(i) I think it's temp() in Perl6, (ii) I don't know what hypotheticals
are.

Anyway, guys, I'll take your word for it...


Michele
--
You know, you would learn a lot more mathematics from a mathematics
book than from a Mathematica book.
- Dave Rusin in sci.math, "Re: A Klein Bottle has no inside or outside."

Jonadab The Unsightly One

unread,
Jun 29, 2004, 6:50:04 PM6/29/04
to Michele Dondi, perl6-l...@perl.org
Michele Dondi <bla...@pcteor1.mi.infn.it> writes:

> I must say I've still not read all apocalypses, and OTOH I suspect
> that this could be done more or less easily with a custom function
> (provided that variables will have a method to keep track of their
> history, or, more reasonably, will be *allowed* to have it), but I
> wonder if Perl6 may include a builtin undo() function to recover
> values prior, say, to the last assignement (or push() or,
> etc. etc.[*])

Hmmm...

If we have $foo.undo(), then we will want a multi-step undo to go with
it, probably $foo.undo($n), with $n able to be negative for redo. Are
we prepared to give the mouse that cookie? (This is not intended as a
rhetorical question; I suspect people will stake out both positions.)

I heard a rumour we were getting continuations (a la Scheme). They
wouldn't be tied to a specific variable like what you propose, but
they would allow the state of the entire process to be rolled back to
an earlier point, or something along those lines. Of course, the
overhead issues are different. You don't have to start keeping delta
data just because a continuation _might_ be taken; you keep it when a
continuation _has_ been created, and then you use it if the
continuation is ever called (or such is my limited understanding).

With .undo() you would have to keep all the delta data all the time if
.undo() is used at all. You could try to only keep it for specific
variables that are used with .undo(), but that probably falls apart if
references are brought into the mix.

Could be *mightily* inefficient with RAM. Of course, you only take
that hit if you ever use .undo()

You could make the programmer specify which variables he wants delta
data for, and then any *others* wouldn't keep it and wouldn't be
undoable.

use undo <<foo bar baz>>; # Or use the funny characters I can't type.
my $foo++; $foo.undo(); # Undoes the increment.
my $quux++; $quux.undo(); # Throws an exception or something.

--
$;=sub{$/};@;=map{my($a,$b)=($_,$;);$;=sub{$a.$b->()}}
split//,"ten.thgirb\@badanoj$/ --";$\=$ ;-> ();print$/

Luke Palmer

unread,
Jun 29, 2004, 7:31:29 PM6/29/04
to Jonadab the Unsightly One, Michele Dondi, perl6-l...@perl.org
Jonadab the Unsightly One writes:
> Michele Dondi <bla...@pcteor1.mi.infn.it> writes:
>
> > I must say I've still not read all apocalypses, and OTOH I suspect
> > that this could be done more or less easily with a custom function
> > (provided that variables will have a method to keep track of their
> > history, or, more reasonably, will be *allowed* to have it), but I
> > wonder if Perl6 may include a builtin undo() function to recover
> > values prior, say, to the last assignement (or push() or,
> > etc. etc.[*])
>
> Hmmm...
>
> If we have $foo.undo(), then we will want a multi-step undo to go with
> it, probably $foo.undo($n), with $n able to be negative for redo. Are
> we prepared to give the mouse that cookie? (This is not intended as a
> rhetorical question; I suspect people will stake out both positions.)
>
> I heard a rumour we were getting continuations (a la Scheme). They
> wouldn't be tied to a specific variable like what you propose, but
> they would allow the state of the entire process to be rolled back to
> an earlier point, or something along those lines.

Oh no! Someone doesn't understand continuations! How could this
happen?! :-)

You need two things to bring the state of the process back to an earlier
state: undo and continuations. People say continuations are like time
traveling; I like to put it this way:

Say you're in the kitchen in front of the refrigerator, thinking about a
sandwitch. You take a continuation right there and stick it in your
pocket. Then you get some turkey and bread out of the refrigerator and
make yourself a sandwitch, which is now sitting on the counter. You
invoke the continuation in your pocket, and you find yourself standing
in front of the refrigerator again, thinking about a sandwitch. But
fortunately, there's a sandwitch on the counter, and all the materials
used to make it are gone. So you eat it. :-)

A continuation doesn't save data. It's just a closure that closes over
the execution stack (and any lexicals associated with it; thus the "I
want a sandwitch" thought). If things change between the taking and
invoking of the continuation, those things remain changed after
invoking.

> You could make the programmer specify which variables he wants delta
> data for, and then any *others* wouldn't keep it and wouldn't be
> undoable.
>
> use undo <<foo bar baz>>; # Or use the funny characters I can't type.
> my $foo++; $foo.undo(); # Undoes the increment.
> my $quux++; $quux.undo(); # Throws an exception or something.

A much more useful way to do this would be:

use undo << $foo $bar $baz >>;
my $foo = 41;
my $state = undo.save;
$foo++; $foo.undo($state); # or perhaps $state.remember;

That is, you save the state at certain points in execution and remember
them later, rather than quantizing on some arbitrary "step size" (one
instruction).

I don't want to think about what happens when you write:

use undo << $state >>;
...

Luke

Luke Palmer

unread,
Jun 29, 2004, 7:35:35 PM6/29/04
to Michele Dondi, Rafael Garcia-Suarez, Mark A. Biggar, perl6-l...@perl.org
Michele Dondi writes:
> On Tue, 29 Jun 2004, Rafael Garcia-Suarez wrote:
>
>
> > Difficulties: define "history" of a function w.r.t. threads; closures;
> > and system side-effects (writing to files, locking them etc.)
>
>
> On Tue, 29 Jun 2004, Mark A. Biggar wrote:
>
> > Besides we already have MTOWTDI with local() and hypotheticals.
>
> (i) I think it's temp() in Perl6, (ii) I don't know what hypotheticals
> are.

Hypotheticals are those C<let> things from Apocalypse 5. They are best
illustrated by example:

my $x = 5;
try {
let $x = 10;
die; # unsuccessful exit from block
}
# $x is 5 again
try {
let $x = 10;
} # successful exit from block
# $x is now 10

They're a way of making a hypothesis, and then if that hypothesis leads
to failure, "undoing" the hypothesis since it was false. It's really
neat stuff.

See Whatif.pm for a Truly Evil Perl 5 implementation of this kind of
thing. Don't look at the source: you might vomit.

Luke

David Storrs

unread,
Jun 30, 2004, 6:10:13 PM6/30/04
to perl6-l...@perl.org
On Tue, Jun 29, 2004 at 05:31:29PM -0600, Luke Palmer wrote:

> Oh no! Someone doesn't understand continuations! How could this
> happen?! :-)
>
> You need two things to bring the state of the process back to an earlier
> state: undo and continuations. People say continuations are like time
> traveling; I like to put it this way:
>
> Say you're in the kitchen in front of the refrigerator, thinking about a
> sandwitch. You take a continuation right there and stick it in your
> pocket. Then you get some turkey and bread out of the refrigerator and
> make yourself a sandwitch, which is now sitting on the counter. You
> invoke the continuation in your pocket, and you find yourself standing
> in front of the refrigerator again, thinking about a sandwitch. But
> fortunately, there's a sandwitch on the counter, and all the materials
> used to make it are gone. So you eat it. :-)

Urf. Okay, put me on the list as "someone who thought he understood
continuations at least somewhat but obviously didn't have a clue."

I was under the impression that a continuation was the entire state of
the program at that point and that, when invoked, it overwrites the
current state with the saved one. Therefore, if you invoke a
continuation, you are resetting everything to the when it was when the
continuation was taken. So external changes (the fact that you wrote
to a file) will remain, but internal changes (the fact that you
assigned 7 to $foo) will be undone. I'm not sure how some of the edge
cases (where things are partially internal and partially external) are
supposed to work out, for example:

$dbh = connect_to_db_and_prepare_fetch_call();
# save continuation here
close_connection_to_db($dbh);
# invoke saved continuation here
$dbh->fetch_row(); # DB has closed connection so this fails.

Needless to say, I have never worked with continuations myself, just
studied them very briefly in college (a long time ago).


> A continuation doesn't save data. It's just a closure that closes over
> the execution stack (and any lexicals associated with it; thus the "I
> want a sandwitch" thought). If things change between the taking and
> invoking of the continuation, those things remain changed after
> invoking.

Well, at least that's a nice simple explanation. Why couldn't anyone
have explained it to me that way before? Unfortunately, it means that
continuations are a lot less useful than I thought they were. :<

How do continuations and threads interact? When you take a cont, are
you taking it only within the current thread? Or does it snapshot all
threads in the process?

--Dks

Michele Dondi

unread,
Jul 1, 2004, 5:46:51 AM7/1/04
to Jonadab the Unsightly One, perl6-l...@perl.org
On Tue, 29 Jun 2004, Jonadab the Unsightly One wrote:

> If we have $foo.undo(), then we will want a multi-step undo to go with
> it, probably $foo.undo($n), with $n able to be negative for redo. Are

Definitely! I didn't add that to the point that it wuld have been obvious,
and I wanted to keep the message as simple as possible. Not sure about
negative values...

> we prepared to give the mouse that cookie? (This is not intended as a
> rhetorical question; I suspect people will stake out both positions.)

Well, I've slightly changed my mind myself too. As we have C<redo>, it may
make more sense and better fit in the natural-language-like scheme of Perl
to have a builtin undo() for blocks, with the obvious caveat that not
everything that was done a block can be undo()ne, e.g. wrt removed files
et similia...

> I heard a rumour we were getting continuations (a la Scheme). They

Even if it is not expressed properly, I think that the idea hinted at
above is more similar to this one.

> wouldn't be tied to a specific variable like what you propose, but
> they would allow the state of the entire process to be rolled back to
> an earlier point, or something along those lines. Of course, the

Yep, for sure this makes much more sense!


Michele
--
> (I don't know why I can't resist jumping in on this thread. I wonder if
> it's a mass hypnosis worm ...)
It must be the usenet equivalent of a spectacular car crash, where
passersby feel compelled to stop and stare.
- Keith Keller in clpmisc, "Re: Clarifications"

Brent 'Dax' Royal-Gordon

unread,
Jul 1, 2004, 6:37:43 AM7/1/04
to David Storrs, perl6-l...@perl.org
David Storrs wrote:
> Well, at least that's a nice simple explanation. Why couldn't anyone
> have explained it to me that way before? Unfortunately, it means that
> continuations are a lot less useful than I thought they were. :<

Actually, I think you're underestimating the little guys. After all, if
they rolled back *all* of your changes, all they could do was repeatedly
execute the same code!

> How do continuations and threads interact? When you take a cont, are
> you taking it only within the current thread? Or does it snapshot all
> threads in the process?

Continuations are an operation on the call stack (although it's usually
a call chain for continuations), so a continuation only operates on the
current thread. I think.

(Incidentally, IIRC you can implement user-mode cooperative threading
with continuations--yield() enqueues its return continuation and then
dequeues and invokes another thread's continuation. But that's not what
you're asking at all.)

--
Brent "Dax" Royal-Gordon <br...@brentdax.com>
Perl and Parrot hacker

Oceania has always been at war with Eastasia.

Rod Adams

unread,
Jul 1, 2004, 12:52:35 PM7/1/04
to perl6-l...@perl.org
Brent 'Dax' Royal-Gordon wrote:

> David Storrs wrote:
>
>> Well, at least that's a nice simple explanation. Why couldn't anyone
>> have explained it to me that way before? Unfortunately, it means that
>> continuations are a lot less useful than I thought they were. :<
>
>
> Actually, I think you're underestimating the little guys. After all,
> if they rolled back *all* of your changes, all they could do was
> repeatedly execute the same code!
>

Hmm... Could someone please give a few prototypical cases where
continuations really shine over other methods of structure?

A guess from my current understanding:

You're wanting to play with a database. You take a continuation. You see
if have a database handle open and good to go, if so you do your thing.
(can you then dismiss the continuation? do uninvoked continuations pile
up somewhere?). If the handle is not ready, you do everything needed to
prepare the handle, and then invoke the continuation.
But I don't see how a continuation gained you much over C<prepare($dbh)
unless ready($dbh);>.


So what makes them so cool?

-- Rod

Austin Hastings

unread,
Jul 1, 2004, 1:17:37 PM7/1/04
to Rod Adams, perl6-l...@perl.org
--- Rod Adams <r...@rodadams.net> wrote:
> A guess from my current understanding:
>
> You're wanting to play with a database. You take a continuation. You
> see
> if have a database handle open and good to go, if so you do your
> thing.
> (can you then dismiss the continuation? do uninvoked continuations
> pile
> up somewhere?). If the handle is not ready, you do everything needed
> to
> prepare the handle, and then invoke the continuation.
> But I don't see how a continuation gained you much over
>
> C<prepare($dbh) unless ready($dbh);>.
>
>
> So what makes them so cool?

You know how you can log in to your webmail/slashdot/sourceforge/amazon
account, and get a cookie that says you're logged in?

And you know how you can then go into your browser's history list and
pick up some entry that was invalid, or came from yesterday, and when
you click through, the cookie (local data) that says you're
legitimately logged in stays with you, so the site doesn't give you a
hard time?

That's continuation-like behavior.

Continuations will let you take "function pointers" at an arbitrary
location: instead of entering the top of the function, you can come in
to the middle. They are similar to setjmp/longjmp in this context: you
have to pass through once to "take" the continuation, before you can
invoke it. But you can invoke it arbitrarily many times, unlike
set-/long-jmp, since the continuation closes over the entire call
stack.

=Austin

Joseph Ryan

unread,
Jul 1, 2004, 2:28:20 PM7/1/04
to Luke Palmer, perl6-l...@perl.org
----- Original Message -----
From: Luke Palmer <lu...@luqui.org>
Date: Tuesday, June 29, 2004 7:31 pm
Subject: Re: undo()?
>
> Oh no! Someone doesn't understand continuations! How could this
> happen?! :-)
>
> You need two things to bring the state of the process back to an
> earlierstate: undo and continuations. People say continuations
> are like time
> traveling; I like to put it this way:
>
> Say you're in the kitchen in front of the refrigerator, thinking
> about a
> sandwitch. You take a continuation right there and stick it in your
> pocket. Then you get some turkey and bread out of the
> refrigerator and
> make yourself a sandwitch, which is now sitting on the counter. You
> invoke the continuation in your pocket, and you find yourself standing
> in front of the refrigerator again, thinking about a sandwitch. But
> fortunately, there's a sandwitch on the counter, and all the materials
> used to make it are gone. So you eat it. :-)
>
> A continuation doesn't save data. It's just a closure that closes
> overthe execution stack (and any lexicals associated with it; thus
> the "I
> want a sandwitch" thought). If things change between the taking and
> invoking of the continuation, those things remain changed after
> invoking.
>
> > You could make the programmer specify which variables he wants delta
> > data for, and then any *others* wouldn't keep it and wouldn't be
> > undoable.
> >
> > use undo <<foo bar baz>>; # Or use the funny characters I can't
> type.> my $foo++; $foo.undo(); # Undoes the increment.
> > my $quux++; $quux.undo(); # Throws an exception or something.
>
> A much more useful way to do this would be:
>
> use undo << $foo $bar $baz >>;
> my $foo = 41;
> my $state = undo.save;
> $foo++; $foo.undo($state); # or perhaps $state.remember;

Do you think it would be possible to implement C<undo> with pure Perl6 using continuations? My intuition thinks it could, but my brain starts hating me when I start to think about it... It would definitely be a pretty neat module if it could be done though.

P.S. That was a truly spectacular explanation of continuations. :)

Rod Adams

unread,
Jul 1, 2004, 6:51:33 PM7/1/04
to Austin_...@yahoo.com, perl6-l...@perl.org
Austin Hastings wrote:

Well, that's another explanation that jives with my understanding of
them..... But I still don't have an idea of when I would actually want
to use them in something I'm writing.

-- Rod

Brent 'Dax' Royal-Gordon

unread,
Jul 2, 2004, 6:31:46 AM7/2/04
to Rod Adams, Austin_...@yahoo.com, perl6-l...@perl.org
Rod Adams wrote:
> Well, that's another explanation that jives with my understanding of
> them..... But I still don't have an idea of when I would actually want
> to use them in something I'm writing.

You can use them to implement all sorts of interesting control flow
constructs.

For example, here's an implementation of exceptions (though not the one
we'll be using):

our Continuation $try_cont;

sub try(&try_block) {
temp $try_cont = take Continuation;
unless defined $! {
try_block();
}
}

sub catch(&catch_block) {
if defined $! {
catch_block($!);
}
undef $!;
}

multi sub throw(Exception $except) {
$!=$exception;
throw();
}
multi sub throw() {
$try_cont();
}

try {
throw new Exception: "Whoa there!";
}
catch {
print "Caught exception: $!";
}

(Disclaimer: untested, and I've never actually used continuations.)

Note here that we don't want the changes to $! to be undone--that's what
determines whether try_block or catch_block is executed (this time
around). If the $! changes were undone, then try_block would either be
called repeatedly until it finally managed to succeed. In the case of
the try_block used here, the program would get stuck in an infinite loop.

That example's a bit obvious, since continuations are similar to
setjmp()/longjmp(), and one of the things those functions are often used
for is exceptions. But there are other cases, too...

Suppose, for example, you're writing a disk checker (fsck, scandisk,
etc.). Like all such programs, yours has the infuriating habit of
starting over every five seconds:

for @ARGS -> $partition {
my &cont := take Continuation;

my $timer=new Timer: &cont
:interval<<5sec>> :repeat(1);

do_scan($partition);
#Aren't race conditions fun, children?

#Like this'll ever happen.
$timer.cancel();
}

Could this be done with redo()? Sure. But realize that *redo() itself
could be implemented with continuations*. Nearly any control flow
construct can. (I think a goto() can't, but that's about it.) Loops,
exceptions, and subroutines can all be implemented in terms of
continuations--but so can almost any other control flow construct you
can think of, and most likely some you can't.

Jonadab The Unsightly One

unread,
Jul 3, 2004, 11:49:39 AM7/3/04
to Juerd, Mark A. Biggar, perl6-l...@perl.org
Juerd <ju...@convolution.nl> writes:

> I thought temp replaced local.

temp is dynamic scoping, the same thing as Perl5's local.

Hypotheticals are the ones that turn permanent if everything succeeds
according to plan but revert to the old value if stuff fails -- a
rollback mechanism, basically. I was just about to mention
hypothetical scoping wrt undo but for some reason did not.

In fairness to the undo suggestion, there is a significant difference:
to use hypotheticals to revert you have to plan the reverting when (or
before) you make the change. I think continuations work this way also
(except that they don't just revert one thing). This sounds like a
no-brainer (i.e., you're writing the code that uses undo so obviously
you planned at coding time to do the reversion) until you think about
putting references into the mix; with undo you could revert an
arbitrary item.

One thing worth noting about .undo is that retrofitting it later would
not break backward-compatibility at the language level. It would be
one heck of a messy change under the hood, but any user who wasn't
using it wouldn't have to even know about the change.

Jonadab The Unsightly One

unread,
Jul 3, 2004, 12:44:34 PM7/3/04
to Brent 'Dax' Royal-Gordon, David Storrs, perl6-l...@perl.org
Brent 'Dax' Royal-Gordon <br...@brentdax.com> writes:

> Actually, I think you're underestimating the little guys. After
> all, if they rolled back *all* of your changes, all they could do
> was repeatedly execute the same code!

Except that you can pass the continuation some arguments, possibly
including functions, closures, or even other continuations, which
would rather complicate matters.

But Luke's explanation makes sense of some things I previously
couldn't make sense of.

Jonadab The Unsightly One

unread,
Jul 3, 2004, 12:48:23 PM7/3/04
to Luke Palmer, Jonadab the Unsightly One, Michele Dondi, perl6-l...@perl.org
Luke Palmer <lu...@luqui.org> writes:

> Oh no! Someone doesn't understand continuations! How could this
> happen?! :-)

Yes, well, I've only just started reading up on them recently...

> A continuation doesn't save data. It's just a closure that closes
> over the execution stack

Ah. That helps a lot. For some reason, I hadn't realize that yet
from reading about them in Dybvig.

>> You could make the programmer specify which variables he wants delta
>> data for, and then any *others* wouldn't keep it and wouldn't be
>> undoable.
>>

> A much more useful way to do this would be:
>
> use undo << $foo $bar $baz >>;
> my $foo = 41;
> my $state = undo.save;
> $foo++; $foo.undo($state); # or perhaps $state.remember;

That seems reasonable to me.

> I don't want to think about what happens when you write:
>
> use undo << $state >>;

Something terribly inefficient, I suppose. There could be a warning
in the documentation about that.

Or something could try to be clever and detect this sort of thing; I'm
not entirely certain whether that's equivalent to the halting problem,
but either way it sounds like all kinds of excitement, or something.

Reply all
Reply to author
Forward
0 new messages