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
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
|
<HTML>
<!--
***********************************************************************
FUNNELWEB MANUAL WEB PAGE
=========================
Copyright (c) Ross N. Williams 1992,1999. All rights reserved.
Permission is granted to redistribute and use this manual in
any medium, with or without modification, provided that all
notices (including, without limitation, the copyright
notice, this permission notice, any record of modification,
and all legal notices) are preserved on all copies, that all
modifications are clearly marked, and that modified versions
are not represented as the original version unless all the
modifications since the manual's original release by Ross N.
Williams (www.ross.net) consist of translations or other
transformations that alter only the manual's form, not its
content. THIS MANUAL IS PROVIDED "AS IS" AND WITHOUT ANY
EXPRESS OR IMPLIED WARRANTIES, INCLUDING, WITHOUT
LIMITATION, THE IMPLIED WARRANTIES OF MERCHANTIBILITY AND
FITNESS FOR A PARTICULAR PURPOSE. TO THE EXTENT PERMITTED BY
LAW THERE IS ABSOLUTELY NO WARRANTY.
***********************************************************************
-->
<HEAD>
<TITLE>6.7 Generics</TITLE>
<STYLE TYPE="text/css"> <!-- A {text-decoration: none} // --> </STYLE>
</HEAD>
<BODY BACKGROUND="binary/background.gif"
BGCOLOR="#FFFFFF"
TEXT="#000000"
VLINK="#660000"
LINK="#FF0000"
ALINK="#CC0000">
<TABLE WIDTH="490">
<TR>
<TD WIDTH="130" VALIGN="top">
<IMG SRC="binary/d_clear.gif" ALT="" WIDTH="130" HEIGHT="1"><BR>
<FONT SIZE="2">
<BR>
<A HREF="http://www.ross.net/"
TARGET="rosshome"
onClick="window.open('','rosshome','location,status,menubar,scrollbars,resizable',false).focus(); return true;"
>
<IMG SRC="binary/rossnet_logo.gif"
WIDTH="64" HEIGHT="32"
BORDER="0" ALT="RossNet"
HSPACE="0" VSPACE="1"></A><BR>
<BR>
<A HREF="../index.shtml"
TARGET="funnelweb"
onClick="window.open('','funnelweb','location,status,menubar,scrollbars,resizable',false).focus(); return true;"
>
<IMG SRC="binary/linklogo.gif"
WIDTH="64" HEIGHT="32"
BORDER="0" ALT="FunnelWeb"
HSPACE="0" VSPACE="1"></A><BR>
<BR>
<TABLE CELLSPACING=0 CELLPADDING=0 BORDER=0><TR><TD BGCOLOR="#000000">
<A HREF="../reference/index.html"
TARGET="funnelwebreference"
onClick="window.open('','funnelwebreference','location,status,menubar,scrollbars,resizable',false).focus(); return true;"
><FONT COLOR="#FFFFFF"><B>Reference</B></FONT></A><BR>
<BR>
<A HREF="../developer/index.html"
TARGET="funnelwebdeveloper"
onClick="window.open('','funnelwebdeveloper','location,status,menubar,scrollbars,resizable',false).focus(); return true;"
><FONT COLOR="#FFFFFF"><B>Developer</B></FONT></A><BR>
<BR>
<A HREF="index.html"><FONT COLOR="#FFFFFF"><B>Tutorial</B></FONT></A><BR>
<A HREF="intro.html"><FONT COLOR="#FFFFFF">1 Introduction</FONT></A><BR>
<A HREF="macro.html"><FONT COLOR="#FFFFFF">2 Macros</FONT></A><BR>
<A HREF="type.html"><FONT COLOR="#FFFFFF">3 Typesetting</FONT></A><BR>
<A HREF="example.html"><FONT COLOR="#FFFFFF">4 Example</FONT></A><BR>
<A HREF="hints.html"><FONT COLOR="#FFFFFF">5 Hints</FONT></A><BR>
<A HREF="examples.html"><FONT COLOR="#FFFFFF">6 Examples</FONT></A><BR>
<A HREF="web.html"><FONT COLOR="#FFFFFF">7 Webmaking</FONT></A><BR>
<BR>
<A HREF="search.html"><FONT COLOR="#FFFFFF"><B>SEARCH</B></FONT></A><BR>
</FONT>
</TD></TR></TABLE>
</TD>
<TD WIDTH="360" VALIGN="top">
<FONT SIZE="3">
<A HREF="../reference/index.html"><IMG SRC="binary/title.gif"
WIDTH="302" HEIGHT="24"
BORDER="0" ALT="FunnelWeb Tutorial Manual"
HSPACE="0" VSPACE="0"></A>
<P><FONT SIZE="5">6.7 Generics</FONT><BR>
<P>It is well known that generics in programming languages
are closely aligned with textual substitution. In fact, a
good way to understand the generic facility of a new
programming language is to ask oneself the question
"In what way does this generic facility differ from
simple text substitution?" The differences, if any,
typically have to do with the difference in scoping between
textual and intelligent substitution and whether the generic
code is shared or copied by the implementation. In most
cases the differences are quite minor.
<P>Because generic facilities are so closely aligned with
text substitution, it is possible to use FunnelWeb's
parameterized macros to provide generics in programming
languages that do not support generics. Simply write a
FunnelWeb macro whose parameters are the parameters of the
generic and whose body is the generic object.
<P>The following FunnelWeb file gives an example of a
fully worked Vax Pascal generic set package
implemented using FunnelWeb parameterized macros. The
package was written by Barry Dwyer of
the Computer Science Department of the University of
Adelaide in 1987 and was
emailed to me on 11 November 1987. The generic package
provides a set abstraction
implemented using linked lists. Note the clever use of the
instantiation parameters in type, function, and procedure
names.
<P>
<PRE>
@$@<Generic Set Module@>@(@2@)==@{@-
@! @1 is the base type, @2 is the set type.
[inherit ('@1'), environment ('@2')]
module @2;
type @2 = ^@2Record;
@2Record = record
Member: @1;
Next: @2;
end;
procedure Null@2 (var Result: @2);
begin new (Result);
Result^.Member := (- MaxInt)::@1;
Result^.Next := nil end;
function IsNull@2 (S: @2): boolean;
begin
IsNull@2 := S^.Member::integer = - MaxInt
end;
procedure ForEach@1 (S: @2; procedure DoIt (i: @1));
var ThisS, NextS: @2;
begin ThisS := S;
while ThisS^.Member::integer <> - MaxInt do
begin NextS := ThisS^.Next;
DoIt (ThisS^.Member);
ThisS := NextS end;
end;
function First@1 (S: @2): @1;
begin First@1 := S^.Member end;
function Is@1InSet (i: @1; S: @2): boolean;
procedure TestEquals (j: @1);
begin if Equal@1 (i, j) then Is@1InSet := true; end;
begin
Is@1InSet := false;
ForEach@1 (S, TestEquals);
end;
function Includes@2 (S1, S2: @2): boolean;
var Result: boolean;
procedure TestIfInS1 (i: @1);
begin
if Result then
if not Is@1InSet (i, S1) then
Result := false;
end;
begin Result := true;
ForEach@1 (S2, TestIfInS1);
Includes@2 := Result end;
function Disjoint@2s (S1, S2: @2): boolean;
var Result: boolean;
procedure TestIfInS1 (i: @1);
begin
if Result then
if Is@1InSet (i, S1) then
Result := false;
end;
begin Result := true;
ForEach@1 (S2, TestIfInS1);
Disjoint@2s := Result end;
function Equal@2 (S1, S2: @2): boolean;
begin
Equal@2 := Includes@2 (S1, S2) and
Includes@2 (S2, S1);
end;
procedure Insert@1 (i: @1; var S: @2);
var This, Pred, Succ: @2;
begin
if not Is@1InSet (i, S) then
begin
Pred := nil; Succ := S;
while Succ^.Member::integer > i::integer do
begin Pred := Succ; Succ := Succ^.Next end;
if Succ^.Member::integer < i::integer then
begin
new (This);
This^.Next := Succ;
This^.Member := i;
if Pred <> nil then
Pred^.Next := This
else
S := This;
end;
end;
end;
procedure Insert@1s (S1: @2; var S2: @2);
var This, Pred, Succ: @2;
procedure Add@1 (i: @1);
begin Insert@1 (i, S2) end;
begin
ForEach@1 (S1, Add@1);
end;
procedure Remove@1 (i: @1; var S: @2);
var Pred, This: @2;
begin
Pred := nil; This := S;
while not Equal@1 (This^.Member, i) do begin
Pred := This; This := This^.Next end;
if Pred <> nil then
Pred^.Next := This^.Next
else
S := This^.Next;
Dispose (This);
end;
procedure Dispose@2 (var S: @2);
var Old: @2;
begin
while S <> nil do
begin
Old := S;
S := S^.Next;
Dispose (Old)
end;
end;
end.
@}
@O@<NaryTreeSet.pas@>==@{@-
@<Generic Set Module@>@-
@(@"NaryTree@"@,@"NaryTreeSet@"@)@}
@O@<NaryTreeSetSet.pas@>==@{@-
@<Generic Set Module@>@-
@(@"NaryTreeSet@"@,@"NaryTreeSetSet@"@)@}
</PRE>
<P>A great advantage of the approach reflected in the
above example is that it allows the programmer to construct
a generic object in a language that does not supply
generics, <I>with complete
typesafety.</I> This contrasts to
the approach that might be used in a language such as C
where the programmer might choose to construct a
"generic" package by parameterizing a package with
pointers to <SAMP>void</SAMP>. The resulting package is
powerful but extremely untypesafe. Such a generic list
package is used in the code of FunnelWeb itself and caused
no end of problems, as the compiler had no way of telling if
pointers to the correctly typed object were being handed to
the correct list-object/function combination.
<P>The major disadvantage of the text generic approach is
that it causes the code of the generic object to be
duplicated once for each instantiation. Depending on the
number and size of the instantiations, this may or may not
be acceptable.
<P>Where the duplication of code is unacceptable, a hybrid
approach may be taken. As in the C example, the programmer
could write a single generic package using pointers to
<SAMP>void</SAMP> or some other untypesafe mechanism. Then the
programmer creates a FunnelWeb generic package whose
functions do nothing more than call the functions of the
untypesafe package, and whose types do nothing more than
contain the types of the untypesafe package. This solution
involves the use of untypesafe programming, but this is a
one-off and if done carefully and correctly, the result can
be a typesafe generic package involving minimal code
duplication.
<P>
<TABLE WIDTH="100%">
<TR>
<TD ALIGN="left" VALIGN="bottom"><A HREF="examples_sharing.html"><IMG SRC="binary/fw_left.gif" HEIGHT="32" WIDTH="32" BORDER="0" ALT="Prev"></A></TD>
<TD ALIGN="center" VALIGN="bottom"><A HREF="examples.html"><IMG SRC="binary/fw_up.gif" HEIGHT="32" WIDTH="32" BORDER="0" ALT="Up"></A></TD>
<TD ALIGN="right" VALIGN="bottom"><A HREF="examples.html"><IMG SRC="binary/fw_up.gif" HEIGHT="32" WIDTH="32" BORDER="0" ALT="Up"></A></TD>
</TR>
</TABLE>
<HR>
<FONT SIZE="2">
<A HREF="mailto:webmaster@ross.net">Webmaster</A>
<A HREF="copyright.html">Copyright © Ross N. Williams 1992,1999. All rights reserved.</A><BR>
</FONT>
</FONT>
</TD>
</TR>
</TABLE>
</BODY>
<!-- *********************************************************************** -->
<!-- End Of A FunnelWeb Manual Web Page (www.ross.net/funnelweb/) -->
<!-- *********************************************************************** -->
</HTML>
|
