week6.mdwn

   1 [[!toc]]
   2
   3 Types, OCAML
   4 ------------
   5
   6 OCAML has type inference: the system can often infer what the type of
   7 an expression must be, based on the type of other known expressions.
   8
   9 For instance, if we type
  10
  11     # let f x = x + 3;;
  12
  13 The system replies with
  14
  15     val f : int -> int = <fun>
  16
  17 Since `+` is only defined on integers, it has type
  18
  19      # (+);;
  20      - : int -> int -> int = <fun>
  21
  22 The parentheses are there to turn off the trick that allows the two
  23 arguments of `+` to surround it in infix (for linguists, SOV) argument
  24 order. That is,
  25
  26     # 3 + 4 = (+) 3 4;;
  27     - : bool = true
  28
  29 In general, tuples with one element are identical to their one
  30 element:
  31
  32     # (3) = 3;;
  33     - : bool = true
  34
  35 though OCAML, like many systems, refuses to try to prove whether two
  36 functional objects may be identical:
  37
  38     # (f) = f;;
  39     Exception: Invalid_argument "equal: functional value".
  40
  41 Oh well.
  42
  43
  44 Booleans in OCAML, and simple pattern matching
  45 ----------------------------------------------
  46
  47 Where we would write `true 1 2` and expect it to evaluate to `1`, in
  48 OCAML boolean types are not functions (equivalently, are functions
  49 that take zero arguments).  Choices are made as follows:
  50
  51     # if true then 1 else 2;;
  52     - : int = 1
  53
  54 The types of the `then` clause and of the `else` clause must be the
  55 same.
  56
  57 The `if` construction can be re-expressed by means of the following
  58 pattern-matching expression:
  59
  60     match <bool expression> with true -> <expression1> | false -> <expression2>
  61
  62 That is,
  63
  64     # match true with true -> 1 | false -> 2;;
  65     - : int = 1
  66
  67 Compare with
  68
  69     # match 3 with 1 -> 1 | 2 -> 4 | 3 -> 9;;
  70     - : int = 9
  71
  72 Unit
  73 ----
  74
  75 All functions in OCAML take exactly one argument.  Even this one:
  76
  77     # let f x y = x + y;;
  78     # f 2 3;;
  79     - : int = 5
  80
  81 Here's how to tell that `f` has been curry'd:
  82
  83     # f 2;;
  84     - : int -> int = <fun>
  85
  86 After we've given our `f` one argument, it returns a function that is
  87 still waiting for another argument.
  88
  89 There is a special type in OCAML called `unit`.  There is exactly one
  90 object in this type, written `()`.  So
  91
  92     # ();;
  93     - : unit = ()
  94
  95 Just as you can define functions that take constants for arguments
  96
  97     # let f 2 = 3;;
  98     # f 2;;
  99     - : int = 3;;
 100
 101 you can also define functions that take the unit as its argument, thus
 102
 103     # let f () = 3;;
 104     val f : unit -> int = <fun>
 105
 106 Then the only argument you can possibly apply `f` to that is of the
 107 correct type is the unit:
 108
 109     # f ();;
 110     - : int = 3
 111
 112 Let's have some fn: think of `rec` as our `Y` combinator.  Then
 113
 114     # let rec f n = if (0 = n) then 1 else (n * (f (n - 1)));;
 115     val f : int -> int = <fun>
 116     # f 5;;
 117     - : int = 120
 118
 119 We can't define a function that is exactly analogous to our &omega;.
 120 We could try `let rec omega x = x x;;` what happens?  However, we can
 121 do this:
 122
 123     # let rec omega x = omega x;;
 124
 125 By the way, what's the type of this function?
 126 If you then apply this omega to an argument,
 127
 128     # omega 3;;
 129
 130 the interpreter goes into an infinite loop, and you have to control-C
 131 to break the loop.
 132
 133 Oh, one more thing: lambda expressions look like this:
 134
 135     # (fun x -> x);;
 136     - : 'a -> 'a = <fun>
 137     # (fun x -> x) true;;
 138     - : book = true
 139
 140 (But `(fun x -> x x)` still won't work.)
 141
 142 So we can try our usual tricks:
 143
 144     # (fun x -> true) omega;;
 145     - : bool = true
 146
 147 OCAML declined to try to evaluate the argument before applying the
 148 functor.  But remember that `omega` is a function too, so we can
 149 reverse the order of the arguments:
 150
 151     # omega (fun x -> true);;
 152
 153 Infinite loop.
 154
 155 Now consider the following differences:
 156
 157     # let test = omega omega;;
 158     [Infinite loop, need to control c out]
 159
 160     # let test () = omega omega;;
 161     val test : unit -> 'a = <fun>
 162
 163     # test;;
 164     - : unit -> 'a = <fun>
 165
 166     # test ();;
 167     [Infinite loop, need to control c out]
 168
 169 We can use functions that take arguments of type unit to control
 170 execution.  In Scheme parlance, functions on the unit type are called
 171 *thunks* (which I've always assumed was a blend of "think" and "chunk").
 172