[9fans] Concurrency and message passing with Newsqueak
Uriel
Thanks caerwyn for the heads up and please forgive me for posting
something most people in this list will actually care about
uriel
Micah Stetson
I think I'm missing something. All the urls in the slides are like this:
what is http://go/? I doubt it's go.com.
Micah
Rob Pike
was going to be made public until shortly beforehand and didn't
twig fast enough that the links wouldn't work, but you'll have
no trouble finding the papers by the usual means. Just convert
the go name back into words and do a search.
-rob
erik quanstrom
- erik
W B Hacker
> It's a google-internal site like tinyurl.com. I didn't know the talk
> was going to be made public until shortly beforehand and didn't
> twig fast enough that the links wouldn't work, but you'll have
> no trouble finding the papers by the usual means. Just convert
> the go name back into words and do a search.
>
> -rob
? Presume that was a Plan9 'browser-specific' issue?
Original link (thanks, Uriel, it is interesting) opened right up and played when
clicked here (SeaMonkey on OS X)
Side issue, but is there any value to contributing a Newsqueak code snippet as
one-more language sample on:
http://en.literateprograms.org/Sieve_of_Eratosthenes_%28Haskell%29
I list the Haskell link as it seemed closest in concept - other implementations
at top of that page.
Bill
Rob Pike
to the way lazy lists work. The power series program also comes
out quite well in Haskell. The systems examples I talked about
don't work quite so well, I believe. Channels are not really the
same as lazy lists.
-rob
W B Hacker
> The Haskell version is quite pretty
..if one groks Haskell. Or maybe only if one does NOT grok Haskell
Take, for example, the APL version ('bet you can't guess what THIS does') found
here:
http://www-users.cs.york.ac.uk/susan/cyc/p/prog.htm
;-)
> but almost a special case due
> to the way lazy lists work. The power series program also comes
> out quite well in Haskell. The systems examples I talked about
> don't work quite so well, I believe. Channels are not really the
> same as lazy lists.
>
> -rob
>
ACK.
Shifting gears yet again, I do notice Newsqueak has an entry here:
http://www.informatik.uni-freiburg.de/Java/misc/lang_list.html
(one of 2,350 languages as at January 1995!)
But not known to me if a 'modernized' list anywhere near as comprehensive as
that is extent (shorter ones certainly abound).
Bill
Kris Maglione
> The Haskell version is quite pretty but almost a special case due
> to the way lazy lists work. The power series program also comes
> out quite well in Haskell. The systems examples I talked about
> don't work quite so well, I believe. Channels are not really the
> same as lazy lists.
Haskell's lazy lists make for one of the most beautiful implementations
I've seen, and I agree that the CSP implementations is one of the most
beautiful pieces of code I've seen. If we're to compare channels to any
language feature, though, why not closures? I won't argue for replacing
one with the other of course, but there are some interesting
similarities. It's apparant to most readers that the CSP implementation
is basically checking that each number is 0 modulo any of the previous
primes, so applying a lambda to a list of previous primes immediately
came to mind. But this first implementation is almost an exact mapping
of the CSP implementation into lambdas and closures. Each new channel is
replaced with a new closure around the same lambda (the first being the
exception, as in CSP). I've also implemented it in Limbo, for the hell
of it, and for the sake of the topic. :)
As it turns out, the first implementation is the fastest.
(defun get-sieve ()
(let* ((n 1)
(fn (lambda ()
(incf n))))
(lambda ()
(let ((n (funcall fn))
(f fn))
(labels ((me ()
(let ((m (funcall f)))
(if (= (mod m n) 0)
(me)
m))))
(setf fn #'me)
n)))))
(defun get-sieve ()
(let ((n 1)
(list nil))
(labels ((prime (n)
(if (member-if (lambda (x) (= (mod n x) 0))
list)
(prime (1+ n))
n)))
(lambda ()
(prog1
(setf n (prime (1+ n)))
(setf list (cons n list)))))))
(defun primes (num)
(let ((sieve (get-sieve)))
(dotimes (n num)
(print (funcall sieve)))))
(defun getprimes (num)
(let ((sieve (get-sieve)))
(do ((n 0 (funcall sieve)))
((> n num))
(print n))))
nofactor(aux: int, l: list of int): int
{
for(; l != nil; l = tl l)
if(aux % hd l == 0)
return 0;
return 1;
}
primes(num: int)
{
l : list of int;
n := 2;
for(i := 0; i < num; n++) {
if(nofactor(n, l)) {
l = n :: l;
i++;
sys->print("%d\n", n);
}
}
}
--
Kris Maglione
In any hierarchy, each individual rises to his own level
of incompetence, and then remains there.
Russ Cox
> language feature, though, why not closures?
And why not for loops?
Prime sieves and power series are undeniably clean
message-passing programs. They are good examples
of *how* channels can be used, but not *why*
channels are useful in systems programs.
Channels provide a mechanism for implementing the
interface between two different pieces of code and
also a way to synchronize the two. Both are very
important reasons why people use channels for
systems programming. Closures alone don't provide
either.
Closures are useful too, just for different things.
Acme uses a trick where closures get sent from one
proc to another along a channel in order to start
the closure running as a new thread in the target
proc. The acme paper, p. 12 (Concurrency in the
implementation) discusses this.
When using libthread (or Alef), one reason you
care which proc each thread (task) runs in is that
when a proc blocks on a system call (not a channel
op), all the other threads in that proc block too.
So you might have one proc whose only job is to do
blocking I/O, using a channel to get I/O requests
from threads in other procs -- see ioproc(2) for a
library that wraps this up (ioproc(3) on p9p).
I reimplemented venti's buildindex a couple years
ago to run a lot faster. In the new buildindex,
the first step is to read each data block on the
arena disks, make an index entry for that data
block, and write it to the correct index disk, in
any order. (Future passes sort the individual
index disks into the right format, in parallel.
This step is just "spraying" each index entry onto
the right disk, like a multiway quicksort pivot.)
Buildindex starts a proc reading each arena and a
proc writing each index disk. The arena procs
just read a data block at a time and write an
index entry to the channel for the appropriate
disk. Each index proc reads a buffer worth of
index entries from its disk's channel, writes the
buffer to disk, and repeats. It just worked the
first time, and channels made the I/O trivial.
Russ
David Leimbach
> > It's a google-internal site like tinyurl.com. I didn't know the talk
> > was going to be made public until shortly beforehand and didn't
> > twig fast enough that the links wouldn't work, but you'll have
> > no trouble finding the papers by the usual means. Just convert
> > the go name back into words and do a search.
> >
> > -rob
>
> ? Presume that was a Plan9 'browser-specific' issue?
>
> Original link (thanks, Uriel, it is interesting) opened right up and played when
> clicked here (SeaMonkey on OS X)
>
> Side issue, but is there any value to contributing a Newsqueak code snippet as
> one-more language sample on:
>
> http://en.literateprograms.org/Sieve_of_Eratosthenes_%28Haskell%29
>
> I list the Haskell link as it seemed closest in concept - other implementations
> at top of that page.
>
I'm not sure that's even valid Haskell though. Looks like two type
definitions for the same function, and even if you correct that I
don't think it produces what one might think it does. At least not on
GHC :-)
Still the idea looks nice :-)
> Bill
>
>
W B Hacker
>>
>> http://en.literateprograms.org/Sieve_of_Eratosthenes_%28Haskell%29
>>
>> I list the Haskell link as it seemed closest in concept - other
>> implementations
>> at top of that page.
>>
>
> I'm not sure that's even valid Haskell though. Looks like two type
> definitions for the same function, and even if you correct that I
> don't think it produces what one might think it does. At least not on
> GHC :-)
>
> Still the idea looks nice :-)
>
Pass. I don't actually grok Haskell, just saw the use of a 'filter' structure as
a similarity to Newsqueak.
The version in Forth. OTOH I have used.
Or one much like it - Ray Duncan's LMI Forth on CP/M 2.X, CP/M-86, & PCDOS.
Bill
Bakul Shah
> I'm not sure that's even valid Haskell though. Looks like two type
> definitions for the same function, and even if you correct that I
> don't think it produces what one might think it does. At least not on
> GHC :-)
The second type definition on the referred page is not needed
(actually you don't need either defn). The function works
but you have to give it [2..], all natural numbers >= 2. The
prime sieve definition I like most is this:
sieve (a:xs) = a:sieve [x | x<- xs, x `mod` a > 0]
primes = sieve [2..]
Now you can just do
100 `take` primes
to get first 100 primes.
A stream such as primes will (and must) return the same Nth
value every time so after computing a value it will be cached
for later. A stream in effect has storage proportional to
the number of cdr (i.e. tail) operations done on it. A
channel on the other hand needs fixed minimum storage to
affect one value transfer and it has no memory of what was
already transferred.
David Leimbach
The channel itself has no memory of what was transferred, but I can't
think of a good reason one couldn't also memoize the remainder
computation needed such that if the spawned process/thread were to
stay alive for multiple runs, one could avoid re-computing the result,
which is what Haskell is doing, except that it's also probably caching
the results of "take" applied to "primes" in your case :-)
Jeff Sickel
adding the following to u.h
#ifdef __APPLE__
#include <unistd.h>
#include <string.h>
#include <stdlib.h>
#include <stdarg.h>
#include <fcntl.h>
#include <setjmp.h>
#include <math.h>
typedef unsigned char uchar;
typedef unsigned long ulong;
typedef unsigned long long uvlong;
typedef long long vlong;
#endif
David Leimbach
seemed to show Rob's home directory.
Russ Cox
>
> That's cool, where can I get newsqueak anyway? :-) The presentation
> seemed to show Rob's home directory.
http://google.com/search?q=unix+implementation+of+newsqueak
russ