coroutine.clone and stateful web applications

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

coroutine.clone and stateful web applications

Markus Walther
Hello,

by way of quick introduction: I am associate professor for Computer Science at Asmara University in Eritrea/NE Africa, and we use Lua quite a bit for teaching and in student software projects!

Recently I have been looking at ways to simplify web programming in a server-side Lua scripting context. Reading up on the functional programming community's ideas, I saw their prevailing idea of using continuations, e.g.

"When the consumer submits a response to this Web form, the browser
issues a request for the URL associated with a continuation. This request and all future requests for the URL resume the continuation with the data from the Web form. In particular, because a Scheme continuation can be invoked an arbitrary number of times, the consumer can respond to the same Web form a multiple number of times and thus resume the script as often as desired." (Matthews et al. 2004:Automatically Restructuring Programs for the Web)

Recall that consumers can respond to the same web forms multiple times _because_ of the Back button and the ability of web browers to clone existing windows and re-submit them. Though it may be debatable, people often think this enriched style of interaction (allowing what-if exploration of web app behaviour) should be supported smoothly.

Lua doesn't have continuations (as first-class values) - a PhD thesis attempt from 2000 posted to lua-l apparently never made it to the Lua mainstream distribution (why not?) and the link http://www.inf.puc-rio.br/~mjulia/luacc.tgz is broken.

You can simulate simplistic continuations to a certain extent with source-to-source transformations that return closures at the (appropriately marked) resumption points, but it's a bit clumsy (and requires more restructuring in the face of loops).

But maybe COROUTINES come close, as also speculated by another post to lua-l? Only problem is: you can't resume the _same_ resumption/yield() point multiple times.

My central question therefore is: How difficult is it to make available the following new primitive

     independentCopyOfCo=coroutine.clone(co) ?

It should be callable at any time during co's life.

With this primitive we could create additional resumption points on demand.

(That demand, i.e. the fact that we are revisiting a page can be detected by the server in the web programming scenario outlined above)

I am not familiar with the innards of Lua at present - can some of the implementors help out with comments on feasibility, whether this makes sense to have for other applications and how to approach an implementation?

--Markus Walther





Reply | Threaded
Open this post in threaded view
|

Re: coroutine.clone and stateful web applications

Javier Guerra Giraldez
On Saturday 28 January 2006 2:16 pm, Markus Walther wrote:
> Recently I have been looking at ways to simplify web programming in a
> server-side Lua scripting context. Reading up on the functional
> programming community's ideas, I saw their prevailing idea of using
> continuations, e.g.

i've implemented this using coroutines, it's in the CVS of Xavante.  (can you 
access it in luaforge? if not, i can send you a tarball).

i haven't used real continuations, but i've read a bit of them in Scheme.  i 
didn't find necessary to do multiple resumptions; but to be sincere, very few 
people have looked at that code, so maybe there are some desirable features i 
haven't thought about.

IOW, look at it, i'd love to get some feedback.

-- 
Javier

Attachment: pgpFkU0qcs7yo.pgp
Description: PGP signature

Reply | Threaded
Open this post in threaded view
|

Re: coroutine.clone and stateful web applications

Mike Pall-41
In reply to this post by Markus Walther
Hi,

Markus Walther wrote:
> My central question therefore is: How difficult is it to make available 
> the following new primitive
> 
>      independentCopyOfCo=coroutine.clone(co) ?
> 
> It should be callable at any time during co's life.

See the attached experimental patch (relative to 5.1 rc). This
was a 10 minute hack, so I may not have gotten everything right.

Of course you can only clone suspended coroutines (after creation
or after yielding), i.e. not the currently running coroutine
(this would be like fork() -- doable, but not supported).

One semantic problem: open upvalues remain open only in the
original coroutine. This is usually what you want, but may yield
some semantic surprises (pun intended).

I suggest you play a little bit with it and report back to the
mailing list. I'd be interested to see the concept at work in a
non-trivial web application. Thank you!

Example program:

local resume, yield = coroutine.resume, coroutine.yield
local co1 = coroutine.create(function(x)
  for i=1,10 do yield(x+i) end
  return x+99
end)
local co2 = coroutine.clone(co1)
print("co1", resume(co1, 100))
print("co2", resume(co2, 200))
for i=1,5 do
  print("co1", resume(co1))
  print("co2", resume(co2))
end
local co3 = coroutine.clone(co2)
for i=1,5 do
  print("co1", resume(co1))
  print("co2", resume(co2))
  print("co3", resume(co3))
end

Bye,
     Mike
--- lua-5.1/src/lua.h	2006-01-10 13:50:13.000000000 +0100
+++ lua-5.1-clone/src/lua.h	2006-01-28 23:05:35.000000000 +0100
@@ -109,6 +109,7 @@
 LUA_API lua_State *(lua_newstate) (lua_Alloc f, void *ud);
 LUA_API void       (lua_close) (lua_State *L);
 LUA_API lua_State *(lua_newthread) (lua_State *L);
+LUA_API lua_State *lua_clonethread (lua_State *L, lua_State *from);
 
 LUA_API lua_CFunction (lua_atpanic) (lua_State *L, lua_CFunction panicf);
 
--- lua-5.1/src/lapi.c	2006-01-10 13:50:00.000000000 +0100
+++ lua-5.1-clone/src/lapi.c	2006-01-28 23:10:42.000000000 +0100
@@ -146,6 +146,46 @@
 }
 
 
+LUA_API lua_State *lua_clonethread (lua_State *L, lua_State *from) {
+  lua_State *to;
+  lua_lock(L);
+  if (!(from->status == LUA_YIELD ||
+      (from->status == 0 && from->ci == from->base_ci)))
+    luaG_runerror(L, "attempt to clone uncloneable coroutine");
+  lua_unlock(L);
+  to = lua_newthread(L);
+  lua_lock(to);
+  luaD_reallocstack(to, from->stacksize - EXTRA_STACK - 1);
+  luaD_reallocCI(to, from->size_ci);
+  {  /* Copy stack slots. */
+    TValue *f, *t;
+    for (f = from->stack, t = to->stack; f < from->top; f++, t++)
+      setobjs2s(to, t, f);
+    to->top = t;
+    for (; f < from->ci->top; f++, t++)
+      setnilvalue(t);
+    to->base = (from->base - from->stack) + to->stack;
+  }
+  {  /* Copy frames. */
+    CallInfo *f, *t;
+    for (f = from->base_ci, t = to->base_ci; f <= from->ci; f++, t++) {
+      t->base = (f->base - from->stack) + to->stack;
+      t->func = (f->func - from->stack) + to->stack;
+      t->top = (f->top - from->stack) + to->stack;
+      t->nresults = f->nresults;
+      t->savedpc = f->savedpc;
+      t->tailcalls = f->tailcalls;
+    }
+    to->ci = (from->ci - from->base_ci) + to->base_ci;
+  }
+  /* Copy misc fields. Hooks are deliberately not copied. */
+  to->status = from->status;
+  to->savedpc = from->savedpc;
+  lua_unlock(to);
+  return to;
+}
+
+
 
 /*
 ** basic stack manipulation
--- lua-5.1/src/lbaselib.c	2006-01-18 12:49:12.000000000 +0100
+++ lua-5.1-clone/src/lbaselib.c	2006-01-28 23:06:34.000000000 +0100
@@ -592,6 +592,14 @@
 }
 
 
+static int luaB_clone (lua_State *L) {
+  lua_State *co = lua_tothread(L, 1);
+  luaL_argcheck(L, co, 1, "coroutine expected");
+  lua_clonethread(L, co);
+  return 1;
+}
+
+
 static const luaL_Reg co_funcs[] = {
   {"create", luaB_cocreate},
   {"resume", luaB_coresume},
@@ -599,6 +607,7 @@
   {"status", luaB_costatus},
   {"wrap", luaB_cowrap},
   {"yield", luaB_yield},
+  {"clone", luaB_clone},
   {NULL, NULL}
 };
 
Reply | Threaded
Open this post in threaded view
|

Re: coroutine.clone and stateful web applications

Mike Pall-41
Hi,

I wrote:
> See the attached experimental patch (relative to 5.1 rc). This
> was a 10 minute hack, so I may not have gotten everything right.

Indeed. Add this before the last lua_unlock(to) in lua_clonethread():
  setobj2n(L, gt(to), gt(from));

Bye,
     Mike

Reply | Threaded
Open this post in threaded view
|

Re: coroutine.clone and stateful web applications

Markus Walther
Mike,

thanks for the amazingly quick patch and subsequent enhancement!

I successfully built Lua 5.1 rc with the clone patch.
My own tests show coroutine.clone to be wellbehaved sofar.

Of course, upvalues written to by one clone appear modified in the
other, as is to be expected.

>One semantic problem: open upvalues remain open only in the
>original coroutine. This is usually what you want, but may yield
>some semantic surprises (pun intended).

I don't quite follow. What's the open/closed distinction here (not
defined in the ref manual, though I see such terminology in the source)?
Can you give an example of a semantic surprise?

Other than that, I'll report back to the list again once I have a
FastCGI webapp in Lua that can demonstrate what I had in mind when
requesting coroutine.clone - that may take a little while.

Cheers, Markus


Reply | Threaded
Open this post in threaded view
|

Re: coroutine.clone and stateful web applications

Mike Pall-41
Hi,

Markus Walther wrote:
> Of course, upvalues written to by one clone appear modified in the
> other, as is to be expected.

Yes, if the upvalue is _outside_ of the coroutine context.

> >One semantic problem: open upvalues remain open only in the
> >original coroutine. This is usually what you want, but may yield
> >some semantic surprises (pun intended).
> 
> I don't quite follow. What's the open/closed distinction here (not
> defined in the ref manual, though I see such terminology in the source)?

Ok, this is a bit difficult to explain, but I'll try:

Upvalues are kept open as long as the context holding them is
alive. An open upvalue points to a stack slot. Subsequently
created closures share the same upvalue (full read-write
sharing).

If the context of the upvalue is terminated (e.g. when a function
or a loop ends) the stack slot must be freed or recycled. To
avoid dangling upvalue pointers, the upvalue is closed by copying
the value from the stack slot to an extra area in the upvalue and
changing the internal upvalue pointer to point to this area.

The upvalue struct definition helps to understand what's going on:

typedef struct UpVal {
  CommonHeader;
  TValue *v;  /* points to stack or to its own value */
  union {
    TValue value;  /* the value (when closed) */
    struct {  /* double linked list (when open) */
      struct UpVal *prev;
      struct UpVal *next;
    } l;
  } u;
} UpVal;

The following example creates 10 closures. The context is kept
alive and all share the same upvalue u. If the function exits,
the upvalue is closed, but the closures can still access it and
it will be shared:

function create_table_of_closures_with_shared_upvalue()
  local t = {}
  local u
  for i=1,10 do
    t[i] = function(y) if y then u = y else return u end end
  end
  return t      -- <-- Close of u happens here.
end

In the next example the upvalue is local to the loop. This means
it needs to be closed after every loop iteration. Every closure
gets a unique upvalue and no sharing is going on:

function create_table_of_closures_with_unshared_upvalues()
  local t = {}
  for i=1,10 do
    local u
    t[i] = function(y) if y then u = y else return u end end
    -- <-- Close of u happens here.
  end
  return t
end

There are some more complications with coroutines because an
outer lexical scope may be part of a different coroutine (i.e.
hold upvalues pointing to a different stack). But since only one
context can hold an upvalue open at any time, the algorithm still
works. Garbage collecting a coroutine closes all its open
upvalues, too.

> Can you give an example of a semantic surprise?

Cloning a coroutine duplicates the stack. But it doesn't
duplicate open upvalues because this would violate the invariant
that only one context can hold an upvalue open. Also local access
to the stack slot in the lexical context holding the upvalue
would be unshared, anyway.

A new upvalue is created if the outer lexical scope holding the
upvalue (relative to the yield point where the clone happened)
is continued in the cloned coroutine.

This upvalue is not shared with the upvalue created by the
original coroutine, but it's shared by all closures subsequently
created in the clone:

local resume, yield = coroutine.resume, coroutine.yield
local co1 = coroutine.create(function(u)
  repeat until yield(function(y) if y then u = y else return u end end)
end)
local _, f1a = resume(co1, 1)
local _, f1b = resume(co1)
local co2 = coroutine.clone(co1)
local _, f2a = resume(co2)
local _, f2b = resume(co2)
print(f1a(), f1b(), f2a(), f2b()) -- Read-only sharing is ok.
f1a(2)
print(f1a(), f1b(), f2a(), f2b()) -- But read-write sharing is not cloned.
f2a(3)
print(f1a(), f1b(), f2a(), f2b()) -- A new upvalue is shared by the clone.
local _, f1c = resume(co1)
local _, f2c = resume(co2)
print(f1a(), f1b(), f1c(), f2a(), f2b(), f2c()) -- The split is persistent.

Usually outer lexical scopes holding upvalues are either outside
of the coroutine (this works fine) or they are read-only (like
cached functions). I don't think this is much of a a problem in
practice.

Bye,
     Mike