My google summer of code is wispylisp, a web framework.
I had been taking time away from lisp due to a burn out. Now
I am ready for some more lisping.
Web-continuation is useful but has its troubles, as mentioned in other
posts. One difficulty is it's hard to invalidate continuations that
are no longer relevant.
What I have in mind is an analogue of prolog's proof tree and cut
operator. A series of pages may be seen as a proof in the tree. User
interaction with the web application is like traversing the proof
tree. So browser duplication is like nondeterministic branching, and
back/forward buttons allows the user to pick an arbitrary node in the
tree, and branch from there. The cut operator invalidates all sibling
branches and children of a cut point.
For example, a hypothetical shopping process
1) select item
2) gift wrap options
3) billing
4) confirm and cut to 1).
The kind of item selected would influence the possible gift wrap
options. 1,2,and 3 together influence 4, which shows the invoice.
4) confirms, cuts to 1, which invalidates other branches, and then
produce a report. Here's a possible proof tree.
0) cutpoint
1a) book
1b) car
1c) woman
2aa) wrap in discreet, anonymous packaging
2ab) wrap in newspaper
2ca) wrap in latex
2cb) wrap in lingerie
3aaa) pay with mastercard
2cba) pay with pain
2cbb) pay with charm
4cbba) confirms buying a woman in lingerie with charm.
4aaaa) confirms buying a book wrapped in anonymouse packaging with
mastercard. But this branch is invalidated by "4cbba" so gives error,
and leads the user back the cutpoint 1, from where he may start another
nondeterministic buy process.
"4cbba" means a node in the fourth level of the proof tree located by
going from the root to branch c, then branch b, then branch b, then
finally branch a.
I am not sure how to implement this. The idea I have is to keep the
stack of cutpoints in the dynamic environment. A continuation would
capture the current cutpoint, and register itself as one branching in
the cutpoint. Or maybe the cut operator should be like return-from,
where the cutpoints are lexical.
I am kinda confused myself. This model doesn't really make sense
outside the web application context.
Comments?
howard yeh wrote:
> So browser duplication is like nondeterministic branching, and
> back/forward buttons allows the user to pick an arbitrary node in the
> tree, and branch from there. The cut operator invalidates all sibling
> branches and children of a cut point.
Why sibling branches? See below...
> 4aaaa) confirms buying a book wrapped in anonymouse packaging with
> mastercard. But this branch is invalidated by "4cbba" so gives error,
> and leads the user back the cutpoint 1, from where he may start another
> nondeterministic buy process.
So you lost a second sale. That can't be right :)
I'm not sure I'm understanding how this proof tree maps to an actual
session, but it does not seem correct that someone having completed
steps up to confirming their purchase should be given an error and
returned to square one. It seems more correct that 4cbba should
invalidate any earlier continuations /in that branch only/, so that if
a user after confirming a purchase uses back or a stale browser window
to try to modify the shipping options /on that purchase/ it fails, but
any other continuations in different branches (even with a common
parent) are still live.
The interesting question, then, is what to do when someone duplicates
the browser after an intermediate step, like choosing wrapping. Say
that in browser A they then choose payment and confirm. Now browser B
is still live, awaiting payment information. If you invalidate browser
A's branch all the way back to its root, then branch B just lost some
of its history. Perhaps it can go forward (if it doesn't need history
to do so), but it definitely can't go back. I guess this implies that
whenever someone duplicates a browser, you need to duplicate all
earlier continuations back to a cut point, as well.
joh wrote:
> howard yeh wrote:
> > So browser duplication is like nondeterministic branching, and
> > back/forward buttons allows the user to pick an arbitrary node in the
> > tree, and branch from there. The cut operator invalidates all sibling
> > branches and children of a cut point.
>
> Why sibling branches? See below...
>
> > 4aaaa) confirms buying a book wrapped in anonymouse packaging with
> > mastercard. But this branch is invalidated by "4cbba" so gives error,
> > and leads the user back the cutpoint 1, from where he may start another
> > nondeterministic buy process.
>
> So you lost a second sale. That can't be right :)
[snip]
> The interesting question, then, is what to do when someone duplicates
> the browser after an intermediate step, like choosing wrapping. Say
> that in browser A they then choose payment and confirm. Now browser B
> is still live, awaiting payment information. If you invalidate browser
> A's branch all the way back to its root, then branch B just lost some
> of its history. Perhaps it can go forward (if it doesn't need history
> to do so), but it definitely can't go back. I guess this implies that
> whenever someone duplicates a browser, you need to duplicate all
> earlier continuations back to a cut point, as well.
I agree that *that* is the interesting question. "Interaction-Safe
State for the Web" pertains to the topic and will be presented at ICFP
2006 by Jay McCarthy and Shriram Krishnamurthi. it can be found at
<http://scheme2006.cs.uchicago.edu/03-mccarthy.pdf>.
I think that seeing web interactions like nondeterministic programming
is interesting, but it might be simpler to see it as not sharing
side-effects between multiple invocations of the same continuation (as
a ~equivalent mental model). In my prototype continuations-based
framework, I implemented that with a functional dictionary. Every time
the dictionary was changed, the *store* variable was _rebound_, so no
side-effect was shared with the original continuation and, when the new
continuation was recaptured, it saved the new binding for *store*
(since it was dynamically scoped). It would be simpler in a DSL.
Once you have that, I don't see why you'd ever have to invalidate
anything in the webstore example. If the client presses the "Buy"
button twice*, she made 2 transactions, each with the state as it was
in the corresponding branch. As for the classic example of the online
exam, you don't need a cut operator as much as you need a global store
(e.g., a database). You can then check if an answer to the question was
stored in the *global* store, and, if so, display an appropriate error
message (There's no generic Right Thing to do here, I think). I don't
see how it makes sense to have any other kind of state than completely
shared and completely unshared.
* Obviously, you still need to protect against reloads, which can be
done with a post & redirect.
So yes, nondeterminisn is appropriate for web programming. However, I
don't see why you'd need cut.
Paul Khuong
·······@gmail.com wrote:
> Once you have that, I don't see why you'd ever have to invalidate
> anything in the webstore example.
To conserve memory, possibly? I mean, if it is possible to determine
that a branch is truly dead, it seems unfortunate to store several
continuations that can never be used.
> If the client presses the "Buy"
> button twice*, she made 2 transactions, each with the state as it was
> in the corresponding branch.
That's a neat answer, but what happens when customers start complaining
that they accidentally made multiple transactions? This may be unlikely
for "Buy," since that usually has multiple confirmations and customers
are at their most wary, but for many other things, like "delete
message" for example, you may need to help the user by detecting
multiple submissions and confirming their intent.
> I don't
> see how it makes sense to have any other kind of state than completely
> shared and completely unshared.
What about this example: A user of a webmail client has two browsers
open to compose two separate emails. We're clever enough to use
unshared memory for each message, so no problem, right? But suppose the
user is interacting with an address book in the same application, and
using back and forward in each browser to try to add more addresses to
each message? The message can't be "completely unshared": when the user
adds an address and then clicks back, they don't want to pick up from
exactly where they were before -- they want the last change to the
message to persist. But the message can't be "completely shared"
either, because changes in the other browser shouldn't affect it.
What's desired is that the message be shared /along this branch/.
So again we get the interesting questions: what if the user branches
after the message is partially composed? What if the user backs up from
after the message was sent to before the message was sent? I do like
the cut point idea for the latter problem. For the former, I still
think the most helpful thing is to duplicate the whole branch (back to
some predefined start point -- in this case, the completely unpopulated
message).
joh
joh wrote:
> ·······@gmail.com wrote:
>
> > Once you have that, I don't see why you'd ever have to invalidate
> > anything in the webstore example.
>
> To conserve memory, possibly? I mean, if it is possible to determine
> that a branch is truly dead, it seems unfortunate to store several
> continuations that can never be used.
Doubt it makes any noticeable impact in the end.
> > If the client presses the "Buy"
> > button twice*, she made 2 transactions, each with the state as it was
> > in the corresponding branch.
>
> That's a neat answer, but what happens when customers start complaining
> that they accidentally made multiple transactions? This may be unlikely
> for "Buy," since that usually has multiple confirmations and customers
> are at their most wary, but for many other things, like "delete
> message" for example, you may need to help the user by detecting
> multiple submissions and confirming their intent.
"Delete message" deletes a given (uniquely identified) message. Sure,
the user may delete a given message twice, but that's just the same as
deleting once (except maybe if you decide to show an error page).
> > I don't
> > see how it makes sense to have any other kind of state than completely
> > shared and completely unshared.
>
> What about this example: A user of a webmail client has two browsers
> open to compose two separate emails. We're clever enough to use
> unshared memory for each message, so no problem, right? But suppose the
> user is interacting with an address book in the same application, and
> using back and forward in each browser to try to add more addresses to
> each message? The message can't be "completely unshared": when the user
> adds an address and then clicks back, they don't want to pick up from
> exactly where they were before -- they want the last change to the
> message to persist. But the message can't be "completely shared"
> either, because changes in the other browser shouldn't affect it.
> What's desired is that the message be shared /along this branch/.
I don't think anyone who has any experience with the web expect changes
to affect what is shown when they press "Back". In fact, I'd expect the
opposite: considering "Back" as a local (since it can't affect what's
outside the browser's window) "Undo" button. BTW, in the current case,
the normal way to structure the interaction seems to be to have to
click on "add address" or "continue writing message" to add an address
or get to the message writing page, with the new addresses. In this
case, pressing back should simply let you undo the choice to add
addresses to the email.
> So again we get the interesting questions: what if the user branches
> after the message is partially composed? What if the user backs up from
> after the message was sent to before the message was sent? I do like
> the cut point idea for the latter problem. For the former, I still
> think the most helpful thing is to duplicate the whole branch (back to
> some predefined start point -- in this case, the completely unpopulated
> message).
Well, if the user backs up to before the message was sent once it's
already been sent, she can edit the message and resend it. I don't see
the problem with that. If you want to show an error message or a
warning that the message has already been sent, a message-id that's
generated where you would put a cut point would work just as well, but
also let you generate a meaningful message instead of just rewinding to
the cut point. Plus, it works even when you basically serialize your
continuations into URLs. Moreover, the cut doesn't let you completely
free those continuations: you must still keep a dictionary from
continuations (that have been "cut" away) to the cut point's
continuation. In any case, both approaches are equivalent, except that
the "cut"-ful approach also has an implicit GCing of the
continuation->cut-point dictionary, something which can be done
explicitly, and only makes sense when your URLs/continuations are
transient.
Paul Khuong
·······@gmail.com wrote:
> joh wrote:
> > ·······@gmail.com wrote:
> >
> > > Once you have that, I don't see why you'd ever have to invalidate
> > > anything in the webstore example.
> >
> > To conserve memory, possibly? I mean, if it is possible to determine
> > that a branch is truly dead, it seems unfortunate to store several
> > continuations that can never be used.
> Doubt it makes any noticeable impact in the end.
Well, it's essentially a memory leak. Sure, it's probably a slow leak.
If you're convinced that something else is going to be the limiting
factor that prevents huge sites from using your framework, I guess
that's fine.
> > > If the client presses the "Buy"
> > > button twice*, she made 2 transactions, each with the state as it was
> > > in the corresponding branch.
> >
> > That's a neat answer, but what happens when customers start complaining
> > that they accidentally made multiple transactions? This may be unlikely
> > for "Buy," since that usually has multiple confirmations and customers
> > are at their most wary, but for many other things, like "delete
> > message" for example, you may need to help the user by detecting
> > multiple submissions and confirming their intent.
> "Delete message" deletes a given (uniquely identified) message. Sure,
> the user may delete a given message twice, but that's just the same as
> deleting once (except maybe if you decide to show an error page).
OK, let's try another example. Let's say, sending a fax. Perhaps this
has a small cost to the user, plus ties up the receiver's phone line a
bit. It's too annoying to demand confirmation every time a user uses
the tool, but it would still be nice to warn them if they're sending a
duplicate.
To put it abstractly, I believe there's a large class of actions where
repetition is problematic. Perhaps most nonidempotent actions fall into
this category. A good framework for web applications should give the
programmer a hook for responding to the reinvocation of a continuation.
>
> > > I don't
> > > see how it makes sense to have any other kind of state than completely
> > > shared and completely unshared.
> >
> > What about this example: A user of a webmail client has two browsers
> > open to compose two separate emails. We're clever enough to use
> > unshared memory for each message, so no problem, right? But suppose the
> > user is interacting with an address book in the same application, and
> > using back and forward in each browser to try to add more addresses to
> > each message? The message can't be "completely unshared": when the user
> > adds an address and then clicks back, they don't want to pick up from
> > exactly where they were before -- they want the last change to the
> > message to persist. But the message can't be "completely shared"
> > either, because changes in the other browser shouldn't affect it.
> > What's desired is that the message be shared /along this branch/.
>
> I don't think anyone who has any experience with the web expect changes
> to affect what is shown when they press "Back". In fact, I'd expect the
> opposite: considering "Back" as a local (since it can't affect what's
> outside the browser's window) "Undo" button. BTW, in the current case,
> the normal way to structure the interaction seems to be to have to
> click on "add address" or "continue writing message" to add an address
> or get to the message writing page, with the new addresses. In this
> case, pressing back should simply let you undo the choice to add
> addresses to the email.
But "Back" is "Back," not "Undo," and many users don't equate them. (I
would guess most do not, but I have no data.) They see Back as just
another way to navigate. They have noticed that Back is faster than
clicking the same link they used before (since it pulls from cache), so
they use Back to speed up the process.
I think you are reinterpreting the meaning of "Back" to give it a
meaning that better fits with continuation style. There is certainly no
spec that says "Clicking Back should (or should not) Undo the previous
action. I can only speak from my own experience as a user, and from
spending the last five years programming a messaging system, but I
assure you that adding an address and then backing up and adding a
second address is a very natural way to interact with a browser.
I agree with the rest of your remarks. (See, I'm not just being
contrary -- I'm very interested in this topic.)
joh
joh wrote:
> OK, let's try another example. Let's say, sending a fax. Perhaps this
> has a small cost to the user, plus ties up the receiver's phone line a
> bit. It's too annoying to demand confirmation every time a user uses
> the tool, but it would still be nice to warn them if they're sending a
> duplicate.
>
> To put it abstractly, I believe there's a large class of actions where
> repetition is problematic. Perhaps most nonidempotent actions fall into
> this category. A good framework for web applications should give the
> programmer a hook for responding to the reinvocation of a continuation.
As I wrote before, this is something that can be handled by a global
store. Generate a transaction id at the cut point, and save that id to
the DB when you commit. A macro should easily capture the patterns of
use that will arise; I'm thinking dynamically scoped variable that
contains the transaction-id and handler, something like
(with-transaction body...) to open a transaction (and save the id in
the right variable), and a wrapper around send/suspend to make the
continuation check whether a commit has already been made. The only
difference (apart from your ability to generate a better error message
than warping to the cut point) is then that, with cut, GCing the set of
dead continuations is implicit when continuations time out (note that
with the global store approach, we only need to store an unique
identifier). That, and it's simpler to think about the global-store
model than cut, imo. Less magic: the explanation can be very concrete
:)
Paul Khuong
joh wrote:
> ·······@gmail.com wrote:
>
> > Once you have that, I don't see why you'd ever have to invalidate
> > anything in the webstore example.
>
> To conserve memory, possibly? I mean, if it is possible to determine
> that a branch is truly dead, it seems unfortunate to store several
> continuations that can never be used.
And furthermore, it's nice to have control over which continuations
are no longer valid. As far as I know, other frameworks use timeout,
or when user logs out, to clean continuations.
> So again we get the interesting questions: what if the user branches
> after the message is partially composed? What if the user backs up from
> after the message was sent to before the message was sent? I do like
> the cut point idea for the latter problem. For the former, I still
> think the most helpful thing is to duplicate the whole branch (back to
> some predefined start point -- in this case, the completely unpopulated
> message).
In my model, the series of continuations that lead to the "send"
action determines the final outcome. It's like a quantum possible
worlds collapse... I think in the case of webmail, it makes sense that
the send-mail process has one "solution", namely, a mail, and it being
sent.
So duplicating the browser, backtrack, duplicate the browser,
whatever, all create alternate paths to possible answers. But once
an answer is decided upon, we throw away everything else. Again, this
crucially depends on the fact that this computation has one single
answer.
> So you lost a second sale. That can't be right :)
The example isn't very good. The one crucial point I failed to
emphasize is that the cut-operator is used only when you the
programmer know there can't possibly be any more solutions. You are
satisfied with the one you've found, and can discard the rest of the
tree. Hence, all the children and siblings of the cut-point.
So as you said, invalidating other items when the user confirms to buy
one item doesn't make sense. A more likely scenario is the
shipping->payment->invoice->confirm->report process. In thise case,
the user may branches on different shipping addresses, different
payment methods, different whatever. But when he hits "confirm", then
we know he's done for the current order, and all other possibilities
are no longer relevant
Suppose the user had duplicate a window when choosing the payment
method. He goes on to confirm the payment, while the system would cut,
and redirect the user to the report. If the user goes back to the
window
he had duplicated earlier, and attempts to change the payment
method, because that continuation had been invalidated, the system
emits an error message, and suggest a place for him to start over.
> The interesting question, then, is what to do when someone duplicates
> the browser after an intermediate step, like choosing wrapping. Say
> that in browser A they then choose payment and confirm. Now browser B
> is still live, awaiting payment information. If you invalidate browser
> A's branch all the way back to its root, then branch B just lost some
> of its history. Perhaps it can go forward (if it doesn't need history
> to do so), but it definitely can't go back. I guess this implies that
> whenever someone duplicates a browser, you need to duplicate all
> earlier continuations back to a cut point, as well.
Continuations are independent from each other, that is, they don't
share any data. So you can safely delete a prior continuation, and
still invoke a latter.
Continuations are created when the server prompts user for input, not
when user duplicates the browser. What we are interested here is a
way to clean up all the continuations related to a nondeterministic,
single-solution computation.
Suppose we have something like
(defun foo ()
(if (prompt1)
(if (prompt2)
(if (prompt3)
(print "yipee!")))))
When the user visits foo, prompt1 saves the continuation (k1), outputs
a
html form, then suspends. Now, each time user submits the form for k1,
the computation proceeds to prompt2, saves a new continuation (k2),
and outputs a form, then suspends. Every time prompt2 returns from
suspension, a new continuation is created for prompt3. So you can see
we have an exponential blowup, and because we have no idea whether the
user is backtracking or duplicating window, we need to save all the
continuations.
But if we only want one answer, we can use the cut-operator:
(defun foo ()
(cut-point (start)
(if (prompt1)
(if (prompt2)
(if (prompt3)
(print "yipee!")
(cut-point 'start))))))
howard yeh wrote:
> > So you lost a second sale. That can't be right :)
>
> The example isn't very good. The one crucial point I failed to
> emphasize is that the cut-operator is used only when you the
> programmer know there can't possibly be any more solutions. You are
> satisfied with the one you've found, and can discard the rest of the
> tree. Hence, all the children and siblings of the cut-point.
I see ... that makes better sense to me.
> > The interesting question, then, is what to do when someone duplicates
> > the browser after an intermediate step, like choosing wrapping. Say
> > that in browser A they then choose payment and confirm. Now browser B
> > is still live, awaiting payment information. If you invalidate browser
> > A's branch all the way back to its root, then branch B just lost some
> > of its history. Perhaps it can go forward (if it doesn't need history
> > to do so), but it definitely can't go back. I guess this implies that
> > whenever someone duplicates a browser, you need to duplicate all
> > earlier continuations back to a cut point, as well.
>
> Continuations are independent from each other, that is, they don't
> share any data. So you can safely delete a prior continuation, and
> still invoke a latter.
Right, I was a little muddled (I've read a fair bit about
continuation-style web apps, but haven't used them), but my basic point
I think is still valid -- if you delete back to a cut point, you may
invalidate earlier continuations on multiple branches. But again, that
looked like a problem in your example, but probably isn't if you're
more careful about placing your cut point.
joh wrote:
> but my basic point
> I think is still valid -- if you delete back to a cut point, you may
> invalidate earlier continuations on multiple branches. But again, that
> looked like a problem in your example, but probably isn't if you're
> more careful about placing your cut point.
I think the whole point of the cut operator is to invalidate earlier
continuations even if they are on other computation branches...
I am not aware if any framework's doing something
so fancy. It might turn out to be unruly in practice.
In my mind though, the benefit of user feedback is greater than
the memory efficiency. The cut operator provides a controlled way
for the programmer to communicate to the user that certain of his
actions are no longer valid.
(message (Hello 'howard)
(you :wrote :on '(16 Sep 2006 11:39:23 -0700))
(
hy> My google summer of code is wispylisp, a web framework.
did you analyze performance of your framework -- i.e. how many users it can
serve on typical hardware? just interesting
hy> I am kinda confused myself. This model doesn't really make sense
hy> outside the web application context.
hy> Comments?
i don't think people really want back-button to work, since many sites
nowadays use JavaScript/AJAX stuff that does not work with browser buttons
at all. only few freaks will actully press back-button or clone browser
windows, why should you optimize for them?
at same time they can duplicate windows.
so if you want window duplication, use a link-style navigation and preserve
all continuations. but when you do a button, after you catch notification
that it's pressed, kill continuation after it's got processed.
quite simple logic, but i think it would be quite satisfying.
)
(With-best-regards '(Alex Mizrahi) :aka 'killer_storm)
"People who lust for the Feel of keys on their fingertips (c) Inity")
Alex Mizrahi wrote:
> i don't think people really want back-button to work, since many sites
> nowadays use JavaScript/AJAX stuff that does not work with browser buttons
> at all. only few freaks will actully press back-button or clone browser
> windows, why should you optimize for them?
I can't speak beyond anecdotal evidence, but in the application I work
on, people use Back all the time. Anything that breaks support for it
is guaranteed to cause problems. And supporting it without some help
from your web application framework is a living hell.
We recently took an application that had been running wild for a couple
of years, with all error messages logged but ignored, and went through
to find and fix the cause of every error logged. I'd say that the vast
majority of logged errors were caused in some way by using the browser
history.
Also, I should note that the Google Web Toolkit ("JavaScript/AJAX
stuff") goes to great lengths to support Back. And I think the tabbed
browser model encourages window cloning -- I know I clone a lot more
now that I can easily manage those extra windows.
Alex Mizrahi wrote:
> i don't think people really want back-button to work, since many sites
> nowadays use JavaScript/AJAX stuff that does not work with browser buttons
> at all. only few freaks will actully press back-button or clone browser
> windows, why should you optimize for them?
That's actually what I thought at first. Ajax turns web-app to an event
driven
model. Then I noticed that dojo allegedly supports "back button" and
"bookmarkable" url for ajax events... That brings back our old friends.
Talk about irony.
My hope is that my framework would support both styles. With
continuation or without. So for simple CRUD, the programmer
can just use stateless controllers. But for more complex page flow,
like ordering form, continuation would be a huge time saver.
> i don't think people really want back-button to work, since many sites
> nowadays use JavaScript/AJAX stuff that does not work with browser buttons
> at all. only few freaks will actully press back-button or clone browser
> windows, why should you optimize for them?
That's actually what I thought at first. Ajax turns web-app to an event
driven
model. Then I noticed that dojo allegedly supports "back button" and
"bookmarkable" url for ajax events... That brings back our old friends.
Talk about the irony.
My hope is that my framework would support both styles. With
continuation or without. So for simple CRUD, the programmer
can just use stateless controllers. But for more complex page flow,
like ordering form, continuation would be a huge time saver.