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 bugs
as variables change their values
seemingly on their own"
...::
...

vv

 

 

 

 

 

 

 

 

 

 

 

Contents ::

Listings
  1. Aliasing: two or more names of the same phenomenon
  2. Get there and bleed: Fortran, C
  3. Don't get there: occam
  4. Encapsulation and aliasing in in OO-languages
  5. Create me but never change me: immutable objects
  6. Encapsulation and aliasing in concurrent languages
  7. Sending isn't believing: shallow and deep copying
  8. Drive faster, but not safer: C99's restrict keyword
  9. If we don't alias we don't leak either
  10. Paradox: Objects, components & aliasing (need & bleed)
  11. The future?
  1. Fortran
  2. C
  3. occam
  4. Java
  5. 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]
  1. Aliasing caused by reference parameters
    (two parameters aliased or a parameter and a global aliased)
  2. Aliasing caused by arrays
    (e.g., do A[i] and A[j] refer to the same location?)
  3. 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.

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] ::

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 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)
  1. a is instance of A, which subclasses B
    b is instance of B
  2. 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)

vv

 

 

 

 

 

 

 

 

 

 

 

6. Encapsulation and aliasing in concurrent languages :: ^

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

But his document doesn't mention aliasing specifically.

The concurrent language occam ::


vv

 

 

 

 

 

 

 

 

 

 

 

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

Copying in Java [Pitfalls p60-66]

  1. 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".
  2. Primitive types copying
  3. 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]
  4. Mutable deep copying

    Only objects that can be changed (mutable) are copied.
  5. 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? ::

vv

 

 

 

 

 

 

 

 

 

 

 

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


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]

Conclusion ::

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]
[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]
[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

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.