Commit | Line | Data |
---|---|---|
7f918cf1 CE |
1 | ObjectOrientedProgramming |
2 | ========================= | |
3 | ||
4 | <:StandardML:Standard ML> does not have explicit support for | |
5 | object-oriented programming. Here are some papers that show how to | |
6 | express certain object-oriented concepts in SML. | |
7 | ||
8 | * <!Cite(Berthomieu00, OO Programming styles in ML)> | |
9 | ||
10 | * <!Cite(ThorupTofte94, Object-oriented programming and Standard ML)> | |
11 | ||
12 | * <!Cite(LarsenNiss04, mGTK: An SML binding of Gtk+)> | |
13 | ||
14 | * <!Cite(FluetPucella06, Phantom Types and Subtyping)> | |
15 | ||
16 | The question of OO programming in SML comes up every now and then. | |
17 | The following discusses a simple object-oriented (OO) programming | |
18 | technique in Standard ML. The reader is assumed to be able to read | |
19 | Java and SML code. | |
20 | ||
21 | ||
22 | == Motivation == | |
23 | ||
24 | SML doesn't provide subtyping, but it does provide parametric | |
25 | polymorphism, which can be used to encode some forms of subtyping. | |
26 | Most articles on OO programming in SML concentrate on such encoding | |
27 | techniques. While those techniques are interesting -- and it is | |
28 | recommended to read such articles -- and sometimes useful, it seems | |
29 | that basically all OO gurus agree that (deep) subtyping (or | |
30 | inheritance) hierarchies aren't as practical as they were thought to | |
31 | be in the early OO days. "Good", flexible, "OO" designs tend to have | |
32 | a flat structure | |
33 | ||
34 | ---- | |
35 | Interface | |
36 | ^ | |
37 | | | |
38 | - - -+-------+-------+- - - | |
39 | | | | | |
40 | ImplA ImplB ImplC | |
41 | ---- | |
42 | ||
43 | ||
44 | and deep inheritance hierarchies | |
45 | ||
46 | ---- | |
47 | ClassA | |
48 | ^ | |
49 | | | |
50 | ClassB | |
51 | ^ | |
52 | | | |
53 | ClassC | |
54 | ^ | |
55 | | | |
56 | ---- | |
57 | ||
58 | tend to be signs of design mistakes. There are good underlying | |
59 | reasons for this, but a thorough discussion is not in the scope of | |
60 | this article. However, the point is that perhaps the encoding of | |
61 | subtyping is not as important as one might believe. In the following | |
62 | we ignore subtyping and rather concentrate on a very simple and basic | |
63 | dynamic dispatch technique. | |
64 | ||
65 | ||
66 | == Dynamic Dispatch Using a Recursive Record of Functions == | |
67 | ||
68 | Quite simply, the basic idea is to implement a "virtual function | |
69 | table" using a record that is wrapped inside a (possibly recursive) | |
70 | datatype. Let's first take a look at a simple concrete example. | |
71 | ||
72 | Consider the following Java interface: | |
73 | ||
74 | ---- | |
75 | public interface Counter { | |
76 | public void inc(); | |
77 | public int get(); | |
78 | } | |
79 | ---- | |
80 | ||
81 | We can translate the `Counter` interface to SML as follows: | |
82 | ||
83 | [source,sml] | |
84 | ---- | |
85 | datatype counter = Counter of {inc : unit -> unit, get : unit -> int} | |
86 | ---- | |
87 | ||
88 | Each value of type `counter` can be thought of as an object that | |
89 | responds to two messages `inc` and `get`. To actually send messages | |
90 | to a counter, it is useful to define auxiliary functions | |
91 | ||
92 | [source,sml] | |
93 | ---- | |
94 | local | |
95 | fun mk m (Counter t) = m t () | |
96 | in | |
97 | val cGet = mk#get | |
98 | val cInc = mk#inc | |
99 | end | |
100 | ---- | |
101 | ||
102 | that basically extract the "function table" `t` from a counter object | |
103 | and then select the specified method `m` from the table. | |
104 | ||
105 | Let's then implement a simple function that increments a counter until a | |
106 | given maximum is reached: | |
107 | ||
108 | [source,sml] | |
109 | ---- | |
110 | fun incUpto counter max = while cGet counter < max do cInc counter | |
111 | ---- | |
112 | ||
113 | You can easily verify that the above code compiles even without any | |
114 | concrete implementation of a counter, thus it is clear that it doesn't | |
115 | depend on a particular counter implementation. | |
116 | ||
117 | Let's then implement a couple of counters. First consider the | |
118 | following Java class implementing the `Counter` interface given earlier. | |
119 | ||
120 | ---- | |
121 | public class BasicCounter implements Counter { | |
122 | private int cnt; | |
123 | public BasicCounter(int initialCnt) { this.cnt = initialCnt; } | |
124 | public void inc() { this.cnt += 1; } | |
125 | public int get() { return this.cnt; } | |
126 | } | |
127 | ---- | |
128 | ||
129 | We can translate the above to SML as follows: | |
130 | ||
131 | [source,sml] | |
132 | ---- | |
133 | fun newBasicCounter initialCnt = let | |
134 | val cnt = ref initialCnt | |
135 | in | |
136 | Counter {inc = fn () => cnt := !cnt + 1, | |
137 | get = fn () => !cnt} | |
138 | end | |
139 | ---- | |
140 | ||
141 | The SML function `newBasicCounter` can be described as a constructor | |
142 | function for counter objects of the `BasicCounter` "class". We can | |
143 | also have other counter implementations. Here is the constructor for | |
144 | a counter decorator that logs messages: | |
145 | ||
146 | [source,sml] | |
147 | ---- | |
148 | fun newLoggedCounter counter = | |
149 | Counter {inc = fn () => (print "inc\n" ; cInc counter), | |
150 | get = fn () => (print "get\n" ; cGet counter)} | |
151 | ---- | |
152 | ||
153 | The `incUpto` function works just as well with objects of either | |
154 | class: | |
155 | ||
156 | [source,sml] | |
157 | ---- | |
158 | val aCounter = newBasicCounter 0 | |
159 | val () = incUpto aCounter 5 | |
160 | val () = print (Int.toString (cGet aCounter) ^"\n") | |
161 | ||
162 | val aCounter = newLoggedCounter (newBasicCounter 0) | |
163 | val () = incUpto aCounter 5 | |
164 | val () = print (Int.toString (cGet aCounter) ^"\n") | |
165 | ---- | |
166 | ||
167 | In general, a dynamic dispatch interface is represented as a record | |
168 | type wrapped inside a datatype. Each field of the record corresponds | |
169 | to a public method or field of the object: | |
170 | ||
171 | [source,sml] | |
172 | ---- | |
173 | datatype interface = | |
174 | Interface of {method : t1 -> t2, | |
175 | immutableField : t, | |
176 | mutableField : t ref} | |
177 | ---- | |
178 | ||
179 | The reason for wrapping the record inside a datatype is that records, | |
180 | in SML, can not be recursive. However, SML datatypes can be | |
181 | recursive. A record wrapped in a datatype can contain fields that | |
182 | contain the datatype. For example, an interface such as `Cloneable` | |
183 | ||
184 | [source,sml] | |
185 | ---- | |
186 | datatype cloneable = Cloneable of {clone : unit -> cloneable} | |
187 | ---- | |
188 | ||
189 | can be represented using recursive datatypes. | |
190 | ||
191 | Like in OO languages, interfaces are abstract and can not be | |
192 | instantiated to produce objects. To be able to instantiate objects, | |
193 | the constructors of a concrete class are needed. In SML, we can | |
194 | implement constructors as simple functions from arbitrary arguments to | |
195 | values of the interface type. Such a constructor function can | |
196 | encapsulate arbitrary private state and functions using lexical | |
197 | closure. It is also easy to share implementations of methods between | |
198 | two or more constructors. | |
199 | ||
200 | While the `Counter` example is rather trivial, it should not be | |
201 | difficult to see that this technique quite simply doesn't require a huge | |
202 | amount of extra verbiage and is more than usable in practice. | |
203 | ||
204 | ||
205 | == SML Modules and Dynamic Dispatch == | |
206 | ||
207 | One might wonder about how SML modules and the dynamic dispatch | |
208 | technique work together. Let's investigate! Let's use a simple | |
209 | dispenser framework as a concrete example. (Note that this isn't | |
210 | intended to be an introduction to the SML module system.) | |
211 | ||
212 | === Programming with SML Modules === | |
213 | ||
214 | Using SML signatures we can specify abstract data types (ADTs) such as | |
215 | dispensers. Here is a signature for an "abstract" functional (as | |
216 | opposed to imperative) dispenser: | |
217 | ||
218 | [source,sml] | |
219 | ---- | |
220 | signature ABSTRACT_DISPENSER = sig | |
221 | type 'a t | |
222 | val isEmpty : 'a t -> bool | |
223 | val push : 'a * 'a t -> 'a t | |
224 | val pop : 'a t -> ('a * 'a t) option | |
225 | end | |
226 | ---- | |
227 | ||
228 | The term "abstract" in the name of the signature refers to the fact that | |
229 | the signature gives no way to instantiate a dispenser. It has nothing to | |
230 | do with the concept of abstract data types. | |
231 | ||
232 | Using SML functors we can write "generic" algorithms that manipulate | |
233 | dispensers of an unknown type. Here are a couple of very simple | |
234 | algorithms: | |
235 | ||
236 | [source,sml] | |
237 | ---- | |
238 | functor DispenserAlgs (D : ABSTRACT_DISPENSER) = struct | |
239 | open D | |
240 | ||
241 | fun pushAll (xs, d) = foldl push d xs | |
242 | ||
243 | fun popAll d = let | |
244 | fun lp (xs, NONE) = rev xs | |
245 | | lp (xs, SOME (x, d)) = lp (x::xs, pop d) | |
246 | in | |
247 | lp ([], pop d) | |
248 | end | |
249 | ||
250 | fun cp (from, to) = pushAll (popAll from, to) | |
251 | end | |
252 | ---- | |
253 | ||
254 | As one can easily verify, the above compiles even without any concrete | |
255 | dispenser structure. Functors essentially provide a form a static | |
256 | dispatch that one can use to break compile-time dependencies. | |
257 | ||
258 | We can also give a signature for a concrete dispenser | |
259 | ||
260 | [source,sml] | |
261 | ---- | |
262 | signature DISPENSER = sig | |
263 | include ABSTRACT_DISPENSER | |
264 | val empty : 'a t | |
265 | end | |
266 | ---- | |
267 | ||
268 | and write any number of concrete structures implementing the signature. | |
269 | For example, we could implement stacks | |
270 | ||
271 | [source,sml] | |
272 | ---- | |
273 | structure Stack :> DISPENSER = struct | |
274 | type 'a t = 'a list | |
275 | val empty = [] | |
276 | val isEmpty = null | |
277 | val push = op :: | |
278 | val pop = List.getItem | |
279 | end | |
280 | ---- | |
281 | ||
282 | and queues | |
283 | ||
284 | [source,sml] | |
285 | ---- | |
286 | structure Queue :> DISPENSER = struct | |
287 | datatype 'a t = T of 'a list * 'a list | |
288 | val empty = T ([], []) | |
289 | val isEmpty = fn T ([], _) => true | _ => false | |
290 | val normalize = fn ([], ys) => (rev ys, []) | q => q | |
291 | fun push (y, T (xs, ys)) = T (normalize (xs, y::ys)) | |
292 | val pop = fn (T (x::xs, ys)) => SOME (x, T (normalize (xs, ys))) | _ => NONE | |
293 | end | |
294 | ---- | |
295 | ||
296 | One can now write code that uses either the `Stack` or the `Queue` | |
297 | dispenser. One can also instantiate the previously defined functor to | |
298 | create functions for manipulating dispensers of a type: | |
299 | ||
300 | [source,sml] | |
301 | ---- | |
302 | structure S = DispenserAlgs (Stack) | |
303 | val [4,3,2,1] = S.popAll (S.pushAll ([1,2,3,4], Stack.empty)) | |
304 | ||
305 | structure Q = DispenserAlgs (Queue) | |
306 | val [1,2,3,4] = Q.popAll (Q.pushAll ([1,2,3,4], Queue.empty)) | |
307 | ---- | |
308 | ||
309 | There is no dynamic dispatch involved at the module level in SML. An | |
310 | attempt to do dynamic dispatch | |
311 | ||
312 | [source,sml] | |
313 | ---- | |
314 | val q = Q.push (1, Stack.empty) | |
315 | ---- | |
316 | ||
317 | will give a type error. | |
318 | ||
319 | === Combining SML Modules and Dynamic Dispatch === | |
320 | ||
321 | Let's then combine SML modules and the dynamic dispatch technique | |
322 | introduced in this article. First we define an interface for | |
323 | dispensers: | |
324 | ||
325 | [source,sml] | |
326 | ---- | |
327 | structure Dispenser = struct | |
328 | datatype 'a t = | |
329 | I of {isEmpty : unit -> bool, | |
330 | push : 'a -> 'a t, | |
331 | pop : unit -> ('a * 'a t) option} | |
332 | ||
333 | fun O m (I t) = m t | |
334 | ||
335 | fun isEmpty t = O#isEmpty t () | |
336 | fun push (v, t) = O#push t v | |
337 | fun pop t = O#pop t () | |
338 | end | |
339 | ---- | |
340 | ||
341 | The `Dispenser` module, which we can think of as an interface for | |
342 | dispensers, implements the `ABSTRACT_DISPENSER` signature using | |
343 | the dynamic dispatch technique, but we leave the signature ascription | |
344 | until later. | |
345 | ||
346 | Then we define a `DispenserClass` functor that makes a "class" out of | |
347 | a given dispenser module: | |
348 | ||
349 | [source,sml] | |
350 | ---- | |
351 | functor DispenserClass (D : DISPENSER) : DISPENSER = struct | |
352 | open Dispenser | |
353 | ||
354 | fun make d = | |
355 | I {isEmpty = fn () => D.isEmpty d, | |
356 | push = fn x => make (D.push (x, d)), | |
357 | pop = fn () => | |
358 | case D.pop d of | |
359 | NONE => NONE | |
360 | | SOME (x, d) => SOME (x, make d)} | |
361 | ||
362 | val empty = | |
363 | I {isEmpty = fn () => true, | |
364 | push = fn x => make (D.push (x, D.empty)), | |
365 | pop = fn () => NONE} | |
366 | end | |
367 | ---- | |
368 | ||
369 | Finally we seal the `Dispenser` module: | |
370 | ||
371 | [source,sml] | |
372 | ---- | |
373 | structure Dispenser : ABSTRACT_DISPENSER = Dispenser | |
374 | ---- | |
375 | ||
376 | This isn't necessary for type safety, because the unsealed `Dispenser` | |
377 | module does not allow one to break encapsulation, but makes sure that | |
378 | only the `DispenserClass` functor can create dispenser classes | |
379 | (because the constructor `Dispenser.I` is no longer accessible). | |
380 | ||
381 | Using the `DispenserClass` functor we can turn any concrete dispenser | |
382 | module into a dispenser class: | |
383 | ||
384 | [source,sml] | |
385 | ---- | |
386 | structure StackClass = DispenserClass (Stack) | |
387 | structure QueueClass = DispenserClass (Queue) | |
388 | ---- | |
389 | ||
390 | Each dispenser class implements the same dynamic dispatch interface | |
391 | and the `ABSTRACT_DISPENSER` -signature. | |
392 | ||
393 | Because the dynamic dispatch `Dispenser` module implements the | |
394 | `ABSTRACT_DISPENSER`-signature, we can use it to instantiate the | |
395 | `DispenserAlgs`-functor: | |
396 | ||
397 | [source,sml] | |
398 | ---- | |
399 | structure D = DispenserAlgs (Dispenser) | |
400 | ---- | |
401 | ||
402 | The resulting `D` module, like the `Dispenser` module, works with | |
403 | any dispenser class and uses dynamic dispatch: | |
404 | ||
405 | [source,sml] | |
406 | ---- | |
407 | val [4, 3, 2, 1] = D.popAll (D.pushAll ([1, 2, 3, 4], StackClass.empty)) | |
408 | val [1, 2, 3, 4] = D.popAll (D.pushAll ([1, 2, 3, 4], QueueClass.empty)) | |
409 | ---- |