How dangerous is trustMe?

Question

Here's what I understand about Relation.Binary.PropositionalEquality.TrustMe.trustMe: it seems to take an arbitrary x and y, and:

• if x and y are genuinely equal, it becomes refl
• if they are not, it behaves like postulate lie : x ≡ y.

Now, in the latter case it can easily make Agda inconsistent, but this in itself is not so much a problem: it just means that any proof using trustMe is a proof by appeal to authority. Moreover, though you can use such things to write coerce : {A B : Set} -> A -> B, it turns out to be the case that coerce {ℕ} {Bool} 0 doesn't reduce (at least, not according to C-c C-n), so it's really not analogous to, say, Haskell's semantic-stomping unsafeCoerce.

So what do I have to fear from trustMe? On the other hand, is there ever a reason to use it outside of implementing primitives?

Answer 1

Indeed, attempting to pattern match on trustMe which does not evaluate to refl results in a stuck term. Perhaps it is enlightening to see (part of) the code that defines the primitive operation behind trustMe, primTrustMe:

(u', v') <- normalise (u, v)
if (u' == v') then redReturn (refl $ unArg u) else
  return (NoReduction $ map notReduced [a, t, u, v])

Here, u and v represent the terms x and y, respectively. The rest of the code can be found in the module Agda.TypeChecking.Primitive.

So yes, if x and y are not definitionally equal, then primTrustMe (and by extension trustMe) behaves as a postulate in the sense that evaluation simply gets stuck. However, there's one crucial difference when compiling Agda down to Haskell. Taking a look at the module Agda.Compiler.MAlonzo.Primitives, we find this code:

("primTrustMe"       , Right <$> do
       refl <- primRefl
       flip runReaderT 0 $
         term $ lam "a" (lam "A" (lam "x" (lam "y" refl))))

This looks suspicious: it always returns refl no matter what x and y are. Let's have a test module:

module DontTrustMe where

open import Data.Nat
open import Data.String
open import Function
open import IO
open import Relation.Binary.PropositionalEquality
open import Relation.Binary.PropositionalEquality.TrustMe

postulate
  trustMe′ : ∀ {a} {A : Set a} {x y : A} → x ≡ y

transport : ℕ → String
transport = subst id (trustMe {x = ℕ} {y = String})

main = run ∘ putStrLn $ transport 42

Using trustMe inside transport, compiling the module (C-c C-x C-c) and running the resulting executable, we get... you guessed it right - a segfault.

If we instead use the postulate, we end up with:

DontTrustMe.exe: MAlonzo Runtime Error:
    postulate evaluated: DontTrustMe.trustMe′

---

If you do not intend to compile your programs (at least using MAlonzo) then inconsistency should be your only worry (on the other hand, if you only typecheck your programs then inconsistency usually is kind of a big deal).

There are two use cases I can think of at the moment, first is (as you've said) for implementing primitives. The standard library uses trustMe in three places: in implementation of decidable equality for Names (Reflection module), Strings (Data.String module) and Chars (Data.Char module).

The second one is much like the first one, except that you provide the data type and the equality function yourself and then use trustMe to skip the proving and just use the equality function to define a decidable equality. Something like:

open import Data.Bool
open import Relation.Binary
open import Relation.Binary.PropositionalEquality
open import Relation.Nullary

data X : Set where
  a b : X

eq : X → X → Bool
eq a a = true
eq b b = true
eq _ _ = false

dec-eq : Decidable {A = X} _≡_
dec-eq x y with eq x y
... | true  = yes trustMe
... | false = no whatever
  where postulate whatever : _

However, if you screw up eq, the compiler cannot save you.