From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id OAA17497; Sun, 26 Aug 2001 14:24:49 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id OAA17443 for ; Sun, 26 Aug 2001 14:24:47 +0200 (MET DST) Received: from moutvdom00.kundenserver.de (moutvdom00.kundenserver.de [195.20.224.149]) by nez-perce.inria.fr (8.11.1/8.10.0) with ESMTP id f7QCOgn09946 for ; Sun, 26 Aug 2001 14:24:47 +0200 (MET DST) Received: from [195.20.224.204] (helo=mrvdom00.schlund.de) by moutvdom00.kundenserver.de with esmtp (Exim 2.12 #2) id 15ayy1-0004ad-00; Sun, 26 Aug 2001 14:24:41 +0200 Received: from drms-3e364b46.pool.mediaways.net ([62.54.75.70] helo=ice.gerd-stolpmann.de) by mrvdom00.schlund.de with esmtp (Exim 2.12 #2) id 15ayy0-0005rs-00; Sun, 26 Aug 2001 14:24:41 +0200 Received: from localhost (localhost [[UNIX: localhost]]) by ice.gerd-stolpmann.de (8.9.3/8.9.3) id OAA21751; Sun, 26 Aug 2001 14:23:53 +0200 From: Gerd Stolpmann Reply-To: info@gerd-stolpmann.de Organization: privat To: Al Christians , caml-list@inria.fr Subject: Re: [Caml-list] Queens examples Date: Sun, 26 Aug 2001 13:33:40 +0200 X-Mailer: KMail [version 1.0.28] Content-Type: text/plain References: <3B88A467.D16DD57D@easystreet.com> In-Reply-To: <3B88A467.D16DD57D@easystreet.com> MIME-Version: 1.0 Message-Id: <0108261423530A.02716@ice> Content-Transfer-Encoding: 8bit Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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