Skip to content

Alpha-equivalence for recursive let-bindings gives false positives

I was looking at the Eq (DeBruijn CoreExpr) instance and I noticed that the types of recursive let-bindings aren't checked for alpha-equivalence:

https://gitlab.haskell.org/ghc/ghc/-/blob/master/compiler/GHC/Core/Map/Expr.hs#L166-174

    go (Let (Rec ps1) e1) (Let (Rec ps2) e2)
      = equalLength ps1 ps2
      && D env1' rs1 == D env2' rs2
      && D env1' e1  == D env2' e2
      where
        (bs1,rs1) = unzip ps1
        (bs2,rs2) = unzip ps2
        env1' = extendCMEs env1 bs1
        env2' = extendCMEs env2 bs2

But that means that:

let (x :: Int) = x in x

and

let (y :: Bool) = y in y

are considered alpha-equivalent, whilst they're not.

The same mistake is made in eqExpr https://gitlab.haskell.org/ghc/ghc/-/blob/master/compiler/GHC/Core/Utils.hs#L2148-2154

    go env (Let (Rec ps1) e1) (Let (Rec ps2) e2)
      = equalLength ps1 ps2
      && all2 (go env') rs1 rs2 && go env' e1 e2
      where
        (bs1,rs1) = unzip ps1
        (bs2,rs2) = unzip ps2
        env' = rnBndrs2 env bs1 bs2

Note that the types don't have checked for non-recursive bindings (and aren't checked): when the RHSs are the same, the types of the bindings must be the same.

To upload designs, you'll need to enable LFS and have an admin enable hashed storage. More information