{ 
[A,S1,S2:Type]. [F1:S1 
A (S1 
Top)]. [F2:S2 A (S2 Top)].
[G:Top]. [as:A List]. [s1:S1]. [s2:S2].
(data-stream(better-parallel-dataflow(
2;
k.[rec-dataflow(s1;s,a.F1[s;a]);
rec-dataflow(s2;s,a.F2[s;a])][k];
g.G[g 0;g 1]);as)
~ data-stream(rec-dataflow(<s1, s2>;s,a.let s1,s2 = s
in let s1',out1 = F1[s1;a]
in let s2',out2 = F2[s2;a]
in <<s1', s2'>
, G[out1;out2]
>);as)) }
{ Proof }
Definitions occuring in Statement :
better-parallel-dataflow: better-parallel-dataflow,
data-stream: data-stream(P;L),
rec-dataflow: rec-dataflow(s0;s,m.next[s; m]),
select: l[i],
uall: [x:A]. B[x],
top: Top,
so_apply: x[s1;s2],
apply: f a,
lambda: x.A[x],
function: x:A B[x],
spread: spread def,
pair: <a, b>,
product: x:A B[x],
cons: [car / cdr],
nil: [],
list: type List,
natural_number: $n,
universe: Type,
sqequal: s ~ t
Definitions :
uall: [x:A]. B[x],
top: Top,
member: t 
T,
all: x:A. B[x],
subtype: S 
T,
better-parallel-dataflow: better-parallel-dataflow,
select: l[i],
so_apply: x[s1;s2],
pi2: snd(t),
dataflow-ap: df(a),
eval-parallel-dataflow: eval-parallel-dataflow(n;s;m),
primrec: primrec(n;b;c),
select-tuple: select-tuple,
ycomb: Y,
ifthenelse: if b then t else f fi ,
eq_int: (i =
j),
btrue: tt,
bfalse: ff,
le_int: i 
z j,
bnot: 
b,
lt_int: i <z j,
implies: P 
Q,
pi1: fst(t),
rec-dataflow: rec-dataflow(s0;s,m.next[s; m])
Lemmas :
top_wf,
data-stream-cons,
pi1_wf_top
\mforall{}[A,S1,S2:Type]. \mforall{}[F1:S1 {}\mrightarrow{} A {}\mrightarrow{} (S1 \mtimes{} Top)]. \mforall{}[F2:S2 {}\mrightarrow{} A {}\mrightarrow{} (S2 \mtimes{} Top)]. \mforall{}[G:Top]. \mforall{}[as:A List].
\mforall{}[s1:S1]. \mforall{}[s2:S2].
(data-stream(better-parallel-dataflow(
2;\mlambda{}k.[rec-dataflow(s1;s,a.F1[s;a]); rec-dataflow(s2;s,a.F2[s;a])][k];
\mlambda{}g.G[g 0;g 1]);as) \msim{} data-stream(rec-dataflow(<s1, s2>s,a.let s1,s2 = s
in let s1',out1 =
F1[s1;a]
in let s2',out2 =
F2[s2;a]
in <<s1', s2'>
, G[out1;out2]
>);as))
Date html generated:
2011_08_10-AM-08_16_08
Last ObjectModification:
2011_06_18-AM-08_30_50
Home
Index