I finally think I've figured out a basic #Nix heap using the #Haskell/#GHC technique of flagging every heap object to detect infinite loops. Cache invalidation really is hard... Fortunately, Nix is pure, so I don't have to invalidate any heap objects directly. #RPython makes it easy to hack, although it's still a bit of a slog to debug segfaults.
I think I might have to actually look at #CppNix now, or at least reread Eelco's thesis. I need to understand the differences between evaluation and instantiation.