But ac.scm itself is not immutable. cref lib/scanner.arc , which redefines 'car and 'cdr (which are in ac.scm). If ac.scm, which is even more basic than arc.arc, is itself not immutable, then why should arc.arc be immutable?

So no.

In arc2c functions are represented by closures. Pointers to closures are effectively handles to the actual function code.

Now the function code is immutable (that's how arc2c does it - after all, all the code has to be written in C). When a function is redefined, we create a new closure, which contains a pointer to the new function code (which was already compiled and thus immutable), then assign that closure to the global variable.

Basically my idea for a cache would also have an incremented update pointer:

  class SymbolAtom : public Atom {
  private:
          std::string name;
          Generic* value;
          size_t version;
  public:
          friend class Process;
  };

  class Process : public Heap {
  /*blah blah heap stuff...*/
  private:
          std::map<Atom*, pair<size_t, Generic*> > g_cache;
  public:
          Generic* get_global(Atom* a){
                  std::map<Atom*, pair<size_t, Generic*> >::iterator i;
                  i = g_cache.find(a);
                  // not in cache
                  if(i == g_cache.end()){
                          Generic* mycopy = a->value->clone(*this);
                          g_cache[a] = pair<size_t, Generic*>(a->version, mycopy);
                          return a->value;
                  } else {
                          pair<Atom*, pair<size_t, Generic*> > ip = *i;
                          pair<size_t, Generic*> ipp = ip.second();
                          // no change, return value
                          if(a->version == ipp.first()){
                                  return ipp.second();
                          } else {
                                  //recache
                                  Generic* mycopy = a->value->clone(*this);
                                  g_cache[a] = pair<size_t,Generic*>(a->version, mycopy);
                                  return mycopy;
                          }
                  }
          }
  }