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
|
<!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>Storage Options</TITLE>
<META NAME="description" CONTENT="Storage Options">
<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="node10.html">
<LINK REL="previous" HREF="node8.html">
<LINK REL="up" HREF="node6.html">
<LINK REL="next" HREF="node10.html">
</HEAD>
<BODY >
<!--Navigation Panel-->
<A NAME="tex2html235"
HREF="node10.html">
<IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next"
SRC="/usr/share/latex2html/icons/next.png"></A>
<A NAME="tex2html231"
HREF="node6.html">
<IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up"
SRC="/usr/share/latex2html/icons/up.png"></A>
<A NAME="tex2html225"
HREF="node8.html">
<IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous"
SRC="/usr/share/latex2html/icons/prev.png"></A>
<A NAME="tex2html233"
HREF="node4.html">
<IMG WIDTH="65" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="contents"
SRC="/usr/share/latex2html/icons/contents.png"></A>
<A NAME="tex2html234"
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="tex2html236"
HREF="node10.html">Life Time of Terms</A>
<B> Up:</B> <A NAME="tex2html232"
HREF="node6.html">Input</A>
<B> Previous:</B> <A NAME="tex2html226"
HREF="node8.html">Attributes of Terms</A>
<BR>
<BR>
<!--End of Navigation Panel-->
<H2><A NAME="SECTION00063000000000000000"> </A>
<A NAME="storage-options-input"> </A>
<BR>
Storage Options
</H2>
<P>
The system (currently) provides two storage options, selectable on a per
phylum basis.
For both of them a C data type is generated for each phylum, together with
a `create' function for each operator.
In the default storage option
each operator `application' just yields a new
`memory cell' containing pointers to the arguments of the operator, with
initialised attributes.
The second storage option, called `uniq',<A NAME="150"> </A> is more interesting.
It will guarantee that if the operator is once called with a certain
set of arguments, each additional call with the
<EM>same</EM>
arguments will yield a pointer to the cell that was created by the first
call.
The result is that common (sub)trees are automatically shared.
This technique is known as `hashed-consing'<A NAME="152"> </A> (because consing is the LISP
function to create new cells, and hashing is used to implement this
uniqueness of representation property).
In this storage option attributes will be initialised only
at the first call.
Obviously, side effects on subterms can jeopardize this scheme: terms
maintained under unique storage should not be modified (though their
attributes may be modified because they do not contribute to the uniqueness).
An example<A NAME="153"> </A> application is as follows.
<PRE><HR><!--lgrindfile: uniq_phylum_example.k 19:44 Oct 21 1992-->
ID {<B>uniq</B>}:Str(<B>casestring</B>)
{ <B>short</B> type = UNDEF;};
<HR></PRE>
<P>
Suppose that for each defining occurrence of an identifier a term is
created with the attribute
<I>type</I>
appropriately set,
then to check the type one merely has to `create' it again, e.g. through
<I>Str(yourstring)</I>
and look at the attribute.
In the same way one can check if the identifier is already defined at a
defining occurrence.
A sketch of this code is as follows.
It checks that an identifier is defined only once, and defined before its use.
<A NAME="157"> </A><A NAME="158"> </A>
<PRE><HR><!--lgrindfile: symbol_table_example.k 19:44 Oct 21 1992-->
<I>/* defining occurrence */</I>
id = Str(mkcasestring(<code>"foo"</code>));
<B>if</B> (id->type != UNDEF) error(<code>"doubly defined"</code>);
id->type = USED; <I>/* set other attributes here as well */</I>
<BR>
<I>/* applied occurrence */</I>
id = Str(mkcasestring(<code>"foo"</code>));
<B>if</B> (id->type == UNDEF) error(<code>"undefined"</code>);
<HR></PRE>
Of course, this is not the most sophisticated example of a symbol table,
but serves as an example.
<P>
An essential condition on phyla definitions is that all constituent phyla of
a `uniq' phylum are also `uniq'.
The term processor warns at generation time about violations of this condition.
<P>
As will be explained in Section <A HREF="node31.html#cook-ag">4.3</A>, in some cases a phylum
that has inherited attributes should <EM>not</EM> be stored `uniq'.
The following example<A NAME="162"> </A><A NAME="163"> </A>
declares ID as explicitly `non-uniq'.
<PRE><HR><!--lgrindfile: non_uniq_declaration_example.k 15:00 Sep 28 1992-->
ID {! <B>uniq</B>}:;
<HR></PRE>
Phyla may not be declared both <I>{uniq}</I> and <I>{!uniq}</I>.
<P>
<HR>
<!--Navigation Panel-->
<A NAME="tex2html235"
HREF="node10.html">
<IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next"
SRC="/usr/share/latex2html/icons/next.png"></A>
<A NAME="tex2html231"
HREF="node6.html">
<IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up"
SRC="/usr/share/latex2html/icons/up.png"></A>
<A NAME="tex2html225"
HREF="node8.html">
<IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous"
SRC="/usr/share/latex2html/icons/prev.png"></A>
<A NAME="tex2html233"
HREF="node4.html">
<IMG WIDTH="65" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="contents"
SRC="/usr/share/latex2html/icons/contents.png"></A>
<A NAME="tex2html234"
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="tex2html236"
HREF="node10.html">Life Time of Terms</A>
<B> Up:</B> <A NAME="tex2html232"
HREF="node6.html">Input</A>
<B> Previous:</B> <A NAME="tex2html226"
HREF="node8.html">Attributes of Terms</A>
<!--End of Navigation Panel-->
<ADDRESS>
<I></I>
<BR><I>2000-04-17</I>
</ADDRESS>
</BODY>
</HTML>
|
