Threads and asyncs

Threads and asyncs

[Marius Vollmer]

Hi,

currently, when you mark a system-async, it is run at the next 'safe'
point.  This does not take the current thread into account and thus,
you can not have thread-specific system-asyncs.  One example where you
might want to have a thread-specific async is when you want to
interrupt the computation in a certain thread, the way you can now
interrupt the repl via C-c.

I would like to specify explicitely that marking a system-async will
run its thunk in the thread that did the marking.  That should not be
a large change since the next safe point will most likely occur before
the next thread switch.

Also, I'd like to add a function that marks a system-async for a
specified thread.  The async would run at the next safe point in that
thread.

The implementation can be changed from a global list of system-asyncs,
each with a mark, to a per-thread list of marked system-asyncs.
Marking a system-asnyc for a thread would add that system-async to the
thread's lists.  SCM_ASYNC_TICK would check whether the current
thread's list is non-empty.  Also, a thread would wake up when it is
blocked and run its asyncs anyway.

'sigaction' can be extended to allow marking of an async for a
specified thread.

With this change, an async would simply be a thunk.  We could just use
the thunk directly and deprecate the async abstraction.

OK?

(Non-system asyncs would not be affected.)

-- 
GPG: D5D4E405 - 2F9B BCCC 8527 692A 04E3  331E FAF8 226A D5D4 E405


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Threads and asyncs

[Tom Lord]

	> I would like to specify explicitely that marking a system-async will
	> run its thunk in the thread that did the marking.


Why can't that be layered?

In other words, start with thread-independent asyncs (which have the
virtue of simplicity and speed) and then build thread-specific on top
of that (at additional cost).

Is there no use for thread-independent system-asyncs?

There is a definate design tension trying to model stack-based,
kernel-driven execution in Scheme.

I've often considered layering call/cc for that reason -- making it
strictly optional, perhaps with a modest performance penalty,
implementing it via a transformation to continuation passing style.
One difficulty is primitives that call apply or eval: you can do away
with them or give them their own threads or mirror them in
tail-recursive scheme (somehow).

There are other alternatives, such as radical changes to the execution
model, so that C stacks aren't used by Scheme at all.  In my personal
Scheme design, this is the route I've (more or less) decided on.  When
worked out, and made to work cleanly with primitives written in
"classic C style" (i.e., freely calling eval or apply), I think it
winds up converging on more-or-less the same solution as making
call/cc work by transformation to CPS.

Anyway, where I to hack Guile, I'd look into building up the
abstractions to a point where eval is potentially a stackless graph
machine, instead of a hybrid stack/graph machine -- but preserving
optimizations such as SCM's copying-gc for environment frames.

-t


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Threads and asyncs

[Marius Vollmer]

Tom Lord <lord@regexps.com> writes:

> 	> I would like to specify explicitely that marking a system-async will
> 	> run its thunk in the thread that did the marking.
> 
> 
> Why can't that be layered?

Hmm, I don't see the need.

> In other words, start with thread-independent asyncs (which have the
> virtue of simplicity and speed) [...]

I don't think they are simpler or faster.

> Is there no use for thread-independent system-asyncs?

I can't think of any, right now.  The question is not whether to
execute a async in a thread or not, the question is only, in which
thread.  A thread-independent wouldn't care in what thread it is
executed so it is OK to run it in the thread that has marked it.

-- 
GPG: D5D4E405 - 2F9B BCCC 8527 692A 04E3  331E FAF8 226A D5D4 E405


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Threads and asyncs

[Tom Lord]

	> I don't think they are simpler or faster.

Plausibly thread-independent asyncs are faster, at least by a few
instructions, since global data is less expensive to access than
thread-specific data.  Against that, I suppose, are locking issues.

My concern is not only how it works out in the current implementation,
as an incremental change -- but also how it works out as a candidate
feature of an implementation independent Scheme API.   While the
performance loss may be negligable in Guile, it might not be in other
plausible implementations.

There's always wiggle room.  Nobody has said that it's Guile's job to
solve the Scheme API problem.  You can (and have) just declare "that
doesn't matter for Guile's aims" and then there is no basis for
disagreement.


	> Is there no use for thread-independent system-asyncs?

	I can't think of any, right now.  

Any short computation that needs to be invoked asynchronously (say,
perhaps, driven by a timer) is a candidate.  One can imagine efficient
I/O working this way, for example; or simple animation of some sort in
a GUI.

Suppose we have a multi-CPU system and an application with roughly one
thread per CPU -- being able to schedule tasks that float to the next
available CPU seems obviously useful, to me.

-t


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Threads and asyncs

[Rob Browning]

Tom Lord <lord@regexps.com> writes:

> There are other alternatives, such as radical changes to the execution
> model, so that C stacks aren't used by Scheme at all.  In my personal
> Scheme design, this is the route I've (more or less) decided on.  When
> worked out, and made to work cleanly with primitives written in
> "classic C style" (i.e., freely calling eval or apply), I think it
> winds up converging on more-or-less the same solution as making
> call/cc work by transformation to CPS.

If I understand correctly, one of the reasons guile used the "one (C)
stack with copying" approach was so that call/cc could work properly
with a stack that included intermixed C and scheme function calls
without too much extra magic.  If that's a correct assesment, then how
do you deal with that problem in a stackless approach?

It was also my impression that the call/cc issue, along with an
aversion to having to explicitly deal with GC on the C side (which as
you've pointed out before might be dealt with via preprocessing,
etc.), were the two main things that would make switching to a
stackless approach somewhat controversial or difficult.  Are those the
only two big issues, or are there others?

(fairly interested in the topic ATM)

Thanks

-- 
Rob Browning
rlb @defaultvalue.org, @linuxdevel.com, and @debian.org
Previously @cs.utexas.edu
GPG=1C58 8B2C FB5E 3F64 EA5C  64AE 78FE E5FE F0CB A0AD


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Threads and asyncs

[Tom Lord]

   From: Rob Browning <rlb@defaultvalue.org>

   > If I understand correctly, one of the reasons guile used the "one (C)
   > stack with copying" approach was so that call/cc could work properly
   > with a stack that included intermixed C and scheme function calls
   > without too much extra magic.  If that's a correct assesment, then how
   > do you deal with that problem in a stackless approach?


Well, blush....

I think I initially overvalued that feature.   I (nowadays) don't
think it should be central to _any_ implementation.

Instead, i'd make an implementation that is good as just a pure scheme
implementation, then add in that seductive integration with that C
stack via a foreign-function interface.  I think a good pure scheme is
not at all likely to use the C stack that way, especially for
procedures of central importance like `apply' and `eval'.

Most primitives, especially the core ones, would not rely on using the
C stack in the manner of SCM.

But since Guile is an extension language, one should _be able to_
write primitives that way (i.e. C-stack friendly), perhaps with a
modest performance trade-off, when necessary.  That would let people
add Guile to programs with minimal disruption.

In fact, the C-stack-friendly API could be made largely implementation
independent.

If Guile never budges on the stack issue, I would still be inclined to
see it as an implementation optimized for cases when the C stack is
used heavily.



   > It was also my impression that the call/cc issue, along with an
   > aversion to having to explicitly deal with GC on the C side (which as
   > you've pointed out before might be dealt with via preprocessing,
   > etc.), were the two main things that would make switching to a
   > stackless approach somewhat controversial or difficult.  Are those the
   > only two big issues, or are there others?

You've caught me talking from memory.   We'd need to sit down with a
wiki or whiteboard and map it out together.   I won't pretend to be
able to list all the issues off the top of my head.   I won't pretend
to have finished my own personal map of the various design spaces :-)

Do you have a good library of Scheme implementation papers?  Maybe
there should be a collaborative bibliography to bring together a bunch
of the good ideas floating around out there.

-t




_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Threads and asyncs

[Tom Lord]

       > If Guile never budges on the stack issue, I would still be
       > inclined to see it as an implementation optimized for cases
       > when the C stack is used heavily.

And, not to reopen old wounds or restart old fights --- 

RnRS is plainly wrong on (eq? #f '()) ....  that's the biggest
obstacle.

Indeed, after resuming hacking emacs lisp in recent history, I'm
starting to think that the old CL bit of:

	(car nil) => nil
	(cdr nil) => nil

is also not a bad idea.   "Protective errors" are often wrong.

-t




_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Threads and asyncs

[Marius Vollmer]

Tom Lord <lord@regexps.com> writes:

> 	> Is there no use for thread-independent system-asyncs?
> 
> 	I can't think of any, right now.  
> 
> Any short computation that needs to be invoked asynchronously (say,
> perhaps, driven by a timer) is a candidate.  One can imagine efficient
> I/O working this way, for example; or simple animation of some sort in
> a GUI.

Hmm, I'd like to see these as thread-independent sources of async
activation, not as thread-independent asyncs.  A timer could be
configured to mark a particular async to run in whatever thread is
current when the timer goes off.  Likewise when I/O becomes possible.

Compared to thread-independent asyncs, you will only notice a
difference when there is a thread switch between the time an async is
marked and the original thread next checks for asyncs.  If that ever
becomes a problem, we can make a thread check its asyncs before
switching away from the CPU.

-- 
GPG: D5D4E405 - 2F9B BCCC 8527 692A 04E3  331E FAF8 226A D5D4 E405


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Threads and asyncs

[Lynn Winebarger]

On Monday 02 September 2002 18:36, Tom Lord wrote:
>        > If Guile never budges on the stack issue, I would still be
>        > inclined to see it as an implementation optimized for cases
>        > when the C stack is used heavily.
> 
> And, not to reopen old wounds or restart old fights --- 
       
   You were making sense right up until this part.
   
Lynn


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Threads and asyncs

[Tom Lord]

   >> And, not to reopen old wounds or restart old fights --- 
   >> [#f vs ()]

   > You were making sense right up until this part.


SCM (still?) supports:

	(eq? #f ()) => #t

Guile has:

	(eq? #f '()) => #f


R4RS arguably permits either.

R5RS mandates Guile's behavior.

Old implementations have SCM's behavior (also found in systas scheme).

Common Lisp and Emacs Lisp have SCM's behavior.

A while back I tried to flame the current guile developers into
submission on this point, but they are resiliant against such attacks.
The "restart old fights" bit is in reference to that flame war -- it's
just me obsequiously mentioning the design issue in a hopefully
neutral way.

The SCM behavior described above is correct, if for no other reason
than that's how space aliens do it (see c.l.s. a few months back) :-)

the sometimes silly,
-t


(I really like english: what's the difference between obsequious and
sycophantic?)


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Threads and asyncs

[Thomas Bushnell, BSG]

Tom Lord <lord@regexps.com> writes:

> And, not to reopen old wounds or restart old fights --- 
> 
> RnRS is plainly wrong on (eq? #f '()) ....  that's the biggest
> obstacle.

But to do it anyway.

You keep saying "plainly wrong" which is the most infuriating part.

Seems to me it's *plainly right*.


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Threads and asyncs

[Thomas Bushnell, BSG]

Tom Lord <lord@regexps.com> writes:

> Common Lisp and Emacs Lisp have SCM's behavior.

No, Common Lisp and Emacs Lisp have (eq '() nil) -> t.

> A while back I tried to flame the current guile developers into
> submission on this point, but they are resiliant against such attacks.
> The "restart old fights" bit is in reference to that flame war -- it's
> just me obsequiously mentioning the design issue in a hopefully
> neutral way.

Perhaps they didn't submit, but rather actually *agreed* with the R5RS
editors.

Or is that just totally impossible??




_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

RnRS process/history/documentation (was Re: Threads and asyncs)

[Lynn Winebarger]

On Monday 02 September 2002 20:28, Tom Lord wrote:
> ObPolitics 2: The, arguably politically problematic process by which
> the RnRS arose (arises?) also adds lots of noise to any signal that
> might be there.

      I've found reading the rrrs-authors archives from
http://www.swiss.ai.mit.edu/projects/scheme/rrrs-archive.html
very enlightening.  Too bad it stops at 1998.  For example,
it reveals why Guile has the macro expansion problems it
has.
    Maybe a pointer to that archive should go up on the Guile
webpage somewhere.
      
Lynn



_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Threads and asyncs

[Rob Browning]

Tom Lord <lord@regexps.com> writes:

> ObPolitics: If you think this is merely a friendly design space
> disagreement, that will work itself out on the merits of which idea
> works out better in practice, think again.

Believe it or not, I was *actually* thinking "I hope no one brings
this up so we can continue with a conversation that *appears* to be
headed in a productive direction."

Oh well.

-- 
Rob Browning
rlb @defaultvalue.org, @linuxdevel.com, and @debian.org
Previously @cs.utexas.edu
GPG=1C58 8B2C FB5E 3F64 EA5C  64AE 78FE E5FE F0CB A0AD


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Threads and asyncs

[Tom Lord]

       > You keep saying "plainly wrong" which is the most infuriating part.

       > Seems to me it's *plainly right*.


Yes, well...

[very long list of purely anecdotal reasons why you are full of crap
omitted]

None of which is a solid argument that you are wrong.

So there we are.

ObPolitics: If you think this is merely a friendly design space
disagreement, that will work itself out on the merits of which idea
works out better in practice, think again.  Accidental economics of
the situation give significantly greater weight to one side than the
other -- which is an economic bug (at least comperable to standards
for railroad-track sizes; arguably much more serious).

ObPolitics 2: The, arguably politically problematic process by which
the RnRS arose (arises?) also adds lots of noise to any signal that
might be there.

ObPolitics 3: As nearly as I can tell, I'm having much more *fun*
programming in my #f == () implementation than y'all are in your #f !=
() implementation.  Nyah nyah!

ObPolitics 4: a *process* to map out the design space for this an
other issues would be more valuable to me, at this juncture, than
continued contextless argument over this particular design issue.


-t


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Threads and asyncs

[Tom Lord]

   Perhaps they didn't submit, but rather actually *agreed* with the R5RS
   editors.

   Or is that just totally impossible??


Whatever.  This is very boring.

-t



_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Threads and asyncs

[Tom Lord]

   >> Perhaps they didn't submit, but rather actually *agreed* with the R5RS
   >> editors.

   >> Or is that just totally impossible??


   > Whatever.  This is very boring.


Or is it possible that it is only boring to me, and not to others?

Perhaps it is exciting from some other perspective...have you
considered that?

Your constant argumentation agitates me.

Not.

-t



_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Threads and asyncs

[Thomas Bushnell, BSG]

Tom Lord <lord@regexps.com> writes:

> None of which is a solid argument that you are wrong.

If you don't want flame wars, then don't post trolls.  



_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Threads and asyncs

[Tom Lord]

   Tom Lord <lord@regexps.com> writes:

   > ObPolitics: If you think this is merely a friendly design space
   > disagreement, that will work itself out on the merits of which idea
   > works out better in practice, think again.

   Believe it or not, I was *actually* thinking "I hope no one brings
   this up so we can continue with a conversation that *appears* to be
   headed in a productive direction."

   Oh well.


Oh gosh, dude.   Please don't take it that way.

I like chatting with the guile developers.

For some greater context on obpolitics, see the arch mailing list
archives at regexps.com, the fsb mailing list archives at crynwr.com,
and I'd be happy to fill you in on anything that's not clear.

Talking with y'all has been generally productive, at least for me.
Sorry if it isn't for you -- that's not my intent.

Gnu Cash made newsforge recently -- congrats!

Practical guile applications actually give me a little hope :-)

Lillypond makes me (please forgive the vulgarity) cream my jeans.

-t



_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Threads and asyncs

[Lynn Winebarger]

On Monday 02 September 2002 20:27, Rob Browning wrote:
> Tom Lord <lord@regexps.com> writes:
> 
> > ObPolitics: If you think this is merely a friendly design space
> > disagreement, that will work itself out on the merits of which idea
> > works out better in practice, think again.
> 
> Believe it or not, I was *actually* thinking "I hope no one brings
> this up so we can continue with a conversation that *appears* to be
> headed in a productive direction."

    I agree, it was headed in a good direction (actually right towards
the subject of the "Stack SIze?" thread on guile-user).
     What is the upper limit on the trouble Guile users could be made
to deal with vis-a-vis garbage collection, in particular, precise
generational,copying,compacting garbage collection?  They apparently
have to go to some trouble now to make sure the compiler doesn't
optimize SCM's off the stack.  Would it be too much to have them
explicitly declare the lifetimes of these SCMs (alternatively, to insure
they are accessible from some known root)?  Or to make them
not hide SCM's in other values in the un-preprocessed source
(so we could write a pass to analyze types for the GC to use)?
     Yeah, I know, it's all blue sky.
     As long as we're at it, I'd like the C continuation semantics to 
be that you can't return from a C function twice, but otherwise
you can jump back and forth between Scheme code even
if you returned through the C function once.  There's really
no reason to pretend C functions have anything like a real
continuation, so we shouldn't have to go to special lengths
to support them (ok, keep around the old behaviour for those
who really,really want it applied to specific functions that are
written specifically to be valid: i.e. they guarantee no resources
in use (other than the ones on the stack, which are maintained
by the copying) are explicitly freed by their return.
      As for the rest, I think we should make C functions
declare themselves as primitives that never call Scheme,
and "other", that might call eval.  The first could use some
fixed "scratch" stack space, the others should get a freshly
allocated stack (whose size they declare through snarfage
or somesuch).  The interpreter could then analyze the
scheme code to find regions "between" call/cc's that could
use some fixed stack.  Call/cc's allocate a fresh Scheme
stack for the "next" block of code that gets executed.
    Is that enough to get us back on track?


ObGripe:  Pick one mailing list or the other.  

Lynn
 


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Threads and asyncs

[Marius Vollmer]

Marius Vollmer <mvo@zagadka.ping.de> writes:

> Also, a thread would wake up when it is blocked and run its asyncs
> anyway.

I'd like to draw your attention to this.  What do you think of it?

When a thread blocks to wait for a mutex, say, it will wake up when a
async is marked for it and run that async.  Then it will go to sleep
again (unless it has acquired the mutex).  Likewise for condition
variables, select and other kind of blocks.

Also, I think we need a single mechanism that can block on multiple
objects.  For that, we should probably extend 'select' to also handle
mutixes, condition variables, thread joins, and maybe other things.

I have made asyncs per-thread in my working copy and they work fine.
I have also added 'current-thread' and 'all-threads' functions, which
I think are useful.

-- 
GPG: D5D4E405 - 2F9B BCCC 8527 692A 04E3  331E FAF8 226A D5D4 E405


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Threads and asyncs

[NIIBE Yutaka]

In threaded applications, we should avoid "asynchronous" signal
handling.  This is some sort of common technique/discipline, I think.

If we do want asynchronous signal handling in threaded applications,
we'll open can of dead-lock worms.  Signal handler will access some
shared data to affect some thread control, which means, need some
mutual exclusion for that.  What if when signal hander will be invoked
asynchronously in the critical region?  Signal handler cannot get the
lock.  That'll be cause of the dead lock(s).

(Usually) In threaded applications, signal is handled synchronously, 
by assigning a dedicated thread for signal handling.  I mean, a thread
like that:
		while (1)
		  {
		    switch (get_signal ()) /* Blocked if none */
		     {
		    case SIGINT:
			sigint_handler ();
			break;
		    case SIGHUP:
			sighup_handler ();
			break;
		    /* ... */
		     }
		  }
-- 


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Threads and asyncs

[Marius Vollmer]

NIIBE Yutaka <gniibe@m17n.org> writes:

> If we do want asynchronous signal handling in threaded applications,
> we'll open can of dead-lock worms.

Asyncronous signals are also a clean way to break up a dead-lock.

-- 
GPG: D5D4E405 - 2F9B BCCC 8527 692A 04E3  331E FAF8 226A D5D4 E405


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Threads and asyncs

[NIIBE Yutaka]

Marius Vollmer wrote:
 > Asyncronous signals are also a clean way to break up a dead-lock.

Well, yup, it's convenient to break up dead-lock by some interruption
scheme.  That's true.  However, I think that it's not UNIX signal and
its signal handler, in general.  Definitely not.

I think that we're talking about Guile language support for UNIX
siganls and threads.  In this case, we need to think about the
semantics of UNIX signals with thread library.  Please refer some
thread programming introduction(s) for UNIX signal.

	http://www.serpentine.com/~bos/threads-faq/
	Bil Lewis and Daniel J. Berg, Multithreaded Programming with Pthread

Or else, looking the implementation such as Python would help.
-- 


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Threads and asyncs

[Lynn Winebarger]

On Monday 02 September 2002 20:48, Lynn Winebarger wrote:
>       As for the rest, I think we should make C functions
> declare themselves as primitives that never call Scheme,
> and "other", that might call eval.  The first could use some
> fixed "scratch" stack space, the others should get a freshly
> allocated stack (whose size they declare through snarfage
> or somesuch).  The interpreter could then analyze the
> scheme code to find regions "between" call/cc's that could
> use some fixed stack.  Call/cc's allocate a fresh Scheme
> stack for the "next" block of code that gets executed.

    I believe I can be clearer on this now.  
    Let's say we're doing some computation on stack A with
frames A1 - A50, recalling that primitives (whether foreign
or internal) have their own "scratch" stack, and non-primitive
foreign functions get a freshly allocated stack; so that A really
contains only frames generated by eval.  Now, let's say we
see a call/cc for the first time at A50, so we allocate another
stack and set its continuation to the top of this one.  Now,
after returning from that call (if/when that happens) any
subsequent stack using calls get their own stack space, with
a continuation into A wherever it left from.  For example,
let's say I returned, and then descended the stack to frame
A40, then called myota (defined in Scheme).  Then a new stack
C (since B was allocated for the first call/cc) gets allocated
with its continuation pointer to A40 (and maybe to A's bottom
to make the GC's job easier).  
  This amounts to lazy allocation of continuations, whereas a 
straightforward implementation where each stack frame is 
freshly allocated will result in lots of garbage, this should result 
in only as much continuation garbage as absolutely necessary.
Call/cc should be reasonably fast,  and current C programs
can be grandfathered in by assuming non-primitivity, and
only a minimal amount of declarative work for those who
want GUILE to know which of their functions are primitives.
Of course, there should also be some way to return unused
space off the top of the stack to the GC.  The garbage collector
could be made to recognize when the top part of the stack
is no longer referenced an can be reused.
     Did that make sense?  Anyone see a hole in it?

Lynn


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Threads and asyncs

[Tom Lord]

       > so that A really contains only frames generated by eval.


Why do you need more than one such frame (on a C stack) per Scheme
thread (without calls out to "non-primitive foreign functions")?

With only one C frame, call/cc can be _really_ fast and I think you
can go in this direction without trashing eval's performance.

But, loosely speaking -- the idea of mixing special stacks for
classical C with stacks just for Scheme seems to me to be a useful
one, and, if the interfaces in Guile are suitably cleaned up, a way to
evolve forward.

It's a drag that the work on Guile debugger support has thwarted
simply dropping in the faster eval from recent SCMs -- but you could
leapfrog over that with a stackless eval.


	 > and current C programs can be grandfathered

One language implementor I met made a big fuss over amdhal's law --
which has the implication for Guile that cleaning up various apis
(internal and external) should be a big priority.

I sort of agree, except that there's a trap there: which is to build
up abstractions for abstraction sake in areas where, really, there are
right and wrong answers, with the right answers requiring less than
fully general abstractions (and, in fact, being somewhat incompatible
with fully general abstractions).  

Sort of.  (Isn't there a better way to map out design spaces than
email threads?  That'd be wikid cool.)


     > Did that make sense?  Anyone see a hole in it?

IM*H*O: nothing major.  Keep going in that direction.   But you're
nearing the frontier between my experience and my speculation, so I'll
shut up now.



bibop,
-t


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Threads and asyncs

[Lynn Winebarger]

On Wednesday 04 September 2002 19:20, Tom Lord wrote:
>        > so that A really contains only frames generated by eval.
> 
> 
> Why do you need more than one such frame (on a C stack) per Scheme
> thread (without calls out to "non-primitive foreign functions")?
> 
> With only one C frame, call/cc can be _really_ fast and I think you
> can go in this direction without trashing eval's performance.

      The problem with this is that it requires really fast garbage collection.
Guile's commitment to conservative collection can present a serious
problem in this regard.   WIth this proposal, continuations that
do not have a reference after the first execution (i.e. no call/cc)
will be "garbage collected" simply by popping the stack.  New
continuations get allocated only and exactly when needed.
   Indeed, I think it can the proposal can be completely characterized
as merely an allocation strategy for heap-allocated stack frames,
and nothing more.  Now that I think about it, I believe it will do strictly 
less work than applying general GC to individual activation records.
(that is, whatever general GC the interpreter is using - I don't make
the claim for this method plus Guile's GC versus unfettered frame
allocation + some other GC; rather this method plus GC versus
unfettered frame allocation plus that same GC).

> But, loosely speaking -- the idea of mixing special stacks for
> classical C with stacks just for Scheme seems to me to be a useful
> one, and, if the interfaces in Guile are suitably cleaned up, a way to
> evolve forward.
> 
> It's a drag that the work on Guile debugger support has thwarted
> simply dropping in the faster eval from recent SCMs -- but you could
> leapfrog over that with a stackless eval.

       Is all the thread hair in SCM as well?

> 	 > and current C programs can be grandfathered
> 
> One language implementor I met made a big fuss over amdhal's law --
> which has the implication for Guile that cleaning up various apis
> (internal and external) should be a big priority.

     Ok, I give up, how do the two relate exactly?

> I sort of agree, except that there's a trap there: which is to build
> up abstractions for abstraction sake in areas where, really, there are
> right and wrong answers, with the right answers requiring less than
> fully general abstractions (and, in fact, being somewhat incompatible
> with fully general abstractions).  

     It's hard to determine the correct answer without knowing
what the question is.

>      > Did that make sense?  Anyone see a hole in it?
> 
> IM*H*O: nothing major.  Keep going in that direction.   But you're
> nearing the frontier between my experience and my speculation, so I'll
> shut up now.

     It's beyond my experience as well, but I think it is correct.  After getting
my MCSI's syntax-case working, I might use it to experiment with this idea.

Lynn
* Is "metacircular scheme interpreter" a common enough phrase (in the scheme
community) to be recognizable as an acronym?


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Threads and asyncs

[Thomas Bushnell, BSG]

Tom Lord <lord@regexps.com> writes:

> And, again, I'm talking a little bit pie-in-the-sky.  Should Guile
> never undertake to change its core away from (for example)
> conservative GC, if it converges on a nice API, then it is simply an
> implementation optimized for that particular API.  #f/() is the only
> irreconcilable issue I know of in this regard.  (Please, tb, spare us
> a rehearsal of jimb's design -- we all either agree with me, know i'm
> wrong, or already know the arguments.  Ok, now, please say something
> argumentive *anyway*.)

What "reconciliation" is needed?  

Who does guile have to reconcile with?


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Threads and asyncs

[Tom Lord]

      > The problem with this is that it requires really fast garbage collection.

Again -- I'll point at the substantial (from vague recollection: 20%?)
speedup SCM got from generationally collecting environments.  The 
common case pattern of how environments are used makes this a really
excellent choice.

There's also Stallman's ancient spaghetti-stack approach -- which is
kinda close to what SCM is doing.

You can view Guile's use of the C stack for eval as a way to trick the
C compiler into doing most of the most-common-case of
spaghetti-stacks.   Then you can ask: is bending over backwards for
that trick *really* worth it?   Screw-it: compilers for C-like
languages *aren't that hard* (in spite of the cultural machismo of the
GCC group).



      > Guile's commitment to conservative collection can present a serious
      > problem in this regard.   

As with calling conventions, I think there is room for a two-level
approach.   Precise GC in the core -- conservative GC for
"non-primitive foreign functions".   In the very long term we can
talk the rest of the world into using some language other than C: in
which case the entire issue may very well simply disappear.

I'm not sure (aside from 1-3 year political reasons) why such care for
C should be so important.  For example, 5 years ago or so, I wrote a
low-level buffer implementation and redisplay algorithm in Guile with
the result being smaller, simpler, more general code, compilable by
hobbit to produce acceptable performance on hardware that was (already
by that time) a bit behind the curve (thank Cygnus-cum-Red-Hat for its
non-release/stalled development).  There is no performance critical
code in Emacs (for example) that couldn't be usefully rewritten in
Scheme.

And, again, I'm talking a little bit pie-in-the-sky.  Should Guile
never undertake to change its core away from (for example)
conservative GC, if it converges on a nice API, then it is simply an
implementation optimized for that particular API.  #f/() is the only
irreconcilable issue I know of in this regard.  (Please, tb, spare us
a rehearsal of jimb's design -- we all either agree with me, know i'm
wrong, or already know the arguments.  Ok, now, please say something
argumentive *anyway*.)

In Emacs-of-the-future, where the "market" for extensions heats up
quite a bit, I think conservative, incremental GC is essential to
robust operation.


       > Now that I think about it [...]

you lost me with the rest of that, in case you want to clarify.


       > Is all the thread hair in SCM as well?

Grr.  We need a wiki to sort that out.  No, I don't (recall that) it's
in SCM -- but then I also think Guile is dead-ending in this regard.

It's freekin hard.   I tend to think of implementations in terms of
some data structures in the heap.   You want those to be really fast.
Any kind of global locking makes them horribly slow.   So, threads
_suck_ for Scheme.

But then on the other hand, it makes sense to put multiple CPUs on a
bus, sharing memory.   So, what is the right abstraction to take
advantage of that?   I keep coming back to the idea that, for multiple
Scheme threads, each thread gets its own separate universe -- no `eq?'
sharing at all.  

But I want a wiki -- it's just intuitive speculation, at this point --
and the issues are large enough that one can easily wind up going in
circles out of shear confusion.




	>> One language implementor I met made a big fuss over amdhal's law --
	>> which has the implication for Guile that cleaning up various apis
	>> (internal and external) should be a big priority.

        > Ok, I give up, how do the two relate exactly?


Am I misunderstanding the referent of "the two"?   amdhal's law talks
about the impact of optimizing components on the performance of a
system that incorporates those components.   Clean APIs can enable
swappable components.

If the FFI/GC-interface don't overdetermine the implementation of
eval, gc, etc....then there's room to change strategies.

If the interfaces are _too_ general, then you can swap components, but
you can never implement the good ones in a reasonable way.

-t



_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Threads and asyncs

[Thomas Bushnell, BSG]

Tom Lord <lord@regexps.com> writes:

> Thank you.

Aw, shucks.  You have an amazing knack to turn any discussion into a
pissing contest.  Ok, you win!  You are better than anyone else at
spraying urine around.

Now, back to the point:

Why do we have to change at all?  You seem to offer continual pressure
and impetus for the notion that guile is *deeply* wrong in its current
trajectory, but you don't seem to be either cooperating in development
or doing more than just arguing for the sake of arguing.

You want guile to be inconsistent with nearly every other Scheme
system out there (even MIT scheme now has #f != ()) for what?  So that
it will be compatible with systas?

Is this whole stupid on-going flame fest of yours merely about some
desire to have the world adopt your favorite system instead of the one
they are already using?  Instead of convincing them, why not just make
systas so much obviously better that people will use it?

Thomas



_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Threads and asyncs

[Tom Lord]

       >> Please, tb, [....] say something
       >> argumentive *anyway*.)

	> What "reconciliation" is needed?  

	> Who does guile have to reconcile with?


Thank you.




-t



_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Threads and asyncs

[Thomas Bushnell, BSG]

Tom Lord <lord@regexps.com> writes:

> p.s.: tb -- i've been wondering for a few years now:  a lot of my
> scheme plans derive from stuff that was "in the air" around the 4th
> floor and MIT generally a while back.   Do you argue with me so
> consistently because you feel I've ripped you off somehow?  I thought
> we were all egoless on this bus.

I argue with you consistently because you use a strategy which is an
irresponsible and unfair debating tactic, and which I will not permit
you to use.  It's called the "Cato" tactic.

Cato ended every speech with "Carthago delenda est" (Carthage must be
destroyed)--whether it was relevant to the speech or not.  Eventually
people stopped disputing it with him, and eventually they started
going along with it just so he wouldn't annoy them further.  And
finally, a costly war ensued.

You use the same strategy.  You have decided that (eq? #t '()) is the
Right Thing--by no means is this the only thing.  You toss in that
claim as often as possible, as frequently as you can, in as many
messages as you can manage to bring it up.  You pretend that this is
harmless, and you think it's tedious and bad for me to object, each
and every time, to it.

You are trying the Cato strategy, and it's not reasonable, and I don't
accept it.  The only way to defeat the Cato strategy is to argue
against the falsehood, each and every time it is brought up.  You'll
note that I do *not* initiate the discussion, each and every time it
has been you who does so.  You do so in the hopes that you can get in
your Cato-like pronouncement without being challenged, and you just
don't get that.

You can choose to debate it if you like, or not, but you don't get to
just toss off the assertion as if it's harmless, in the hope that it
will sink in and we'll do the your thing only because of your dogged
persistence.

You seem to think everything is personal, which pisses me off no end.
I have no idea what you were talking about in Scheme regards in Tech
Sq.  I have generally been singularly unimpressed by your
self-promotional enterprises, though I admit the graphic design of
your web pages is fun.

Thomas




_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Threads and asyncs

[Tom Lord]

       > So that it will be compatible with systas?

No.

I think systas is pretty much a dead end -- but there's a bunch of
useful bits and pieces in there.  A frustrating aspect of systas has
been that, just when I think I've finally killed it, I have some
practical problem to solve for which it is the best available
solution.

A nice property of Guile is that there is _enough_ code using it to
make it attractive to an audience larger than its developers, yet not
_so much_ code that the design or language is carved in stone.

Another nice property is that it has the GNU label, which, in the long
run, I hope stands for technical excellence.


Yours from the "just rumour and here-say" underground....
-t

p.s.: tb -- i've been wondering for a few years now:  a lot of my
scheme plans derive from stuff that was "in the air" around the 4th
floor and MIT generally a while back.   Do you argue with me so
consistently because you feel I've ripped you off somehow?  I thought
we were all egoless on this bus.



_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Threads and asyncs

[Lynn Winebarger]

On Wednesday 04 September 2002 21:38, Tom Lord wrote:
>       > The problem with this is that it requires really fast garbage collection.
> Again -- I'll point at the substantial (from vague recollection: 20%?)
> speedup SCM got from generationally collecting environments.  The 
> common case pattern of how environments are used makes this a really
> excellent choice.
     I believe the ML community has the most history of needing
fast GC to deal with heap-allocated frames.  Appel has several
papers on SML/NJ's GC and dealing with this design decision.
     I haven't read them, of course, but they seem like the
canonical starting place.

> There's also Stallman's ancient spaghetti-stack approach -- which is
> kinda close to what SCM is doing.

      I'm not familiar with this spaghetti stack.  

>        > Now that I think about it [...]
> 
> you lost me with the rest of that, in case you want to clarify.

       Ok.  Stack based function calling is a particular allocation
strategy for activation records.  It's simple and reasonably quick.
In C,  you don't have grabbable continuations (at least not 
supported by the language), so when the function returns,
the only valid reference to the activation record is dropped,
and that activation record's memory is reclaimed by popping
the stack.  
    In Scheme, you can grab continuations, of course,
so as long as there's an external reference to an activation 
record/continuation, the stack cannot be popped.  However,
the only way such a reference can be (legally) created is
by call/cc.  Unless that is called, we know we are safe
"collecting" that activation record by popping the stack.  On
the other hand if we know there is a possible reference to
a continuation that's higher on the stack, we haven't collected
those frames, so we must freshly allocate new space for
activation records.  Now, you may occasionally create
stacks unnecessarily (e.g. the continuation was used only
for escaping, and there's no other way to get into the
lambda of the (call/cc (lambda (k) ...))); however, we will
never invalidly collect it either.  Instead, the garbage collector
will have the responsibility of seeing when that frame isn't
reachable.  
     In the straightforward, always allocate from the heap
model, the GC is always responsible for collecting activation
records.  In this model, we explicitly handle a very common
case, so the GC doesn't have to.  Otherwise, the GC handles
it, as it would have anyway.  Thus we have strictly improved
the speed (because popping the stack is about the
fastest deallocation anybody will ever have, other than exiting,
of course).
      Better?

>        > Is all the thread hair in SCM as well?
> 
> Grr.  We need a wiki to sort that out.  No, I don't (recall that) it's
> in SCM -- but then I also think Guile is dead-ending in this regard.

    I don't think anybody's found the grail yet.  
   
> Am I misunderstanding the referent of "the two"?   amdhal's law talks
> about the impact of optimizing components on the performance of a
> system that incorporates those components.   Clean APIs can enable
> swappable components.

       Sorry, the last time I heard a reference to Amdhal's law was
in a hardware course three years ago.  I looked it up on FOLDOC
and it gave a definition referring to the maximum speedup 
of parallelization (which is why I didn't see the connection).  I just 
went back to Hennessy and Patterson and they give the right definition.

Lynn


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Threads and asyncs

[Tom Lord]

       > You use the same strategy.  You have decided that (eq? #t '()) is the
       > Right Thing

Only because I have written a lot of code, from both perspetives.

I am not debating, when I post here.   More like: "reporting".


	> You seem to think everything is personal, 

I do not.

	> which pisses me
	> off no end.

I'm sorry.


	> I have no idea what you were talking about in Scheme regards
	> in Tech Sq.

Revok(? was that how it was spelled?  it's somewhere on google) stems
from the same roots, for example.  I wonder if I still have, on some
backup tape or other, the Scheme impl. sketches that the
near-to-FSF-community shared, back then.  I suppose I am blessed with
a very detailed memory of some events.

	> I admit the graphic design of your web pages is fun.

Thank you again.  I credit mostly Scott Draves' computationational
art, which I mostly tried to set against a complementary color scheme
and not distract from with too much text.   Plus, I outright stole a
three-word poetic form that he initiated at CMU.....


Uh.... why is this on guile-devel?  Sorry folks -- having put tb's and
my interactions in a hopefully more favorable light, I'll take the
non-technical foo off-list now.


-t


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Threads and asyncs

[Thomas Bushnell, BSG]

Tom Lord <lord@regexps.com> writes:

>        > In C,  you don't have grabbable continuations 
> 
> or closures.  Though, sure, closures don't capture entire activation
> records.

In GNU C, you can create closures, albeit, ones only with dynamic
extent.  (This was a necessary feature to support Pascal, so it seemed
appropriate to add the necessary extension to support it in C as
well.)  



_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Threads and asyncs

[Tom Lord]

       > In C,  you don't have grabbable continuations 

or closures.  Though, sure, closures don't capture entire activation
records.



	> In the straightforward, always allocate from the heap
	> model, the GC is always responsible for collecting activation
	> records.  

Right -- but, as SCM illustrates or points-towards, you can still
treat them specially.


      > Thus we have strictly improved the speed (because popping the
      > stack is about the fastest deallocation anybody will ever
      > have, other than exiting, of course).

Spaghetti stacks speak to this issue.


      > Better?

Totally clear.

-t




_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Threads and asyncs

[Tom Lord]

       > Spaghetti stacks speak to this issue.

Ugh....

On second thought -- i think they might have been called "phantom
stacks".


-t




_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel

Re: Threads and asyncs

[Lynn Winebarger]

On Wednesday 04 September 2002 23:01, Tom Lord wrote:
>        > Spaghetti stacks speak to this issue.
> 
> Ugh....
> 
> On second thought -- i think they might have been called "phantom
> stacks".

     You were right the first time.  I haven't read these completely yet.

Bobrow & Wegbreit 1973
http://portal.acm.org/citation.cfm?id=362379&dl=ACM&coll=portal&CFID=4248345&CFTOKEN=47013179

Steele's "Macaroni Stacks"
http://portal.acm.org/citation.cfm?id=806933&dl=ACM&coll=portal
Of course, Steele was doing a lot more code analysis than Guile
is currently (or probably will anytime soon).  

Lynn


_______________________________________________
Guile-devel mailing list
Guile-devel@gnu.org
http://mail.gnu.org/mailman/listinfo/guile-devel