Mission impossible?
Encapsulate that aliased alien!

Between need and bleed: aliasing in computer languages

Collected by Øyvind Teig
Navia Maritime AS, division Autronica

A luncheon presentation given at NTNU, Telematikk, 10.Nov.2000

::
Last updated: 12.03.04 08:18

vv

...
"Aliases can result in mysterious bu^gs
as variables change their values
seemingly on their own"
...::...

vv

Contents ::	Listings
Aliasing: two or more names of the same phenomenon Get there and bleed: Fortran, C Don't get there: occam Encapsulation and aliasing in in OO-languages Create me but never change me: immutable objects Encapsulation and aliasing in concurrent languages Sending isn't believing: shallow and deep copying Drive faster, but not safer: C99's restrict keyword If we don't alias we don't leak either Paradox: Objects, components & aliasing (need & bleed) The future?	Fortran C occam Java Java - Subclass polymorphism aliasing error
References

vv

1. Aliasing: two or more names of the same phenomenon :: ^

Morning Star:
Phosphorus

=Venus

Hesperus :Evening Star

The Greeks thought they had two stars. But they had one planet (Venus)
[Geneva]

Aliasing: definition ::

"When several different identifiers refer to the same object". [Foldoc]

Has been called "semantic singularity". [Welch]

In this presentation the term "aliasing" often means "problems because of aliasing". (The terms are aliased!)

This is probably the only presentation you'll ever come across about it

Very little considered(?)

Very little cared about

You probably won't find "aliasing" in the index of any textbook

Aliasing: when it is a problem

When there is a reader/writer role conflict

Aliasing: when it is not a problem

When there is not a reader/writer role conflict

Need ::

Recursive structures, like doubly linked lists will contain aliased elements
("graphs" - with two directions)

Other recursive structures, like singly linked lists will not contain aliased elements
("trees" - with one direction)

Parameter passing

A union in C is a deliberate aliasing,
but it should not be used if there is a reader/writer role conflict(?)

Does OO [Wegner] need to allow aliased elements? (Stay tuned..)

Examples [Ref1]

Aliasing caused by reference parameters
(two parameters aliased or a parameter and a global aliased)

Aliasing caused by arrays
(e.g., do A[i] and A[j] refer to the same location?)

Aliasing caused by pointers
(do *p and q->key refer to the same location?)

You don't need pointers to get aliasing!

Any reference of some sort may give rise to aliasing:
as with Java objects -
(but not Java's references to methods, which are stored "by value")

How about hardware description languages?

I don't know!
But it's easy to see that read/write role conflict of hardware would be fatal.

vv

2. Get there and bleed: Fortran, C :: ^

The "Hoare formula" {precondition} assignment {postcondition}
{x = true} y := false {x = true}.
may not always be valid.

If x and y refer to the same boolean variable, i.e., x and y are aliased, then the formula will not be valid. [Geneva]

It will also break down for parallel code with uncontrolled access to shared variables. [Welch]

Fortran example
integer a, y
   write(*,*) 
   a = 123
   y = 500
   Call Test(y)
   Call PrintAandY()   ! a=123, y=500
   a = 123
   y = 500
   Call Test(a)
   Call PrintAandY()   ! a=0 is wrong!, y=500
   Contains
   Subroutine Test(x)
      integer x
      x = x + a
      x = x - a
   End Subroutine Test
   Subroutine PrintAandY()
      write(*,*) 'a = ',a
      write(*,*) 'y = ',y
   End Subroutine PrintAandY
End
Thanks to Jacob Kuhnle, SINTEF Telecom and Informatics.

The Fortran standard [Fortran] states that there should be no aliasing, but it's not verified.

Some of the rules were [Meyers] ::

You can pass any one variable to a function at most once in the argument list

If you pass a variable as an argument to a function, that function cannot also reference the variable as a global (COMMON)

If you pass a variable to a function, you cannot also pass anything, and the function cannot reference anything, that overlaps in storage (EQUIVALENCE)

C example
int a, y;
Test (int *x) {
  *x = *x + a;
  *x = *x - a;
}
PrintAandY() {
  printf("a = %d\n", a);
  printf("y = %d\n", y);
}
main() /* AliasTest */ {
  printf("\n");
  a = 123;
  y = 500;
  Test(&y);
  PrintAandY(); /* a=123, b=500 */
  a = 123;
  y = 500;
  Test(&a);
  PrintAandY(); /* a=0 is wrong!, b=500 */
}

vv

3. Don't get there: occam :: ^

occam example
PROC AliasTest ()
  INT a,y:
  PROC Test (INT x)
    SEQ
      x := x + a
      x := x - a
  :
  SEQ -- SEQ-uential (not PAR-allel)
    a,y := 123,500
    Test(y)
    Test(a) -- Won't compile (is not wrong!)      
:
occam compiler generates this error output:

"Aliasing error, 'a' is a free variable." [occam]
(Aliasing can only be allowed by using a #pragma)

Proving that aliasing cannot occur is not always straightforward ::

To the practising programmer, aliases can result in mysterious bugs as variables change their values seemingly on their own

A classic example is the matrix multiply routine mult(left, right, result) ..

.. which puts the product of its first two parameters into the third.
This works perfectly well
.. until the day some unsuspecting programmer writes the very
.. reasonable statement mult(a, b, a)

If the implementer of the routine did not consider the possibility..

.. that an argument may be aliased with the result
.. disaster is inevitable

[Geneva]

vv

4. Encapsulation and aliasing in OO-languages :: ^

Java, like many other OO languages, is depending completely on aliasing [Beton]

Aliasing problems are always possible with the object based paradigm [Geneva]

Java example
class thing {
  // By [Welch]
  int x;
  public thing (int v) {x = v;}
  public static void harmless (thing t1, thing t2) {
    t1.x = t1.x + t2.x;
    t1.x = t1.x - t2.x;
  }
}
class alias {
  public static void main (String args[]) {
    thing c1 = new thing(123);
    thing c2 = new thing(500);
    thing.harmless (c1,c2); // c1.x=123 c2.x=500
    thing.harmless (c1,c1); // c1.x=0 is wrong!, c2.x=500 
  }
}
But OO claims encapsulation as one of its traits! ::

There is a subtle relationship between (loss of) encapsulation and aliasing and OO

Aliasing problems will affect, but do not stem from

inheritance

concurrency

persistence

Subclass polymorphism aliasing error

C++: "f (A&a, B&b)" (See Java example code)

a is instance of A, which subclasses B
b is instance of B

a is instance of A
b is instance of B, which subclasses A

Aliasing may give errors even without the affected object being accessed

Because objects may refer to other objects

[Geneva]

vv

5. Create me but never change me: immutable objects :: ^

Immutable (definition)

Objects which are created and then never modified
(Like in functional languages)

Java's String class is immutable, use StringBuffer if you want to modify

Immutable objects are read safely by concurrent threads

They have a central role in anti-aliasing reasoning

even when aliased, they don't hurt

because you don't get the reader/writer role conflict

You may still need to copy them

vv

6. Encapsulation and aliasing in concurrent languages :: ^

In a discussion of what could be done to improve Java's threading model [Holub] writes:

Java's threading model isn't the least bit OO

Arguments to the asynchronous method must be immutable to be thread safe

Permit the syntax "private private"
To make objects really private,
because private & synchronous is not a horse & jockey to bet on!

Require all field definitions to be private unless they reference truly immutable objects or define static final primitive types

But his document doesn't mention aliasing specifically.

The concurrent language occam ::

Does not allow aliasing of variables in sequential (SEQ) components

Has "usage rules" for concurrent parallel (PAR) access:
CREW = Concurrent Read Exclusive Write
= No role conflict neither in SEQuential nor PARallel code
= Static exchange of data: enter/exit parameters

CHANnels for dynamic exchange of data (real copying is done)

Concurrent processes are therefore 100% encapsulated

Is a runnable subset of the CSP process algebra [CSP]

All the rules are verified by the compilers

Runs on several architectures

.. but now we need a next generation of it.. [Icarus?] or a new occam itself?

vv

7. Sending isn't believing: shallow and deep copying :: ^

Copying in Java [Pitfalls p60-66]

Immutable object copying

You (also) need to take copies of an immutable object "to prevent different copies of an object from sharing references to the same mutable object".

Primitive types copying

Clone copying

Cloning = shallow copy (only the primitive and reference values ("pointers to") are copied to the new object).
"The bottom line is that you have to be careful when cloning objects, to make sure that each object in your object graph is properly cloned on order to create a deep copy. Otherwise, you may be debugging "weird" behavior for weeks!"
"Make Your Classes Uncloneable" [Viega]

Mutable deep copying

Only objects that can be changed (mutable) are copied.

Deep copying

All non-primitive objects are cloned as well.
(I believe this is "serializing")
"Make Your Classes Unserializeable" [Viega]

Now, we take all ways to copy
and all ways to control object accessibility, can we extrapolate from there? ::

Programming by coding conventions,
not by rules mandated by language design

Where's aliasing control in OO?

Where's concurrency in OO?

This is where graphical OO tools come in handy

vv

8. Drive faster, but not safer: C99's restrict keyword :: ^

No aliasing yields faster code!
Avoids redundant loads and stores.

[C99]'s restrict keyword allows the compiler to potentially build faster code

The concept takes care of a "restricted pointer"

restrict = "I know (hope) that I have no aliasing in the use of this pointer"

The only meaning of restrict is to permit additional optimization (not to make the program safer)

restrict is a type-qualifier like const and volatile

But you have to check usage of it yourself! There's no aliasing verification!

Elaborated well in [Mitchell] and [Meyers]

vv

9. If we don't alias we don't leak either :: ^

Some definitions [Boosten]:

Garbage Collection (GC)

The process of collecting unused memory fragments

Memory de-fragmentation

The process of reordering used memory fragments such that the memory is used more effectively

Memory leak

Cycle in data objects which seem to own each other - will never be freed

No aliasing means no reference cycles and no memory leaks!
..This is almost sensational..

vv

10. Paradox: Objects, components & aliasing (need & bleed) :: ^

Is aliasing needed in order to express common object-oriented idioms?

vs.

Directly accessing the fields of a class violates two basic principles of OO design: abstraction and encapsulation.

[Geneva][Holub] (Abstraction: representation details are hidden, opposite of concretisation [Foldoc])

Component

A component's characteristic properties are that it is a unit of independent deployment; it is a third-party composition; and it has no observable state.

Inheritance across modules

Whether or not inheritance across components is a good thing is the focus of heated debate (most likely it is not a good thing).

[Szyperski]

Aliasing/encapsulation issues are probably close to the core of the problems

vv

11. The future? :: ^

Treatment of aliasing [Geneva]

Alias detection (when aliasing occurs).

Static or dynamic (run-time) diagnosis of potential or actual aliasing.

Alias advertisement (when aliasing is possible).

Annotations that help modularize detection by declaring aliasing properties of methods.

Alias prevention (when aliasing is not wanted).

Constructs that disallow aliasing in a statically checkable fashion.

Alias control (when aliasing is needed).

Methods that isolate the effects of aliasing.

Conclusion ::

We have seen an example of a static object-based language which disallows aliasing.

We will probably in the future see that it is also possible to design dynamic, object-based languages.

vv

Afterthought [Geneva, 1991] ::

...
By avoiding reference copying
aliasing is also avoided,
and its problem will disappear
...
Naturally, the programmer must learn a different paradigm
...
It is unclear whether this paradigm can mesh well with
mainstream object-oriented techniques
...
The future looks bright
if researchers treat the problem from a
truly object-oriented perspective
...

vv

ATS ::

Does the Automatic Train Stop System (ATS) contain a reader/writer role conflict?

Eastbound train

?
Westbound train

Push "Refresh" in your browser (Explorer).

vv

Appendix :: ^

Subclass polymorphism aliasing error

The program below and the comment are from a personal communication with [Welch]. I am asking, he is answering:

> 2.In "The Geneva Convention On The Treatment of Object Aliasing"
> http://g.cs.oswego.edu/dl/aliasing/aliasing.html there is
> this sentence: "Even simple subclass polymorphism can make
> aliasing opportunities even more difficult to notice and
> appreciate, especially in statically typed languages. For
> example, in a C++ function f(A& a, B& b), a and b may indeed
> be aliased if B is a subclass of A or vice versa."
>
> I've tried to program the example in Java, but haven't yet
> "found" it. I don't understand the C++. Does this make sense
> to YOU?

What I think it's saying is that you can still have two parameters aliased to the same object - even if they have apparently different types. This is because one parameter type may be a sub-type of the other and, so, the same argument may be passed to both. So different parameter types do not guarantee no aliasing singularities. However, if the parameter types are not sub-type related, we should be safe! Having said that, if the parameters were unrelated Java interface types, the same object (of a class that implemented both) could still be passed and we are back with aliasing!!

I guess the point is that a casual inspection of "harmleast" would not spot the potential alias (and, hence, singularity) from the two parameters, since they appear to have different types.


class Foo {                          // Foo is just an int wrapper
  // By [Welch]
  int x;
  public Foo (int v) {x = v;}
}
class Bar extends Foo {
  public Bar (int v) {super (2*v);}  // Bar is just a little different
}
class Useful {
  public static void harmless (Foo a, Foo b) {
    a.x = a.x + b.x;
    a.x = a.x - b.x;
  }
  public static void harmleast (Foo a, Bar b) {
    a.x = a.x + b.x;
    a.x = a.x - b.x;
  }
}
class Alias { // ::
  public static void main (String[] args) {
    Foo f0 = new Foo (123);
    Foo f1 = new Foo (500);
    Bar b0 = new Bar (123);
    System.out.println (f0.x + " " + f1.x + " " + b0.x);  // 123 500 246
    Useful.harmless (f0, f1);
    System.out.println (f0.x + " " + f1.x + " " + b0.x);  // f0 & f1 unharmed
    Useful.harmless (f0, f0);
    System.out.println (f0.x + " " + f1.x + " " + b0.x);  // f0 zapped is wrong!
    Useful.harmleast (f1, b0);
    System.out.println (f0.x + " " + f1.x + " " + b0.x);  // f1 & b0 unharmed
    Useful.harmleast (b0, b0);
    System.out.println (f0.x + " " + f1.x + " " + b0.x);  // b0 zapped is wrong!
  }
}

vv

References :: ^

Navia Maritime AS, division Autronica

Navia Maritime AS, division Autronica is a subsidiary that develops, produces and sells monitoring equipment for ship and offshore markets. The subsidiary has some 200 employees, the headquarter is located in Trondheim, Norway (http://www.autronica.no). Navia has recently been purchased by Kongsberg Gruppen ASA, and "Autronica" will soon appear under a different company name, continuing the "Autronica" branded products (http://www.kongsberg-gruppen.no/).

Author

Øyvind Teig is Senior Development engineer at Navia Maritime AS, division Autronica (http://www.autronica.no/). He has worked with embedded systems more than 20 years, and is especially interested in real-time language issues. Several articles by technical staff at "Autronica" may be read at http://www.autronica.no/pub/tech/rd/Index.htm.

Main reference

[The Geneva Convention On The Treatment of Object Aliasing]

John Hogg, Bell-Northern Research &
Doug Lea, SUNY Oswego &
Alan Wills, University of Manchester &
Dennis deChampeaux, Hewlett-Packard &
Richard Holt, University of Toronto
Written August 1991. Formatted in HTML September 1997
http://g.cs.oswego.edu/dl/aliasing/aliasing.html

Other references

[Aliasing in Fortran context][Ref1]

http://compilers.iecc.com/comparch/article/90-05-016

[Beton]

Rich Beton, to group java-threads@ukc.ac.uk (Join by sending a mail to P.H.Welch@ukc.ac.uk). There also exist another group called "occam-com".

[Boosten]

Marcel Boosten to the same group (see above)

[C99]

The new "ANSI" C standard - http://home.att.net/~jackklein/c/standards.html#c99. Also see Dennis Ritchie- Why I do not like X3J11 type qualifiers

[CSP]

C.A.R. Hoare, "Communicating Sequential Processes". Prentice Hall, 1985. Also see the CSP archive at archive.comlab.ox.ac.uk/csp.html

Ø.Teig, "Safer multitasking with communicating sequential processes", Embedded Systems June 2000. http://www.autronica.no/pub/tech/rd/pub_details.html#Safer_with_CSP
Also contains pointers to Java CSP libraries.

[Foldoc]

http://foldoc.doc.ic.ac.uk/foldoc/index.html - Free On-Line Dictionary Of Computing

[Fortran]

http://www.fortran.com/fortran/F77_std/rjcnf.html - About aliasing

[Hoare calculus]

http://www.csi.uottawa.ca/ordal/papers/peter/node13.html

[Holub]

If I were king: A proposal for fixing the Java programming language's threading problems. Allen Holub. October 2000. http://www-4.ibm.com/software/developer/library/j-king.html?dwzone=java

[Icarus]

http://www.cs.bris.ac.uk/Tools/Reports/Abstracts/1997-may.html - A new "occam" (?) made for "wearable" software

[Meyers]

Meyers, "It all Began with FORTRAN". C/C++ Users Journal, Nov.2000. "Sometimes the best way to improve a language is to make it look more like the one it set out to obsolete 30 years earlier." (About C99 and restricted pointers)

[Mitchell]

Mark Mitchell. "Type-Based Alias Analysis. Optimization that makes C++ faster than C", Dr.Dobb's Journal, October 2000.

[occam]

"occam2 Reference Manual". INMOS Ltd, Prentice Hall, 1988 (C.A.R. Hoare is series editor) ISBN 0-13-629312-3. Also see occam archive at archive.comlab.ox.ac.uk/occam.html.

http://wotug.ukc.ac.uk/parallel/occam/ - Internet Parallel Computing Archive

Øyvind Teig. "Occam - et blindspor? (occam - a dead end?)". SISU Forum 1998. http://www.autronica.no/pub/tech/rd/pub_details.html#OccamEtBlindspor

[Pitfalls]

"Java Pitfalls", Daconta, Monk, Kellr, Bohnenberger. ISBN 0-471-36174-7.

[Szyperski]

Components versus Objects. ObjectiveView, issue 5. http://www.ratio.co.uk

[Viega]

Viega, McGraw, Mutdosch, Felten, "Statically Scanning Java Code: Finding Security Vulnerabilities", IEEE Software Sept./Oct. 2000.

[Welch]

Professor Peter Welch, University of Kent at Canterbury. http://www.cs.ukc.ac.uk/people/staff/phw/

[Wegner]

Wegner's taxonomy
"Object-based implies that the notion of object is supported, encapsulating state and providing a set of operations on the state. Class-based in addition introduces the notion of a class, providing a means for creating objects according to a class template. Object-oriented finally adds inheritance that organizes classes in an inheritance hierarchy."
In P.Wegner: Dimensions of Object-Based language design. In Proc. of the OOPSLA ´87 Conf. on Object-Oriented Programming Systems, Languages and Applications, 1987.
Taken from: A-J.Berre: Vision 1997: An Object-oriented Open Approach to Future SDL Run-time Environments. SISU-II, 1993

Go to top

Mission impossible? Encapsulate that aliased alien!

Between need and bleed: aliasing in computer languages

Collected by Øyvind Teig Navia Maritime AS, division Autronica

A luncheon presentation given at NTNU, Telematikk, 10.Nov.2000

Contents ::

Listings

1. Aliasing: two or more names of the same phenomenon :: ^

The Greeks thought they had two stars. But they had one planet (Venus) [Geneva]

2. Get there and bleed: Fortran, C :: ^

The "Hoare formula" {precondition} assignment {postcondition}

may not always be valid.

If x and y refer to the same boolean variable, i.e., x and y are aliased, then the formula will not be valid. [Geneva]

It will also break down for parallel code with uncontrolled access to shared variables. [Welch]

Fortran example

The Fortran standard [Fortran] states that there should be no aliasing, but it's not verified.

Some of the rules were [Meyers] ::

You can pass any one variable to a function at most once in the argument list

If you pass a variable as an argument to a function, that function cannot also reference the variable as a global (COMMON)

If you pass a variable to a function, you cannot also pass anything, and the function cannot reference anything, that overlaps in storage (EQUIVALENCE)

C example

3. Don't get there: occam :: ^

occam example

4. Encapsulation and aliasing in OO-languages :: ^

Java, like many other OO languages, is depending completely on aliasing [Beton]

Aliasing problems are always possible with the object based paradigm [Geneva]

Java example

5. Create me but never change me: immutable objects :: ^

Java's String class is immutable, use StringBuffer if you want to modify

Immutable objects are read safely by concurrent threads

They have a central role in anti-aliasing reasoning

even when aliased, they don't hurt

because you don't get the reader/writer role conflict

You may still need to copy them

6. Encapsulation and aliasing in concurrent languages :: ^

In a discussion of what could be done to improve Java's threading model [Holub] writes:

Java's threading model isn't the least bit OO

Arguments to the asynchronous method must be immutable to be thread safe

Permit the syntax "private private" To make objects really private, because private & synchronous is not a horse & jockey to bet on!

Require all field definitions to be private unless they reference truly immutable objects or define static final primitive types

But his document doesn't mention aliasing specifically.

The concurrent language occam ::

Does not allow aliasing of variables in sequential (SEQ) components

Has "usage rules" for concurrent parallel (PAR) access: CREW = Concurrent Read Exclusive Write = No role conflict neither in SEQuential nor PARallel code = Static exchange of data: enter/exit parameters

CHANnels for dynamic exchange of data (real copying is done)

Concurrent processes are therefore 100% encapsulated

Is a runnable subset of the CSP process algebra [CSP]

All the rules are verified by the compilers

Runs on several architectures

.. but now we need a next generation of it.. [Icarus?] or a new occam itself?

7. Sending isn't believing: shallow and deep copying :: ^

Copying in Java [Pitfalls p60-66]

Immutable object copying You (also) need to take copies of an immutable object "to prevent different copies of an object from sharing references to the same mutable object".

Primitive types copying

Mutable deep copying Only objects that can be changed (mutable) are copied.

Deep copying All non-primitive objects are cloned as well. (I believe this is "serializing") "Make Your Classes Unserializeable" [Viega]

Now, we take all ways to copy and all ways to control object accessibility, can we extrapolate from there? ::

Programming by coding conventions, not by rules mandated by language design

Where's aliasing control in OO?

Where's concurrency in OO?

This is where graphical OO tools come in handy

8. Drive faster, but not safer: C99's restrict keyword :: ^

No aliasing yields faster code! Avoids redundant loads and stores.

[C99]'s restrict keyword allows the compiler to potentially build faster code

The concept takes care of a "restricted pointer"

restrict = "I know (hope) that I have no aliasing in the use of this pointer"

The only meaning of restrict is to permit additional optimization (not to make the program safer)

restrict is a type-qualifier like const and volatile

But you have to check usage of it yourself! There's no aliasing verification!

Elaborated well in [Mitchell] and [Meyers]

9. If we don't alias we don't leak either :: ^

Some definitions [Boosten]:

No aliasing means no reference cycles and no memory leaks! ..This is almost sensational..

10. Paradox: Objects, components & aliasing (need & bleed) :: ^

Is aliasing needed in order to express common object-oriented idioms?

vs.

Directly accessing the fields of a class violates two basic principles of OO design: abstraction and encapsulation.

Aliasing/encapsulation issues are probably close to the core of the problems

11. The future? :: ^

Treatment of aliasing [Geneva]

Alias detection (when aliasing occurs). Static or dynamic (run-time) diagnosis of potential or actual aliasing.

Mission impossible?
Encapsulate that aliased alien!

Collected by Øyvind Teig
Navia Maritime AS, division Autronica

The Greeks thought they had two stars. But they had one planet (Venus)
[Geneva]

Permit the syntax "private private"
To make objects really private,
because private & synchronous is not a horse & jockey to bet on!

Has "usage rules" for concurrent parallel (PAR) access:
CREW = Concurrent Read Exclusive Write
= No role conflict neither in SEQuential nor PARallel code
= Static exchange of data: enter/exit parameters

Immutable object copying

You (also) need to take copies of an immutable object "to prevent different copies of an object from sharing references to the same mutable object".

Mutable deep copying

Only objects that can be changed (mutable) are copied.

Deep copying

All non-primitive objects are cloned as well.
(I believe this is "serializing")
"Make Your Classes Unserializeable" [Viega]

Now, we take all ways to copy
and all ways to control object accessibility, can we extrapolate from there? ::

Programming by coding conventions,
not by rules mandated by language design

No aliasing yields faster code!
Avoids redundant loads and stores.

No aliasing means no reference cycles and no memory leaks!
..This is almost sensational..

Alias detection (when aliasing occurs).

Static or dynamic (run-time) diagnosis of potential or actual aliasing.

Alias advertisement (when aliasing is possible).

Annotations that help modularize detection by declaring aliasing properties of methods.

Alias prevention (when aliasing is not wanted).

Constructs that disallow aliasing in a statically checkable fashion.

Alias control (when aliasing is needed).

Methods that isolate the effects of aliasing.