[Caml-list] Why List.map does not be implemented tail-recursively?

[Caml-list] Why List.map does not be implemented tail-recursively?

[Shuai Wang]

[-- Attachment #1: Type: text/plain, Size: 895 bytes --]

Hello list,


I am working on some stack_overflow exception in our recent project written
in OCaml
and eventually it turns out that this exception is thrown by List.map
function.

By seeing the source code of OCaml's List module
<https://code.ohloh.net/file?fid=P5Us_txNCMHIhpdfML6OZ8QN4Zs&cid=Jigg8RAfQdg&s=ocaml%20list.ml&pp=0&fp=305967&fe=ml&ff=1&filterChecked=true&mp=1&ml=1&me=1&md=1#L3>,
it seems that map function
does not be implemented tail-recursively:

let rec map f = function
    [] -> []
  | a::l -> let r = f a in r :: map f l



So my question is:

*Why would OCaml's implementation List.map like this?  *

In my humble option, it definitely should be written in a tail-recursive
way,
and it not, stack_overflow would be unavoidable.
For example in order to handle the exception,
I abandon the code using List.map and rewrite it into a tail-recursive help
function.

Best,
Shuai

[-- Attachment #2: Type: text/html, Size: 7798 bytes --]

Re: [Caml-list] Why List.map does not be implemented tail-recursively?

[Gabriel Scherer]

[-- Attachment #1: Type: text/plain, Size: 2356 bytes --]

The compiler library chose to keep it's implementation simple and clean, at
the cost of not being tail-recursive, and therefore unsuitable for large
lists. This is documented in the manual:
  http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html

> Some functions are flagged as not tail-recursive. A tail-recursive
function uses constant stack space, while a non-tail-recursive function
uses stack space proportional to the length of its list argument, which can
be a problem with very long lists.

>  List.map f [a1; ...; an] applies function f to a1, ..., an, and builds
the list [f a1; ...; f an] with the results returned by f. Not
tail-recursive.

Other libraries have made different design choices, so you can easily use a
different List module that provides tail-recursive operations. There are
several larger libraries, some (such as Batteries
http://batteries.forge.ocamlcore.org/ ) which directly extend the compiler
library, and are therefore usable as a drop-in replacement for it, some
others (such as Core
https://ocaml.janestreet.com/ocaml-core/111.28.00/doc/core/ ) which use
different conventions. They all provide tail-recursive mapping functions
suitable for use on long lists.

(Of course you can also simply replace `List.map f li` with `List.rev_map f
(List.rev li)` if you know `li` may be long.)

On Sun, Sep 28, 2014 at 9:31 PM, Shuai Wang <wangshuai901@gmail.com> wrote:

> Hello list,
>
>
> I am working on some stack_overflow exception in our recent project
> written in OCaml
> and eventually it turns out that this exception is thrown by List.map
> function.
>
> By seeing the source code of OCaml's List module
> <https://code.ohloh.net/file?fid=P5Us_txNCMHIhpdfML6OZ8QN4Zs&cid=Jigg8RAfQdg&s=ocaml%20list.ml&pp=0&fp=305967&fe=ml&ff=1&filterChecked=true&mp=1&ml=1&me=1&md=1#L3>,
> it seems that map function
> does not be implemented tail-recursively:
>
> let rec map f = function
>     [] -> []
>   | a::l -> let r = f a in r :: map f l
>
>
>
> So my question is:
>
> *Why would OCaml's implementation List.map like this?  *
>
> In my humble option, it definitely should be written in a tail-recursive
> way,
> and it not, stack_overflow would be unavoidable.
> For example in order to handle the exception,
> I abandon the code using List.map and rewrite it into a tail-recursive
> help function.
>
> Best,
> Shuai
>

[-- Attachment #2: Type: text/html, Size: 9985 bytes --]

Re: [Caml-list] Why List.map does not be implemented tail-recursively?

[Anthony Tavener]

[-- Attachment #1: Type: text/plain, Size: 1543 bytes --]

(Oh, Gabriel beat me to the punch, but I'll add my reply anyway.)

The standard library is a fairly minimal library of basic features. Not a
high-level full-featured library which helps you make good choices. :)

However, the documentation (in .mli files) is fairly clear about what is
tail-recursive or not. And there is rev_map:

val rev_map : ('a -> 'b) -> 'a list -> 'b list
(** [List.rev_map f l] gives the same result as
   {!List.rev}[ (]{!List.map}[ f l)], but is tail-recursive and
   more efficient. *)


On Sun, Sep 28, 2014 at 1:31 PM, Shuai Wang <wangshuai901@gmail.com> wrote:

> Hello list,
>
>
> I am working on some stack_overflow exception in our recent project
> written in OCaml
> and eventually it turns out that this exception is thrown by List.map
> function.
>
> By seeing the source code of OCaml's List module
> <https://code.ohloh.net/file?fid=P5Us_txNCMHIhpdfML6OZ8QN4Zs&cid=Jigg8RAfQdg&s=ocaml%20list.ml&pp=0&fp=305967&fe=ml&ff=1&filterChecked=true&mp=1&ml=1&me=1&md=1#L3>,
> it seems that map function
> does not be implemented tail-recursively:
>
> let rec map f = function
>     [] -> []
>   | a::l -> let r = f a in r :: map f l
>
>
>
> So my question is:
>
> *Why would OCaml's implementation List.map like this?  *
>
> In my humble option, it definitely should be written in a tail-recursive
> way,
> and it not, stack_overflow would be unavoidable.
> For example in order to handle the exception,
> I abandon the code using List.map and rewrite it into a tail-recursive
> help function.
>
> Best,
> Shuai
>

[-- Attachment #2: Type: text/html, Size: 8919 bytes --]

Re: [Caml-list] Why List.map does not be implemented tail-recursively?

[Goswin von Brederlow]

And I'll will do the same, reply anyway.

You can't write List.map tail recursive unless:

1) You use List.rev (List.rev_map fn list).

or

2) Use hacks to create a mutable list so you can grow it head to tail
instead of tail to head.

The fastest code seems to be when you do List.map recursively up to
some limit (say 1000 items) and return the remainder. Repeat and glue
the lists together into one large list using hacks.

MfG
	Mrvn

On Sun, Sep 28, 2014 at 01:45:41PM -0600, Anthony Tavener wrote:
> (Oh, Gabriel beat me to the punch, but I'll add my reply anyway.)
> 
> The standard library is a fairly minimal library of basic features. Not a
> high-level full-featured library which helps you make good choices. :)
> 
> However, the documentation (in .mli files) is fairly clear about what is
> tail-recursive or not. And there is rev_map:
> 
> val rev_map : ('a -> 'b) -> 'a list -> 'b list
> (** [List.rev_map f l] gives the same result as
>    {!List.rev}[ (]{!List.map}[ f l)], but is tail-recursive and
>    more efficient. *)
> 
> 
> On Sun, Sep 28, 2014 at 1:31 PM, Shuai Wang <wangshuai901@gmail.com> wrote:
> 
> > Hello list,
> >
> >
> > I am working on some stack_overflow exception in our recent project
> > written in OCaml
> > and eventually it turns out that this exception is thrown by List.map
> > function.
> >
> > By seeing the source code of OCaml's List module
> > <https://code.ohloh.net/file?fid=P5Us_txNCMHIhpdfML6OZ8QN4Zs&cid=Jigg8RAfQdg&s=ocaml%20list.ml&pp=0&fp=305967&fe=ml&ff=1&filterChecked=true&mp=1&ml=1&me=1&md=1#L3>,
> > it seems that map function
> > does not be implemented tail-recursively:
> >
> > let rec map f = function
> >     [] -> []
> >   | a::l -> let r = f a in r :: map f l
> >
> >
> >
> > So my question is:
> >
> > *Why would OCaml's implementation List.map like this?  *
> >
> > In my humble option, it definitely should be written in a tail-recursive
> > way,
> > and it not, stack_overflow would be unavoidable.
> > For example in order to handle the exception,
> > I abandon the code using List.map and rewrite it into a tail-recursive
> > help function.
> >
> > Best,
> > Shuai

Re: [Caml-list] Why List.map does not be implemented tail-recursively?

[Pierre Chambart]

On 29/09/2014 14:08, Goswin von Brederlow wrote:
> And I'll will do the same, reply anyway.
>
> You can't write List.map tail recursive unless:
>
> 1) You use List.rev (List.rev_map fn list).
>
> or
>
> 2) Use hacks to create a mutable list so you can grow it head to tail
> instead of tail to head.
>
> The fastest code seems to be when you do List.map recursively up to
> some limit (say 1000 items) and return the remainder. Repeat and glue
> the lists together into one large list using hacks.
>
> MfG
> 	Mrvn
>
Please, don't do that hack ! The compiler assumes immutable data are not
mutated and optimise knowing that.
-- 
Pierre

Re: [Caml-list] Why List.map does not be implemented tail-recursively?

[Yaron Minsky]

Agreed.  To be clear, there's a "hack" in Core_kernel's List module
that does more or less what is described, but the gluing together
isn't hacky, i.e., uses no Obj.magic and no mutation.  It's both fast
for short lists and doesn't blow the stack for long lists.

y

On Mon, Sep 29, 2014 at 10:02 AM, Pierre Chambart
<pierre.chambart@laposte.net> wrote:
> On 29/09/2014 14:08, Goswin von Brederlow wrote:
>> And I'll will do the same, reply anyway.
>>
>> You can't write List.map tail recursive unless:
>>
>> 1) You use List.rev (List.rev_map fn list).
>>
>> or
>>
>> 2) Use hacks to create a mutable list so you can grow it head to tail
>> instead of tail to head.
>>
>> The fastest code seems to be when you do List.map recursively up to
>> some limit (say 1000 items) and return the remainder. Repeat and glue
>> the lists together into one large list using hacks.
>>
>> MfG
>>       Mrvn
>>
> Please, don't do that hack ! The compiler assumes immutable data are not
> mutated and optimise knowing that.
> --
> Pierre
>
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs

Re: [Caml-list] Why List.map does not be implemented tail-recursively?

[Gabriel Scherer]

[-- Attachment #1: Type: text/plain, Size: 2033 bytes --]

>
> Please, don't do that hack ! The compiler assumes immutable data are not
> mutated and optimise knowing that.
>

My understanding was that it is unsafe to Obj.magic an immutable data
structure into a mutable one (one mental model is that immutable data
might be allocated in read-only memory, although that's not what the
current implementation does), but that on the contrary it is safe to
Obj.magic a mutable data-structure into an immutable one. The
Obj.magic-using code for List.map, implemented in Extlib and inherited by
Batteries, is careful to use an unsafe cast in exactly the second
situation. This is a feature that other languages (eg. Mezzo) safely
provide.

If this last technique became invalid because of compiler optimization in
the future, that would need to be clearly exposed and justified. Could you
confirm that this is not the case today?

(I think this is also the way immutable recursive value work, with a
tying-the-knot mutation followed by a conceptual "freeze" of the resulting
structure.)

On Mon, Sep 29, 2014 at 4:02 PM, Pierre Chambart <
pierre.chambart@laposte.net> wrote:

> On 29/09/2014 14:08, Goswin von Brederlow wrote:
> > And I'll will do the same, reply anyway.
> >
> > You can't write List.map tail recursive unless:
> >
> > 1) You use List.rev (List.rev_map fn list).
> >
> > or
> >
> > 2) Use hacks to create a mutable list so you can grow it head to tail
> > instead of tail to head.
> >
> > The fastest code seems to be when you do List.map recursively up to
> > some limit (say 1000 items) and return the remainder. Repeat and glue
> > the lists together into one large list using hacks.
> >
> > MfG
> >       Mrvn
> >
> Please, don't do that hack ! The compiler assumes immutable data are not
> mutated and optimise knowing that.
> --
> Pierre
>
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>

[-- Attachment #2: Type: text/html, Size: 3064 bytes --]

Re: [Caml-list] Why List.map does not be implemented tail-recursively?

[Goswin von Brederlow]

On Mon, Sep 29, 2014 at 04:02:11PM +0200, Pierre Chambart wrote:
> On 29/09/2014 14:08, Goswin von Brederlow wrote:
> > And I'll will do the same, reply anyway.
> >
> > You can't write List.map tail recursive unless:
> >
> > 1) You use List.rev (List.rev_map fn list).
> >
> > or
> >
> > 2) Use hacks to create a mutable list so you can grow it head to tail
> > instead of tail to head.
> >
> > The fastest code seems to be when you do List.map recursively up to
> > some limit (say 1000 items) and return the remainder. Repeat and glue
> > the lists together into one large list using hacks.
> >
> > MfG
> > 	Mrvn
> >
> Please, don't do that hack ! The compiler assumes immutable data are not
> mutated and optimise knowing that.
> -- 
> Pierre
> 

I didn't describe the hack. The hack would be to build the result as
mutable list (so the compiler uses write barriers when mutating and
such). But you only mutate once every 1000 items so the cost is
minimal. And at the end you cast the mutable list to an immutable list
(the actual list type).

While still a huge hack I believe going from mutable to immutable is
safe.

MfG
	Goswin

Re: [Caml-list] Why List.map does not be implemented

[oleg]

Gabriel Scherer wrote
> it is safe to Obj.magic a mutable data-structure into an immutable
> one. The Obj.magic-using code for List.map, implemented in Extlib and
> inherited by Batteries, is careful to use an unsafe cast in exactly
> the second situation. This is a feature that other languages
> (eg. Mezzo) safely provide.

Let me relay a short anecdote about the List.map function in
Batteries. Once I received a message from a person who was using the
Hansei library of probabilistic programming. He reported a problem:
his program produced clearly wrong results. He even traced the problem
to the function 'List.map' -- saying that if he wrote List.map himself,
the problem disappeared. I was initially puzzled: how one can possibly
mis-write List.map. I asked for more details and he said that he was
using Batteries. That gave me a hunch: I went to the Battery
repository to look at the source code and found what I expected --
mutation. In probabilistic programs, mutation has to be done
carefully. Mutation to the global heap forces correlation on what
should be independent ``possible worlds''. Mutation has to be done
with world-local heaps, which Hansei provides for that purpose. There
are times when hidden optimizations come to bite us. 

I guess in Mezzo I would have seen from the type that a mutation is
performed, and would have avoided the optimized Map (or the type
checker would make me avoid it).

Re: [Caml-list] Why List.map does not be implemented

[Gabriel Scherer]

[-- Attachment #1: Type: text/plain, Size: 2337 bytes --]

That is an extremely interesting story that I would like to understand
better. Which pointers would you recommend to read more about mutation in
HANSEI?

My intuition would be that the mutation should not be observable in this
case, as it is only done on "private" data that the List.map function
allocate, owns, and which never escapes in its immutable form. While I
understand why mutating global data is an observable side-effect that can
play badly with any form of backtracking/probabilistic monad, I do not have
any intuition about why mutating a privately-owned heap fragment would
perturb the system. If I was pressed to make an hypothesis (while not
knowing the system), I would guess that this is because of an
implementation detail of HANSEI, not because of its actual semantic
requirements.

On Tue, Sep 30, 2014 at 10:46 AM, <oleg@okmij.org> wrote:

>
> Gabriel Scherer wrote
> > it is safe to Obj.magic a mutable data-structure into an immutable
> > one. The Obj.magic-using code for List.map, implemented in Extlib and
> > inherited by Batteries, is careful to use an unsafe cast in exactly
> > the second situation. This is a feature that other languages
> > (eg. Mezzo) safely provide.
>
> Let me relay a short anecdote about the List.map function in
> Batteries. Once I received a message from a person who was using the
> Hansei library of probabilistic programming. He reported a problem:
> his program produced clearly wrong results. He even traced the problem
> to the function 'List.map' -- saying that if he wrote List.map himself,
> the problem disappeared. I was initially puzzled: how one can possibly
> mis-write List.map. I asked for more details and he said that he was
> using Batteries. That gave me a hunch: I went to the Battery
> repository to look at the source code and found what I expected --
> mutation. In probabilistic programs, mutation has to be done
> carefully. Mutation to the global heap forces correlation on what
> should be independent ``possible worlds''. Mutation has to be done
> with world-local heaps, which Hansei provides for that purpose. There
> are times when hidden optimizations come to bite us.
>
> I guess in Mezzo I would have seen from the type that a mutation is
> performed, and would have avoided the optimized Map (or the type
> checker would make me avoid it).
>
>

[-- Attachment #2: Type: text/html, Size: 2775 bytes --]

Re: [Caml-list] Why List.map does not be implemented

[oleg]

Gabriel Scherer wrote
> My intuition would be that the mutation should not be observable in this
> case, as it is only done on "private" data that the List.map function
> allocate, owns, and which never escapes in its immutable form.

Let me explain, on the example of the simplest Hansei function
        val flip : float -> bool
that flips (a possibly unfair) coin; flip 0.5 flips the fair coin.
A good way to understand the meaning of this function is to take the
frequentist approach. There are two ways the function call (flip 0.5)
can return: it can return with true or with false. There are total two
choices, in one of them the function returns true, in another
false. So, the probability of returning true is 1/2. In general, the
complete distribution -- which is the meaning of the program 
(flip 0.5) -- is as follows

# exact_reify (fun () -> flip 0.5);;
- : bool Ptypes.pV = [(0.5, Ptypes.V true); (0.5, Ptypes.V false)]

which is what Hansei computes. Let's take a more complex example,
closer to the topic: two independent coin flips

# let model () = List.map flip [0.5; 0.5]
val model : unit -> bool list = <fun>

# exact_reify model;;
- : bool list Ptypes.pV =
[(0.25, Ptypes.V [true; true]); (0.25, Ptypes.V [true; false]);
 (0.25, Ptypes.V [false; true]); (0.25, Ptypes.V [false; false])]

The result correctly tells that there are four possible choices.

Let us consider the function map from the Batteries. After desugaring,
it has the following form

type 'a mut_list = {
    hd: 'a;
    mutable tl: 'a list
  }

let map : ('a -> 'b) -> 'a list -> 'b list = fun f -> function
  | [] -> []
  | h :: t ->
      let rec loop dst = function
        | [] -> ()
        | h :: t ->
            let cell = {hd = f h; tl = []} in
            dst.tl <- Obj.magic cell;
            loop cell t
      in
      let r = {hd = f h; tl = []} in
      loop r t;
      Obj.magic r

Using this function, we obtain

# let model1 () = map flip [0.5; 0.5]
val model1 : unit -> bool list = <fun>

# exact_reify model1
- : bool list Ptypes.pV =
[(0.5, Ptypes.V [true; false]); (0.5, Ptypes.V [false; false])]

Something went wrong, didn't it? Where are the other two possible
choices -- with true for the second flip -- for the list of two
independent coin flips?

To understand the problem, let us recall the main principle stated
earlier: ``There are two ways the function call (flip 0.5)
can return: it can return with true or with false.'' That is, the
function call (flip 0.5) returns *twice*. Therefore, the call (f h)
in the let cell statement returns twice. Therefore, the assignment
            dst.tl <- Obj.magic cell;
will be executed twice. And the second execution of that assignment
will be with a different cell, which will override and destroy the
result of the first assignment. That is how the "true" choices became
lost.

Re: [Caml-list] Why List.map does not be implemented

[Gerd Stolpmann]

[-- Attachment #1: Type: text/plain, Size: 1741 bytes --]

Am Mittwoch, den 01.10.2014, 06:29 -0400 schrieb oleg@okmij.org:
> To understand the problem, let us recall the main principle stated
> earlier: ``There are two ways the function call (flip 0.5)
> can return: it can return with true or with false.'' That is, the
> function call (flip 0.5) returns *twice*. Therefore, the call (f h)
> in the let cell statement returns twice. Therefore, the assignment
>             dst.tl <- Obj.magic cell;
> will be executed twice. And the second execution of that assignment
> will be with a different cell, which will override and destroy the
> result of the first assignment. That is how the "true" choices became
> lost.

IMHO this is irrelevant for the normal OCaml evaluation regime. The
standard interpretation of a type 'a -> 'b is that it returns only once.
There is no alternate local world. I don't know what Hansei is doing to
get this effect, but it looks like it uses continuations, STM, or some
other technique to checkpoint some state and restart from there. This
technique is obviously not taking local state into account (which would
also have to be duplicated), but this is a limitation of this technique.
I don't think this is a valid argument against using hidden local state.
It's more an argument that if you use such checkpointing techniques, you
need to be extremely careful.

Gerd

> 
> 
> 

-- 
------------------------------------------------------------
Gerd Stolpmann, Darmstadt, Germany    gerd@gerd-stolpmann.de
My OCaml site:          http://www.camlcity.org
Contact details:        http://www.camlcity.org/contact.html
Company homepage:       http://www.gerd-stolpmann.de
------------------------------------------------------------


[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 473 bytes --]

Re: [Caml-list] Why List.map does not be implemented tail-recursively?

[Stephen Dolan]

On Mon, Sep 29, 2014 at 10:00 PM, Gabriel Scherer
<gabriel.scherer@gmail.com> wrote:
>> Please, don't do that hack ! The compiler assumes immutable data are not
>> mutated and optimise knowing that.
>
> My understanding was that it is unsafe to Obj.magic an immutable data
> structure into a mutable one (one mental model is that immutable data  might
> be allocated in read-only memory, although that's not what the current
> implementation does), but that on the contrary it is safe to Obj.magic a
> mutable data-structure into an immutable one. The Obj.magic-using code for
> List.map, implemented in Extlib and inherited by Batteries, is careful to
> use an unsafe cast in exactly the second situation. This is a feature that
> other languages (eg. Mezzo) safely provide.

This trick is unsound in our implementation of multicore OCaml: the
system assumes that immutable objects only point to older objects, and
thus that a shared immutable object cannot point to a private
immutable object. This can be hacked around (we have a similar hack
for recursive immutable objects), but the point is that such tricks
are fragile and depend on very implementation-specific behaviour.

Even in single-threaded OCaml, this trick is broken by quite
reasonable compiler optimisations (although not ones that OCaml does
today). For instance, if ocamlopt were to perform alias analysis and
optimise based on the results, the first thing the alias analyser
would do is conclude that references to immutable and mutable fields
do not alias. This would allow it to swap the order of references to
the immutable and mutable fields, and after inlining would mean that
the cons cell is read before it is initialised.

Stephen

Re: [Caml-list] Why List.map does not be implemented

[Gabriel Scherer]

During a discussion of Tail-Recursion Modulo Cons with Frédéric Bour,
I had an amusing idea of how to fix that problem pointed out by Oleg.
The idea is that we can detect at mutation time whether non-linear
control effect happened, and in that case do a deep copy of the
partially-filled structure. It sounds slightly crazy but works
beautifully.

Here is the current implementation style of `map` in Batteries; it is
merely an abstraction over Oleg's code example above (the decision to
implement destination-passing style was not made by Batteries, but in
the former Extlib project, but the small abstraction layer is due to
François Bérenger as part of Batteries).

type 'a mut_list = {
  hd: 'a;
  mutable tl: 'a list
}
external inj : 'a mut_list -> 'a list = "%identity"

module Acc1 = struct
  let create x = { hd = x; tl = [] }

  let accum acc x =
    let cell = create x in
    acc.tl <- inj cell;
    cell

  let return head = inj head
end

let map_dst f = function
  | [] -> []
  | x :: xs ->
     let open Acc1 in
     let rec loop f acc = function
       | [] -> return acc
       | x :: xs ->
          loop f (accum acc (f x)) xs
     in
     let acc = create (f x) in
     loop f acc xs

`accum` performs a mutation and returns the new destination in which
to produce the rest of the list. This is destination-passing-style,
and can also be understood as a manual TRMC optimization. It can also
be read as a "snoc" operation (adding a new element to the tail of a
list): it is possible to look at map_dst and think it is a pure
implementation. This pure implementation is optimized using mutation
under the hood, assuming (Mezzo-style) that the "map" function is the
unique owner of the intermediate list, which can thus be
mutated-in-place (even using strong mutation turning its type from a
mutable value to an immutable one).

Oleg explains that non-linear use of control operators (calling a
captured (delimited) continuation several times) allows to observe
this mutation, which thus destroys the probability computation of
HANSEI. Another way to see this problem is that non-linear use of
continuations breaks the unique-ownership invariant justifying the
optimization.

Yet it is possible to dynamically detect when we do not uniquely own
the list anymore (a previous invocation of the current continuation
has already mutated it), by filling the yet-to-be-mutated holes with a
secret canary value (instead of []). An accumulator is "fresh"
(uniquely owned) when its tail is (physically) equal to the canary
value. If we notice a mutator is not fresh, we perform a deep copy of
the list (from the head to the accumulator) and start accumulating
again from this copy.

Here is the new implementation of "map" using an Acc2 module
implementing freshness-check and deep-copy (code at the end of this
mail):

let rec map_dst2 f = function
  | [] -> []
  | x :: xs ->
     let open Acc2 in
     (* precondition: acc is fresh *)
     let rec loop f head acc = function
       | [] -> return head acc
       | x :: xs ->
      let next = f x in
      (* control effects during (f x) may destroy freshness *)
      if fresh acc then loop f head (accum acc next) xs
      else begin
         let head, acc = copy head (inj acc) in
         (* fresh after copy *)
         loop f head (accum acc next) xs
      end
     in
     let head = create (f x) in
     (* head is fresh *)
     loop f head head xs

The code is slightly more verbose because the deep-copy iteration
needs to be passed both the current accumulator and the head of the
list (it wouldn't know where to copy from otherwise). Notice that the
fast path (in absence of non-linear control) only has an additional
freshness check. I benchmarked the two implementations and the
difference is negligible -- in particular, it does not perform any
additional allocation in the fast case.

This version works fine with HANSEI.

(I'm not claiming this implementation alone is what people should use
for List.map. It does not behave particularly well on small lists,
which is the most important thing for most use-cases. The only point
is that the destination-passing-style can be made to work with
non-linear control.)

Finally, here is the "protected" Acc module implementing canary-check
and deep copy:

module Acc2 = struct
  let rec canary = Obj.magic () :: canary

  let copy head limit =
    let rec copy li limit tail =
      match li with
        | [] -> assert false
        | hd::tl ->
           let cell = { hd; tl = canary } in
           tail.tl <- inj cell;
           if li == limit then cell
           else copy tl limit cell
    in
    let new_head = { hd = head.hd; tl = canary } in
    if inj head == limit then (new_head, new_head)
    else begin
      let tail = copy head.tl limit new_head in
      new_head, tail
    end

  let create x = { hd = x; tl = canary }

  let fresh acc = acc.tl == canary

  let accum acc x =
    let cell = { hd = x; tl = canary } in
    acc.tl <- inj cell;
    cell

  let return head acc =
    acc.tl <- [];
    inj head
end

Full source for this experiment is available here:
  https://www.gitorious.org/gasche-snippets/destination-passing-style-and-control-effects/source/HEAD:map.ml

On Wed, Oct 1, 2014 at 12:29 PM,  <oleg@okmij.org> wrote:
>
> Gabriel Scherer wrote
>> My intuition would be that the mutation should not be observable in this
>> case, as it is only done on "private" data that the List.map function
>> allocate, owns, and which never escapes in its immutable form.
>
> Let me explain, on the example of the simplest Hansei function
>         val flip : float -> bool
> that flips (a possibly unfair) coin; flip 0.5 flips the fair coin.
> A good way to understand the meaning of this function is to take the
> frequentist approach. There are two ways the function call (flip 0.5)
> can return: it can return with true or with false. There are total two
> choices, in one of them the function returns true, in another
> false. So, the probability of returning true is 1/2. In general, the
> complete distribution -- which is the meaning of the program
> (flip 0.5) -- is as follows
>
> # exact_reify (fun () -> flip 0.5);;
> - : bool Ptypes.pV = [(0.5, Ptypes.V true); (0.5, Ptypes.V false)]
>
> which is what Hansei computes. Let's take a more complex example,
> closer to the topic: two independent coin flips
>
> # let model () = List.map flip [0.5; 0.5]
> val model : unit -> bool list = <fun>
>
> # exact_reify model;;
> - : bool list Ptypes.pV =
> [(0.25, Ptypes.V [true; true]); (0.25, Ptypes.V [true; false]);
>  (0.25, Ptypes.V [false; true]); (0.25, Ptypes.V [false; false])]
>
> The result correctly tells that there are four possible choices.
>
> Let us consider the function map from the Batteries. After desugaring,
> it has the following form
>
> type 'a mut_list = {
>     hd: 'a;
>     mutable tl: 'a list
>   }
>
> let map : ('a -> 'b) -> 'a list -> 'b list = fun f -> function
>   | [] -> []
>   | h :: t ->
>       let rec loop dst = function
>         | [] -> ()
>         | h :: t ->
>             let cell = {hd = f h; tl = []} in
>             dst.tl <- Obj.magic cell;
>             loop cell t
>       in
>       let r = {hd = f h; tl = []} in
>       loop r t;
>       Obj.magic r
>
> Using this function, we obtain
>
> # let model1 () = map flip [0.5; 0.5]
> val model1 : unit -> bool list = <fun>
>
> # exact_reify model1
> - : bool list Ptypes.pV =
> [(0.5, Ptypes.V [true; false]); (0.5, Ptypes.V [false; false])]
>
> Something went wrong, didn't it? Where are the other two possible
> choices -- with true for the second flip -- for the list of two
> independent coin flips?
>
> To understand the problem, let us recall the main principle stated
> earlier: ``There are two ways the function call (flip 0.5)
> can return: it can return with true or with false.'' That is, the
> function call (flip 0.5) returns *twice*. Therefore, the call (f h)
> in the let cell statement returns twice. Therefore, the assignment
>             dst.tl <- Obj.magic cell;
> will be executed twice. And the second execution of that assignment
> will be with a different cell, which will override and destroy the
> result of the first assignment. That is how the "true" choices became
> lost.
>
>
>

RE: [Caml-list] Why List.map does not be implemented tail-recursively?

[Jon Harrop]

What happens when the first allocation in the creation of a cyclic immutable structure incurs a minor collection?

let rec xs = 0::ys and ys = 1::xs

-----Original Message-----
From: stedolan@stedolan.net [mailto:stedolan@stedolan.net] On Behalf Of Stephen Dolan
Sent: 02 October 2014 11:10
To: Gabriel Scherer
Cc: Pierre Chambart; Goswin von Brederlow; caml users
Subject: Re: [Caml-list] Why List.map does not be implemented tail-recursively?

On Mon, Sep 29, 2014 at 10:00 PM, Gabriel Scherer <gabriel.scherer@gmail.com> wrote:
>> Please, don't do that hack ! The compiler assumes immutable data are 
>> not mutated and optimise knowing that.
>
> My understanding was that it is unsafe to Obj.magic an immutable data 
> structure into a mutable one (one mental model is that immutable data  
> might be allocated in read-only memory, although that's not what the 
> current implementation does), but that on the contrary it is safe to 
> Obj.magic a mutable data-structure into an immutable one. The 
> Obj.magic-using code for List.map, implemented in Extlib and inherited 
> by Batteries, is careful to use an unsafe cast in exactly the second 
> situation. This is a feature that other languages (eg. Mezzo) safely provide.

This trick is unsound in our implementation of multicore OCaml: the system assumes that immutable objects only point to older objects, and thus that a shared immutable object cannot point to a private immutable object. This can be hacked around (we have a similar hack for recursive immutable objects), but the point is that such tricks are fragile and depend on very implementation-specific behaviour.

Even in single-threaded OCaml, this trick is broken by quite reasonable compiler optimisations (although not ones that OCaml does today). For instance, if ocamlopt were to perform alias analysis and optimise based on the results, the first thing the alias analyser would do is conclude that references to immutable and mutable fields do not alias. This would allow it to swap the order of references to the immutable and mutable fields, and after inlining would mean that the cons cell is read before it is initialised.

Stephen

--
Caml-list mailing list.  Subscription management and archives:
https://sympa.inria.fr/sympa/arc/caml-list
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs

Re: [Caml-list] Why List.map does not be implemented tail-recursively?

[Stephen Dolan]

On Mon, Jun 1, 2015 at 1:02 PM, Jon Harrop <jon@ffconsultancy.com> wrote:
> What happens when the first allocation in the creation of a cyclic immutable structure incurs a minor collection?
>
> let rec xs = 0::ys and ys = 1::xs

Such allocations are handled specially. Essentially, it boils down to
having a write barrier on the final mutation that ties the knot on the
cyclic data structure. This isn't multicore-specific: see
caml_alloc_dummy and caml_update_dummy in byterun/alloc.c for the gory
details.

In multicore, this mutation needs to promote (copy to the shared heap)
the cyclic data structure if the head node has already been collected.

Stephen

Re: [Caml-list] Why List.map does not be implemented tail-recursively?

[Goswin von Brederlow]

On Tue, Jun 02, 2015 at 01:04:46PM +0100, Stephen Dolan wrote:
> On Mon, Jun 1, 2015 at 1:02 PM, Jon Harrop <jon@ffconsultancy.com> wrote:
> > What happens when the first allocation in the creation of a cyclic immutable structure incurs a minor collection?
> >
> > let rec xs = 0::ys and ys = 1::xs
> 
> Such allocations are handled specially. Essentially, it boils down to
> having a write barrier on the final mutation that ties the knot on the
> cyclic data structure. This isn't multicore-specific: see
> caml_alloc_dummy and caml_update_dummy in byterun/alloc.c for the gory
> details.
> 
> In multicore, this mutation needs to promote (copy to the shared heap)
> the cyclic data structure if the head node has already been collected.
> 
> Stephen

I believe ocaml already optimizes this into a single allocation for
both objects. So there can't be a GC run between them. And even if
there is, both xs and ys are alive in the local stackframe and can not
be collected just yet.

MfG
	Goswin

Re: [Caml-list] Why List.map does not be implemented tail-recursively?

[Erkki Seppala]

Oop, of course the forward_order function doesn't work with these types
properly, but I prematurely sent the email thanks to having the same key
binding for compilation and sending mail :).

-- 
  _____________________________________________________________________
     / __// /__ ____  __               http://www.modeemi.fi/~flux/\   \
    / /_ / // // /\ \/ /                                            \  /
   /_/  /_/ \___/ /_/\_\@modeemi.fi                                  \/

Re: [Caml-list] Why List.map does not be implemented tail-recursively?

[Erkki Seppala]

Martin Jambon <martin.jambon@ens-lyon.org> writes:

> Unfortunately the practice obfuscates the source code. It makes it
> tricky to add or remove an operation in the chain, and overall it's an
> unnecessary cognitive burden for anyone reading the code.

While I do agree with this, perhaps this kind of trick could be used
where it is crucial to eliminate excess reversing:

type forwards = Forwards
type backwards = Backwards

let reverse (order1, order2, list) = (order2, order1, List.rev list)

let mk list = (Forwards, Backwards, list)

let forward_order = function
  | Forwards, _, list -> list
  | _, Forwards, list -> List.rev list

let foo () = 
  let xs = mk [1; 2; 3] in
  let xs = reverse xs in
  let xs = reverse xs in
  (* let xs = reverse xs in*)
  let (Forwards, _, xs) = xs in xs
  (* forward_order xs*)
  (* or: let (Forwards, _, xs) = xs in xs for compile-time assertion *)
 
Or is it excessive?-)

-- 
  _____________________________________________________________________
     / __// /__ ____  __               http://www.modeemi.fi/~flux/\   \
    / /_ / // // /\ \/ /                                            \  /
   /_/  /_/ \___/ /_/\_\@modeemi.fi                                  \/

Re: [Caml-list] Why List.map does not be implemented tail-recursively?

[Martin Jambon]

On Sun 28 Sep 2014 09:09:48 PM PDT, Anthony Tavener wrote:
> A remark about the "reverse" list operations... I find that it often
> turns out that I'll have an even number of these reverse operations.
> So even if I need to maintain the final list order, it can be for free.
>
> For example, List.rev_map, followed by a List.rev_append... everything
> is tail-recursive without adding extra list-reversals, and the final
> order is maintained.

I also was obsessed with this when I started using OCaml a long time 
ago and was worried that list operations would double the cost of my 
algorithms (do the math: this is not how it works).

Unfortunately the practice obfuscates the source code. It makes it 
tricky to add or remove an operation in the chain, and overall it's an 
unnecessary cognitive burden for anyone reading the code. These 
optimizations should be done outside of the application code, either in 
the list library or by the compiler; most of the time they are 
absolutely needless anyway.


Martin

> On Sun, Sep 28, 2014 at 8:31 PM, Shuai Wang <wangshuai901@gmail.com
> <mailto:wangshuai901@gmail.com>> wrote:
>
>     Wow, List.rev_map f (List.rev li) looks very elegant, thank you
>     all for the helpful materials! I should definitely try Core lib soon.
>
>     I have been working on a binary program analysis project for over
>     half a year in OCaml, and it is really enjoyable to write OCaml code!
>     hope I can open source the analysis tool eventually and contribute
>     to the community :)
>
>     Best,
>     Shuai
>
>
>
>     On Sun, Sep 28, 2014 at 4:26 PM, Yaron Minsky
>     <yminsky@janestreet.com <mailto:yminsky@janestreet.com>> wrote:
>
>         Indeed, the implementation from that post did make it into
>         Core_kernel.  Here's the link:
>
>         https://github.com/janestreet/core_kernel/blob/release-112.01.00/lib/core_list.ml#L380
>
>         y
>
>         On Sun, Sep 28, 2014 at 3:45 PM, Malcolm Matalka
>         <mmatalka@gmail.com <mailto:mmatalka@gmail.com>> wrote:
>         > https://blogs.janestreet.com/optimizing-list-map/
>         >
>         > And from the horse's mouth:
>         >
>         >
>         https://groups.google.com/forum/#!msg/fa.caml/YaLYqkpn928/1jdo8a0K6AEJ
>         >
>         > Shuai Wang <wangshuai901@gmail.com
>         <mailto:wangshuai901@gmail.com>> writes:
>         >
>         >> Hello list,
>         >>
>         >>
>         >> I am working on some stack_overflow exception in our recent
>         project written
>         >> in OCaml
>         >> and eventually it turns out that this exception is thrown
>         by List.map
>         >> function.
>         >>
>         >> By seeing the source code of OCaml's List module
>         >>
>         <https://code.ohloh.net/file?fid=P5Us_txNCMHIhpdfML6OZ8QN4Zs&cid=Jigg8RAfQdg&s=ocaml%20list.ml&pp=0&fp=305967&fe=ml&ff=1&filterChecked=true&mp=1&ml=1&me=1&md=1#L3>,
>         >> it seems that map function
>         >> does not be implemented tail-recursively:
>         >>
>         >> let rec map f = function
>         >>     [] -> []
>         >>   | a::l -> let r = f a in r :: map f l
>         >>
>         >>
>         >>
>         >> So my question is:
>         >>
>         >> *Why would OCaml's implementation List.map like this?  *
>         >>
>         >> In my humble option, it definitely should be written in a
>         tail-recursive
>         >> way,
>         >> and it not, stack_overflow would be unavoidable.
>         >> For example in order to handle the exception,
>         >> I abandon the code using List.map and rewrite it into a
>         tail-recursive help
>         >> function.
>         >>
>         >> Best,
>         >> Shuai
>         >
>         > --
>         > Caml-list mailing list.  Subscription management and archives:
>         >https://sympa.inria.fr/sympa/arc/caml-list
>         > Beginner's list:http://groups.yahoo.com/group/ocaml_beginners
>         > Bug reports:http://caml.inria.fr/bin/caml-bugs
>
>
>

Re: [Caml-list] Why List.map does not be implemented tail-recursively?

[Anthony Tavener]

[-- Attachment #1: Type: text/plain, Size: 2799 bytes --]

A remark about the "reverse" list operations... I find that it often turns
out that I'll have an even number of these reverse operations. So even if I
need to maintain the final list order, it can be for free.

For example, List.rev_map, followed by a List.rev_append... everything is
tail-recursive without adding extra list-reversals, and the final order is
maintained.

On Sun, Sep 28, 2014 at 8:31 PM, Shuai Wang <wangshuai901@gmail.com> wrote:

> Wow, List.rev_map f (List.rev li) looks very elegant, thank you all for
> the helpful materials! I should definitely try Core lib soon.
>
> I have been working on a binary program analysis project for over half a
> year in OCaml, and it is really enjoyable to write OCaml code!
> hope I can open source the analysis tool eventually and contribute to the
> community :)
>
> Best,
> Shuai
>
>
>
> On Sun, Sep 28, 2014 at 4:26 PM, Yaron Minsky <yminsky@janestreet.com>
> wrote:
>
>> Indeed, the implementation from that post did make it into
>> Core_kernel.  Here's the link:
>>
>>
>> https://github.com/janestreet/core_kernel/blob/release-112.01.00/lib/core_list.ml#L380
>>
>> y
>>
>> On Sun, Sep 28, 2014 at 3:45 PM, Malcolm Matalka <mmatalka@gmail.com>
>> wrote:
>> > https://blogs.janestreet.com/optimizing-list-map/
>> >
>> > And from the horse's mouth:
>> >
>> > https://groups.google.com/forum/#!msg/fa.caml/YaLYqkpn928/1jdo8a0K6AEJ
>> >
>> > Shuai Wang <wangshuai901@gmail.com> writes:
>> >
>> >> Hello list,
>> >>
>> >>
>> >> I am working on some stack_overflow exception in our recent project
>> written
>> >> in OCaml
>> >> and eventually it turns out that this exception is thrown by List.map
>> >> function.
>> >>
>> >> By seeing the source code of OCaml's List module
>> >> <
>> https://code.ohloh.net/file?fid=P5Us_txNCMHIhpdfML6OZ8QN4Zs&cid=Jigg8RAfQdg&s=ocaml%20list.ml&pp=0&fp=305967&fe=ml&ff=1&filterChecked=true&mp=1&ml=1&me=1&md=1#L3
>> >,
>> >> it seems that map function
>> >> does not be implemented tail-recursively:
>> >>
>> >> let rec map f = function
>> >>     [] -> []
>> >>   | a::l -> let r = f a in r :: map f l
>> >>
>> >>
>> >>
>> >> So my question is:
>> >>
>> >> *Why would OCaml's implementation List.map like this?  *
>> >>
>> >> In my humble option, it definitely should be written in a
>> tail-recursive
>> >> way,
>> >> and it not, stack_overflow would be unavoidable.
>> >> For example in order to handle the exception,
>> >> I abandon the code using List.map and rewrite it into a tail-recursive
>> help
>> >> function.
>> >>
>> >> Best,
>> >> Shuai
>> >
>> > --
>> > Caml-list mailing list.  Subscription management and archives:
>> > https://sympa.inria.fr/sympa/arc/caml-list
>> > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
>> > Bug reports: http://caml.inria.fr/bin/caml-bugs
>>
>
>

[-- Attachment #2: Type: text/html, Size: 5282 bytes --]

Re: [Caml-list] Why List.map does not be implemented tail-recursively?

[Shuai Wang]

[-- Attachment #1: Type: text/plain, Size: 2255 bytes --]

Wow, List.rev_map f (List.rev li) looks very elegant, thank you all for the
helpful materials! I should definitely try Core lib soon.

I have been working on a binary program analysis project for over half a
year in OCaml, and it is really enjoyable to write OCaml code!
hope I can open source the analysis tool eventually and contribute to the
community :)

Best,
Shuai



On Sun, Sep 28, 2014 at 4:26 PM, Yaron Minsky <yminsky@janestreet.com>
wrote:

> Indeed, the implementation from that post did make it into
> Core_kernel.  Here's the link:
>
>
> https://github.com/janestreet/core_kernel/blob/release-112.01.00/lib/core_list.ml#L380
>
> y
>
> On Sun, Sep 28, 2014 at 3:45 PM, Malcolm Matalka <mmatalka@gmail.com>
> wrote:
> > https://blogs.janestreet.com/optimizing-list-map/
> >
> > And from the horse's mouth:
> >
> > https://groups.google.com/forum/#!msg/fa.caml/YaLYqkpn928/1jdo8a0K6AEJ
> >
> > Shuai Wang <wangshuai901@gmail.com> writes:
> >
> >> Hello list,
> >>
> >>
> >> I am working on some stack_overflow exception in our recent project
> written
> >> in OCaml
> >> and eventually it turns out that this exception is thrown by List.map
> >> function.
> >>
> >> By seeing the source code of OCaml's List module
> >> <
> https://code.ohloh.net/file?fid=P5Us_txNCMHIhpdfML6OZ8QN4Zs&cid=Jigg8RAfQdg&s=ocaml%20list.ml&pp=0&fp=305967&fe=ml&ff=1&filterChecked=true&mp=1&ml=1&me=1&md=1#L3
> >,
> >> it seems that map function
> >> does not be implemented tail-recursively:
> >>
> >> let rec map f = function
> >>     [] -> []
> >>   | a::l -> let r = f a in r :: map f l
> >>
> >>
> >>
> >> So my question is:
> >>
> >> *Why would OCaml's implementation List.map like this?  *
> >>
> >> In my humble option, it definitely should be written in a tail-recursive
> >> way,
> >> and it not, stack_overflow would be unavoidable.
> >> For example in order to handle the exception,
> >> I abandon the code using List.map and rewrite it into a tail-recursive
> help
> >> function.
> >>
> >> Best,
> >> Shuai
> >
> > --
> > Caml-list mailing list.  Subscription management and archives:
> > https://sympa.inria.fr/sympa/arc/caml-list
> > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> > Bug reports: http://caml.inria.fr/bin/caml-bugs
>

[-- Attachment #2: Type: text/html, Size: 4461 bytes --]

Re: [Caml-list] Why List.map does not be implemented tail-recursively?

[Yaron Minsky]

Indeed, the implementation from that post did make it into
Core_kernel.  Here's the link:

https://github.com/janestreet/core_kernel/blob/release-112.01.00/lib/core_list.ml#L380

y

On Sun, Sep 28, 2014 at 3:45 PM, Malcolm Matalka <mmatalka@gmail.com> wrote:
> https://blogs.janestreet.com/optimizing-list-map/
>
> And from the horse's mouth:
>
> https://groups.google.com/forum/#!msg/fa.caml/YaLYqkpn928/1jdo8a0K6AEJ
>
> Shuai Wang <wangshuai901@gmail.com> writes:
>
>> Hello list,
>>
>>
>> I am working on some stack_overflow exception in our recent project written
>> in OCaml
>> and eventually it turns out that this exception is thrown by List.map
>> function.
>>
>> By seeing the source code of OCaml's List module
>> <https://code.ohloh.net/file?fid=P5Us_txNCMHIhpdfML6OZ8QN4Zs&cid=Jigg8RAfQdg&s=ocaml%20list.ml&pp=0&fp=305967&fe=ml&ff=1&filterChecked=true&mp=1&ml=1&me=1&md=1#L3>,
>> it seems that map function
>> does not be implemented tail-recursively:
>>
>> let rec map f = function
>>     [] -> []
>>   | a::l -> let r = f a in r :: map f l
>>
>>
>>
>> So my question is:
>>
>> *Why would OCaml's implementation List.map like this?  *
>>
>> In my humble option, it definitely should be written in a tail-recursive
>> way,
>> and it not, stack_overflow would be unavoidable.
>> For example in order to handle the exception,
>> I abandon the code using List.map and rewrite it into a tail-recursive help
>> function.
>>
>> Best,
>> Shuai
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs

Re: [Caml-list] Why List.map does not be implemented tail-recursively?

[Malcolm Matalka]

https://blogs.janestreet.com/optimizing-list-map/

And from the horse's mouth:

https://groups.google.com/forum/#!msg/fa.caml/YaLYqkpn928/1jdo8a0K6AEJ

Shuai Wang <wangshuai901@gmail.com> writes:

> Hello list,
>
>
> I am working on some stack_overflow exception in our recent project written
> in OCaml
> and eventually it turns out that this exception is thrown by List.map
> function.
>
> By seeing the source code of OCaml's List module
> <https://code.ohloh.net/file?fid=P5Us_txNCMHIhpdfML6OZ8QN4Zs&cid=Jigg8RAfQdg&s=ocaml%20list.ml&pp=0&fp=305967&fe=ml&ff=1&filterChecked=true&mp=1&ml=1&me=1&md=1#L3>,
> it seems that map function
> does not be implemented tail-recursively:
>
> let rec map f = function
>     [] -> []
>   | a::l -> let r = f a in r :: map f l
>
>
>
> So my question is:
>
> *Why would OCaml's implementation List.map like this?  *
>
> In my humble option, it definitely should be written in a tail-recursive
> way,
> and it not, stack_overflow would be unavoidable.
> For example in order to handle the exception,
> I abandon the code using List.map and rewrite it into a tail-recursive help
> function.
>
> Best,
> Shuai

[Caml-list] Why List.map does not be implemented tail-recursively?

[Shuai Wang]

[-- Attachment #1: Type: text/plain, Size: 895 bytes --]

Hello list,


I am working on some stack_overflow exception in our recent project written
in OCaml
and eventually it turns out that this exception is thrown by List.map
function.

By seeing the source code of OCaml's List module
<https://code.ohloh.net/file?fid=P5Us_txNCMHIhpdfML6OZ8QN4Zs&cid=Jigg8RAfQdg&s=ocaml%20list.ml&pp=0&fp=305967&fe=ml&ff=1&filterChecked=true&mp=1&ml=1&me=1&md=1#L3>,
it seems that map function
does not be implemented tail-recursively:

let rec map f = function
    [] -> []
  | a::l -> let r = f a in r :: map f l



So my question is:

*Why would OCaml's implementation List.map like this?  *

In my humble option, it definitely should be written in a tail-recursive
way,
and it not, stack_overflow would be unavoidable.
For example in order to handle the exception,
I abandon the code using List.map and rewrite it into a tail-recursive help
function.

Best,
Shuai

[-- Attachment #2: Type: text/html, Size: 6927 bytes --]