Re: Side-Effects in Functions [Rosen Trick]

[dmitry@elros.cbb-automation.de (Dmitry A. Kazakov)]

On Tue, 6 Nov 2001 00:10:31 -0000, "Nick Roberts"
<nickroberts@adaos.worldonline.co.uk> wrote:

>"Dmitry A. Kazakov" <dmitry@elros.cbb-automation.de> wrote in message
>news:3be666fe.6426140@News.CIS.DFN.DE...
>> On 4 Nov 2001 23:26:03 -0800, pete@nospam <pete_member@newsguy.com>
>> wrote:
>>
>> >functions, in the mathemtical sense, do not accept an IN OUT paramters,
>> >and do not have side effects.
>> >
>> >y=f(x), x here can never be modified by the function f().
>> >
>> >so, Ada function is more like a math function.
>
>From a pedagogical point of view, care needs to be taken not to give the
>impression that a function in a procedural programming language (most
>programming languages, really) is the same thing as a mathematical function.
>Clearly it isn't: a mathematical function is a kind of relation called a
>'bijection' (and is nowadays specifically defined as such, I think); a
>programming function is really just an encapsulated computation.
>
>Nevertheless, because a great many (practically useful) computations are, in
>fact, essentially to work out the mapping represented by a mathematical
>function from one value to another, it has become idiomatic to call these
>computations functions. Classic examples include such functions as sin, cos,
>and tan. Since the computations involve no side-effects, they neatly fit the
>'no side-effects' model for programming functions.
>
>> No function in a programming language may have no side effects. One
>> could say that there are side effects which are of no interest, but no
>> more than that.
>
>I think, perhaps, that depends on precisely how you define a side-effect. If
>you include modification of registers or memory as side-effects, then it's
>true. However, we are only interested in side-effects in which we are
>interested!

It is a great problem to give a careful definition of side-effects.
Ada follows rather a pragmatic view, side-effects are ones of
arguments. Unfortunately this definition is too weak for correctness
checks. Though I doubt that a correct definition exists. Just consider
an assertion that includes absolute time!

>> The discussion about in out parameters is proved to be evergreen
>> (:-)). But what I presonally cannot understand is why not to allow
>> PROCEDUREs having a result, i.e.
>>
>> procedure Find (Folder : in out Table) return Table_Token;
>>
>> procedure GetNext  (Item_List : in out Iterator) return Element;
>
>It would be pointless to have value-returning procedures in Ada. The reason
>why is because procedures of this kind would suffer from precisely the same
>dangers as functions (and would therefore be of no benefit over functions).
>
>I'm going to spell out the problems with side-effects in functions, so that
>(hopefully) everyone will be aware of them.
>
>Ada (like many procedural languages) permits compilers to evaluate the
>arguments of a function call in any order it chooses. (Obviously we are
>talking about a functions with more than one parameter here.) The arguments
>to this function call could be other function calls (nested within). For
>example:
>
>   A := B(C(E),D(E));
>
>B, C, and D are all functions. First, the compiler will compile code to
>evaluate E, then it will compile code to evaluate (call) C and D, and then
>finally code that evaluates (calls) B, passing in the results from C and D.
>The code calling C may come before or after the code calling D: it is the
>choice of the compiler.
>
>Now, suppose B, C, and D all have a side-effect when called: they print
>their name onto a log file. The result on the log file of compiling and
>executing this line of code with one compiler could be "C D B", but with
>another compiler it could be "D C B". You have the self-same program,
>compiled on two perfectly correct and compliant compilers, doing two
>different things.
>
>The two different behaviours may seem innocuous in the above example, but
>consider this example, adapted from a real-life situation:
>
>   Header := Decode(Data(1..4)) & Decode(Data(5..8));
>
>The Decode function was really a pseudo-random number generator, but it used
>the values it generated to decode an encrypted message. It used a global
>variable for its state, which had to be seeded with the correct encryption
>key; its side-effect was to update this state. Each 'chunk' that it decoded
>had to be 4 bytes long.
>
>The header of a certain message format was 8 bytes long, so we passed it
>into Decode in two 4-byte chunks, as shown. This code worked fine for us,
>but half-way through the project we changed compilers, and suddenly it
>stopped working. Nobody had altered the code. Recriminations flew. Can you
>see what had happened?
>
>Answer: the first compiler evaluated Decode(Data(1..4)) first, and
>Decode(Data(5..8)) second. So the first decryption value generated (at that
>point in the program) by Decode was used on Data(1..4) first, and the second
>on Data(5..8); the second compiler did it the other way around (as it was
>perfectly entitled to do, since the two calls to Decode are the two
>arguments of a call to "&").
>
>If we had declared Decode as a procedure instead, and then written:
>
>   Decode(Data(1..4),Header(1..4));
>   Decode(Data(5..8),Header(5..8));
>
>this bizarre and mystifying problem would never had occurred (and a certain
>blameless manager -- not myself, I was a junior at the time -- would
>probably not had been sacked).
>
>Side-effects can be programmed into functions quite safely, if you know what
>you're doing. As a rule of thumb, either: (a) diligently ensure that the
>side-effect can't possibly cause a (significant) problem due to an
>'order-of-evaluation dependency', or (b) remove the side-effect.
>
>Typically, the easiest way to remove a side-effect from a function is to
>turn the function into a procedure.
>
>I hope I've convinced any doubters, at this point. If you're still not sure,
>just trust your uncle Nicky, eh?

The above is of course correct. Perhaps everybody enjoyed things like
that at least once [lucky ones did it several times (:-))] 

Yet it proves nothing more than if you have side-effects then, well,
there are side-effects.

Side-effects are bad, dangerous, nasty,... but sometimes necessary.
Then, can Ada's functions prevent users from writting things like
above? The answer is no.

P.S. A comment about computation order. I am not sure, but maybe it
would be worth to think about introducing lazy parameters (Algol's by
name). Ada already has them hard-wired in "and then" and "or else".
The order lazy parameters are evaluated is obviously defined by the
implementation of the subroutine, thus the above problems will
disappear, or better to say, become the responsibility of the
implementation. In your example "&" should have the second parameter
lazy, so 

    Decode(Data(1..4)) & Decode(Data(5..8));

would  mean: evaluate Decode(Data(1..4)); call "&", which internally
calls Decode(Data(5..8)).

Regards,
Dmitry Kazakov