author | noschinl |
Mon, 13 Apr 2015 20:11:12 +0200 (2015-04-13) | |
changeset 60054 | ef4878146485 |
parent 58864 | 505a8150368a |
child 64565 | 5069ddebc937 |
permissions | -rw-r--r-- |
6118 | 1 |
(* Title: Pure/General/source.ML |
6116
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
2 |
Author: Markus Wenzel, TU Muenchen |
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
3 |
|
8806 | 4 |
Coalgebraic data sources -- efficient purely functional input streams. |
6116
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
5 |
*) |
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
6 |
|
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
7 |
signature SOURCE = |
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
8 |
sig |
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
9 |
type ('a, 'b) source |
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
10 |
val get: ('a, 'b) source -> 'a list * ('a, 'b) source |
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
11 |
val unget: 'a list * ('a, 'b) source -> ('a, 'b) source |
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
12 |
val get_single: ('a, 'b) source -> ('a * ('a, 'b) source) option |
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
13 |
val exhaust: ('a, 'b) source -> 'a list |
19485 | 14 |
val map_filter: ('a -> 'b option) -> ('a, 'c) source -> ('b, ('a, 'c) source) source |
6116
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
15 |
val filter: ('a -> bool) -> ('a, 'b) source -> ('a, ('a, 'b) source) source |
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
16 |
val of_list: 'a list -> ('a, 'a list) source |
37903
b7ae269c0d68
replaced Source.of_list_limited by slightly more economic Source.of_string_limited;
wenzelm
parents:
29606
diff
changeset
|
17 |
val exhausted: ('a, 'b) source -> ('a, 'a list) source |
6116
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
18 |
val of_string: string -> (string, string list) source |
37903
b7ae269c0d68
replaced Source.of_list_limited by slightly more economic Source.of_string_limited;
wenzelm
parents:
29606
diff
changeset
|
19 |
val of_string_limited: int -> string -> (string, substring) source |
27732 | 20 |
val source': 'a -> 'b Scan.stopper -> ('a * 'b list -> 'c list * ('a * 'b list)) -> |
6116
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
21 |
('b, 'e) source -> ('c, 'a * ('b, 'e) source) source |
27732 | 22 |
val source: 'a Scan.stopper -> ('a list -> 'b list * 'a list) -> |
6116
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
23 |
('a, 'd) source -> ('b, ('a, 'd) source) source |
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
24 |
end; |
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
25 |
|
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
26 |
structure Source: SOURCE = |
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
27 |
struct |
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
28 |
|
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
29 |
|
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
30 |
(** datatype source **) |
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
31 |
|
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
32 |
datatype ('a, 'b) source = |
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
33 |
Source of |
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
34 |
{buffer: 'a list, |
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
35 |
info: 'b, |
58850 | 36 |
drain: 'b -> 'a list * 'b}; |
6116
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
37 |
|
58850 | 38 |
fun make_source buffer info drain = |
39 |
Source {buffer = buffer, info = info, drain = drain}; |
|
6116
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
40 |
|
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
41 |
|
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
42 |
(* get / unget *) |
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
43 |
|
58850 | 44 |
fun get (Source {buffer = [], info, drain}) = |
45 |
let val (xs, info') = drain info |
|
46 |
in (xs, make_source [] info' drain) end |
|
47 |
| get (Source {buffer, info, drain}) = (buffer, make_source [] info drain); |
|
6116
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
48 |
|
58850 | 49 |
fun unget (xs, Source {buffer, info, drain}) = make_source (xs @ buffer) info drain; |
6116
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
50 |
|
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
51 |
|
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
52 |
(* variations on get *) |
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
53 |
|
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
54 |
fun get_single src = |
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
55 |
(case get src of |
15531 | 56 |
([], _) => NONE |
57 |
| (x :: xs, src') => SOME (x, unget (xs, src'))); |
|
6116
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
58 |
|
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
59 |
fun exhaust src = |
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
60 |
(case get src of |
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
61 |
([], _) => [] |
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
62 |
| (xs, src') => xs @ exhaust src'); |
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
63 |
|
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
64 |
|
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
65 |
(* (map)filter *) |
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
66 |
|
58850 | 67 |
fun drain_map_filter f src = |
6116
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
68 |
let |
58850 | 69 |
val (xs, src') = get src; |
19485 | 70 |
val xs' = map_filter f xs; |
6116
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
71 |
in |
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
72 |
if null xs orelse not (null xs') then (xs', src') |
58850 | 73 |
else drain_map_filter f src' |
6116
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
74 |
end; |
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
75 |
|
58850 | 76 |
fun map_filter f src = make_source [] src (drain_map_filter f); |
19485 | 77 |
fun filter pred = map_filter (fn x => if pred x then SOME x else NONE); |
6116
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
78 |
|
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
79 |
|
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
80 |
|
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
81 |
(** build sources **) |
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
82 |
|
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
83 |
(* list source *) |
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
84 |
|
58850 | 85 |
fun of_list xs = make_source [] xs (fn xs => (xs, [])); |
37903
b7ae269c0d68
replaced Source.of_list_limited by slightly more economic Source.of_string_limited;
wenzelm
parents:
29606
diff
changeset
|
86 |
|
b7ae269c0d68
replaced Source.of_list_limited by slightly more economic Source.of_string_limited;
wenzelm
parents:
29606
diff
changeset
|
87 |
fun exhausted src = of_list (exhaust src); |
b7ae269c0d68
replaced Source.of_list_limited by slightly more economic Source.of_string_limited;
wenzelm
parents:
29606
diff
changeset
|
88 |
|
b7ae269c0d68
replaced Source.of_list_limited by slightly more economic Source.of_string_limited;
wenzelm
parents:
29606
diff
changeset
|
89 |
|
b7ae269c0d68
replaced Source.of_list_limited by slightly more economic Source.of_string_limited;
wenzelm
parents:
29606
diff
changeset
|
90 |
(* string source *) |
6181 | 91 |
|
40627
becf5d5187cc
renamed raw "explode" function to "raw_explode" to emphasize its meaning;
wenzelm
parents:
38253
diff
changeset
|
92 |
val of_string = of_list o raw_explode; |
23875
e22705ccc07d
added of_string_limited (more efficient for partial scans);
wenzelm
parents:
23700
diff
changeset
|
93 |
|
37903
b7ae269c0d68
replaced Source.of_list_limited by slightly more economic Source.of_string_limited;
wenzelm
parents:
29606
diff
changeset
|
94 |
fun of_string_limited limit str = |
58850 | 95 |
make_source [] (Substring.full str) |
96 |
(fn s => |
|
37903
b7ae269c0d68
replaced Source.of_list_limited by slightly more economic Source.of_string_limited;
wenzelm
parents:
29606
diff
changeset
|
97 |
let |
b7ae269c0d68
replaced Source.of_list_limited by slightly more economic Source.of_string_limited;
wenzelm
parents:
29606
diff
changeset
|
98 |
val (s1, s2) = Substring.splitAt (s, Int.min (Substring.size s, limit)); |
b7ae269c0d68
replaced Source.of_list_limited by slightly more economic Source.of_string_limited;
wenzelm
parents:
29606
diff
changeset
|
99 |
val cs = map String.str (Substring.explode s1); |
b7ae269c0d68
replaced Source.of_list_limited by slightly more economic Source.of_string_limited;
wenzelm
parents:
29606
diff
changeset
|
100 |
in (cs, s2) end); |
9123
f8f54877a18c
added exhausted: ('a, 'b) source -> ('a, 'a list) source;
wenzelm
parents:
8806
diff
changeset
|
101 |
|
6116
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
102 |
|
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
103 |
|
23700
fb1102e98cd4
moved source cascading from scan.ML to source.ML;
wenzelm
parents:
23682
diff
changeset
|
104 |
(** cascade sources **) |
6116
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
105 |
|
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
106 |
(* state-based *) |
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
107 |
|
58864 | 108 |
fun drain_source' stopper scan (state, src) = |
23700
fb1102e98cd4
moved source cascading from scan.ML to source.ML;
wenzelm
parents:
23682
diff
changeset
|
109 |
let |
58850 | 110 |
val drain = Scan.drain get stopper; |
111 |
val (xs, s) = get src; |
|
23700
fb1102e98cd4
moved source cascading from scan.ML to source.ML;
wenzelm
parents:
23682
diff
changeset
|
112 |
val ((ys, (state', xs')), src') = |
fb1102e98cd4
moved source cascading from scan.ML to source.ML;
wenzelm
parents:
23682
diff
changeset
|
113 |
if null xs then (([], (state, [])), s) |
58864 | 114 |
else drain (Scan.error scan) ((state, xs), s); |
23700
fb1102e98cd4
moved source cascading from scan.ML to source.ML;
wenzelm
parents:
23682
diff
changeset
|
115 |
in (ys, (state', unget (xs', src'))) end; |
fb1102e98cd4
moved source cascading from scan.ML to source.ML;
wenzelm
parents:
23682
diff
changeset
|
116 |
|
58864 | 117 |
fun source' init_state stopper scan src = |
118 |
make_source [] (init_state, src) (drain_source' stopper scan); |
|
6116
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
119 |
|
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
120 |
|
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
121 |
(* non state-based *) |
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
122 |
|
58864 | 123 |
fun drain_source stopper scan = |
124 |
Scan.unlift (drain_source' stopper (Scan.lift scan)); |
|
23700
fb1102e98cd4
moved source cascading from scan.ML to source.ML;
wenzelm
parents:
23682
diff
changeset
|
125 |
|
58864 | 126 |
fun source stopper scan src = |
127 |
make_source [] src (drain_source stopper scan); |
|
6116
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
128 |
|
8ba2f25610f7
files scan.ML, source.ML, symbol.ML, pretty.ML moved to Pure/General;
wenzelm
parents:
diff
changeset
|
129 |
end; |