Entries tagged with monads - Channel 9

Expert to Expert: Brian Beckman and Erik Meijer - Inside the .NET Reactive Framework (Rx)

Charles — Thu, 09 Jul 2009 18:36:00 GMT

Erik Meijer and team (developer Wes Dyer, in particular) have created a profound and beautiful .NET library that will take managed event based programming to new levels. Of course, many of you wish that you could write LINQ expressions over events. Well, now you can thanks to Erik's and Wes Dyer's latest creation, Rx - .NET Reactive Framework. Erik, being a fundamentalist functional theoritician, can't create new programming abstractions without employing some form of monadic magic.

Enter astrophysicist and monadic composition wizard Brian Beckman. The last time Brian was on C9 he taught us about the State Monad. At the end of that discussion he mentioned he wanted to teach us about the Continuation Monad next. So, who better to conduct this episode of Expert to Expert than Dr. Beckman? Yep. You guessed it! Rx employs the Continuation Monad in its composition. Erik is in the hot seat this time and it's always a real pleasure to converse with Erik and Brian in the same room at the same whiteboard.

Now, what is Rx?

The .NET Reactive Framework (Rx) is the mathematical dual of LINQ to Objects. It consists of a pair of interfaces IObserver/IObservable that represent push-based, or observable, collections, plus a library of extension methods that implement the LINQ Standard Query Operators and other useful stream transformation functions.

interface IObservable<out T>
{
    IDisposable Subscribe(IObserver o);
}

interface IObserver<in T>
{
    void OnCompleted();
    void OnNext(T v);
    void OnError(Exception e);
}

Observable collections capture the essence of the well-known subject/observer design pattern, and are tremendously useful for dealing with event-based and asynchronous programming, i.e. AJAX-style applications. For example, here is the prototypical Dictionary Suggest written using LINQ query comprehensions over observable collections:

IObservable<Html> q = from fragment in textBox

from definitions in Dictionary.Lookup(fragment, 10).Until(textBox)

select definitions.FormatAsHtml();

q.Subscribe(suggestions => { div.InnerHtml = suggestions; })

Please subscribe to this Channel 9 interview to be notified when we have clearance to distribute Rx over the counter (lame puns intended :-).

Tune in. This should prove to be an instant classic besides being a very important episode of E2E. Rx is deep, man. Deep.

Enjoy!

Brian Beckman: The Zen of Stateless State - The State Monad - Part 2

Charles — Thu, 20 Nov 2008 21:38:00 GMT

Exercise 2: go from labeling a tree to doing a constrained
container computation, as in WPF. Give everything a
bounding box, and size subtrees to fit inside their
parents, recursively.

Exercise 3: promote @return and @bind into an abstract
class "M" and make "SM" a subclass of that.

Exercise 4 (HARD): go from binary tree to n-ary tree.

Exercise 5: Abstract from n-ary tree to IEnumerable; do
everything in LINQ! (Hint: SelectMany).

Exercise 6: Go look up monadic parser combinators and
implement an elegant parser library on top of your new
state monad in LINQ.

Exercise 7: Verify the Monad laws, either abstractly
(pencil and paper), or mechnically, via a program, for the
state monad.

Exercise 8: Design an interface for the operators @return
and @bind and rewrite the state monad so that it implements
this interface. See if you can enforce the monad laws
(associativity of @bind, left identity of @return, right
identity of @return) in the interface implementation.

Exercise 9: Look up the List Monad and implement it so that it implements the same interface.

Exercise 10: deconstruct this entire example by using
destructive updates (assignment) in a discipline way that
treats the entire CLR and heap memory as an "ambient
monad." Identify the @return and @bind operators in this
monad, implement them explicitly both as virtual methods
and as interface methods.

Brian Beckman: The Zen of Stateless State - The State Monad - Part 1

Charles — Thu, 20 Nov 2008 21:36:00 GMT

Concurrency is a problem that faces all developers as we move to the age of ManyCore processor architectures. Managing state is an important aspect of programming generally and for parallel programming especially. The great Brian Beckman demonstrates three ways of labeling a binary tree with unique integer node numbers: (1) by hand, (2) non-monadically, but functionally, by threading an updating counter state variable through function arguments, and (3) monadically, by using a partially generalized state-monad implementation to handle the threading via composition. Of course during this lesson from one of the masters of mathematical programming, we wind through various conversational contexts, but always stay true to the default topic in a stateful monadic way (watch/listen to this piece to understand what this actually means :))

This is another great conversation with astrophysicist and programming master Brian Beckman. Brian is one of the true human treasures of Microsoft. If you don't get mondas, this is a great primer. Even if you don't care about monadic data types, this is worth your time, especially if you write code for a living. This is part 1 of a 2 part series.

See Part 2 here.

Included with this interview is a .zip file containing all of the code and diagrams Brian shows us (including both Haskell and C#). To understand the State Monad program, it may be best to start with Main, seeing how the various facilities are used, then backtrack through the code learning first the non-monadic tree labeler, starting with the function Label, then finally the monadic tree labeler, starting with the function MLabel.

Below, you will find several exercises for generalizing the constructions further. Brian will monitor this thread so start your coding engines!!

Exercise 1: generalize over the type of the state, from int$0 to <S>, say, so that the SM type can handle any kind of$0 state object. Start with Scp<T> --> Scp<S, T>, from "label-content pair" to "state-content pair".

Exercise 2: go from labeling a tree to doing a constrained$0 container computation, as in WPF. Give everything a$0 bounding box, and size subtrees to fit inside their$0 parents, recursively.

Exercise 3: promote @return and @bind into an abstract$0 class "M" and make "SM" a subclass of that.

Exercise 4 (HARD): go from binary tree to n-ary tree.

Exercise 5: Abstract from n-ary tree to IEnumerable; do everything in LINQ! (Hint: SelectMany).

Exercise 6: Go look up monadic parser combinators and implement an elegant parser library on top of your new$0 state monad in LINQ.

Exercise 7: Verify the Monad laws, either abstractly$0 (pencil and paper), or mechnically, via a program, for the state monad.

Exercise 8: Design an interface for the operators @return and @bind and rewrite the state monad so that it implements this interface. See if you can enforce the monad laws (associativity of @bind, left identity of @return, right identity of @return) in the interface implementation.

Exercise 9: Look up the List Monad and implement it so that it implements the same interface.

Exercise 10: deconstruct this entire example by using destructive updates (assignment) in a discipline way that treats the entire CLR and heap memory as an "ambient monad." Identify the @return and @bind operators in this monad, implement them explicitly both as virtual methods and as interface methods.

Brian Beckman: Don't fear the Monad

Charles — Thu, 22 Nov 2007 18:28:00 GMT

Functional programming is increasing in popularity these days given the inherent problems with shared mutable state that is rife in the imperative world. As we march on to a world of multi and many-core chipsets, software engineering must evolve to better equip software engineers with the tools to exploit the vast power of multiple core processors as it won't come for free as it did in the recent past which was predictably based on Moore's law.

Of course, learning new ways to think about programming semantics and code patterns are not always straight forward. For example, most imperative programmers (which include most of us who build software for a living...) are somewhat perplexed by the notion of functions as first class data structures that can be combined to create powerful and composable systems. Languages like Haskell are pure functional languages and require programmers to think in a different way, often in a precise mathematical fashion where composing and chaining functions is "the Way".

Dr. Brian Beckman, a Channel 9 celebrity, astrophysicist and senior software engineer thought it would be a very good idea to address the complexity of monads in an easy to understand way: a technical conversation at the whiteboard with yours truly for Channel 9.

This video interview is the result of Brian's idea that he can in fact remove the fear of monads from anybody who pays attention to his explanation. Of course, you can't just cover monads in a vacuum (category theory is not really addressed here) so the context is functional programming (Brian covers functions and composable functional structures (function chains) and of course monoids and then monads).

Tune in. There's a lot to learn here and only Brian can make monads easy to understand for the rest of us!

Happy Thanksgiving to all the US Niners out there.

Enjoy.

Brian Beckman: Monads, Monoids, and Mort

Charles — Tue, 29 Aug 2006 17:34:24 GMT

Brian Beckman is a fascinating individual. Ex-cosmologist, ex-military operating system and simulation developer (have you ever considered processes that move both forward and backward in time? Well, Brian and team at JPL created just that. He explains in this interview...). Brian was one of the first members of Microsoft Research and one of a group of physicists who joined Microsoft in the early 90s. At Microsoft he is a passionate advocate for Mort, the somewhat ambiguous class name for novice developers. In fact, he considers himself a mort (somewhat hard to believe, honestly, but we'll go along with it...). His team works on innovative incubation projects that turn into developer platform features (like LINQ, for example) and more. Tune in to this very interesting interview.

Brainbec's Weblog