Some questions on semantics

[ChristopherKing42]

This library is pretty awesome. I have some quick questions:

• If I serialize a value A and send it, evaluate, and then send it again, will the end-point recognize them as the same and try to merge work?
• If a thunk A depends on B, and I send B, and then A, will B be sent twice? Will it be evaluated by the recipient twice? Or will the recipient use the first B when evaluating A.

[jberthold]

Glad you like the library.

Your questions are very good technical ones!

The short answers are "no" , and "yes, maybe, no".
Short rationale: any way of detecting "the same thing again" on the sender or receiver side means to implement a virtual global heap, and will require global garbage collection.

Long answers:

• if an a is serialized twice, the resulting two Serialized a values won't have any relation to each other, apart from evaluating to the same value -- if no effects are involved
• Also: If a is serialized (and externalised in whatever way, file, network, etc), and then evaluated, the a after evaluation may not be the same as the one before (unless it was actually already evaluated). So what you would 'send' won't be the same thing anyway. serialize captures current evaluation state.
• If a thunk b is shared between two a1 and a2, serialising a1 and a2 will destroy this sharing.
• In general, serialisation and deserialisation can be used to decouple values (i.e. destroy sharing).

A virtual global heap would be a great addition to the implementation, but I believe it is very difficult, if at all possible, to implement it as a library instead of in the runtime system itself. Would be exciting to look into it.

For the virtual shared heap, recommended reading are papers on GUM, in particular a 1996 paper that was later shortened for PLDI. https://www.macs.hw.ac.uk/~dsg/gph/papers/abstracts/gum.html

We have written a JFP paper on this topic (parallel runtime system in distributed memory), which is on the way to publication. I should put a draft online (need to migrate my publication page, so it is lagging); will post a link here when it is up.

[ChristopherKing42]

Thanks for your answers

Also, couldn't the heap be hashed or otherwise given a unique identifier?

[jberthold]

Also, couldn't the heap be hashed or otherwise given a unique identifier?

What should be identified (by the unique identifier) is not the heap but the bindings at the language level, or (shared) subgraphs of those, so hashing the heap (or the serialisation result) won't help. Another point to consider: if this was possible, how should it be decided whether or not to keep a thing that is known under such an identifier but otherwise not used? Again, this will lead you straight to global addresses with reference counting, a virtual global heap, and global garbage collection.

[jberthold]

I have put the forthcoming JFP paper online: http://jberthold.github.io/pdf/BertholdLoidlHammond_JFP16PAEAN-authorVersion.pdf (linked from http://jberthold.github.io/papers.html) Closing this issue, please reopen if more clarifications are needed.