meisl

Thank you Greg! Thank you Charles!

This one was really giving me a blast (and still is). Today I got my copy of D.E.Knuth's "Surreal Numbers", which is an excellent little intro to Conway numbers back from 1974, and I would like to recommend it here. I devoured it in one go and will read it again as soon as possible, then equipped with pencil and paper. The other book, Conway's "On Numbers and Games", appearing in the slides, I have ordered already... and Greg's book is on the list

Now, having settled the praise, here's something that sparked off quite towards the end of this installment. It's about abstracting over the container representation for 'left' and 'right'. Hmm, possibly there's a good thing even in Scala's oddity of non-variant (immutable!) Sets (see ShiNoNoir's link above).

Ok, I got two things, the second about transfinite ordinals. I know, that sounds quite scary/impressive - but it ain't really so (much). I have put together a postscript below (admittedly long for a post, but still...) which I hope establishes the relevant point while presuming virtually nothing. Please also leave your comment on that particular attempt alone, if you have some.

•  Isn't the "second hole", i.e. the abstraction over the containers just including the "first hole" that you poked? That is to say: once we're free to provide any container representation we like, can't we get rid of the A type parameter in GenConWayGame[M[_],A] and the Either[A, ...] in left and right and just "push" that into the M[_]?
• The M[_] that we pass in to GenConWayGame is free to choose any (internal) representation of collections it prefers, as long as it provides unit and bind (and adheres to some "Set contract", e.g. order-insensitive, duplicate-free etc), right? Well, if so why not represent Sets as the "recipe" how to create them, i.e. as code. I mean code as data, i.e. we're not going to execute that code but rather want to manipulate it. So ω would just be some (finite!) representation of code that, if executed, would give the empty set for right and for left enumerate the naturals, ad infinitum. Adding 1 to that, for example, would give code that, if executed, would give the empty set for right and for left enumerate {ω,2,3,4,....}. And, even better, we could simply return the equivalent ({ω}, {}). Not so hard to imagine how to represent that, is it? You see, it's calculating (=reasoning about) it, not actually writing it out. We'd like to defer as long as we can - at best forever

 ____ 

p.s., "What's that Conway ω, by the way?" (simplifying quite a bit - as Greg mentioned, "there's a lot of devil (detail) in there"):

1. To start, let's define a binary relation to compare Conway games, "LTE" ("Less-Than-or-Equal"): x = (X_L, X_R) is LTE  y = (Y_L, Y_R) :IFF every x_L in X_L is LTE y AND x is LTE every y_R in Y_R. Again, this appears crazily circular but look, since it's composed of universal statements ("for every foo in bar: ...") and we're starting from empty sets, it's well-founded (note that "for every foo in the empty set: ..." is always true, regardless of what the "..." say).
2. Not every Conway game is also a Conway number, i.e. there exist games g and h such that  neither g LTE h nor h LTE g is the case. Odd as this may seem, it rather shows that the data structure is even more powerful than to "just represent numbers". Anyways, let's consider Conway numbers only; these are the games x = (X_L, X_R) where we have: every x_L in X_L is LTE than any (="every") x_R in X_R.  Again, this looks crazily circular but... - we're getting used to it, aren't we?
3. 1) and 2) (not obviously) imply that every "intuitive" number has a many structurally distinct Conway numbers (or better "numerals") that represent it. However, all those representations of one "intuitive" number have the common property to "behave" identically w.r.t. comparison, addition etc., i.e. they are "practically the same". Even better, from all the representations that are equivalent in the said sense we can easily choose (=construct) a single canonical one to stand for them all - and thus forget about the problem altogether. We'll simply use the canonical one to denote "or any of its equivalents". Oh, and btw, the set of equivalents (the "equivalence class") for any number is infinite...
4. Uhm... actually there's a catch in 3), in particular the "we can easily choose (=construct)". In fact, that's not entirely true when it comes to the interesting bits. Now what are these? Well,  let's start by sticking with 3) for awhile and have a look at the non-negative integers only. We have 0 = ({},{}), then 1 = ({0}, {}), then 2 = ({1}, {}), then 3 = ({2}, {})... you get it: left is the set containing just the (set containing the) predecessor and right is always empty. These were the canonical representations as proposed in 3), but e.g. the "intuitive" number 2 could also be represented by ({0,1}, {}), that means ({0,1}, {}) "is practically the same as" ({1}, {}). Likewise, the "intuitive" number 3 could be as well represented by ({0,1,2}, {}) or ({0,2}, {}) or ({1,2}, {}). The "trick", of course, is that the "behavior" solely depends on the maximal element (check yourself using the definition of LTE). Hence the choice of the canonical representative is straight-forward: simply use the singleton set with exactly that maximal element for left and the empty set for right. This covers all of the non-negative integers nicely. Now for the fun part
5. Who said the left and/or right collections of a Conway number (or game, for that matter) need to be finite? Well, nobody, of course. But that means there is this critter: ({0,1,2,3,4,...}, {}), i.e. empty right and in left all the non-negative integers from 4). This actually is a Conway number according to 2), yet any non-negative integer from 4) is LTE it. Check it yourself, you'll see it's trivial. This critter is commonly denoted by ω and it was created on the day after infinitely many days (when the integers [and some more, like the rationals] were created), aka day aleph (1). Anyhow, here come the interesting bits: how to actually represent ω in a program? Obviously we cannot replay the "trick" from 3), as there is no maximal element (although we could agree on a canonical representation that contains just the singleton sets from 4) - but that doesn't help, it's still infinite). However, it's not at all hard to envision ω - or is it?! C'mon, all we're talking about is the pair of a) all the non-negative integers and b) the empty set, that ain't really hard. But wait, what is just that? It's an English sentence, consisting of... uhm... a number of characters - but definitely finite! And it characterizes this infinite critter ω . So...

Great workshop on exciting concepts - congratulations!

Had been watching Rx "from the distance" for quite a time, but now I decided to really get hands on.

So, re Challenge1: my first go on it yielded considerably less and more concise code for events than for Observables! I just could not see how this ought to illustrate the (better) composability of Observables; it seemed rather to the contrary... oops.

Then I realized that my simple-minded solution for events was way off spec (or what I think is the intended semantics) - while with Observables it all comes out just as it should be automatically.

However, the problem with the challenge at hand is IMHO that the "test case" in Program.cs does not surface any of the relevant bits. That is, I think, because it only tests the case where there is one subscriber for changes in length. Therefore I'd like to propose the following as expected output:

            // Expected Output:
            // *** Events ***
            // The
            // Reactive
            // Extensions
/*  *  */   // 1: 10
            // are
/*  *  */   // 1: 3
/*  +  */   // new
/*  +  */   // and          // verify: there is NO change in length!
/*  *  */   // 1: 13
/*  +  */   // 2: 13        // verify: 2nd handler gets notified, too!
/*  +  */   // 2: 1
            // *** Observables ***
            // The
            // Reactive
            // Extensions
/*  *  */   // 1: 10
            // Extensions
            // are
/*  *  */   // 1: 3
/*  +  */   // new
/*  +  */   // and          // verify: there is NO change in length!
/*  *  */   // 1: 13
/*  +  */   // 2: 13        // verify: 2nd handler gets notified, too!
/*  +  */   // 2: 1

...produced by the this test code:

            Console.WriteLine("*** Events ***");
            var events = new Events();
            Action<string> textHandler = text => Console.WriteLine(text);
/*  *  */   Action<int> lengthHandler1 = length => Console.WriteLine("1: " + length);
/*  +  */   Action<int> lengthHandler2 = length => Console.WriteLine("2: " + length);
            events.TextChanged += textHandler;
            events.OnTextChanged("The");
            events.OnTextChanged("Reactive");
/*  *  */   events.LengthChanged += lengthHandler1;
            events.OnTextChanged("Extensions");
            events.OnTextChanged("are");
/*  +  */   events.LengthChanged += lengthHandler2;
/*  +  */   events.OnTextChanged("new");
/*  +  */   events.OnTextChanged("and");
            events.TextChanged -= textHandler;
            events.OnTextChanged("compositional");
/*  *  */   events.LengthChanged -= lengthHandler1;
            events.OnTextChanged("!");
/*  +  */   events.LengthChanged -= lengthHandler2;

            Console.WriteLine("*** Observables ***");
            var observables = new Observables();
            var textChangedSubscription = observables.TextChanged.Subscribe(text => Console.WriteLine(text));
            observables.OnTextChanged("The");
            observables.OnTextChanged("Reactive");
/*  *  */   var lengthSubscription1 = observables.LengthChanged.Subscribe(length => Console.WriteLine("1: " + length));
            observables.OnTextChanged("Extensions");
            observables.OnTextChanged("are");
/*  +  */   var lengthSubscription2 = observables.LengthChanged.Subscribe(length => Console.WriteLine("2: " + length));
/*  +  */   observables.OnTextChanged("new");
/*  +  */   observables.OnTextChanged("and");
            textChangedSubscription.Dispose();
            observables.OnTextChanged("compositional");
            lengthSubscription1.Dispose();
            observables.OnTextChanged("!");
/*  +  */   lengthSubscription2.Dispose();

The prefixed comments denote my changes/additions relative to the original. Besides the additional length-change subscriber I have added the new text-change events "new" and "and" after "are", which both should NOT yield a length-change event. The whole point of this is that the stream of events as such should really be independent of the subscribers, particularly:

a) which / how many subscribers there are and

b) *when* a particular subscriber actually did subscribe.

***Note that the above test case still does not account for the one case where we have both,

a) a length-change subscriber that subscribed even before the very first *text-change* event (missing in test case, SHOULD see an event since (no text ~ length 0) != (some text ~ length > 0)

b) a length-change subscriber that subscribed right in between the text-change events of "are" and "new" (present in test case, should NOT see an event since "are" and "new" are both three characters long)

The problem I'm seeing there is that in the event solution you can get either a) or b) to see the right thing(s), but not both - whereas, again, with Observables you get it right for both just naturally. That is, at least given the restriction that the original [Events|Observables].OnTextChanged(string) firing method may not be changed, I'm not even sure if it's possible at all to get it completely right with only events.

Well, and there we're back at compositionality: adding a new kind of event (stream) should really only require an additive change.

So that's what I wanted to share; this my train of thought felt somewhat educational to me. Sorry for that it all got soo lengthy

___

p.s.: please do try yourself a solution for *** based on events-only, it's one of those things which you deem "definitely doable" at first glance but find yourself utterly puzzled at when having to actually do it. At least that's what applies to me.