Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!zaphod.mps.ohio-state.edu!samsung!munnari.oz.au!bunyip!brolga!uqcspe!batserver.cs.uq.oz.au!ianh
From: ianh@batserver.cs.uq.oz.au (Ian Hayes)
Newsgroups: comp.theory
Subject: Re: Procedures with multiple out parameters: why not?
Message-ID: <4625@uqcspe.cs.uq.oz.au>
Date: 24 Aug 90 01:25:47 GMT
References: <1990Aug15.231838.5664@zaphod.mps.ohio-state.edu>
Sender: news@uqcspe.cs.uq.oz.au
Reply-To: ianh@batserver.cs.uq.oz.au
Lines: 73

vidynath@function.mps.ohio-state.edu (Vidhyarath K Rao) writes:


>I hope that this is the right newsgroup for this article.

>I was reading E. Dijkstra, "The humble programmer", Comm ACM 15(1972), 
>pp. 859--866, as reprinted in "Classics in Software Engineering" edited by
>E. N. Yourdon. I came across the following [para 2 on p. 121 in the reprint]:
>	A number of rules have been discovered, voilation of which will
>	either seriously impair or totally destory the intellectual
>	managebility of the program. These are of two kinds. Those of the first
>	kind ... Examples are the exclusion of the goto-statements and of
>	procedures with more than one output parameter.
>	^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

I suspect the theoretical problem that Dijkstra is referring to is
aliasing of variables. For example, consider
^^^^^^^^^^^^^^^^^^^^^
	proc P(var x, y : integer);
	begin
		x := 1; y := 2
	end
At the end of this procedure one can assert { x = 1 and y = 2 }.
Most people would consider this procedure equivalent to the
following procedure Q.
	proc Q(var x, y : integer);
	begin
		y := 2; x := 1
	end
One can also assert { x = 1 and y = 2} after this.

Now consider the calls P(z,z).
Using the usual substitution rules on assertion one can deduce
	{ z = 1 and z = 2 }
is true. But it is false. The problem comes from having two names
(aliases) x and y within the procedure P for the one variable z.

If var parameters are implemented by call by reference then P(z,z)
will leave z with the value 2 and Q(z,z) will leave z with the value
1. The two procedures which are intuitively equivalent are not
equivalent in this case. 

Another more practical example is the following matrix
multiplication procedure
	procedure MatrixMultiply(var A, B, C : matrix);
	begin
		what you would expect
		{ C = A * B }
	end
Here the A and B are passed as var parameters even though they are
not being modified by the matrix multiplication procedure. However,
if we have a call of the form
	MatrixMultiply(M,M,M)
we will not get the result that we want as A, B and C will all be
aliases for the same matrix M. To avoid this problem we need the
header to read
	procedure MatrixMultiply( A, B : matrix; var C : matrix)
this avoids any aliasing problems and will work correctly for the
call
	MatrixMultiply(M,M,M).
If you still don't follow try it and see what happens with the two
different headers.

This does not rule out a procedure that returns a composite object
such as a record or Cartesian product. Such an object is still a
single variable and doesn't suffer from aliasing.


--
Ian Hayes				ACSNet: ianh@uqcspe.cs.uq.oz.au
Mail: Department of Computer Science, University of Queensland,
      St. Lucia, Queensland  4067, Australia.
Work: +61 (7) 377 4131, Room 618.	FAX:  +61 (7) 371 0783.