Sieve of Eratosthenes in Magpie

[Dave Cleaver]

There was a Go example that implemented the Sieve of Eratosthenes
using goroutines. I rewrote it with the async libraries to see how
easy it would be.

The Go implementation can be found at http://golang.org/doc/progs/sieve.go

My magpie implementation is at https://gist.github.com/1025282

Dave

[Bob Nystrom]

Very cool!

I've been meaning to add a more flexible counting method to the standard lib for numeric loops. Once I get that in, that could be simplified a bit: https://gist.github.com/1025344.

- bob

[Dave Cleaver]

I was thinking about a lazy iterator library. The count function would
fit neatly with that, although I suppose it could also handle non lazy
iteration.

count(from: 1, by: 2, to: 10)

or

1 by(2) to(10)

although I think I like the former better.

Dave

[Dave Cleaver]

Hmmm. I kept playing with this. I wrote up the infinite count function
and was playing with code that would let me write:

for i = from(channel) do somethingWith(i)

I think I've found a race condition. Sometimes the code functions
fine. And then at other times I get the following error with the name
of the initialization that failed changing:

Uncaught InitializationError: Instance of class Range was not
initialized.

I'm going to poke around at how init, threads, and Scope interact.

Dave

On Jun 14, 1:25 pm, Dave Cleaver <dsclea...@gmail.com> wrote:
> I was thinking about a lazy iterator library. The count function would
> fit neatly with that, although I suppose it could also handle non lazy
> iteration.
>
> count(from: 1, by: 2, to: 10)
>
> or
>
> 1 by(2) to(10)
>
> although I think I like the former better.
>
> Dave
>

> On Tue, Jun 14, 2011 at 1:12 PM, Bob Nystrom <munificent...@gmail.com> wrote:
> > Very cool!
>
> > I've been meaning to add a more flexible counting method to the standard lib
> > for numeric loops. Once I get that in, that could be simplified a bit:
> >https://gist.github.com/1025344.
>
> > - bob
>

> > On Tue, Jun 14, 2011 at 9:47 AM, Dave Cleaver <dsclea...@gmail.com> wrote:
>
> >> There was a Go example that implemented the Sieve of Eratosthenes
> >> using goroutines. I rewrote it with the async libraries to see how
> >> easy it would be.
>

> >> The Go implementation can be found athttp://golang.org/doc/progs/sieve.go

[Dave Cleaver]

I made a new version of the Sieve. It uses an infinite iterator over
the numbers and an iterator over a channel

https://gist.github.com/1025282

Dave

P.S - I patched my local version of magpie for the race condition by
putting the synchronized keyword on Interpreter.constructNewObject. I
don't think this is a viable long term solution to the race condition.

[Bob Nystrom]

On Tue, Jun 14, 2011 at 7:12 PM, Dave Cleaver <dscl...@gmail.com> wrote:

Hmmm. I kept playing with this. I wrote up the infinite count function
and was playing with code that would let me write:

for i = from(channel) do somethingWith(i)

I think I've found a race condition. Sometimes the code functions
fine. And then at other times I get the following error with the name
of the initialization that failed changing:

Uncaught InitializationError: Instance of class Range was not
initialized.

Unsurprising. Magpie's current level of concurrency support is about fifteen minutes of hacking on my part. It needs a lot more work. The long term goal is that no non-thread-safe state should be visible across multiple threads. Some of the small pieces are there:

1. Channels are thread-safe (I think?).
2. Primitive types are all immutable.
3. "val" for class fields will let you define immutable types.

But a lot more work is needed.

I'm going to poke around at how init, threads, and Scope interact.

Answer: poorly. :)

When you create an instance of a class, it works something like this:

1. you call "new".
2. the interpreter makes a fresh object and sticks in MAGIC_LOCATION.
3. the interpreter calls "init".
4. that does whatever you define it do to, eventually calling the canonical init that was defined for the class.
5. the canonical init gets the object from MAGIC_LOCATION and initializes its field.
6. init returns.
7. new returns the new object from MAGIC_LOCATION.

The problem here is that MAGIC_LOCATION is a single field in the interpreter. If you create objects simultaneously in multiple threads, there's nothing preventing them from stomping all over each other. A simple fix should be to just make the mConstructing and mInitializingCount in Interpreter be ThreadLocal.

The longer term solution will likely involve Magpie having its own stack frames and its own concept of a "thread" slightly removed from what Java provides.

- bob

[Dave Cleaver]

I was thinking of working on the threading stuff. If you would rather
I look at something else, then I can. I don't want to step on your
toes or duplicate work.

Dave

On Jun 15, 2:38 am, Bob Nystrom <munificent...@gmail.com> wrote:

> On Tue, Jun 14, 2011 at 7:12 PM, Dave Cleaver <dsclea...@gmail.com> wrote:
> > Hmmm. I kept playing with this. I wrote up the infinite count function
> > and was playing with code that would let me write:
>
> > for i = from(channel) do somethingWith(i)
>
> > I think I've found a race condition. Sometimes the code functions
> > fine. And then at other times I get the following error with the name
> > of the initialization that failed changing:
>
> > Uncaught InitializationError: Instance of class Range was not
> > initialized.
>
> Unsurprising. Magpie's current level of concurrency support is about fifteen

> minutes of hacking on my part. It needs a *lot* more work. The long term

[Bob Nystrom]

I don't mind you working on it, but later work may invalidate what you do.

The current interpreter is a really basic AST walker that uses the Java callstack as its own callstack. I want Magpie to have its own concept of stack frames, which likely also means bytecode compilation. I want to do that for a bunch of reasons:

1. Easier to do tail call elimination.
2. Makes it possible to have a restartable condition system.
3. Should make it easier/faster to spawn new "threads".

The current implementation is closer to being a prototype while I banged on the language semantics than what I'd consider a "real" implementation. Now that it looks like the semantics have settled down a bit (classes/multimethods/patterns/etc.) it will soon be time to start thinking about what a more... professional? implementation would look like.

So you're welcome to work on concurrency in the meantime, but do so knowing that your code may end up getting nuked at some point in the future. If you're OK with that, by all means go for it. :)

- bob

[Dave Cleaver]

Hah. I don't mind if my stuff gets invalidated. It might help at least solidify concepts that are worth preserving when the interpreter changes. 

When you talk about bytecode compilation do you mean compiling to the JVM specifically?

Dave

[Bob Nystrom]

On Wed, Jun 15, 2011 at 10:24 AM, Dave Cleaver <dscl...@gmail.com> wrote:

Hah. I don't mind if my stuff gets invalidated. It might help at least solidify concepts that are worth preserving when the interpreter changes. 

When you talk about bytecode compilation do you mean compiling to the JVM specifically?

Possibly, but more likely to its own bytecode format. I'm no expert so I have no idea if that's a good idea or not. I just know that's a simple path to having more control over stack frames, which is important for things like tail call elimination. Smarter compiler people than I can likely come up with a more effective solution. :)

- bob
 

[Dave Cleaver]

I have no idea either. I've just recently become interested in
building new languages.

I've been thinking about the enforcement of only accessing vars
defined within the current thread, and I think I have a pretty simple
solution. If every Scope associated itself with the thread (either JVM
thread or some other lightweight thread concept) that creates it, then
the look up procedure could enforce that mutable variables can only be
seen by the thread that created them. This would effectively make the
mutable state invisible to any other thread. We would also need to do
something similar to prevent access to the var fields in Obj.

Dave

On Jun 16, 11:56 pm, Bob Nystrom <munificent...@gmail.com> wrote:

> On Wed, Jun 15, 2011 at 10:24 AM, Dave Cleaver <dsclea...@gmail.com> wrote:
> > Hah. I don't mind if my stuff gets invalidated. It might help at least
> > solidify concepts that are worth preserving when the interpreter changes.
>
> > When you talk about bytecode compilation do you mean compiling to the JVM
> > specifically?
>
> Possibly, but more likely to its own bytecode format. I'm no expert so I
> have no idea if that's a good idea or not. I just know that's a simple path
> to having more control over stack frames, which is important for things like
> tail call elimination. Smarter compiler people than I can likely come up
> with a more effective solution. :)
>
> - bob
>
>
>
>
>
>
>
>
>
> > Dave
>

> > On Jun 15, 2011, at 1:02 PM, Bob Nystrom <munificent...@gmail.com> wrote:
>
> > I don't mind you working on it, but later work may invalidate what you do.
>
> > The current interpreter is a really basic AST walker that uses the Java
> > callstack as its own callstack. I want Magpie to have its own concept of
> > stack frames, which likely also means bytecode compilation. I want to do
> > that for a bunch of reasons:
>
> > 1. Easier to do tail call elimination.
> > 2. Makes it possible to have a restartable condition system.
> > 3. Should make it easier/faster to spawn new "threads".
>
> > The current implementation is closer to being a prototype while I banged on
> > the language semantics than what I'd consider a "real" implementation. Now
> > that it looks like the semantics have settled down a bit
> > (classes/multimethods/patterns/etc.) it will soon be time to start thinking
> > about what a more... professional? implementation would look like.
>
> > So you're welcome to work on concurrency in the meantime, but do so knowing
> > that your code may end up getting nuked at some point in the future. If
> > you're OK with that, by all means go for it. :)
>
> > - bob
>

> > On Wed, Jun 15, 2011 at 8:50 AM, Dave Cleaver < <dsclea...@gmail.com>

> >> > > > > <https://gist.github.com/1025344>https://gist.github.com/1025344.

>
> >> > > > > - bob
>
> >> > > > > On Tue, Jun 14, 2011 at 9:47 AM, Dave Cleaver <
> >> dsclea...@gmail.com>
> >> > > wrote:
>
> >> > > > >> There was a Go example that implemented the Sieve of Eratosthenes
> >> > > > >> using goroutines. I rewrote it with the async libraries to see
> >> how
> >> > > > >> easy it would be.
>
> >> > > > >> The Go implementation can be found athttp://

> >> > > <http://golang.org/doc/progs/sieve.go>golang.org/doc/progs/sieve.go
>
> >> > > > >> My magpie implementation is athttps://<http://gist.github.com/1025282>
> >> gist.github.com/1025282
>
> >> > > > >> Dave

[Bob Nystrom]

On Thu, Jun 16, 2011 at 9:38 PM, Dave Cleaver <dscl...@gmail.com> wrote:

I've been thinking about the enforcement of only accessing vars
defined within the current thread, and I think I have a pretty simple
solution. If every Scope associated itself with the thread (either JVM
thread or some other lightweight thread concept) that creates it, then
the look up procedure could enforce that mutable variables can only be
seen by the thread that created them.

I was thinking something similar, though I worry it may be painfully slow. Still, it's better than nothing which is what we have now. :)
 

This would effectively make the mutable state invisible to any other thread.

Instead of hiding it, it should probably throw an error.
 

We would also need to do something similar to prevent access to the var fields in Obj.

Good idea. It's pretty easy to tell if an object is thread-safe or not. If not, we can probably tag it with the thread that owns it and throw an error if you try to access it from another thread.

- bob

[Dave Cleaver]

I tried this by just saving off the Thread.currentThread in the Scope
when it was created and checking on get and set of a var value. It
really only adds an extra if condition and 1-2 == compares. I throw an
IllegalStateException for now and the results are spectacularly
disastrous if you try to access vars from other threads.

Dave

[Bob Nystrom]

On Fri, Jun 17, 2011 at 7:24 PM, Dave Cleaver <dscl...@gmail.com> wrote:
> I tried this by just saving off the Thread.currentThread in the Scope
> when it was created and checking on get and set of a var value. It
> really only adds an extra if condition and 1-2 == compares. I throw an
> IllegalStateException for now and the results are spectacularly
> disastrous if you try to access vars from other threads.

We'll need to relax that a little bit so that you can access
thread-safe stuff from across threads. Otherwise this won't work:

defclass Foo
end

run with
Foo new() // Oops! Foo is defined in another thread
end

But for stuff that isn't thread-safe, that sounds swell. :)

- bob