Currently my (unimplemented) plan is, memory is kept in managed heaps, which are handled by a mark-and-sweep collector (can't use semispace or variants for reasons below; at least, I don't think I can use semispace). If a message is passed to another thread, the memory of that message (and every other managed area it refers to) is moved from "managed" space to "shared" space, which is reference counted (the references counted are from threads to shared objects, so circular references are impossible). Objects in "shared" space are immutable (and can thus be accessed lock-free). If a thread attempts to mutate a shared object, instead all shared objects still referenced by that thread are copied to managed space (copy-on-write), the shared objects are released (decrement refcount by 1, free if zero), and the managed copy is mutated (we copy all of them because other shared objects might refer to the shared object being mutated).

Note that "managed" space and "shared" space are not separate areas of memory: they are actually two sets of pointers, so moving an area of memory is just moving a pointer from one set to the other (very cheap). The reason I think I can't use a copy collector is that a shared memory object might end up being located between two managed objects, and the shared object can't be moved without disturbing all the other threads that might be referring to it.

Shared objects are OK to refcount because we're refcounting from threads to shared objects. A thread might have 1000 references to a shared object, but it just counts as 1. Only when the thread GC's and determines that the shared object is not marked does it actually decrement the refcount.

Marks are normally kept in a bool with the memory area, if the memory is managed. If it's shared, then the marking information is kept by membership in a marked_and_shared set while marking (in order to preserve the invariant that shared objects are immutable). Sweeping involves traversing both the managed and the shared set; if the managed set memory area is not marked, then it is freed and removed from the set, etc. If the shared set memory area is not in the marked_and_shared set, then it is released (decrement refcount, free if zero) and removed from the set, etc.

There is also a "light" GC which just sweeps the managed set. Crucially, because shared objects are immutable, they cannot point to managed objects, so mark-and-sweep on only managed objects won't have the overhead of referring to marked_and_shared objects.

(and, err, that's pretty much most of my thinking with regards to having separate heaps being used by various threads. I actually have some of the messier details written down in a text file, anyone interested can post their email addresses ^^)

Basically the main thing I'm trying to solve is the copying of memory of messages when an object is sent across processes. Hence my use of shared immutable data, which is only copied if necessary.

However the problem is really something like this:

  ; process A
  (let v (some-value)
    (==> B v)
    (==> B v))

This can actually happen more often than you think. Consider the case where a process serves as an STM-style container:

  (def container (state)
    (while t
      (<==
        ('put obj)
          (= state obj)
        ('query pid)
          (==> pid state))))

   A ==> object ==> B

   A ==> query ==> B

   A <== object <== B

The bit that's bothering me about copy collectors is that it's somewhat difficult to handle cleanup/finalization. For example, it would be neat if the VM automatically closed any file handles you happened to have dropped, or to automatically terminate processes that are waiting for a message (without a timeout) and whose pid's have been dropped (so that you can return a pid as a "data structure" with impunity, and still have the process be garbage collected when the data structure loses scope).

I think I've hit upon a possible way of handling this though. A copy collector needs to put up to-pointers anyway; I think it may be possible to have the to-pointers as part of the object. The to-pointers default to NULL. When a heap is released (i.e. after its contents have been copied to another heap), the heap inspects its held objects. Any objects whose to-pointers are NULL are finalized/deleted; in effect, the to-pointers become really expensive mark bits.

> You could even use different GC strategies on a per-thread basis (I don't know how much this would be helpful, though...).

(the vtable also serves as my "type code", and is probably better thought of that way)

So I can't safely replace a Generic object on the heap with a ToPointer object, because I'd lose access to the size (i.e. I lose the type code, which I'm using to determine the size). This means I can't sweep and finalize afterwards. The alternative is to keep the size separate from the type code/vtable, but then for each object I end up storing a size_t, which on most systems is probably the same size as a Generic* - so I don't save it either.

So basically my options are:

  type code (automagically inserted by C++ as the vtable)
  to-pointer
  data

  size
  type code
  data

However I intend to use the same copy-algorithm for message passing, so I can't overwrite the tag/type code and the data just because I've copied it, since the original could be reused.

In this case, as you've already said, you can't overwrite the orginal type and you have to reserve extra space for the to-pointer (this means one extra word for every allocated object). This way another problem arises: you have to be sure that the to-pointer is clear every time you start a copy this is automatic after a GC, but not after a copy for message passing. This means that after every message passing, the whole heap must be scanned.

> Or maybe I should actually use a different routine for message passing and GC.

Or again use a mark and sweep with copying instead of sharing of objects ^^. Well, not much different.

Such as?

I know we need to have more Erlang-style VM's. In particular I think we need VM's that pretty much enforce shared-nothing by causing all messages to be copied at the VM level. Hence my current project, which will also tie in some code from the AST-based compiler of arc2c.

- Could we make pattern matching through unification a part of the core language?

- Could we make some tasks easier (I mean terser) using Icon or Prolog-like goal-oriented programming?

- Could Haskell typeclasses be adapted to a dynamic language? (I know that is not possible in general, but maybe in the most common cases). CLOS-like oop is the way?

- Easy defstruct as in Haskell is also a win.

- Which would be the best module system? Python's first order modules are cool, but I also Haskell's module system seems better to do ADTs.

- Could we use generators using a lazy list-like interface?

- To which point could the system be reflective? In the past it was considered that "flambda" (user defined, first class special forms) and redefition of eval with "reflective towers" are not that good ideas, because of efficiency. Should we spend more cycles to allow such things?

- Should the read s-expressions also have associated meta-information?

- Could Arc live in an image?

- Could Arc be just the specification of its own compiler, making the bytecode an official part of the language (as pg once said)?

- Could Arc be blazingly fast?

- Could Arc be prepared for multiprocessor architectures like the guys (pun intended ;)) in Fortress want it to be? Or to intensive scalability like Erlang seems to have?

Of course all that questions are implementable. There probably is a library for every one of them in Cliki.

I am just asking which of them we should take and encourage to be seen as part of "Arc's core". Commonality and practice of an idiom, more than its mere possibility, is what actually defines what a language is.

Currently, Arc's core is not much more than sugar for Scheme (modulo defcall, mostly unseen and great). This doesn't want to be insultive, I am happy that people find Arc useful.

IMO yes. It might even be possible to have the meta-information attached to the nearest cons cell instead, so a cons cell might have, say, (cons a d (o line-number) (o file-name)). This makes symbols always equal other symbols without having to worry about attached meta-information for each "symbol".

Might be useful to add in my VM then ^^.

> - Could Arc be just the specification of its own compiler, making the bytecode an official part of the language (as pg once said)?

Interesting. Might be useful to define Arc as a set of macros which just expand to a bunch of bytecode.

Anyway I'm thinking my VM should be "bytecode" based. The bytecode won't have a numeric representation, but it will have a symbolic one, like ((localvar 0) (globalvar foo) (plus))

> - Could Arc be prepared for multiprocessor architectures like the guys (pun intended ;)) in Fortress want it to be? Or to intensive scalability like Erlang seems to have?

Well, this is what I want to do ^^.

> - Could we use generators using a lazy list-like interface?

Anyway, you could build a Prolog-Like DSL with pat-m and amb

  http://arclanguage.org/item?id=2556
  http://arclanguage.org/item?id=6669

- How should you call functional functions from logical functions?

- How should you call logical functions from functional functions without violating referential transparency?

- Do closures over logical variables make any sense?

  import module

  x = module
  x.function(...)

  (mac assign (name expr)
    `(= ,name ,expr))

  (When you do that,
   it comes out like this.)

The original one I wrote wasn't working quite right. Then I found something in On Lisp, a macro called with-gensyms that I renamed with-hygeine due to a symbol conflict with something in Clisp:

  (defmacro with-hygiene (syms &body body)
   `(let ,(mapcar #'(lambda (s)
                    `(,s (gensym)))
                syms)
    ,@body))

  (defmacro my-stupid-macro (x y z)
    (with-hygeine (a b c)
      `(do-something-with ,x ,y ,z ,a ,b ,c)))

  (hyg my-stupid-macro (x y z) (a b c)
    `(do-something-with ,x ,y ,z ,a ,b ,c))

  (defmacro hyg (name args syms &body body)
    `(defmacro ,name ,args
       (with-hygiene ,syms ,@body)))

  (hyg swap (a b) (temp) 
    `(progn 
      (setf ,temp ,a) 
      (setf ,a ,b) 
      (setf ,b ,temp)))

  (DEFMACRO SWAP (A B) 
    (WITH-HYGIENE (TEMP) 
     `(PROGN 
        (SETF ,TEMP ,A) 
        (SETF ,A ,B) 
        (SETF ,B ,TEMP))))

  (PROGN 
    (SETF #:G3089 A) 
     (SETF A B) 
     (SETF B #:G3089))