Trouble with doubly-linked, circular list using lazy evaluation

Trouble with doubly-linked, circular list using lazy evaluation

[Denis Bueno]

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 ();;

Re: [Caml-list] Trouble with doubly-linked, circular list using lazy evaluation

[Richard Jones]

On Tue, Oct 24, 2006 at 09:46:52PM -0400, Denis Bueno wrote:
> 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.

I can confirm a seg fault on OCaml 3.09.1, Linux/AMD64.  Have you
thought about filing a bug here: http://caml.inria.fr/mantis/main_page.php

Rich.

-- 
Richard Jones, CTO Merjis Ltd.
Merjis - web marketing and technology - http://merjis.com
Internet Marketing and AdWords courses - http://merjis.com/courses - NEW!
Merjis blog - http://blog.merjis.com - NEW!

Re: Re: [Caml-list] Trouble with doubly-linked, circular list using lazy evaluation

[Denis Bueno]

On 10/25/06, Richard Jones <rich@annexia.org> wrote:
> I can confirm a seg fault on OCaml 3.09.1, Linux/AMD64.  Have you
> thought about filing a bug here: http://caml.inria.fr/mantis/main_page.php

Reported. It's issue 0004141.

-Denis

Re: Re: [Caml-list] Trouble with doubly-linked, circular list using lazy evaluation

[skaller]

On Wed, 2006-10-25 at 06:59 -0400, Denis Bueno wrote:
> On 10/25/06, Richard Jones <rich@annexia.org> wrote:
> > I can confirm a seg fault on OCaml 3.09.1, Linux/AMD64.  Have you
> > thought about filing a bug here: http://caml.inria.fr/mantis/main_page.php
> 
> Reported. It's issue 0004141.

Also 3.09.3+rc1 has the segfault linux/AMD64.

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net

Re: [Caml-list] Trouble with doubly-linked, circular list using lazy evaluation

[Damien Doligez]

On 2006-10-25, at 03:46, Denis Bueno wrote:

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

That was an interesting bug.  Thanks for reporting it.

It has nothing to do with lazy values: it's an interference between
"let rec" of values and an optimization in the implementation of
the { ... with ... } construct.

To work around the bug, you can remove all instances of

   let rec ... = { ... with ... }

(i.e. the "with" construct as the toplevel expression of a letrec-bound
variable) by expanding the "with" construct by hand.

I am fixing it in the 3.09 branch (3.09.4+dev1).

-- Damien