I am constantly frustrated by the lack of good concurrency abstractions
available in most Common Lisp implementations. Rather than be a whiner I
have tried to roll my own-- at least as an exercise.
I started with a small functional interpreter and added preemptive threads
and asynchronous channels. I've developed some of those ideas in a
multi-threaded lisp (sbcl). However, as nice as it is to have os-level
threads at my disposal, I would like something a little more light weight.
The problem is I can't seem to wrap my brain around preemptive threads (or
fibers, or whatever the kids are calling it these days) as a _user_
program (as opposed to threads as a language primitive).
Do I need to but the bullet and learn how to write a CPS transformer, and
implement a thread scheduler with full orchestra and choir.
Would it be simpler to iteratively expand my interpreter to handle more
actual Common Lisp (instead of the elementary school lambda calculus I got
going)?
How do other people handle multi-processing tasks in single threaded lisps?
Note: Scheme implementations seem to be sick with language-level threads.
How come no thread love for Common Lisp?
Anyway, suggestions welcome.
Matt
--
"You do not really understand something unless you can
explain it to your grandmother." — Albert Einstein.
Matthew D Swank wrote:
> The problem is I can't seem to wrap my brain around preemptive threads (or
> fibers, or whatever the kids are calling it these days) as a _user_
> program (as opposed to threads as a language primitive).
I think you can't really implement fully preemptive threads in
user-space. The BSDs are or were using a concept called Scheduler
Activations (SA), which is basically user-threads but with regular
interrupts (kind of) sent to the process, so the user-level scheduler
can preempt threads. It doesn't seem to be faster than Linux's threads
(which are full kernel-level threads), but Linux is more optimized in
its core algorithms I think, so maybe that's not a fault of the SA model.
An alternative (though maybe not too efficient) are engines. You feed
them a number of ticks, and after having consumed those ticks they
return to the scheduler. Not sure if there are other implementation
possibilities than loop-with-decrement (especially non-invasive ones,
that could run arbitrary user-code without needing to modify it to
integrate with the loop).
Maybe you can take some inspiration out of Friedman, Wand, Ganz's
Trampolined Style paper.
--
We're glad that graduates already know Java,
so we only have to teach them how to program.
somewhere in a German company
(credit to M. Felleisen and M. Sperber)
On Sat, 01 Oct 2005 13:57:17 +0200, Ulrich Hobelmann wrote:
> Maybe you can take some inspiration out of Friedman, Wand, Ganz's
> Trampolined Style paper.
Thanks for the reference. The trampoline architectures presented in the
paper are similar to what I was calling a thread monad. In fact
trampoline style seems very similar to using a monad. I was really writing
a trampolined interpreter!
For example, instead of "doing" and "done" as states, I had:
(def-datatype (thread monad)
(halted (val expression))
(running (thunk function))
(receiving (chan channel)
(cont function))
(sending (thunk function)
(chan channel)
(message thread))
(thread-pair (thread1 thread)
(thread2 thread)))*
Matt
*def-datatype is a modest implementation of plai's define-datatype in CLOS
--
"You do not really understand something unless you can
explain it to your grandmother." — Albert Einstein.
On Sat, 01 Oct 2005 13:57:17 +0200, Ulrich Hobelmann wrote:
> Maybe you can take some inspiration out of Friedman, Wand, Ganz's
> Trampolined Style paper.
The key insight for me in the paper (as far as overlaying threads on an
existing language) was:
Just as CPS makes the continuation visible during computation,
trampolining makes the thread queue visible.
...
Given any interpreter in tail form, we can trampoline it and add
our new operators to a source language so that they can be used
without trampolined style. The procedures that gain the power of
multitasking by extending the trampolined style in controlled ways
then _correspond to clauses of the interpreter which do the same_.
So the machinery is already there in the interpreter. We just turn an
interpretation of an expression running _on_ lisp into a compilation of an
expression _into_ lisp: a shift from eval to defmacro.
I know this is, for most experienced lisp users, obvious. However, lisp
is one of the few languages that makes the transition from interpreter to
compiler possible, even commonplace. The concept still hits me like
baseball bat to the head every now and then (usually when I least expect
it).
Matt
--
"You do not really understand something unless you can
explain it to your grandmother." — Albert Einstein.
On Sat, 01 Oct 2005 06:11:07 -0500, Matthew D Swank wrote:
> Anyway, suggestions welcome.
Well, obviously green threads aren't as interesting as "A Moronicity of
Guido van Rossum" or "Hi, I'm Jon Harrop", but I was expecting more than
one post (thanks Ulrich).
Still, I am puzzled by a lack of light weight concurrency in Common Lisp
implementations. Does scheme's provision of first class continuations
make it a more attractive prospect in that language? Is it an itch
that most CL'ers don't need to scratch?
Context switching using Linux threads seems snappy enough, but for the
kind of abstractions provided by CSP, Actor languages, or Join Calculi (my
current personal obsession), OS threads still seem too heavy.
Erlisp is a step in the right direction, but is dependent on existing
thread implementations. Also, the project seems stalled.
"So if it's so bad, do something about it" I hear no one say.
Well I am trying, but it's slow going. Also, I post here as an informal
measure of community interest and expertise.
Matt
--
"You do not really understand something unless you can
explain it to your grandmother." — Albert Einstein.
Of course you could also avoid threads completely and go with something
like event loops instead. Checked out Twisted framework for Python, for
example. Or the E language at www.erights.org.
James Graves
On Mon, 03 Oct 2005 01:09:09 +0000, James Graves wrote:
> Of course you could also avoid threads completely and go with something
> like event loops instead. Checked out Twisted framework for Python, for
> example. Or the E language at www.erights.org.
>
> James Graves
Yes, I believe this is also the slime/swank approach on single threaded
lisps. I didn't realize E also used an event loop.
I realize event loops and threads provide similar functionality, but they
impose different conceptual models. Processes and channels seem more
functional, while event-loops make the state machine more explicit (and,
for some reason, harder for me to reason about :)
Matt
--
"You do not really understand something unless you can
explain it to your grandmother." — Albert Einstein.
Have you read "on lisp"? Somewhere in there he implements continuations
in common lisp, and then uses them to create threads. It's slightly
clunky though, and probably very slow, but it might be worth a look
On Mon, 03 Oct 2005 02:11:03 -0700, ··············@gmail.com wrote:
> Have you read "on lisp"? Somewhere in there he implements continuations
> in common lisp, and then uses them to create threads. It's slightly
> clunky though, and probably very slow, but it might be worth a look
I've read a little of it. The tricky bit for me (w/respect to CPS,
Trampolines, Monads, etc.) is getting the transformation macros right.
Common Lisp seems more complicated in the regard than scheme.
I noticed arnesi went from using macros to provide first class
continuations to using an interpreter.
Matt
--
"You do not really understand something unless you can
explain it to your grandmother." — Albert Einstein.
On Mon, 03 Oct 2005 05:07:00 -0500, Matthew D Swank wrote:
> I noticed arnesi went from using macros to provide first class
> continuations to using an interpreter.
>
I realize this is a mischaracterization on my part, but they do use a
custom interpreter instead of the underlying lisp. Though this may be do,
in part, to a desire to serialize continuations.
Matt
--
"You do not really understand something unless you can
explain it to your grandmother." — Albert Einstein.
Matthew D Swank <·······································@c.net> writes:
> On Mon, 03 Oct 2005 02:11:03 -0700, ··············@gmail.com wrote:
>
> > Have you read "on lisp"? Somewhere in there he implements continuations
> > in common lisp, and then uses them to create threads. It's slightly
> > clunky though, and probably very slow, but it might be worth a look
>
> I've read a little of it. The tricky bit for me (w/respect to CPS,
> Trampolines, Monads, etc.) is getting the transformation macros right.
> Common Lisp seems more complicated in the regard than scheme.
A couple days ago I was extending a toy cps-transforming CL-to-CL
compiler that I wrote to handle all the CL special operators. Parts
of it read like a Scheme textbook -- which makes sense, because Scheme
tries to give you a tiny language that's sufficiently powerful to
build any advanced control structures you might need on your own. CL
pushes more of that onto the implementor, not the user. So, when you
find yourself with an implementor's hat on, a lot of the simplicity
you gain as a user (eg, unwind-protect), comes back as complexity in
implementation.
That said, it was a fun sort of puzzle challenge, but nothing turned
out to be that difficult. Here's a hint, though: my life was a lot
easier because I kept three things passed along in the lexical
environment: in addition to the continuation, I pass the dynamic stack
and the unwind continuation.
--
/|_ .-----------------------.
,' .\ / | Free Mumia Abu-Jamal! |
,--' _,' | Abolish the racist |
/ / | death penalty! |
( -. | `-----------------------'
| ) |
(`-. '--.)
`. )----'
On Mon, 03 Oct 2005 11:21:13 -0700, Thomas F. Burdick wrote:
> Here's a hint, though: my life was a lot
> easier because I kept three things passed along in the lexical
> environment: in addition to the continuation, I pass the dynamic stack
> and the unwind continuation.
How do you handle call/cc in the presence of unwind-protect?
Matt
--
"You do not really understand something unless you can
explain it to your grandmother." — Albert Einstein.
Matthew D Swank <·······································@c.net> writes:
> On Mon, 03 Oct 2005 11:21:13 -0700, Thomas F. Burdick wrote:
>
>
> > Here's a hint, though: my life was a lot
> > easier because I kept three things passed along in the lexical
> > environment: in addition to the continuation, I pass the dynamic stack
> > and the unwind continuation.
>
> How do you handle call/cc in the presence of unwind-protect?
I think the question makes more sense the other way around: how does
unwind-protect work with continuations? With all the code CPS
transformed, the easiest way to implement it was to have
unwind-protect evaluate the cleanup forms every time control unwinds
through it. That means that you can't unwind through with-open-file
more than once without getting an error, but I don't see how you could
expect to. All I did was CPS transform CL, not design a new CL-ish
Lisp that has continuations integrated seamlessly into it. It
probably makes sense to also have dynamic-wind, and an unwind-protect
variant that makes it easy to control the number of winds that go
through it, but that won't change the fact that you need to write your
code carefully if you want it to be safe to invoke its continuation
more than once -- and ordinary Common Lisp is not written defensively
with regards to continuations.
--
/|_ .-----------------------.
,' .\ / | Free Mumia Abu-Jamal! |
,--' _,' | Abolish the racist |
/ / | death penalty! |
( -. | `-----------------------'
| ) |
(`-. '--.)
`. )----'
Matthew D Swank wrote:
> Yes, I believe this is also the slime/swank approach on single threaded
> lisps. I didn't realize E also used an event loop.
(Disclaimer: current E written-program count: zero.)
E uses promises at the language level; event loops are an
implementation strategy. The user writes handlers for delayed values
(or just waits till they appear), but the event processing itself is
abstract, there's no explicit select() call or file descriptor activity
dispatch.
Does anyone have a good reference to a comparison of promises/futures
and Erlang/message-passing/CSP? I wasn't sure that CSP's
"segmentation" of a computation over different input dispatches was how
I thought about concurrent programs, so I implemented a toy promise
library to try and understand what it would feel like to program using
promises. I never finished it, though, so I'd love to read a
comparison. Thanks!
"Tony Martinez" <························@gmail.com> writes:
> Does anyone have a good reference to a comparison of promises/futures
> and Erlang/message-passing/CSP?
They serve somewhat different purposes, in my mind. If you have an
explicitly concurrent algorithm, message passing seems a better fit
(or, if you're unlucky, shared state). Futures, on the other hand, are
handy when you want to exploit (implicit) parallelism with a minimum
of fuss. I might want both, at least when pretending to be a power user.
Best,
Thomas
--
Thomas Lindgren
"It's becoming popular? It must be in decline." -- Isaiah Berlin
Tony Martínez wrote:
> Does anyone have a good reference to a comparison of promises/futures
> and Erlang/message-passing/CSP?
I'm not sure whether it has promises/futures in it, but you could try
CTM, Concepts Techniques and Models of Computer Programming by Van Roy
and Haridi.
http://c2.com/cgi/wiki?ConceptsTechniquesAndModelsOfComputerProgramming
I have found it very good to learn about dataflow, message-passing, and
explicit state concurrency. I do wish it used Lisp rather than Oz
though.