#version 100

/*
Suggested by Luc Edixhoven.
Source: https://en.wikipedia.org/wiki/Thue%E2%80%93Morse_sequence

In mathematics, the Thue–Morse sequence, or Prouhet–Thue–Morse sequence,
is the binary sequence (an infinite sequence of 0s and 1s) obtained by
starting with 0 and successively appending the Boolean complement of the
sequence obtained thus far.

To compute the nth element t_n, write the number n in binary. If the
number of ones in this binary expansion is odd then t_n = 1, if even
then t_n = 0. For this reason John H. Conway et al. call numbers n
satisfying t_n = 1 odious (for odd) numbers and numbers for which
t_n = 0 evil (for even) numbers. In other words, t_n = 0 if n is
an evil number and t_n = 1 if n is an odious number.

*/

import std.reo;

composite main(out x) {
	channel ao -> ai;
	channel bo -> bi;
	channel co -> ci;
	new evil_or_odious(ai, bo);
	new replicator(bi, {co, x});
	new recorder(ao, ci);
}

primitive evil_or_odious(in x, out y) {
	while (true) {
		synchronous {
			if (fires(x) && fires(y)) {
				msg a = get(x);
				msg result = create(1);
				boolean even = true;
				int i = 0;
				while (i < a.length) {
					if (a[i++] == '1')
						even = !even;
				}
				result[0] = even ? '1' : '0';
				put(y, result);
			} else {
				assert !fires(x);
				assert !fires(y);
			}
		}
	}
}
primitive recorder(out h, in a) {
	msg c = create(0);
	while (true) {
		synchronous {
			if (fires(h) && fires(a)) {
				put(h, c);
				{
					msg x = get(a);
					msg n = create(c.length + 1);
					int i = 0;
					while (i < c.length) {
						n[i] = c[i];
						i++;
					}
					n[c.length] = x[0];
					c = n;
				}
			}
		}
	}
}