Index: libcfa/src/bits/collection.hfa
===================================================================
--- libcfa/src/bits/collection.hfa	(revision b3ed43a33d4dacc657b93e882c9a2295be8888f2)
+++ libcfa/src/bits/collection.hfa	(revision b3ed43a33d4dacc657b93e882c9a2295be8888f2)
@@ -0,0 +1,57 @@
+#pragma once
+
+struct Colable {
+	Colable * next;										// next node in the list
+	// invariant: (next != 0) <=> listed()
+};
+
+inline {
+	void ?{}( Colable & co ) with( co ) {
+		next = 0p;
+	} // post: ! listed()
+
+	// return true iff *this is an element of a collection
+	bool listed( Colable & co ) with( co ) {			// pre: this != 0
+		return next != 0;
+	}
+
+	Colable * getNext( Colable & co ) with( co ) {
+		return next;
+	}
+
+	Colable *& Next( Colable * cp ) {
+		return cp->next;
+	}
+} // distribution
+
+struct Collection {
+	void * root;										// pointer to root element of list
+};
+
+inline {
+	// class invariant: root == 0 & empty() | *root in *this
+	void ?{}( Collection &, const Collection & ) = void; // no copy
+	Collection & ?=?( const Collection & ) = void;		// no assignment
+
+	void ?{}( Collection & collection ) with( collection ) {	
+		root = 0p;
+	} // post: empty()
+
+	bool empty( Collection & collection ) with( collection ) { // 0 <=> *this contains no elements
+		return root == 0p;
+	}
+	void * head( Collection & collection ) with( collection ) {
+		return root;
+	} // post: empty() & head() == 0 | !empty() & head() in *this
+} // distribution
+
+
+struct ColIter {
+	void * curr;										// element to be returned by >>
+};
+
+inline {
+	void ?{}( ColIter & colIter ) with( colIter ) {
+		curr = 0p;
+	} // post: elts = null
+} // distribution
Index: libcfa/src/bits/queue.hfa
===================================================================
--- libcfa/src/bits/queue.hfa	(revision b3ed43a33d4dacc657b93e882c9a2295be8888f2)
+++ libcfa/src/bits/queue.hfa	(revision b3ed43a33d4dacc657b93e882c9a2295be8888f2)
@@ -0,0 +1,203 @@
+#pragma once
+
+#include "collection.hfa"
+
+forall( dtype T ) {
+	struct Queue {
+		inline Collection;								// Plan 9 inheritance
+		T * last;										// last element, or 0 if queue is empty.
+	};
+
+	inline {
+		// wrappers to make Collection have T
+		T * head( Queue(T) & q ) with( q ) {
+			return (T *)head( (Collection &)q );
+		} // post: empty() & head() == 0 | !empty() & head() in *q
+
+		bool empty( Queue(T) & q ) with( q ) {			// 0 <=> *q contains no elements
+			return empty( (Collection &)q );
+		}
+
+		bool listed( T * n ) {
+			return Next( (Colable *)n ) != 0;
+		}
+
+		T *& Next( T * n ) {
+			return (T *)Next( (Colable *)n );
+		}
+
+		T * Root( Queue(T) & q ) with( q ) {
+			return (T *)root;
+		}
+
+		void ?{}( Queue(T) &, const Queue(T) & ) = void; // no copy
+		Queue(T) & ?=?( const Queue(T) & ) = void;		// no assignment
+
+		void ?{}( Queue(T) & q ) with( q ) {
+			((Collection &)q){};
+			last = 0p;
+		} // post: empty()
+
+		T * tail( Queue(T) & q ) with( q ) {
+			return last;
+		}
+
+		T * succ( Queue(T) & q, T * n ) with( q ) {		// pre: *n in *q
+#ifdef __CFA_DEBUG__
+			if ( ! listed( n ) ) abort( "(Queue &)%p.succ( %p ) : Node is not on a list.", &q, n );
+#endif // __CFA_DEBUG__
+			return (Next( n ) == n) ? 0p : Next( n );
+		} // post: n == tail() & succ(n) == 0 | n != tail() & *succ(n) in *q
+
+		void addHead( Queue(T) & q, T * n ) with( q ) {
+#ifdef __CFA_DEBUG__
+			if ( listed( n ) ) abort( "(Queue &)%p.addHead( %p ) : Node is already on another list.", &q, n );
+#endif // __CFA_DEBUG__
+			if ( last ) {
+				Next( n ) = Root( q );
+				q.root = n;
+			} else {
+				root = last = n;
+				Next( n ) = n;							// last node points to itself
+			}
+		}
+
+		void addTail( Queue(T) & q, T * n ) with( q ) {
+#ifdef __CFA_DEBUG__
+			if ( listed( n ) ) abort( "(Queue &)%p.addTail( %p ) : Node is already on another list.", &q, n );
+#endif // __CFA_DEBUG__
+			if ( last ) Next( last ) = n;
+			else root = n;
+			last = n;
+			Next( n ) = n;								// last node points to itself
+		}
+
+		void add( Queue(T) & q, T * n ) with( q ) {
+			addTail( q, n );
+		}
+
+		T * dropHead( Queue(T) & q ) with( q ) {
+			T * t = head( q );
+			if ( root ) {
+				root = Next( root );
+				if ( Root( q ) == t ) {
+					root = last = 0p;					// only one element
+				}
+				Next( t ) = 0p;
+			}
+			return t;
+		}
+
+		T * drop( Queue(T) & q ) with( q ) {
+			return dropHead( q );
+		}
+
+		void remove( Queue(T) & q, T * n ) with( q ) {	// O(n)
+#ifdef __CFA_DEBUG__
+			if ( ! listed( (Colable &)(*n) ) ) abort( "(Queue &)%p.remove( %p ) : Node is not on a list.", &q, n );
+#endif // __CFA_DEBUG__
+			T * prev = 0;
+			T * curr = (T *)root;
+			for ( ;; ) {
+				if (n == curr) {						// found => remove
+					if ((T *)root == n) {
+						dropHead( q );
+					} else if (last == n) {
+						last = prev;
+						Next( last ) = last;
+					} else {
+						Next( prev ) = Next( curr );
+					}
+					Next( n ) = 0p;
+					break;
+				}
+#ifdef __CFA_DEBUG__
+				// not found => error
+				if (curr == last) abort( "(Queue &)%p.remove( %p ) : Node is not in list.", &q, n );
+#endif // __CFA_DEBUG__
+				prev = curr;
+				curr = Next( curr );
+			}
+		} // post: ! listed( n )
+
+		T * dropTail( Queue(T) & q ) with( q ) { // O(n)
+			T * n = tail( q );
+			return n ? remove( q, n ), n : 0p;
+		}
+
+		// Transfer the "from" list to the end of queue sequence; the "from" list is empty after the transfer.
+		void transfer( Queue(T) & q, Queue(T) & from ) with( q ) {
+			if ( empty( from ) ) return;				// "from" list empty ?
+			if ( empty( q ) ) {							// "to" list empty ?
+				root = from.root;
+			} else {									// "to" list not empty
+				Next( last ) = Root( from );
+			}
+			last = from.last;
+			from.root = from.last = 0p;					// mark "from" list empty
+		}
+
+		// Transfer the "from" list up to node "n" to the end of queue list; the "from" list becomes the list after node "n".
+		// Node "n" must be in the "from" list.
+		void split( Queue(T) & q, Queue(T) & from, T * n ) with( q ) {
+#ifdef __CFA_DEBUG__
+			if ( ! listed( (Colable &)(*n) ) ) abort( "(Queue &)%p.split( %p ) : Node is not on a list.", &q, n );
+#endif // __CFA_DEBUG__
+			Queue(T) to;
+			to.root = from.root;						// start of "to" list
+			to.last = n;								// end of "to" list
+			from.root = Next( n );						// start of "from" list
+			if ( n == Root( from ) ) {					// last node in list ?
+				from.root = from.last = 0p;				// mark "from" list empty
+			} else {
+				Next( n ) = n;							// fix end of "to" list
+			}
+			transfer( q, to );
+		}
+	} // distribution
+} // distribution
+
+forall( dtype T ) {
+	struct QueueIter {
+		inline ColIter;									// Plan 9 inheritance
+	};	
+
+	inline {
+		// wrappers to make ColIter have T
+		T * Curr( QueueIter(T) & qi ) with( qi ) {
+			return (T *)curr;
+		}
+
+		void ?{}( QueueIter(T) & qi ) with( qi ) {
+			((ColIter &)qi){};
+		} // post: curr == 0p
+
+		// create an iterator active in Queue q
+		void ?{}( QueueIter(T) & qi, Queue(T) & q ) with( qi ) {
+			curr = head( q );
+		} // post: curr = {e in q}
+
+		void ?{}( QueueIter(T) & qi, T * start ) with( qi ) {
+			curr = start;
+		} // post: curr = {e in q}
+
+		// make existing iterator active in Queue q
+		void over( QueueIter(T) & qi, Queue(T) & q ) with( qi ) {
+			curr = head( q );
+		} // post: curr = {e in q}
+
+		bool ?>>?( QueueIter(T) & qi, T *& tp ) with( qi ) {
+			if ( curr ) {
+				tp = Curr( qi );
+				T * n = Next( Curr( qi ) );
+				curr = (n == Curr( qi ) ) ? 0p : n;
+			} else tp = 0p;
+			return tp != 0p;
+		}
+		// post: elts == null & !operator>>(tp) | elts != null & *tp' in elts & elts' == elts - *tp & operator>>(tp)
+	} // distribution
+} // distribution
+
+// Local Variables: //
+// compile-command: "make install" //
+// End: //
Index: libcfa/src/bits/queue_example.cfa
===================================================================
--- libcfa/src/bits/queue_example.cfa	(revision b3ed43a33d4dacc657b93e882c9a2295be8888f2)
+++ libcfa/src/bits/queue_example.cfa	(revision b3ed43a33d4dacc657b93e882c9a2295be8888f2)
@@ -0,0 +1,113 @@
+#include <fstream.hfa>
+#include <stdlib.hfa>									// new, delete
+#include "queue.hfa"
+
+int main() {
+	// Fred test
+
+	struct Fred {
+		inline Colable;									// Plan 9 inheritance
+		int i;
+	};
+	void ?{}( Fred & fred ) { abort(); }
+	void ?{}( Fred & fred, int p ) with( fred ) {
+		i = p;
+	}
+
+	Queue(Fred) fred;
+	QueueIter(Fred) fredIter = { fred };
+	Fred * f;
+	int i;
+
+	sout | nlOff;										// turn off auto newline
+
+	for ( ; fredIter >> f; ) {							// empty list
+		sout | f->i | ' ';
+	}
+	sout | "empty" | nl;
+	
+	for ( i = 0; i < 10; i += 1 ) {
+		add( fred, new( 2 * i ) );
+	}
+
+	for ( over( fredIter, fred ); fredIter >> f; ) {
+		sout | f->i | ' ';
+	}
+	sout | nl;
+
+	for ( i = 0; i < 9; i += 1 ) {
+		delete( drop( fred ) );
+	}
+
+	for ( over( fredIter, fred ); fredIter >> f; ) {
+		sout | f->i | ' ';
+	}
+	sout | nl;
+	
+	for ( i = 0; i < 10; i += 1 ) {
+		add( fred, new( 2 * i + 1 ) );
+	}
+	for ( over( fredIter, fred ); fredIter >> f; ) {
+		sout | f->i | ' ';
+	}
+	sout | nl;
+
+	for ( over( fredIter, fred ); fredIter >> f; ) {
+		delete( f );
+	}
+
+	// Mary test
+
+	struct Mary {
+		inline Fred;									// Plan 9 inheritance
+		int j;
+	};
+	void ?{}( Mary & mary ) { abort(); }
+	void ?{}( Mary & mary, int p ) with( mary ) {
+		((Fred &)mary){ p };
+		j = i = p;
+	}
+
+	Queue(Mary) mary;
+	QueueIter(Mary) maryIter = { mary };
+	Mary * m;
+
+	for ( ; maryIter >> m; ) {							// empty list
+		sout | m->i | m->j | ' ';
+	}
+	sout | "empty" | nl;
+	
+	for ( i = 0; i < 10; i += 1 ) {
+		add( mary, new( 2 * i ) );
+	}
+
+	for ( over( maryIter, mary ); maryIter >> m; ) {
+		sout | m->i | m->j | ' ';
+	}
+	sout | nl;
+	
+	for ( i = 0; i < 9; i += 1 ) {
+		delete( drop( mary ) );
+	}
+
+	for ( over( maryIter, mary ); maryIter >> m; ) {
+		sout | m->i | m->j | ' ';
+	}
+	sout | nl;
+	
+	for ( i = 0; i < 10; i += 1 ) {
+		add( mary, new( 2 * i + 1 ) );
+	}
+	for ( over( maryIter, mary ); maryIter >> m; ) {
+		sout | m->i | m->j | ' ';
+	}
+	sout | nl;
+
+	for ( over( maryIter, mary ); maryIter >> m; ) {
+		delete( m );
+	}
+}
+
+// Local Variables: //
+// compile-command: "cfa queue_example.cfa" //
+// End: //
Index: libcfa/src/bits/sequence.hfa
===================================================================
--- libcfa/src/bits/sequence.hfa	(revision b3ed43a33d4dacc657b93e882c9a2295be8888f2)
+++ libcfa/src/bits/sequence.hfa	(revision b3ed43a33d4dacc657b93e882c9a2295be8888f2)
@@ -0,0 +1,304 @@
+#pragma once
+
+#include "collection.hfa"
+
+struct Seqable {
+	inline Colable;
+	Seqable * back;										// pointer to previous node in the list
+};
+
+inline {
+	void ?{}( Seqable & sq ) with( sq ) {
+		((Colable & ) sq){};
+		back = 0p;
+	} // post: ! listed()
+
+	Seqable * getBack( Seqable & sq ) with( sq ) {
+		return back;
+	}
+
+	Seqable *& Back( Seqable * sq ) {
+		return sq->back;
+	}
+} // distribution
+
+forall( dtype T ) {
+	struct Sequence {
+		inline Collection;								// Plan 9 inheritance
+	};
+
+	inline {
+		// wrappers to make Collection have T
+		T * head( Sequence(T) & s ) with( s ) {
+			return (T *)head( (Collection &)s );
+		} // post: empty() & head() == 0 | !empty() & head() in *s
+
+		bool empty( Sequence(T) & s ) with( s ) {		// 0 <=> *s contains no elements
+			return empty( (Collection &)s );
+		}
+
+		bool listed( T * n ) {
+			return Next( (Colable *)n ) != 0;
+		}
+
+		T *& Next( T * n ) {
+			return (T *)Next( (Colable *)n );
+		}
+
+		T *& Back( T * n ) {
+			return (T *)Back( (Seqable *)n );
+		}
+
+		T * Root( Sequence(T) & s ) with( s ) {
+			return (T *)root;
+		}
+
+		void ?{}( Sequence(T) &, const Sequence(T) & ) = void; // no copy
+		Sequence(T) & ?=?( const Sequence(T) & ) = void; // no assignment
+
+		void ?{}( Sequence(T) & s ) with( s ) {	
+			((Collection &) s){};
+		}	// post: isEmpty().
+
+		// Return a pointer to the last sequence element, without removing it.	
+		T * tail( Sequence(T) & s ) with( s ) {
+			return root ? (T *)Back( Root( s ) ) : 0p;	// needs cast?
+		}	// post: empty() & tail() == 0 | !empty() & tail() in *s
+
+		// Return a pointer to the element after *n, or 0p if there isn't one.
+		T * succ( Sequence(T) & s, T * n ) with( s ) {	// pre: *n in *s
+#ifdef __CFA_DEBUG__
+			if ( ! listed( n ) ) abort( "(Sequence &)%p.succ( %p ) : Node is not on a list.", &s, n );
+#endif // __CFA_DEBUG__
+			return Next( n ) == Root( s ) ? 0p : Next( n );
+		}	// post: n == tail() & succ(n) == 0 | n != tail() & *succ(n) in *s
+
+		// Return a pointer to the element before *n, or 0p if there isn't one.
+		T * pred( Sequence(T) & s, T * n ) with( s ) {	// pre: *n in *s
+#ifdef __CFA_DEBUG__
+			if ( ! listed( n ) ) abort( "(Sequence &)%p.pred( %p ) : Node is not on a list.", &s, n );
+#endif // __CFA_DEBUG__
+			return n == Root( s ) ? 0p : Back( n );
+		}	// post: n == head() & head(n) == 0 | n != head() & *pred(n) in *s
+
+
+		// Insert *n into the sequence before *bef, or at the end if bef == 0.
+		void insertBef( Sequence(T) & s, T * n, T * bef ) with( s ) { // pre: !n->listed() & *bef in *s
+#ifdef __CFA_DEBUG__
+			if ( listed( n ) ) abort( "(Sequence &)%p.insertBef( %p, %p ) : Node is already on another list.", &s, n, bef );
+#endif // __CFA_DEBUG__
+			if ( bef == Root( s ) ) {					// must change root
+				if ( root ) {
+					Next( n ) = Root( s );
+					Back( n ) = Back( Root( s ) );
+					// inserted node must be consistent before it is seen
+					asm( "" : : : "memory" );			// prevent code movement across barrier
+					Back( Root( s ) ) = n;
+					Next( Back( n ) ) = n;
+				} else {
+					Next( n ) = n;
+					Back( n ) = n;
+				} // if
+				// inserted node must be consistent before it is seen
+				asm( "" : : : "memory" );				// prevent code movement across barrier
+				root = n;
+			} else {
+				if ( ! bef ) bef = Root( s );
+				Next( n ) = bef;
+				Back( n ) = Back( bef );
+				// inserted node must be consistent before it is seen
+				asm( "" : : : "memory" );				// prevent code movement across barrier
+				Back( bef ) = n;
+				Next( Back( n ) ) = n;
+			} // if
+		}	// post: n->listed() & *n in *s & succ(n) == bef
+
+
+		// Insert *n into the sequence after *aft, or at the beginning if aft == 0.
+		void insertAft( Sequence(T) & s, T *aft, T *n ) with( s ) {	// pre: !n->listed() & *aft in *s
+#ifdef __CFA_DEBUG__
+			if ( listed( n ) ) abort( "(Sequence &)%p.insertAft( %p, %p ) : Node is already on another list.", &s, aft, n );
+#endif // __CFA_DEBUG__
+			if ( ! aft ) {								// must change root
+				if ( root ) {
+					Next( n ) = Root( s );
+					Back( n ) = Back( Root( s ) );
+					// inserted node must be consistent before it is seen
+					asm( "" : : : "memory" );			// prevent code movement across barrier
+					Back( Root( s ) ) = n;
+					Next( Back( n ) ) = n;
+				} else {
+					Next( n ) = n;
+					Back( n ) = n;
+				} // if
+				asm( "" : : : "memory" );				// prevent code movement across barrier
+				root = n;
+			} else {
+				Next( n ) = Next( aft );
+				Back( n ) = aft;
+				// inserted node must be consistent before it is seen
+				asm( "" : : : "memory" );				// prevent code movement across barrier
+				Back( Next( n ) ) = n;
+				Next( aft ) = n;
+			} // if
+		}	  // post: n->listed() & *n in *s & succ(n) == bef
+		
+		// pre: n->listed() & *n in *s
+		void remove( Sequence(T) & s, T *n ) with( s ) { // O(1)
+#ifdef __CFA_DEBUG__
+			if ( ! listed( n ) ) abort( "(Sequence &)%p.remove( %p ) : Node is not on a list.", &s, n );
+#endif // __CFA_DEBUG__
+			if ( n == Root( s ) ) {
+				if ( Next( Root( s ) ) == Root( s ) ) root = 0p;
+				else root = Next( Root(s ) );
+			} // if
+			Back( Next( n ) ) = Back( n );
+			Next( Back( n ) ) = Next( n );
+			Next( n ) = Back( n ) = 0p;
+		}							// post: !n->listed().
+
+		// Add an element to the head of the sequence.
+		void addHead( Sequence(T) & s, T *n ) {			// pre: !n->listed(); post: n->listed() & head() == n
+			insertAft( s, 0, n );
+		}
+		// Add an element to the tail of the sequence.
+		void addTail( Sequence(T) & s, T *n ) {			// pre: !n->listed(); post: n->listed() & head() == n
+			insertBef( s, n, 0 );
+		}
+		// Add an element to the tail of the sequence.
+		void add( Sequence(T) & s, T *n ) {				// pre: !n->listed(); post: n->listed() & head() == n
+			addTail( s, n );
+		}
+		// Remove and return the head element in the sequence.
+		T * dropHead( Sequence(T) & s ) {
+			T * n = head( s );
+			return n ? remove( s, n ), n : 0p;
+		}
+		// Remove and return the head element in the sequence.
+		T * drop( Sequence(T) & s ) {
+			return dropHead( s );
+		}
+		// Remove and return the tail element in the sequence.
+		T * dropTail( Sequence(T) & s ) {
+			T * n = tail( s );
+			return n ? remove( s, n ), n : 0p;
+		}
+
+		// Transfer the "from" list to the end of s sequence; the "from" list is empty after the transfer.
+		void transfer( Sequence(T) & s, Sequence(T) & from ) with( s ) {
+			if ( empty( from ) ) return;				// "from" list empty ?
+			if ( empty( s ) ) {							// "to" list empty ?
+				root = from.root;
+			} else {									// "to" list not empty
+				T * toEnd = Back( Root( s ) );
+				T * fromEnd = Back( Root( from ) );
+				Back( root ) = fromEnd;
+				Next( fromEnd ) = Root( s );
+				Back( from.root ) = toEnd;
+				Next( toEnd ) = Root( from );
+			} // if
+			from.root = 0p;								// mark "from" list empty
+		}
+
+		// Transfer the "from" list up to node "n" to the end of s list; the "from" list becomes the sequence after node "n".
+		// Node "n" must be in the "from" list.
+		void split( Sequence(T) & s, Sequence(T) & from, T * n ) with( s ) {
+#ifdef __CFA_DEBUG__
+			if ( ! listed( n ) ) abort( "(Sequence &)%p.split( %p ) : Node is not on a list.", &s, n );
+#endif // __CFA_DEBUG__
+			Sequence(T) to;
+			to.root = from.root;						// start of "to" list
+			from.root = Next( n );						// start of "from" list
+			if ( to.root == from.root ) {				// last node in list ?
+				from.root = 0p;							// mark "from" list empty
+			} else {
+				Back( Root( from ) ) = Back( Root( to ) ); // fix "from" list
+		 		Next( Back( Root( to ) ) ) = Root( from );
+				Next( n ) = Root( to );					// fix "to" list
+				Back( Root( to ) ) = n;
+			} // if
+			transfer( s, to );
+		}
+	} // distribution
+} // distribution
+
+forall( dtype T ) {
+	// SeqIter(T) is used to iterate over a Sequence(T) in head-to-tail order.
+	struct SeqIter {
+		inline ColIter;
+		Sequence(T) * seq;
+	};
+
+	inline {
+		// wrappers to make ColIter have T
+		T * Curr( SeqIter(T) & si ) with( si ) {
+			return (T *)curr;
+		}
+
+		void ?{}( SeqIter(T) & si ) with( si ) {	
+			((ColIter &) si){};
+			seq = 0p;
+		} // post: elts = null.
+
+		void ?{}( SeqIter(T) & si, Sequence(T) & s ) with( si ) {
+			((ColIter &) si){};
+			seq = &s;
+		} // post: elts = null.
+		
+		void over( SeqIter(T) & si, Sequence(T) & s ) with( si ) {
+			seq = &s;
+			curr = head( s );
+		} // post: elts = {e in s}.
+
+		bool ?>>?( SeqIter(T) & si, T *& tp ) with( si ) {
+			if ( curr ) {
+				tp = Curr( si );
+				T *n = succ( *seq, Curr( si ) );
+				curr = n == head( *seq ) ? 0p : n;
+			} else tp = 0p;
+			return tp != 0p;
+		}
+	} // distribution
+
+
+	// A SeqIterRev(T) is used to iterate over a Sequence(T) in tail-to-head order.
+	struct SeqIterRev {
+		inline ColIter;
+		Sequence(T) * seq;
+	};
+
+	inline {
+		// wrappers to make ColIter have T
+		T * Curr( SeqIterRev(T) & si ) with( si ) {
+			return (T *)curr;
+		}
+
+		void ?{}( SeqIterRev(T) & si ) with( si ) {	
+			((ColIter &) si){};
+			seq = 0p;
+		} // post: elts = null.
+
+		void ?{}( SeqIterRev(T) & si, Sequence(T) & s ) with( si ) {	
+			((ColIter &) si){};
+			seq = &s;
+		} // post: elts = null.
+		
+		void over( SeqIterRev(T) & si, Sequence(T) & s ) with( si ) {
+			seq = &s;
+			curr = tail( s );
+		} // post: elts = {e in s}.
+
+		bool ?>>?( SeqIterRev(T) & si, T *&tp ) with( si ) {
+			if ( curr ) {
+				tp = Curr( si );
+				T *n = pred( *seq, Curr( si ) );
+				curr = n == tail( *seq ) ? 0p : n;
+			} else tp = 0p;
+			return tp != 0p;
+		}
+	} // distribution
+} // distribution
+
+// Local Variables: //
+// compile-command: "make install" //
+// End: //
Index: libcfa/src/bits/sequence_example.cfa
===================================================================
--- libcfa/src/bits/sequence_example.cfa	(revision b3ed43a33d4dacc657b93e882c9a2295be8888f2)
+++ libcfa/src/bits/sequence_example.cfa	(revision b3ed43a33d4dacc657b93e882c9a2295be8888f2)
@@ -0,0 +1,143 @@
+#include <fstream.hfa>
+#include <stdlib.hfa>									// new, delete
+#include "sequence.hfa"
+
+int main() {
+	// Fred test
+
+	struct Fred {
+		inline Seqable;									// Plan 9 inheritance
+		int i;
+	};
+	void ?{}( Fred & fred ) { abort(); }
+	void ?{}( Fred & fred, int p ) with( fred ) {
+		i = p;
+	}
+
+	Sequence(Fred) fred;
+	SeqIter(Fred) fredIter = { fred };
+	Fred * f;
+	int i;
+
+	sout | nlOff;										// turn off auto newline
+
+	for ( ; fredIter >> f; ) {							// empty list
+		sout | f->i | ' ';
+	}
+	sout | "empty" | nl;
+	
+	for ( i = 0; i < 10; i += 1 ) {
+		add( fred, new( 2 * i ) );
+	}
+
+	for ( over( fredIter, fred ); fredIter >> f; ) {
+		sout | f->i | ' ';
+	}
+	sout | nl;
+
+	for ( i = 0; i < 9; i += 1 ) {
+		delete( dropHead( fred ) );
+	}
+
+	for ( over( fredIter, fred ); fredIter >> f; ) {
+		sout | f->i | ' ';
+	}
+	sout | nl;
+	
+	for ( i = 0; i < 10; i += 1 ) {
+		addTail( fred, new( 2 * i + 1 ) );
+	}
+	for ( over( fredIter, fred ); fredIter >> f; ) {
+		sout | f->i | ' ';
+	}
+	sout | nl;
+
+	for ( i = 0; i < 9; i += 1 ) {
+		delete( dropTail( fred ) );
+	}
+	for ( over( fredIter, fred ); fredIter >> f; ) {
+		sout | f->i | ' ';
+	}
+	sout | nl;
+
+	for ( over( fredIter, fred ); fredIter >> f; ) {
+		delete( f );
+	}
+
+	// Mary test
+
+	struct Mary {
+		inline Fred;									// Plan 9 inheritance
+		int j;
+	};
+	void ?{}( Mary & mary ) { abort(); }
+	void ?{}( Mary & mary, int p ) with( mary ) {
+		((Fred &)mary){ p };
+		j = p;
+	}
+
+	Sequence(Mary) mary;
+	Sequence(Mary) baz;
+	SeqIter(Mary) maryIter = { mary };
+	Mary * m;
+
+	for ( ; maryIter >> m; ) {							// empty list
+		sout | m->i | m->j | ' ';
+	}
+	sout | "empty" | nl;
+	
+	for ( i = 0; i < 10; i += 1 ) {
+		add( mary, new( 2 * i ) );
+		add( baz, new( 2 * i ) );
+	}
+
+	for ( over( maryIter, mary ); maryIter >> m; ) {
+		sout | m->i | m->j | ' ';
+	}
+	sout | nl;
+	
+	for ( i = 0; i < 9; i += 1 ) {
+		delete( dropHead( mary ) );
+	}
+
+	for ( over( maryIter, mary ); maryIter >> m; ) {
+		sout | m->i | m->j | ' ';
+	}
+	sout | nl;
+	
+	for ( i = 0; i < 10; i += 1 ) {
+		addTail( mary, new( 2 * i + 1 ) );
+	}
+	for ( over( maryIter, mary ); maryIter >> m; ) {
+		sout | m->i | m->j | ' ';
+	}
+	sout | nl;
+
+	for ( i = 0; i < 9; i += 1 ) {
+		delete( dropTail( mary ) );
+	}
+	for ( over( maryIter, mary ); maryIter >> m; ) {
+		sout | m->i | m->j | ' ';
+	}
+	sout | nl;
+
+	transfer( mary, baz );
+
+	for ( over( maryIter, baz ); maryIter >> m; ) {
+		sout | m->i | m->j | ' ';
+	}
+	sout | "empty" | nl;
+
+	for ( over( maryIter, mary ); maryIter >> m; ) {
+		sout | m->i | m->j | ' ';
+	}
+	sout | nl;
+
+	for ( over( maryIter, mary ); maryIter >> m; ) {
+		delete( m );
+	}
+}
+
+// Local Variables: //
+// compile-command: "cfa sequence_example.cc" //
+// End: //
Index: libcfa/src/bits/stack.hfa
===================================================================
--- libcfa/src/bits/stack.hfa	(revision b3ed43a33d4dacc657b93e882c9a2295be8888f2)
+++ libcfa/src/bits/stack.hfa	(revision b3ed43a33d4dacc657b93e882c9a2295be8888f2)
@@ -0,0 +1,114 @@
+#pragma once
+
+#include "collection.hfa"
+
+forall( dtype T ) {
+	struct Stack {
+		inline Collection;								// Plan 9 inheritance
+	};
+
+	inline {
+		// wrappers to make Collection have T
+		T * head( Stack(T) & s ) with( s ) {
+			return (T *)head( (Collection &)s );
+		} // post: empty() & head() == 0 | !empty() & head() in *this
+
+		bool empty( Stack(T) & s ) with( s ) {			// 0 <=> *this contains no elements
+			return empty( (Collection &)s );
+		}
+
+		T *& Next( T * n ) {
+			return (T *)Next( (Colable *)n );
+		}
+
+		T * Root( Stack(T) & s ) with( s ) {
+			return (T *)root;
+		}
+
+		void ?{}( Stack(T) &, const Stack(T) & ) = void; // no copy
+		Stack(T) & ?=?( const Stack(T) & ) = void;		// no assignment
+
+		void ?{}( Stack(T) & s ) with( s ) {
+			((Collection &)s){};
+		} // post: empty()
+
+		T * top( Stack(T) & s ) with( s ) {
+			return head( s );
+		}
+
+		void addHead( Stack(T) & s, T * n ) with( s ) {
+#ifdef __CFA_DEBUG__
+			if ( listed( (Colable &)(*n) ) ) abort( "(Stack &)%p.addHead( %p ) : Node is already on another list.", &s, n );
+#endif // __CFA_DEBUG__
+			Next( n ) = Root( s ) ? Root( s ) : n;
+			root = n;
+		}
+
+		void add( Stack(T) & s, T * n ) with( s ) {
+			addHead( s, n );
+		}
+
+		void push( Stack(T) & s, T * n ) with( s ) {
+			addHead( s, n );
+		}
+
+		T * drop( Stack(T) & s ) with( s ) {
+			T * t = head( s );
+			if ( root ) {
+				root = ( T *)Next(root);
+				if ( Root( s ) == t ) root = 0p;		// only one element ?
+				Next( t ) = 0p;
+			} // if
+			return t;
+		}
+
+		T * pop( Stack(T) & s ) with( s ) {
+			return drop( s );
+		}
+	} // distribution
+} // distribution
+
+
+forall( dtype T ) {
+	struct StackIter {
+		inline ColIter;									// Plan 9 inheritance
+	};	
+
+	inline {
+		// wrappers to make ColIter have T
+		T * Curr( StackIter(T) & si ) with( si ) {
+			return (T *)curr;
+		}
+
+		void ?{}( StackIter(T) & si ) with( si ) {
+			((ColIter &)si){};
+		} // post: curr == 0p
+
+		// create an iterator active in Stack s
+		void ?{}( StackIter(T) & si, Stack(T) & s ) with( si ) {
+			curr = head( s );
+		} // post: curr = {e in s}
+
+		void ?{}( StackIter(T) & si, T * start ) with( si ) {
+			curr = start;
+		} // post: curr = {e in s}
+
+		// make existing iterator active in Stack q
+		void over( StackIter(T) & si, Stack(T) & s ) with( si ) {
+			curr = head( s );
+		} // post: curr = {e in s}
+
+		bool ?>>?( StackIter(T) & si, T *& tp ) with( si ) {
+			if ( curr ) {
+				tp = Curr( si );
+				T * n = Next( Curr( si ) );
+				curr = (n == Curr( si ) ) ? 0p : n;
+			} else tp = 0p;
+			return tp != 0p;
+		}
+	} // distribution
+} // distribution
+
+// Local Variables: //
+// compile-command: "make install" //
+// End: //
Index: libcfa/src/bits/stack_example.cfa
===================================================================
--- libcfa/src/bits/stack_example.cfa	(revision b3ed43a33d4dacc657b93e882c9a2295be8888f2)
+++ libcfa/src/bits/stack_example.cfa	(revision b3ed43a33d4dacc657b93e882c9a2295be8888f2)
@@ -0,0 +1,113 @@
+#include <fstream.hfa>
+#include <stdlib.hfa>									// new, delete
+#include "stack.hfa"
+
+int main() {
+	// Fred test
+
+	struct Fred {
+		inline Colable;									// Plan 9 inheritance
+		int i;
+	};
+	void ?{}( Fred & fred ) { abort(); }
+	void ?{}( Fred & fred, int p ) with( fred ) {
+		i = p;
+	}
+
+	Stack(Fred) fred;
+	StackIter(Fred) fredIter = { fred };
+	Fred * f;
+	int i;
+
+	sout | nlOff;										// turn off auto newline
+
+	for ( ; fredIter >> f; ) {							// empty list
+		sout | f->i | ' ';
+	}
+	sout | "empty" | nl;
+	
+	for ( i = 0; i < 10; i += 1 ) {
+		push( fred, new( 2 * i ) );
+	}
+
+	for ( over( fredIter, fred ); fredIter >> f; ) {
+		sout | f->i | ' ';
+	}
+	sout | nl;
+	
+	for ( i = 0; i < 9; i += 1 ) {
+		delete( pop( fred ) );
+	}
+
+	for ( over( fredIter, fred ); fredIter >> f; ) {
+		sout | f->i | ' ';
+	}
+	sout | nl;
+	
+	for ( i = 0; i < 10; i += 1 ) {
+		push( fred, new( 2 * i + 1 ) );
+	}
+	for ( over( fredIter, fred ); fredIter >> f; ) {
+		sout | f->i | ' ';
+	}
+	sout | nl;
+
+	for ( over( fredIter, fred ); fredIter >> f; ) {
+		delete( f );
+	}
+
+	// Mary test
+
+	struct Mary {
+		inline Fred;									// Plan 9 inheritance
+		int j;
+	};
+	void ?{}( Mary & mary ) { abort(); }
+	void ?{}( Mary & mary, int p ) with( mary ) {
+		((Fred &)mary){ p };
+		j = i = p;
+	}
+
+	Stack(Mary) mary;
+	StackIter(Mary) maryIter = { mary };
+	Mary * m;
+
+	for ( ; maryIter >> m; ) {							// empty list
+		sout | m->i | m->j | ' ';
+	}
+	sout | "empty" | nl;
+	
+	for ( i = 0; i < 10; i += 1 ) {
+		push( mary, new( 2 * i ) );
+	}
+
+	for ( over( maryIter, mary ); maryIter >> m; ) {
+		sout | m->i | m->j | ' ';
+	}
+	sout | nl;
+	
+	for ( i = 0; i < 9; i += 1 ) {
+		delete( pop( mary ) );
+	}
+
+	for ( over( maryIter, mary ); maryIter >> m; ) {
+		sout | m->i | m->j | ' ';
+	}
+	sout | nl;
+	
+	for ( i = 0; i < 10; i += 1 ) {
+		push( mary, new( 2 * i + 1 ) );
+	}
+	for ( over( maryIter, mary ); maryIter >> m; ) {
+		sout | m->i | m->j | ' ';
+	}
+	sout | nl;
+
+	for ( over( maryIter, mary ); maryIter >> m; ) {
+		delete( m );
+	}
+}
+
+// Local Variables: //
+// compile-command: "cfa stack_example.cfa" //
+// End: //