[Agda] termination & open public

Noam Zeilberger noam+agda at cs.cmu.edu
Mon Mar 17 20:44:01 CET 2008


Is this a bug?  It seems that definitions exported by "open M public"
are not available to the termination checker.  Here is an example,
which is intended to capture some reasoning about the well-foundedness
of a subformula relationship:
=====
module Main where

  module Formula where
    data Form1 : Set where
      NAT : Form1
      D : Form1 -> Form1

  module Formula' where
    open Formula public

  module Subformula where
    open Formula'

    data Form2 : Set where
      OBU : Form2
      E : Form2 -> Form2

    data opt (A : Set) : Set where
      Some : A -> opt A
      None : opt A

    data Foo1 : opt Form1 -> Form1 -> Set where
      Fu : {A : Form1} -> Foo1 (Some A) (D A)
      Fz : Foo1 None NAT
      Fs : {x : opt Form1} -> Foo1 x NAT -> Foo1 x NAT

    data Foo2 : opt Form2 -> Form2 -> Set where
      Gu : {A : Form2} -> Foo2 (Some A) (E A)
      Gz : Foo2 None OBU
      Gs : {x : opt Form2} -> Foo2 x OBU -> Foo2 x OBU

    data _<<1_ : Form1 -> Form1 -> Set where
      1< : {A B : Form1} -> Foo1 (Some A) B -> A <<1 B

    data _<<2_ : Form2 -> Form2 -> Set where
      2< : {A B : Form2} -> Foo2 (Some A) B -> A <<2 B

    data Access1 (f : Form1) : Set where
      Acc1 : ({f' : Form1} -> (f' <<1 f) -> Access1 f') -> Access1 f

    data Access2 (f : Form2) : Set where
      Acc2 : ({f' : Form2} -> (f' <<2 f) -> Access2 f') -> Access2 f

    wfacc1 : (A : Form1) -> {B : Form1} -> (B <<1 A) -> Access1 B
    wfacc1 (D B) (1< Fu) = Acc1 (wfacc1 B)
    wfacc1 NAT (1< (Fs p)) = wfacc1 NAT (1< p)

    wfacc2 : (A : Form2) -> {B : Form2} -> (B <<2 A) -> Access2 B
    wfacc2 (E B) (2< Gu) = Acc2 (wfacc2 B)
    wfacc2 OBU (2< (Gs p)) = wfacc2 OBU (2< p)
=====

Form1 and Form2 are equivalent definitions of formulas, except that
Form2 is defined inside Subformula, while Form1 is exported from
Formula'.  All the other definitions are also alpha-equivalent.  Both
wfacc1 and wfacc2 should be well-founded by the lexicographic ordering
on their two arguments -- however, only wfacc2 passes the termination
checker.  Looking at the output of "agda -v 10", I think that the
termination checker is claiming ignorance about the first argument of
wfacc1.

Noam


More information about the Agda mailing list