Pascal vs C, again (was: Pascals Origins)

[Gregory Smith]

In article <5378 at topaz.RUTGERS.EDU> gaynor at topaz.RUTGERS.EDU (Silver) writes:
[linear array search in Pascal]
>me (greg at utcsri:)
>> 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).

True, except it is quite common for a search test to produce a 'no-match'
result very quickly most of the time, and to always take a long time to
come up with match. The 'match' is the repeated test. Your point is well taken
though.

>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...
:omitted:
>> 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.

But I don't like them :-). Anyway, the idea of using different workarounds
for the same language flaw depending on the expected number of loops is
a bit rancid.
>
>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 ...
>
Try that with an 'else' clause, or with 'if a or b'. Try that with
'while a and/or b'. Your example is the only case that works
( DeMorganizing an OR to an AND won't work either ).

>These are applications of Boehm and Jacopini's Fundamental Control
>Structure Theorem.

The great thing about the C operators is that a code generator can be
made which generates exactly the same code for 'if(a&&b)' as for 
if(!(!a||!!!b)). Without any extra work, too; it happens as a side effect
if conditionals are handled properly (i've written one of these). In effect
they allow you to write spaghetti testing code neatly.

As for the lack of break, it is a fact of life that loops do not always
exit at the same point in the cycle as they start. Pascal ignores this.

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

Sorry, I don't feel that you have shot me *that* full of holes. I do regret
the posting, though, because it was essentially a negative contribution. Must
have been in a bad mood.

Someone pointed out that a goto could be used to break the loop. I had
effectively forgotten that. The only big program I have written in Pascal
was a subset Pascal compiler for an undergrad course. Since it was an
undergrad course, the word 'goto' automatically lost you points, and I had
to do lots of array searching of the above type. Eventually steam started
coming out of my ears. Some of it came back last week :-)

-- 
"You'll need more than a Tylenol if you don't tell me where my father is!"
						- The Ice Pirates
----------------------------------------------------------------------
Greg Smith     University of Toronto      UUCP: ..utzoo!utcsri!greg