Theory POTS

(*<*)
―‹ ********************************************************************
 * Project         : HOL-CSPM - Architectural operators for HOL-CSP
 *
 * Author          : Benoît Ballenghien, Safouan Taha, Burkhart Wolff.
 *
 * This file       : POTS example
 *
 * Copyright (c) 2025 Université Paris-Saclay, France
 *
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 *
 *     * Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *
 *     * Redistributions in binary form must reproduce the above
 *       copyright notice, this list of conditions and the following
 *       disclaimer in the documentation and/or other materials provided
 *       with the distribution.
 *
 *     * Neither the name of the copyright holders nor the names of its
 *       contributors may be used to endorse or promote products derived
 *       from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 ******************************************************************************›
(*>*)


chapter‹ Example: Plain Old Telephone System›

text‹The "Plain Old Telephone Service is a standard medium-size example for
     architectural modeling of a concurrent system. 

     Plain old telephone service (POTS), or plain ordinary telephone system,[1] 
     is a retronym for voice-grade telephone service employing analog signal  transmission over 
     copper loops. POTS was the standard service offering from telephone companies from 1876 until 
     1988[2] in the United States when the Integrated Services Digital Network (ISDN) Basic Rate 
     Interface (BRI) was introduced, followed by cellular telephone systems, and voice over 
     IP (VoIP). POTS remains the basic form of residential and small business service connection 
     to the telephone network in many parts of the world. The term reflects the technology that has 
     been available since the introduction of the public telephone system in the late 19th century, 
     in a form mostly unchanged despite the introduction of Touch-Tone dialing, electronic telephone 
     exchanges and fiber-optic communication into the public switched telephone network (PSTN).


     C.f. wikipedia 🌐‹https://en.wikipedia.org/wiki/Plain_old_telephone_service›.
›    (* rework this small text *)

(*<*)
theory POTS                                               
  imports "HOL-CSPM" 
begin
  (*>*)

text ‹We need to see typ‹int› as a class‹cpo›.›
  ―‹We may replace this instantiation by an import of "HOLCF-Library.Int_Discrete"›
instantiation int :: discrete_cpo
begin

definition below_int_def:
  "(x::int) ⊑ y ⟷ x = y"

instance proof
qed (rule below_int_def)

end



section‹ The Alphabet and Basic Types of POTS ›

text‹Underlying terminology apparent in the acronyms: 
▸ T-side (target side, callee side)
▸ O-side (originator (?) side, caller side)›

datatype MtcO = Osetup | Odiscon_o
datatype MctO = Obusy  | Oalert    | Oconnect | Odiscon_t
datatype MtcT = Tbusy  | Talert    | Tconnect | Tdiscon_t
datatype MctT = Tsetup | Tdiscon_o

type_synonym Phones = ‹int›


datatype channels = tcO ‹Phones × MtcO›            ―‹  ›       
  | ctO ‹Phones × MctO›            
  | tcT ‹Phones × MtcT × Phones› 
  | ctT ‹Phones × MctT × Phones› 
  | tcOdial    ‹Phones × Phones›   
  | StartReject Phones            ―‹ phone x rejects from now on to be called ›
  | EndReject   Phones            ―‹ phone x accepts from now on to be called ›
  | terminal    Phones 
  | off_hook    Phones     
  | on_hook     Phones      
  | digits     ‹Phones × Phones› ―‹ communication relation: x calls y ›     
  | tone_ring   Phones    
  | tone_quiet  Phones   
  | tone_busy   Phones
  | tone_dial   Phones    
  | connected   Phones


locale POTS = 
  fixes min_phones :: int
    and max_phones :: int
    and VisibleEvents :: ‹channels set›
  assumes min_phones_g_1[simp]          :          ‹1 ≤ min_phones›
    and max_phones_g_min_phones[simp] : ‹min_phones < max_phones›
begin

definition phones :: ‹Phones set› where ‹phones ≡ {min_phones ..  max_phones}›

lemma nonempty_phones[simp]: ‹phones ≠ {}›
  and finite_phones[simp]: ‹finite phones›
  and at_least_two_phones[simp]: ‹2 ≤ card phones›
  and not_singl_phone[simp]: ‹phones - {p} ≠ {}›
  apply (simp_all add: phones_def)
  using max_phones_g_min_phones apply linarith+
  by (metis atLeastAtMost_iff less_le_not_le max_phones_g_min_phones order_refl singletonD subsetD)



definition  EventsIPhone :: ‹Phones ⇒ channels set›
  where    ‹EventsIPhone u ≡ {tone_ring u, tone_quiet u, tone_busy u, tone_dial u, connected u}›
definition  EventsUser :: ‹Phones ⇒ channels set›
  where    ‹EventsUser u ≡ {off_hook u, on_hook u} ∪ {x . ∃ n. x = digits (u, n)}›



section‹Auxilliaries to Substructure the Specification›

abbreviation
  Tside_connected     :: ‹Phones ⇒ Phones ⇒ channels process›
  where ‹Tside_connected ts os ≡ 
           (ctT!(ts,Tdiscon_o,os) → tcT!(ts,Tdiscon_t,os) → EndReject!ts→Skip)
       ⊳ (tcT!(ts,Tdiscon_t,os) → ctT!(ts,Tdiscon_o,os) → EndReject!ts→Skip)›



abbreviation
  Oside_connected     :: ‹Phones ⇒ channels process›
  where   ‹Oside_connected ts ≡
            (ctO!(ts,Odiscon_t) → tcO!(ts,Odiscon_o) → EndReject!ts→Skip)
        ⊳ (tcO!(ts,Odiscon_o) → ctO!(ts,Odiscon_t) → EndReject!ts→Skip)›



abbreviation
  Oside1 :: ‹[Phones, Phones] ⇒ channels process›
  where 
    ‹Oside1 ts p ≡  tcOdial!(ts,p)
	                 →   (ctO!(ts,Oalert)
                         → ctO!(ts,Oconnect)
                         → (Oside_connected ts))
                      □(ctO!(ts,Oconnect) →(Oside_connected ts))
                      □(ctO!(ts,Obusy) → tcO!(ts,Odiscon_o) → EndReject!ts → Skip)›


definition
  ITside_connected    :: ‹[Phones,Phones,channels process] ⇒ channels process›
  where
    ‹ITside_connected ts os IT ≡ (ctT(ts,Tdiscon_o,os)
                                →(  (tone_busy!ts
                                       → on_hook!ts
                                       → tcT!(ts,Tdiscon_t,os)
                                       → EndReject!ts 
                                       → IT)
                                   □ (on_hook!ts
                                       → tcT!(ts,Tdiscon_t,os)
                                       → EndReject!ts
                                       → IT)
                                   ))
                                □ (on_hook!ts
                                     → tcT!(ts,Tdiscon_t,os)
                                     → ctT!(ts,Tdiscon_o,os)
                                     → EndReject!ts
                                     →IT)›


section‹A Telephone ›

(* TODO : more work on is_finite_ticks *)

(* TODO: abbreviation for Seq when unit ? *)

fixrec     T        :: ‹Phones → channels process›
  and Oside    :: ‹Phones → channels process›
  and Tside    :: ‹Phones → channels process›
  and NoReject :: ‹Phones → channels process›
  and Reject   :: ‹Phones → channels process›
  where
    T_rec        [simp del]: ‹T⋅ts        = (Tside⋅ts ; T⋅ts) ⊳ (Oside⋅ts ; T⋅ts)›
  | Oside_rec    [simp del]: ‹Oside⋅ts    = StartReject!ts 
                                              → tcO!(ts,Osetup) 
                                              → (⊓ p ∈ phones. Oside1 ts p)›
  | Tside_rec    [simp del]: ‹Tside⋅ts    = ctT?(y,z,os)|((y,z)=(ts,Tsetup)) 
                                              → StartReject!ts 
                                              → (   tcT!(ts,Talert,os)
                                                     → tcT!(ts,Tconnect,os)
                                                     →(Tside_connected ts os)
                                                  ⊓ (tcT!(ts,Tconnect,os)
                                                     → (Tside_connected ts os)))›  
  | NoReject_rec [simp del]: ‹NoReject⋅ts = StartReject!ts → Reject⋅ts›
  | Reject_rec   [simp del]: ‹Reject⋅ts   = ctT?(y,z,os)|(y=ts ∧ z=Tsetup ∧ os∈phones ∧ os≠ts)
                                              →     (tcT!(ts,Tbusy,os) → Reject⋅ts)
                                                 □  (EndReject!ts → NoReject⋅ts)›





definition Tel:: ‹Phones ⇒ channels process›
  where   ‹Tel p ≡ (T⋅p ⟦{StartReject p, EndReject p}⟧ NoReject⋅p) \ {StartReject p, EndReject p}›




section‹A Connector with the Network ›

fixrec     Call      :: ‹Phones → channels process›
  and BUSY      :: ‹Phones → Phones → channels process›
  and Connected :: ‹Phones → Phones → channels process›
  where
    Call_rec  [simp del]: ‹Call⋅os     = (tcO!  (os,Osetup) → tcOdial?(x,ts)|(x=os) → (BUSY⋅os⋅ts)) ; Call⋅os›
  | BUSY_rec  [simp del]: ‹BUSY⋅os⋅ts  = (if ts = os 
                              then ctO!(os,Obusy) → tcO!(os,Odiscon_o) → Skip
                              else ctT!(ts,Tsetup,os)
                                   →( (tcT!(ts,Tbusy,os)
                                          → ctO!(os,Obusy)
                                          → tcO!(os,Odiscon_o) → Skip)
                                       □
                                         (tcT ! (ts,Talert,os)
                                          → ctO!(os,Oalert)
                                          → tcT!(ts,Tconnect,os)
                                          → ctO!(os,Oconnect)
                                          → Connected⋅os⋅ts)
                                       □
                                         (tcT!(ts,Tconnect,os)
                                          → ctO!(os,Oconnect)
                                          → Connected⋅os⋅ts)))›
  | Connected_rec [simp del]: ‹Connected⋅os⋅ts =  (tcO!(os,Odiscon_o) →
                             (( (ctT!(ts,Tdiscon_o,os) → tcT!(ts,Tdiscon_t,os) → Skip)
                                □ 
                                (tcT!(ts,Tdiscon_t,os)→ ctT!(ts,Tdiscon_o,os) → Skip)
                              )
                              ; (ctO!(os,Odiscon_t) → Skip)))
                              □
                             (tcT!(ts,Tdiscon_t,os) →
                                     (  (ctO!(os,Odiscon_t) 
                                         → ctT!(ts,Tdiscon_o,os) 
                                         → tcO!(os,Odiscon_o) 
                                         → Skip )
                                        □
                                        (tcO!(os,Odiscon_o) 
                                         → ctT!(ts,Tdiscon_o,os) 
                                         → ctO!(os,Odiscon_t)
                                         → Skip) 
                                     )
                             )›



section‹Combining NETWORK and TELEPHONES to a SYSTEM ›

definition  NETWORK     :: ‹channels process›
  where      ‹NETWORK     ≡  (||| os ∈# (mset_set phones). Call⋅os)›

definition  TELEPHONES  :: ‹channels process›               
  where      ‹TELEPHONES  ≡  (||| ts ∈# (mset_set phones). Tel ts)›

definition  SYSTEM      :: ‹channels process›
  where      ‹SYSTEM      ≡  NETWORK ⟦VisibleEvents⟧ TELEPHONES›

text ‹We underline here the usefulness of the architectural operators, especially const‹MultiSync›
      but also const‹GlobalNdet› which appears in const‹Oside› recursive definition.›




section‹A simple Model of a User ›

fixrec     User      :: ‹Phones → channels process›
  and UserSCon  :: ‹Phones → channels process›
  where
    User_rec[simp del]  : ‹User⋅u = (off_hook!u →
                         (tone_dial!u →
                          (⊓ p ∈ phones. digits!(u,p)→tone_quiet!u→
                                          (  (tone_ring!u→connected!u→UserSCon⋅u)
                                           □ (connected!u→UserSCon⋅u)
                                           □ (tone_busy!u→on_hook!u→User⋅u)
                                          )
                          )
                         )
                       □ (connected!u → UserSCon⋅u)
                       )
                        □ (tone_ring!u→off_hook!u→connected!u →UserSCon⋅u)›
  | UserSCon_rec[simp del]: ‹UserSCon⋅u = (tone_busy!u → on_hook!u → User⋅u) ⊳ (on_hook!u → User⋅u)›



fixrec     User_Ndet      :: ‹Phones → channels process›
  and UserSCon_Ndet  :: ‹Phones → channels process›
  where
    User_Ndet_rec[simp del]  : ‹User_Ndet⋅u = (off_hook!u →
                         (tone_dial!u →
                          (⊓ p ∈ phones. digits!(u,p)→tone_quiet!u→
                                          (  (tone_ring!u→connected!u→UserSCon_Ndet⋅u)
                                           ⊓ (connected!u→UserSCon_Ndet⋅u)
                                           ⊓ (tone_busy!u→on_hook!u→User_Ndet⋅u)
                                          )
                          )
                         )
                       ⊓ (connected!u → UserSCon_Ndet⋅u)
                       )
                        ⊓ (tone_ring!u→off_hook!u→connected!u →UserSCon_Ndet⋅u)›
  | UserSCon_Ndet_rec[simp del]: ‹UserSCon_Ndet⋅u = (tone_busy!u → on_hook!u → User_Ndet⋅u) ⊓ (on_hook!u → User_Ndet⋅u)›



definition  ImplementT          :: ‹Phones ⇒ channels process›
  where    ‹ImplementT ts ≡ ((Tel ts) ⟦EventsIPhone ts ∪ EventsUser ts⟧ (User⋅ts))
                            \ (EventsIPhone ts ∪ EventsUser ts)›




section ‹ Toplevel Proof-Goals›

text‹ This has been proven in an ancient FDR model for @{term ‹max_phones = 5›}...  ›


lemma ‹∀p ∈ phones. deadlock_free (Tel p)› oops
lemma ‹∀p ∈ phones. deadlock_free_v2 (Call⋅p)› oops
lemma ‹deadlock_free_v2 NETWORK› oops
lemma ‹deadlock_free_v2 SYSTEM› oops
lemma ‹lifelock_free SYSTEM› oops 
lemma ‹∀p ∈ phones. lifelock_free (ImplementT p)› oops
lemma ‹∀p ∈ phones. Tel p ⊑FD ImplementT p› oops

lemma ‹∀p ∈ phones. Tel'⋅p  ⊑F RUN UNIV› oops
  text‹this should represent "deterministic" in process-algebraic terms. . .›


end

(*<*)
end
  (*>*)