1<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> 2<html> 3<head> 4<title>An Overview of the Poly Programming Language</title> 5<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1"> 6</head> 7 8<body> 9<p>This document was presented at the First Workshop on Persistent Objects, Appin, 10 Scotland in August 1985 and published as a Cambridge University Technical Report 11 (TR99) in November 1986.</p> 12<h1 align="center">An Overview of the Poly Programming Language</h1> 13<h1 align="center">David C.J. Matthews</h1> 14 15Poly is a general purpose programming language based on the idea of treating 16types as first-class values. It can support polymorphic operations by passing 17types as parameters to procedures, and abstract types and parameterised types 18by returning types as results. 19 20Although Poly is not intended specifically as a database programming language 21it was convenient to implement it in a persistent storage system. 22This allows the user to retain data structures from one session to the 23next and can support large programming systems such as 24the Poly compiler and a Standard ML system. 25 26<h2>1. Poly and its Type System</h2> 27<p>Poly[Mat85] is based on the idea of types as first class values first used 28 in the language Russell.[Dem79] In the terms used by Cardelli and MacQueen[Car85] 29 it uses the <em>abstract witness</em> model of a type. Treating a type this 30 way means that polymorphism, parameterised types and modules are all handled 31 by the general concept of function application. </p> 32<h3>1.1 Types as Values</h3> 33<p>A type in Poly is a set of values, normally functions. For example the type 34 <em>integer</em> has operations +, - etc. Other types may have these operations, 35 the type <em>real</em> also has + and - but will not have a <em>mod</em> (remainder) 36 operation. The operations need not be functions, <em>integer</em> also has <em>zero</em>, 37 <em>first</em> and <em>last</em> which are <em>simple values</em>, and other types 38 may contain types. All values in Poly have a <em>signature</em>, called a <em> 39 specification</em> in earlier reports, which is only used at compile-time. It is 40 the analogue of a type in languages like Pascal and corresponds in many ways 41 to the idea of a type in Ponder\cite{Ponder}. There are three classes of value 42 in Poly, the <em>simple value</em> which corresponds to what are normally thought 43 of as values in, say Pascal, numbers, strings, vectors etc.; the <em>procedure</em> 44 or function which operates on values and the <em>type</em> which is a set of values. 45 Each kind of value has a signature. To show why this view of types is useful 46 we will consider some properties of other languages, and how they are handled 47 in Poly.</p> 48<h3>1.2 Polymorphism</h3> 49<p>A polymorphic function is one that can be applied to values of many different 50 types. The phrase is sometimes used where <em>overloading</em> would be more appropriate, 51 for example the + operator in Pascal. In Pascal, or languages like it, there 52 are operators which can be applied to values of more than one data type and 53 their meanings are different according to the type of their arguments. They 54 can be thought of as a set of overloaded operators in the same way as operators 55 in Ada can be overloaded. Truly polymorphic functions are somewhat different. 56 They are functions which are applicable to values of a wide variety of data 57 types, including types which may not exist at the time the function is written. 58 The fundamental difference is that a new polymorphic function can be written 59 in terms of other polymorphic functions, while a function written in terms of 60 overloaded functions must be defined for each data type even if the program 61 is the same for each. For example </p> 62<p> <font face="Arial, Helvetica, sans-serif"><strong>function</strong></font> 63 <em>min</em>(<em>i</em>,<em>j</em>: <em>integer</em>):<em>integer<br> 64 </em><font face="Arial, Helvetica, sans-serif"><strong>begin</strong></font><br> 65 <font face="Arial, Helvetica, sans-serif"><strong>if</strong></font> <em>i</em> 66 < <em>j</em> <font face="Arial, Helvetica, sans-serif"><strong>then</strong></font> 67 <em>min</em> := <em>i</em> <font face="Arial, Helvetica, sans-serif"><strong>else</strong></font> 68 <em>min</em> := <em>j</em><font face="Arial, Helvetica, sans-serif"><strong><br> 69 end</strong></font>;<font face="Arial, Helvetica, sans-serif"><strong><br> 70 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> 71 begin<br> 72 </strong></font><font face="Arial, Helvetica, sans-serif"><strong>if</strong></font> 73 <em>i</em> < <em>j</em> <font face="Arial, Helvetica, sans-serif"><strong>then</strong></font> 74 <em>min</em> := <em>i</em> <font face="Arial, Helvetica, sans-serif"><strong>else</strong></font> 75 <em>min</em> := <em>j</em><br> 76 <font face="Arial, Helvetica, sans-serif"><strong>end</strong></font>;</p> 77<p>The ML [Mil84] programming language provides polymorphic operations on an all-or-nothing 78 basis. This allows one to write an identity function which simply returns its 79 argument, and this function is applicable to values of any type. One can also 80 write functions which operate on lists of any type or on functions of any type. 81 This generally works very well but has problems when one wants to write an operation 82 which operates differently on different data types. For example it is still 83 necessary to overload = since comparing two integers is different to comparing 84 two lists of real numbers. The <em>min</em> function cannot be written as a 85 single function in ML. What is required is a way of writing operations which 86 are <em> type-dependent</em>.</p> 87<p>A type in Poly is characterised by the operations it has. Both <em>real</em> 88 and <em>integer</em> have < operations though they will be implemented in 89 different ways. Many other types may have < operations since Poly allows 90 the user to make new types. Poly allows a function to be written which selects 91 certain operations from a type and values of any type with those operations 92 can be used as a parameter. For example there is a <em>single</em> < function 93 which works on types which have a < operation and simply applies the operations 94 to the arguments. The effect is as though < were being overloaded. However, 95 we can write a function in terms of this, such as the <em>min</em> function. 96 This will also work on values of any type which has a < operation. For example, 97 <em>min</em> is a function which will work on values of any type with the < 98 operation. Such a type has signature</p> 99<p><font face="Arial, Helvetica, sans-serif"><strong>type</strong></font> (<em>t</em>) 100 < : <font face="Arial, Helvetica, sans-serif"><strong>proc</strong></font>(<em>t</em>;<em>t</em>)<em>boolean</em> 101 <font face="Arial, Helvetica, sans-serif"><strong>end</strong></font></p> 102<p>This type has an operation, <, which takes two values and returns a <em>boolean</em>. 103 We will first write a version of <em>min</em> which takes three parameters; 104 a type and two values of this type and returns a value of the type. It has signature:</p> 105<p><font face="Arial, Helvetica, sans-serif"><strong>proc</strong></font>(<em>t</em>: 106 <font face="Arial, Helvetica, sans-serif"><strong>type</strong></font> (<em>t</em>) 107 < : <font face="Arial, Helvetica, sans-serif"><strong>proc</strong></font>(<em>t</em>;<em>t</em>)<em>boolean</em> 108 <font face="Arial, Helvetica, sans-serif"><strong>end</strong></font>; <em>t</em>; 109 <em>t</em>)<em>t</em> </p> 110<p>We can write the whole function.</p> 111<p><font face="Arial, Helvetica, sans-serif"><strong>let</strong></font> <em>min</em> 112 ==<br> <font face="Arial, Helvetica, sans-serif"><strong>proc</strong></font>(<em>t</em>: 113 <font face="Arial, Helvetica, sans-serif"><strong>type</strong></font> (<em>t</em>) 114 < : <font face="Arial, Helvetica, sans-serif"><strong>proc</strong></font>(<em>t</em>; 115 <em>t</em>)boolean <font face="Arial, Helvetica, sans-serif"><strong>end</strong></font>; 116 <em>x</em>, <em>y</em>: <em>t</em>)<em>t<br> 117 </em><font face="Arial, Helvetica, sans-serif"><strong>begin</strong></font><font face="Arial, Helvetica, sans-serif"><strong><br> 118 if</strong></font> <em>x</em> < <em>y</em> <font face="Arial, Helvetica, sans-serif"><strong>then</strong></font> 119 <em>x</em> <font face="Arial, Helvetica, sans-serif"><strong>else</strong></font> 120 <em>y</em><br> 121 <font face="Arial, Helvetica, sans-serif"><strong>end</strong></font>;</p> 122<p>It can be applied to integer values </p> 123<p><em>min</em>(<em>integer</em>, 1, 2)</p> 124<p>or string values </p> 125<p><em>min</em>(<em>string</em>, "abc", "abd"</p> 126<p> or values of any type with a < operation. The first parameter is a type 127 which must have a < operation which compares two values of the type, and 128 the second and third parameters must be values of the type. When we call </p> 129<p><em>min</em>(<em>integer</em>, 1, 2)</p> 130<p>the actual parameters are matched to the formal parameters from left to right. 131 First the types are matched by checking that the type given has the appropriate 132 operation, and then the values are matched. They are not of course the same 133 type as <em>t</em>, since they have type <em>integer</em>, but we invoke a matching 134 rule which says that if we have matched an actual type parameter to a formal 135 type then we can match values of corresponding types. In addition the type of 136 the result becomes matched so that the result has type <em>integer</em>. This 137 can be thought of as a systematic renaming of <em>t</em> with <em>integer</em>. 138</p> 139<h3>1.3 Implied Parameters</h3> 140<p>Having to pass the types explicitly is often a nuisance so there is a sugared 141 form which gives a way of omitting the types and having the compiler insert 142 them automatically using the types of the parameters. The only difference to 143 the definition of the function is that the types are written in square brackets 144 before the other parameters. The definition of <em>min</em> would then be: </p> 145<p><font face="Arial, Helvetica, sans-serif"><strong>let</strong></font> <em>min</em> 146 ==<font face="Arial, Helvetica, sans-serif"><strong><br> 147 proc</strong></font>$[$<em>t</em>: <font face="Arial, Helvetica, sans-serif"><strong>type</strong></font> 148 (<em>t</em>) < : <font face="Arial, Helvetica, sans-serif"><strong>proc</strong></font>(<em>t</em>; 149 <em>t</em>)boolean <font face="Arial, Helvetica, sans-serif"><strong>end</strong></font>$]$ 150 (<em>x</em>, <em>y</em>: <em>t</em>)<em>t</em><br> 151 <font face="Arial, Helvetica, sans-serif"><strong>begin</strong></font><br> 152 <font face="Arial, Helvetica, sans-serif"><strong>if</strong></font> <em>x</em> 153 < <em>y</em> <font face="Arial, Helvetica, sans-serif"><strong>then</strong></font> 154 <em>x</em> <font face="Arial, Helvetica, sans-serif"><strong>else</strong></font> 155 <em>y</em><font face="Arial, Helvetica, sans-serif"><strong><br> 156 end</strong></font>;</p> 157<p>It can be used by just giving the values. </p> 158<p><em>min</em>(1, 2);<br> <em><br> 159 min</em>("abc", "abd"); </p> 160<p>This sugaring also allows us to define operators such as + and < which simply 161 apply the operation with the same name from the types of their arguments giving 162 the effect of overloading. </p> 163<p><font face="Arial, Helvetica, sans-serif"><strong>let</strong></font> + ==<br> 164 <font face="Arial, Helvetica, sans-serif"><strong>proc</strong></font> <font face="Arial, Helvetica, sans-serif"><strong>infix</strong></font> 165 6 $[$<em>t</em>: <font face="Arial, Helvetica, sans-serif"><strong>type</strong></font> 166 (<em>t</em>) + : <font face="Arial, Helvetica, sans-serif"><strong>proc</strong></font>(<em>t</em>; 167 <em>t</em>)<em>t</em> <font face="Arial, Helvetica, sans-serif"><strong>end</strong></font>$]$ 168 (<em>x</em>, <em>y</em>: <em>t</em>)<em>t</em><br> 169 <font face="Arial, Helvetica, sans-serif"><strong>begin</strong></font><br> 170 <em>t</em>$+ (<em>x</em>, <em>y</em>)<br> 171 <font face="Arial, Helvetica, sans-serif"><strong>end</strong></font>;</p> 172<h2>2. Parameterised Types</h2> 173<p>So far we have seen how having types as parameters to a procedure allows us 174 to write polymorphic operations. Types can also be returned from procedures 175 and this provides a way of defining types which are parameterised by either 176 types or values. As an example, suppose we wanted to construct an associative 177 memory in which to store values of arbitrary type together with a number which 178 would identify each. This could be defined as follows</p> 179<p><font face="Arial, Helvetica, sans-serif"><strong>let</strong></font> <em>associative</em> 180 ==<br> 181 <font face="Arial, Helvetica, sans-serif"><strong>proc</strong></font>(<em>element</em>: 182 <font face="Arial, Helvetica, sans-serif"><strong>type</strong></font> <font face="Arial, Helvetica, sans-serif"><strong>end</strong></font>)<br> 183 <font face="Arial, Helvetica, sans-serif"><strong>type</strong></font> (<em>assoc</em>)<br> 184 <em>enter</em>: <font face="Arial, Helvetica, sans-serif"><strong>proc</strong></font>(<em>assoc</em>; 185 <em>integer</em>; <em>element</em>)<em>assoc</em>;<br> 186 <em>lookup</em>: <font face="Arial, Helvetica, sans-serif"><strong>proc</strong></font>(<em>assoc</em>; 187 <em>integer</em>)<em>element</em>;<br> 188 <em>empty</em>: <em>assoc</em><br> 189 <font face="Arial, Helvetica, sans-serif"><strong>end</strong></font><br> 190 <font face="Arial, Helvetica, sans-serif"><strong>begin</strong></font><br> 191 <font face="Arial, Helvetica, sans-serif"><strong>type</strong></font> (<em>assoc</em>)<br> 192 <font face="Arial, Helvetica, sans-serif"><strong>extends</strong></font> <font face="Arial, Helvetica, sans-serif"><strong>struct</strong></font>(<em>next</em>: 193 <em>assoc</em>; <em>index</em>: <em>integer</em>; <em>value</em>: <em>element</em>);<br> 194 <font face="Arial, Helvetica, sans-serif"><strong>let</strong></font> <em>empty</em> 195 == <em>assoc</em>$<em>nil</em>;<br> 196 <font face="Arial, Helvetica, sans-serif"><strong>let</strong></font> <em>enter</em> 197 ==<br> 198 <font face="Arial, Helvetica, sans-serif"><strong>proc</strong></font>(<em>table</em>: 199 <em>assoc</em>; <em>num</em>: <em>integer</em>; <em>val</em>: <em>element</em>)<em>assoc</em><br> 200 <font face="Arial, Helvetica, sans-serif"><strong>begin</strong></font><br> 201 <em>assoc</em>$<em>constr</em>(<em>table</em>, <em>num</em>, <em>val</em>)<br> 202 <font face="Arial, Helvetica, sans-serif"><strong>end</strong></font>;<br> 203 <font face="Arial, Helvetica, sans-serif"><strong>letrec</strong></font> <em>lookup</em> 204 ==<br> 205 <font face="Arial, Helvetica, sans-serif"><strong>proc</strong></font>(<em>table</em>: 206 <em>assoc</em>; <em>num</em>: <em>integer</em>)<em>element</em><br> 207 <font face="Arial, Helvetica, sans-serif"><strong>begin</strong></font><br> 208 <font face="Arial, Helvetica, sans-serif"><strong>if</strong></font> <em>table</em> 209 = <em>assoc</em>$<em>nil</em><br> 210 <font face="Arial, Helvetica, sans-serif"><strong>then</strong></font> <font face="Arial, Helvetica, sans-serif"><strong>raise</strong></font> 211 <em>not_found</em><br> 212 <font face="Arial, Helvetica, sans-serif"><strong>else</strong></font> <font face="Arial, Helvetica, sans-serif"><strong>if</strong></font> 213 <em>table</em>.<em>index</em> = <em>num</em><br> 214 <font face="Arial, Helvetica, sans-serif"><strong>then</strong></font> <em>table</em>.<em>value</em><br> 215 <font face="Arial, Helvetica, sans-serif"><strong>else</strong></font> <em>lookup</em>(<em>table</em>.<em>next</em>, 216 <em>num</em>)<br> 217 <font face="Arial, Helvetica, sans-serif"><strong>end</strong></font><br> 218 <font face="Arial, Helvetica, sans-serif"><strong>en</strong></font>}<br> 219 <font face="Arial, Helvetica, sans-serif"><strong>end</strong></font>;</p> 220<p>This is a very simple minded definition but it illustrates the point. We start 221 by giving the header of the procedure which includes the signature of the argument, 222 in this case that <em>element</em> is a type but that any type will do, and 223 the signature of the result. The result is a type with three objects, a value 224 which denotes the empty table and procedures to enter and look up items from 225 the table. It is implemented in terms of a <font face="Arial, Helvetica, sans-serif"><strong>struct</strong></font> 226 (a record with a <em>nil</em> value and equality) which makes up a list of index/value 227 pairs. <em>enter</em> just returns a new list with the new pair "cons-ed" 228 onto the front (We could have written simply <font face="Arial, Helvetica, sans-serif"><strong>let</strong></font> 229 <em>enter</em> == <em>assoc</em>$<em>constr</em>; since the arguments are in 230 the same order). A better implementation would check to see if there was already 231 an entry with that index and return a list with the old entry replaced by the 232 new one. <em>lookup</em> searches the list for an entry with the required index 233 and either returns the value or raises an exception. </p> 234<p>There is no particular reason why we should use integers as the indexing value, 235 it would be perfectly possible to use any type which had an equality operation. 236 The procedure header would then be </p> 237<p><font face="Arial, Helvetica, sans-serif"><strong>proc</strong></font>(<em>element</em>: 238 <font face="Arial, Helvetica, sans-serif"><strong>type</strong></font> <font face="Arial, Helvetica, sans-serif"><strong>end</strong></font>;<br> 239 <em>index_type</em>: <font face="Arial, Helvetica, sans-serif"><strong>type</strong></font> 240 (<em>i</em>) = : <font face="Arial, Helvetica, sans-serif"><strong>proc</strong></font>(<em>i</em>;<em>i</em>)<em>boolean</em> 241 <font face="Arial, Helvetica, sans-serif"><strong>end</strong></font>)...</p> 242<p> with <em>integer</em> replaced everywhere in the body by <em>index_type</em>. 243 A more efficient implementation for index types with an ordering would be to 244 use binary trees rather than lists. We would then have to add a > or < to 245 <em>index_type</em>, or at least replace the = by one of these. Now, since types 246 are values we could incorporate an if-statement into the procedure and use one 247 or other of the implementations depending on the value of a further parameter. 248 We might want to do this because one implementation may be more efficient for, 249 say, small tables and the other for larger ones. For the example we will assume 250 a parameter <em>use_binary_tree</em>. The procedure will now look something 251 like this.</p> 252<p><font face="Arial, Helvetica, sans-serif"><strong>proc</strong></font>(<em>element</em>: 253 <font face="Arial, Helvetica, sans-serif"><strong>type</strong></font> <font face="Arial, Helvetica, sans-serif"><strong>end</strong></font>;<br> 254 <em>index_type</em>: <font face="Arial, Helvetica, sans-serif"><strong>type</strong></font> 255 (<em>i</em>) = , < : <font face="Arial, Helvetica, sans-serif"><strong>proc</strong></font>(<em>i</em>;<em>i</em>)<em>boolean</em> 256 <font face="Arial, Helvetica, sans-serif"><strong>end</strong></font>;<br> 257 <em>use_binary_tree</em>: <em>boolean</em>)...<br> 258 <font face="Arial, Helvetica, sans-serif"><strong>begin</strong></font><br> 259 <font face="Arial, Helvetica, sans-serif"><strong>if</strong></font> <em>use_binary_tree</em><br> 260 <font face="Arial, Helvetica, sans-serif"><strong>then</strong></font><br> 261 <font face="Arial, Helvetica, sans-serif"><strong>type</strong></font> .... 262 {Binary tree implementation}<br> 263 <font face="Arial, Helvetica, sans-serif"><strong>end</strong></font><br> 264 <font face="Arial, Helvetica, sans-serif"><strong>else</strong></font><br> 265 <font face="Arial, Helvetica, sans-serif"><strong>type</strong></font> .... 266 {List implementation}<br> 267 <font face="Arial, Helvetica, sans-serif"><strong>end</strong></font><br> 268 <font face="Arial, Helvetica, sans-serif"><strong>end</strong></font></p> 269<p>This could now be called as</p> 270<p><font face="Arial, Helvetica, sans-serif"><strong>let</strong></font> <em>a_table</em> 271 == <em>associative</em>(<em>string</em>, <em>integer</em>, <em>true</em>);<br> 272 <font face="Arial, Helvetica, sans-serif"><strong>let</strong></font> <em>another_table</em> 273 == <em>associative</em>(<em>string</em>, <em>integer</em>, <em>size</em> > 30); 274</p> 275<p>In the second case the expression may not be able to be evaluated when the 276 call to the procedure is compiled, <em>but this does not matter</em>. We do 277 not know at compile-time which of the two implementations of the type will be 278 used, but we know that either of them have all the operations required so they 279 will do equally well. There is however a problem with this idea of types which 280 this example shows quite nicely. Since the expression may not be evaluated at 281 compile-time how do we know when two values have the same type? The type system 282 must ensure that we apply the <em>lookup</em> procedure which understands the 283 representation of the particular associative memory. It would be catastrophic 284 to try to look up a value assuming that the value represented a tree when it 285 was in fact a list. We need the type system to assure us at compile-time that 286 the expressions </p> 287<p><font face="Arial, Helvetica, sans-serif"><strong>let</strong></font> <em>y</em> 288 == X$<em>enter</em>(X$<em>empty</em>, 1, "hello");<br> 289 X$<em>lookup</em>(<em>y</em>); </p> 290<p>where X stands for a type or type-returning expression, will not give faults 291 at run-time because of a mistake in interpreting the representations. There 292 are several possible approaches to the problem of which Poly and Russell illustrate 293 two. In Russell values can have types such as </p> 294<p><em>associative</em>(<em>string</em>, <em>integer</em>, <em>size</em> > 30)</p> 295<p>provided nothing in the expression involves a global variable (Variable in 296 this context means something whose value can be changed by assignment.) This 297 essentially means that all functions have to be "variable-free", not 298 just those which directly return types. Given this restriction it is possible 299 to say that if two expressions are syntatically the same in a given context 300 then they return the same value. If however, <em>size</em> were a variable, 301 or <em>associative</em> looked at the value of a global variable, then we could 302 not say with certainty that two values with type</p> 303<p><em>associative</em>(<em>string</em>, <em>integer</em>, <em>size</em> > 30)</p> 304<p>had the same type. Taking a purely synatactic view means that expressions like</p> 305<p><em>associative</em>(<em>string</em>, <em>integer</em>, 2 > 1)</p> 306<p>and </p> 307<p><em>associative</em>(<em>string</em>, <em>integer</em>, <em>true</em>)</p> 308<p>are not the same type. In Poly types are only regarded as the same if they 309 are the same <em>named</em> type. So while values with types which are expressions 310 can sometimes be produced there is very little that can be done with them. To 311 be useful a type-returning expression has to be bound to an identifier.</p> 312<p><font face="Arial, Helvetica, sans-serif"><strong>let</strong></font> <em>a_table</em> 313 == <em>associative</em>(<em>string</em>, <em>integer</em>, <em>true</em>);<br> 314 <font face="Arial, Helvetica, sans-serif"><strong>let</strong></font> <em>a_val</em> 315 == <em>a_table</em>$<em>enter</em>(<em>a_table</em>$<em>empty</em>, 1, "hello");<br> 316 <font face="Arial, Helvetica, sans-serif"><strong>let</strong></font> <em>another_table</em> 317 == <em>associative</em>(<em>string</em>, <em>integer</em>, <em>true</em>);<br> 318 <font face="Arial, Helvetica, sans-serif"><strong>let</strong></font> <em>another_val</em> 319 == <em>another_table</em>$<em>enter</em>(<em>another_table</em>$<em>empty</em>, 320 1, "hello"); </p> 321<p><em>a_val</em> and <em>another_val</em> have distinct types <em>a_table</em> 322 and <em>another_table</em>. </p> 323<p>A side-effect of this is that "types" such as</p> 324<p><em>list</em>(<em>integer</em>)</p> 325<p>cannot be used directly. We have to write</p> 326<p><font face="Arial, Helvetica, sans-serif"><strong>let</strong></font> <em>int_list</em> 327 == <em>list</em>(<em>integer</em>); </p> 328<p>and then use <em>int_list</em> as the type. However this is not such a problem 329 as might at first appear. Since we can write functions which take implied parameters 330 we can write an <em>append</em> function which will work on values of any type 331 with the appropriate <em>hd</em>, <em>tl</em> etc., irrespective of their actual 332 implementations. </p> 333<h2>3. Modules</h2> 334<p>A module is conventionally thought of as a collection of types and functions 335 which can be separately compiled. It has an interface which is the types of 336 these functions so that other modules can make use of it without having to know 337 the precise implementation.</p> 338<p>Types in Poly can be thought of in the same way. A type is a collection of 339 operations and its signature gives their "types" (We usually think of a type 340 as being something like <em>integer</em> which has values, but a type in Poly 341 can be any collection of objects. So a collection of floating point functions 342 <em>sin</em>, <em>cos</em> etc. could be combined as a type even though there 343 is no such thing as a value of this type.). A module which makes use of other 344 modules, <em>imports</em> them in conventional terms, can be represented as 345 a procedure which is applied to types and returns a type. One of the big advantages 346 of this view of modules is that binding modules together is done using statements 347 written in Poly and type-checked using the normal Poly type-checker. There is 348 no need, as with MESA and C-MESA[Mit79] for a separate module binding language. 349</p> 350<p>The module system for ML[Har85] is essentially a system built on top of the 351 kernel language. <em>Structures</em> and <em>functors</em> correspond to values 352 and functions in the kernel but the ML type system makes it impossible to unify 353 these concepts. </p> 354<h2>4. Persistence in Poly</h2> 355<p>Poly is an interactive system in which the user types expressions and declarations 356 and these are compiled and executed immediately. When objects are declared they 357 are added to the objects the system knows about and they can be used in subsequent 358 expressions. Such systems are quite common and usually work on a core image 359 which can be saved from one session to the next. This is fine provided that 360 the core image does not grow too big. However as the core image gets larger 361 the costs of reading it in and writing it out get more serious. Also the cost 362 of garbage-collection rises. There is a further question about the security 363 of the data if the machine crashes while writing out a large image. </p> 364<p>For these reasons Poly is implemented in a persistent store [Atk81a][Atk81b] 365 which can be thought of as a core image where objects are only read in when 366 they are actually required. The cost of loading objects from the image, or database, 367 depends on the amount of the store which is used by a program rather than the 368 total size of the image. A simple transaction mechanism ensures that the database 369 remains in a consistent state in the event of a machine crash or if the program 370 is killed halfway through writing out. Some experiments have been done on using 371 multiple databases so that large programs such as the compiler can be shared 372 between several users. </p> 373<p>Using this persistent store the Poly compiler has been boot-strapped so that 374 it is just another procedure. A Standard ML compiler has also been written which 375 uses the same back-end as the Poly compiler.</p> 376<p> In a typical interactive programming system there is a single name space for 377 all identifiers, but as the number of declarations have grown it has become 378 necessary to divide up the name space into separate <em>environments</em>. An 379 environment is very similar to a directory in a filing system or to a block 380 in a programming language. When an environment is selected all new identifiers 381 are entered into it and looked up in it. There is the equivalent of the scope 382 rules in a programming language so that an identifier is looked up in a series 383 of nested environments until it is found. It could be thought of as a Poly type 384 since it is a collection of objects, but it cannot be quite the same because 385 declarations can be added or removed dynamically to an environment while a Poly 386 type must be "frozen". </p> 387<h2>5. Conclusions</h2> 388<p>Poly was designed as a general purpose language and has been used successfully 389 for some medium scale projects (there is about 20000 lines of code in the Poly 390 and ML compilers). After some years of programming in it the type system has 391 proved to work very well. Treating types as first-class values seems to result 392 in a generally simpler language than languages where types are treated as purely 393 compile-time objects. Experience with Standard ML suggests that pattern-matching 394 and exceptions with parameters (exceptions in Poly cannot carry parameters) 395 are something that should be added. Some kind of type inference based on unification 396 could be used to reduce the amount of type information which must be given explicitly, 397 though it cannot remove it completely. The presence of a persistent store tends 398 to break down the distinction between compile-time and run-time, since the compiler 399 is just another function to be applied. Compile-time does have some meaning 400 in this system however. Compiling an expression means checking the interfaces 401 between functions and their arguments so that the result can be guaranteed not 402 to produce a type-checking error later on. If we compile a procedure then we 403 want to produce a type for the procedure as a whole and remove the type information 404 within it. Not only does this improve the efficiency of the procedure but it 405 also gives us a degree of certainty that the procedure will not fail. It is 406 a little way along the road to proving the correctness of the procedure. There 407 is a cost in this static type checking in Poly in that some procedures which 408 are in fact type-correct will fail to pass a static type-checker, but the advantages 409 of static type-checking more than outweigh the disadvantages.</p> 410<h2> References</h2> 411<table width="100%" border="0"> 412 <tr> 413 <td valign="top">[Atk81a]</td> 414 <td>Atkinson M.P., Chisholm K.J. and Cockshott W.P. "PS-Algol: An Algol with 415 a Persistent Heap." Technical Report CSR-94-81, Computer Science Dept., 416 University of Edinburgh.</td> 417 </tr> 418 <tr> 419 <td valign="top">[Atk81b]</td> 420 <td>Atkinson, M.P., Bailey P., Cockshott W.P., Chisholm K.J. and Morrison 421 R. "Progress with Persistent Programming." Technical Report PPR-8-81, 422 Computer Science Dept., University of Edinburgh. </td> 423 </tr> 424 <tr> 425 <td valign="top">[Car85]</td> 426 <td>Cardelli L. and MacQueen D. "Persistence and Type Abstraction." Proc. 427 of the Persistence and Data Types Workshop, August 1985.</td> 428 </tr> 429 <tr> 430 <td valign="top">[Dem79]</td> 431 <td>Demers A. and Donahue J. "Revised Report on Russell." TR 79-389 Dept. 432 of Computer Science, Cornell University.</td> 433 </tr> 434 <tr> 435 <td valign="top">[Fai85]</td> 436 <td>Fairbairn J. "A New Type-Checker for a Functional Language." Proc. of 437 the Persistence and Data Types Workshop, August 1985.</td> 438 </tr> 439 <tr> 440 <td valign="top">[Har85]</td> 441 <td>Harper R. "Modules and Persistence in Standard ML." Proc. of the Persistence 442 and Data Types Workshop, August 1985. </td> 443 </tr> 444 <tr> 445 <td valign="top">[Mat85]</td> 446 <td>Matthews D.C.J. "Poly Manual" SIGPLAN Notices. Vol.20 No.9 Sept. 1985. 447 </td> 448 </tr> 449 <tr> 450 <td valign="top">[Mil84]</td> 451 <td>Milner R. "A Proposal for Standard ML" in "Proceedings of the 1984 452 ACM Symposium on Lisp and Functional Programming", Austin, Texas 1984. 453 </td> 454 </tr> 455 <tr> 456 <td valign="top">[Mit79]</td> 457 <td>Mitchell James G. et al. "MESA Language Manual." XEROX PARC, 458 1979 </td> 459 </tr> 460</table></body> 461</html> 462