1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
pub mod dynamic_tests {
/*
* Try the following at the command line:
*
* $ export FUNGI_VERBOSE_REDUCE=1
*
* $ cargo test examples::seq_nat_dfs -- --nocapture | less -R
*
*/
#[test]
pub fn short() { fgi_dynamic_trace!{
[Expect::SuccessXXX]
open crate::examples::seq_nat_dfs;
open crate::examples::seq_nat_gen;
/// Generate the input sequence
let s = {{force seq_gen} 10}
/// Perform the DFS
let nil = {ref (@@nil) inj1 ()}
let dfs = {thk (@@seq_dfs)
ws(@@seq_dfs){ {force seq_dfs_m} s nil }
}
let res1 = {force dfs}
/// Insert element into sequence
/// TODO
/// Re-demand output of DFS
let res2 = {force dfs}
/// Remove element from sequence
/// TODO
/// Re-demand output of DFS
let res3 = {force dfs}
/// All done
ret ()
}}
}
fgi_mod!{
open crate::examples::list_nat;
open crate::examples::seq_nat;
// before/without memoization
fn seq_dfs:(
Thk[0]
0 Ref[?](Seq[?][?]) ->
0 Ref[?](List[?][?]) ->
{?;?}
F Ref[?](List[?][?])
) = {
#seq. #res.
let s = {get seq}
unroll match s {
_nil => { ret res }
leaf => {
let (nm, x) = leaf
{force ref_cons} [?][?][?][?] nm x res
}
bin => {
unpack (X1,X2,Y) bin = bin
let (nm, lev, left, right) = bin
let res = {{force seq_dfs} right res}
{{force seq_dfs} left res}
}
}
}
// use memoization on recursive calls
fn seq_dfs_m:(
Thk[0]
0 Ref[?](Seq[?][?]) ->
0 Ref[?](List[?][?]) ->
{?;?}
F Ref[?](List[?][?])
) = {
#seq. #res.
let s = {get seq}
unroll match s {
_nil => { ret res }
leaf => {
let (nm, x) = leaf
{force ref_cons} [?][?][?][?] nm x res
}
bin => {
unpack (X1,X2,Y) bin = bin
let (nm, lev, left, right) = bin
let (res, _res) = {memo{nm,(@1)}{ {force seq_dfs_m} right res }}
let (res, _res) = {memo{nm,(@2)}{ {force seq_dfs_m} left res }}
ret res
}
}
}
}