doc/guide/src/PropertyList.adoc

   1 PropertyList
   2 ============
   3
   4 A property list is a dictionary-like data structure into which
   5 properties (name-value pairs) can be inserted and from which
   6 properties can be looked up by name.  The term comes from the Lisp
   7 language, where every symbol has a property list for storing
   8 information, and where the names are typically symbols and keys can be
   9 any type of value.
  10
  11 Here is an SML signature for property lists such that for any type of
  12 value a new property can be dynamically created to manipulate that
  13 type of value in a property list.
  14
  15 [source,sml]
  16 ----
  17 signature PROPERTY_LIST =
  18    sig
  19       type t
  20
  21       val new: unit -> t
  22       val newProperty: unit -> {add: t * 'a -> unit,
  23                                 peek: t -> 'a option}
  24    end
  25 ----
  26
  27 Here is a functor demonstrating the use of property lists.  It first
  28 creates a property list, then two new properties (of different types),
  29 and adds a value to the list for each property.
  30
  31 [source,sml]
  32 ----
  33 functor Test (P: PROPERTY_LIST) =
  34    struct
  35       val pl = P.new ()
  36
  37       val {add = addInt: P.t * int -> unit, peek = peekInt} = P.newProperty ()
  38       val {add = addReal: P.t * real -> unit, peek = peekReal} = P.newProperty ()
  39
  40       val () = addInt (pl, 13)
  41       val () = addReal (pl, 17.0)
  42       val s1 = Int.toString (valOf (peekInt pl))
  43       val s2 = Real.toString (valOf (peekReal pl))
  44       val () = print (concat [s1, " ", s2, "\n"])
  45    end
  46 ----
  47
  48 Applied to an appropriate implementation `PROPERTY_LIST`, the `Test`
  49 functor will produce the following output.
  50
  51 ----
  52 13 17.0
  53 ----
  54
  55
  56 == Implementation ==
  57
  58 Because property lists can hold values of any type, their
  59 implementation requires a <:UniversalType:>.  Given that, a property
  60 list is simply a list of elements of the universal type.  Adding a
  61 property adds to the front of the list, and looking up a property
  62 scans the list.
  63
  64 [source,sml]
  65 ----
  66 functor PropertyList (U: UNIVERSAL_TYPE): PROPERTY_LIST =
  67    struct
  68       datatype t = T of U.t list ref
  69
  70       fun new () = T (ref [])
  71
  72       fun 'a newProperty () =
  73          let
  74             val (inject, out) = U.embed ()
  75             fun add (T r, a: 'a): unit = r := inject a :: (!r)
  76             fun peek (T r) =
  77                Option.map (valOf o out) (List.find (isSome o out) (!r))
  78          in
  79             {add = add, peek = peek}
  80          end
  81    end
  82 ----
  83
  84
  85 If `U: UNIVERSAL_TYPE`, then we can test our code as follows.
  86
  87 [source,sml]
  88 ----
  89 structure Z = Test (PropertyList (U))
  90 ----
  91
  92 Of course, a serious implementation of property lists would have to
  93 handle duplicate insertions of the same property, as well as the
  94 removal of elements in order to avoid space leaks.
  95
  96 == Also see ==
  97
  98 * MLton relies heavily on property lists for attaching information to
  99 syntax tree nodes in its intermediate languages.  See
 100 <!ViewGitFile(mlton,master,lib/mlton/basic/property-list.sig)> and
 101 <!ViewGitFile(mlton,master,lib/mlton/basic/property-list.fun)>.
 102
 103 * The <:MLRISCLibrary:> <!Cite(LeungGeorge99, uses property lists
 104 extensively)>.