当前位置: 首页 > 文档资料 > OCaml 中文教程 >

OCaml 中的指针

优质
小牛编辑
141浏览
2023-12-01

指针在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 = ()

l1l2 连接到了一起:

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