Mailing list for all users of the OCaml language and system.
 help / color / mirror / Atom feed
* Trouble with doubly-linked, circular list using lazy evaluation
@ 2006-10-25  1:46 Denis Bueno
  2006-10-25  9:01 ` [Caml-list] " Richard Jones
  2006-11-17 15:02 ` Damien Doligez
  0 siblings, 2 replies; 5+ messages in thread
From: Denis Bueno @ 2006-10-25  1:46 UTC (permalink / raw)
  To: OCaml Mailing List

I get a "Bus error" when running a unit test on a doubly-linked
circular list (of length 2). A self-contained test case is included
[1]. I have 8 fields in a record which includes two left & right
pointers (not ref types).

I am running a PowerMac G5 2.5GHz (uname -a: Darwin ford.local 8.8.0
Darwin Kernel Version 8.8.0: Fri Sep  8 17:18:57 PDT 2006;
root:xnu-792.12.6.obj~1/RELEASE_PPC Power Macintosh powerpc) and
ocaml 3.09.3.

Interestingly, if I remove a field (such as the mark field), the test
case succeeds.

Anyone have any idea why I have a problem, or how to solve it?

-Denis

[1]
Compile with:
ocamlc.opt -w FUE -I .		 -g	 -c ll_test.ml
ocamlc.opt -o ll_test -w FUE -I .		 -g	  ll_test.cmo


Source:
(* Self-contained test case for doubly-linked list troubles. *)
type 'a dllnode = {key : int;
                   right : 'a dllnode Lazy.t;
                   left : 'a dllnode Lazy.t;
                   parent : 'a dllnode option;
                   child : 'a dllnode option;
                   mark : bool;
                   degree : int;
                   data : 'a;
};;

let rec empty = {key = 0; left = lazy empty; right = lazy empty;
parent = None; child = None; mark = false; degree = 0; data = 0};;

let make_proper_node data =
  let rec l = {empty with left = lazy l; right = lazy l; data = data} in
    l

and node_ll_add llnode new_node =
  (* ... <-> llnode <-> former_right <-> ...

     =>

     ... <-> llnode <-> new_node <-> former_right <-> ...
  *)
  if Lazy.force llnode.right == llnode
    (* there is only 1 node in this linked list. *)
  then
    let rec new_node' = {new_node with right = lazy other; left = lazy other}
    and other = {llnode with right = lazy new_node'; left = lazy new_node'} in
      new_node'

  else
    let former_right = Lazy.force llnode.right in
    let rec new_node' =
      {new_node with
        right = lazy {former_right with left = lazy new_node'};
        left = lazy {llnode with right = lazy new_node'}} in
      new_node'
;;


let test () =
  let node = make_proper_node 0 in
  let _ = assert (Lazy.force node.left == Lazy.force node.right) in
  let _ = assert (Lazy.force node.left == node) in
  let _ = assert (node.data = 0) in
  let node = node_ll_add node (make_proper_node 1) in
  let _ = assert ((Lazy.force node.left).data = 0) in
  let _ = assert (Lazy.force node.left == Lazy.force node.right) in
  let _ = assert (not (Lazy.force node.left == node)) in
  let _ = assert (Lazy.force (Lazy.force node.left).right == node) in
  let _ = assert (Lazy.force (Lazy.force node.right).left == node) in
  let _ = assert (Lazy.force (Lazy.force node.right).right == node) in
  let _ = assert (Lazy.force (Lazy.force node.left).left == node) in
    ()
;;

test ();;


^ permalink raw reply	[flat|nested] 5+ messages in thread
end of thread, other threads:[~2006-11-17 15:01 UTC | newest]

Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2006-10-25  1:46 Trouble with doubly-linked, circular list using lazy evaluation Denis Bueno
2006-10-25  9:01 ` [Caml-list] " Richard Jones
2006-10-25 10:59   ` Denis Bueno
2006-10-25 12:10     ` skaller
2006-11-17 15:02 ` Damien Doligez

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox