[Agda] (s ◃ m ) * (s' ◃ n)

Sergei Meshveliani mechvel at botik.ru
Sat Jan 11 12:07:02 CET 2014


See the attached   Integer2.agda
(about 150 lines).

My implementation for 

  s◃m*s'◃n : (s s' : Sign) → (m n : ℕ) →
                             (s ◃ m ) * (s' ◃ n) ≡ (s *s s') ◃ (m *n n)

takes about 30 lines (not counting import declarations and comments). 
1/3 of it take 5 lemmata (which probably need to be in the library). 

These 30 line size looks a bit strange for such a trivial thing.

About termination, emacs colors, and reports under emacs:
I never tried anything special for adga-mode, it just happen to set so.

Regards,

------
Sergei




On Fri, 2014-01-10 at 23:32 +0100, Andreas Abel wrote:
> As always, if you want a more thorough investigation of your case, 
> provide self-contained Agda code.
> 
> Best,
> Andreas
> 
> On 10.01.2014 16:36, Sergei Meshveliani wrote:
> > On Fri, 2014-01-10 at 14:13 +0100, Andreas Abel wrote:
> >> On 10.01.2014 13:30, Sergei Meshveliani wrote:
> >>> 1) The part
> >>>
> >>>         e
> >>>      where
> >>>      e : ....
> >>>      e =
> >>>
> >>> needs to be skipped (as I usually do), so that the RHS to be just
> >>> (begin ... end).
> >>> But the checker   (MAlonzo of January 8, 2014)
> >>>
> >>> does not allow this, showing      [ lemma s' s 0 m ]   with yellow
> >>> (probably a termination problem).
> >>> So that I have avoided a termination problem by a lucky occasion with
> >>> extra  "e : ...".
> >>
> >> Termination errors have red background.  Yellow is for unsolved
> >> meta-variables.  By giving the type signature for e you probably helped
> >> Agda to solve some meta-variables.
> >
> >
> > I tried compilation from the command line, and it reports a termination
> > check fail
> > (see my respond to my letter).
> >
> > In _my_ emacs setting, a  termination check fail  looks as follows:
> >
> > several calls of the same function are shown _yellow_, and nothing is
> > reported
> > (in the case of unsolved meta, it usually reports something).
> >
> > Concerning emacs:
> > in command line, I see the reports in full. May be, it is also possible
> > in emacs -- if I knew how to scroll the lower part, in which the report
> > is shown.
> >
> > Regards,
> >
> > ------
> > Sergei
> >
> >
> 
> 

-------------- next part --------------
module Integer2 where

open import Level    using () renaming (zero to 0ℓ)
open import Function using (_$_; case_of_)
open import Algebra.FunctionProperties as FuncProp using ()
open import Algebra using (CommutativeSemiring; module CommutativeSemiring;
                           CommutativeRing; module CommutativeRing)
open import Algebra.Structures using (IsAbelianGroup; module IsAbelianGroup)  
import Algebra.Props.Ring 
open import Relation.Nullary using (Dec; ¬_; yes; no)
open import Relation.Binary using (Setoid; DecSetoid; DecTotalOrder; 
                                                         module DecTotalOrder)
open import Relation.Binary.PropositionalEquality as PE using (_≡_; _≢_)
open PE.≡-Reasoning renaming (_≡⟨_⟩_ to _≡[_]_; begin_ to ≡begin_;
                                                       _∎ to _≡end)
open import Data.Empty   using (⊥-elim) 
open import Data.Product using (_×_; _,_; proj₁; proj₂)
open import Data.Nat as Nat using (ℕ; _>_; s≤s; z≤n) 
                            renaming (suc to sucN; _+_ to _+n_; _*_ to _*n_)
open import Data.Nat.Properties as NatProp using ()
open import Data.Sign    as Sign using (Sign) renaming (_*_ to _*s_)
open import Data.Integer as Int using (ℤ; module ℤ; sign; _◃_; ∣_∣)
open import Data.Integer.Properties as IntProp using 
                                              (commutativeRing; sign-◃; abs-◃)



------------------------------------------------------------------------------
natDTO       = Nat.decTotalOrder
natDecSetoid = DecTotalOrder.Eq.decSetoid natDTO    -- for ℕ           
natSetoid    = DecSetoid.setoid natDecSetoid
natEquiv     = Setoid.isEquivalence natSetoid

intSetoid : Setoid 0ℓ 0ℓ 
intSetoid = DecSetoid.setoid Int.decSetoid 

intDTO = Int.decTotalOrder 

natCommSemir = NatProp.commutativeSemiring
open CommutativeSemiring natCommSemir using () renaming (*-comm to *n-comm)

intCommRing = IntProp.commutativeRing
open CommutativeRing intCommRing 
               using (+-isAbelianGroup; _+_; -_; _-_; _*_; +-assoc; 
                      +-comm; *-assoc; *-comm; distrib; *-identity; *-cong)
               renaming (ring to intRing)

module FPs  = FuncProp (_≡_ {A = Sign})

open ℤ
open IsAbelianGroup +-isAbelianGroup using () 
                              renaming (identity to zero; inverse to opposite) 

------------------------------------------------------------------------------
*n-0 : (n : ℕ) → (n *n 0) ≡ 0
*n-0 n =  PE.trans (*n-comm n 0) PE.refl

*0 : (x : ℤ) → x * (+ 0) ≡ + 0     
*0 x =  
       ≡begin  x * (+ 0)          ≡[ PE.refl ] 
               sg ◃ (∣ x ∣ *n 0)  ≡[ PE.cong (_◃_ sg) $ *n-0 ∣ x ∣ ]
               sg ◃ 0             ≡[ PE.refl ]
               + 0
       ≡end 
       where   sg = (sign x) *s Sign.+

0* :  (x : ℤ) → (+ 0) * x ≡ + 0     
0* x =  PE.trans (*-comm (+ 0) x) $ *0 x

◃-0 : (s : Sign) → s ◃ 0 ≡ + 0 
◃-0 _ = PE.refl            

*s-comm : FPs.Commutative _*s_
*s-comm Sign.+ Sign.+ = PE.refl
*s-comm Sign.+ Sign.- = PE.refl
*s-comm Sign.- Sign.+ = PE.refl
*s-comm Sign.- Sign.- = PE.refl

------------------------------------------------------------------------------
s◃m*s'◃n : (s s' : Sign) → (m n : ℕ) → 
                           (s ◃ m ) * (s' ◃ n) ≡ (s *s s') ◃ (m *n n)
s◃m*s'◃n _ _  0 _ =  PE.refl 
s◃m*s'◃n s s' m 0 =  e         
    where
    -- Reduce "m 0" to the case of "0 m".
    -- Note:  omitting  "e : ..."  leads to a termination problem.

    e : (s ◃ m) * (+ 0) ≡ (s *s s') ◃ (m *n 0)
    e = ≡begin   
            (s ◃ m) * (+ 0)        ≡[ *0 (s ◃ m) ]
            + 0                    ≡[ PE.sym $ 0* (s ◃ m) ]
            (+ 0) * (s ◃ m)        ≡[ PE.cong (\z → z * (s ◃ m)) $ ◃-0 s' ]
            (s' ◃ 0) * (s ◃ m)     ≡[ s◃m*s'◃n s' s 0 m ]
            (s' *s s) ◃ (0 *n m)   ≡[ PE.cong (_◃_ (s' *s s)) $ *n-comm 0 m ]
            (s' *s s) ◃ (m *n 0)   ≡[ PE.cong (\sg → sg ◃ (m *n 0)) $ 
                                                               *s-comm s' s ]
            (s *s s') ◃ (m *n 0)
        ≡end
                  
s◃m*s'◃n s s' (sucN m) (sucN n) = 
  ≡begin 
    (s ◃ m') * (s' ◃ n')                                          ≡[ PE.refl ]
    (sign (s ◃ m') *s sign (s' ◃ n')) ◃ ((∣ s ◃ m' ∣) *n (∣ s' ◃ n' ∣))

                           ≡[ PE.cong (\sg → sg ◃ part2) $ 
                                      PE.cong₂ _*s_ (sign-◃ s m) (sign-◃ s' n)
                            ]
    (s *s s') ◃ ((∣ s ◃ m' ∣) *n (∣ s' ◃ n' ∣))
                         ≡[ PE.cong (_◃_ (s *s s')) $ 
                                    PE.cong₂ _*n_ (abs-◃ s m') (abs-◃ s' n') ]
    (s *s s') ◃ (m' *n n')
  ≡end
  where
  m'    = sucN m
  n'    = sucN n
  part2 = (∣ s ◃ m' ∣) *n (∣ s' ◃ n' ∣)


More information about the Agda mailing list