Re: [Caml-list] Queens examples

[Gerd Stolpmann <info@gerd-stolpmann.de>]

On Sun, 26 Aug 2001, Al Christians wrote:
>I have downloaded the examples from 
>
>	http://caml.inria.fr/Examples/oc.tar.gz
>
>These look very nice and informative for a beginner, thanks very much,
>but ...
>
>Running the queens and queens_lazy basic examples in OCamlWin gives 
>a stack overflow with board size of 12 x 12.   The queens_lazy 
>example is set-up to do 12 x 12, so it crashes right out of the box.

The queens example is programmed in a heavily recursive way, so the program
needs lots of stack space. This is similar to other programming languages. For
example, look at the definition of concmap:

let rec concmap f = function
  | [] -> []
  | h :: t -> f h (concmap f t);;

The point is that the recursive call (concmap f t) occurs within an expression,
and the current execution environment must be saved on the stack before the
self-invocation such that it is still available when the containing expression
(f h (concmap f t)) is being evaluated. This is what all programming languages
do when recursive definitions are executed.

You can avoid that only by changing the algorithm, i.e. avoid concmap (and
perhaps filter_append). The simplest way is to make some parts of the program
imperative, because managing the stack effectively can be _very_ difficult for
purely functional programming. It is a very interesting feature of OCaml that
you can mix functional and imperative programming styles. For the queens
example, such a mixed-style solution is:

let find_solutions size =
  let line = interval 1 size in
  let rec gen n size =
    if n = 0 then [[]] else
      let pred_solutions = gen (n-1) size in
      let solutions = ref [] in
      List.iter
        (fun b ->
          let candidates = map (fun q -> q :: b) line in
          List.iter
            (fun candidate ->
              if ok candidate then 
                solutions := candidate :: !solutions)
            candidates
        )
      	pred_solutions;
      !solutions
  in
  gen size size;;

This solution avoids the ineffectiveness of concmap by iterating over the
solution sets using List.iter. It does only need constant stack space instead
of stack space growing with the number of solutions.

>Does OCaml often produce such errors?  Is there a trick to preventing
>these errors that was overlooked in writing these examples?

OCaml doesn't produce such errors if the programmer takes some care of the
stack. Of course, this requires some understanding of how the stack is used.

OCaml invites the programmer to use the functional features of the
language, and so the shortest ("just hacked") algorithm often has such
problems. But this is more an error of the programmer than an error of the
language.

Gerd
-- 
----------------------------------------------------------------------------
Gerd Stolpmann      Telefon: +49 6151 997705 (privat)
Viktoriastr. 45             
64293 Darmstadt     EMail:   gerd@gerd-stolpmann.de
Germany                     
----------------------------------------------------------------------------
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr