Or am I wrong in assuming this is a functional language?
I think the question is: how does Lisp function without garbage collecting cons cells?
For one, I'm not sure they even rely on cons cells like "real" Lisp. Clojure doesn't either. They cite ML as inspiration.
Carp language guide states object lifetimes are statically inferred [1] which my guess is they allocate on stack (or malloc/free by scope) and detect use-after-free at compile time.
Another, more theoretical approach is using linear types which require all values to be "consumed" [2]
1: https://github.com/carp-lang/Carp/blob/master/docs/LanguageG...
2: https://www.cs.utexas.edu/users/hunt/research/hash-cons/hash...
[0] https://www.reddit.com/r/haskell/comments/d5d13i/is_it_possi...
[1] https://github.com/carp-lang/Carp/blob/master/docs/Memory.md
As far as I'm aware, this really only applies to single threaded systems. However, if you implement threadsafe modules and keep the shared stuff internal (use the ASAP algos here), you can fit the majority of use-cases including hard-realtime constraints.
Composita is the module system I'm referring to. http://www.composita.net/Composita.html It allows concurrency with managed memory and no GC, through static analysis of the module (component) interface queues.
"TN-tools in Nokia were automatically compiled into C-code to be run in VAX-computers. Compiled C-code did not have garbage collector, there was separate reclaim-command for discarding used data. If you managed to run your program without ever hearing the BEEP caused by garbage collector, your program was ready for VAXing."
First-class functions are a necessary feature of FP, but the mere presence of the feature does not make a language functional. Some counterexamples include Fortran and Smalltalk.
It's an easy misconception because most the well-known newer entries to the lisp family - Scheme, Racket, and Clojure - are all mostly functional, and because most of the major non-functional dialects of lisp died out 30 or 40 years ago.
star e = let (sp, a) = (Split a e, atom sp) in sp
But yes, such code is often useful so that e.g. a parent xml node can refer to its childen nodes while also children nodes can refer to their parents.
Anyway, I'm not sure about this, but I think you can't have circular data structures in the context of strict evaluation (or can you? maybe by defering execution via anonymous functions? I wonder....)
One is through “tying the knot”. E.g. to create an infinite list of 1,1,1,1,1,…
ones = 1 : ones
This will actually be compiled to a list cell with a pointer back to itself. You can construct more complicated self-referential data structures thanks to laziness.
The other way you could get a cycle is that it actually does have mutable data structures, although their use is restricted so they can’t have any observable mutable effect in pure code. But you have e.g. IORef which is basically a mutable pointer.
If you wanted no cycles you would need to eliminate some subset of laziness, knot-tying transformations, recursion, and any support for mutable data structures. But yes, I think it could be done.
Without reference counting, here's the end of a hairy function scope that deallocates 15 local variables and restores two callee-saved registers:
11a6: 48 83 c4 78 add $0x78,%rsp
11aa: 5b pop %rbx
11ab: 41 5e pop %r14
11ad: c3 retq
This gets worse with multithreading, because writing to the same reference count on different cores would even in the best case require one core stealing the cache line from another in order to modify it, which may stall the core; but often even an atomic reference count increment is more expensive even than that because it involves a memory barrier.
Reference counting can become reasonably cheap if it's done at large granularity (filesystem files or COM objects, not conses); if you can elide almost all of the reference-count updates, as in Rust; or if your language runtime is just so dog-slow at everything that the extra cost of reference counting isn't that important, like CPython.
30 years ago or more, before generational GC had gone mainstream, reference counting was a more reasonable choice, because GC was going to be very slow in any case, and ref counting at least used less memory—especially important on machines without cache or virtual memory.
(Purely immutable (applicative) languages like Haskell and Miranda are usually lazy, since that's the payoff for completely abjuring side effects. But lazy evaluation is implemented at the machine level by mutation.)
There are many papers out there on how to elide most ref count operations on locals, and runtimes that use ref counting for automatic memory management typically defer ref count updates in various clever ways (like Nim IIRC). You give up some latency for significant throughput gains.
This is true, but if you can prove things about lifetimes then you can eliminate RC operations with that.
Also, GC is expensive for large processes because 1. peak memory is typically higher 2. you have to scan all of memory for pointers 3. that memory may have been swapped out. Of course this can be optimized too.
Yes, this is true, and in fact with Rust's lifetime analysis you can get excellent performance with reference counting in many places. There is more information about this in https://news.ycombinator.com/item?id=28879401 and https://news.ycombinator.com/item?id=28884775.
> Also, GC is expensive for large processes because 1. peak memory is typically higher 2. you have to scan all of memory for pointers 3. that memory may have been swapped out. Of course this can be optimized too.
It's true that a tracing GC usually requires significantly more memory than manual allocation or reference counting, though occasionally it doesn't, since to implement compacting you basically have to implement a tracing GC, so a GC can sometimes give you lower fragmentation.
It's not true that you have to scan all of memory for pointers, for two reasons:
1. You may have a region of memory that contains no pointers, like Erlang's binary storage.
2. Generational GCs only have to look for pointers in the nursery, the stack, and things marked by the write barrier. If they're GCing a generation that isn't the nursery, at that point they have to scan that generation too, but that's so much less frequent that it doesn't make GC expensive. You say, "Of course this can be optimized too," but actually almost all modern GCs are generational, since the late 01990s. Except...
3. Things like Erlang partition the heap into separate per-process heaps for a large number of lightweight processes. Each of these heaps can be GCed independently because you can't have pointers from one heap to another. "What about unreferenced processes?", you might ask. Well, Erlang doesn't GC processes; you have to explicitly create and destroy them, like a larger-granularity malloc/free, typically using a Rust-like ownership hierarchy to avoid process leaks. This works better than it sounds like it should.
I was going to come back and edit this to say "…when you violate an assumption of generational GC" but you somehow managed to instantly reply to my 3 days late post!
Though I'm not too familiar with how GC runtimes are really implemented; I thought generations were more or less based on allocation age but don't know if it actually does analysis to separate allocations that can't reference each other.
(I should write a HN user-agent to watch old threads, though.)
I should preface this by saying I've never actually written a GC, or maintained one someone else wrote, so I might be off-base here; this is just my understanding from reading books and papers:
The awesome thing about generational GC is that (normally) the generations are physically separate in memory, so the GC can avoid even looking at objects in generations older than the one it's emptying out. (Unless they might contain pointers to objects in that generation, that is, which is detected by the write barrier.)
This combines nicely with the potential killer advantage of copying collectors: they don't need to even look at garbage. So if your nursery (or Garden of Eden, if you prefer) is 8MiB and contains only 128 live objects averaging 64 bytes each, a non-concurrent nursery GC consists of walking the stack and any marked older objects, copying those 8192 bytes into the next generation while adjusting the relevant pointers, then resetting the allocation pointer to the beginning of the nursery. The other, say, 130,944 objects that were allocated in the nursery aren't even looked at by the GC, because nothing points to them. (Unless they have finalizers (destructors).) So the GC examines and copies on average 0.06 bytes per object allocated.
Initializing the objects in the first place, as you must do whether they're allocated by decrementing a stack pointer or anything else, is far more expensive.
Of course, most programs retain a larger fraction of their nursery objects than that, stack allocation makes better use of memory caches than a multi-megabyte nursery, and if your program keeps retaining nursery objects long enough, it will eventually need to GC one of the other generations. So GC still isn't free even in the throughput sense. But it's competitive with manual dynamic allocation.
Memory management is handled by static analysis, a value is owned by the function where it was created. When a value is returned or passed to another function the initial function will give up ownership of it and any subsequent use will lead to a compiler error. To temporarily lend a value to another function (for example to print it) a reference must be created, using the ref special form (or the & reader macro).
and
achieved through a linear type system where memory is owned by the function or let-scope that allocated it. When the scope is exited the memory is deleted, unless it was returned to its outer scope or handed off to another function (passed as an argument).
(Quite often the answer is "it isn't")
Nothing can substitute for a really good allocator.
[1] https://coalton-lang.github.io/20211010-introducing-coalton/