[Caml-list] Queens examples

[Caml-list] Queens examples

[Al Christians]

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.

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

My computer is WinNT 4.0, SP6 with 128MB of ram.  I am running the
from the binary distribution pcaml-3.02-win.exe.


Al Christians
-------------------
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

Re: [Caml-list] Queens examples

[Gerd Stolpmann]

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

Re: [Caml-list] Queens examples

[Laurent Chéno]

(* please excuse my poor english *)

Le dimanche 26 août 2001, à 01:33, Gerd Stolpmann a écrit :

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

You can avoid the stack problem by writing (still functionnaly) :

let concmap f l =
	let rec aux result = function
		| [] -> result
		| h :: t -> aux (f h result) t
	in aux [] (List.rev l) ;;

Of course, List.rev has been written with terminal recursion, like this :

let reverse l =
	let rec aux result = function
		| [] -> result
		| h :: t -> aux (h :: result) t
	in aux [] l ;;

(compare the two functions... !)

Best regards,

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

Re: [Caml-list] Queens examples

[Frank Atanassow]

Gerd Stolpmann wrote (on 26-08-01 13:33 +0200):
> 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.

First, stack allocation of activation frames is more usually a property of a
programming language implementation, than of the programming language itself.

Second, the last statement is false. For example, SML/NJ, Stackless Python and
undoubtedly some implementations of Scheme all allocate activation frames on
the heap (in order to support first-class continuations efficiently).

-- 
Frank Atanassow, Information & Computing Sciences, Utrecht University
Padualaan 14, PO Box 80.089, 3508 TB Utrecht, Netherlands
Tel +31 (030) 253-3261 Fax +31 (030) 251-379
-------------------
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

Re: [Caml-list] Queens examples

[Xavier Leroy]

> 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.
> Does OCaml often produce such errors?  Is there a trick to preventing
> these errors that was overlooked in writing these examples?

Just to complement the detailed replies already made on this list:
OCaml would happily grow the stack until all the available memory
(physical and virtual) is exhausted.  However, excessive stack
consumption is often the sign of a programming error (recursion that
misses the base case), and exhausting all the memory before reporting
it is not nice, so OCaml implements a soft limit on the size of the
stack.  By default, it's 1 megabyte, but it can be changed from the
command line (the CAMLRUNPARAM variable) or even from within the
program or the interactive system:

        Gc.set {(Gc.get()) with Gc.stack_limit = 4 * 1024 * 1024}

The above bumps the limit to 4 mega-words (16 mega-bytes), and is
enough to run the Queens example with size 12.

Hope this helps,

- Xavier Leroy
-------------------
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