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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
|
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
<!--Converted with LaTeX2HTML 98.1p1 release (March 2nd, 1998)
originally by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds
* revised and updated by: Marcus Hennecke, Ross Moore, Herb Swan
* with significant contributions from:
Jens Lippmann, Marek Rouchal, Martin Wilck and others -->
<HTML>
<HEAD>
<TITLE>Memo Functions</TITLE>
<META NAME="description" CONTENT="Memo Functions">
<META NAME="keywords" CONTENT="tpman">
<META NAME="resource-type" CONTENT="document">
<META NAME="distribution" CONTENT="global">
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
<LINK REL="STYLESHEET" HREF="tpman.css">
<LINK REL="next" HREF="node35.html">
<LINK REL="previous" HREF="node33.html">
<LINK REL="up" HREF="node28.html">
<LINK REL="next" HREF="node35.html">
</HEAD>
<BODY >
<!--Navigation Panel-->
<A NAME="tex2html547"
HREF="node35.html">
<IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next"
SRC="/usr/share/latex2html/icons/next.png"></A>
<A NAME="tex2html543"
HREF="node28.html">
<IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up"
SRC="/usr/share/latex2html/icons/up.png"></A>
<A NAME="tex2html537"
HREF="node33.html">
<IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous"
SRC="/usr/share/latex2html/icons/prev.png"></A>
<A NAME="tex2html545"
HREF="node4.html">
<IMG WIDTH="65" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="contents"
SRC="/usr/share/latex2html/icons/contents.png"></A>
<A NAME="tex2html546"
HREF="node58.html">
<IMG WIDTH="43" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="index"
SRC="/usr/share/latex2html/icons/index.png"></A>
<BR>
<B> Next:</B> <A NAME="tex2html548"
HREF="node35.html">Beyond Symbol Tables</A>
<B> Up:</B> <A NAME="tex2html544"
HREF="node28.html">Cookbook</A>
<B> Previous:</B> <A NAME="tex2html538"
HREF="node33.html">Rewrite Systems and Functions</A>
<BR>
<BR>
<!--End of Navigation Panel-->
<H2><A NAME="SECTION00096000000000000000">
Memo Functions</A>
</H2>
Memo functions remember (`memorize') their results.
If called again with the same arguments, they will return the remembered value.
Memo functions are functional in their behaviour:
a subsequent call with the same argument
will yield the same result.
In their performance they are not functional:
the subsequent call will not need recomputation.
Memo functions of course constitute a time/space trade off<A NAME="1170"> </A>.
Their performance comes at the expense of memory to store
the results (and, in some schemes, memory to store the operands).
<P>
Using the term processor, memo-functions of one argument can be implemented as an
attribute of the phylum of the argument term.
Memo-functions of more than one argument can be implemented as an attribute
of a uniquely represented term that represents the function call.
E.g. for a function <I>F</I> of two arguments one introduces a term <I>F_memo(x,y)</I> of
which the function result is an attribute.
In both approaches it is essential that the arguments of the function are represented
uniquely.
<P>
An example to illustrate memo functions is the Fibonacci function.
This is a good example because the standard recursive definition recomputes
the same result over and over again.
For example, fib(5) uses fib(4) and fib(3), but for fib(4), fib(3) is also
computed.
It is also a silly example, because the best solution is a simple iteration.
Furthermore we use abstract data type natural numbers, and the cost
of the rewrite functions outweighs the costs of Fibonacci.
The non-memo solution looks as follows, the phylum and rewrite definitions
are from the previously discussed natural numbers example.
<A NAME="1173"> </A><A NAME="1174"> </A>
<A NAME="1175"> </A>
<A NAME="1176"> </A>
<PRE><HR><!--lgrindfile: fibonacci.k 15:29 Jul 19 1996-->
<I>/* Fibonacci */</I>
%{
<B>#include</B> <code>"rk.h"</code>
%}
<BR>
nat fib(nat $n) {
zero(): { <B>return</B> s(zero()); }
s(zero()): { <B>return</B> s(zero()); }
s(s(x)): { <B>return</B> rewrite_nat( plus(fib(x), fib(s(x)))); }
}
<HR></PRE>
The memo version looks as follows, the natural number phylum is made unique
and has an attribute <I>fib</I> to store the result.
<PRE><HR><!--lgrindfile: fibonacci_memo.k 15:30 Jul 19 1996-->
<I>/* Fibonacci with memo function */</I>
nat{<B>uniq</B>}: zero()
| s(nat)
| plus(nat nat)
{ nat fib = (nat)0; }
;
<BR>
<I>/* rewrite rules omitted */</I>
<BR>
%{
<B>#include</B> <code>"rk.h"</code>
%}
<BR>
nat fibm(nat n) {
nat result;
<B>if</B> (n->fib != (nat)0) <B>return</B> n->fib;
<B>with</B>(n){
zero(): { result = s(zero()); }
s(zero()): { result = s(zero()); }
s(s(x)): { result = rewrite_nat( plus(fibm(x), fibm(s(x)))); }
}
n->fib = result;
<B>return</B> result;
}
<HR></PRE>
Note the initialisation of the attribute <I>fib</I>.
We take the nil pointer to mean `no value known yet'.
In the second line of the function body the test is made for this, and in the second last
line the result is stored.
Measurements show that computing fib(15) (which is 987) takes 1973 calls on
<I>fib</I>.
In <I>fibm</I> the with-statement is entered only 16 times.
However, as stated, using rewriting to compute addition makes this hardly noticeable
on total run time.
Both functions compute <I>plus(377, 610)</I> exactly once,
and this takes most of the time.
<P>
<HR>
<!--Navigation Panel-->
<A NAME="tex2html547"
HREF="node35.html">
<IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next"
SRC="/usr/share/latex2html/icons/next.png"></A>
<A NAME="tex2html543"
HREF="node28.html">
<IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up"
SRC="/usr/share/latex2html/icons/up.png"></A>
<A NAME="tex2html537"
HREF="node33.html">
<IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous"
SRC="/usr/share/latex2html/icons/prev.png"></A>
<A NAME="tex2html545"
HREF="node4.html">
<IMG WIDTH="65" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="contents"
SRC="/usr/share/latex2html/icons/contents.png"></A>
<A NAME="tex2html546"
HREF="node58.html">
<IMG WIDTH="43" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="index"
SRC="/usr/share/latex2html/icons/index.png"></A>
<BR>
<B> Next:</B> <A NAME="tex2html548"
HREF="node35.html">Beyond Symbol Tables</A>
<B> Up:</B> <A NAME="tex2html544"
HREF="node28.html">Cookbook</A>
<B> Previous:</B> <A NAME="tex2html538"
HREF="node33.html">Rewrite Systems and Functions</A>
<!--End of Navigation Panel-->
<ADDRESS>
<I></I>
<BR><I>2000-04-17</I>
</ADDRESS>
</BODY>
</HTML>
|
