Threads are continuations

Parrot has Continuations. In fact, Parrot is *based* on Continuations: rather than having a call stack and stack frames, each sub call has a return continuation - a pointer back to the call frame and bytecode position to return to after the sub completes.

As the Scheme and Ruby users keep telling us, continuations are pretty neat stuff. In fact they're so neat that they give us light weight cooperative threads "for free".

The basic idea of cooperative threading is reasonably straightforward. There are two basic primitives: spawn and yield. Spawn takes a subroutine reference and schedules it to run as a separate thread. Yield stops the current thread - saving its current state - and starts or resumes the next thread to run. Each thread needs calls to "yield" sprinked throughout, or else the other threads will never get to run.

This type of mechanism is more useful than it sounds. Early versions of both Microsoft Windows and Mac OS used a mechanism like this for *all* of their multitasking.

Going from this to preemptive green threads shouldn't be that big a leap. All it'll need is for the VM to occasionally force a call to "yield".

So here's how we can do this in Parrot with continuations:

# green_threads.pir

=head1 Cooperative threads in pure PIR

This file demonstrates cooperative concurrency using continuations
on Parrot.

=cut

=head1 th_init

First, we create an array to store unscheduled threads in. For simplicity,
this is stored in a global.

=cut

.include 'interpinfo.pasm'

.sub th_init
    $P0 = new 'ResizablePMCArray'
    set_global 'threads', $P0
.end

=head1 th_create

This is the 'spawn' call. It takes a sub and schedules it to run as a
thread.

=cut

.sub th_create
    .param pmc in_sub
    $P0 = get_global 'threads'
    push $P0, in_sub
.end

=head1 th_resched

This is the 'yield' call. When called from a running thread, it saves the
current point in the computation as a continuation and runs the next thread.

=cut

.sub th_resched
    .local pmc cur_th, next_th, ths
    ths = get_global 'threads'

    # This gets the return continuation for the currently running sub.
    # When this continuation is invoked, it will be as if this call
    # to th_resched just returned.
    cur_th = interpinfo .INTERPINFO_CURRENT_CONT
    push ths, cur_th

again:  
    next_th = shift ths
    invokecc next_th

    $I0 = ths
    if $I0 > 0 goto again
.end

=head1 th_main

This starts up the thread system (after some threads have been scheduled) and makes
sure the program doesn't exit before all the threads have run to completion.

=cut

.sub th_main
    .local pmc ths

again1: 
    ths = get_global 'threads'

    $I0 = ths
    if $I0 <= 0 goto done

    th_resched()
    
    goto again1
done:   
.end

=head1

That's it. All we need now is some test threads and a main function to run them.

=cut

.sub sub1
    say "sub1: Hallo"
    th_resched()

    say "sub1: Dance! <(\"< >\")> <(\"<"
    th_resched()

    say "sub1: Bye"
.end

.sub sub2
    say "sub2: Hallo"
    th_resched()

    say "sub2: Dance! <(\"< >\")> <(\"<"
    th_resched()

    say "sub2: Bye"
.end

.sub sub3
    say "sub3: Good morning"

    th_resched()
    
    $I0 = 5
    $I1 = $I0 + 3

    th_resched()
    
    print "sub3: 5 + 3 = "
    say $I1

    th_resched()

    say "sub3: Is leaving."
.end

.sub main :main
    th_init()

    $P0 = get_global 'sub1'
    th_create($P0)

    $P0 = get_global 'sub3'
    th_create($P0)
    
    $P0 = get_global 'sub2'
    th_create($P0)

    th_main()

    say "All done"
.end

=head1 Expected Output

The program should (and does) produce this output:

sub1: Hallo
sub3: Good morning
sub2: Hallo
sub1: Dance! <("< >")> <("<
sub2: Dance! <("< >")> <("<
sub1: Bye
sub3: 5 + 3 = 8
sub2: Bye
sub3: Is leaving.
All done

=cut

Here's a link to the file that will eventually break:
http://pandion.ferrus.net/green_threads.pir