Data Sharing
The Two Ways To Share Data
- implicit reference to data: references in Python, Ruby, Java, C#
- explicit reference to data: pointers in C/C++/C#, references in OCaml (ref)
The Three Ways To Have Mutable Data
- implicit reference to data: references in Python, Ruby, Java, C#
- explicit reference to data: pointers in C, references in OCaml (ref)
- mutable fields: struct fields in C/C++/C#, mutable record fields in OCaml.
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
- implicit reference to data: shallow copy (known exception: PHP)
- explicit reference to data: shallow copy
- mutable fields: deep copy
- immutable values: deep and shallow copy are semantically the same
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:
- in MLs (like OCaml), immutable data is implicit whereas mutability must be
explicit
- in many other languages (C, C++, Java, C#, dynamically typed
languages... [1]), mutable data is implicit whereas
immutability can sometimes be explicitly asked:
- readonly fields in C#
- final fields in Java
- const fields/pointers in C++
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
- the first apply call needs a non-mutable second parameter, so type of
apply must be x->y, x -> y.
- the second apply call must have a mutable second parameter (because
of ++), so type of apply must be Inout(x)->y, Inout(x) -> y.
- the third apply call must have a mutable return value,
so type of apply must be x->Inout(y), x -> Inout(y).
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
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 $