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

Posted By: Charles | Nov 20th, 2008 @ 1:36 PM

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 Smiley

)

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.

Tags: , Brian Beckman, Concurrency, Functional Programming, Monads, Parallel Computing, Programming

Rating:

Views (77,330)

Comments (43)

Downloads

dot_tom

I was thinking that when Visual Studio 2010 finally ships it would be incredibly useful if all these recent C9 parallelism videos (including related theory ones like Brian's) could be pulled together somehow and bundled with the package. If not actually on the DVD then certainly permanently archived online in one, easily navigatable, place.

Charles
Welcome Change

In reply to dot_tom

#Nov 19th, 2008 @ 9:34 PM

Excellent idea. And it's totally possible by pulling in the content to VS using our tagged RSS feeds. The home page of VS today does exactly this. Putting the content on the DVD is an interesting notion. Not sure how feasible it is given the size constraints (all of C9's videos and screencasts related to Parallel Computing would fill up up a DVD or two Smiley

Something that would be really cool would be launching a C9 screencast in VS and having the code in the video automatically written to your VS text editor. So, your text editor extensibly replaces the one in the video stream...

C

Duncanma
Just Coding for Fun...

In reply to Charles

#Nov 19th, 2008 @ 9:39 PM

Charles said:

Something that would be really cool would be launching a C9 screencast in VS and having the code in the video automatically written to your VS text editor. So, your text editor extensibly replaces the one in the video stream...

I think Erik already wrote something like this about a year ago... you should bug him about it

aL_
mm.. linq.. *arrggha*

man, its been a while since briain tied my brain in a knot, ive missed that Smiley

aL_
mm.. linq.. *arrggha*

still watching but i gotta ask, is the secret stuff brian's working with oslo? or is it something else? Smiley

--edit--

great stuff :O this interview ranks among the best ones ive seen on channel9 but the wmvhigh version (and possibly the others, havent looked yet) end 1:00:47 real abruptly, is there a part two coming?

dot_tom

In reply to aL_

#Nov 20th, 2008 @ 1:29 AM

My guess would be the deep type system and associated libraries support for notions of mutability and functional purity. David Callahan, Anders et al dropped serious hints about this at the PDC.

AdityaG
OMG VISTA FTW LOLZ!!1one

I am sorry... but is that a wall of patent cubes on his window sill? O_o

Charles
Welcome Change

In reply to aL_

#Nov 20th, 2008 @ 1:29 AM

Oh man... Looks like I missed the last part. Dammit. Sometimes my camera creates a second file when interviews last too long... I'll need to find the ending and patch it on and re-upload the files. Thanks for catching this. Sorry for the troubles.
C

Charles
Welcome Change

In reply to Charles

#Nov 20th, 2008 @ 10:06 AM

Fixed. Broken in two parts now. Sorry about that....

Part 2.

C