Macros, a reader (can be implemented in Arc using lib/treeparse.arc), symeval, I/O

> And then what do we need to do to skip c? Or is that even reasonable?

We could have separate os threads for the io, one for each major io system: HDDs, network, keyboard, etc. We could write special io methods for the green threads that request the io from the scheduler. The scheduler adds the request to the appropriate io thread queue. When the operation completes, it either unblocks the gt, uses the provided call-back, or passes a SNAP style message.

I don't know if that would work very well. It doesn't seem very scalable, and at the very least is complicated. It would be best of course, if we could find a cross platform async io lib. But it still might be a good idea to make the scheduler responsible for io, whatever we use. I'm sure you know more about the whole process than I do.

Here's a list of ideas:

nil

> Does erlang have async io?

I assume it uses async I/O: For a long time Erlang had only green threads and didn't actually use OS threads. From what little I could grok of the Erlang source, it seems it has a set of OS-specific "drivers" for I/O, but these drivers seem to be extremely basic. It seems to have some sort of queue, but I can't figure out how it handles the queue (i.e. how it prevents the queue from blocking normal operation).

Each port is apparently modeled as a process that happens to have the ability to resume/suspend other processes. When the port gets its timeslice (?) it goes through its queue, does one I/O request (?), then resumes the process that asked for that I/O (I think).

In fact the scheme you described seems, approximately, what Erlang does. I think. I haven't found any particularly good discussions on the Erlang source.

Then there's some note somewhere in erl_async too that if threads (OS threads?) are unsupported, then the "async" I/O becomes synchronous (?).

> How does the JVM get it's async io?

Boost also seems to have plenty of libraries that would be useful for SNAP. How is that going anyway, almkglor? I should probably ask questions pertaining to that subjects in it's own thread.

Boost also has asio, but it appears to be concentrated more on socket I/O than I/O in general.

What I would like is to have a general-purpose asynchronous I/O library, which would handle all details of asynchronicity.

Basically, I intend to allow SNAP to be compiled in two modes:

1. Single worker thread, multiple process. For cases where the OS doesn't have decent threads (dorky embedded systems? LOL, quite a few of the embedded systems I've seen recently actually have decent threads)

2. Multiple worker OS-level threads, single runqueue.

async I/O is needed for 1, and would be nice for 2: in case 2, if a worker thread blocks on synchronous I/O, the others will still fetch processes to run from the runqueue, although the blocked worker thread is one less thread that can work.

More of a way of taking advantage of multiple processors/cores while not having to do a lot of process management. Of course, there's not much point in using multiple processors anyway if the VM itself is slow ^^

> I would go for simplicity and copy always. Unless Arc had some kind of inmutable data structure and the vm were able to copy just the mutable parts.

I agree, I did have a plan for a sometimes-sharing, copy-on-write-and-if-receiver-has-a-shared-copy VM, but it felt more complex than necessary.

How about when the user, say, loads lib/scanner.arc and then expects that existing running processes are now able to handle scanners?

cough let the programmer second-guess you cough

> How does Erlang do it?

Heh, you're right. So, in that mindset, why not give a lot of nice macros for controlling share vs copy, and make the default be copy? Then programmers could control nearly everything. Of course, they could always hack on your vm if they really wanted tons of control.

But still, concurrent writing to a global variable sounds dangerous.

I kind of like the idea of them being "registered processes." I'll have to do some more thinking on that.

>It doesn't, actually...

Yes, that answers some of the question, but I was a bit more interested in how they implemented their hot code loading. The code still exists for a while as the existing processes continue to use it. But they eventually phase out the functions and swap to the new ones.

It's in the OTP library actually. For example, they have a standard gen_server module. The gen_server would look approximately like this in snap:

  (def gen-server (fun state)
    (<==
      ('request pid tag param)
        (let (state . response) (fun state param)
          (==> pid (list 'response tag response))
          (gen-server fun state))
      ; hot code swapping!!
      ('upgrade new-fun)
        (gen-server new-fun state)
      ('stop)
        t))

It's actually more complex than that - they generally make messages include a version number so that nodes with new versions can communicate to nodes with older versions. This versioning is, in fact, part and parcel of the gen_server series of functions. Requests to servers are made via functions which send a message (with tags and other metadata such as versions abstracted away) and wait for a receive.

I think what they say is, the programmers good at concurrency write the gen_server and other parts of the OTP, while the average programmers write application code ^^

  (def gen-server (fun state)
    (<==

      ('request pid tag param)

        (let (state . response) (fun state param)

          (==> pid (list 'response tag response))

          (gen-server fun state))

      ; hot code swapping!!
      ('upgrade new-fun)
        (gen-server new-fun state)

      ('stop)
        t))

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;
                          }
                  }
          }
  }

Having to do the checking on each write has the slight disadvantage of slowing down writes. For that matter, we still have to consider how heaps are organized.

For example, in my current stop-and-copy, always-copy-on-message-send, each heap has several semispaces. Semispaces conceptually belong to only one heap. One of the semispaces is the current semispace, the one that is being allocated into. The others were semispaces that were received during message sending.

When a message is sent, it is copied into its own semispace, then the semispace is added to the list of "other semispaces" held by the heap.

During a GC, the GC copies all semispaces into a single new semispace, then the heap releases all the other semispaces and sets the new semispace as the current semispace.

In theory it should be possible to reduce slightly the GC overhead by just copying some (but not all) semispaces into the newest semispace: this is basically an incremental GC

> you could use a Bloom filter to determine if the object is present on the other process.

Hmm. I did think of using Bloom filters, but then I would also end up "copying unnecessarily" anyway for some N% of false positives. Not to mention that I'd still have to build k different hash functions for pointers. So I decided, darn it, just copy all.

> How much are you implementing on the c++ side?

Memory management, worker threads (processes are green but are distributed among a set of worker threads), async I/O (technically Arc-side won't get async I/O, just sync, but then the Arc-side can launch a process to do the actual I/O and send a message to the original process that the I/O's done.) Async I/O is always a problem (even in arc2c), it doesn't seem to be very portable.

Might do a very very basic reader in C, maybe just enough to read numbers, symbols, and lists of same. I want to do the actual reader in Arc and use raymyers' treeparse ^^.

Also, I have to design the bytecode.

The arc2c "machine" is really a simple pushdown stack machine, except that function calls will simply reset the stack to the top N entries (where N is the number of arguments to the function call, including the function/object to call and the continuation).

Bloom filters are probably only a good idea if your copy is a large one, rather than just a small variable.

Here's an interesting idea: for extremely large messages, have some sort of "lazy copying" where the process only copies pieces just before it uses them, or when there isn't a cost associated with the transfer. That way large copies don't slow down your system. You'd still increment the reference counter, if you were using one, and any mutations would have to change a different copy.

Actually, a good question is what the relative costs of sharing vs. copying are. I would think that for small things copying is less expensive than keeping track of who has it, etc., just to avoid copying. For bigger items, it might be worth avoiding a premature copy. I don't know.

Edit 1: About the k hash functions, I think that if there is low enough correlation between bytes in the result you can break up one hash function into several. Also, most good hash functions, (the ones that might be too slow for this purpose) have enough of a difference in the result with slight changes to the input that you could add just 1 to the value several times, and get a dozen hashes. So you could use:

  (hash val)
  (hash (+ val 1))
  (hash (+ val 2))
  ...

Yes, but it is in fact the only case where we copy objects anyway (even reading a global variable would be effectively sending the object in the global to the process in question)

> for extremely large messages...

  #define N    I don't know
  if(msg.total_size() > N){
    msg.share(process);
  } else {
    msg.copy(process);
  }

Take note also that sending messages is recursive: we might be sending a list and thus end up sending several items.

> I would think that for small things copying is less expensive than keeping track of who has it, etc., just to avoid copying.

This was the justification in the Erlang BEAM and JAM machines to always copy.

> About the k hash functions...

Unless we make some special immutable types as mentioned above; then we could share those. Maybe I'm just prematurely optimizing, and should just give up on trying to find ways to avoid the copy. Life is much simpler just copying. :)

How about just starting with always-copy, and later when we have performance data, and experience using it, we can code exceptions? I don't know how easy it would be to code such exceptions, but it would be less likely to break if we didn't make these decisions without empirical evidence.

>twice the overhead... I didn't think it would create any extra mechanisms, just a short circuit rule when deciding to copy or not. Rather than checking the ref counts each time the item is mutated or sent, if it is smaller than a certain amount, we know it was copied.

Now, maybe ref counts are faster than total_size(), but I don't know.

  (load "foo.arc" your-macro-expander-here)

  (def load-my-reader (file read)
    (push current-load-file* load-file-stack*)
    (= current-load-file* file)
    (after
      (w/infile f file
        (whilet e (read f)
          (eval (hook e))))
      (do (= current-load-file* (pop load-file-stack*)) nil)))

  (def f (n k)
    (if
      (is n k 0)
        1
      (and (even n) (odd k))
        0
      ; else
        (f (round:/ n 2) (round:/ k 2)))) ; works if n and k are ints

  arc> (round 4.5)
  4
  arc> (round 5.5)
  6
  arc> (trunc 4.5)
  4
  arc> (trunc 5.5)
  5

from: http://en.wikipedia.org/wiki/Rounding

  Although it is customary to round the number 4.5 up to 5, 
  in fact 4.5 is no nearer to 5 than it is to 4 (it is 0.5 
  away from both). When dealing with large sets of 
  scientific or statistical data, where trends are 
  important, traditional rounding on average biases the data
  upwards slightly. Over a large set of data, or when many 
  subsequent rounding operations are performed as in digital
  signal processing, the round-to-even rule tends to reduce 
  the total rounding error, with (on average) an equal 
  portion of numbers rounding up as rounding down. This 
  generally reduces upwards skewing of the result.

  (apply rand-choice (list 1 2 3))

  "Function call on inappropriate object #3(tagged mac #<procedure>) (1 2 3)"

As for your problem (and no, it doesn't work on Anarki[1]), the problem is that rand-choice is a macro, not a function, and apply only works on functions. The only solution is a terrible hack:

  (def mapply (macro . parms)
    " Applies the macro `macro' to `parms', which are not quoted.
      See also [[mac]] [[apply]] "
    (eval:apply (rep macro) (join (butlast parms) (last parms))))

random-elt does exactly what I want.