What I Always Wanted to Know about Second Class Values | Hacker News Reader

What I Always Wanted to Know about Second Class Values

dl.acm.org

42 pointstodsacerdoti25 comments

I feel that this work, and that other one it references which proposes modeling first and second class values with type, are simply ignorant of the massive amount of research that had been done in this area in decades past.

I'm actually astonished you can still publish anything on this stuff: papers that talk about upward funargs and show trivial Lisp lambda code, like it's 1973.

The stack/heap dichotomy dictating second class vs first class is wrongheaded; we already have results which show that the distinction between stack and heap is artificial and phony.

For instance oh, Richard Stallman's 1980 work, the "Phantom Stacks" paper. The following two italicized paragraphs are an excerpt:

The key to reducing the impact of a stack on the complexity of the system is to realize that a stack really is not a sort of object that lives in memory, but a way of allocating memory among other objects. It need not have any existence, except in the "mind" of some part of the system which is allocating memory, for some length of time. If the data which is stored in the stack looks like ordinary Lisp objects, then most of the Lisp system will be able to deal with it properly without having to be aware that there is a stack.

One consequence of making the stack not recognizable as a stack is that the garbage collector won't know it is a stack. It will compactify, reorder or reallocate it willy nilly. But the stack's contents, valid accessible Lisp objects, will be preserved in meaning by the garbage collection, just like all such Lisp objects. So no harm is done, as long as we realize that the stack isn't a stack any more. The area of memory which used to be a stack is now part of the heap.

Chicken Scheme, famously, implements an idea from Henry Baker of bump allocating all objects on the stack. All function calls create new frames, and so do function returns: function returns are actually compiled into calls to the continuation and therefore are new function calls with new frames on the stack. When the stack reaches a certain limit, it is rolled back. All objects on it that are still reachable (including lambda environments) are moved to the heap at that moment.

So according to the present paper, objects must be transparently switching from the second class to the first class --- and that is incompatible with the idea of treating them as different types.

Other languages (such as Go) try to keep objects on the stack rather than the heap to avoid putting pressure on the garbage collector, increasing performance. (This seems more important from a practical perspective than supporting continuations?)

But Go doesn't distinguish them using the type system either. New versions of Go sometimes do better escape analysis, keeping more objects on the stack, and that doesn't break any programs.

This makes a lot of sense. It makes me think of Go's approach to blur the distinction of heap/stack by just treating it as an escape analysis problem leading to an allocation choice. If it provably doesn't escape => optimize it by using the stack, otherwise fallback to the heap.

The distinction of stack vs heap objects is an old distinction that is deeply encoded in the semantics of C. It's not obvious that's the right choice.

It's worth pointing out however that you do want to have control sometimes. When you're coding for performance, etc it can be very important to control exactly where objects live (e.g. this must be on the stack with a certain layout). I feel like sometimes it's underappreciated in modern PL design that low-level coding needs this kind of control sometimes.

I think there exists a happy medium solution ultimately though.

> The distinction of stack vs heap objects is an old distinction that is deeply encoded in the semantics of C.

It's the most flexible way to implement recursive functions, and it's encoded on the semantics of the opcodes of every modern processor. They are way more deeply entrenched in our tech than just in C.

But it may make sense to mix them in some ways. None of that detracts from the point.

A linear stack, distinct from a heap, is not required for recursion. It's also not required for most of the local state: the minimal requirement is to keep track of the minimal context information in order to resume the suspended caller when the callee terminates.

That's a good point. It is pretty intertwined with ISAs. But, I think you could successfully argue it's just C semantics leaking into the ISA. C was so incredibly successful that it's hard to appreciate sometimes that all the systems (abstractions above and below) that touch it came to embrace and conform to it's semantics.

In a lot of cases, we could argue that ISAs have been shackled by catering to the specific details of C. But if we're just referring to the CALL instruction (and its equivalents), that's not a reaction to C, it's a reaction to structured programming, which was a good thing.

Whether a CALL instruction (by whatever name) does anything with the stack is ISA dependent. On ARM, the BL instruction saves the return address into the LR register and performs a branch, much like the B instruction.

> The distinction of stack vs heap objects is an old distinction that is deeply encoded in the semantics of C. It's not obvious that's the right choice.

Nothing about C requires a contiguous stack, and there are perfectly standard C environments where the stack isn't contiguous, where call frames are allocated dynamically and managed (singularly or in groups) as a linked-list, e.g. some mainframe environments, gcc's segmented stacks, etc. C's automatic ("stack") variables are defined in terms of their lifetime, which is basically lexical.

I don't think the OP assumed that stacks were contiguous. The main distinction from the heap is that stack management is automatic in C.

That's https://dl.acm.org/doi/10.1145/214448.214454 https://guenchi.github.io/Scheme/doc/CONS%20Should%20Not%20C... right?

> we already have results which show that the distinction between stack and heap is artificial and phony.

That's not really true on modern architectures.

The "stack" is a way to time-alias memory and, on modern architectures, that also has performance implications. The stack gets pushed and popped repeatedly so that area of memory stays very hot in the caches.

Garbage collection, by definition, trashes locality. So, pushing onto the "stack" and unwinding it by "garbage collection" is pretty disastrous for performance on modern architectures.

> Garbage collection, by definition, trashes locality.

No, it doesn't necessarily. It is correct if you are thinking about mark and sweep GC. But that is 50 years old. Generational GC has much better locality. And GC can even improve locality sometimes by moving objects together that are connected by references. I am not claiming that GC is always a big win for locality. That would be very far from the truth. On the other hand it is not by definition so, that locality is trashed by GC.

This call to continuation business sounds pretty bad for performance, though: all local state needs to be copied. One could just pass on a pointer to a memory blob / arena or some such, I guess, which is not too different from using the same stack pointer before and after the call, so Hmmm... I wonder what the downsides really are.

> all local state needs to be copied

all local live state. The idea is that most objects are ephemeral and will be orphaned before there is a need to be collected.

Simply to call a helper function and have it return, you need to create a lexical closure and pass that as the return continuation to that helper. Now since everything is being allocated off the stack, that makes the closure a bit cheaper: the environment is all on the stack, and so it is much the same as a frame link pointer plus return address. The difference is that the callee can run out of stack, and have to invoke a stack reset. During the stack reset, the previously cheaply allocated return continuation/lambda will be moved to the heap --- along with others like it up the call stack.

Some may argue that the real problem here is the unstated assumption of wanting to have a garbage collector in the first place.

Even if you use C++, and your lambdas allocate to the heap when created and deallocate when going out of scope, this paper could still help reduce the need for heap allocation for capturing lambdas in the first place, improving performance.

to be clear, C++ doesn't allocate lambdas on the heap. The allocation is under user control like for any other type.

Sorry for being ignorant of the basics, but how does the following work?

> However, seg-ments of code that are provably free of garbage collection > have deterministic timing and can satisfy hard timing con-straints, as they > are certainly not interrupted by garbage collection.

You are only ever "certainly not interrupted" if you turn off interrupts, which requires a high level of privileges. And not being interrupted still does not mean you have uncontended access to main memory or shared caches, which is a relevant factor for hard real-time. Nor do you have uncontended access to execution facilities (e.g. multipliers or floating-point ALUs), but at least for those you might be able to find an upper bound even for contended access.

Well, you're guaranteed not to be interrupted by garbage collection, which is the point here. Segments of code that are provably free of garbage collection can satisfy hard timing constraints, but that doesn't mean that they just will. It's a paper about garbage collection; addressing all the other things that need to be done to ensure compliance with hard real-time requirements is clearly outside the scope of the work.

I'm speaking a little outside my wheelhouse here (experts, please jump in), but my understanding is that if you have actual hard real-time requirements, you very well might turn off interrupts, multithreading, etc. and work with uncontested access to CPU/memory resources during time-sensitive parts of your code, as needed.

But that's still "draw the rest of the owl" category of complexity, and you probably can't really get hard real time on an ordinary kernel.

At that point you might as well take a look at runtimes that have a GC and is hard real time, which exists for the JVM. So not sure if it's really that valuable to separate out GC, especially when there are many other functions that can run much longer than expected (e.g. think of stack unwinding).

It's a curious sentence and one of only two to mention timing, the other being the introduction's mention of the "unpredictable timing" of garbage collection.

Obviously it is true in a single threaded system. If the one and only thread executes a basic block of instructions, none of which call into memory management, or call any functions which might do that, then it holds that it's not interrupted by garbage collection.

If there are threads, and a stop-the-world discipline for GC, then obviously not.

Note that garbage collection itself can have a switch, not involving disabling interrupts. Of course, you wouldn't want to insert that around every block that doesn't need GC. I'm just mentioning that in order to note that we don't a heavy hammer like disabling interrupts in order to momentarily disable garbage collection. When GC is disabled, it is still possible to allocate objects, but no garbage collection passes are invoked to reclaim storage. This means that if the allocator has exhausted the available heaps, since it is not able to run a garbage collection pass, it has to ask the system for more memory for a new heap.

I've used a switch like this around calls to a Yacc-generated parser, due to the Yacc stack being invisible to the garbage collector; newly allocated objects could be prematurely reclaimed as they are being "laundered" through the Yacc stack before being nailed into the abstract syntax tree.

> Obviously it is true in a single threaded system.

But only if you disable interrupts, right? Of course, if you are working that close to the hardware, it makes sense to include "no interrupts" in your definition of "single threaded".

> Note that garbage collection itself can have a switch, not involving disabling interrupts.

I don't understand this. If you get thrashed with interrupts then no switch will remove the overhead of the interrupt handler, so you'd need an upper bound on the time for that handler AND the frequency of hardware interrupts to achieve hard real-time.

The only reason you'd need to disable interrupts to be sure that GC is not called over some block of code is if interrupt service routines are allowed to invoke GC.

For that to work, thread-like concurrency issues already have to be solved in the run-time.

Separately from that, we can have a system in which interrupts are allowed to call into the garbage collection module in order to allocate objects from an atomic free list, but a garbage collection pass is not allowed in interrupt context. (Allowing garbage collection passes, even if ephemeral, in interrupt context strikes as a bad idea because you generally want interrupt context to do as little work as possible.)

Now if we care about some block of instructions executing with absolute minimal delay then we do have to disable interrupts (at least local interrupts on the processor where that block is executed). We don't want the code to be interrupted to service any interrupts. No timer interrupts, no network interrupts, nothing. It is not related to GC.

Reply on news.ycombinator.com