Dicebot on leaving D: It is anarchy driven development in all its glory.

[Timon Gehr]

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.