Data Sharing

The Two Ways To Share Data

The Three Ways To Have Mutable Data

Note that data sharing implies mutable data, but mutable data does not imply data sharing! An example is OCaml. In C, pointers to struct fields are allowed and permit data sharing. Mutable fields are a special kind of implicit reference.

Deep vs Shallow Copy for Parameter Passing

Special Variable Reference Construct: C++ and PHP have a special construct permitting shallow copy instead of deep copy.

Const'ness

Const'ness in Data Structure

In most languages, you have to choose between mutability or immutability when declaring the data structure:

Locally declaring Const'ness

A few languages also give the ability to locally deny any mutability. C++ features:
declaring constant function parameters
The compiler will disallow anything in the function body that could modify the parameter's value [2].
declaring constant a method
The compiler will disallow anything in the method body that could modify the current object (this).
declaring constant the return value of a function
The compiler will disallow any use of the return value that could modify it.
declaring constant a local variable
This goes together with constant return value. Without constant local variables, you can't store such a constant return value [3]

The const'ness doesn't span pointers. You can't restrict pointer mutability inside structs.

Using a mutable value as an immutable value is a kind of subtyping:

Const'ness and Subtyping

Simple examples in C++

In C++, you can give a "int *" where a "int * const" is expected. This is easily understandable: you have an object you are allowed to modify, and you give it to a function which is only allowed to read.

On contrary, you can't give a "int * const" where a "int *" is expected.

Const subtyping rule

const A is a supertype of A

A is a subtype of const(A)

The need for structural equivalence

C++ only allows one to add constness for a whole structure. It doesn't span pointers inside this structure. Nor does it allow to add constness for a part of a structure.

In a structural equivalence based C++, one could write:

struct point2d {
  double x;
  double y;
};
struct point2d_x_mut {
  double x;
  const double y;
};

void x_translate(point2d_x_mut &p, double x) { p.x += x; }
Here we have point2d_x_mut a supertype of point2d.

This may seem overkill on such a small example, but for much bigger objects, one could declare various subtypes of the same class, and that way pinpoint the mutability.

The need for parametric constness polymorphism

In C++, one usually give up constness allowing both mutability and constness is somewhat ugly. If you provide a read-write view on something, you must provide it twice:
      char & String::at(int pos)       { ... }
const char & String::at(int pos) const { ... }
The implementation for both "at" being the same. Read/write iterators are plagued with the same problem.

A solution to this problem is parametric constness polymorphism: if the object is mutable, the function gives you write access to the view, otherwise you only have read access.

(note that C++ is not very nice, but at least it gives precise constness whereas other languages have given up)

Higher-order functions, Parametric Polymorphism and constness

Below is still investigations. I'm currently (deadly) stuck because type inference with subtyping doesn't get along with parametric constness polymorphism.
apply(f, x) = f(x)
v =
    x = apply(+1, 2)
    apply(++, x)
    l = [ 1, 2 ]
    apply((l -> l[0]), l) = 4
    x
Parametric constness polymorphism allows all this:
 (io_x(x) -> io_y(y)), io_x(x) -> io_y(y)
Of course, this is quite verbose and tedious to write. One solution is to have inoutness inference together with hiding this complexity when it's not necessary, only displaying the simple x->y, x -> y

Note that x -> x is not always io_x(x) -> io_x(x):

id1(x) := x
id2(x) := x' = x ; x'
id3(x) := x' = x ; x'.ref
# x' = x  is deep-copying
# id1 !! io_x(x) -> io_x(x)
# id2 !! x -> x
# id3 !! x -> Inout(x)
v =
    i = 1
    id1(i)++
    id2(i)++ # error
    id3(i)++
and here is a more useful example:
side_effect(f, x) := f(x) ; x.ref
# side_effect !! io_x(x)->(), io_x(x) -> io_x(x)
apply_side_effect(f, x) := x' = x ; f(x) ; x
# apply_side_effect !! x->(), x -> x

side_effect(++, 1) # error, 1 is not mutable
apply_side_effect(++, 1) # gives 2

Inoutness Inference

Examples

ignore(x) = ()
ignore !! x -> ()           # io_x = None generalised to In

assign(x, v) := x = v
assign !! Out(x), x -> ()   # io_v = In+ generalised to In

one() := 1
one !! () -> 1

one'() := x = 1 ; x.ref
one' !! () -> Inout(a where a !> 1)  # io_x = None generalised to Inout

copy(x) := x' = x ; x'.ref
copy !! x -> Inout(x)          # io_x' = In generalised to Inout

id(x) = x
id !! io(x) -> io(x)

f(x) = id(x)
f !! io(x) -> io(x)

f(x) = ignore(id(x))
f !! x -> ()                   # io_x = In+ generalised to In

f(x,y) := x = id(y)
f !! Out(x), x -> ()           # io_y = In+ generalised to In, 

f(x,y) := x = id(y) ; y.ref
f !! Out(x), io(x) -> io(x)

Why Having Inoutness Inference?



Inoutness inference and Higher-Order Functions

apply !! (Flex_io(None, 1, 0)(x)->Flex_io(None, 1, 1)(y)), Flex_io(None, 0, 0)(x) -> Flex_io(None, 0, 1)(y) apply(f, x) = f(x) f(x, y) = apply(x, y) creating prototype x1->x0 io_x1 = io_apply0 io_x0 = io_apply1 ___ io_x1 = io_y io_y = io_apply0 io_x0 = io_ret io_ret = io_apply1 f(x, y) := ignore(y) ; apply(x, y) creating prototype x1->x0 io_y > In io_x1 = io_apply0 io_x0 = io_apply1 ___ io_x1 = io_y = In io_y = io_apply0 io_x0 = io_ret io_ret = io_apply1 Problem #1: Here we can have f(x) v = x = 1 apply(++, x) x

References


Notes

[1] One exception is tuples in Python.

[2] Java has the final modifier which disallow to assign the parameter to a new value. Since the value (either a reference to an object or a builtin value) is passed by value, no data sharing is involved and the parameter value constant, but allowing to change the content of the object is quite dumb. This is equivalent to using "char * const" in C++ which is very rarely useful.

Search New Uses for final for more about this.

[3] Java has the final modifier which disallow to re-assign the local variable. Once again, not very useful since you can still modify the value of the object. In any case, constant local variables have no real use without constant methods (which Java doesn't have).


Pixel
This document is licensed under GFDL (GNU Free Documentation License).

Release: $Id: inoutness.html,v 1.9 2002/06/06 10:57:10 pixel_ Exp $