OCaml 中的指针
指针在OCaml
OCaml有指针,而实际上他们无处不在。它们大部分隐式地使用,也有些时候显式使用会更方便些。 C中繁琐的指针操作在OCaml中消失了,更准确地说,指针完全被编译器自动处理了,因此OCaml程序员 可以忽略掉指针的存在而专注于程序本身,而不会带来额外的问题。
在一些极其罕有的情况,显式的指针是必需的(比如说用OCaml把指令式语言的算法翻译一遍), OCaml提供的引用已经相当成熟,并且还是一等公民(可以被创建、保存、传入、返回)。
显式指针是ref
类型
你总可以显式地管理指针,但这往往是浪费时间和精力。
让我们以链表为例,这里的C和Pascal中的数据类型用到了指针:
/* Cells and lists type in C */
struct cell {
int hd;
struct cell *tl;
};
typedef struct cell cell, *list;
{Cells and lists type in Pascal}
type
list = ^cell;
cell = record
hd: integer;
tl: cell;
end;
我们可以把这段代码翻译成OCaml,定义一个类型,而不用指针:
# type list = Nil | Cons of int * list;;
type list = Nil | Cons of int * list
链表是一个递归结构,分别有两个子类,一个是空链表Nil
,另一个被表示成一个pair Cons
。
自动内存管理在这里发挥了作用:你只要通过 Cons (x, l)
就可以把 x
加在链表 l
前。 在C中,你必须手动处理这所有的一切:
/* 空链表 */
#define nil NULL
/* 链表的构造器 */
list cons (element x, list l)
{
list result;
result = (list) malloc (sizeof (cell));
result -> hd = x;
result -> tl = l;
return (result);
}
Pascal也类似:
{创建一个链节}
function cons (x: integer; l: list): list;
var p: list;
begin
new(p);
p^.hd := x;
p^.tl := l;
cons := p
end;
我们可以看见C程序中,链节的域必须是可变的,否则不可能对其初始化。而OCaml则把内存 分配和初始化放到了一个操作中:构造器构造。这样,就可以合理定义不可变数据结构(一般认为是纯 函数式数据结构)。如果必须对数据进行修改,OCaml的record可以定义可变域。这里,一个 元素可变的链表可以如下定义:
# type list = Nil | Cons of cell
and cell = { mutable hd : int; tl : list };;
type list = Nil | Cons of cell
and cell = { mutable hd : int; tl : list; }
如果链节引用本身也要被修改,那么tl
也可以定义成可变:
# type list = Nil | Cons of cell
and cell = {mutable hd : int; mutable tl : list};;
type list = Nil | Cons of cell
and cell = { mutable hd : int; mutable tl : list; }
这里赋值的意义依然不大:你还是要通过Cons {hd = 1; tl = l}
来把 1
加到 l
前。 OCaml中,除非逼不得已,否则不会使用赋值操作。
指针于可变域或向量
通常情况下,指针式用来修改数据结构的。在OCaml程序中,这意味着在record中使用向量或者可变域。 对指针的这种用法,Pascal的指令:x^.label := val
(x
是一个有field
域的record) 对应于OCaml的 x.label <- val
(x
是一个有field
可变域的record)。Pascal的 ^
消失了,因为解引用已经由编译器处理好。
结论: 你能在OCaml中如C,Pascal使用指针,但这不是OCaml的风格,否则这和你在典型的 编程语言与指针纠缠没有区别。下面是个更完整的例子。
OCaml中定义指针
一个一般的pointer类型可以用来定义一个指针,而一个指针的值不是null就是某个内存地址:
# type 'a pointer = Null | Pointer of 'a ref;;
type 'a pointer = Null | Pointer of 'a ref
显式的解引用和指针赋值很容易就可以定义。我们定义一个前缀操作符 !^
来解引用,和一个中缀操作符 ^:=
来赋值。
# let ( !^ ) = function
| Null -> invalid_arg "Attempt to dereference the null pointer"
| Pointer r -> !r;;
val ( !^ ) : 'a pointer -> 'a = <fun>
# let ( ^:= ) p v =
match p with
| Null -> invalid_arg "Attempt to assign the null pointer"
| Pointer r -> r := v;;
val ( ^:= ) : 'a pointer -> 'a -> unit = <fun>
现在我们定义一个指针的分配和初始化:
# let new_pointer x = Pointer (ref x);;
val new_pointer : 'a -> 'a pointer = <fun>
现在我们可以定义一个指向整数的指针:
# let p = new_pointer 0;;
val p : int pointer = Pointer {contents = 0}
# p ^:= 1;;
- : unit = ()
# !^p;;
- : int = 1
整数链表
现在我们可以如一般的指令式语言用指针定义链表:
# (* The list type ``à la Pascal'' *)
type ilist = cell pointer
and cell = {mutable hd : int; mutable tl : ilist};;
type ilist = cell pointer
and cell = { mutable hd : int; mutable tl : ilist; }
然后我们定义链节的分配,链表的构造器和解构器:
# let new_cell () = {hd = 0; tl = Null};;
val new_cell : unit -> cell = <fun>
# let cons x l =
let c = new_cell () in
c.hd <- x;
c.tl <- l;
(new_pointer c : ilist);;
val cons : int -> ilist -> ilist = <fun>
# let hd (l : ilist) = !^l.hd;;
val hd : ilist -> int = <fun>
# let tl (l : ilist) = !^l.tl;;
val tl : ilist -> ilist = <fun>
现在我们可以编写经典的给予指针的算法,连同他们的问题,和null引起的错误。比方说,链表 连接会修改第一个链表参数,然后把第二个链表连接到第一个链表的最后:
# (* Physical append *)
let append (l1 : ilist) (l2 : ilist) =
let temp = ref l1 in
while tl !temp <> Null do
temp := tl !temp
done;
!^ !temp.tl <- l2;;
val append : ilist -> ilist -> unit = <fun>
# (* An example: *)
let l1 = cons 1 (cons 2 Null);;
val l1 : ilist =
Pointer
{contents = {hd = 1; tl = Pointer {contents = {hd = 2; tl = Null}}}}
# let l2 = cons 3 Null;;
val l2 : ilist = Pointer {contents = {hd = 3; tl = Null}}
# append l1 l2;;
- : unit = ()
l1
和 l2
连接到了一起:
# l1;;
- : ilist =
Pointer
{contents =
{hd = 1;
tl =
Pointer
{contents = {hd = 2; tl = Pointer {contents = {hd = 3; tl = Null}}}}}}
但这个操作引入了一个很糟糕的副作用:l1
现在不止包括原来的元素,还包括了l2
的。所以 从原来意义上的l1
已经不存在了,可以认为append
消费了第一个参数。换句话说,一个函数 调用的结果隐式地依赖于函数调用的历史。这个奇怪的行为引入了很多指针操作上的困难。比方说 这个例子中,一切事情似乎工作正常:
# append l1 l1;;
- : unit = ()
然后看看 l1
成了什么值?:
# l1;;
- : ilist =
Pointer
{contents =
{hd = 1;
tl =
Pointer
{contents = {hd = 2; tl = Pointer {contents = {hd = 3; tl = <cycle>}}}}}}
多态链表
为了超过Pascal的类型系统,,我们可以用指针定义多态链表,下面是一个简单的实现:
# type 'a lists = 'a cell pointer
and 'a cell = {mutable hd : 'a pointer; mutable tl : 'a lists};;
type 'a lists = 'a cell pointer
and 'a cell = { mutable hd : 'a pointer; mutable tl : 'a lists; }
# let new_cell () = {hd = Null; tl = Null};;
val new_cell : unit -> 'a cell = <fun>
# let cons x l =
let c = new_cell () in
c.hd <- new_pointer x;
c.tl <- l;
(new_pointer c : 'a lists);;
val cons : 'a -> 'a lists -> 'a lists = <fun>
# let hd (l : 'a lists) = !^l.hd;;
val hd : 'a lists -> 'a pointer = <fun>
# let tl (l : 'a lists) = !^l.tl;;
val tl : 'a lists -> 'a lists = <fun>
# let append (l1 : 'a lists) (l2 : 'a lists) =
let temp = ref l1 in
while tl !temp <> Null do
temp := tl !temp
done;
!^ !temp.tl <- l2;;
val append : 'a lists -> 'a lists -> unit = <fun>