So I've noticed a large amount of new Erlang articles popping up. The
only innovation is that they've added microthreads + message passing.
That got me thinking. What is message passing...?
>From Erlang's point of view, message passing is a mechanism to avoid
having to lock resources, by copying data instead of copying pointers
to data. The message passing paradigm seems to be the most damning and
most encouraging piece of innovation in Erlang. The problem is that
message passing means that to pass a large data structure like a tree
from one thread to another, you have to break it down into tiny pieces,
and send the pieces through messages, and then the other thread will
receive those messages and reconstruct the tree. The encouraging part
is that since the other thread has to deal with a lossy connection, the
messages contain metadata that help describe their relationships with
other messages. So, at the end of the tree copy from one thread to
another, you'd end up with two identical trees, but moreover, you'd
have the metadata available to mirror additional changes on one tree on
the other. Woo!
However, I can't help feeling like this is overkill. A purely
functional language can also be easily multithreaded, because all data
is immutable, which is a nice property. In fact, in some ways, message
passing feels like a mix of about 33% functional (data is immutable
across threads) and about 66% procedural, since a thread is happily
crunching away on its own personal data, presumably in a procedural
manner. [correct me if I'm wrong, I'm no Erlang expert]
So it seems that in Lisp, you can mostly avoid locking issues, except
when combining the results from different threads. It may not have
microthreads, but that's not a big issue if your number of threads is
only about 2X # of cpu's in a computer. Are any actual Lisp
implementations up to the job?
1) I've always heard that there was no common multithreading interface
for Lisp. True? Not true? An unofficial one that everyone is always
using?
2) If I have a quad core computer, what, if any computations can the
other 3 processors perform while the garbage collector is working? Do
any implementations have GC's that somehow can work while another
thread is simulataneously accessing data?
-pTymN
"pTymN" <·········@gmail.com> writes:
> So I've noticed a large amount of new Erlang articles popping up. The
> only innovation is that they've added microthreads + message passing.
> That got me thinking. What is message passing...?
>
> >From Erlang's point of view, message passing is a mechanism to avoid
> having to lock resources, by copying data instead of copying pointers
> to data. The message passing paradigm seems to be the most damning and
> most encouraging piece of innovation in Erlang. The problem is that
> message passing means that to pass a large data structure like a tree
> from one thread to another, you have to break it down into tiny pieces,
> and send the pieces through messages, and then the other thread will
> receive those messages and reconstruct the tree.
There is no need to split up the data -- you can send arbitrary terms in
a message like this:
Recipient ! Tree
or Recipient ! {node, key1, val1, {node, key2, val2, leaf, leaf}, leaf}
and the recipient process can then receive the message as, e.g.:
receive
Tree -> ...
end
(Here, Tree and Recipient are variables, but in general you'd use
pattern matching to select messages.) Terms are immutable, however, so
the logical operation of message passing can be implemented by copying
or pointer-passing. Either approach has been tried.
Interestingly, Erlang-as-it-is-used often _also_ employs a simple form
of shared state, namely ets/dets/mnesia tables (the latter with
transactions). The verdict thus seems to be that pure message passing
isn't quite flexible enough.
Finally, I'd say Erlang is not necessarily wildly innovative, but it
fits together into a really nice, practical, easy-to-learn solution
for writing concurrent, fault tolerant, soft real-time, distributed
systems.
Best,
Thomas
--
Thomas Lindgren
"pTymN" <·········@gmail.com> writes:
> 1) I've always heard that there was no common multithreading interface
> for Lisp. True? Not true? An unofficial one that everyone is always
> using?
(asdf-install:install :bordeaux-threads)
(asdf:oos 'asdf:load-op :bordeaux-threads)
(use-package :bordeaux-threads)
> 2) If I have a quad core computer, what, if any computations can the
> other 3 processors perform while the garbage collector is working? Do
> any implementations have GC's that somehow can work while another
> thread is simulataneously accessing data?
AFAIK, no (free) implementation has such a "parallel" garbage collector.
--
__Pascal Bourguignon__ http://www.informatimago.com/
"Specifications are for the weak and timid!"
"pTymN" <·········@gmail.com> writes:
>> AFAIK, no (free) implementation has such a "parallel" garbage collector.
>
> What about Allegro CL or Lispworks?
They're not free.
When I write free, read freedom.
When I write gratis, read $0.
I know very little of commercial implementations.
--
__Pascal Bourguignon__ http://www.informatimago.com/
Pour moi, la grande question n'a jamais �t�: �Qui suis-je? O� vais-je?�
comme l'a formul� si adroitement notre ami Pascal, mais plut�t:
�Comment vais-je m'en tirer?� -- Jean Yanne
On 2006-08-18 09:58:45 +0100, Pascal Bourguignon <···@informatimago.com> said:
> "pTymN" <·········@gmail.com> writes:
>
>>> AFAIK, no (free) implementation has such a "parallel" garbage collector.
>>
>> What about Allegro CL or Lispworks?
>
> They're not free. When I write free, read freedom. When I write
> gratis, read $0.
It might be revealing to start drawing some kind of matrix
. gratis for cost
."free" (1) (2)
.
.in-jail (3) (4)
(1) I guess we could list SBCL, OpemMCL, ...
(2) ???
(3) LW PE, Allegro "Eval"
(4) As for (3) but the paying version?
Obviously, now, we become interested in spotting
anything in category (2)
Or is it empty, as far as CL implementations go?
Which would render the distinction between "free" and "gratis"
rather moot, don't you think?
--
JFB
pTymN wrote:
> So I've noticed a large amount of new Erlang articles popping up. The
> only innovation is that they've added microthreads + message passing.
*****************
> That got me thinking. What is message passing...?
Not true - the error recovery mechanisms are central to the language
design.
The concepts of links, and the exact semantics of how process groups
fail is unique to Erlang.
Then there are things like changing code "on the fly" so you can work
with old and
new copies of the code at the same time ...
>
> >From Erlang's point of view, message passing is a mechanism to avoid
> having to lock resources, by copying data instead of copying pointers
> to data. The message passing paradigm seems to be the most damning and
> most encouraging piece of innovation in Erlang. The problem is that
> message passing means that to pass a large data structure like a tree
> from one thread to another, you have to break it down into tiny pieces,
> and send the pieces through messages, and then the other thread will
> receive those messages and reconstruct the tree.
No, in Erlang you send the tree (or any data structure) in one
operation
The sender does
Pid ! Tree
The receiver says
receive
Tree -> ...
end,
> The encouraging part
> is that since the other thread has to deal with a lossy connection, the
> messages contain metadata that help describe their relationships with
> other messages. So, at the end of the tree copy from one thread to
> another, you'd end up with two identical trees, but moreover, you'd
> have the metadata available to mirror additional changes on one tree on
> the other. Woo!
>
> However, I can't help feeling like this is overkill. A purely
> functional language can also be easily multithreaded, because all data
> is immutable, which is a nice property. In fact, in some ways, message
> passing feels like a mix of about 33% functional (data is immutable
> across threads) and about 66% procedural, since a thread is happily
> crunching away on its own personal data, presumably in a procedural
> manner. [correct me if I'm wrong, I'm no Erlang expert]
Well the big gain of copying comes from the independence of the copies.
When means on a multi-core CPU all the CPUs can happily work on their
copying without worring about locks
Incidently, to make a fault tolerent system you need at least two
computers
(think about it :-) - and you need to copy all the data you need for
recovery purposes
so rather than thinking out what to copy you might as well copy
everything -
this increase concurrency, redundance etc. and is easy to understand
/Joe Armstrong
>
> So it seems that in Lisp, you can mostly avoid locking issues, except
> when combining the results from different threads. It may not have
> microthreads, but that's not a big issue if your number of threads is
> only about 2X # of cpu's in a computer. Are any actual Lisp
> implementations up to the job?
>
> 1) I've always heard that there was no common multithreading interface
> for Lisp. True? Not true? An unofficial one that everyone is always
> using?
>
> 2) If I have a quad core computer, what, if any computations can the
> other 3 processors perform while the garbage collector is working? Do
> any implementations have GC's that somehow can work while another
> thread is simulataneously accessing data?
>
> -pTymN
>>>>> "joe" == joearms <·······@gmail.com> writes:
joe> Then there are things like changing code "on the fly" so you can
joe> work with old and new copies of the code at the same time ...
A neat feature indeed, but is this unique to Erlang?
The granularity may be, but in lisp you certainly also can replace
functions with new versions in a running program, even though you
probably will not be able to replace the currently running version of
an executing function, as I have heard Erlang is able to do.
------------------------+-----------------------------------------------------
Christian Lynbech | christian ··@ defun #\. dk
------------------------+-----------------------------------------------------
Hit the philistines three times over the head with the Elisp reference manual.
- ·······@hal.com (Michael A. Petonic)
Christian Lynbech wrote:
> >>>>> "joe" == joearms <·······@gmail.com> writes:
>
> joe> Then there are things like changing code "on the fly" so you can
> joe> work with old and new copies of the code at the same time ...
>
> A neat feature indeed, but is this unique to Erlang?
>
Erlang can hot-swap code in clustered PCs.
> The granularity may be, but in lisp you certainly also can replace
> functions with new versions in a running program, even though you
> probably will not be able to replace the currently running version of
> an executing function, as I have heard Erlang is able to do.
>
Erlang can not replace the function that is being execute, either. But
as soon as the next function call is made, it will be made to the new
version. I think this is the same with Common Lisp.
>
> ------------------------+-----------------------------------------------------
> Christian Lynbech | christian ··@ defun #\. dk
> ------------------------+-----------------------------------------------------
> Hit the philistines three times over the head with the Elisp reference manual.
> - ·······@hal.com (Michael A. Petonic)
From: Pascal Costanza
Subject: Re: Erlang brings up interesting questions about Lisp
Date:
Message-ID: <4l2qjoFeb7nlU1@individual.net>
Pisin Bootvong wrote:
>
>> The granularity may be, but in lisp you certainly also can replace
>> functions with new versions in a running program, even though you
>> probably will not be able to replace the currently running version of
>> an executing function, as I have heard Erlang is able to do.
>>
>
> Erlang can not replace the function that is being execute, either. But
> as soon as the next function call is made, it will be made to the new
> version. I think this is the same with Common Lisp.
>
ANSI Common Lisp doesn't seem to specify anything in this regard, so
this is probably implementation-dependent.
I am not aware of a lot of systems where a currently executing function
can be replaced with a new definition and that new definition
immediately takes effect, but it's certainly not impossible.
Pascal
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
From: Marcin 'Qrczak' Kowalczyk
Subject: Re: Erlang brings up interesting questions about Lisp
Date:
Message-ID: <871wr6w6db.fsf@qrnik.zagroda>
Pascal Costanza <··@p-cos.net> writes:
> I am not aware of a lot of systems where a currently executing
> function can be replaced with a new definition and that new definition
> immediately takes effect, but it's certainly not impossible.
I don't think there can be a sane semantics of that.
(defun f ()
(+ (g1) (g2) (g3) (g4)))
Now let's say that g2 changes the definition of f to this:
(defun f ()
(+ (g5) (g6)))
What happens when g2 returns?
--
__("< Marcin Kowalczyk
\__/ ······@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
From: Pascal Bourguignon
Subject: Re: Erlang brings up interesting questions about Lisp
Date:
Message-ID: <877j0y2j7l.fsf@informatimago.com>
Marcin 'Qrczak' Kowalczyk <······@knm.org.pl> writes:
> Pascal Costanza <··@p-cos.net> writes:
>
>> I am not aware of a lot of systems where a currently executing
>> function can be replaced with a new definition and that new definition
>> immediately takes effect, but it's certainly not impossible.
>
> I don't think there can be a sane semantics of that.
>
> (defun f ()
> (+ (g1) (g2) (g3) (g4)))
>
> Now let's say that g2 changes the definition of f to this:
>
> (defun f ()
> (+ (g5) (g6)))
>
> What happens when g2 returns?
Nothing. That is, before calling g2 you have this situation:
(symbol-function 'f) = (lambda () (+ (g1) (g2) (g3) (g4)))
stack = ( (result of (g1)) (return after (f)) )
pc: = ((g2) (g3) (g4) + value1 return )
after g2, you have this situation:
(symbol-function 'f) = (lambda () (+ (g5) (g6))
stack = ( (result of (g2)) (result of (g1)) (return after (f)) )
pc: = ( (g3) (g4) + value1 return )
g3 and g4 are called the four number summed and returned.
Next time f is called, the new function will be executed.
--
__Pascal Bourguignon__
Pascal Bourguignon wrote:
> Marcin 'Qrczak' Kowalczyk <······@knm.org.pl> writes:
>
> > Pascal Costanza <··@p-cos.net> writes:
> >
> >> I am not aware of a lot of systems where a currently executing
> >> function can be replaced with a new definition and that new definition
> >> immediately takes effect, but it's certainly not impossible.
> >
> > I don't think there can be a sane semantics of that.
> >
> > (defun f ()
> > (+ (g1) (g2) (g3) (g4)))
> >
> > Now let's say that g2 changes the definition of f to this:
> >
> > (defun f ()
> > (+ (g5) (g6)))
> >
> > What happens when g2 returns?
>
> Nothing. That is, before calling g2 you have this situation:
>
> (symbol-function 'f) = (lambda () (+ (g1) (g2) (g3) (g4)))
> stack = ( (result of (g1)) (return after (f)) )
> pc: = ((g2) (g3) (g4) + value1 return )
>
>
> after g2, you have this situation:
>
> (symbol-function 'f) = (lambda () (+ (g5) (g6))
> stack = ( (result of (g2)) (result of (g1)) (return after (f)) )
> pc: = ( (g3) (g4) + value1 return )
>
>
> g3 and g4 are called the four number summed and returned.
> Next time f is called, the new function will be executed.
As semantics that makes sense. But the new function definition does
not take effect immediately, which was the context of the original
problem.
From: Pascal Bourguignon
Subject: Re: Erlang brings up interesting questions about Lisp
Date:
Message-ID: <873bbm2ion.fsf@informatimago.com>
"Rob Thorpe" <·············@antenova.com> writes:
> Pascal Bourguignon wrote:
>> Marcin 'Qrczak' Kowalczyk <······@knm.org.pl> writes:
>>
>> > Pascal Costanza <··@p-cos.net> writes:
>> >
>> >> I am not aware of a lot of systems where a currently executing
>> >> function can be replaced with a new definition and that new definition
>> >> immediately takes effect, but it's certainly not impossible.
>> >
>> > I don't think there can be a sane semantics of that.
>> >
>> > (defun f ()
>> > (+ (g1) (g2) (g3) (g4)))
>> >
>> > Now let's say that g2 changes the definition of f to this:
>> >
>> > (defun f ()
>> > (+ (g5) (g6)))
>> >
>> > What happens when g2 returns?
>>
>> Nothing. That is, before calling g2 you have this situation:
>>
>> (symbol-function 'f) = (lambda () (+ (g1) (g2) (g3) (g4)))
>> stack = ( (result of (g1)) (return after (f)) )
>> pc: = ((g2) (g3) (g4) + value1 return )
>>
>>
>> after g2, you have this situation:
>>
>> (symbol-function 'f) = (lambda () (+ (g5) (g6))
>> stack = ( (result of (g2)) (result of (g1)) (return after (f)) )
>> pc: = ( (g3) (g4) + value1 return )
>>
>>
>> g3 and g4 are called the four number summed and returned.
>> Next time f is called, the new function will be executed.
>
> As semantics that makes sense. But the new function definition does
> not take effect immediately, which was the context of the original
> problem.
Define "immediately". In lisp, it takes effect immediately:
(defun g1 () 1)
(defun g2 () (setf (symbol-function 'f) (lambda (x) 100)) 2)
(defun g3 () 3)
(defun g4 () 4)
(defun f (x)
(if (= x 0)
1
(+ (g1) (g2) (f (- x 1)) (g4))))
(f 2) --> 107
Even if you use it immediately in g2:
(defun f (x)
(if (= x 0)
1
(+ (g1) (g2) (f (- x 1)) (g4))))
(defun g2 () (setf (symbol-function 'f) (lambda (x) 100)) (f 0))
(g2) --> 100
--
__Pascal Bourguignon__
Pascal Bourguignon wrote:
> "Rob Thorpe" <·············@antenova.com> writes:
>
> > Pascal Bourguignon wrote:
> >> Marcin 'Qrczak' Kowalczyk <······@knm.org.pl> writes:
> >>
> >> > Pascal Costanza <··@p-cos.net> writes:
> >> >
> >> >> I am not aware of a lot of systems where a currently executing
> >> >> function can be replaced with a new definition and that new definition
> >> >> immediately takes effect, but it's certainly not impossible.
> >> >
> >> > I don't think there can be a sane semantics of that.
> >> >
> >> > (defun f ()
> >> > (+ (g1) (g2) (g3) (g4)))
> >> >
> >> > Now let's say that g2 changes the definition of f to this:
> >> >
> >> > (defun f ()
> >> > (+ (g5) (g6)))
> >> >
> >> > What happens when g2 returns?
> >>
> >> Nothing. That is, before calling g2 you have this situation:
> >>
> >> (symbol-function 'f) = (lambda () (+ (g1) (g2) (g3) (g4)))
> >> stack = ( (result of (g1)) (return after (f)) )
> >> pc: = ((g2) (g3) (g4) + value1 return )
> >>
> >>
> >> after g2, you have this situation:
> >>
> >> (symbol-function 'f) = (lambda () (+ (g5) (g6))
> >> stack = ( (result of (g2)) (result of (g1)) (return after (f)) )
> >> pc: = ( (g3) (g4) + value1 return )
> >>
> >>
> >> g3 and g4 are called the four number summed and returned.
> >> Next time f is called, the new function will be executed.
> >
> > As semantics that makes sense. But the new function definition does
> > not take effect immediately, which was the context of the original
> > problem.
>
> Define "immediately". In lisp, it takes effect immediately:
>
> (defun g1 () 1)
> (defun g2 () (setf (symbol-function 'f) (lambda (x) 100)) 2)
> (defun g3 () 3)
> (defun g4 () 4)
>
> (defun f (x)
> (if (= x 0)
> 1
> (+ (g1) (g2) (f (- x 1)) (g4))))
>
> (f 2) --> 107
>
>
> Even if you use it immediately in g2:
>
> (defun f (x)
> (if (= x 0)
> 1
> (+ (g1) (g2) (f (- x 1)) (g4))))
> (defun g2 () (setf (symbol-function 'f) (lambda (x) 100)) (f 0))
> (g2) --> 100
>
> --
I define "immediately" as "effect current function call".
So really immediate-effect hot swap code would looks like this
(defun f(x)
(format t "x is ~a~%" x)
(setf (symbol-function 'f)
(lambda (x)
(format t "x is ~a~%" x)
(format t "new code: x is ~a~%" x))))
And running (f 10) *might* result in
x is 10
new code: x is 10
I said "might" because it really doesn't look like sound semantic. But
that's why I think effecting the function immediately doesn't make
sense.
Your examples looks like it effects the *next* invocation of 'f
immediately, but not the *current* invocation of 'f immediately.
I think this is what "immediately" means, for example, if you redefine
CLOS class to have new slot, all *current* instance of the class
immediately get the new slot (even if they may be unbounded). You
don't have wait until the *next* make-instance to get instance with new
defined slot. (disclaimer: I tried this with CLISP, and it looks like
all instances get new updated slot, but may be it's not ANSI defined
behavior).
I am not aware of any programming language that can make hot swap
immediately affects current invocation of a function and still provide
usable semantic.
> __Pascal Bourguignon__
From: Pascal Costanza
Subject: Re: Erlang brings up interesting questions about Lisp
Date:
Message-ID: <4l62m9FernnU1@individual.net>
Marcin 'Qrczak' Kowalczyk wrote:
> Pascal Costanza <··@p-cos.net> writes:
>
>> I am not aware of a lot of systems where a currently executing
>> function can be replaced with a new definition and that new definition
>> immediately takes effect, but it's certainly not impossible.
>
> I don't think there can be a sane semantics of that.
>
> (defun f ()
> (+ (g1) (g2) (g3) (g4)))
>
> Now let's say that g2 changes the definition of f to this:
>
> (defun f ()
> (+ (g5) (g6)))
>
> What happens when g2 returns?
I am aware of two approaches. In DYMOS (PhD thesis by Insup Lee), you
can add information to a procedure at what places it can be "morphed"
into another one. Since these places are identified, you have an
interface that you can control.
In my own PhD thesis, I am using an exception that unwinds the call
stack until the first call of the respective method, replaces the
method, and then calls the same method again to continue from there.
Both approaches allow you to even replace methods with non-terminating
loops.
In my approach, g2 would simply not return, but f would be called again.
There is no roll back taking place, but you can write exception handlers
that can take the necessary action when the stack is unwound.
Pascal
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
>>>>> "Pisin" == Pisin Bootvong <··········@gmail.com> writes:
Pisin> Erlang can hot-swap code in clustered PCs.
Sure, but I am trying to understand if this is different from what
Lisp is capable of doing (wrt. to code replacement that is).
------------------------+-----------------------------------------------------
Christian Lynbech | christian ··@ defun #\. dk
------------------------+-----------------------------------------------------
Hit the philistines three times over the head with the Elisp reference manual.
- ·······@hal.com (Michael A. Petonic)
pTymN wrote:
> So I've noticed a large amount of new Erlang articles popping up. The
> only innovation is that they've added microthreads + message passing.
> That got me thinking. What is message passing...?
>
>
> >From Erlang's point of view, message passing is a mechanism to avoid
> having to lock resources, by copying data instead of copying pointers
> to data. The message passing paradigm seems to be the most damning and
> most encouraging piece of innovation in Erlang. The problem is that
> message passing means that to pass a large data structure like a tree
> from one thread to another, you have to break it down into tiny pieces,
> and send the pieces through messages, and then the other thread will
> receive those messages and reconstruct the tree. The encouraging part
> is that since the other thread has to deal with a lossy connection, the
> messages contain metadata that help describe their relationships with
> other messages. So, at the end of the tree copy from one thread to
> another, you'd end up with two identical trees, but moreover, you'd
> have the metadata available to mirror additional changes on one tree on
> the other. Woo!
>
> However, I can't help feeling like this is overkill. A purely
> functional language can also be easily multithreaded, because all data
> is immutable, which is a nice property. In fact, in some ways, message
> passing feels like a mix of about 33% functional (data is immutable
> across threads) and about 66% procedural, since a thread is happily
> crunching away on its own personal data, presumably in a procedural
> manner. [correct me if I'm wrong, I'm no Erlang expert]
>
Erlang is closer to being purely functional language than Common Lisp.
Erlang is single assignment language, which means you can not change a
value of a variable once it is assign. This effectively makes all data
record immutable. But it is not as pure as haskell that doesn't even
allow IO operation to be done in computation code.
> So it seems that in Lisp, you can mostly avoid locking issues, except
> when combining the results from different threads.
Common Lisp is not purely functional language. And even if you wrote
purely functional style in Common Lisp I still doubt that the
compiler/GC will be smarter than those design in language with
immutable data in mind.
> It may not have
> microthreads, but that's not a big issue if your number of threads is
> only about 2X # of cpu's in a computer. Are any actual Lisp
> implementations up to the job?
>
Erlang program can have over thounsands of processes(Erlang threads) at
the same time (google for YAWS vs Apache performance). Unless you had
500 cores CPU, then you still need micro threads :-)
> 1) I've always heard that there was no common multithreading interface
> for Lisp. True? Not true? An unofficial one that everyone is always
> using?
>
> 2) If I have a quad core computer, what, if any computations can the
> other 3 processors perform while the garbage collector is working? Do
> any implementations have GC's that somehow can work while another
> thread is simulataneously accessing data?
>
> -pTymN