author | oheimb |
Fri, 31 Jan 1997 16:51:58 +0100 | |
changeset 2569 | 3a8604f408c9 |
parent 2277 | 9174de6c7143 |
permissions | -rw-r--r-- |
1274 | 1 |
(* |
2 |
ID: $Id$ |
|
1479 | 3 |
Author: Franz Regensburger |
1274 | 4 |
Copyright 1993 Technische Universitaet Muenchen |
5 |
||
2569 | 6 |
NOT SUPPORTED ANY MORE. USE HOLCF/ex/Stream.thy INSTEAD. |
7 |
||
1274 | 8 |
Theory for streams without defined empty stream |
9 |
'a stream = 'a ** ('a stream)u |
|
10 |
||
11 |
The type is axiomatized as the least solution of the domain equation above. |
|
12 |
The functor term that specifies the domain equation is: |
|
13 |
||
14 |
FT = <**,K_{'a},U> |
|
15 |
||
16 |
For details see chapter 5 of: |
|
17 |
||
18 |
[Franz Regensburger] HOLCF: Eine konservative Erweiterung von HOL um LCF, |
|
19 |
Dissertation, Technische Universit"at M"unchen, 1994 |
|
20 |
*) |
|
21 |
||
22 |
Stream = Dnat2 + |
|
23 |
||
24 |
types stream 1 |
|
25 |
||
26 |
(* ----------------------------------------------------------------------- *) |
|
27 |
(* arity axiom is validated by semantic reasoning *) |
|
28 |
(* partial ordering is implicit in the isomorphism axioms and their cont. *) |
|
29 |
||
30 |
arities stream::(pcpo)pcpo |
|
31 |
||
32 |
consts |
|
33 |
||
34 |
(* ----------------------------------------------------------------------- *) |
|
35 |
(* essential constants *) |
|
36 |
||
1479 | 37 |
stream_rep :: "('a stream) -> ('a ** ('a stream)u)" |
38 |
stream_abs :: "('a ** ('a stream)u) -> ('a stream)" |
|
1274 | 39 |
|
40 |
(* ----------------------------------------------------------------------- *) |
|
41 |
(* abstract constants and auxiliary constants *) |
|
42 |
||
1479 | 43 |
stream_copy :: "('a stream -> 'a stream) ->'a stream -> 'a stream" |
1274 | 44 |
|
1479 | 45 |
scons :: "'a -> 'a stream -> 'a stream" |
46 |
stream_when :: "('a -> 'a stream -> 'b) -> 'a stream -> 'b" |
|
47 |
is_scons :: "'a stream -> tr" |
|
48 |
shd :: "'a stream -> 'a" |
|
49 |
stl :: "'a stream -> 'a stream" |
|
50 |
stream_take :: "nat => 'a stream -> 'a stream" |
|
51 |
stream_finite :: "'a stream => bool" |
|
52 |
stream_bisim :: "('a stream => 'a stream => bool) => bool" |
|
1274 | 53 |
|
54 |
rules |
|
55 |
||
56 |
(* ----------------------------------------------------------------------- *) |
|
57 |
(* axiomatization of recursive type 'a stream *) |
|
58 |
(* ----------------------------------------------------------------------- *) |
|
59 |
(* ('a stream,stream_abs) is the initial F-algebra where *) |
|
60 |
(* F is the locally continuous functor determined by functor term FT. *) |
|
61 |
(* domain equation: 'a stream = 'a ** ('a stream)u *) |
|
62 |
(* functor term: FT = <**,K_{'a},U> *) |
|
63 |
(* ----------------------------------------------------------------------- *) |
|
64 |
(* stream_abs is an isomorphism with inverse stream_rep *) |
|
65 |
(* identity is the least endomorphism on 'a stream *) |
|
66 |
||
1479 | 67 |
stream_abs_iso "stream_rep`(stream_abs`x) = x" |
68 |
stream_rep_iso "stream_abs`(stream_rep`x) = x" |
|
69 |
stream_copy_def "stream_copy == (LAM f. stream_abs oo |
|
2277
9174de6c7143
moved Lift*.* to Up*.*, renaming of all constans and theorems concerned,
oheimb
parents:
1479
diff
changeset
|
70 |
(ssplit`(LAM x y. (|x , (fup`(up oo f))`y|) )) oo stream_rep)" |
1479 | 71 |
stream_reach "(fix`stream_copy)`x = x" |
1274 | 72 |
|
73 |
defs |
|
74 |
(* ----------------------------------------------------------------------- *) |
|
75 |
(* properties of additional constants *) |
|
76 |
(* ----------------------------------------------------------------------- *) |
|
77 |
(* constructors *) |
|
78 |
||
1479 | 79 |
scons_def "scons == (LAM x l. stream_abs`(| x, up`l |))" |
1274 | 80 |
|
81 |
(* ----------------------------------------------------------------------- *) |
|
82 |
(* discriminator functional *) |
|
83 |
||
84 |
stream_when_def |
|
2277
9174de6c7143
moved Lift*.* to Up*.*, renaming of all constans and theorems concerned,
oheimb
parents:
1479
diff
changeset
|
85 |
"stream_when == (LAM f l.ssplit `(LAM x l.f`x`(fup`ID`l)) `(stream_rep`l))" |
1274 | 86 |
|
87 |
(* ----------------------------------------------------------------------- *) |
|
88 |
(* discriminators and selectors *) |
|
89 |
||
1479 | 90 |
is_scons_def "is_scons == stream_when`(LAM x l.TT)" |
91 |
shd_def "shd == stream_when`(LAM x l.x)" |
|
92 |
stl_def "stl == stream_when`(LAM x l.l)" |
|
1274 | 93 |
|
94 |
(* ----------------------------------------------------------------------- *) |
|
95 |
(* the taker for streams *) |
|
96 |
||
97 |
stream_take_def "stream_take == (%n.iterate n stream_copy UU)" |
|
98 |
||
99 |
(* ----------------------------------------------------------------------- *) |
|
100 |
||
1479 | 101 |
stream_finite_def "stream_finite == (%s.? n.stream_take n `s=s)" |
1274 | 102 |
|
103 |
(* ----------------------------------------------------------------------- *) |
|
104 |
(* definition of bisimulation is determined by domain equation *) |
|
105 |
(* simplification and rewriting for abstract constants yields def below *) |
|
106 |
||
107 |
stream_bisim_def "stream_bisim == |
|
108 |
(%R.!s1 s2. |
|
1479 | 109 |
R s1 s2 --> |
1274 | 110 |
((s1=UU & s2=UU) | |
111 |
(? x s11 s21. x~=UU & s1=scons`x`s11 & s2 = scons`x`s21 & R s11 s21)))" |
|
112 |
||
113 |
end |
|
114 |
||
115 |
||
116 |
||
117 |