Programming Language Research on .NET @ MSR

.NET Programming
Language Research
@ MSR Cambridge
Nick Benton
Microsoft Research
Cambridge
MSR Cambridge Programming
Principles and Tools Group

Luca Cardelli

Nick Benton
Cedric Fournet
Andy Gordon
Tony Hoare
Andrew Kennedy
Simon Peyton Jones
Don Syme










Simon Marlow
Claudio Russo
Mark Shields
+ visitors, PhD students, interns,…
MS.NET days March 2002
.NET in MSR Programming
Principles and Tools Group









Verifier spec (POPL)
CLR design feedback
Project 7 (Babel)
SML.NET (ICFP,ICFP,HOOTS)
Generics for C# and .NET (PLDI)
Extended IL (Babel)
Polyphonic C# (FOOL, ECOOP)
Stack-Walking Security analysis (POPL)
Assertions
MS.NET days March 2002
Part 1
SML.NET
Nick Benton, Andrew Kennedy
and Claudio Russo
Advanced Programming
Languages on the CLR

.NET and the CLR provide a great opportunity
for programming language designers and
implementers:
 The
runtime provides services (execution engine,
garbage collection,…) which make producing a good
implementation of your language easier
 The frameworks & libraries mean you can actually do
useful things with your new language (graphics,
networking, database access, web services,…)
 Multi-language component-based programming
makes it much more practical for other people to use
your language in their own projects
MS.NET days March 2002
Our favourite language:
Standard ML




A safe, modular, strict, higher-order, functional,
polymorphic programming language with
compile-time type checking and type inference,
garbage collection, exception handling,
immutable data types, pattern-matching and
updatable references, abstract data types, and
parametric modules.
with several efficient implementations
and a formal definition with a proof of
soundness.
(Scheme+types+real syntax, Haskell with call by
value evaluation)
MS.NET days March 2002
Some SML
datatype order = LESS | GREATER | EQUAL
datatype 'a Tree = Empty
| Node of 'a * ('a Tree) * ('a Tree)
fun contains compare (x, Empty) = false
| contains compare (x, Node(v, left, right)) =
(case compare (x,v) of
LESS => contains compare (x,left)
| GREATER => contains compare (x, right)
| EQUAL => true
)
contains : ('a * 'a -> order) -> ('a * 'a Tree) -> bool
MS.NET days March 2002
What is SML.NET?


Compiler for SML that targets verifiable CIL
Research Issues:

Can we compile a polymorphic functional language to a
monomorphic, object-oriented runtime?


How can we make it produce fast, compact code?


Yes
Whole-program optimising compiler. Monomorphisation.
Representation tricks. Novel typed intermediate language using
monads to track side-effects.
How can we make cross-language working easy?

We extend SML to support all of the .NET CLS (Common Language
Specification), providing smooth bidirectional interoperability with
.NET framework libraries & other .NET languages
MS.NET days March 2002
Previous approaches to interop
Bilateral interface with marshalling and explicit
calling conventions (e.g. JNI, O’Caml interface
for C).
1.
•
Awkward, ugly, tied to one implementation, only for
experts
Multilateral interface with IDL (e.g. COM,
CORBA) together with particular language
mappings (e.g. H/Direct, Caml COM,
MCORBA).
2.
•
Have to write IDL and use tools, tend to be lowestcommon denominator, memory management often
tricky
MS.NET days March 2002
Interop in .NET

Languages share a common higher-level
infrastructure (CLR):
 shared
heap means no tricky cross-heap pointers
(cf reference counting in COM)
 shared type system means no marshalling
(cf string<->char* marshalling for Java<->C)
 shared exception model supports cross-language
exception handling
MS.NET days March 2002
SML.NET interop

Sounds great, but SML is not object-oriented


So we are going to have to do some work…
Possible approaches to interop:

do not extend language; instead provide wrappers that give a
functional view of a CLS library (Haskell, Mercury).



Powerful functional type systems can go a very long way towards
modelling OO type systems
redesign the language (OO-SML?)
Our approach – a middle way:



re-use existing features where appropriate (non-object-oriented
subset)
extend language for convenient interop when “fit” is bad (objectoriented features)
live with the CLS at boundaries: don’t try to export complex ML
types to other languages (what would they do with them?)
MS.NET days March 2002
Re-use SML features
multiple args
void
null
static field
static method
CLS
namespace
delegate
mutability
using
private fields
MS.NET days March 2002
tuple
unit
NONE
val binding
fun binding
SML
structure
first-class function
ref
open
local decls
Extend language
type test
cast patterns
class definitions
instance method invocation
instance field access
custom attributes
casts
classtype
obj.#meth
obj.#fld
attributes in classtype
exp :> ty
CLS
SML
MS.NET days March 2002
Extract from WinForms interop
open System.Windows.Forms System.Drawing System.ComponentModel
no args = ML unit value
fun selectXML () =
CLS Namespace
let
= ML structure
val fileDialog = OpenFileDialog()
in
static method = ML function
fileDialog.#set_DefaultExt("XML");
fileDialog.#set_Filter("XML files (*.xml) |*.xml");
if fileDialog.#ShowDialog() = DialogResult.OK
then
static constant field = ML value
case fileDialog.#get_FileName() of
NONE => ()
instance method invocation
| SOME name =>
replaceTree (ReadXML.make name, "XML file '" ^ name ^ "'")
else ()
end
CLS string = ML string
null value = NONE
And note that there are no explicit types in this code
MS.NET days March 2002
Ray tracing in ML


ICFP programming competition: build a ray
tracer in under 3 days
39 entries in all kinds of languages:
 C,
C++, Clean, Dylan, Eiffel, Haskell, Java, Mercury,
ML, Perl, Python, Scheme, Smalltalk

ML (Caml) was in 1st and 2nd place
MS.NET days March 2002
Ray tracing in SML.NET




Translate winning entry to SML
Add WinForms interop
Run on .NET CLR
Performance on this example twice as good as
popular optimizing native compiler for SML
 (though
on others we’re twice as bad)
MS.NET days March 2002
Visual Studio Integration
Bootstrap the compiler to produce a .NET
component for parsing, typechecking, etc.
of SML
 Use interlanguage working extensions to
expose that as a COM component which
can be glued into Visual Studio
 Write new ML code to handle syntax
highlighting, tooltips, error reporting, etc.

MS.NET days March 2002
Part 2
Generics in the CLR
and C#
Andrew Kennedy and Don
Syme
Note: This is not in V1 of the CLR 
It will be in V2

MS.NET days March 2002
Part 1: Introduction
MS.NET days March 2002
What are generics?





Types which are parameterized by other types,
e.g. Stack<int>, Stack<string>
Generics, templates, parametric polymorphism
Ada, Eiffel, C++, ML, Haskell, Mercury,
Component Pascal,…
Promote code reuse, increase type safety, better
performance
Good for collections, higher-order programming
and generally building higher-level, reusable
abstractions
MS.NET days March 2002
Generic code in C# today (1)
class Stack {
private Object[] items;
private int nitems;
Stack() { nitems = 0; items = new Object[50]; }
Object Pop() {
if (nitems == 0) throw new EmptyException();
return items[--nitems];
}
void Push(Object item) {
...
return items[nitems++];
}
}
MS.NET days March 2002
Generic code in C# today (2)
Stack s = new Stack();
s.Push(1);
s.Push(2);
int n = (int)(s.Pop()) + (int)(s.Pop());
What’s wrong with that?
• It’s inexpressive. Type system doesn’t document what
should be in a particular stack.
• It’s unsafe. Type errors (s.Push(“2”); ) lead to
runtime exceptions instead of being caught by compiler
• It’s ugly. Casts everywhere.
• It’s slow. Casts are slow, and converting base types
(e.g. ints) to Objects involves expensive boxing.
MS.NET days March 2002
Generic code in C# tomorrow (1)
class Stack<T> {
private T[] items;
private int nitems;
Stack() { nitems = 0; items = new T[50]; }
T Pop() {
if (nitems == 0) throw new EmptyException();
return items[--nitems];
}
void Push(T item) {
if (items.Length == nitems) {
T[] temp = items;
items = new T[nitems*2];
Array.Copy<T>(temp, items, nitems);
}
items[nitems++] = item;
}
}
MS.NET days March 2002
Generics: large design space
But can type
instantiations can be
non-reference?

Parameterized
classes,Set<int>
interfaces, and
Do you erase
List<float>
// at
two-parameter
class
types
runtime?
methods
e.g.{ ... }
class Dict<K,D>
// parameterized interface
Do we have exact runtime
Do you share
interface IComparable<T> { ... } type information?
code?
// parameterized struct
struct Pair<A,B> { ... }
if (x is Set<int>)
....
// generic method
Constraints?
What goes
in
the
class
C<T: IFoo, IBar>
T[] Slice<T>(T[] arr, int start, int
count)
CLR? What goes in
{ ... }
the compilers?
MS.NET days March 2002
Generic interfaces
interface IDictionary<K,D>
{
D Lookup(K);
...
}
class Dictionary<K,D> : IDictionary<K,D>
{
D Lookup(K);
...
}
Dictionary<String,String>
MS.NET days March 2002
Generic methods
A generic method is just a
family of methods, indexed
by type.
static void Sort<T> (T[]) { ... }
int[] x = { 5,4,3,2 };
Sort(x);
MS.NET days March 2002
Explicit Constraints
interface IComparable<T> { static int Compare(T,T); }
class BinaryTree<T : IComparable<T> >
{
void insert(T x) {
switch (x.Compare(y)) {
...
}
}
T y;
Static constraints are
available via interfaces.
Tree<T> left;
Tree<T> right;
}
MS.NET days March 2002
Part 2: Implementing Generics
for the .NET CLR
MS.NET days March 2002
Generics: Our design


Parameterized classes, interfaces, structs,
methods, delegates
Yes
Exact runtime types:
Yes
if (x is Set<string>) { ... }

Instantiations at value types: Yes
Set<String>

Set<int>
List<float>
Constraints:
Yes (by interfaces)
class C<T: IComponent>

Variance:
No
Set<String> is not subtype-related to Set<Object>
MS.NET days March 2002
How does it work?
Stack<int> si = new Stack<int>();
1a. Look for Stack<int>
1b. Nothing exists yet, so create
structures for Stack<int>
Stack<int> si2 = new Stack<int>();
2a. Look for Stack<int>
Stack<string> ss = new Stack<string>(); 2b. Type already loaded!
Stack<object> so = new Stack<object>();
si.Push(5);
ss.Push(“Generics”);
so.Push(myObj);
3a. Look for Stack<string>
3b. <string> not compatible with
<int>, so create structures for
Stack<string>
4a. Look for Stack<object>
4b. <object> compatible with <string>, so
re-use Stack<string>
MS.NET days March 2002
How does it work?
Stack<int> si = new Stack<int>();
Stack<int> si2 = new Stack<int>();
Stack<string> ss = new Stack<string>();
Stack<object> so = new Stack<object>();
si.Push(5);
ss.Push(“Generics”);Compile
code for Stack<int>.Push
so.Push(myObj);
Compile code for
Stack<string>.Push
Re-use code from
Stack<string>.Push
MS.NET days March 2002
Implementing Generics (0)

Dynamic loading & JIT compilation change many
fundamental assumptions
 Can
consider code generation at runtime
 Can use more dynamic data structures

The current challenge is to implement all of:
 exact runtime types + code sharing +
dynamic loading + non-uniform instantiations
MS.NET days March 2002
Implementing Generics (1)

Our implementation:
1. Dynamic code expansion and sharing
Instantiating generic classes and methods is
handled by the CLR.
 Generate/compile code as necessary
 Use JIT compiler
 Share code for “compatible” instantiations
 Compatibility is determined by the implementation

MS.NET days March 2002
Implementing Generics (2)

Our implementation:
1. Dynamic code expansion and sharing
2. Pass and store runtime type information

Objects carry runtime type information
We record this information by duplicating vtables.
 Other options are possible.

Generic methods take an extra parameter
 The active type context is always recoverable

MS.NET days March 2002
Implementing Generics (3)
 Our
implementation:
1. Dynamic code expansion and sharing
2. Pass and store runtime type
information
3. Optimized use of runtime type
information
MS.NET days March 2002
Generics: Performance
1.
Instantiations at value types

Stack with repeated push and
pops of 0...N elements
(a) List_int
(b) List (i.e. existing collection class)
(c) List<int>

2.
No casts

3.
5X speedup (c) v. (b)
20% speed on similar micro-benchmarks
Runtime type computations

Generic allocation ~10% slower in generic code
MS.NET days March 2002
Generics: Design Comparison
GJ
NextGen








½
½





½





½





½











½




½



C++
Dynamic Load
Efficient nonreference
instantiations
Exact run-time
types
Efficient via fewer
runtime type tests
Code Sharing
Ship without
source
Debug (type pars
visible at runtime)
Safe, efficient covariance
PolyJ
Bracha,
Odersky,
Stoutamire,
Wadler
Cartwright,
Steele
MS.NET days March 2002
Bank,
Liskov,
Myers
Agesen,
Freund,
Mitchell
CLR
Kennedy,
Syme
Comparison with C++ templates

What C++ gets wrong:
 Modularity

need to see the template at link time
 Efficiency

nearly all implementations code-expand
 Safety

not checked at declaration & use, but at link time
 Simplicity

very complicated
MS.NET days March 2002
Comparison with C++ templates

What we get right:
 Modularity:

no need to see the generic IL until runtime
 Efficiency:

code expansion managed by the VM
 Safety:

check at declaration & use
 Simplicity:

there are some corners, but the mechanism is
simple to explain & use
MS.NET days March 2002
Summary

A world first: cross-language generics.
A world first: generics in a high-level virtual machine
design.

Implementation:



The virtual machine (runtime) level is the right place to
implement generics for .NET
Potential for:



Other implementation techniques (more aggressive sharing, some
boxing, etc.)
Further extensions (type functions, variance, more expressive
constraints)
Good performance
MS.NET days March 2002
Part 3
Polyphonic C#
Nick Benton, Luca Cardelli
and Cedric Fournet
Introduction
MS.NET days March 2002
Programming in a networked world

Developers now have to work in a
 Concurrent
 Distributed
 High
 (&
latency
low reliability, security sensitive, multi-everything)
environment.
 Which is hard
 And they’re mostly not very good at it
 Try
using Outlook over dialup 
MS.NET days March 2002
Asynchronous communication
Distribution => concurrency + latency
=> asynchrony
=> more concurrency
 Message-passing, event-based
programming, dataflow models
 For programming languages, coordination
(orchestration) languages & frameworks,
workflow

MS.NET days March 2002
Language support for concurrency
Make invariants and intentions more
apparent (part of the interface)
 Good software engineering
 Allows the compiler much more freedom to
choose different implementations
 Also helps other tools

MS.NET days March 2002
.NET Today





Multithreaded execution environment with lock per object
C# has “lock” keyword, libraries include traditional
shared-memory synchronization primitives (mutexes,
monitors, r/w locks)
Delegate-based asynchronous calling model, events,
messaging
Higher level frameworks built on that
Hard to understand, use and get right


Different models at different scales
Support for asynchrony all on the caller side – little help building
code to handle messages (must be thread-safe, reactive, and
deadlock-free)
MS.NET days March 2002
Polyphonic C#


An extension of the C# language with new
concurrency constructs
Based on the join calculus
process calculus like the p-calculus but
better suited to asynchronous, distributed systems
 A foundational

A single model which works both for
 local
concurrency (multiple threads on a single
machine)
 distributed concurrency (asynchronous messaging
over LAN or WAN)
MS.NET days March 2002
The Language
MS.NET days March 2002
In one slide:


Objects have both synchronous and asynchronous methods.
Values are passed by ordinary method calls:



If the method is synchronous, the caller blocks until the method
returns some result (as usual).
If the method is async, the call completes at once and returns void.
A class defines a collection of synchronization patterns
(chords), which define what happens once a particular set of
methods have been invoked on an object:




When pending method calls match a pattern, its body runs.
If there is no match, the invocations are queued up.
If there are several matches, an unspecified pattern is selected.
If a pattern containing only async methods fires, the body runs in a
new thread.
MS.NET days March 2002
A Simple Buffer
class Buffer {
String get() & async put(String s) {
return s;
}
}
MS.NET days March 2002
A Simple Buffer
class Buffer {
String get() & async put(String s) {
return s;
}
}
•An ordinary (synchronous) method with no
arguments, returning a string
MS.NET days March 2002
A Simple Buffer
class Buffer {
String get() & async put(String s) {
return s;
}
}
•An ordinary (synchronous) method with no
arguments, returning a string
•An asynchronous method (hence returning no
result), with a string argument
MS.NET days March 2002
A Simple Buffer
class Buffer {
String get() & async put(String s) {
return s;
}
}
•An ordinary (synchronous) method with no
arguments, returning a string
•An asynchronous method (hence returning no
result), with a string argument
•Joined together in a chord
MS.NET days March 2002
A Simple Buffer
class Buffer {
String get() & async put(String s) {
return s;
}
}
•Calls to put() return immediately (but are internally queued if there’s
no waiting get()).
•Calls to get() block until/unless there’s a matching put()
•When there’s a match the body runs, returning the argument of the
put() to the caller of get().
•Exactly which pairs of calls are matched up is unspecified.
MS.NET days March 2002
A Simple Buffer
class Buffer {
String get() & async put(String s) {
return s;
} •Does example this involve spawning any threads?
}
•No. Though the calls will usually come from different preexisting threads.
•So is it thread-safe? You don’t seem to have locked anything…
•Yes. The chord compiles into code which uses locks. (And that
doesn’t mean everything is synchronized on the object.)
•Which method gets the returned result?
•The synchronous one. And there can be at most one of those in
a chord.
MS.NET days March 2002
Reader/Writer

…using threads and mutexes in Modula 3
An introduction to programming with threads.
Andrew D. Birrell, January 1989.
MS.NET days March 2002
Reader/Writer in five chords
class ReaderWriter {
void Exclusive() & private async Idle() {}
void ReleaseExclusive() { Idle(); }
void
void
void
if
}
Shared() & private async Idle()
{ S(1); }
Shared() & private async S(int n) { S(n+1); }
ReleaseShared() & private async S(int n) {
(n == 1) Idle(); else S(n-1);
ReaderWriter() { Idle(); }
}
A single private message represents the state:
none  Idle()  S(1)  S(2)  S(3) …
MS.NET days March 2002
Asynchronous Service Requests
and Responses

The service might export an async method
which takes parameters and somewhere to put
the result:
a
buffer, or a channel, or
 a delegate (O-O function pointer)
delegate async IntCB(int v);
class Service {
public async request(String arg, IntCB callback) {
int result;
// do something interesting…
callback(result);
}
}
MS.NET days March 2002
Asynchronous Service Requests
and Responses - join
class Join2 {
void wait(out int i, out int j)
& async first(int r1)
& async second(int r2) {
i = r1; j = r2; return;
}
}
// client code:
int i,j;
Join2 x = new Join2();
service1.request(arg1, new IntCB(x.first));
service2.request(arg2, new IntCB(x.second));
// do something useful
// now wait until both results have come back
x.wait(i,j);
// do something with i and j
MS.NET days March 2002
Asynchronous Service Requests
and Responses - select
class Select {
int wait()
& async reply(int r) {
return r;
}
}
// client code:
int i;
Select x = new Select();
service1.request(arg1, new IntCB(x.reply));
service2.request(arg2, new IntCB(x.reply));
// do something useful
// now wait until one result has come back
i = x.wait();
// do something with i
MS.NET days March 2002
Extending C# with chords

Classes can declare methods using generalized
chord-declarations instead of method-declarations.
chord-declaration ::= method-header [ & method-header ]* body
method-header ::= attributes modifiers [return-type | async] name
(parms)

Interesting well-formedness conditions:
1.
2.
3.
At most one header can have a return type (i.e. be synchronous).
The inheritance restriction.
“ref” and “out” parameters cannot appear in async headers.
MS.NET days March 2002
Implementation
MS.NET days March 2002
Example: Sum of Squares
add(1)
total(0,8
)
add(4)
SumOfSquares
add(9)
add(64
)
MS.NET days March 2002
Sum of Squares
total(1,7
)
add(4)
SumOfSquares
add(9)
add(64
)
MS.NET days March 2002
Sum of Squares Code
class SumOfSquares {
private async loop(int i) {
if (i > 0) {
add(i * i);
loop(i - 1);
}
}
private int total(int r, int i) & private async add(int dr) {
int rp = r + dr;
if (i > 1) return total(rp, i - 1);
return rp;
}
public SumOfSquares(int x) {
loop(x);
int i = total(0, x);
System.Console.WriteLine("The result is {0}.", i);
}
}
MS.NET days March 2002
Sum of Squares Translation
using System;
using System.Collections;
using System.Threading;
class SyncQueueEntry{
public int pattern;
public System.Threading.Thread mythread;
public System.Object joinedentries;
}
class SumOfSquares{
Queue Q_totalint_int_ = new Queue();
Queue Q_addint_ = new Queue();
class loopint__runner{
SumOfSquares parent;
int field_0;
public loopint__runner(SumOfSquares p_p,int p_0) {
parent = p_p;
field_0 = p_0;
Thread t = new Thread(new ThreadStart(this.doit));
t.Start();
}
void doit() {
parent.loopint__worker(field_0);
}
}
private void loopint__worker(int i) {
if (i >= 1) {add(i * i);
loop(i - 1);
}
}
static void Main() {
SumOfSquares s = new SumOfSquares();
int thesum = s.sum(10);
Console.WriteLine(thesum);
}
public int sum(int x) {
loop(x);
return total(0, x);
}
private int total(int sync_p_0,int sync_p_1) {
SyncQueueEntry qe = new SyncQueueEntry();
int matchindex=0;
System.Threading.Monitor.Enter(Q_totalint_int_);
if (!(Q_addint_.Count ==0)) {
qe.joinedentries = (int) (Q_addint_.Dequeue());
System.Threading.Monitor.Exit(Q_totalint_int_);
matchindex = 0;
goto joinlabel;
try {
Thread.Sleep(Timeout.Infinite);
} catch (ThreadInterruptedException) {}
// wake up here
matchindex = qe.pattern;
joinlabel:
switch (matchindex) {
case 0: int r = sync_p_0;
int i = sync_p_1;
int dr = (int)(qe.joinedentries);
int rp = r + dr;
if (i > 1) {return total(rp, i - 1);
}
return rp;
}
throw new System.Exception();
}
private void add(int p_0) {
Object qe = p_0;
System.Threading.Monitor.Enter(Q_totalint_int_);
if (!(Q_totalint_int_.Count ==0)) {
SyncQueueEntry sqe = (SyncQueueEntry) (Q_totalint_int_.Dequeue());
sqe.joinedentries = qe;
System.Threading.Monitor.Exit(Q_totalint_int_);
sqe.pattern = 0;
sqe.mythread.Interrupt();
return;
}
Q_addint_.Enqueue(qe);
System.Threading.Monitor.Exit(Q_totalint_int_);
return;
}
private void loop(int i) {
loopint__runner r = new loopint__runner(this,i);
}
}
}// enqueue myself and sleep;
qe.mythread = Thread.CurrentThread;
Q_totalint_int_.Enqueue(qe);
System.Threading.Monitor.Exit(Q_totalint_int_);
MS.NET days March 2002
Sum of Squares Translation
using System;
using System.Collections;
using System.Threading;
class SyncQueueEntry{
public int pattern;
public System.Threading.Thread mythread;
public System.Object joinedentries;
}
class SumOfSquares{
Queue Q_totalint_int_ = new Queue();
Queue Q_addint_ = new Queue();
class loopint__runner{
SumOfSquares parent;
int field_0;
public loopint__runner(SumOfSquares p_p,int p_0) {
parent = p_p;
field_0 = p_0;
Thread t = new Thread(new ThreadStart(this.doit));
t.Start();
}
void doit() {
parent.loopint__worker(field_0);
}
}
private void loopint__worker(int i) {
if (i >= 1) {add(i * i);
loop(i - 1);
}
}
static void Main() {
SumOfSquares s = new SumOfSquares();
int thesum = s.sum(10);
Console.WriteLine(thesum);
}
public int sum(int x) {
loop(x);
return total(0, x);
}
private int total(int sync_p_0,int sync_p_1) {
SyncQueueEntry qe = new SyncQueueEntry();
int matchindex=0;
System.Threading.Monitor.Enter(Q_totalint_int_);
if (!(Q_addint_.Count ==0)) {
qe.joinedentries = (int) (Q_addint_.Dequeue());
System.Threading.Monitor.Exit(Q_totalint_int_);
matchindex = 0;
goto joinlabel;
try {
Thread.Sleep(Timeout.Infinite);
} catch (ThreadInterruptedException) {}
// wake up here
matchindex = qe.pattern;
class SumOfSquares{
Queue Q_totalint_int_ = new Queue();
Queue Q_addint_ = new Queue();
…
joinlabel:
switch (matchindex) {
case 0: int r = sync_p_0;
int i = sync_p_1;
int dr = (int)(qe.joinedentries);
int rp = r + dr;
if (i > 1) {return total(rp, i - 1);
}
return rp;
}
throw new System.Exception();
}
private void add(int p_0) {
Object qe = p_0;
System.Threading.Monitor.Enter(Q_totalint_int_);
if (!(Q_totalint_int_.Count ==0)) {
SyncQueueEntry sqe = (SyncQueueEntry) (Q_totalint_int_.Dequeue());
sqe.joinedentries = qe;
System.Threading.Monitor.Exit(Q_totalint_int_);
sqe.pattern = 0;
sqe.mythread.Interrupt();
return;
}
Q_addint_.Enqueue(qe);
System.Threading.Monitor.Exit(Q_totalint_int_);
return;
}
private void loop(int i) {
loopint__runner r = new loopint__runner(this,i);
}
}
}// enqueue myself and sleep;
qe.mythread = Thread.CurrentThread;
Q_totalint_int_.Enqueue(qe);
System.Threading.Monitor.Exit(Q_totalint_int_);
MS.NET days March 2002
Sum of Squares Translation
using System;
using System.Collections;
using System.Threading;
class SyncQueueEntry{
public int pattern;
public System.Threading.Thread mythread;
public System.Object joinedentries;
}
class SumOfSquares{
Queue Q_totalint_int_ = new Queue();
Queue Q_addint_ = new Queue();
class loopint__runner{
SumOfSquares parent;
int field_0;
public loopint__runner(SumOfSquares p_p,int p_0) {
parent = p_p;
field_0 = p_0;
Thread t = new Thread(new ThreadStart(this.doit));
t.Start();
}
void doit() {
parent.loopint__worker(field_0);
}
}
private void loopint__worker(int i) {
if (i >= 1) {add(i * i);
loop(i - 1);
}
}
static void Main() {
SumOfSquares s = new SumOfSquares();
int thesum = s.sum(10);
Console.WriteLine(thesum);
}
public int sum(int x) {
loop(x);
return total(0, x);
}
private int total(int sync_p_0,int sync_p_1) {
SyncQueueEntry qe = new SyncQueueEntry();
int matchindex=0;
System.Threading.Monitor.Enter(Q_totalint_int_);
if (!(Q_addint_.Count ==0)) {
qe.joinedentries = (int) (Q_addint_.Dequeue());
System.Threading.Monitor.Exit(Q_totalint_int_);
matchindex = 0;
goto joinlabel;
try {
Thread.Sleep(Timeout.Infinite);
} catch (ThreadInterruptedException) {}
// wake up here
matchindex = qe.pattern;
private void add(int p_0) {
System.Threading.Monitor.Enter(Q_totalint_int_);
if (!(Q_totalint_int_.Count ==0)) {
SyncQueueEntry sqe =
(SyncQueueEntry)(Q_totalint_int_.Dequeue());
sqe.joinedentries = p_0;
System.Threading.Monitor.Exit(Q_totalint_int_);
sqe.pattern = 0;
sqe.mythread.Interrupt();
return;
}
Q_addint_.Enqueue(p_0);
System.Threading.Monitor.Exit(Q_totalint_int_);
return;
}
joinlabel:
switch (matchindex) {
case 0: int r = sync_p_0;
int i = sync_p_1;
int dr = (int)(qe.joinedentries);
int rp = r + dr;
if (i > 1) {return total(rp, i - 1);
}
return rp;
}
throw new System.Exception();
}
private void add(int p_0) {
Object qe = p_0;
System.Threading.Monitor.Enter(Q_totalint_int_);
if (!(Q_totalint_int_.Count ==0)) {
SyncQueueEntry sqe = (SyncQueueEntry) (Q_totalint_int_.Dequeue());
sqe.joinedentries = qe;
System.Threading.Monitor.Exit(Q_totalint_int_);
sqe.pattern = 0;
sqe.mythread.Interrupt();
return;
}
Q_addint_.Enqueue(qe);
System.Threading.Monitor.Exit(Q_totalint_int_);
return;
}
private void loop(int i) {
loopint__runner r = new loopint__runner(this,i);
}
}
}// enqueue myself and sleep;
qe.mythread = Thread.CurrentThread;
Q_totalint_int_.Enqueue(qe);
System.Threading.Monitor.Exit(Q_totalint_int_);
MS.NET days March 2002
Current Work

Examples and test cases
 Web
combinators, adaptive scheduler, web
services (Terraserver), active objects and
remoting (stock trader)
 Generally looking at integration with existing
mechanisms and frameworks

Language design
 Direct

syntactic support for timeouts
Solid Implementation
MS.NET days March 2002
Predictable Demo:
Dining Philosophers
waiting
to eat
eating
waiting
to eat
thinking
eating
MS.NET days March 2002
Code extract
class Room {
public Room (int size) { hasspaces(size); }
public void enter() & private async hasspaces(int n) {
if (n > 1)
hasspaces(n-1);
else
isfull();
}
public void leave() & private async hasspaces(int n) {
hasspaces(n+1);
}
public void leave() & private async isfull() {
hasspaces(1); }
}
MS.NET days March 2002
Conclusions

A clean, simple, new model for asynchronous
concurrency in C#







Declarative, local synchronization
Applicable in both local and distributed settings
Efficiently compiled to queues and automata
Easier to express and enforce concurrency
invariants
Compatible with existing constructs, though they
constrain our design somewhat
Solid foundations
Works well in practice
MS.NET days March 2002
That’s all

For more information, contact me
[email protected] or see

http://research.microsoft.com/~{nick,akenn,dsyme}
MS.NET days March 2002
TimeoutBuffer
class TimeoutBuffer {
TimeoutBuffer(int delay) {
Timer t = new Timer(new TimerCallBack(this.tick), delay);
empty();
}
async empty() & void put(Object o) {has(o);}
async empty() & void tick() {timeout();}
async timeout() & void put(Object o) {timeout();}
async timeout() & Object get() {timeout(); throw new TimeOutExn();}
async has(Object o) & Object get() {has(o); return o;}
async has(Object o) & void tick() {has(o);}
}
MS.NET days March 2002
Why only one synchronous method
in a chord?

JoCaml allows multiple synchronous methods to be
joined, as in the following rendezvous
int f(int x) & int g(int y) {
return y to f;
return x to y;
}

But in which thread does the body run? In C#, thread
identity is “very” observable, since threads are the
holders of particular re-entrant locks. So we rule this out
in the interests of keeping & commutative. (Of course, it’s
still easy to code up an asymmetric rendezvous in
Polyphonic C#.)
MS.NET days March 2002
The problem with inheritance
class C {
virtual void f() & virtual async g() {…}
virtual void f() & virtual async h() {…}
}
class D : C {
override async g() { …}
}


We’ve “half” overridden f
Too easy to create deadlock or async leakage
void m(C x) { x.g(); x.f();}
…
m(new D());
MS.NET days March 2002
The Inheritance Restriction

Inheritance may be used as usual, with a restriction
to prevent the partial overriding of patterns:

For a given class, two methods f ang g are co-declared if
there is a chord in which they are both declared.

Whenever a method is overriden,
every codeclared method must also be overriden.
Hence, the compiler rejects patterns such as

public virtual void f() & private async g() {…}

In general, inheritance and concurrency do not mix well.
Our restriction is simple; it could be made less restrictive.
MS.NET days March 2002
Types etc.


async is a subtype of void
Allow covariant return types on those two:
 An async method may override a void one
 A void delegate may be created from an async
method
 An async method may implement a void method in
an interface

async methods are automatically given the
[OneWay] attribute, so remote calls are nonblocking
MS.NET days March 2002
Compiling chords

Since synchronization is statically defined for every class,
we can compile it efficiently (state automata).




We cache the synchronization state in a single word.
We use a bit for every (polyphonic) method.
We pre-compute bitmasks for every pattern.
Simple version just looks up queue state directly

For every polyphonic method, we allocate a queue
for storing delayed threads (or pending messages).

The compilation scheme can be optimized:



Some states are not reachable.
Empty messages only need to be counted.
The content of (single, private) messages can be stored in local
variables. Requires some analysis.
MS.NET days March 2002
Implementation issues

When compiling a polyphonic class, we add




The code handling the join patterns must be thread-safe.



private fields for the synchronization state and the queues;
private methods for the body of asynchronous patterns;
some initialization code.
We use a single lock (from the first queue) to protect the state word
and all queues.
This is independent from the object lock and only held briefly whilst
queues are being manipulated.
For asynchronous methods, there’s an auxiliary class for
storing the pending messages.
MS.NET days March 2002
Adding synchronization code

When an asynchronous method is called:

add the message content to the queue;
 if the method bit is 0, set it to 1 in the synchronization state
and check for a completed pattern:



For every pattern containing the method,
compare the new state to the pattern mask.
If there is a match, then wake up a delayed thread
(or start a new thread if the pattern is entirely asynchronous).
When a synchronous method is called:

if the method bit is 0, set it to 1 in the synchronization state
and check for a completed pattern



For every pattern containing the method,
compare the new state to the pattern mask.
If there is a match, dequeue the asynchronous arguments,
adjust the mask, and run the body for that pattern.
Otherwise, enqueue the thread, go to sleep, then retry.
MS.NET days March 2002

Download Report