catch, throw, prompt, control, fluids, garbage collection

catch, throw, prompt, control, fluids, garbage collection

[Andy Wingo]

Hello all,

I am currently shaving a yak[0], trying to integrate nonlocal exits into
the VM. That's `catch', `throw', and all that. I have also been wanting
to integrate delimited continuations into Guile; that's a bigger topic.
Anyway it turns out that one can implement catch and throw using
delimited continuations. Flatt et al's paper at ICFP 07 [1] shows how.

Sitaram 93 shows why you want delimited continuations [2]. Felleisen 88
is the first appearance of delimited continuations that I'm aware of,
though I think it's behind a paywall; Sitaram and Felleisen 90 seems to
be an adequate substitute [3]. Dybvig et al 07 is a great summary of the
relationship between the various delimited continuation operators [4].

[0] http://projects.csail.mit.edu/gsb/old-archive/gsb-archive/gsb2000-02-11.html
[1] http://www.cs.utah.edu/plt/publications/icfp07-fyff.pdf
[2] http://www.ccs.neu.edu/scheme/pubs/pldi93-sitaram.pdf
[3] http://www.ccis.northeastern.edu/scheme/pubs/lasc1990-sf.pdf
[4] http://www.cs.indiana.edu/~dyb/pubs/monadicDC.pdf

So, the deal. The deal is that Flatt shows very clearly and elegantly
how to implement catch and throw using prompt, abort, and dynamic
binding. (Actually he uses the % flavor of prompt; and abort is like
Sitaram's control afaict. See Sitaram 93.) The dynamic binding is for
the current exception handler (corresponding to catch) and for the
current "abort handler", which is like a pre-unwind handler.

The problem: Well, you might want to set some exception handlers, and
then spawn a bunch of threads all with those handlers. But if a
pre-unwind handler throws an exception, that exception shouldn't be
handled by itself, or you get an infinite loop. Basically you need a bit
to say whether a given handler is running in a given thread or not -- a
fluid.

But you can't / shouldn't make a new fluid every time you enter a
`catch', because currently fluids are never garbage collected! We really
need to fix this. I think it's a 1.9 regression.

To do so effectively, I think you'd need to make fluid objects store
their values directly, so that the GC doesn't have to go through hoops
to know that they're collectable. Ideally they would get their values
via pthread_getspecific; but that would defeat some bits of ours about
"dynamic states" (not a very useful concept IMO), and the GC would need
help. Actually it would be nice if libgc supported thread-local
allocations. (Does it?)

Anyway, some disconnected thoughts here. I could have simply implemented
catch and throw using what we have now, but I think it's a great
opportunity to see if we can do delimited continations.

There's some half-complete prompt support in master. I thought I'd get
to the rest sooner, but it seems that it will take another couple weeks.
I haven't been able to have good hacktime over the last week or two, so
things are going slower than they usually do. Also, getting to
understand delimited continuations was a bit paralyzing.

Regarding the release... I have no thoughts. Perhaps I should prepare
the NEWS, and we get a release out the door this week, then the next one
will have catch/throw nicely integrated, and at that point I'll be
mostly happy for 2.0. Thoughts?

Cheers,

Andy
-- 
http://wingolog.org/

Fluids

[Ludovic Courtès]

Hi Andy!

Andy Wingo <wingo@pobox.com> writes:

> But you can't / shouldn't make a new fluid every time you enter a
> `catch', because currently fluids are never garbage collected! We really
> need to fix this. I think it's a 1.9 regression.

Indeed.  We should use a weak vector or some such instead of the current
scm_gc_malloc’d array.

> To do so effectively, I think you'd need to make fluid objects store
> their values directly, so that the GC doesn't have to go through hoops
> to know that they're collectable. Ideally they would get their values
> via pthread_getspecific; but that would defeat some bits of ours about
> "dynamic states" (not a very useful concept IMO), and the GC would need
> help. Actually it would be nice if libgc supported thread-local
> allocations. (Does it?)

I think dynamically allocating thread-local storage can only be done
with pthread_key_create ().  Libgc knows how to scan pthread keys.  So
we could have fluids be wrappers around pthread keys and fluid-ref would
boil down to pthread_getspecific ().  Then we wouldn’t even need the
fluid number hack.

Is it what you had in mind?

Thanks,
Ludo’.

Plan for the next release

[Ludovic Courtès]

Hello!

Andy Wingo <wingo@pobox.com> writes:

> Regarding the release... I have no thoughts. Perhaps I should prepare
> the NEWS, and we get a release out the door this week, then the next one
> will have catch/throw nicely integrated, and at that point I'll be
> mostly happy for 2.0. Thoughts?

I think the main focus for the two months preceding 2.0 should be:

  0. Licensing and copyright (‘pmatch’, etc.). [*]

  1. Portability fixes.

  2. Backward-compatibility fixes.

  3. Documented anything new and undocumented.

  4. Bug hunting.

If you think catch/throw on delimited continuations may be ready in a
couple of weeks, and that it’s the last big feature you have in mind for
2.0, then that’s fine with me.  :-)  Otherwise, I’d be in favor of
delaying 2.0 as long as needed so we can work on the above points.

Note that I’m in favor of shorter release cycles, which means 2.2
shouldn’t be decades away from 2.0.  We could even create a 2.2 branch
one of these days for things we want to play with but that won’t be
ready for prime time until some time.

What do you think?

Thanks,
Ludo’.

[*] For obvious reasons, we shouldn’t be accepting any new code with
    unclear copyright/licensing status.  Likewise, to be on the safe
    side, code whose copyright is to be assigned to the FSF should not
    be committed it until the copyright assignment is actually on file.

Re: Fluids

[Andy Wingo]

Heya,

On Sun 14 Feb 2010 15:32, ludo@gnu.org (Ludovic Courtès) writes:

> Andy Wingo <wingo@pobox.com> writes:
>
>> But you can't / shouldn't make a new fluid every time you enter a
>> `catch', because currently fluids are never garbage collected! We really
>> need to fix this. I think it's a 1.9 regression.
>
> Indeed.  We should use a weak vector or some such instead of the current
> scm_gc_malloc’d array.
>
>> To do so effectively, I think you'd need to make fluid objects store
>> their values directly, so that the GC doesn't have to go through hoops
>> to know that they're collectable. Ideally they would get their values
>> via pthread_getspecific; but that would defeat some bits of ours about
>> "dynamic states" (not a very useful concept IMO), and the GC would need
>> help. Actually it would be nice if libgc supported thread-local
>> allocations. (Does it?)
>
> I think dynamically allocating thread-local storage can only be done
> with pthread_key_create ().  Libgc knows how to scan pthread keys.  So
> we could have fluids be wrappers around pthread keys and fluid-ref would
> boil down to pthread_getspecific ().  Then we wouldn’t even need the
> fluid number hack.
>
> Is it what you had in mind?

Yes, this is what I had in mind; I was not aware that libgc could scan
thread-specific variables. This is great news, I think.

My only qualm regards the number of potential pthread_key variables. My
current emacs session has about 15K functions and 7K variables. Does the
pthread_key mechanism scale well to this number of thread-local
variables?

Also we would probably still need a weak vector of all fluids, to
support dynamic states. But this is well-supported by libgc.

Andy
-- 
http://wingolog.org/

Re: Plan for the next release

[Andy Wingo]

Howdy,

On Sun 14 Feb 2010 15:45, ludo@gnu.org (Ludovic Courtès) writes:

> Andy Wingo <wingo@pobox.com> writes:
>
>> Regarding the release... I have no thoughts. Perhaps I should prepare
>> the NEWS, and we get a release out the door this week, then the next one
>> will have catch/throw nicely integrated, and at that point I'll be
>> mostly happy for 2.0. Thoughts?
>
> I think the main focus for the two months preceding 2.0 should be:
>
>   0. Licensing and copyright (‘pmatch’, etc.). [*]
>
>   1. Portability fixes.
>
>   2. Backward-compatibility fixes.
>
>   3. Documented anything new and undocumented.
>
>   4. Bug hunting.

Agreed. Let me add: full parallel-installability (currently our support
is only partial), so that a 2.2 can come out without affecting 2.0
installations. (e.g. putting libguile.h in a versioned subdir, and have
pkg-config add -I$includedir/guile-2.0/ to the CFLAGS)

> If you think catch/throw on delimited continuations may be ready in a
> couple of weeks, and that it’s the last big feature you have in mind for
> 2.0, then that’s fine with me.  :-)  Otherwise, I’d be in favor of
> delaying 2.0 as long as needed so we can work on the above points.

OK. I think I can get it in, yes.

> Note that I’m in favor of shorter release cycles, which means 2.2
> shouldn’t be decades away from 2.0.  We could even create a 2.2 branch
> one of these days for things we want to play with but that won’t be
> ready for prime time until some time.

This sounds great to me.

Cheers,

Andy
-- 
http://wingolog.org/

Re: Fluids

[Ken Raeburn]

On Feb 14, 2010, at 10:50, Andy Wingo wrote:
> My only qualm regards the number of potential pthread_key variables. My
> current emacs session has about 15K functions and 7K variables. Does the
> pthread_key mechanism scale well to this number of thread-local
> variables?

Repeating the IRC info, for the rest of the audience:

POSIX implementations are allowed to impose a limit of as little as 128 keys.  It looks like glibc's limit (PTHREAD_KEYS_MAX) is 1024 on the box I'm looking at, and Mac OS X uses 512.  So, no, it won't scale.

Ken

Re: catch, throw, prompt, control, fluids, garbage collection

[Andy Wingo]

Hi,

A brief note.

On Sun 14 Feb 2010 13:33, Andy Wingo <wingo@pobox.com> writes:

> I am currently shaving a yak.

I wrote more about the yak:
http://wingolog.org/archives/2010/02/14/sidelong-glimpses

In it I concluded,

    I need an efficient with-fluids, some pieces of prompt and abort,
    and to add that all to the bootstrap language of Guile, and I have
    it.

So, regarding fluids:

> The problem: Well, you might want to set some exception handlers, and
> then spawn a bunch of threads all with those handlers. But if a
> pre-unwind handler throws an exception, that exception shouldn't be
> handled by itself, or you get an infinite loop. Basically you need a bit
> to say whether a given handler is running in a given thread or not -- a
> fluid.

It should probably be thread-local, but it doesn't need to be
per-exception-handler -- a thread-local weak hash or even a list would
be fine.

At the same time, I came to the conclusion that Guile's current
implementation of fluids is best. With Emacs we really want shallow
binding, and we can store a pointer to the fluid vector (dynamic state)
in the VM's data itself, so accessing fluids can be quite fast.

It will need to be documented that currently fluids can't be collected,
and if users need collectable fluids, they should use an indirection
(like a fluid containing a weak key hash table).

See also:
    http://www.gnu.org/s/emacs/manual/html_node/elisp/Impl-of-Scope.html
and
    http://www.franz.com/support/documentation/8.0/doc/multiprocessing.htm#wide-binding-1.

I'm close to having the problem solved, but it will take another couple
weeks. Also I haven't gotten to NEWS this evening. Sorry!

Ciao,

Andy
-- 
http://wingolog.org/

Re: catch, throw, prompt, control, fluids, garbage collection

[Andy Wingo]

Hi,

Feeling a little silly replying to myself, but...

On Mon 15 Feb 2010 23:07, Andy Wingo <wingo@pobox.com> writes:

>     I need an efficient with-fluids, some pieces of prompt and abort,
>     and to add that all to the bootstrap language of Guile, and I have
>     it.

Efficient with-fluids: check! The implementation still causes a couple
allocations, but those will be avoidable in the future as an
implementation change -- if we change the wind stack to actually be
stack-allocated, and not a list.

So on to figuring out the prompt and abort implementations...

A
-- 
http://wingolog.org/

Re: catch, throw, prompt, control, fluids, garbage collection

[Andy Wingo]

Hola,

On Thu 18 Feb 2010 23:35, Andy Wingo <wingo@pobox.com> writes:

> Feeling a little silly replying to myself, but...

Following a pattern, are we?

> On Mon 15 Feb 2010 23:07, Andy Wingo <wingo@pobox.com> writes:
>
>>     I need an efficient with-fluids, some pieces of prompt and abort,
>>     and to add that all to the bootstrap language of Guile, and I have
>>     it.
>
> Efficient with-fluids: check! So on to figuring out the prompt and
> abort implementations...

Prompt and abort: check! NB, that's full prompt and abort. Guile does
delimited continuations now. There are almost certainly bugs, but I feel
pretty good about things.

Now to finally implement catch, throw, and all that in terms of
delimited continuations... (Do I foresee a future reply from myself?)

Peace,

Andy
-- 
http://wingolog.org/

Re: catch, throw, prompt, control, fluids, garbage collection

[Andy Wingo]

Heyas,

On Thu 25 Feb 2010 01:00, Andy Wingo <wingo@pobox.com> writes:

> On Thu 18 Feb 2010 23:35, Andy Wingo <wingo@pobox.com> writes:
>
>> On Mon 15 Feb 2010 23:07, Andy Wingo <wingo@pobox.com> writes:
>>
>>>     I need an efficient with-fluids, some pieces of prompt and abort,
>>>     and to add that all to the bootstrap language of Guile, and I have
>>>     it.
>>
>> Efficient with-fluids: check! So on to figuring out the prompt and
>> abort implementations...
>
> Prompt and abort: check! Now to finally implement catch, throw, and
> all that in terms of delimited continuations... (Do I foresee a future
> reply from myself?)

Catch and throw in terms of prompt and abort: check! And passing the
test suites, of course. Give master a pull!

Andy
-- 
http://wingolog.org/

Re: catch, throw, prompt, control, fluids, garbage collection

[Neil Jerram]

Andy Wingo <wingo@pobox.com> writes:

>>> Efficient with-fluids: check! So on to figuring out the prompt and
>>> abort implementations...
>>
>> Prompt and abort: check! Now to finally implement catch, throw, and
>> all that in terms of delimited continuations... (Do I foresee a future
>> reply from myself?)
>
> Catch and throw in terms of prompt and abort: check! And passing the
> test suites, of course. Give master a pull!

Sorry for breaking the reply pattern... :-)

This all sounds like great stuff to me.  I haven't understood every
detail, but it all feels very right.

One particular application that I don't think you've mentioned: it was
recently suggested to me that when a Guile program is running under a
debugger, and hits some kind of error, the debugger could offer a menu
of places in the program to jump back to.  I think that would align
exactly with the set of prompt tags.

Two specific questions:

1. Right at the start of the yak, you introduced the need for the
"running" flag to be a fluid, because of the possibility of multiple
threads simultaneously using the same set of handlers.  I haven't
checked how dynwinds may have changed in 1.9, but in 1.8 I'm fairly sure
that your suggestion is impossible, because each new thread would be
created with a clean dynamic context (including dynwinds), and not
inherit the context of its creator thread.  And, it feels to me like
this is quite natural, not just a limitation of the 1.8 implementation.
So, are you sure that elements of the wind list can be shared across
thread, and hence that "running" really needs to be a fluid?

2. Does SRFI-34 (and the R6RS equivalent) fit into your plan at all?  I
appreciated the discussion about only being able to implement catch and
throw using call/cc, if the application doesn't also use call/cc -
because I think the problems with implementing SRFI-34 in terms of
catch/throw, or vice versa, are very similar.

        Neil

Re: Fluids

[Ludovic Courtès]

[-- Attachment #1: Type: text/plain, Size: 658 bytes --]

Hello,

ludo@gnu.org (Ludovic Courtès) writes:

> Andy Wingo <wingo@pobox.com> writes:
>
>> But you can't / shouldn't make a new fluid every time you enter a
>> `catch', because currently fluids are never garbage collected! We really
>> need to fix this. I think it's a 1.9 regression.
>
> Indeed.  We should use a weak vector or some such instead of the current
> scm_gc_malloc’d array.

Just to clarify: fluids themselves *are* GC’d, but fluid numbers aren’t
recycled so ALLOCATED_FLUIDS grows endlessly (1 byte per fluid).

The working patch below allows fluid numbers to be recycled but it’s
inefficient.  Needs more thought.

Thanks,
Ludo’.


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: the patch --]
[-- Type: text/x-patch, Size: 3928 bytes --]

diff --git a/libguile/fluids.c b/libguile/fluids.c
index d493053..157737a 100644
--- a/libguile/fluids.c
+++ b/libguile/fluids.c
@@ -34,6 +34,7 @@
 #include "libguile/deprecation.h"
 #include "libguile/lang.h"
 #include "libguile/validate.h"
+#include "libguile/bdw-gc.h"
 
 #define FLUID_GROW 20
 
@@ -63,7 +64,7 @@ static scm_i_pthread_mutex_t fluid_admin_mutex = SCM_I_PTHREAD_MUTEX_INITIALIZER
  */
 static size_t allocated_fluids_len = 0;
 static size_t allocated_fluids_num = 0;
-static char *allocated_fluids = NULL;
+static void **allocated_fluids = NULL;
 
 #define IS_FLUID(x)         SCM_I_FLUID_P (x)
 #define FLUID_NUM(x)        SCM_I_FLUID_NUM (x)
@@ -120,45 +121,53 @@ scm_i_dynamic_state_print (SCM exp, SCM port, scm_print_state *pstate SCM_UNUSED
   scm_putc ('>', port);
 }
 
-static size_t
-next_fluid_num ()
+static SCM
+new_fluid ()
 {
   size_t n;
+  SCM fluid;
+
+  /* Fluids are cells: the first word is the type tag; the second word is the
+     fluid number.  */
+  fluid = PTR2SCM (scm_gc_malloc_pointerless (sizeof (scm_t_cell), "fluid"));
+  SCM_SET_CELL_TYPE (fluid, scm_tc7_fluid);
+
+  /* Look for a fluid number.  */
 
   scm_dynwind_begin (0);
   scm_i_dynwind_pthread_mutex_lock (&fluid_admin_mutex);
 
-  if ((allocated_fluids_len > 0) &&
-      (allocated_fluids_num == allocated_fluids_len))
-    {
-      /* All fluid numbers are in use.  Run a GC to try to free some
-	 up.
-      */
-      scm_gc ();
-    }
-
   if (allocated_fluids_num < allocated_fluids_len)
+    n = allocated_fluids_num;
+  else
     {
+      /* All fluid numbers are in use.  Run a GC and look for a number recently
+	 freed.  */
+      scm_i_gc ("fluids");
+
       for (n = 0; n < allocated_fluids_len; n++)
-	if (allocated_fluids[n] == 0)
-	  break;
+	if (allocated_fluids[n] == NULL)
+	  {
+	    allocated_fluids_num--;
+	    break;
+	  }
     }
-  else
+
+  if (n >= allocated_fluids_len)
     {
       /* Grow the vector of allocated fluids.  */
-      /* FIXME: Since we use `scm_malloc ()', ALLOCATED_FLUIDS is scanned by
-	 the GC; therefore, all fluids remain reachable for the entire
-	 program lifetime.  Hopefully this is not a problem in practice.  */
-      char *new_allocated_fluids =
-	scm_gc_malloc (allocated_fluids_len + FLUID_GROW,
-		       "allocated fluids");
+      void **new_allocated_fluids =
+	scm_gc_malloc_pointerless ((allocated_fluids_len + FLUID_GROW)
+				   * sizeof (*allocated_fluids),
+				   "allocated fluids");
 
       /* Copy over old values and initialize rest.  GC can not run
 	 during these two operations since there is no safe point in
-	 them.
-      */
-      memcpy (new_allocated_fluids, allocated_fluids, allocated_fluids_len);
-      memset (new_allocated_fluids + allocated_fluids_len, 0, FLUID_GROW);
+	 them.  */
+      memcpy (new_allocated_fluids, allocated_fluids,
+	      allocated_fluids_len * sizeof (*allocated_fluids));
+      memset (new_allocated_fluids + allocated_fluids_len, 0,
+	      FLUID_GROW * sizeof (*allocated_fluids));
       n = allocated_fluids_len;
 
       /* Update the vector of allocated fluids.  Dynamic states will
@@ -167,12 +176,16 @@ next_fluid_num ()
       allocated_fluids = new_allocated_fluids;
       allocated_fluids_len += FLUID_GROW;
     }
-  
+
   allocated_fluids_num += 1;
-  allocated_fluids[n] = 1;
-  
+  allocated_fluids[n] = SCM2PTR (fluid);
+  SCM_SET_CELL_WORD_1 (fluid, (scm_t_bits) n);
+
+  GC_GENERAL_REGISTER_DISAPPEARING_LINK (&allocated_fluids[n],
+					 SCM2PTR (fluid));
+
   scm_dynwind_end ();
-  return n;
+  return fluid;
 }
 
 SCM_DEFINE (scm_make_fluid, "make-fluid", 0, 0, 0, 
@@ -186,7 +199,7 @@ SCM_DEFINE (scm_make_fluid, "make-fluid", 0, 0, 0,
 	    "with its own dynamic state, you can use fluids for thread local storage.")
 #define FUNC_NAME s_scm_make_fluid
 {
-  return scm_cell (scm_tc7_fluid, (scm_t_bits) next_fluid_num ());
+  return new_fluid ();
 }
 #undef FUNC_NAME
 

Re: Fluids

[Andy Wingo]

On Wed 03 Mar 2010 00:52, ludo@gnu.org (Ludovic Courtès) writes:

> ludo@gnu.org (Ludovic Courtès) writes:
>
>> Andy Wingo <wingo@pobox.com> writes:
>>
>>> But you can't / shouldn't make a new fluid every time you enter a
>>> `catch', because currently fluids are never garbage collected! We really
>>> need to fix this. I think it's a 1.9 regression.
>>
>> Indeed.  We should use a weak vector or some such instead of the current
>> scm_gc_malloc’d array.
>
> Just to clarify: fluids themselves *are* GC’d, but fluid numbers aren’t
> recycled so ALLOCATED_FLUIDS grows endlessly (1 byte per fluid).

One word per make-fluid, per thread, right?

FWIW I don't need fluids to be gc'd any more, though it probably is a
good idea.

A
-- 
http://wingolog.org/

Re: Fluids

[Ludovic Courtès]

Hi Andy,

Andy Wingo <wingo@pobox.com> writes:

> On Wed 03 Mar 2010 00:52, ludo@gnu.org (Ludovic Courtès) writes:
>
>> ludo@gnu.org (Ludovic Courtès) writes:
>>
>>> Andy Wingo <wingo@pobox.com> writes:
>>>
>>>> But you can't / shouldn't make a new fluid every time you enter a
>>>> `catch', because currently fluids are never garbage collected! We really
>>>> need to fix this. I think it's a 1.9 regression.
>>>
>>> Indeed.  We should use a weak vector or some such instead of the current
>>> scm_gc_malloc’d array.
>>
>> Just to clarify: fluids themselves *are* GC’d, but fluid numbers aren’t
>> recycled so ALLOCATED_FLUIDS grows endlessly (1 byte per fluid).
>
> One word per make-fluid, per thread, right?

1 byte per fluid in ALLOCATED_FLUIDS, plus potentially 1 word per fluid
per thread in the dynamic state.

> FWIW I don't need fluids to be gc'd any more, though it probably is a
> good idea.

It surely is.  :-)

Thanks,
Ludo’.

Re: Fluids

[Ludovic Courtès]

Hello!

I’ve committed a fix that allows fluid numbers to be recycled, which in
turn leads to smaller fluid vectors in dynamic states:

  http://git.sv.gnu.org/cgit/guile.git/commit/?id=bd5a75dcd8436ebe077c9ce52300d013e9519d94

There’s still room for improvement, see ‘TODO’ in ‘fluids.c’.

Thanks,
Ludo’.

Re: catch, throw, prompt, control, fluids, garbage collection

[Andy Wingo]

Hi,

A late reply :)

On Sun 28 Feb 2010 23:16, Neil Jerram <neil@ossau.uklinux.net> writes:

> it was recently suggested to me that when a Guile program is running
> under a debugger, and hits some kind of error, the debugger could
> offer a menu of places in the program to jump back to.  I think that
> would align exactly with the set of prompt tags.

Yeah! We need a fluid to hold the restarts, and some sort of restart
data type that includes a prompt tag and a description of the
restart. Something like that. We should look to see what other schemes
do, and what other lisps do.

Fortunately this can be implemented entirely in Scheme :) Someone
interested in making a prototype?

Andy
-- 
http://wingolog.org/