- Many thanks for the suggestion. I did see however that recursion is a mixed blessing, comparing the iterative and the recursive versions. Is there any way to predict or circumvent a stack overflow in this case?

let summation a b =

let rec sum x =

if (x = a) then a

else x + (sum (x - 1)) in

sum b;;

versus

let i_summation a b =

let step = ref 0 in

for i = a to b do

step := !step + i

done;

!step;;

when calculating summation 1 1000000

-: Stack overflow during evaluation (looping recursion?).

but i_summation 1 1000000

-: int = 363189984

I was *hoping* the stack overflow would coincide with exceeding the value of int 2^^31. Are we safe in believing the value int = 363189984 to be correct then? Do we need to add another statement in the recursive version that if b > 262,000 then print_string "Cannot proceed with this value, stack overflow may result!" else compute_the_value &etc. Something along the lines

let summation a b =

let rec sum x =

if (x = a) then a

else x + (sum (x - 1)) in

if not (b >= 262000) then sum b else print_string "Not possible";;

Avec de sincères amitiés

bj

--- En date de : Sam 1.8.09, Yang Ye <leafyoung@...> a écrit :

De: Yang Ye <leafyoung@...>

Objet: Re: "ocaml_beginners"::[] Re: how can I convert an iterative to a recursive summation?

À: ocaml_beginners@yahoogroups.com

Date: Samedi 1 Août 2009, 12h56

Hi,

sum := !sum + (b - 1) is of type unit so a is inferred as unit as well. The

second function evaluates as

int -> unit -> int.

the correct recursive version is

let sum a b = let rec sum2 x = if (x = a) then a else x + (sum2 (x-1)) in

sum2 b ;;

Regards,

Yang Ye

On Sat, Aug 1, 2009 at 2:07 AM, Bill James <w_a_x_man@yahoo. com> wrote:

>

>

> --- In ocaml_beginners@ yahoogroups. com <ocaml_beginners% 40yahoogroups. com>,

> Jaques Bertrand <bertrandjaques@ ...> wrote:

> >

> >

> > Hi,

> >

> > I was trying to code a function that computes a summation given a lower

> and an upper boundry, but for some reason, I am not able to find a recursive

> solution. My instincts tell me that a recursive solution would be preferred

> in OCaml. For example, given 1 and 5, a sum of all the integers between 1

> and 5 is 15. I think the recursive step would be (n-1) or (n+1), but I keep

> missing the guard component.

> >

> > Thus far I came up with the iterative solution:

> >

> > let summation a b =

> > let step = ref 0 in

> > for i = a to b do

> > step := !step + i

> > done;

> > !step;;

> >

> > summation 1 5;;

> > :- int = 15 and

> > summation 3 8;;

> > :- int = 33

> >

> > let summation a b =

> > let rec sum = ref 0 in

> > if b - 1 = 0 then a

> > else sum := !sum + (b - 1);;

> > # summation 1 5;;

> > -: Error: This expression has type int but an expression was expected of

> type unit.

> >

> > Regards,

> >

> > bj

> >

>

> Just for fun:

>

> (* Make array of ints from a to z, inclusive. *)

> let ( -- ) a z = Array.init (z-a+1) (fun i -> i + a) ;;

>

> let summation a b =

> Array.fold_left (fun x y -> x+y) 0 (a -- b) ;;

>

> print_int (summation 1 5)

>

>

>

--

Regards,

Yang Ye

[Non-text portions of this message have been removed] - On Sunday 09 August 2009 15:34:02 Jaques Bertrand wrote:
> Many thanks for the suggestion. I did see however that recursion is a

You need to read up on tail calls and tail call elimination or tail call

> mixed blessing, comparing the iterative and the recursive versions. Is

> there any way to predict or circumvent a stack overflow in this case?

>

> let summation a b =

> let rec sum x =

> if (x = a) then a

> else x + (sum (x - 1)) in

> sum b;;

>

> versus

>

> let i_summation a b =

> let step = ref 0 in

> for i = a to b do

> step := !step + i

> done;

> !step;;

>

> when calculating summation 1 1000000

> -: Stack overflow during evaluation (looping recursion?).

> but i_summation 1 1000000

> -: int = 363189984

optimization (TCO) or proper tail recursion.

Essentially, you should rewrite your code such that the recursive calls are in

tail position to ensure that stack consumption is bounded.

In this case, use an accumulator:

# let rec sum ?(t=0) a b =

if a=b then t+a else

sum ~t:(t+a) (a+1) b;;

val sum : ?t:int -> int -> int -> int = <fun>

# sum 1 1000000;;

- : int = -363189984

> I was *hoping* the stack overflow would coincide with exceeding the value

No. The stack is much smaller than that and the number of non-tail calls that

> of int 2^^31.

can be made before you run out of stack is also a function of the size of

each stack frame.

> Are we safe in believing the value int = 363189984 to be

Depends what you mean by "correct". I suspect it is not the answer you were

> correct then?

hoping for.

> Do we need to add another statement in the recursive version

No, that is a really bad idea. You do not know when a stack overflow will

> that if b > 262,000 then print_string "Cannot proceed with this value,

> stack overflow may result!" else compute_the_value &etc. Something along

> the lines

>

> let summation a b =

> let rec sum x =

> if (x = a) then a

> else x + (sum (x - 1)) in

> if not (b >= 262000) then sum b else print_string "Not possible";;

occur but can safely assume that 1,000 non-tail recursions will work.

Therefore, you can use constant or O(log n) for machine-precision "n"

non-tail recursions.

--

Dr Jon Harrop, Flying Frog Consultancy Ltd.

http://www.ffconsultancy.com/?e - Hi,Would you be so kind and elaborate on the use of optional parameter to create an accumulator in the syntax

let rec sum ?( t = 0 ) a b =

if a = b then t + a

else

sum ~t:( t + a ) ( a + 1 ) b;;

Although we do not get a stack overflow, the negative sign in the result does give a hint that something is amiss. For example,sum 1 1000000 (* million *)-: int = -363189984whereassum 1 1000000000 (* billion *)(* after 2-3 min pause *)-: int = -243309312but it could not possibly be smaller than the first value and I suspect we do not see all the digits in the answer inspite of the fact we do not get an overflow error.Even an iterative solution fails us, for this we need big_int and we cannot count the stars in our galaxy using a summation.With kindest regards,bj

--- En date de : Dim 9.8.09, Jon Harrop <jon@...> a écrit :

De: Jon Harrop <jon@...>

Objet: Re: "ocaml_beginners"::[] Re: how can I convert an iterative to a recursive summation?

À: ocaml_beginners@yahoogroups.com

Date: Dimanche 9 Août 2009, 16h13

On Sunday 09 August 2009 15:34:02 Jaques Bertrand wrote:

> Many thanks for the suggestion. I did see however that recursion is a

> mixed blessing, comparing the iterative and the recursive versions. Is

> there any way to predict or circumvent a stack overflow in this case?

>

> let summation a b =

> let rec sum x =

> if (x = a) then a

> else x + (sum (x - 1)) in

> sum b;;

>

> versus

>

> let i_summation a b =

> let step = ref 0 in

> for i = a to b do

> step := !step + i

> done;

> !step;;

>

> when calculating summation 1 1000000

> -: Stack overflow during evaluation (looping recursion?).

> but i_summation 1 1000000

> -: int = 363189984

You need to read up on tail calls and tail call elimination or tail call

optimization (TCO) or proper tail recursion.

Essentially, you should rewrite your code such that the recursive calls are in

tail position to ensure that stack consumption is bounded.

In this case, use an accumulator:

# let rec sum ?(t=0) a b =

if a=b then t+a else

sum ~t:(t+a) (a+1) b;;

val sum : ?t:int -> int -> int -> int = <fun>

# sum 1 1000000;;

- : int = -363189984

> I was *hoping* the stack overflow would coincide with exceeding the value

> of int 2^^31.

No. The stack is much smaller than that and the number of non-tail calls that

can be made before you run out of stack is also a function of the size of

each stack frame.

> Are we safe in believing the value int = 363189984 to be

> correct then?

Depends what you mean by "correct". I suspect it is not the answer you were

hoping for.

> Do we need to add another statement in the recursive version

> that if b > 262,000 then print_string "Cannot proceed with this value,

> stack overflow may result!" else compute_the_ value &etc. Something along

> the lines

>

> let summation a b =

> let rec sum x =

> if (x = a) then a

> else x + (sum (x - 1)) in

> if not (b >= 262000) then sum b else print_string "Not possible";;

No, that is a really bad idea. You do not know when a stack overflow will

occur but can safely assume that 1,000 non-tail recursions will work.

Therefore, you can use constant or O(log n) for machine-precision "n"

non-tail recursions.

--

Dr Jon Harrop, Flying Frog Consultancy Ltd.

http://www.ffconsul tancy.com/ ?e

[Non-text portions of this message have been removed] - On Monday 10 August 2009 00:50:26 Jaques Bertrand wrote:
> Hi,Would you be so kind and elaborate on the use of optional parameter to

Sure. The optional parameter for the accumulator "t" is introduced with the ?

> create an accumulator in the syntax

> let rec sum ?( t = 0 ) a b =

> if a = b then t + a

> else

> sum ~t:( t + a ) ( a + 1 ) b;;

(t=...) syntax, giving it a name "t" and a default value. When the optional

argument is not given via an explicit it assumes the default value of zero,

e.g. in the external call to "sum". The internal recursive call explicitly

declares the first argument with the label "t" using the ~t: syntax.

In this case, I call the style an "implicit accumulator design pattern".

Optional arguments offer an elegant solution to many practical problems and

were described in detail in the "Labeled and Optional arguments" article

(April 2008) of the OCaml Journal:

http://ocamlnews.blogspot.com/2008/04/labeled-and-optional-arguments.html

--

Dr Jon Harrop, Flying Frog Consultancy Ltd.

http://www.ffconsultancy.com/?e