Entries:
Comments:
Posts:

Loading User Information from Channel 9

Something went wrong getting user information from Channel 9

Latest Achievement:

Loading User Information from MSDN

Something went wrong getting user information from MSDN

Visual Studio Achievements

Latest Achievement:

Loading Visual Studio Achievements

Something went wrong getting the Visual Studio Achievements

C9 Lectures: Greg Meredith - Monadic Design Patterns for the Web 4 of 4

Download

Right click “Save as…”

Greg Meredith, a mathematician and computer scientist, has graciously agreed to do a C9 lecture series covering monadic design principles applied to web development. You've met Greg before in a Whiteboard jam session with Brian Beckman.

The fundamental concept here is the monad, and Greg has a novel and conceptually simplified explanation of what a monad is and why it matters. This is a very important and required first step in the series since the whole of it is about the application of monadic composition to real world web development.

In part 4, Greg primarily focuses on the idea that a monad is really an API—a view into the organization of data and control structures, not those structures themselves. In OO terms, it's an interface. To make this point concrete, Greg explores one of the simplest possible data structures supporting at least two different, though consistent, interpretations of the same API. The structure used, Conway's partisan games, turns out to be tailor-made for this investigation. Not only does this data structure have the requisite container-like shape, it provides opportunities to see just what's necessary in a container to implement the monadic interface. 

Running throughout the presentation is a more general comparison of reuse between an OO approach and a more functional one. When the monadic API is "mixed into" the implementing structure, we get less reuse than when the implementing structure is passed as a type parameter. Finally, doing the work puts us in a unique position to see not just how to generalize Conway's construction monadically, but also the underlying pattern that allows the generalization to suggest itself.

Source code for the Conway game
Slides for this presenation

See part 1
See part 2
See part 3

Tags:

Follow the Discussion

  • Some background information for one of the slides: Difference between List and Set variance?
  • Thanks Greg & Charles. Very much enjoyed this latest instalment. Looking forward to the next one and/or the book!
  • Aaron StainbackAceHack AceHack

    Hey this was great.  What would this look like in F#?  Thanks.

  • @AceHack:

    F# has a DSL for monads called Computation Expressions so monads 'look' different in F#. Also, I think that once you have a monad implementation, the DSL makes it easier to use the implementation in your code.

    So F# provides some extra language support for monads.

    However, unlike Scala, F# does not have higher-kinded types so you cannot compose two monad implementations together (as easily).

    I struggled with monads at first but then I realized that monads are really about function composition. Here is blog post that emphasizes this aspect of monads that may help with the understanding:

    http://fwaris.wordpress.com/2011/07/30/understanding-monads/

  • 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 Smiley

    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 Smiley

     ____ 

    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 Smiley
    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...

Remove this comment

Remove this thread

close

Comments Closed

Comments have been closed since this content was published more than 30 days ago, but if you'd like to continue the conversation, please create a new thread in our Forums,
or Contact Us and let us know.