On 29.08.2018 22:01, Walter Bright wrote:
On 8/29/2018 10:50 AM, Timon Gehr wrote:
D const/immutable is stronger than immutability in Haskell (which is
usually _lazy_).
I know Haskell is lazy, but don't see the connection with a weaker
immutability guarantee.
In D, you can't have a lazy value within an immutable data structure
(__mutable will fix this).
In any case, isn't immutability a precept of FP?
Yes, but it's at a higher level of abstraction. The important property
of a (lazy) functional programming language is that a language term can
be deterministically assigned a value for each concrete instance of an
environment in which it is well-typed (i.e., values for all free
variables of the term). Furthermore, the language semantics can be given
as a rewrite system such that each rewrite performed by the system
preserves the semantics of the rewritten term. I.e., terms change, but
their values are preserved (immutable). [1]
To get this property, it is crucially important the functional
programming system does not leak reference identities of the underlying
value representations. This is sometimes called referential
transparency. Immutability is a means to this end. (If references allow
mutation, you can detect reference equality by modifying the underlying
object through one reference and observing that the data accessed
through some other reference changes accordingly.)
Under the hood, functional programming systems simulate term rewriting
in some way, ultimately using mutable data structures. Similarly, in D,
the garbage collector is allowed to change data that has been previously
typed as immutable, and it can type-cast data that has been previously
typed as mutable to immutable. However, it is impossible to write a GC
or Haskell-like programs in D with pure functions operating on immutable
data, because of constraints the language puts on user code that
druntime is not subject to.
Therefore, D immutable/pure are both too strong and too weak: they
prevent @system code from implementing value representations that
internally use mutation (therefore D cannot implement its own runtime
system, or alternatives to it), and it does not prevent pure @safe code
from leaking reference identities of immutable value representations:
pure @safe naughty(immutable(int[]) xs){
return cast(long)xs.ptr;
}
(In fact, it is equally bad that @safe weakly pure code can depend on
the address of mutable data.)
[1] E.g.:
(λa b. a + b) 2 3
and
10 `div` 2
are two terms whose semantics are given as the mathematical value 5.
During evaluation, terms change:
(λa b. a + b) 2 3 ⇝ 2 + 3 ⇝ 5
10 `div` 2 ⇝ 5
However, each intermediate term still represents the same value.
