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.
GoingDeep: The State Monad - Part 1
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 uniq...
- Running time
- 0h41m
- File size
- 19.00MB
Episode synopsis
You might also like...
Concurrency forum discussion
-
USB Drive Activity Logger!
by coque0912 (7 replies)
-
SBCGlobal Email Login problem
by demil1602 (0 replies)
-
MultiThreading problem
by JohnnyOmari (0 replies)
-
Exporting data from a repeater to an Excel sheet
by TomBlack (28 replies)
-
Calculate Date of Birth from Age
by k.prashanth (7 replies)
Concurrency jobs
-
.NET, C#, MVC Senior Software Developer
Frontline Technologies, Inc. in Exton, United States
-
C#, JQuery, KnockoutJs. Nhibernate. Unique 3-6 month opportunity in Kitesurfing/Windsurfing heaven
RWI in Cabarete, Dominican Republic
$12,000-12,000 USD per year (Contract) -
C# / .NET Programmer
Mews Systems in Prague, Czech Republic
-
Experienced C# Developer
Zenco Systems Ltd in Rugby, United Kingdom
Annual Bonus, Annual Salary Review, Perfomance Related Bonus
Comments