Back to Questions
3.9k
views13
comments
Should I use monads to carry the "context" of my program
f#monadsmonad

Many programs have a context which is carried around and basically shares a changing state through out the computation. I have many codes with the form:

let f ctx x = 'calculate somthing while modifying the context and return pair tuplet with f(x) plus new context'

Then my code looks like: 

1
2
3

let (ctx1, y1) = f ctx0 x1
let (ctx2, y2) = f ctx1 x2
etc.

Now I read up on monads and understand that I could create a monad containing ctx and then call f withing the scope of this monad, somthing like:

1
2
3
4

ctxmonad {
   let y1 = f' x1
   let y2 = f' x2
   }

where f' would be f also changing the state of the monad with the new value of ctx.

But I have not worked it all out yet and looking at the definition of the monadic syntax in the F# specs leads where it talks about lazyness and things like that makes me wonder if this is the "right thing to do".

Does any one have a point of view?

Thanks

James

.

Hi James.

Monads may be more elegant than explicitly mutating state. However, monadic code (like other code in continuation passing style) requires proper tail recursion and efficient garbage collection.

Alternative .NET implementations like Mono 2.x do not always do tail recursion optimization. (That issue is currently being worked on by Mono developers.) Also producing lots of garbage may be a performance issue both with Microsoft.NET and Mono 2.x.

So I guess there is no clear winner.
Everything depends on the circumstances you want to use the code in.

Regards,
Stefan.

By on 3/25/2009 7:06 AM ()

...That issue is currently being worked on by Mono developers...

When I determined that tail calls are almost entirely broken on Mono I contacted the Mono developers and they made it clear that they do not value tail calls and have no intention of implementing them correctly. Moreover, they did not even seem to understand what tail calls are...

By on 3/28/2009 7:29 PM ()

Of course Mono developers understand tail-calls and their importance for functional programs.
Mono develops at its own pace. Tail-calls are being worked on by Mono developers.

By on 3/29/2009 7:33 AM ()

Of course Mono developers understand tail-calls and their importance for functional programs.

Paolo "lupus" Molaro, author of Mono's JIT, stated "We have a similar test in tests/even-odd.il and it has been working for years in mono.". Alan McGovern said "It was pointed out to you that mono has a testcase which implements this exact test and it works fine.". Rodrigo Kumpera said "Mono support tail calls just like .NET does.". These statements are all incorrect and fly in the face of the counter example I had already provided them with.

Tail-calls are being worked on by Mono developers.

I am not aware of any Mono developer who even understand the issue, much less intends to do something to resolve it.

By on 3/29/2009 12:58 PM ()

Some tail-calls work properly with Mono 2.x, others do not.
Sadly, this renders certain functional programming techniques unusable with current versions of Mono.

Luckily, the issue IS being worked on (even if you may not be aware of it being done or of the people doing it).

One has not only to ask the right people, one has to ask them the right way...

By on 3/30/2009 4:33 AM ()

The CLR didn't have very good tailcalls up until a version ago... I believe one of the restrictions was even "return type can't be a value type". So it's not surprising for Mono to have it lower priority until recently.

As of 2.2, I thought tailcalls were working fine. As you noted on your blog, you can force a GC leak, although I'm not sure what kind of actual production F# or C# code would generate such a path, and if it'd be that hard to fix anyways. (The example I repro'd with the Mono guys was pretty trivial to fix, and the "bad" code wasn't something I'd think people write often.)

By on 3/28/2009 8:46 PM ()

As of 2.2, I thought tailcalls were working fine.

Tail calls have never worked correctly in any version of Mono. Their JIT's implementation of argument passing is fundamentally broken so the fix is non-trivial.

As you noted on your blog, you can force a GC leak, although I'm not

sure what kind of actual production F# or C# code would generate such a

path, and if it'd be that hard to fix anyways.

The GC leaks are a separate issue but, in point of fact, the code I posted was production code and the only reason I looked at these problems in Mono was following complaints from two customers.

By on 3/29/2009 12:41 PM ()

Check out

[link:cs.hubfs.net]

You are almost right; your code will be like

1
2
3
4
5

ctxmonad {
   let! y1 = f' x1
   let! y2 = f' x2
   ...
   }

and the state is implicitly threaded through (with GetState/SetState/MapState available as a way to access/modify it). There is a minor perofmance hit since each "let!" effectively bottles up the 'rest' of the code in a lambda continuation, but the result can be much clearer code for dealing with "effective state" while preserving immutability/referential transparency.

By on 2/19/2009 9:34 AM ()

Thanks Brian,

So now I want to make the writing of f' like functions easier so I thought I would create function in the monad that would allow me to build these functions. Something like:

1
2
3

member b.monadic f = (fun x ->
    let (ns, y) = f GetState x
    in SetState ns; y)

Then I could write f' = monadic f

But that I don't understand how to do it. Clearly this is wrong:

1
2
3

member b.monadic f = (fun x ->
    let! (ns, y) = f GetState x
    in (do! SetState ns); y)

and have

1
2
3

state {
    let! y1 = (monadic f) x1
    }

(The type inference doesn't get the signature right)

So I tried:

1
2
3

member b.monadic f = (fun x ->
    b { let! (ns, y) = f GetState x
       in (do! SetState ns); y) }

But this is no good. Any good ideas?

By on 2/19/2009 3:19 PM ()

I have not tried it, but I think

1
2
3
4
5
6
7

let monadic f x =
    state {
        let! s = GetState()
        let (r,s2) = f s x
        do! SetState(s2)
        return r
    }

would be the way to transform functions-on-tuples to functions-in-monad, then

1
2
3
4
5

    state {
        ...
        let! r = (monadic f) x
        ...
    }

would work.

By on 2/19/2009 3:53 PM ()

Thanks Brian, Here some test code that shows it working.James

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

open State

let monadic f x =
    state {
        let! s = GetState
        let (r,s2) = f s x
        do! SetState(s2)
        return r
    }

let f ctx x = (2*x, ctx+1) // simple test context ctx is just counting operations

let g ctx x = (3*x, ctx+1)
let f' = monadic f
let g' = monadic g

let h =
    state {
        let! x1 =f' 1
        let! x2 =f' x1 
        let! x3 =g' x2 
        return x3
        }

let (x, ctx) = Run h 0 // initial context is 0
printf "%d %d\n" x ctx
By on 2/20/2009 2:04 PM ()

Not wanting to drag this thread on for ever, but the above context management can also be solved with a mutable. Something like this:

1
2
3
4
5
6
7
8
9

let mutable ctx=0

let f x = ctx<-ctx+1; 2*x 
let g x = ctx<-ctx+1; 3*x

let x1 =f 1
let x2 =f x1 
let x3 =g x2 
return x3

So the question: is this "good practice". And... will a sufficiently clean monad be reduced the previous code? The reference guide implies that the monad by default "heavy" weight and sort of leads me to believe that there is no way that the compiler will do this type of optmization. But I happy to be told otherwise.

On the other hand maybe the use of the mutable kills the optmizer and also results in a strong degradation.

Does anybody know what the compiler can do?

James

By on 3/24/2009 1:58 AM ()

The mutable will almost certainly compile to more efficient code than the monad. The trade-off is 'global' mutable state (e.g. it may be harder to make the mutable version work correctly in a multi-threaded environment).

By on 3/24/2009 10:23 AM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper