Pascal vs C, again (was: Pascals Origins)

[Silver]

[ You are getting sleeepy, very sleeeeepy...  tired...  relaxed...  Your ]
[ eyelids are getting heeeaavy...  closing...  You are now in my power.  ]

In article <3130 at utcsri.UUCP>, greg at utcsri.UUCP (Gregory Smith) writes:

> ....

[Begin Paraphrasing]

> Write a code fragment to ensure all the elements of x (an array [1
> .. 1000] of integer) are non-zero, in standard Pascal.  All operands
> of boolean expressions are assumed evaluated.

[End Paraphrasing]

> ....

> This is the best I can find:
> 	var i: integer;
> 	...
> 	i :=1 ;
> 	while i<1000 and x[i] <> 0 do
> 		i := i+1;
> 	if x[i] = 0 then writeln('zero at location', i )
> 	else writeln('not found');
> 
> weird,huh? Note that the condition 'x[i]=0' is evaluated twice ( once
> in the negative sense ), which would be unacceptable if we were searching
> an array of records and the test was expensive.

Your analysis of your own code is misleading.  Assuming an arbitrarily
large array and the unit of work is array element comparison, your
code is an optimal solution.  Your gripe about evaluating x[i] twice
when it is noticed that i is indexing a zero element is NOT valid,
though, because it is only a constant amount of work (q: what's the
difference between 6984713 out of 100000000 and 6948714 out of
10000000? a: practically nothing).

Of course, if the size of the array is constrained to a (small)
constant, then your gripe about your solution IS valid.  Perhaps a
better (in terms of array element comparisons) solution, using boolean
flags...

  function Any_Zeros (List : array [0 .. List_Size] of integer) : boolean;
                             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
                             no flames, I know it wants a type identifier...

    var
      i : -1 .. List_Size;
      Zero_Found : boolean;

    begin
        i := -1;
        Zero_Found := false;
        while (i < List_Size) and not Zero_Found do begin
            i := succ (i);
            Zero_Found := (List[i] = 0)
          end;
        Any_Zeros := Zero_Found
      end;

Note that twice as many book-keeping (namely assignments) operations
are done, but we've assumed array element comparison as the sole unit
of work.  The order of the book-keeping operations remains of the same
order as that of the order of the unit of work.

> The problem is the behaviour of 'and' plus the lack of 'break'.

Noper.  The effect of the break statement can always be simulated by
the use of boolean flags.  These will increase the amount of the
book-keeping, but not change the order of an algorithm as far as the
fundamental work unit(s) goes.

The evaluation of the operands in boolean expressions can be
controlled with nested if-thens.  For example, if I wanted to write

    if a and b then ...

but didn't want to bother evaluating b if a was false, I would write

    if a then if b then ...

These are applications of Boehm and Jacopini's Fundamental Control
Structure Theorem.  For more information, consult a *human*
interpretation of this theorem (perhaps sections 5.2 and 5.3 of The
Programming Language Landscape, by Ledgard and Marcotty (Science
Research Associates, Inc; 1981)).

Do your homework BEFORE posting.  People are watching you, and paying
for it.

Silver  {...!topaz!gaynor}