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
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
|
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<title>An Overview of the Poly Programming Language</title>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
</head>
<body>
<p>This document was presented at the First Workshop on Persistent Objects, Appin,
Scotland in August 1985 and published as a Cambridge University Technical Report
(TR99) in November 1986.</p>
<h1 align="center">An Overview of the Poly Programming Language</h1>
<h1 align="center">David C.J. Matthews</h1>
Poly is a general purpose programming language based on the idea of treating
types as first-class values. It can support polymorphic operations by passing
types as parameters to procedures, and abstract types and parameterised types
by returning types as results.
Although Poly is not intended specifically as a database programming language
it was convenient to implement it in a persistent storage system.
This allows the user to retain data structures from one session to the
next and can support large programming systems such as
the Poly compiler and a Standard ML system.
<h2>1. Poly and its Type System</h2>
<p>Poly[Mat85] is based on the idea of types as first class values first used
in the language Russell.[Dem79] In the terms used by Cardelli and MacQueen[Car85]
it uses the <em>abstract witness</em> model of a type. Treating a type this
way means that polymorphism, parameterised types and modules are all handled
by the general concept of function application. </p>
<h3>1.1 Types as Values</h3>
<p>A type in Poly is a set of values, normally functions. For example the type
<em>integer</em> has operations +, - etc. Other types may have these operations,
the type <em>real</em> also has + and - but will not have a <em>mod</em> (remainder)
operation. The operations need not be functions, <em>integer</em> also has <em>zero</em>,
<em>first</em> and <em>last</em> which are <em>simple values</em>, and other types
may contain types. All values in Poly have a <em>signature</em>, called a <em>
specification</em> in earlier reports, which is only used at compile-time. It is
the analogue of a type in languages like Pascal and corresponds in many ways
to the idea of a type in Ponder\cite{Ponder}. There are three classes of value
in Poly, the <em>simple value</em> which corresponds to what are normally thought
of as values in, say Pascal, numbers, strings, vectors etc.; the <em>procedure</em>
or function which operates on values and the <em>type</em> which is a set of values.
Each kind of value has a signature. To show why this view of types is useful
we will consider some properties of other languages, and how they are handled
in Poly.</p>
<h3>1.2 Polymorphism</h3>
<p>A polymorphic function is one that can be applied to values of many different
types. The phrase is sometimes used where <em>overloading</em> would be more appropriate,
for example the + operator in Pascal. In Pascal, or languages like it, there
are operators which can be applied to values of more than one data type and
their meanings are different according to the type of their arguments. They
can be thought of as a set of overloaded operators in the same way as operators
in Ada can be overloaded. Truly polymorphic functions are somewhat different.
They are functions which are applicable to values of a wide variety of data
types, including types which may not exist at the time the function is written.
The fundamental difference is that a new polymorphic function can be written
in terms of other polymorphic functions, while a function written in terms of
overloaded functions must be defined for each data type even if the program
is the same for each. For example </p>
<p> <font face="Arial, Helvetica, sans-serif"><strong>function</strong></font>
<em>min</em>(<em>i</em>,<em>j</em>: <em>integer</em>):<em>integer<br>
</em><font face="Arial, Helvetica, sans-serif"><strong>begin</strong></font><br>
<font face="Arial, Helvetica, sans-serif"><strong>if</strong></font> <em>i</em>
< <em>j</em> <font face="Arial, Helvetica, sans-serif"><strong>then</strong></font>
<em>min</em> := <em>i</em> <font face="Arial, Helvetica, sans-serif"><strong>else</strong></font>
<em>min</em> := <em>j</em><font face="Arial, Helvetica, sans-serif"><strong><br>
end</strong></font>;<font face="Arial, Helvetica, sans-serif"><strong><br>
function</strong></font> <em>min</em>(<em>i</em>,<em>j</em>: <em>real</em>):<em>real</em><font face="Arial, Helvetica, sans-serif"><strong><br>
begin<br>
</strong></font><font face="Arial, Helvetica, sans-serif"><strong>if</strong></font>
<em>i</em> < <em>j</em> <font face="Arial, Helvetica, sans-serif"><strong>then</strong></font>
<em>min</em> := <em>i</em> <font face="Arial, Helvetica, sans-serif"><strong>else</strong></font>
<em>min</em> := <em>j</em><br>
<font face="Arial, Helvetica, sans-serif"><strong>end</strong></font>;</p>
<p>The ML [Mil84] programming language provides polymorphic operations on an all-or-nothing
basis. This allows one to write an identity function which simply returns its
argument, and this function is applicable to values of any type. One can also
write functions which operate on lists of any type or on functions of any type.
This generally works very well but has problems when one wants to write an operation
which operates differently on different data types. For example it is still
necessary to overload = since comparing two integers is different to comparing
two lists of real numbers. The <em>min</em> function cannot be written as a
single function in ML. What is required is a way of writing operations which
are <em> type-dependent</em>.</p>
<p>A type in Poly is characterised by the operations it has. Both <em>real</em>
and <em>integer</em> have < operations though they will be implemented in
different ways. Many other types may have < operations since Poly allows
the user to make new types. Poly allows a function to be written which selects
certain operations from a type and values of any type with those operations
can be used as a parameter. For example there is a <em>single</em> < function
which works on types which have a < operation and simply applies the operations
to the arguments. The effect is as though < were being overloaded. However,
we can write a function in terms of this, such as the <em>min</em> function.
This will also work on values of any type which has a < operation. For example,
<em>min</em> is a function which will work on values of any type with the <
operation. Such a type has signature</p>
<p><font face="Arial, Helvetica, sans-serif"><strong>type</strong></font> (<em>t</em>)
< : <font face="Arial, Helvetica, sans-serif"><strong>proc</strong></font>(<em>t</em>;<em>t</em>)<em>boolean</em>
<font face="Arial, Helvetica, sans-serif"><strong>end</strong></font></p>
<p>This type has an operation, <, which takes two values and returns a <em>boolean</em>.
We will first write a version of <em>min</em> which takes three parameters;
a type and two values of this type and returns a value of the type. It has signature:</p>
<p><font face="Arial, Helvetica, sans-serif"><strong>proc</strong></font>(<em>t</em>:
<font face="Arial, Helvetica, sans-serif"><strong>type</strong></font> (<em>t</em>)
< : <font face="Arial, Helvetica, sans-serif"><strong>proc</strong></font>(<em>t</em>;<em>t</em>)<em>boolean</em>
<font face="Arial, Helvetica, sans-serif"><strong>end</strong></font>; <em>t</em>;
<em>t</em>)<em>t</em> </p>
<p>We can write the whole function.</p>
<p><font face="Arial, Helvetica, sans-serif"><strong>let</strong></font> <em>min</em>
==<br> <font face="Arial, Helvetica, sans-serif"><strong>proc</strong></font>(<em>t</em>:
<font face="Arial, Helvetica, sans-serif"><strong>type</strong></font> (<em>t</em>)
< : <font face="Arial, Helvetica, sans-serif"><strong>proc</strong></font>(<em>t</em>;
<em>t</em>)boolean <font face="Arial, Helvetica, sans-serif"><strong>end</strong></font>;
<em>x</em>, <em>y</em>: <em>t</em>)<em>t<br>
</em><font face="Arial, Helvetica, sans-serif"><strong>begin</strong></font><font face="Arial, Helvetica, sans-serif"><strong><br>
if</strong></font> <em>x</em> < <em>y</em> <font face="Arial, Helvetica, sans-serif"><strong>then</strong></font>
<em>x</em> <font face="Arial, Helvetica, sans-serif"><strong>else</strong></font>
<em>y</em><br>
<font face="Arial, Helvetica, sans-serif"><strong>end</strong></font>;</p>
<p>It can be applied to integer values </p>
<p><em>min</em>(<em>integer</em>, 1, 2)</p>
<p>or string values </p>
<p><em>min</em>(<em>string</em>, "abc", "abd"</p>
<p> or values of any type with a < operation. The first parameter is a type
which must have a < operation which compares two values of the type, and
the second and third parameters must be values of the type. When we call </p>
<p><em>min</em>(<em>integer</em>, 1, 2)</p>
<p>the actual parameters are matched to the formal parameters from left to right.
First the types are matched by checking that the type given has the appropriate
operation, and then the values are matched. They are not of course the same
type as <em>t</em>, since they have type <em>integer</em>, but we invoke a matching
rule which says that if we have matched an actual type parameter to a formal
type then we can match values of corresponding types. In addition the type of
the result becomes matched so that the result has type <em>integer</em>. This
can be thought of as a systematic renaming of <em>t</em> with <em>integer</em>.
</p>
<h3>1.3 Implied Parameters</h3>
<p>Having to pass the types explicitly is often a nuisance so there is a sugared
form which gives a way of omitting the types and having the compiler insert
them automatically using the types of the parameters. The only difference to
the definition of the function is that the types are written in square brackets
before the other parameters. The definition of <em>min</em> would then be: </p>
<p><font face="Arial, Helvetica, sans-serif"><strong>let</strong></font> <em>min</em>
==<font face="Arial, Helvetica, sans-serif"><strong><br>
proc</strong></font>$[$<em>t</em>: <font face="Arial, Helvetica, sans-serif"><strong>type</strong></font>
(<em>t</em>) < : <font face="Arial, Helvetica, sans-serif"><strong>proc</strong></font>(<em>t</em>;
<em>t</em>)boolean <font face="Arial, Helvetica, sans-serif"><strong>end</strong></font>$]$
(<em>x</em>, <em>y</em>: <em>t</em>)<em>t</em><br>
<font face="Arial, Helvetica, sans-serif"><strong>begin</strong></font><br>
<font face="Arial, Helvetica, sans-serif"><strong>if</strong></font> <em>x</em>
< <em>y</em> <font face="Arial, Helvetica, sans-serif"><strong>then</strong></font>
<em>x</em> <font face="Arial, Helvetica, sans-serif"><strong>else</strong></font>
<em>y</em><font face="Arial, Helvetica, sans-serif"><strong><br>
end</strong></font>;</p>
<p>It can be used by just giving the values. </p>
<p><em>min</em>(1, 2);<br> <em><br>
min</em>("abc", "abd"); </p>
<p>This sugaring also allows us to define operators such as + and < which simply
apply the operation with the same name from the types of their arguments giving
the effect of overloading. </p>
<p><font face="Arial, Helvetica, sans-serif"><strong>let</strong></font> + ==<br>
<font face="Arial, Helvetica, sans-serif"><strong>proc</strong></font> <font face="Arial, Helvetica, sans-serif"><strong>infix</strong></font>
6 $[$<em>t</em>: <font face="Arial, Helvetica, sans-serif"><strong>type</strong></font>
(<em>t</em>) + : <font face="Arial, Helvetica, sans-serif"><strong>proc</strong></font>(<em>t</em>;
<em>t</em>)<em>t</em> <font face="Arial, Helvetica, sans-serif"><strong>end</strong></font>$]$
(<em>x</em>, <em>y</em>: <em>t</em>)<em>t</em><br>
<font face="Arial, Helvetica, sans-serif"><strong>begin</strong></font><br>
<em>t</em>$+ (<em>x</em>, <em>y</em>)<br>
<font face="Arial, Helvetica, sans-serif"><strong>end</strong></font>;</p>
<h2>2. Parameterised Types</h2>
<p>So far we have seen how having types as parameters to a procedure allows us
to write polymorphic operations. Types can also be returned from procedures
and this provides a way of defining types which are parameterised by either
types or values. As an example, suppose we wanted to construct an associative
memory in which to store values of arbitrary type together with a number which
would identify each. This could be defined as follows</p>
<p><font face="Arial, Helvetica, sans-serif"><strong>let</strong></font> <em>associative</em>
==<br>
<font face="Arial, Helvetica, sans-serif"><strong>proc</strong></font>(<em>element</em>:
<font face="Arial, Helvetica, sans-serif"><strong>type</strong></font> <font face="Arial, Helvetica, sans-serif"><strong>end</strong></font>)<br>
<font face="Arial, Helvetica, sans-serif"><strong>type</strong></font> (<em>assoc</em>)<br>
<em>enter</em>: <font face="Arial, Helvetica, sans-serif"><strong>proc</strong></font>(<em>assoc</em>;
<em>integer</em>; <em>element</em>)<em>assoc</em>;<br>
<em>lookup</em>: <font face="Arial, Helvetica, sans-serif"><strong>proc</strong></font>(<em>assoc</em>;
<em>integer</em>)<em>element</em>;<br>
<em>empty</em>: <em>assoc</em><br>
<font face="Arial, Helvetica, sans-serif"><strong>end</strong></font><br>
<font face="Arial, Helvetica, sans-serif"><strong>begin</strong></font><br>
<font face="Arial, Helvetica, sans-serif"><strong>type</strong></font> (<em>assoc</em>)<br>
<font face="Arial, Helvetica, sans-serif"><strong>extends</strong></font> <font face="Arial, Helvetica, sans-serif"><strong>struct</strong></font>(<em>next</em>:
<em>assoc</em>; <em>index</em>: <em>integer</em>; <em>value</em>: <em>element</em>);<br>
<font face="Arial, Helvetica, sans-serif"><strong>let</strong></font> <em>empty</em>
== <em>assoc</em>$<em>nil</em>;<br>
<font face="Arial, Helvetica, sans-serif"><strong>let</strong></font> <em>enter</em>
==<br>
<font face="Arial, Helvetica, sans-serif"><strong>proc</strong></font>(<em>table</em>:
<em>assoc</em>; <em>num</em>: <em>integer</em>; <em>val</em>: <em>element</em>)<em>assoc</em><br>
<font face="Arial, Helvetica, sans-serif"><strong>begin</strong></font><br>
<em>assoc</em>$<em>constr</em>(<em>table</em>, <em>num</em>, <em>val</em>)<br>
<font face="Arial, Helvetica, sans-serif"><strong>end</strong></font>;<br>
<font face="Arial, Helvetica, sans-serif"><strong>letrec</strong></font> <em>lookup</em>
==<br>
<font face="Arial, Helvetica, sans-serif"><strong>proc</strong></font>(<em>table</em>:
<em>assoc</em>; <em>num</em>: <em>integer</em>)<em>element</em><br>
<font face="Arial, Helvetica, sans-serif"><strong>begin</strong></font><br>
<font face="Arial, Helvetica, sans-serif"><strong>if</strong></font> <em>table</em>
= <em>assoc</em>$<em>nil</em><br>
<font face="Arial, Helvetica, sans-serif"><strong>then</strong></font> <font face="Arial, Helvetica, sans-serif"><strong>raise</strong></font>
<em>not_found</em><br>
<font face="Arial, Helvetica, sans-serif"><strong>else</strong></font> <font face="Arial, Helvetica, sans-serif"><strong>if</strong></font>
<em>table</em>.<em>index</em> = <em>num</em><br>
<font face="Arial, Helvetica, sans-serif"><strong>then</strong></font> <em>table</em>.<em>value</em><br>
<font face="Arial, Helvetica, sans-serif"><strong>else</strong></font> <em>lookup</em>(<em>table</em>.<em>next</em>,
<em>num</em>)<br>
<font face="Arial, Helvetica, sans-serif"><strong>end</strong></font><br>
<font face="Arial, Helvetica, sans-serif"><strong>en</strong></font>}<br>
<font face="Arial, Helvetica, sans-serif"><strong>end</strong></font>;</p>
<p>This is a very simple minded definition but it illustrates the point. We start
by giving the header of the procedure which includes the signature of the argument,
in this case that <em>element</em> is a type but that any type will do, and
the signature of the result. The result is a type with three objects, a value
which denotes the empty table and procedures to enter and look up items from
the table. It is implemented in terms of a <font face="Arial, Helvetica, sans-serif"><strong>struct</strong></font>
(a record with a <em>nil</em> value and equality) which makes up a list of index/value
pairs. <em>enter</em> just returns a new list with the new pair "cons-ed"
onto the front (We could have written simply <font face="Arial, Helvetica, sans-serif"><strong>let</strong></font>
<em>enter</em> == <em>assoc</em>$<em>constr</em>; since the arguments are in
the same order). A better implementation would check to see if there was already
an entry with that index and return a list with the old entry replaced by the
new one. <em>lookup</em> searches the list for an entry with the required index
and either returns the value or raises an exception. </p>
<p>There is no particular reason why we should use integers as the indexing value,
it would be perfectly possible to use any type which had an equality operation.
The procedure header would then be </p>
<p><font face="Arial, Helvetica, sans-serif"><strong>proc</strong></font>(<em>element</em>:
<font face="Arial, Helvetica, sans-serif"><strong>type</strong></font> <font face="Arial, Helvetica, sans-serif"><strong>end</strong></font>;<br>
<em>index_type</em>: <font face="Arial, Helvetica, sans-serif"><strong>type</strong></font>
(<em>i</em>) = : <font face="Arial, Helvetica, sans-serif"><strong>proc</strong></font>(<em>i</em>;<em>i</em>)<em>boolean</em>
<font face="Arial, Helvetica, sans-serif"><strong>end</strong></font>)...</p>
<p> with <em>integer</em> replaced everywhere in the body by <em>index_type</em>.
A more efficient implementation for index types with an ordering would be to
use binary trees rather than lists. We would then have to add a > or < to
<em>index_type</em>, or at least replace the = by one of these. Now, since types
are values we could incorporate an if-statement into the procedure and use one
or other of the implementations depending on the value of a further parameter.
We might want to do this because one implementation may be more efficient for,
say, small tables and the other for larger ones. For the example we will assume
a parameter <em>use_binary_tree</em>. The procedure will now look something
like this.</p>
<p><font face="Arial, Helvetica, sans-serif"><strong>proc</strong></font>(<em>element</em>:
<font face="Arial, Helvetica, sans-serif"><strong>type</strong></font> <font face="Arial, Helvetica, sans-serif"><strong>end</strong></font>;<br>
<em>index_type</em>: <font face="Arial, Helvetica, sans-serif"><strong>type</strong></font>
(<em>i</em>) = , < : <font face="Arial, Helvetica, sans-serif"><strong>proc</strong></font>(<em>i</em>;<em>i</em>)<em>boolean</em>
<font face="Arial, Helvetica, sans-serif"><strong>end</strong></font>;<br>
<em>use_binary_tree</em>: <em>boolean</em>)...<br>
<font face="Arial, Helvetica, sans-serif"><strong>begin</strong></font><br>
<font face="Arial, Helvetica, sans-serif"><strong>if</strong></font> <em>use_binary_tree</em><br>
<font face="Arial, Helvetica, sans-serif"><strong>then</strong></font><br>
<font face="Arial, Helvetica, sans-serif"><strong>type</strong></font> ....
{Binary tree implementation}<br>
<font face="Arial, Helvetica, sans-serif"><strong>end</strong></font><br>
<font face="Arial, Helvetica, sans-serif"><strong>else</strong></font><br>
<font face="Arial, Helvetica, sans-serif"><strong>type</strong></font> ....
{List implementation}<br>
<font face="Arial, Helvetica, sans-serif"><strong>end</strong></font><br>
<font face="Arial, Helvetica, sans-serif"><strong>end</strong></font></p>
<p>This could now be called as</p>
<p><font face="Arial, Helvetica, sans-serif"><strong>let</strong></font> <em>a_table</em>
== <em>associative</em>(<em>string</em>, <em>integer</em>, <em>true</em>);<br>
<font face="Arial, Helvetica, sans-serif"><strong>let</strong></font> <em>another_table</em>
== <em>associative</em>(<em>string</em>, <em>integer</em>, <em>size</em> > 30);
</p>
<p>In the second case the expression may not be able to be evaluated when the
call to the procedure is compiled, <em>but this does not matter</em>. We do
not know at compile-time which of the two implementations of the type will be
used, but we know that either of them have all the operations required so they
will do equally well. There is however a problem with this idea of types which
this example shows quite nicely. Since the expression may not be evaluated at
compile-time how do we know when two values have the same type? The type system
must ensure that we apply the <em>lookup</em> procedure which understands the
representation of the particular associative memory. It would be catastrophic
to try to look up a value assuming that the value represented a tree when it
was in fact a list. We need the type system to assure us at compile-time that
the expressions </p>
<p><font face="Arial, Helvetica, sans-serif"><strong>let</strong></font> <em>y</em>
== X$<em>enter</em>(X$<em>empty</em>, 1, "hello");<br>
X$<em>lookup</em>(<em>y</em>); </p>
<p>where X stands for a type or type-returning expression, will not give faults
at run-time because of a mistake in interpreting the representations. There
are several possible approaches to the problem of which Poly and Russell illustrate
two. In Russell values can have types such as </p>
<p><em>associative</em>(<em>string</em>, <em>integer</em>, <em>size</em> > 30)</p>
<p>provided nothing in the expression involves a global variable (Variable in
this context means something whose value can be changed by assignment.) This
essentially means that all functions have to be "variable-free", not
just those which directly return types. Given this restriction it is possible
to say that if two expressions are syntatically the same in a given context
then they return the same value. If however, <em>size</em> were a variable,
or <em>associative</em> looked at the value of a global variable, then we could
not say with certainty that two values with type</p>
<p><em>associative</em>(<em>string</em>, <em>integer</em>, <em>size</em> > 30)</p>
<p>had the same type. Taking a purely synatactic view means that expressions like</p>
<p><em>associative</em>(<em>string</em>, <em>integer</em>, 2 > 1)</p>
<p>and </p>
<p><em>associative</em>(<em>string</em>, <em>integer</em>, <em>true</em>)</p>
<p>are not the same type. In Poly types are only regarded as the same if they
are the same <em>named</em> type. So while values with types which are expressions
can sometimes be produced there is very little that can be done with them. To
be useful a type-returning expression has to be bound to an identifier.</p>
<p><font face="Arial, Helvetica, sans-serif"><strong>let</strong></font> <em>a_table</em>
== <em>associative</em>(<em>string</em>, <em>integer</em>, <em>true</em>);<br>
<font face="Arial, Helvetica, sans-serif"><strong>let</strong></font> <em>a_val</em>
== <em>a_table</em>$<em>enter</em>(<em>a_table</em>$<em>empty</em>, 1, "hello");<br>
<font face="Arial, Helvetica, sans-serif"><strong>let</strong></font> <em>another_table</em>
== <em>associative</em>(<em>string</em>, <em>integer</em>, <em>true</em>);<br>
<font face="Arial, Helvetica, sans-serif"><strong>let</strong></font> <em>another_val</em>
== <em>another_table</em>$<em>enter</em>(<em>another_table</em>$<em>empty</em>,
1, "hello"); </p>
<p><em>a_val</em> and <em>another_val</em> have distinct types <em>a_table</em>
and <em>another_table</em>. </p>
<p>A side-effect of this is that "types" such as</p>
<p><em>list</em>(<em>integer</em>)</p>
<p>cannot be used directly. We have to write</p>
<p><font face="Arial, Helvetica, sans-serif"><strong>let</strong></font> <em>int_list</em>
== <em>list</em>(<em>integer</em>); </p>
<p>and then use <em>int_list</em> as the type. However this is not such a problem
as might at first appear. Since we can write functions which take implied parameters
we can write an <em>append</em> function which will work on values of any type
with the appropriate <em>hd</em>, <em>tl</em> etc., irrespective of their actual
implementations. </p>
<h2>3. Modules</h2>
<p>A module is conventionally thought of as a collection of types and functions
which can be separately compiled. It has an interface which is the types of
these functions so that other modules can make use of it without having to know
the precise implementation.</p>
<p>Types in Poly can be thought of in the same way. A type is a collection of
operations and its signature gives their "types" (We usually think of a type
as being something like <em>integer</em> which has values, but a type in Poly
can be any collection of objects. So a collection of floating point functions
<em>sin</em>, <em>cos</em> etc. could be combined as a type even though there
is no such thing as a value of this type.). A module which makes use of other
modules, <em>imports</em> them in conventional terms, can be represented as
a procedure which is applied to types and returns a type. One of the big advantages
of this view of modules is that binding modules together is done using statements
written in Poly and type-checked using the normal Poly type-checker. There is
no need, as with MESA and C-MESA[Mit79] for a separate module binding language.
</p>
<p>The module system for ML[Har85] is essentially a system built on top of the
kernel language. <em>Structures</em> and <em>functors</em> correspond to values
and functions in the kernel but the ML type system makes it impossible to unify
these concepts. </p>
<h2>4. Persistence in Poly</h2>
<p>Poly is an interactive system in which the user types expressions and declarations
and these are compiled and executed immediately. When objects are declared they
are added to the objects the system knows about and they can be used in subsequent
expressions. Such systems are quite common and usually work on a core image
which can be saved from one session to the next. This is fine provided that
the core image does not grow too big. However as the core image gets larger
the costs of reading it in and writing it out get more serious. Also the cost
of garbage-collection rises. There is a further question about the security
of the data if the machine crashes while writing out a large image. </p>
<p>For these reasons Poly is implemented in a persistent store [Atk81a][Atk81b]
which can be thought of as a core image where objects are only read in when
they are actually required. The cost of loading objects from the image, or database,
depends on the amount of the store which is used by a program rather than the
total size of the image. A simple transaction mechanism ensures that the database
remains in a consistent state in the event of a machine crash or if the program
is killed halfway through writing out. Some experiments have been done on using
multiple databases so that large programs such as the compiler can be shared
between several users. </p>
<p>Using this persistent store the Poly compiler has been boot-strapped so that
it is just another procedure. A Standard ML compiler has also been written which
uses the same back-end as the Poly compiler.</p>
<p> In a typical interactive programming system there is a single name space for
all identifiers, but as the number of declarations have grown it has become
necessary to divide up the name space into separate <em>environments</em>. An
environment is very similar to a directory in a filing system or to a block
in a programming language. When an environment is selected all new identifiers
are entered into it and looked up in it. There is the equivalent of the scope
rules in a programming language so that an identifier is looked up in a series
of nested environments until it is found. It could be thought of as a Poly type
since it is a collection of objects, but it cannot be quite the same because
declarations can be added or removed dynamically to an environment while a Poly
type must be "frozen". </p>
<h2>5. Conclusions</h2>
<p>Poly was designed as a general purpose language and has been used successfully
for some medium scale projects (there is about 20000 lines of code in the Poly
and ML compilers). After some years of programming in it the type system has
proved to work very well. Treating types as first-class values seems to result
in a generally simpler language than languages where types are treated as purely
compile-time objects. Experience with Standard ML suggests that pattern-matching
and exceptions with parameters (exceptions in Poly cannot carry parameters)
are something that should be added. Some kind of type inference based on unification
could be used to reduce the amount of type information which must be given explicitly,
though it cannot remove it completely. The presence of a persistent store tends
to break down the distinction between compile-time and run-time, since the compiler
is just another function to be applied. Compile-time does have some meaning
in this system however. Compiling an expression means checking the interfaces
between functions and their arguments so that the result can be guaranteed not
to produce a type-checking error later on. If we compile a procedure then we
want to produce a type for the procedure as a whole and remove the type information
within it. Not only does this improve the efficiency of the procedure but it
also gives us a degree of certainty that the procedure will not fail. It is
a little way along the road to proving the correctness of the procedure. There
is a cost in this static type checking in Poly in that some procedures which
are in fact type-correct will fail to pass a static type-checker, but the advantages
of static type-checking more than outweigh the disadvantages.</p>
<h2> References</h2>
<table width="100%" border="0">
<tr>
<td valign="top">[Atk81a]</td>
<td>Atkinson M.P., Chisholm K.J. and Cockshott W.P. "PS-Algol: An Algol with
a Persistent Heap." Technical Report CSR-94-81, Computer Science Dept.,
University of Edinburgh.</td>
</tr>
<tr>
<td valign="top">[Atk81b]</td>
<td>Atkinson, M.P., Bailey P., Cockshott W.P., Chisholm K.J. and Morrison
R. "Progress with Persistent Programming." Technical Report PPR-8-81,
Computer Science Dept., University of Edinburgh. </td>
</tr>
<tr>
<td valign="top">[Car85]</td>
<td>Cardelli L. and MacQueen D. "Persistence and Type Abstraction." Proc.
of the Persistence and Data Types Workshop, August 1985.</td>
</tr>
<tr>
<td valign="top">[Dem79]</td>
<td>Demers A. and Donahue J. "Revised Report on Russell." TR 79-389 Dept.
of Computer Science, Cornell University.</td>
</tr>
<tr>
<td valign="top">[Fai85]</td>
<td>Fairbairn J. "A New Type-Checker for a Functional Language." Proc. of
the Persistence and Data Types Workshop, August 1985.</td>
</tr>
<tr>
<td valign="top">[Har85]</td>
<td>Harper R. "Modules and Persistence in Standard ML." Proc. of the Persistence
and Data Types Workshop, August 1985. </td>
</tr>
<tr>
<td valign="top">[Mat85]</td>
<td>Matthews D.C.J. "Poly Manual" SIGPLAN Notices. Vol.20 No.9 Sept. 1985.
</td>
</tr>
<tr>
<td valign="top">[Mil84]</td>
<td>Milner R. "A Proposal for Standard ML" in "Proceedings of the 1984
ACM Symposium on Lisp and Functional Programming", Austin, Texas 1984.
</td>
</tr>
<tr>
<td valign="top">[Mit79]</td>
<td>Mitchell James G. et al. "MESA Language Manual." XEROX PARC,
1979 </td>
</tr>
</table></body>
</html>
|
