5 ms·

> As an example a lot of the list manipulation functions are not tail-recursive because the tail-recursive implementation is less elegant. What makes you say t

by Zababa 4y ago

> As an example a lot of the list manipulation functions are not tail-recursive because the tail-recursive implementation is less elegant. What makes you say this has to do with elegance? This sounds surprising.

jolux 4y ago
Well I’m not certain that’s the case, it’s my guess because the language has a strong academic background and is also used for teaching purposes, and many functions are written like they would be in a textbook chapter on recursion, with the topmost stack frame holding a pointer to the front of the list, meaning you can blow the stack on large inputs. Why else would it be done that way? Certainly possible I’m missing something.
- yawaramin 4y ago
  It's not just about theoretical elegance. The list data structure is massively inefficient. Using lists large enough to blow the stack with recursion is a really good indication that something has gone really wrong and the program design needs rethinking.
  - jolux 4y ago
    The fact that lists are inefficient doesn’t mean that they should be processed in a maximally inefficient way. I would argue the opposite is true. There’s no practical justification for forcing the compiler to allocate a new stack frame when you can get it to use a jump instead.
    - yawaramin 4y ago
      There is actually a practical justification–simplicity of the implementation. For a data structure not meant to be used for large datasets, why optimize for that use case? In any case thanks to TRMC landing in OCaml 4.14+, it's a moot question, we'll be able to have our cake and eat it too. Doubtless someone will add the annotation to the standard library soon enough: https://v2.ocaml.org/releases/4.14/manual/tail_mod_cons.html https://v2.ocaml.org/releases/4.14/manual/tail_mod_cons.html
      - jolux 4y ago
        > There is actually a practical justification–simplicity of the implementation. For a function that is going to be written once and called innumerable times, this is a bad justification. You should optimize for the consumers of your library, not for yourself. > For a data structure not meant to be used for large datasets, why optimize for that use case? Because it’s not the job of a standard library to be opinionated about how people use data structures. It’s the standard library’s job to do what is asked of it as efficiently as possible. The best implementation would be specialized for small Ns but they don’t do that either. Good to hear about TRMC, I haven’t been a daily user of OCaml since 4.07, but it’s good to hear that they’re addressing some of these pain points. I still think Core and Base are a better starting point for real-world applications in general.
        yawaramin 4y ago
        > Because it’s not the job of a standard library to be opinionated about how people use data structures. Well, they're not being opinionated about it per se, they're just not supporting (up until now at least) highly-optimized use of lists. There are tradeoffs to consider here beyond what we have discussed in this thread. Check the OCaml forum threads on optimizing list mapping for the various considerations.
        jolux 4y ago
        You characterized this deficiency in light of your own belief that lists should not be used, so I was responding to that part that I disagree with. It’s like Python purposefully crippling lambdas to discourage their use. If you don’t think people should use a feature, just don’t add it. Incidentally I agree with you about lists and only meant to use it as an example of a place where the stdlib authors chose a simple implementation over one that does what you expect. As soon as I started reading the stdlib source and seeing things like that, I immediately understood why Core exists and realized I wouldn’t be able to trust the stdlib in production. It violates the principle of least surprise. It’s one thing to do stuff like this in Haskell where it makes sense because of lazy evaluation, it’s another to do it in an eager language which acknowledges the need to make concessions to practical usage.
- Zababa 4y ago
  > Why else would it be done that way? My guess would be ease of maintenance. OCaml has a small team of people working on it that are already bringing improvements to the language that are multi year projects (multicore recently, modular implicits may be next and will take a long time too). On the other hand, from what I understand, they also added to the compiler something to solve this problem for every class of problem that looks like this: https://v2.ocaml.org/manual/tail_mod_cons.html https://v2.ocaml.org/manual/tail_mod_cons.html. That leaves the question: why not fix the stdlib List.map while waiting for the tail modulo constructor? I honestly don't know. My guess would be that it was easy for everyone that wanted to replace it to either do it or use an array, but that's just a guess.

by Zababa 4y ago

jolux 4y ago

Well I’m not certain that’s the case, it’s my guess because the language has a strong academic background and is also used for teaching purposes, and many functions are written like they would be in a textbook chapter on recursion, with the topmost stack frame holding a pointer to the front of the list, meaning you can blow the stack on large inputs. Why else would it be done that way? Certainly possible I’m missing something.

yawaramin 4y ago
It's not just about theoretical elegance. The list data structure is massively inefficient. Using lists large enough to blow the stack with recursion is a really good indication that something has gone really wrong and the program design needs rethinking.
- jolux 4y ago
  The fact that lists are inefficient doesn’t mean that they should be processed in a maximally inefficient way. I would argue the opposite is true. There’s no practical justification for forcing the compiler to allocate a new stack frame when you can get it to use a jump instead.
  - yawaramin 4y ago
    There is actually a practical justification–simplicity of the implementation. For a data structure not meant to be used for large datasets, why optimize for that use case? In any case thanks to TRMC landing in OCaml 4.14+, it's a moot question, we'll be able to have our cake and eat it too. Doubtless someone will add the annotation to the standard library soon enough: https://v2.ocaml.org/releases/4.14/manual/tail_mod_cons.html https://v2.ocaml.org/releases/4.14/manual/tail_mod_cons.html
    - jolux 4y ago
      > There is actually a practical justification–simplicity of the implementation. For a function that is going to be written once and called innumerable times, this is a bad justification. You should optimize for the consumers of your library, not for yourself. > For a data structure not meant to be used for large datasets, why optimize for that use case? Because it’s not the job of a standard library to be opinionated about how people use data structures. It’s the standard library’s job to do what is asked of it as efficiently as possible. The best implementation would be specialized for small Ns but they don’t do that either. Good to hear about TRMC, I haven’t been a daily user of OCaml since 4.07, but it’s good to hear that they’re addressing some of these pain points. I still think Core and Base are a better starting point for real-world applications in general.
      - yawaramin 4y ago
        > Because it’s not the job of a standard library to be opinionated about how people use data structures. Well, they're not being opinionated about it per se, they're just not supporting (up until now at least) highly-optimized use of lists. There are tradeoffs to consider here beyond what we have discussed in this thread. Check the OCaml forum threads on optimizing list mapping for the various considerations.
        jolux 4y ago
        You characterized this deficiency in light of your own belief that lists should not be used, so I was responding to that part that I disagree with. It’s like Python purposefully crippling lambdas to discourage their use. If you don’t think people should use a feature, just don’t add it. Incidentally I agree with you about lists and only meant to use it as an example of a place where the stdlib authors chose a simple implementation over one that does what you expect. As soon as I started reading the stdlib source and seeing things like that, I immediately understood why Core exists and realized I wouldn’t be able to trust the stdlib in production. It violates the principle of least surprise. It’s one thing to do stuff like this in Haskell where it makes sense because of lazy evaluation, it’s another to do it in an eager language which acknowledges the need to make concessions to practical usage.
Zababa 4y ago
> Why else would it be done that way? My guess would be ease of maintenance. OCaml has a small team of people working on it that are already bringing improvements to the language that are multi year projects (multicore recently, modular implicits may be next and will take a long time too). On the other hand, from what I understand, they also added to the compiler something to solve this problem for every class of problem that looks like this: https://v2.ocaml.org/manual/tail_mod_cons.html https://v2.ocaml.org/manual/tail_mod_cons.html. That leaves the question: why not fix the stdlib List.map while waiting for the tail modulo constructor? I honestly don't know. My guess would be that it was easy for everyone that wanted to replace it to either do it or use an array, but that's just a guess.