Previous Up Next
B.3 Subject reduction for the rewriting semantics (Theorem 1.2)


We first show a couple of properties relating typing and the set of declared labels.
Lemma 7  []   For any class C such that A |- C : z(r)BV,W, then dl(C) = dom(B).
The proof of this lemma is omitted because it is a straighforward induction on the depth of A |- C : z(r)BV,W.
Lemma 8  []   For any selective refinement clauses S such that A |- S :: BW B'W', V', we have dom(B') \ dom(B) dl(S).

Proof:
Selective refinement clauses can always be written as |i I Ki K'i |> P. A proof of A |- S :: BW B'W', V' can only end with rule Modifier in which the derivation of each premise ends with a rule Modifier-Clause. Hence, we have at least the judgments
  Ai |- Ki :: Bi (18)
  Bi B (19)
  Ai |- Ki' :: B'i (20)
  B' = i i B'i (21)
Hence,
  dom(B') \ dom(B) dom(B') \ (i I dom(Bi)) by (19)
    = (i I dom(B'i)) \ (i I dom(Bi)) by (21)
    = i I ( dom(B'i) \ (j I dom(Bj)))
    i I ( dom(B'i) \ dom(Bi))
    = i I (dl(K'i) \ dl(Ki))
    = dl(S)


We now show that filter rewriting |- preserves typing. We denote with B \ L the set of pairs l : t that belongs to B and such that l L.
Lemma 9  [Filter rewriting]   If all the following conditions hold
C with S |- C'      A |- C :: z(r)BW,V
A |- S :: B1W1 B2W2,V2      dl(S) dom(B1) =      B B1      B2 | dom(B1) B1     
then A |- C' :: z(r)(B (B2 \ L))W',V' for some W' W (W2 dom(B (B2 \ L))), V' V (V2 ( dom(B1) \ L)), and L (dl(S) \ dl(C')) ( dom(B1) \ dom(B)).

Proof:
In this proof, we abbreviate dom(B) by B, for sake of conciseness.

Basic cases.
Filter-Apply.
Let us assume that
  K1 & K |> P with K1 K2 |> Q | S     
       | K2 & K |> P & Q or dl(K1) \ dl(K2) (1)
  A |- K1 & K |> P :: z(r)BW, V (2)
  A |- K1 K2 |> Q | S :: B1W1 B2W2,V2 (3)
  ((dl(K2) \ dl(K1)) dl(S)) B1 = (4)
  B B1 (5)
  B2 | B1 B1 (6)
The judgments (2) and (3) are respectively derived by
[Sub]
[Reaction]
[Synchronization]
A' |- K1 :: B1(7)      A' |- K :: B0  (8)
A' |- K1 & K :: B1' B0  (9)
A + A' |- P (10)      A' = fn(K1 & K(11)
A |- K1 & K |> P :: z(r)(B1' B0)cl(K1 & K),
A |- K1 & K |> P :: z(r)(B1' B0)W,V
and,
[Modifier]+[Sub]
A'' |- K1 :: B1(12)
A'' |- K2 :: B2(14)
A + A'' |- Q  (15)
     B1' B1 (13)
A'' = fn(K2(16)
W2' = cls(B1W1, K1 K2)
A |- K1 K2 |> Q :: B1W1 B2'W2',dl(K1) \ dl(K2)
   
A |- K1 K2 |> Q | S :: B1W1 B2W2,V2
where B = B1' B0 (17), cl(K1 & K) W (18), B2' B2 (19), W2' W2 and dl(K1) \ dl(K2) V2 (20).

From (7) and (12), A' and A'' coincide on fn(K1) because they assign the same types to fn(K1). Moreover, due to the scope rules of reaction rules and the selection operator, we can safely assume that A' A'' = fn(K1). Thus, by Lemma 2 applied to (8), and (14) we derive A'+A'' |- K :: B0 (21) and A'+A'' |- K2 :: B2(22). Similarly, by lemma 2 applied to (10) and (15), we also derive A + A' + A'' |- P (23) and A + A' + A'' |- Q  (24).

Foremost we prove the linearity of K2 & K. Notice that dl(K2) = (dl(K2) \ dl(K1)) (dl(K2) dl(K1)) and both left and right hand-sides of the have an empty intersection with dl(K). This follows from (4) and from the linearity of K1 & K.

By rule Synchronization with premises (22) and (21), we derive A' + A'' |- K2 & K :: B2' B0 (25). Also, combining the judgments (23) and (24) yields A + A' + A'' |- P & Q (26) using rule Parallel. By premises (11) and (16) we have A' A'' = fn(K) fn(K1) fn(K2). By (16) and (12), we have fn(K1) fn(K2). Hence A' + A'' = fn(K2 & K(27). Therefore, by Reaction with premises (25), (26), and (27) we derive
A |- K2 & K |> P & Q :: z(r)(B2' B0)cl(K2 & K),      (28).
By rule Abstract, we also deduce
A |- dl(K1) \ dl(K2) :: z(r)B1'' ,dl(K1) \ dl(K2)     (29)
where B1'' = B1' \ dl(K2(30). Hence, Disjunction allows to derive:
A |- K2 & K |> P & Q or L' :: z(r)(B2' B0 B1'' )cl(K2 & K), dl(K1) \ dl(K2)      (31)
and by rule Sub:
A |- K2 & K |> P & Q or L' :: z(r)(B2' B0 B1'' )W', V'      (32)
where W' = W cl(K2 & K) and V' = V (dl(K1) \ dl(K2)).

Let L be (dl(S) \ (dl(K2) dl(K) dl(K1))) ((B1 \ B) \ dl(K2)), or equivalently, (dl(S) \ (B'2 B0 B'1)) ((B1 \ B) \ B'2(33). Observe that L is choosen so as to satisfy the condition L (dl(S) \ dl(C')) (B1 \ B). To conclude, we verify that other constraints of the lemma are satisfied for the judgment (32). That is,
  1. B2' B0 B1'' = B (B2 \ L). By (6)(13)(17)(19) it is enough to check the set equality: B'2 B0 B''1 = B (B2 \ L). Since both sides of (33) are restrictions outside of the set B'2, we have L B'2 B (34). Therefore,
    B2' B0 B1''
      = B2' B0 (B1' \ dl(K2)) by definition of B'1
      = B2' B0 (B1' \ B'2)) by (16)
      = B2' B0 B1'
      = B2' B by definition of B
      = B (B2 \ L) by (34)


  2. W' W (W2 (B (B2 \ L)). Because W' = W cl(K2 & K) and cl(K2 & K) W2 by (18), and cl(K2 & K) dl(K2 & K) = B'2 B0 B (B2 \ L) by the equality above.

  3. V' V (V2 (B1 \ L)). By definition, V' = V (dl(K1) \ dl(K2)) and dl(K1) \ dl(K2) V2 by (20). It remains to prove that dl(K1) \ dl(K2) B1 \ L. Since dl(K1) \ dl(K2) B1, it suffices to show that (dl(K1) \ dl(K2)) L = . Obviously, (dl(K1) \ dl(K2)) (dl(S) \ dl(K2 & K & K1)) = , whilst (dl(K1) \ dl(K2)) ((B1 \ B) \ dl(K2))= , since dl(K1) = B'1 B.
Filter-End.
Let us assume
  M |> P with 0 | M |> P (1)
  A |- M |> P :: z(r)BW,V (2)
  A |- 0 :: B1W1 B2W2,V2 (3)
  dl(0) B1 = (4)
  B B1 (5)
Since in (3) B2 must be the empty set, we conclude from (2) by choosing L = B1 \ B, W' = W, and V' = V.

Filter-Abstract.
Let us assume
  L' with S | L'
  A |- L' :: z(r)BW,V (1)
  A |- S :: B1W1 B2W2, V2
  dl(S) B1 = (2)
  B B1 (3)
  B2 | B1 B1 (4)
A derivation of (1) must contain an instance of rule Abstract, hence A |- L' :: z(r)B,V and B = V = L(5). Let L be (dl(S) \ L') (B1 \ B). We show that (1) satisfies the lemma:
  1. B (B2 \ L) =B. Since by (4) B2 is compatible with B1 and with B by (3), it suffices to show that B2 \ L B. By (5), it follows that L is equal to (dl(S) B1) \ B (6). Hence:
    B2 \ L = ((B2 | B1) (B2 \ B1)) \ L
      (B1 dl(S)) \ L by (4) and Lemma 8
      = (B1 dl(S)) \ ((B1 dl(S)) \ B)
      = (B1 dl(S)) B


  2. W W (W2 (B B2 \ L)). Obvious.

  3. V V (V2 (B1 \ L)). Obvious.
Inductive cases.
Filter-Next.
Let us assume
  M |> P with K1 K2 |> Q | S | C' (1)
  dl(K1) dl(M) (2)
  A |- M |> P :: z(r)BW,V (3)
  A |- K1 K2 |> Q | S :: B1W1 B2W2, V2 (4)
  ((dl(K2) \ dl(K1)) dl(S)) B1 = (5)
  B B1 (6)
  B2 | B1 B1 (7)
The selection clauses S are of the form |i IKi' K''i |> Qi. A derivation of (4) must contain an instance of Modifier, with premises:
  A |- K1 K2 |> Q :: B1W1 B2'W2', V2' (8)
  (A |- Ki' Ki'' |> Qi :: B1W1 Bi''Wi'', Vi'')i I
where
  B2'' = i I B''i  
  B2 = B2' B2'' (9)
  W2'' = i I Wi''  
  W2 = W2' W2'' (10)
  V2'' = i I Vi''  
  V2 = V2' V2'' (11)
 
Hence, by rule Modifier, we derive
A |- S :: B1W1 B2''W2'', V2''     (12)
A derivation of (1) must end with an instance of rule Filter-Next, hence M |> P with S | C(13). By induction hypothesis applied to (13), (3), (5), (12)(6), and (7) there must exist some L', W', and V' such that
  A |- C' :: z(r)(B (B''2 \ L'))W', V' (14)
  L' (dl(S) \ dl(C')) (B1 \ B) (15)
  W' W (W''2 (B (B''2 \ L'))) (16)
  V' V (V''2 (B1 \ L')) (17)
Let us prove that A |- C' :: z(r)(B (B2 \ L))W', V' (18), for L = L' B'2 \ (B1 B''2) and check that L, W', V' satisfy the conditions of the lemma. We first prove that L (((dl(K2) \ dl(K1)) dl(S)) \ dl(C')) (B1 \ B(19). By Lemma 8 applied to (8), we have B2'\ B1 dl(K2) \ dl(K1(20). Notice that dl(C') = B B''2 \ L' by Lemma 7 and (14), hence dl(C') B B''2 (21). Thus, we have:
  L = L' B'2 \ (B1 B''2)
  = L' (B'2 \ B1) \ B''2  
  L' (dl(K2) \ dl(K1)) \ B''2 by (20)
  = L' (dl(K2) \ dl(K1)) \ (B B''2) by (5)
  L' (dl(K2) \ dl(K1)) \ dl(C') by (21)
  = (dl(S) \ dl(C')) (B1 \ B) (dl(K2) \ dl(K1)) \ dl(C') by (15)
  = ((dl(K2) \ dl(K1)) dl(S)) \ dl(C') B1 \ B
To conclude, we check the following properties:
  1. B (B2 \ L) =B (B''2 \ L'). Since by (7) B2 and B1 agree, and so do B''2 and B by (6) and (9), it suffices to check the equality of their domains. By
    B (B2 \ L)   = B (B2 \ (L' B'2 \ (B1 B''2)))
    = B (B2 \ (B'2 \ (B1 B''2))) \ L'
    = B ((B'2 B''2) \ (B'2 \ (B1 B''2))) \ L'
    = B ((B'2 \ (B'2 \ (B1 B''2)))
      (B'2 \ (B'2 \ (B1 B''2))) ) \ L'
    = B ((B1 B''2) | B'2 B''2) \ L'
    =
    B
     
    (B1 | B'2) \ L'
    B
     
    (B''2 | B'2) \ L'
    B''2 \ L'
    (B''2 \ L')
    = B (B''2 \ L')


  2. W' W (W2 B (B2 \ L)). This follows from (16), W2'' W2 (by (10)), and B (B2 \ L) =B (B''2 \ L').

  3. V' V (V2 (B1 \ L)). This follows from (17), V2 V2' (by (11)) and L' L (by definition of L').
Filter-Or.
Let us assume that:
  C1 or C2 with S |- C' (1)
  A |- C1 or C2 :: z(r)BW,V (2)
  A |- S :: B1 B2W2,V2 (3)
  dl(S) B1 = (4)
  B B1 (5)
  B2 | B1 B1 (6)
A derivation of (2) must end with an instance of rule Disjunction, followed by a sequence of rules Sub. Hence B is of the form B'1 B'2 (7) and:
  A |- C1 :: z(r)B'1W'1, V'1 (8)
  A |- C2 :: z(r)B'2W'2, V'2 (9)
  W'1 W'2 W (10)
  (V'1 \ (B'2 \ V'2)) (V'2 \ (B'1 \ V'1)) V (11)
The condition (4) implies that dl(S) Bi = for i {1,2} (12). The reduction (1) implies that C' is of the form C'1 or C'2 such that Ci with S | C'i for i {1,2} (13). By induction hypothesis applied to (13), (8) and (9), (3), (12), (5), and (6), it follows that there exist some Li, W''i, and V''i such that
  A |- C'i :: z(r)(B'i (B2 \ Li))W''i, V''i (14)
  Li (dl(S) \ dl(C'i)) (B1 \ B'i) (15)
  W''i W'i (W2 B'i (B2 \ Li)) (16)
  V''i V'i (V2 (B1 \ Li)) (17)
for i {1,2}. By rule Disjunction applied to the two cases of (14) and since B'1, B'2 and B''2 are compatible by (6), (5) and by the definition of B'1 and B'2, we have:
A |- C'1 or C'2 :: z(r)(B'1 B'2 (B2 \ L1) (B2 \ L2)W', V'     (18)
where
  W' = W''1 W''2
  V' = V''1 \ (B'2 (B2 \ L2) \ V''2) V''2 \ (B'1 (B2 \ L1) \ V''1)
Let L be L1 L2. Then
  L = L1 L2
  ((dl(S) \ dl(C1)) (B1 \ B'1)) ((dl(S) \ dl(C2)) (B1 \ B'2)) by (15)
  (dl(S) \ dl(C1)) (dl(S) \ dl(C2)) (B1 \ B'1) (B1 \ B'2) by distributivity
  = (dl(S) \ (dl(C1) dl(C2))) (B1 \ (B'1 B'2))
  = (dl(S) \ dl(C)) (B1 \ B) (19)

To conclude, we prove that (18) satisfies the constraints of the lemma. Indeed, we have:
  1. B (B2 \ L) = B'1 B'2 (B2 \ L1) (B2 \ L2). Since B = B'1 B'2 and B2 \ L = B2 \ L1 B2 \ L2.

  2. W' W (W2 B (B2 \ L)). Since W' = W''1 W''2, it suffices to show that W''i W (W2 B (B2 \ L)), for i {1,2}. This follows by (16), (10) and because B'i (B2 \ Li) B (B2 \ L) (by previous item).

  3. V' V (V2 (B1 \ L)). It suffices to show that both
    V''1 \ (B'2 (B2 \ L2) \ V''2) V (V2 (B1 \ L))
    and
    V''2 \ (B'1 (B2 \ L1) \ V''1) V (V2 (B1 \ L))
    Each of these two containments follows by (17), which establishes a stronger relation between a superset of the left hand side and two subsets of the two right hand sides.





Theorem 3  [Process Reduction]   Process rewriting |- preserves typing.

We show that class reduction |-x and process reduction |- preserve typing, simultaneously.

That is, we prove that
  1. if A + x : [r] , x.(B | F) |- C:: z(r)BW,V and C |-x C' then A + x : [r] , x.(B | F) |- C':: z(r)BW,V;

  2. if A |- P and P |- P' then A |- P'.
Proof: We reason by induction on the depth of the proofs of C |-x C' and P |- P'. We write Ax for A + x : [r] , x.(B | F).

Basic cases for class reduction.
Self.
Let self(zC |-x C {z x} and let Ax |- self(zC :: z(r)BW,V. A derivation of this judgment must end with an instance of Self-Binding, followed by a sequence of Sub rules. Hence,
Ax + z : [r] , z.(B | F) |- C :: z(r)B W',V'
with W' W and V' V. Then, by Lemma 5, we have:
Ax |- C {z x} :: z(r)B W',V'
We conclude Ax |- C {z x} :: z(r)BW,V by rule Sub.

Or-Pat.
Let J1 or J2 |> P |-x J1 |> P or J2 |> P and let Ax |- J1 or J2 |> P :: z(r)BW, V (1). The derivation of this judgment must end with the following derivation followed by a sequence of Sub rules:
[Reaction]
[Alternative]
A' |- J1 :: B1      A' |- J2 :: B2     
A' |- J1 or J2 :: B
Ax + A' |- P      dom(A') = fn(J1 or J2(2)
Ax |- J1 or J2 |> P :: z(r)Bcl(J1) cl(J2),
where B is B1 B2 and cl(J1) cl(J2) W. Since fn(J1 or J2) = fn(J1) = fn(J2), we have:
[Disjunction]
A' |- Ji :: Bi      Ax+ A' |- P      dom(A') = fn(Ji)
Ax |- Ji |> P :: z(r)Bicl(Ji),
 i = 1, 2
Ax |- J1 |> P or J2 |> P :: z(r)Bcl(J1) cl(J2),
The we conclude Ax |- J1 |> P or J2 |> P :: z(r)BW, V by rule Sub.

Abstract-Cut.
Let C or L |-x C or L' and Ax |- C or L :: z(r)BW,V and L' = L \ dl(C), with L L'. Therefore L' L (1). The derivation of the judgment Ax |- C or L :: z(r)BW,V must end with the following derivation followed by a sequence of Sub rules:
[Disjunction]
[Abstract]
dom(B2) = L
Ax |- L :: z(r)B2, L
     Ax|- C :: z(r)B1W1,V1
L'' = L \ ( dom(B1) \ V1) (2)
Ax |- C or L :: z(r)(B1 B2)W1, V1 L''
where B = B1 B2, W1 W (3) and V1 L'' V (4).

We first observe that B1 B2 = B1 (B2 | L'). Therefore we can derive:
[Disjunction]
[Abstract]
dom(B2 | L') = L'
Ax |- L' :: z(r)(B2 | L'), L'
     Ax|- C :: z(r)B1W1,V1
L''' = L' \ ( dom(B1) \ V1) (5)
Ax |- C or L' :: z(r)(B1 B2)W1, V1 L'''
By (2), (5) and (1), we derive V1 L''' V1 L''. Hence, by (3), (4) and rule Sub, we obtain Ax |- C or L' :: z(r)(B1 B2)W, V.

Class-Abstract.
Let C or |-x C and Ax |- C or :: z(r)BW,V. The derivation of this judgment must end with rule Disjunction followed by a sequence of Sub rules:
[Disjunction]
Ax |- C :: z(r)BW', V'      Ax|- :: z(r),
Ax |- C or :: z(r)BW',V'
where W' W and V' V. Then, by rule Sub applied to Ax |- C :: z(r)BW',V', we obtain Ax |- C :: z(r)BW,V.

Basic cases for processes.
Class-Var.
Let us assume A |- class c = self(zC in P (1) and class c = C in P |- P {x C}. The final part of the derivation of (1) must have the form
Class
A |- C :: z(r)BW,V (2)
A + c : " Gen (r, B, A). z(r)BW,V |- P (3)
A |- class c = C in P
By Lemma 6 applied to (2) and (3), we derive A |- P {c C}.

Inductive cases for classes.
Class-Context.
Let Ax |- E {C} :: z(r)BW,V and E {C} |-x E {C'}. By inductive hypothesis, if Ax |- C :: z(r)B'W', V' then Ax |- C' :: z(r)B'W',V', since C |-x C'. The judgment Ax |- E {C'} :: z(r)BV follows by induction on the structure of E {}. The details are omitted.

Match.
Let us assume that A |- match C with S end : z(r)BW, V (1) and match C with S end C(2). We must prove that A |- C' : z(r)BW, V (3)

A derivation of (1) must end with an instance of rule Refinement followed by a sequence of Sub. Hence, B is of the form B1 B2 (4) and
  A |- C :: z(r)B1W1, V1 (5)
  A |- S :: B1W1 B2W2, V2 (6)
  dl(S) dom(B1) = (7)
  W1 W2 W (8)
  V1 V2 V (9)
The derivation of (2) must contain a rule Match with the premises:
  C with S C' (10)
  dl(S) dl(C') (11)
From (4) it follows that B2 | dom(B1) dom(B2(12). Lemma 9 applied to (10), (5), (6), (7), and (12) implies that
  A |- C' :: z(r)(B1 (B2 \ L))W',V' (13)
  L (dl(S) \ dl(C')) ( dom(B1) \ dom(B1)) (14)
  W' W1 (W2 dom(B1 (B2 \ L))) (15)
  V' V1 (V2 ( dom(B1) \ L)) (16)
The property (11) combined with (14) imply that L is empty. Therefore W' W1 W2 and V' V1 V2. Hence (3) follows by (13), (8), (9) and rule Sub.

Inductive cases for processes.
Class-Red.
Let A |- obj x = C init P in Q (1) and obj x = C init P in Q |- obj x = C' init P in P', under the assumption that C |-x C(2).

A derivation of (1) has the shape
[Object]
[Self-Binding]
A + x : [r], x :(B | F) |- C :: z(r)BW, (3)
A |- self(xC :: z(r)BW,
r = B | M      X= Gen (r, B, A) \ ctv(B|W)
A + x : " X. [r], x : " X. (B | F) |- P      A + x : " X. [r] |- Q
A |- obj x = C init P in Q
By induction hypothesis applied to (2) and (3), we obtain the judgment A + x : [r], x :(B | F) |- C' :: z(r)BW,, which we can substitute in the previous derivation, thus concluding A |- obj x = C' init P in Q.



Previous Up Next