Beluga-lang / Beluga

Contextual types meet mechanized metatheory!
http://complogic.cs.mcgill.ca/beluga/
GNU General Public License v3.0
184 stars 16 forks source link

Substitution variable splitting doesn't cooperate with dependencies #162

Open tsani opened 4 years ago

tsani commented 4 years ago

Load this signature

LF a : type = ;

schema ctx = a;

LF nat : type =
  | zero : nat
  | succ : nat → nat
;

rec len : {g : ctx} {$S : [⊢ g]} [⊢ nat] =
/ total g (len g _) /
mlam g, $S ⇒ case [g] of
  | [] ⇒ [⊢ zero]
  | [g, x : a] ⇒ case [⊢ $S] of
    | [⊢ $S, M] ⇒ ?
;

It produces the following error

## Type Reconstruction: t/code/success/svar-len.bel ##
t/code/success/svar-len.bel, line 14, column 17:

######   COVERAGE FAILURE: Case expression doesn't cover: ######
##       CASE(S) NOT COVERED:
(1)
Z : [g |- a], X : [ |-  g], $S : [ |-  g, x : a], g* : ctx ;  |-
  [g, x1 |-  X[.., x1], Z]

##

The missing case g, x1 |- X[.., x1], Z appears wrong: the substitution sends g to a closed context, so why should the patterns for $S have a nonempty LF context?

Ailrun commented 4 years ago

I'm not sure whether it's normal or not, so I wrote this for recording purpose.

By repeating the last pattern, Beluga repeats the same non-covered cases.

LF a : type = ;

schema ctx = a;

LF nat : type =
  | zero : nat
  | succ : nat → nat
;

rec len : {g : ctx} {$S : [⊢ g]} [⊢ nat] =
/ total g (len g _) /
mlam g, $S ⇒ case [g] of
  | [] ⇒ [⊢ zero]
  | [g, x : a] ⇒ case [⊢ $S] of
    | [⊢ $S, M] ⇒ ?
    | [⊢ $S, M] ⇒ ?
    | [⊢ $S, M] ⇒ ?
;
## Type Reconstruction: t/code/success/svar-len.bel ##
t/code/success/svar-len.bel, line 14, column 17:

######   COVERAGE FAILURE: Case expression doesn't cover: ######
##       CASE(S) NOT COVERED:
(1)
Z : [g |- a], X : [ |-  g], $S : [ |-  g, x : a], g* : ctx ;  |-
  [g, x1 |-  X[.., x1], Z]
(2)
Z : [g |- a], X : [ |-  g], $S : [ |-  g, x : a], g* : ctx ;  |-
  [g, x1 |-  X[.., x1], Z]
(3)
Z : [g |- a], X : [ |-  g], $S : [ |-  g, x : a], g* : ctx ;  |-
  [g, x1 |-  X[.., x1], Z]

##
tsani commented 4 years ago

That definitely seems wrong, and it's probably related. My guess is that coverage checking for substitution variables is plain broken at the moment.