[9fans] Concurrency and message passing with Newsqueak

111 views
Skip to first unread message

Uriel

unread,
May 18, 2007, 7:46:55 PM5/18/07
to
http://video.google.com/videoplay?docid=810232012617965344

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

unread,
May 18, 2007, 11:25:47 PM5/18/07
to
> http://video.google.com/videoplay?docid=810232012617965344

I think I'm missing something. All the urls in the slides are like this:

http://go/newsqueak

what is http://go/? I doubt it's go.com.

Micah

Rob Pike

unread,
May 19, 2007, 12:04:33 AM5/19/07
to
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

erik quanstrom

unread,
May 19, 2007, 12:16:39 AM5/19/07
to
i'm glad they did, even with the insidious name.

- erik

W B Hacker

unread,
May 19, 2007, 12:36:56 AM5/19/07
to
Rob Pike wrote:
> 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

unread,
May 19, 2007, 12:56:26 AM5/19/07
to
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.

-rob

W B Hacker

unread,
May 19, 2007, 1:14:05 AM5/19/07
to
Rob Pike wrote:
> 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

unread,
May 19, 2007, 2:39:17 AM5/19/07
to
On Fri, May 18, 2007 at 09:55:37PM -0700, Rob Pike wrote:
> 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

unread,
May 19, 2007, 12:11:53 PM5/19/07
to
> If we're to compare channels to any
> 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

unread,
May 22, 2007, 2:33:42 PM5/22/07
to
On 5/18/07, W B Hacker <w...@conducive.org> wrote:
> Rob Pike wrote:
> > 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

unread,
May 22, 2007, 6:09:02 PM5/22/07
to
David Leimbach wrote:
> On 5/18/07, W B Hacker <w...@conducive.org> wrote:
>> Rob Pike wrote: (starter... snipped)

>>
>> 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

unread,
May 22, 2007, 7:36:34 PM5/22/07
to
> > http://en.literateprograms.org/Sieve_of_Eratosthenes_%28Haskell%29

> 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

unread,
May 23, 2007, 9:33:54 AM5/23/07
to

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

unread,
Jun 1, 2007, 1:02:07 AM6/1/07
to
The Unix implementation of Newsqueak (squint) builds on Mac OS X by
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

unread,
Jun 1, 2007, 7:29:50 AM6/1/07
to
That's cool, where can I get newsqueak anyway? :-) The presentation
seemed to show Rob's home directory.

Russ Cox

unread,
Jun 1, 2007, 9:46:17 AM6/1/07
to
>> The Unix implementation of Newsqueak (squint) ...

>
> 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

Reply all
Reply to author
Forward
0 new messages