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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
|
//usr/bin/env myatscc "$0"; exit
(* ****** ****** *)
//
// Author: Hongwei Xi
// Authoremail: gmhwxiATgmailDOTcom
// Time: the 13th of July, 2016
//
(* ****** ****** *)
//
(*
##myatsccdef=\
patsopt --constraint-ignore --dynamic $1 | \
tcc -run -DATS_MEMALLOC_LIBC -I${PATSHOME} -I${PATSHOME}/ccomp/runtime -
*)
//
(* ****** ****** *)
//
#include
"share/atspre_staload.hats"
#include
"share/HATS/atspre_staload_libats_ML.hats"
//
(* ****** ****** *)
//
extern
fun
{a,b:t0p}
memo : (a -<cloref1> b) -> (a -<cloref1> b)
//
(* ****** ****** *)
//
extern
fun{}
fib(n: int): int
//
(* ****** ****** *)
//
extern
fun{}
fib_rec(n: int): int
//
implement
{}(*tmp*)
fib_rec = fib<>
//
(* ****** ****** *)
//
implement
{}(*tmp*)
fib(n) =
if n >= 2
then (fib_rec(n-1) + fib_rec(n-2)) % 1000000 else n
// end of [if]
//
(* ****** ****** *)
//
extern
val
fib_memo
: (int) -<cloref1> int
//
implement
{}(*tmp*)
fib_rec(n) = fib_memo(n)
//
(* ****** ****** *)
local
staload FM = "libats/ML/SATS/funmap.sats"
staload _(*anon*) = "libats/ML/DATS/funmap.dats"
staload _(*anon*) = "libats/DATS/funmap_avltree.dats"
implement(key)
$FM.compare_key_key<key>(x, y) = gcompare_val_val<key> (x, y)
in
implement
{a,b}
memo(f) = let
//
typedef key = a and itm = b
typedef map = $FM.map(key,itm)
val M = ref<map> ($FM.funmap_nil<>())
//
in
//
(
lam a =<cloref1>
case+ $FM.funmap_search(!M, a) of
| ~Some_vt b => b
| ~None_vt _ => b where
{
val b = f a
val-~None_vt() = let
val (vbox pf | t) = ref_get_viewptr(M)
in
$effmask_ref($FM.funmap_insert(!t, a, b))
end
}
)
//
end // end of [memo]
end // end of [local]
(* ****** ****** *)
implement
fib_memo = memo<int,int>(lam(n) => fib(n))
(* ****** ****** *)
implement
main0() =
{
val N = 1000
val () = println! ("fib(", N, ") = ", fib(N))
}
(* ****** ****** *)
(* end of [memoization.dats] *)
|
