Brian Beckman: The Zen of Stateless State - The State Monad
Вставка
- Опубліковано 22 лис 2024
- 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#). (mschnlnine.vo.l...) 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 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.
Very well done! Thanks! The best introduction to the state monad I have seen so far. The way he gets to it makes you understand why the strange looking signature s -> (a, s) makes total sense. Also I love the term he uses for the state-monad return function: monadmaker. Once you get there the state monad bind operator comes natural.
This was just brilliant, especially the diagrams. None of the tutorials I've read ever thought of calling the right operand of bind a "monad creator," but that's exactly what it is! It makes perfect sense. Thanks for all the insights. Who knows if we'll ever see part 3 on the continuation monad! One can hope.
Eternal Sunshine of the Stateless Mind
Wow, didn't know Sean Connery was that smart!
I wasted a lot of time wading through Haskell's source code for the state monad. Could have just watched this excellent video.
The link to the slides, code and exercises is dead. Anyone knows where one could get it?
really enjoying this series. please do part 3.
~ 42:35 programmers who don't do math smell bad
I sort of wish Haskell allowed print to stdErr as the only function with side effects in the language. That would make logging/debugging easier.
+BosonCollider It does. It's called trace. wiki.haskell.org/Debugging
You use it like this:
trace (string to print) (value to return)
usually replacing the last parentheses with $:
trace (string to print) $ value to return
which makes it easier to comment it out:
{- trace (string to print) $ -} value to return
Here's an example tracing function call order:
> import Debug.Trace
> let f 1 = 1; f n = trace ("f " ++ show n) $ n * f (n - 1) in f 4
f 4
f 3
f 2
24
Here's another example tracing both function calls and return values:
> import Text.Printf
> let f 1 = 1; f n = trace (printf "f %d" n) $ let r = n * f (n - 1) in trace (printf "f %d => %d" n r) $ r in f 4
f 4
f 3
f 2
f 2 => 2
f 3 => 6
f 4 => 24
24
Check out the Debug.Trace module. It's in the standard library:
hackage.haskell.org/package/base-4.9.0.0/docs/Debug-Trace.html
Could you upload a higher-resolution version of this video please? It is quite hard to read what's on Brian's screen in 480p,
Thank you for this great video! It's full of insights.
I have a question that might be a bit off topic, but what's the name of the program Brian used to create / present the schematic drawings of the functions?
+Jan Hrček That would be Microsoft Visio. You can find the Visio file in the ZIP that's linked in the description, along with the source code.
Anybody know which paper he is referring to at 16:32?
It might be Berdine (2002). Linear Continuation-Passing. Higher-Order and Symbolic Computation, 15, 181-208. Abstract: Continuations can be used to explain a wide variety of control behaviours, including calling/returning(procedures), raising/handling (exceptions), labelled jumping (gotostatements), process switching (coroutines),and backtracking. However, continuations are often manipulated in a highly stylised way, and we show that all ofthese, bar backtracking, in fact use their continuationslinearly; this is formalised by taking a target language forCPStransforms that has both intuitionistic and linear function types.
It's "Representing monads" by Filinski
When he says "monad maker" is he referring to bind (>>=)?
I'm not sure exactly where you mean, but if it's near the beginning of the explanation of the State monad, the function with signature `a → (S → (S, a))`, that's `mreturn` or `return`. In the case of the state-monad, `return` takes a value and wraps it in the monad, which is a function that will pass state unchanged from argument to return, alongside the original value. For example `mreturn(5)` (where 5 is an int) will produce a callable with signature `S → (S, a)`, and when you call it with `s : S`, you will get back as a pair (s, 5).
"apply your negative attributes to too_negative_to_retire function".. functional is a way of life..
The file link is down :(
@51:19
Wow he's at the point where when asked which of 3 lambda-carrying languages to use the question of available libraries isn't even in the top 3 reasons.
Oof, I guess I'm a few years late to grab the .zip file with all this stuff. It's a dead link now.
Same here! I'd love to have this stuff too.
@@flereoussarg Is there a way to get it back? Is it on the Wayback Machine or some other archive?
i'm a beginner haskellite, and i have a question: i know how to use recursive function that passes some accumulating value to itself (returns it as a tuple element, calls itself with that element as an argument). does this mean i'm using a monad without knowing it, or is that something different?
YumanoidPontifex It's different. It can be a little bit similar in principle (it's another mean how to deal with a state) but it's not a monad-as-it's-talked-about.
Wow! just wow)
Is there some standard (like UML) for those drawings with arrows that describe the functions seen in the video? Looks pretty useful.
its MS Visio
I have the same question. MS Vision is just a tool. It's more about how you represent the concepts. E.g. product types appear to be represented as parallel arrows, how do you represent sum types?
"Okay."
He looks like a bald Santa.
crap quality