rbehrends

Like this?

  sequence { for (x in 0..<10) for (y in 0..<10) yield(x*y) }.toList()

Now, technically, Kotlin doesn't have list comprehensions, only the equivalent of generator expressions in Python, so you have to tack an extra `.toList()` on at the end if you want a list, but you can write pretty much any for comprehension in Python in a similar way in Kotlin.

On the other hand, you're not limited to for loops/ifs inside such a generator, but can use fairly arbitrary control flow.

> the 'yield' keyword

Am I missing something here?

  $ cat fib.kts
  fun fib() = sequence {
    var a = 1; var b = 1
    while (true) {
      yield(a)
      a = b.also { b += a }
    }
  }

  println(fib().take(10).joinToString(" -> "))
  println(fib().first { it >= 50 })
  $ kotlin fib.kts
  1 -> 1 -> 2 -> 3 -> 5 -> 8 -> 13 -> 21 -> 34 -> 55
  55

Of course, yield() is a function in Kotlin, not a keyword, but the same functionality is there.

> Note: I wasn't criticizing the paper. I was criticizing the comment, which claimed "it’s better" to view these as special cases.

I didn't assume you were. My note about it being a good paper was just a general "this is worth reading" recommendation.

> "Can handle" is quite the hedge. You "can" walk across the continent too, but at what cost?

It's not a hedge. You claimed that (tracing) GC can handle cycles, while RC was "the opposite", which I read to mean that you believe it cannot.

While we are at it, let's go through the basics of trial deletion.

Trial deletion first looks at possible candidates for objects involved in a cycle (in the original algorithm, those were objects whose RC got decremented without reaching zero). Then, you do a recursive decrement of their children's (and their children's children's, and so forth) reference counts.

Unlike with regular reference counting decrements, you visit children even if the reference count doesn't reach zero. The net result is that reference counts are reduced only along internal paths, but that objects that are still reachable from external paths have reference counts > 0 after that.

Thus, any object with a reference count of zero after this step must be part of an internal cycle and can be deleted. All other objects have their original reference counts restored.

Because trial deletion operates on reference counts differently, it's not something that you can easily implement as a library, which is why you don't see it much except when a language implementation chooses to go with reference counting over a tracing GC.

> You're saying Python uses RC to handle reference cycles, and doesn't need a GC for that? If so please ask them to update the documentation, because right now it specifically says "you can disable the collector if you are sure your program does not create reference cycles". https://docs.python.org/3/library/gc.html

This is a terminology thing. Python uses a variant (generational) trial deletion approach [1]. It's not a traditional tracing GC, and it's also not inaccurate, because GC can mean more than using a traditional tracing GC.

> Nobody said "real time". I just said "hard guarantee".

I was not sure what you meant, so I answered both, as you may have noticed.

[1] https://github.com/python/cpython/blob/796b3fb28057948ea5b98...

First of all, I recommend giving the paper a read, because I think you're misunderstanding the claim (plus, it is a very good paper). The claim is not that they are equivalent, but that tracing GC and reference counting are dual solutions to the same problem, two ends of the same spectrum if you will, with hybrid solutions existing in between.

Second, what you seem to consider to be fundamental characteristics of tracing GC and RC is not in fact so fundamental.

For starters, RC absolutely can handle cycles (e.g. through trial deletion). Such implementations may be difficult or impossible to implement as pure library solutions, but there is nothing that says it can't be done. The most prominent example of a programming language that uses such an approach is probably Python.

Nor does the claim that tracing GC cannot provide hard performance guarantees in the general case (while RC does) hold up under closer examination. Leaving aside the problem that it's already non-trivial to provide hard real time performance guarantees for malloc()/free() and ignoring the issue of cascading deletions, it doesn't hold under the more relaxed assumptions discussed downthread.

For starters, we have such predictability only for the single-threaded case, not for arbitrary multi-threaded situations. And even in the single-threaded case, there are real use cases where predicting performance becomes functionally intractable. Examples are implementations of binary decision diagrams or certain persistent data structures, where the presence of shared subgraphs of arbitrary size make predicting performance of individual deallocations impractical.

In contrast, in the single-threaded case we can absolutely bound individual operations of a tracing GC by either a constant or (in the case of arbitrarily sized allocations) make them linear in the number of bytes allocated (e.g. Baker's treadmill).

What is true is that in the absence of cycles, (naive) reference counting will free memory at the earliest opportunity, which is not something we can say for tracing GC.

You can express immutability simply by making all instance variables private and not providing any methods to modify them.

Delaying deletions can result in significant memory overhead [1].

TANSTAAFL, as they say.

[1] https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&d...

> It may not be a problem in a language like Rust, where the compiler understands the concept of immutability. But most (if not all) mainstream languages except Rust don’t. Your object may be immutable in January but in February someone makes a change in a class used 10 layers below and suddenly your class is no longer immutable. Add invisible sharing to that and your code explodes.

No offense, but this strikes me as a strawman argument. What software design methodology leads to immutable types suddenly being made mutable? Outside of dynamic languages, where is support for immutability not there?

Note that any language with proper information hiding can expressly do immutability (literally going back to the days of Modula-2), plus of course several mainstream languages that have first-class language features to represent immutability for added convenience.

Finally, this is only one example. One underlying problem is that if all reference counts need to be capped at one, you have to either switch to full reference counting or to copy the underlying data.

You can see this play out in the std::collections::HashSet interface. Operations like intersection, union, difference, and symmetric difference return iterators rather than sets. While there are also operators that do return sets, such as bitor, that's implemented as follows.

    fn bitor(self, rhs: &HashSet<T, S>) -> HashSet<T, S> {
        self.union(rhs).cloned().collect()
    }
    

Because the result and the argument can't in general share references to elements, you end up essentially doing a deep copy for e.g. a set of strings, which you want to minimize as much as possible. Thus, limitations on the sharing of references dictate aspects of the API.

> Abstractions understood as „I can change only X without changing Y” (aka GoF OOP patterns or most Clean Code OOP patterns) are overrated anyways. Readability and understandability of code is more important than ability to add something without changing something else. If code is readable and constraints are enforced by the compiler, it is easy and safe to change.

So, you never work with third-party libraries where you do not control the API and have never written libraries to be consumed by other teams/third parties?

> That is a niche case not a common one though.

It was an example meant as an illustration. The general case of "collection of objects" is hardly niche.

> This attitude of non-systems programmers is why people argue garbage collection is slow.

I started programming writing Z80 assembler in the 1980s, counting T-states in order to make hard realtime code work. I wrote a graphics driver for Atari ST/TT hardware not to soon after. I think I have a pretty good idea what working in a real-time and/or resource-constrained environment means.

> This attitude of non-systems programmers is why people argue garbage collection is slow.

That is an incorrect generalization. In fact, I see plenty of inefficient code in C++ and Rust (e.g. because a lot of the workarounds for not having GC require additional copying).

> Sure they are not leaking memory, but garbage collection is not enough more efficient than reference counted as to make up for thousands of destruction's when the more complex reference counted version only had a couple.

This is some really unclear statement. If you're trying to make a connection between absence of (tracing) GC and having value types, they are not inherently related. You can have tracing GC and value types (e.g. C#) or reference counting and a lack of value types (e.g. Python).

What is true is that in general memory allocation is relatively expensive, so you want to avoid unnecessarily allocating objects, but that's true regardless of whether you use malloc()/free() or a garbage collector and the strategies for dealing with that are the same in both cases.

> Yes the code is more complex, but it is also faster and that is a trade off I'll take.

Again, this is an untrue generalization.

> Still no, because STW GC can pause innocent code in arbitrary unexpected moments.

Well, yes, that's the problem, isn't it? And that's the point I was making. Pauses in the main thread absolutely count for latency purposes. Note that in most stop-the-world GCs you also can have pretty good control over when the GC is invoked, and that doesn't make things better.

The idea that you can always predict when cascading deletes happen in RAII code is also misleading. They can easily be hidden behind an abstraction barrier. Do you exactly know what's happening under the hood in all third-party libraries that you use, just for an example?

> If you’re pausing the thread because the thread is doing some work eg calling into system to do I/O, this is not considered a pause

In real-time scenarios (soft or hard), it absolutely is. "Regular" operations are absolutely part of your latency budget, and if "regular" operations can exceed it, you absolutely have a problem. See e.g. pretty much any of Gil Tene's talks on the subject.

This is not a problem if the returned object is immutable. If you're returning mutable objects, then that already needs to be documented as part of the AI and not an incidental discovery from the object being reference counted.

In any event, that is hardly the only case of manual memory management breaking abstractions.

It would then follow that a stop-the-world collector is A-OK for single-threaded programs, because that doesn't count as pausing?

> They are natural, and easy but that doesn't mean they are the right way.

> Often I find with a little thinking that there is a enum key under it all that I can hard code - and the enum key is also type safe so that the compiler can prove my code is correct against some class of bugs in a way a string as key cannot.

There's a fundamental misunderstanding here, I think. By dictionaries I mean language dictionaries, e.g. English -> French. You won't find an underlying "enum key" here. Nor am I sure how an enum would ever get large.

> This article is about systems programming. In systems programming you rarely have such a large dictionary in that format.

First, the article is, but the subthread that started this discussion was more general than that.

Second, even in systems programming, you will commonly have arrays or other collections. Caches are a very common thing in systems programming, after all.

> That is one option, there are more.

It is trivially true that there are alternative options, but all these are workarounds around the problem, i.e. you have to complicate your design or make silent assumptions that may not hold in the future (e.g. when disposing of memory at process exit does no longer work because you now need the code as a library).

First, I have no desire to handle both memory and external resources in a unified way, because memory management and resource management have different needs.

Memory is not just "one kind of resource", it's a very specific type of resource that if it has to be managed manually, inherently creates crosscutting concerns. And memory allocation is pervasive, often implicit in other language constructs. Garbage collectors get to cheat here, because they have a global view that ignores module boundaries and information hiding.

The classical example is that introducing a caching mechanism usually introduces API breaks. Where a function normally returns a pointer/reference/unique pointer and makes the caller responsible for freeing memory (whether through convention such as in C or enforced/automated through language mechanisms such as in Rust), the moment you cache it, you need to return a reference-counted pointer, because now the memory can only be freed if both the caller and the cache don't use it anymore. And that change from a non-reference-counted pointer to a reference-counted pointer is a breaking API change.

There are plenty more situations where manual memory management interacts poorly with modularity, such as filter() style functions, or the various complications that arise from closures capturing their local environment.

Conversely, it is absolutely possible to have pretty straightforward resource management with guaranteed and predictable lifetimes in a GCed language (though, alas, there's a lack of direct language support for that).

The general approach is as follows: Each resource's constructor takes an explicit or implicit owner argument (implicit being the current scope, whether defined through a language construct). You can also transfer a resource to a different owner (reparenting) [1].

Owners of resources can be lifetime managers such as scopes (but those do not need to correspond to lexical scopes and are more like transactions), that have more complex lifetime logic (such as a pool of resources) or objects that themselves are owned (e.g. if you have resources dependent on other resources). When the lifetime of the owner finishes, it calls a dispose function in all owned objects.

Because an owner is required in order to construct such a resource object (unlike a C# using clause or Java's try-with-resources) by virtue of its constructor requiring it, it is impossible to accidentally create such a resource without a controlled lifetime [2].

Note that this is not the equivalent to RAII. You can have a number of non-owning references to such resource objects, essentially the equivalent of a weak pointer. In my experience, this is generally a good thing, because you do not want to have a hidden pointer secretly extending the lifetime of a potentially expensive resource. I prefer resource lifetimes to be explicit and to get an error if they are used past their intended lifetime.

[1] Note that this is conceptually similar to talloc. https://talloc.samba.org/talloc/doc/html/index.html

[2] Obviously, it is still possible in any language to do the equivalent of a raw fopen() call, but that's not something that RAII can fix, either.

1. Such data structures (or more generally, std::vector<std::string, std::vector<std::string>> or something like that) are the natural way to represent e.g. dictionaries. So, you absolutely often need to do that and "don't do that" doesn't help here.

2. This general issue extends to virtually all collections. The idea that you should avoid large collections is not a practical solution to real world problems.

3. An alternative solution would be lazy destruction, but that comes with its own issues, such as a really bad worst-case memory overhead or making RC sufficiently more complex that it's not really a win over tracing GC anymore [1].

[1] https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&d...

What happens if a large std::unordered_map<std::string, std::string> has its destructor called?

The maximum number of references is a red herring. While having a RC capped at 1 allows you to elide the actual reference count and makes pointer assignment cheaper, it does not materially affect the primary source of latency in a reference counting implementation, namely cascading deletions.

This particular group ("Vulkangruppe") isn't about ecoactivism. They're an extremist, violent anarchist group that have previously attacked objects such as cable ducts or radio masts with the overall aim to disrupt public life.

For what it's worth, in Kotlin you could also do the following:

  val newLoc = oldLoc.run { copy(x = x * 2, y = y * 2, z = z * 2) }

Absolutely not. While it obviously should not be used for use cases that it isn't designed for, as a conservative mark-and-sweep GC it is extremely well engineered and has very good throughput.

> The compiler support you need in practice is quite limited.

This is true, but it's absent especially in C. Of course, as long as you can intercept writes and/or reads through pointers, you are good to go in principle. However, that solution may not be efficient.

> Cascading deletes are rare in practice

An array of objects (e.g. std::vector<std::string>) already has unbounded deallocation cost. People mostly think of tree-like structures here, but such structures only add the risk of stack blowout to the lack of an upper bound. But in principle, any container that does not have a size limit can give rise to unbounded pause times.

> I have been writing low latency code for a decade and never seen cascading deletes be a problem.

I don't know what your domain is, but the domains I'm familiar with (especially hard real-time) deal with the underlying constraints by way of restricting how you write programs. A side effect of these restrictions is that you generally avoid use constructs that give rise to cascading deletes. But ultimately, having to deal with these restrictions is suboptimal.

I remember a talk by Gil Tene (CTO and co-founder of Azul Systems) about how the problem with writing real-time Java was that it historically required you to write non-idiomatic Java code, which came at a serious cost to reuse and where he argued that one of the benefits of Azul's GC was that you could write (mostly) idiomatic Java and still have GC noise be less than OS noise.

There is of course the actual problem that the stricter your latency requirements are, the fewer GCs actually meet them. Plenty of modern off the shelf GCs meet typical soft real time requirements, but the harder your real time requirements get, the fewer implementations actually meet them (and are increasingly more expensive).

I'll also add that depending on how strict your latency requirements are, off the shelf allocators may not meet them, either, even for a single malloc() (though there are allocators that offer hard upper bounds for allocation costs, such as TLSF).

> It was demonstrated in the mid 80s that the MMU could be used to implement the write barrier (when I saw that I knew lisp machines were a dead end, though I kept using them for as long as was feasible). You can use this and other compiler support to implement it in a language not designed for GC support, no problem.

Yes, that's why I wrote about support "on the compiler or hardware side" (i.e. MMUs). That said, while this might work in theory, the BDW GC does have support for it, and in practice it doesn't actually work well. Throughput suffers and pause times can actually get worse.

By the way, another alternative way of having incremental collection without compiler support is to use fork() for snapshotting (there's an option in D for that), but that has its own issues, of course.

> The issue I think you meant is that you can’t have a transporting collector (which also compacts your working set, even allowing you to return memory to the system). A language like C++ doesn’t anticipate an object’s address ever changing, so that’s a no go.

No, I wasn't talking about a compacting collector. I very specifically meant generational and/or incremental collection.

This needs some qualifications.

The above problem is about latency of stop the world collectors in a domain that requires extremely low latency. And if you think that stop the world collections are representative of garbage collection as a whole (i.e. the "bad rap"), this is just not being up to the state of the art. (It's just that generational/incremental collection is hard to impossible without having support for write barriers/read barriers/snapshotting on the compiler or hardware side, which makes that a practical no-go for a language that was never designed to have GC support.)

But in terms of throughput, the BDW GC actually performs pretty well, competitive with or beating malloc()/free() libraries. This is plenty enough for a number of applications, especially when it comes to batch processing. In fact, even the stop the world latency is (combined with parallel marking) plenty good enough for a number of types of regular GUI applications, where you don't have the fairly extreme latency requirements of standard video games.

It is also worth noting that manual deallocation (especially via RAII) isn't a panacea for latency, as that is just as prone to large pauses due to cascading deletes [1].

[1] While in theory you can do that lazily, in this case you're losing timeliness of deletion and may actually have worse worst case latency than a modern GC that can stagger its work to have bounded pause times. The benefit of RAII is that you may be able to plan these deletions, but even that can be surprisingly difficult at times, requiring extra management to keep data structures alive longer than normal. [2]

[2] Note that lazily deleting objects in RC to avoid pause times is not necessarily the answer; for one thing, you're introducing much of the complexity associated with incremental GC again (especially having to do X amount of deallocation work for each allocation), or risking considerable space overhead. https://dl.acm.org/doi/abs/10.1145/964001.964019 It also remains a difficult challenge when you're dealing with objects that aren't of bounded size (e.g. large arrays).

The difference between Git and Bazaar/Breezy is how it handles displaying branches. In the latter case, you're getting a hierarchical log by applying the approach recursively, not a graph, which (IMO) is the better visualization. As an added bonus, you also get a canonical revision numbering scheme and don't have to use hashes to identify a commit.

I could go into some detail here why Git is the harder to use system of the two, but I think that would miss the bigger point.

IMO, the larger and longer-term problem is that (open source) version control systems seem to be mostly stuck in the early aughts. This may sound provocative, but in principle, Git and Mercurial don't offer much that wasn't already part of Monotone. Meta/Facebook has really been the only actor I am aware of who has been really pushing the envelope in terms of making open source version control more convenient.

If you think I'm being needlessly provocative, just consider this simple example: why don't version control systems (especially ones that can change history) have undo/redo functionality out of the box? I've only seen this as a Facebook extension for Mercurial that never made it into the Mercurial proper (and survived only as part of Sapling).

This is an essential feature of every basic editor nowadays and it is not easy to implement for a VCS, but it's still mind-boggling that after nearly two decades, it isn't considered core functionality of a VCS. Recovering from mistakes remains a pain point in pretty much any VCS, but shouldn't be.

Commit graph visualization is another problem that's just not handled very well by either Git or Mercurial and hasn't really improved much since their early incarnations, if at all. "git log --graph" or "hg log -G" don't really produce output fit for human consumption if you have even a moderately complex branch structure.

Version control systems are still generally very low-level, giving you a lot of primitives and very few high-level operations that aim at making complex workflows less complex.

Mercurial runs on Python 3 just fine and has been for a while. In fact, starting with Mercurial 6.2 (from July 2022), Python 2 is no longer supported [1].

[1] https://wiki.mercurial-scm.org/Release6.2

As somebody who has actually been using Sapling (because it provides a much saner UI and mental model than git), the git compatibility of Sapling is at best so-so. It feels more like a stopgap solution while they're evolving their own backend (which I'm pretty sure they use internally, because git just doesn't scale to FB monorepo size and doesn't support their rebase-on-push operation). LFS flat-out doesn't work with Sapling. Force pushing after an amend or rebase is still cumbersome, because you need to explicitly specify (again) the branch you are pushing to. And I'm not sure how bad the file descriptor problem still is that you have (had?) with large repos or submodules [1]; there was a new release recently, but I haven't actually stress-tested that.

[1] At least some of that may be due to file descriptor leaks: https://github.com/facebook/sapling/issues/464

Because EU and German jurisprudence have created plenty of holes. It used to be that pure software inventions were unpatentable, while mixed software/hardware inventions (the classical example is anti-lock brakes) were patentable. Doctrine was that the invention had to have a "technical effect", basically working through the forces of nature. So, an invention was patentable originally if the novel part of the invention extended to the hardware.

But that principle was weakened over time, first by saying that the novel part of the invention did not have to extend to the hardware, just that any novel part in the software had to also be inextricably linked to the hardware, even if there was nothing novel in the hardware portion. That was not per se unreasonable, but then opened the gate for further exceptions.

Exceptions were created for software that e.g.:

- did calculations on a computer that were then manually used to configure hardware, e.g. calculations for how to adjust diving equipment, even if the computer had no physical connection to the equipment. - low-level system software, such as page buffers, even if it was abstracted over the actual hardware. - Programs that tested the validity of chip layouts.

Basically, whenever something could related to hardware, however indirectly (even in a roundabout way, e.g. through energy or memory savings), even if the novelty was unrelated to the hardware, courts were likely to find a way to rule that the software is patentable.

You can also publish .NET apps/services directly as container images [1].

Or you can distribute them as a single file, standalone, "ready to run" application, which precompiles your methods and includes the JIT. This results in a larger executable, but keeps all the functionality, including reflection and runtime code generation, intact.

And, of course, you can install .NET core directly on your Linux system, just as you would for Python or Ruby (where you also don't usually rely on the default installation).

[1] https://learn.microsoft.com/en-us/dotnet/core/docker/publish...

You can have it clean without rebasing. This is simply a matter of properly visualizing the history. Unfortunately, most of the major version control systems have decided to basically just dump a raw graph rather than presenting the history in a more user-friendly fashion.

Well, it was apparently upheld twice on reexamination, where they could have fixed that. The problem is more that the bar for non-obviousness is so low, it's basically on the floor. Paired with a discipline (software development), where independent reinvention is common, this is just a recipe for disaster.