My solution to this (while breaking compatibility with Arc) is to just not have mutable cons cells. I only see two legitimate uses for mutable cons cells:
1) Speed. But honestly, if you're micro-optimizing your Arc code by mutating conses...
2) Intentionally infinite lists, like akkartik's "nils":
(= nils (list nil))
(= cdr.nils nils)
I'm not concerned about the first case, especially because a sufficiently smart compiler should be able to handle immutable cons cells reasonably (I believe Racket does).
As for the second case... I think that's solved by adding in a more general system for dynamically generating lazy lists. Then akkartik's "nils" can be written like this:
Basically, lazy-cons takes two thunks: the first is called to extract the car, and the second to extract the cdr. This lets you dynamically create all kinds of nice things, like streams, and it isn't limited to constant values like cyclic lists are.
Thus, you get all the benefits of immutable conses and a strictly more powerful system for lazy list generation. The only possible downside is some performance, which I don't think would be a big deal.
Of course, I already know you're going for full Arc compatibility, so this post is probably useless, but oh well.
Removing mutating cons cells would only solve part of the problem. One would also need to essentially eliminate hash tables, and practically all mutating state. And no, I never understood how monads worked. XD
And yes, the ultimate goal I have for Arcueid is to make a fully compatible Arc implementation, so breaking this sort of compatibility is out of the question as far as this project is concerned, but it is interesting to consider.
It would, for one, make real-time garbage collection a lot simpler...
"It's a good question whether you ever need cycles outside of these two scenarios."
I suppose there might be some algorithms that work better with mutable conses, but honestly, I think conses work best when they're functional, since they have a recursive definition. Making them mutable muddles a lot of different things with no real gain because you rarely mutate conses in Arc.
