(* the return value of doing so is () *)
(* other return values could also be reasonable: *)
(* such as the old value of ycell, the new value, an arbitrary int, and so on *)
- x + !ycell;; (* the !ycell operation "dereferences" the cell---it retrieves the value it contains *)
+ x + !ycell (* the !ycell operation "dereferences" the cell---it retrieves the value it contains *)
Scheme is similar. There are various sorts of reference cells available in Scheme. The one most like OCaml's `ref` is a `box`. Here's how we'd write the same fragment in Scheme:
let plus_y x = x + !ycell in
let first = plus_y 1 in (* first is assigned the value 2 *)
ycell := 2; let second = plus_y 1 in (* second is assigned the value 3 *)
- first = second;; (* not true! *)
+ first = second (* not true! *)
Notice that the two invocations of `plus_y 1` yield different results, even though the same value is being supplied as an argument to the same function.
Similarly, functions like these:
- let f cell = !cell;;
+ let f cell = !cell
- let g cell = cell := !cell + 1; !cell;;
+ let g cell = cell := !cell + 1; !cell
may return different results each time they're invoked, even if they're always supplied one and the same reference cell as argument.
and be able to refer back to that cell later by using the result that we assigned to the variable `ycell`. In our simple implementation, we're letting the store just be an `int list`, and we can let the "keys" be indexes in that list, which are (also) just `int`s. Somehow we should keep track of which variables are assigned `int`s as `int`s and which are assigned `int`s as indexes into the store. So we'll create a special type to wrap the latter:
- type store_index = Index of int;;
+ type store_index = Index of int
Our interpretation function will look something like this:
Here's the implementation of the State monad, together with an implementation of the Reader monad for comparison:
- type env = (identifier * int) list;;
+ type env = (identifier * int) list
(* alternatively, an env could be implemented as type identifier -> int *)
- type 'a reader = env -> 'a;;
+ type 'a reader = env -> 'a
let reader_mid (x : 'a) : 'a reader =
- fun e -> x;;
+ fun e -> x
let reader_mbind (xx : 'a reader) (k : 'a -> 'b reader) : 'b reader =
fun e -> let x = xx e in
let yy = k x in
- yy e;;
+ yy e
- type store = int;;
+ type store = int
(* very simple store, holds only a single int *)
(* this corresponds to having only a single mutable variable *)
- type 'a state = store -> ('a, store);;
+ type 'a state = store -> ('a, store)
let state_mid (x : 'a) : 'a state =
- fun s -> (x, s);;
+ fun s -> (x, s)
let state_mbind (xx : 'a state) (k : 'a -> 'b state) : 'b state =
fun s -> let (x, s') = xx s in
let yy = k x in
- yy s';;
+ yy s'
Notice the similarities (and differences) between the implementation of these two monads.
With the State monad, we'll also have some special-purpose operations. We'll consider two basic ones here. One will be to retrieve what is the current store. This is like the Reader monad's `asks (lookup "x")`, except in this simple implementation there's only a single location for a value to be looked up from. Here's how we'll do it:
- let state_get : store state =
- fun s -> (s, s);;
+ let state_get : store state = fun s -> (s, s)
This passes through the current store unaltered, and also returns a copy of the store as its payload. (What exactly corresponds to this is the simpler Reader operation `ask`.) We can use the `state_get` operation like this:
The other operation for the State monad will be to update the existing store to a new one. This operation looks like this:
let state_put (new_store : int) : dummy state =
- fun s -> (dummy, new_store);;
+ fun s -> (dummy, new_store)
If we want to stick this in a `... >>= ...` chain, we'll need to prefix it with `fun _ ->` too, like this:
To get the whole process started, the complex computation so defined will need to be given a starting store. So we'd need to do something like this:
let computation = some_state_monad_value >>= operation >>= operation in
- computation initial_store;;
+ computation initial_store
* See also our [[State Monad Tutorial]]. LINK TODO
let ycell = ref 1 in
let xcell = ref 1 in
- ycell := 2; !xcell;;
+ ycell := 2; !xcell
(* evaluates to 1, not to 2 *)
So we have here the basis for introducing a new kind of equality predicate into our language, which tests not for qualitative indiscernibility but for numerical equality. In OCaml this relation is expressed by the double equals `==`. In Scheme it's spelled `eq?` Computer scientists sometimes call this relation "physical equality". Using this equality predicate, our comparison of `ycell` and `xcell` will be `false`, even if they then happen to contain the same `int`.