[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: 6927 bytes --]

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

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?

[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?

[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?

[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?

[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?

[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                                  \/

[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?

[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 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?

[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