[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Chicken-users] R6RS immutable pair
|
From: |
Joerg F. Wittenberger |
|
Subject: |
Re: [Chicken-users] R6RS immutable pair |
|
Date: |
Mon, 3 Jul 2006 15:21:11 +0200 (CEST) |
On Jul 2, 2006, at 20:00 AM, Ken wrote:
> > Is the decision to drop set-c*r! final in R6RS?
> No. The editors are considering it & they want considered feedback
> from the community. I think compiler writers should talk about the
> real gains to be had from immutable pairs. We can take as given the
> answer from regular Scheme programmers.
Here my experience. Full text (formated and linked) at
http://www.askemos.org/A92529c85ccc348aae277522d6d5b801e/mutable-pairs-position.html
= Position Statement on Mutability of Pairs =
Joerg F. Wittenberger
In response to R6RS status report as of june 2006 I'd like to add my
experience concerning section 5, on the mutability of pairs.
Summary
Non-mutability of pairs (i.e. all objects) creates a very different
language than traditional Scheme. Such a setting allows to practically
fulfil semantics of program execution and distributed shared state
beyond feasibility on the basis of a arbitrary mutable store.
I'm personally divided myself whether such a radical change should be
made to the Scheme language. Having made first hand experience with
the implementation of a side effect free dialect of Scheme and on the
background of the reasoning, which lead to the Askemos project, I
value the advantages of controlled mutability. However there is just
too much good Scheme code out there, which should not be broken by
radical language changes.
Wouldn't it be better to add a new data type for those immutable
pairs?
== In Detail ==
=== A Fictional Task ===
An international company has 5 owners from all over the world. Used to
electronic cooperation as they are they want to elect their CEO online
as well. A lack of trust make it difficult to decide whom of them
should host the polling system.
=== Proposed Solution ===
The problem is solved by by hosting the polling system on all five
interested sites simultaneously. The language system stores a copy of
the programs continuation, in the example the polls counter, on each
site. Each vote is counted at each site by this continuation. However
execution is synchronised in byzantine agreement. Now, until three of
those five partners collaborate there's no doubt about the result. But
that's the point of an election anyway.
So the aim is to design a language, which can implement justiciable
processes. (For more (german) background see Rechtssicherheit im Netz
(course of studies at HTWK Leipzig).
The implementer is left with the problem that each mutation to the
shared state has to be agreed. Thus speed of light limits what's
feasible. Here immutable objects become advantageous.
We escaped the problem by dedicating a kind of a coarse Scheme dialect
to control persistent, replicated effects. These are intercepted by
the agreement system. Another side effect free subset of Scheme is
used to query the store and produce proposed modifications for the
persistent part.
For the programmer this boils down to implement two programs, the
query part:
(lambda (this request) <body>) =>response
and the proposal of the new state:
(lambda (this request) <body>) =>(values proposal digest).
The proposal is (kind of a) Scheme program, which describes the
(locally) proposed changes to the persistent state (i.e., the new
continuation and variable assignments) and the final response of the
transaction. However before the proposal is actually executed on all
sites, byzantine agreement is sought on the cryptographic digest
[something like (sha1-digest (with-output-to-string (lambda() (write
proposal))))].
Since <body> never effects the store, complex computations can be done
efficiently. Smart application design means in this context to require
only a small number of persistent (distributed) transactions per user
request. This makes the delay from the agreement protocol negotiable
in exchange for the "tamper proofed backup system".
(The coarse grained language, being slow by design anyway, does
slightly more: some meta data usually interesting in dispute, like
date of creation and check sums to verify content integrity are
maintained. Furthermore the runtime system provides a super user free
permission management system. Eventually there's a resynchronisation
protocol. But that's off topic here. For details see the white paper.)
== Final Note ==
I hope I could demonstrate good reasons to have a standardised side
effect free Scheme subset. Such a language can be used to encode
processes defined by legally binding contracts in machine executable,
tamper proofed way. But I'm not sure that this radical change should
go into R6RS at the expense of breaking compatibility. Due to these
concerns I'd rather vote for an optional language feature or a
distinct data type.