3rd Workshop on Script to Program Evolution
(co-located with ECOOP and PLDI)
Beijing, China
June 11, 2012
http://wrigstad.com/stop12/

OVERVIEW

Recent years have seen increased use of scripting languages in large applications. Scripting  languages optimize development time, especially early in the software life cycle, over safety and robustness. As the understanding of the system reaches a critical point and requirements stabilize, scripting languages become less appealing. Compromises made to optimize development time make it harder to reason about program correctness, harder to do semantic-preserving refactorings, and harder to optimize execution speed. Lack of type information makes code harder to navigate and to use correctly. In the worst cases, this situation leads to a costly and potentially error-prone rewrite of a program in a compiled language, losing the flexibility of scripting languages for future extension.

Recently, pluggable type systems and annotation systems have been proposed. Such systems add compile-time checkable annotations without changing a program’s run-time semantics which facilitates early error checking and program analysis. It is believed that untyped scripts can be retrofitted to work with such systems. Furthermore, integration of typed and untyped code, for example, through use of gradual typing, allows scripts to evolve into safer programs more suitable for program analysis and compile-time optimizations.

With few exceptions, practical reports are yet to be found. The STOP workshop focuses on the evolution of scripts, largely untyped code, into safer programs, with more rigid structure and more  constrained behavior through the use of gradual/hybrid/pluggable typing, optional contract checking, extensible languages, refactoring tools, and the like. The goal is to further the understanding and use of such systems in practice, and connect practice and theory.

CALL FOR CONTRIBUTIONS

Abstracts, position papers, and status reports are welcome. Papers should be 1-2 pages in standard ACM SIGPLAN format. All submissions will be reviewed by the program committee. The accepted papers, after rework by the authors, will be published in an informal proceedings, which will be distributed at the workshop. All accepted submissions shall remain available from the workshop web page.

Papers are to be submitted electronically via the STOP website: http://wrigstad.com/stop12/

IMPORTANT DATES

paper submission: 11:59 PM 30 March 2012 Eastern Daylight Time
notification: 20 April 2012
camera-ready paper: 15 May 2012
conference date: 11 June 2012

PROGRAM COMMITTEE

Avik Chaudhuri, Adobe Labs
Kathryn Gray, Swansea University
Arjun Guha, Brown University
David Herman, Mozilla Research
Manuel Hermenegildo, IMDEA
Atsushi Igarashi, Kyoto University
Ranjit Jhala, University of California, San Diego
Sam Tobin-Hochstadt (Chair), Northeastern University

% raco git --github offby1 rudybot

And that’s all you need to do to install rudybot, everyone’s favorite IRC bot. Now there’s a Racket collection set up called rudybot, and you can do things like:

% racket -t rudybot/loop

To install raco git, do the following:

% git clone http://github.com/samth/raco-git.git
% raco link raco-git
% raco setup raco-git

 % racket -l gcstats -u my-program.rkt

This says to first require the gcstats module before running my-program.rkt. When you do this you’ll get a big printout after your program runs; below the fold, we’ll take a look at each line in detail.

    39,703,916 bytes allocated in the heap
    28,890,688 bytes collected by GC
    17,083,432 bytes max heap size
    16,604,120 bytes max slop
    28,229,632 bytes peak total memory use

Generation 0:       5 collections,       32ms,    31.71ms elapsed
Generation 1:       0 collections,        0ms,        0ms elapsed

INIT  time       256 ms
MUT   time       132 ms (    129.98 ms elapsed)
GC    time        32 ms (     31.71 ms elapsed)
TOTAL time       420 ms (    417.69 ms elapsed)

%GC time       19.51%   ( 19.61% elapsed)

Alloc rate     300,787,242 bytes per MUT second

To install, follow the instructions on the GitHub page.

Right now, the tool is preliminary, but useful. There are a few limitations:

1. There are a few GCs before the tool starts — it can’t report anything about them.
2.  If you have multiple places, it will only report information from the initial place. Fixing this will require  more information from Racket.
3. The current architecture keeps too much info around during the run of the program.  I hope to fix that soon.

Hopefully, this gives people some better information about how the Racket GC behaves.  The output formatting and information gathered is inspired by similar output from the GHC runtime system.

Now let’s return to a detailed look at the output.

  2,715,625,408 bytes allocated in the heap

How many bytes, total, were allocated by the program

  2,687,494,428 bytes collected by GC

How many bytes, total, were collected during the run of the program

     73,728,640 bytes max heap size

The largest heap size observed at any GC

     66,748,764 bytes max slop

The largest difference between the memory allocated and the memory
the GC has reserved.

     85,884,928 bytes peak total memory use

The largest total memory use, including GC overhead.

Generation 0:     147 collections,    1,120ms, 1,157.53ms elapsed

How many nursery collections there were, and how long they took, in both process and elapsed time.

Generation 1:       6 collections,      596ms,   605.63ms elapsed

How many major collections there were, and how long they took, in
both process and elapsed time.

INIT  time       260 ms

Time spent in the process prior to the logging happening. This is primarily Racket startup time, and code loading time.

MUT   time     8,996 ms (  9,038.51 ms elapsed)

How much time the “mutator”, i.e. your program, was running.

GC    time     1,716 ms (  1,763.16 ms elapsed)

How much time the GC took.

TOTAL time    10,972 ms ( 11,061.67 ms elapsed)

The total time from the initial invocation.

%GC time       16.02%   ( 16.32% elapsed)

What percentage of the time (after initialization) was spent in GC.

Alloc rate 301,870,321 bytes per MUT second

The average rate of allocation, not counting GC time.

Except that’s not right. JavaScript’s concurrency model is cooperative, which means that you don’t get descheduled if you don’t want to be, but everything else about shared memory concurrency is still there. As a demonstration, here’s some shared-memory concurrency in JS:

var x = 1;
setTimeout(function() { x = 2; }, 2);
setTimeout(function() { console.log(x); }, 0);

What value of x gets logged? Well, that depends on when the two different callbacks get inserted into the event queue, just like the semantics of a shared-memory program with threads.

For a more involved example, here’s a lock in JavaScript:

// a lock with exponential backoff

function Lock() {
    this.state = 0;
    return this;
}

Lock.prototype.acquire = function(cb) { 
    var self = this;
    var check = function(N) {
	if (self.state === 0) {
	    self.state = 1;
	    cb(); }
	else { 
	    console.log("backing off to ", 2*N);
	    setTimeout(check,N,2*N);
	}
    }
    setTimeout(check,1,1);
}

Lock.prototype.tryAcquire = function() { 
    if (this.state === 0) {
	this.state = 1;
	return true;
    }
    return false;
}

Lock.prototype.release = function() { this.state = 0; }

This code isn’t perfect (you can release someone else’s lock, for example), but it demonstrates all the relevant issues. Now we can code up dining philosophers:

var N = 5;
var forks = [];
for (var i = 0; i < N; i++) {
    forks.push(new Lock());
}

function deadlock () {
    for (var i = 0; i < 5; i++) {
	console.log("starting philosopher", i);
	forks[i].acquire(function(i){
 	    console.log("philosopher", i, "picked up fork", i);
	    return function() {
		forks[(i+1)%N].acquire(function() {
		    console.log("philosopher ", i, " eating");
		    forks[i].release();
		    forks[(i+1)%N].release();
		})}}(i));
    }
}

Running deadlock() deadlocks in my version of Firefox, just like you’d expect. We can adopt a lock ordering solution, as described in the Wikipedia article:

function work () {
    for (var i = 0; i < 5; i++) {
	console.log("starting philosopher", i);
	var j1 = Math.min(i,(i+1)%N);
	var j2 = Math.max(i,(i+1)%N);
	forks[j1].acquire(function(i,j1,j2){
	    console.log("philosopher", i, "picked up fork", i);
	    return function() {
		forks[j2].acquire(function() {
		    console.log("philosopher ", i, " eating");
		    forks[j2].release();
		    forks[j1].release();
		})}}(i,j1,j2));
    }
}

Most of the time in JavaScript, you don’t need to write locks explicitly like this. However, you shouldn’t think that event-based concurrency eliminates synchronization, or shared memory, or anything other than preemption.

Of course, JavaScript is in good company here: even Erlang (message sending is arbitrarily-ordered mutation of process inboxes, see also Mnesia) and Haskell (the M in MVar stands for “mutable”) are languages with concurrency and shared mutable state.

There are now two new Racket versions of the benchmarks, one each using futures and places. The mandelbrot benchmark uses futures, getting a speedup of approximately 3.2x on 4 cores, and the binary-trees benchmark uses places, with a speedup of almost exactly 2x.

I learned a few things writing these programs:

1. Racket’s parallelism constructs, though new, are quite performant, at least on microbenchmarks.  With only two parallel programs, Racket is right now competitive with Erlang on 4 cores.
2. Futures are really easy to use; places take a little more getting used to. Both are quite simple once you get the hang of it, especially if you’ve written concurrent Racket programs before using Racket’s threads.
3. It can be very surprising which languages are easiest to translate to Racket.  F# and OCaml were the easiest, with Scala similar.  Programs written in Common Lisp, though fast, were much harder to convert to Racket.
4. My quick rule of thumb for whether to choose places or futures: if you program does much allocation in parallel, or it needs to synchronize, then use places.  Otherwise, futures are probably easier.  I think this is roughly in line with the original design, and there are more applications where synchronization is unnecessary than you would think.

There are a bunch more programs that could have parallel implementations; feel free to hack on them, or to improve mine.