F# saying value not defined in Computation Expression

Question

I've been working on a State Monad with F# Computation Expression and I'm trying to also utilize Custom Operations. I'm getting some weird behavior that does not make sense. The compiler is reporting that a value does not exist when it was declared just two lines above.

type State<'a, 's> = ('s -> 'a * 's)

module State =
    // Explicit
    // let result x : State<'a, 's> = fun s -> x, s
    // Less explicit but works better with other, existing functions:
    let result x s = 
        x, s

    let bind (f:'a -> State<'b, 's>) (m:State<'a, 's>) : State<'b, 's> =
        // return a function that takes the state
        fun s ->
            // Get the value and next state from the m parameter
            let a, s' = m s
            // Get the next state computation by passing a to the f parameter
            let m' = f a
            // Apply the next state to the next computation
            m' s'

    /// Evaluates the computation, returning the result value.
    let eval (m:State<'a, 's>) (s:'s) = 
        m s 
        |> fst

    /// Executes the computation, returning the final state.
    let exec (m:State<'a, 's>) (s:'s) = 
        m s
        |> snd

    /// Returns the state as the value.
    let getState (s:'s) = 
        s, s

    /// Ignores the state passed in favor of the provided state value.
    let setState (s:'s) = 
        fun _ -> 
            (), s


type StateBuilder() =
    member __.Return(value) : State<'a, 's> = 
        State.result value
    member __.Bind(m:State<'a, 's>, f:'a -> State<'b, 's>) : State<'b, 's> = 
        State.bind f m
    member __.ReturnFrom(m:State<'a, 's>) = 
        m
    member __.Zero() =
        State.result ()
    member __.Delay(f) = 
        State.bind f (State.result ())


let rng = System.Random(123)
type StepId = StepId of int
type Food =
    | Chicken
    | Rice
type Step =
  | GetFood of StepId * Food
  | Eat of StepId * Food
  | Sleep of StepId * duration:int
type PlanAcc = PlanAcc of lastStepId:StepId * steps:Step list

let state = StateBuilder()

let getFood =
    state {
        printfn "GetFood"
        let randomFood = 
            if rng.NextDouble() > 0.5 then Food.Chicken
            else Food.Rice
        let! (PlanAcc (StepId lastStepId, steps)) = State.getState
        let nextStepId = StepId (lastStepId + 1)
        let newStep = GetFood (nextStepId, randomFood)
        let newAcc = PlanAcc (nextStepId, newStep::steps)
        do! State.setState newAcc
        return randomFood
    }

let sleepProgram duration = 
    state {
        printfn "Sleep: %A" duration
        let! (PlanAcc (StepId lastStepId, steps)) = State.getState
        let nextStepId = StepId (lastStepId + 1)
        let newStep = Sleep (nextStepId, duration)
        let newAcc = PlanAcc (nextStepId, newStep::steps)
        do! State.setState newAcc
    }

let eatProgram food =
    state {
        printfn "Eat: %A" food
        let! (PlanAcc (StepId lastStepId, steps)) = State.getState
        let nextStepId = StepId (lastStepId + 1)
        let newStep = Eat (nextStepId, food)
        let newAcc = PlanAcc (nextStepId, newStep::steps)
        do! State.setState newAcc
    }

type StateBuilder with

    [<CustomOperation("sleep", MaintainsVariableSpaceUsingBind=true)>]
    member this.Sleep (state:State<_,PlanAcc>, duration) =
        printfn $"Sleep"
        State.bind (fun _ -> sleepProgram duration) state

    [<CustomOperation("eat", MaintainsVariableSpaceUsingBind=true)>]
    member this.Eat (state:State<_,PlanAcc>, food) =
        printfn $"Eat"
        State.bind (fun _ -> eatProgram food) state


let simplePlan =
    state {
        let! food = getFood
        sleep 2
        eat food // <-- This is where the error is. 
                 // The value or constructor 'food' does not exist
    }

let initalAcc = PlanAcc(StepId 0, [])

let x = State.exec simplePlan initalAcc
x

Here's a picture of the error:

Answer 1

This all has to do with the deep nature of computation expressions, which, judging by the tags you put on your post, you must already understand are monads.

What are monads? It's just a name for this pattern of chaining computations together, passing the result of one as parameter to the next, that's all. See this answer for a somewhat more comprehensive explanation with examples. Here I'll just assume you know how bind and return work, especially seeing how you've implemented them for State yourself.

And what are computation expressions? They're what you might more generally call "monad comprehensions", which basically means they're syntactic sugar for monads. In practical terms, this means that they're clever syntax, which ultimately gets desugared to a series of bind and return calls.

Let's consider a simplified example without sleep:

state {
  let! food = getFood
  printfn $"{food}"
}

This code would desugar into this:

state.Bind(
  getFood,
  (fun food ->
    printfn "${food}"
    state.Return ()
  )
)

See what happened here? The part of the computation that comes after getFood got turned into a function, and this function takes food as a parameter. That's how the printfn line gets the value of food to print - by virtue of it being passed as a parameter to the function.

Custom operations, however, work a bit differently. When the compiler encounters a custom operation, it takes the whole expression (the sequence of Bind calls) that came before the custom operation, and passes that whole thing to the custom operation as a parameter.

To see what happens, let's try to eat:

state {
  let! food = getFood
  printfn $"{food}"
  eat food
}

This would get desugared to:

state.Eat(
  state.Bind(
    getFood,
    (fun food ->
      printfn $"{food}"
      state.Return food
    )
  ),
  food
)

Hmm... See what happened here? The second parameter of Eat is food, but that's not defined anywhere! It's only valid inside that nested function! This is where you're getting your error.

So to deal with this, computation expressions have a special thing: ProjectionParameterAttribute. Here the word "projection" roughly means "transformation", and the idea is that such parameter would be a function, which can be called on the result of the computation that's been computed "so far" to extract some part of it.

In practice this means that if we annotate Eat like so:

member this.Eat (state:State<_,PlanAcc>, [<ProjectionParameter>] food) =

Then the desugaring of the above example becomes this:

state.Eat(
  state.Bind(
    getFood,
    (fun food ->
      printfn $"{food}"
      state.Return(food)
    )
  ),
  (fun x -> x)
)

Notice how the nested function calls state.Return, so that the result of the whole Eat's first parameter is the value of food. This is done on purpose, to make intermediate variables available to the next part of the computation. This is what it means to "maintain variable space".

And then notice how the second parameter of Eat became fun x -> x - meaning it's extracting the value of food from the intermediate state that has been returned from the Eat's first parameter via that state.Return.

Now Eat can actually call that function to get at the value of food.

member this.Eat (state:State<_,PlanAcc>, [<ProjectionParameter>] food) =
    printfn $"Eat"
    State.bind (fun x -> eatProgram (food x)) state

Note the parameter x - that comes from state, funneled into the lambda expression by State.bind. If you look at the type of Eat, you'll see that it became this:

Eat : State<'a, StateAcc> * ('a -> Food) -> State<unit, StateAcc>

Meaning that it takes a state computation producing some 'a, plus a function from 'a to Food, and it returns a state computation producing nothing (i.e. unit).

So far so good. This will fix the "food is not defined" problem.

---

But not so fast! Now you have a new problem. Try introducing sleep back in:

state {
  let! food = getFood
  printfn $"{food}"
  sleep 2
  eat food
}

And now you get a new error: food was expected to have type Food, but here has type unit.

WTF is going on here?!

Well, you're just throwing away the food inside Sleep, that's all.

    member this.Sleep (state:State<_,PlanAcc>, duration) =
        printfn $"Sleep"
        State.bind (fun _ -> sleepProgram duration) state
                        ^
                        |
                    This was `food`. It's gone now.

You see, Sleep takes a computation producing something and proceeds to throw away that something and run sleepProgram, which is a computation producing unit, so that's what the result of sleep becomes.

Let's look at the desugared code:

state.Eat(
  state.Sleep(
    state.Bind(
      getFood,
      (fun food ->
        printfn $"{food}"
        state.Return food
      )
    ),
    2
  ),
  (fun x -> x)
)

See how Sleep's result is the first parameter of Eat? That means Sleep needs to return a computation producing food, so that Eat's second parameter can have access to it. But Sleep doesn't. It returns the result of sleepProgram, which is a computation producing unit. So food is gone now.

What Sleep really needs to do is to first run sleepProgram, then to the end of it chain another computation that would return the result of the original Sleep's first parameter. Like this:

member this.Sleep (state:State<_,PlanAcc>, duration) =
  printfn $"Sleep"
  State.bind 
    (fun x -> 
      State.bind 
        (fun () -> State.result x) 
        (sleepProgram duration)
    ) 
    state

But this is ugly as hell, isn't it? Luckily, we have a handy compiler feature to turn this mess of bind calls into a nice and clean program: computation expressions!

member this.Sleep (st:State<_,PlanAcc>, duration) =
  printfn $"Sleep"
  state {
    let! x = st
    do! sleepProgram duration
    return x 
  }

---

If you take away one thing from all of this, let it be the following:

"Variables" that are defined within a computation expression are not really "variables" at all, they only look like them, but in reality they're function parameters, and you have to treat them as such. This means that every operation has to make sure to thread through whatever parameters it got from upstream. Otherwise those "variables" won't be available downstream.