[r6rs-discuss] Recursively immutable objects and shared-nothing primitives?

From: Alexander Kjeldaas <alexander.kjeldaas>
Date: Thu Mar 15 13:15:42 2007

Hello.

I read on LtU that this is the last day for comments on r6rs, and
there is one thing that is bothering me about scheme.

There does not seem to be a way to express the shared-nothing
communicating processes model in scheme. This is caused by there not
being a way to have immutable objects or possibly some other
abstraction that is missing.

Hopefully I have misunderstood - I don't use scheme regularly and I
don't follow the latest research. But the only reference to immutable
variables in r6rs is in the description of modules(!)

When you don't have immutable objects, there is no way you can promise
not to send mutable state from one process to another process. This
means that for a scheme implementation - if you implement simple
processes using continuations, there is no possibility for the
implementation to have the continuations live in separate
stacks/heaps.

That again means that there is no way you can reliably distribute a
continuations to another machine. I've briefly looked at some
concurrent scheme implementations:


CD-Scheme does not prohibit passing mutable state between processes -
and wraps references to mutable state so that mutating an object in a
foreign process calls back into the sending process(!) making the
death of a process highly problematic.

Termite Scheme makes everything immutable - making it necessary to
model state as a process(!).

None of these can emulate a decent shared-nothing system IMO.

I am sure that supporting shared-nothing can be done in various ways.
But there seems to be a need to be language-defined abstractions or
functions that can:
1) Make immutable objects (so that communication between processes is
possible including making a message queue).
2) Create a closure with an empty environment, or with an environment
consisting only of immutable objects (so that moving a continuation to
a different heap or machine is possible).

Implementing this on top of scheme is a non-solution as there is no
way for the scheme implementation to know about "promises" you are
making. The scheme implementation will not have the ability to
migrate processes across machines or to a different heap or to respawn
a failed process etc without the above being promises that are defined
in the language.

For an implementation that does not want to implement migration of
processes etc, a default implementation of such abstractions should be
trivial. But the other way is close to impossible as you need to go
outside the language to do so.

Actually, for a lot of simple scheme interpreters, instantiating
several interpreter instances is easy. This means that supporting
shared-nothing "natively" is possibly even easier in a simple
interpreter than in an optimized scheme implementation that uses
"global variables" extensively in its implementation.

Looking at this from the implementation side - what is needed is an
abstraction that makes it possible to have multiple heaps in such a
way that parallel garbage collection in the heaps is possible without
any fancy tricks. The heaps can possibly have pointers into a common
heap of immutable objects, but that is optional and thus makes "local"
and "remote" processes conceptually similar - as they are in erlang.

I think this abstraction is crucially important when programming on
32-core processors. The fact that this is painful for an
implementation of scheme today, but trivial for erlang, tells me that
there is an important abstraction missing in this language.

Regards,
Alexander
Received on Thu Mar 15 2007 - 13:15:30 UTC