SICP Concurrency Language

SICP Concurrency Language
=========================

Danny Yoo ([email protected] / [email protected])

Index terms: _sicp_ _concurrency_ _sicp-concurrency_


Introduction
============

This provides primitives for doing concurrency, meant to be used with
material from The Structure and Interpretation of Computer Programs
(SICP) Chapter 3.4.

    http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-23.html#%_sec_3.4


After this PLaneT module is locally installed and DrScheme is
restarted, a new language level called SICP Concurrency should be
selectable.  Alternatively, the provided module "sicp-concurrency.ss"
can be used as a module language.


Example usage
=============

    (module test-concurrency
      (planet "sicp-concurrency.ss" ("dyoo" "sicp-concurrency.plt"))
  
      (define (test-1)
        (define x 10)
        (parallel-execute (lambda () (set! x (* x x)))
                          (lambda () (set! x (+ x 1))))
        x)

      (define (test-2)
        (define x 10)
        (define s (make-serializer))
        (parallel-execute (s (lambda () (set! x (* x x))))
                          (s (lambda () (set! x (+ x 1)))))
        x))

This example comes from SICP Section 3.4.2 (Mechanisms for Controlling
Concurrency).  If we run TEST-1 for multiple rounds, we'll see several
different and surprising values depending on the interleaving that
happens with PARALLEL-EXECUTE.  TEST-2, on the other hand uses a
serializer to protect the respective critical regions.


API for (planet "sicp-concurrency.ss" ("dyoo" "sicp-concurrency.plt"))
======================================================================

This module language provides everything that mzscheme provides,
except for:

     #%app
     #%datum
     set!

which are replaced with custom version of these to cause more
interesting concurrency interactions.

We extend the language with following primitives:

> parallel-execute: thunks* -> (listof any)

Evaluates any number of thunks in parallel.  The scheduler runs in
round-robin order.  There are no guarantees on when context is switched
between the evaluated thunks, and the resulting values of the thunks
come in any order.


> make-serializer: -> (thunk -> any)

Constructs a serializer that consumes a thunk and evaluates it
atomically, returning its value.


> make-cell: boolean -> cell

Constructs a cell that holds a single boolean.


> clear!: cell -> void

Clears the cell's value.


> test-and-set!: cell -> boolean

Given a cell whose contents contain a boolean, atomically tests the cell.  As
in SICP, it evaluates to whatever the content of the cell is, but if
it was originally #f, sets it to #t.


Notes
=====

We deviate slightly in the representation of cells.  To create a new
cell, rather than use a 1-element list, we use the structures provided
by PLT Scheme.



Thanks
======

Thanks to Jens Axel Soegaard, for pretty much writing the hard stuff
in this module.  Most of this is taken from his work; I just added a
nice language package for this.  Also thanks to the PLT team for a
nice programming environment.

Thanks to Emre Berat Nebio\u{g}lu for notifying me when this package
broke under the immutable-list changes in PLT Scheme 4.