Idris2+WebGL, part #17: A Hoare state failure
Tags: idris, functional, webgl
Published: 2021-10-08 11:21:01

---
title: Idris2+WebGL, part #17: A Hoare state failure
published: true
tags: #Idris, #functional, #webgl
series: Idris2 and WebGL
canonical_url: https://drbearhands.com/idris-webgl/part17/
---

As explained in the last log entry, I set out to use decorated state monads to prove certain properties of a program.

Since I have once already, somewhat unsuccesfully, used indexed monads in Haskell, I decided to aim big and [tackle Hoare state monads](https://dev.to/drbearhands/the-hardest-thing-i-ever-did-explained-as-simply-as-possible-jg4). I've changed a few details since writing that article, such as adding a `>>` operator and replacing my custom `exists` function with a standard dependent pair (both are existential quantification, but the latter has nicer syntactic sugar).
While I did manage to get Hoare state monads working in Idris, I found their use rather frustrating. The main problem is that the type checker is strugling to find proofs, requiring manual proofs from the programmer. What's more, vague error messages in Idris 2 and the unability to put holes in some places makes the job substantially harder.

For example, consider the following code:

```Idris
init0 : HoareStateMonad Nat Top () (\_, _, s => s = 0)
init0 = MkHSMonad $ \_ => MkPostS () 0

increment : HoareStateMonad Nat Top () (\s1, _, s2 => s2 = s1 + 1)
increment = MkHSMonad $ \s => MkPostS () (s + 1)

init1 : HoareStateMonad Nat Top () (\_, _, s => s = 1)
init1 = init0 >> increment
```

Remember that `HoareStateMonad s pre a post` considers a state `s`, a precondition `pre : s -> Type` over an input state of type `s`, a return-type `a` and a postcondition `post : s -> a -> s -> Type` over input state, return type, and output state.

As such, `init0` changes the state of a `Nat`, works for any input state (`Top` holds for any value), returns a unit, and guarantees that the output state is `0`. Similarly, the `increment` function guarantees that the output state is the input state + 1. It is obvious to a human that the postcondition of `init1`, which first sets the state to 0 and then adds 1 to it, is that the output state is 1.

For the typechecker, this is a little harder. First is the simple issue of how the bind (`>>=`) operation has been defined, the type signatures end in:

```Idris
HoareStateMonad s p1 a q1
-> ((x : a) -> HoareStateMonad s (p2 x) b (q2 x))
-> HoareStateMonad s (bind_pre p1 q1 p2) b (bind_post q1 q2)
```

so idris excepts the resulting postconditions to be `bind_post q1 q2`, which specifically results in 

```Idris
(x : a ** (s2 : s ** (q1 s1 x s2, q2 x s2 y s3)))
```

and not any arbitrary thing that can be derived from `bind_post q1 q2`. In our case, the typechecker will conclude:

```Idris
(x : a ** (s2 : s ** (s2 = 0, s3 = s2 + 1)))
```

rather than

```Idris
s3 = 1
```

Nevertheless, since we can prove the latter from the former, we want the typechecker to accept this. A similar, but contravariant rather than covariant, situation occurs for the precondition.

So I've experimented with a `simplify` function:

```Idris
simplify : {0 s : Type} 
        -> {0 a : Type}
        -> {0 preA : s -> Type}
        -> {0 preB : s -> Type}
        -> {auto 0 fPre : {s1 : s} -> preB s1 -> preA s1}
        -> {0 postA : s -> a -> s -> Type} 
        -> {0 postB : s -> a -> s -> Type} 
        -> {auto 0 fPost : {s1 : s} -> {x : a} -> {s2 : s} -> postA s1 x s2 -> postB s1 x s2} 
        -> HoareStateMonad s preA a postA
        -> HoareStateMonad s preB a postB
```


I can use this explicitely:

```Idris
init1 : HoareStateMonad Nat Top () (\_, _, s => s = S Z)
init1 = simplify {fPost=fPost} $ init0 >> increment
  where
    fPost : {s2 : Nat} 
          -> (((e1 : () ** (e2 : Nat ** (e2 = Z, s2 = S e2)))))
          -> (s2 = S Z)
    fPost (() ** (e2 ** (p1, p2))) = replace {p = \e => s2 = S e} p1 p2
```

but this is not a particularly easy task. Expecting programmers to provide these proofs all throughout the code base is not realistic. I have not found a way to derive them automatically (although I believe it could theoretically be done).

This, for now, concludes my forray into Hoare state monad. The conclusion being that it is too cumbersome in the current state of Idris 2. Perhaps language updates will change things. If you want to mess with it yourself you can get the code in the [hoare-state branch](https://gitlab.com/DrBearhands/idris-linear/-/tree/hoare-state) of my idris-linear repository (there is no actual linear variant of the Hoare state monad yet), and in particular the [latest commit at the time of writing](https://gitlab.com/DrBearhands/idris-linear/-/tree/487e3a22876119596301bde58c7ac4ed7acc93f2) in that branch.