12 ms·

Perhaps the most interesting "discovery" for me in this area is that these types of data structures are not possible in C++ as they are in other languages, due

Perhaps the most interesting "discovery" for me in this area is that these types of data structures are not possible in C++ as they are in other languages, due to lack of GC or tail recursion[0], either of which could make them a reality. The other discovery is that some languages, like Swift, are introducing lots of surface-level functional idioms that resemble their counterparts in truly functional languages, but without the persistent structures. Since Swift is implemented in C++, no doubt that's why it's not a reality in that new language either. If someone could cleverly invent an implementation of Okasaki that worked in a language like C++ (and some smart people have really tried), I think it would be a major game changer to the language's possibilities. This handicap is a rare example of something that is simply not so possible in C++. [0] https://github.com/BartoszMilewski/Okasaki/issues/1 https://github.com/BartoszMilewski/Okasaki/issues/1

vanderZwan 11y ago
> these types of data structures are not possible in C++ as they are in other languages, due to lack of GC or tail recursion[0] The link doesn't really explain why though. I mean, I'm willing to believe this is true until proven otherwise - it's safe to assume Milewski knows what he's talking about - but I'd love to see a proper explanation.
- sonyandy 11y ago
  It is in fact incorrect. The incorrect assumption is nested structure implies nested destructor calls. This can be avoided by ensuring each node in the structure does not destroy the next node_ptr (explicitly or more likely implicitly). Instead, the destruction has to happen more manually (internally to the overall data structure - not by the user). If the structure only recurses on one child, it can be performed as a loop.
ZenoArrow 11y ago
> "If someone could cleverly invent an implementation of Okasaki" This is new to me, but based on the HN link, isn't Okasaki a reference to a book with multiple different algorithms? What are the names of the Okasaki algorithms that are hard to implement in C++?
- hellofunk 11y ago
  Please see the GH link I posted, and consider replying directly to the author, who is a well-known C++ guy.
tines 11y ago
> due to lack of GC or tail recursion (1) I'm pretty sure that everything that can be done by a GC can be done by `shared_ptr` and `weak_ptr`. If not, then you can use Boehm GC if you don't do anything weird with pointers. (2) If you mean "tail recursion optimization", it's a compiler thing, not a language thing in this case, and GCC and MSVC in fact support it, and I'm sure Clang does too. So since "either one" is sufficient, as you say, it looks like you can go implement Okasaki's stuff in C++ now!
- hellofunk 11y ago
  >If you mean "tail recursion optimization", it's a compiler thing, not a language thing in this case That doesn't help so much. If it is not a standard language feature as per the C++ spec, then it's not as useful as you'd think.
- deleted 11y ago
  [deleted]
- davexunit 11y ago
  Tail calls are not simply an optimization, they are semantic. edit: Not understanding the downvotes here. In Scheme, for example, tail calls are part of the semantics of the language. We know that when we place a recursive call in tail position that we're really describing a linear process. If such a thing is just an optional optimization, programmers can't rely on it in the same way.
  - sonyandy 11y ago
    Luckily, you can do the rewrite manually. I recently implemented an array mapped trie that shared structure when copied. `find`, `erase`, and `at` were all rewritten to use loops after first implementing them recursively (and profiling indicated it to be a problem).
    - masklinn 11y ago
      If you follow the link, the issue isn't iteration, iteration is easy. The issue is the recursive destruction of the tree when the root is destroyed and no subtree is shared. > The list implementation is simple/nice but it imposes a limit on number of stored elements because of "additional effect" of recursive destruction.
legulere 11y ago
> Since Swift is implemented in C++, no doubt that's why it's not a reality in that new language either. The language the compiler is implemented in doesn't matter, so I guess you mean that it's not possible because Swift is too heavily influenced by C++? I don't think that this is really the case, it's more influenced by Objective-C
- deleted 11y ago
  [deleted]
  - scott_s 11y ago
    The language used to implement the compiler and runtime system for a new language has no impact on what is possible in the new language. If the implementation language does not natively support something you want in the new language, you can just implement that yourself, and it is then available to the new language. For example, C does not natively support garbage collection, but Python certainly does. The most popular Python implementation is implemented in C.
    - hellofunk 11y ago
      Thanks for pointing that out. I'm not a language or compiler engineer so my sight wasn't big enough. I tend to think of a new language as a gigantic library sitting on top of another language, and just assumed that if the base language can't handle something like a persistent data structure, then the new language would struggle with that as well.
      - kazagistar 11y ago
        That is almost never an accurate way to think about it.
      - dkersten 11y ago
        Only a very small handful of languages are actually implemented like this. Its worth also pointing out that some languages that compile to C, still support features that C does not (for example, Chicken Scheme compiles to C and supports both garbage collection and continuations, neither of which C supports natively).
bulatb 11y ago
Have you looked at trampolines/continuation passing?

vanderZwan 11y ago

> these types of data structures are not possible in C++ as they are in other languages, due to lack of GC or tail recursion[0] The link doesn't really explain why though. I mean, I'm willing to believe this is true until proven otherwise - it's safe to assume Milewski knows what he's talking about - but I'd love to see a proper explanation.

sonyandy 11y ago
It is in fact incorrect. The incorrect assumption is nested structure implies nested destructor calls. This can be avoided by ensuring each node in the structure does not destroy the next node_ptr (explicitly or more likely implicitly). Instead, the destruction has to happen more manually (internally to the overall data structure - not by the user). If the structure only recurses on one child, it can be performed as a loop.

ZenoArrow 11y ago

> "If someone could cleverly invent an implementation of Okasaki" This is new to me, but based on the HN link, isn't Okasaki a reference to a book with multiple different algorithms? What are the names of the Okasaki algorithms that are hard to implement in C++?

hellofunk 11y ago
Please see the GH link I posted, and consider replying directly to the author, who is a well-known C++ guy.

tines 11y ago

> due to lack of GC or tail recursion (1) I'm pretty sure that everything that can be done by a GC can be done by `shared_ptr` and `weak_ptr`. If not, then you can use Boehm GC if you don't do anything weird with pointers. (2) If you mean "tail recursion optimization", it's a compiler thing, not a language thing in this case, and GCC and MSVC in fact support it, and I'm sure Clang does too. So since "either one" is sufficient, as you say, it looks like you can go implement Okasaki's stuff in C++ now!

hellofunk 11y ago
>If you mean "tail recursion optimization", it's a compiler thing, not a language thing in this case That doesn't help so much. If it is not a standard language feature as per the C++ spec, then it's not as useful as you'd think.
deleted 11y ago
[deleted]
davexunit 11y ago
Tail calls are not simply an optimization, they are semantic. edit: Not understanding the downvotes here. In Scheme, for example, tail calls are part of the semantics of the language. We know that when we place a recursive call in tail position that we're really describing a linear process. If such a thing is just an optional optimization, programmers can't rely on it in the same way.
- sonyandy 11y ago
  Luckily, you can do the rewrite manually. I recently implemented an array mapped trie that shared structure when copied. `find`, `erase`, and `at` were all rewritten to use loops after first implementing them recursively (and profiling indicated it to be a problem).
  - masklinn 11y ago
    If you follow the link, the issue isn't iteration, iteration is easy. The issue is the recursive destruction of the tree when the root is destroyed and no subtree is shared. > The list implementation is simple/nice but it imposes a limit on number of stored elements because of "additional effect" of recursive destruction.

legulere 11y ago

> Since Swift is implemented in C++, no doubt that's why it's not a reality in that new language either. The language the compiler is implemented in doesn't matter, so I guess you mean that it's not possible because Swift is too heavily influenced by C++? I don't think that this is really the case, it's more influenced by Objective-C

deleted 11y ago
[deleted]
- scott_s 11y ago
  The language used to implement the compiler and runtime system for a new language has no impact on what is possible in the new language. If the implementation language does not natively support something you want in the new language, you can just implement that yourself, and it is then available to the new language. For example, C does not natively support garbage collection, but Python certainly does. The most popular Python implementation is implemented in C.
  - hellofunk 11y ago
    Thanks for pointing that out. I'm not a language or compiler engineer so my sight wasn't big enough. I tend to think of a new language as a gigantic library sitting on top of another language, and just assumed that if the base language can't handle something like a persistent data structure, then the new language would struggle with that as well.
    - kazagistar 11y ago
      That is almost never an accurate way to think about it.
    - dkersten 11y ago
      Only a very small handful of languages are actually implemented like this. Its worth also pointing out that some languages that compile to C, still support features that C does not (for example, Chicken Scheme compiles to C and supports both garbage collection and continuations, neither of which C supports natively).

bulatb 11y ago

Have you looked at trampolines/continuation passing?