doc/guide/src/ObjectOrientedProgramming.adoc

   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 ----