idc@minster.UUCP (idc) (08/06/86)
A small contribution to the debate re. forced termination of linear search
in Pascal. Below is a little program in ISO level 1 Pascal that
illustrates the method. It is not original; for example see the paper
R.G. Dromey, "Forced termination of loops", Softw.pract.exp., pp 29-40,
Vol. 15 No. 1, January 1985.
which I strongly recommend. It has only two disadvantages over the
state indicators method: (i) The index variable cannot have the same
subrange as the indextype of the array (but that is not possible with
conformant array parameters anyway), and (ii) really the same as (i),
-maxint may not be the lower bound (in general pred(lowerbound) must be
defined. N.B. Neither a goto nor a Boolean in sight! Read the ref. for
full details.
Here is the example dressed up as a "find a character in a string" function.
------------
program ForcedTerminationTest(Output);
function find(ch:Char; string: packed array[lo..hi:Integer] of Char):Integer;
{
* pre: lo > -maxint
* post: if find(ch,string) = -maxint then true else string[find(ch,string)]=ch
}
var
i, N: Integer;
begin
{ -- Initialise loop variables }
i := lo-1; N := hi;
{ -- Linear search with possible forced termination on hit }
while i <> N do
if string[i+1]=ch then N := i else i := i+1;
{ -- Test termination state }
if i <> hi then find := i+1 else find := -maxint
end{ find};
begin
{ -- Test cases }
writeln(Output,
find('!', 'Forced termination is a good thing!'):1,
' ',
find('?', 'There is no question mark in this string')
)
end.
----------
ps. am really ian@ux.cs.man.ac.uk but am experiencing trouble posting from there.chris@umcp-cs.UUCP (Chris Torek) (08/08/86)
In article <871@minster.UUCP> idc@minster.UUCP (idc) writes: >Below is a little program in ISO level 1 Pascal that >illustrates [a] method [of forced termination of linear search]. > >Here is the example dressed up as a "find a character in a string" function. > >function find(ch:Char; string: packed array[lo..hi:Integer] of Char):Integer; >{ >* pre: lo > -maxint >* post: if find(ch,string) = -maxint then true else string[find(ch,string)]=ch >} > var > i, N: Integer; >begin > { -- Initialise loop variables } > i := lo-1; N := hi; > { -- Linear search with possible forced termination on hit } > while i <> N do > if string[i+1]=ch then N := i else i := i+1; > { -- Test termination state } > if i <> hi then find := i+1 else find := -maxint >end{ find}; Actually, I am not entirely satisified with any of these notations. If I were instructing a person to find an object, I might say something like `search starting at low and going forward, until either you find it or you get to hi'; so in a computer language, I might prefer, e.g.: { return the position of the specified character in the given string, or -maxint if not found } function find(ch: char; string: packed array[l..h: integer] of char): integer; var i, answer: integer; begin { assume it will not be found } answer := -maxint; { iterate only until it is found } for i in [l..h] until answer <> -maxint do if string[i] = ch then answer := i end for; find := answer end; This puts the termination condition directly in the `for' loop. I think (I am at home or I would check) that the language Mesa, developed by Xerox, has a loop of this form (indeed, the loop can declare `i' as well, just for the duration of the loop itself, which is also appropriate)---though in Mesa one would be more likely to write -- apologies for syntax; it has been a while find: PROC [ch: CHAR, string: LONG STRING] RETURNS [pos: CARDINAL, found: BOOL]; BEGIN FOR i:CARDINAL in [0..String.Length[string]] DO IF string[i] = ch THEN RETURN [i, TRUE]; ENDLOOP; RETURN [0, FALSE]; END; -- In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 1516) UUCP: seismo!umcp-cs!chris CSNet: chris@umcp-cs ARPA: chris@mimsy.umd.edu
zben@umd5 (Ben Cranston) (08/09/86)
In article <2785@umcp-cs.UUCP> chris@maryland.UUCP (Chris Torek) writes: > find: PROC [ch: CHAR, string: LONG STRING] > RETURNS [pos: CARDINAL, found: BOOL]; > BEGIN > FOR i:CARDINAL in [0..String.Length[string]] DO > IF string[i] = ch THEN RETURN [i, TRUE]; > ENDLOOP; > RETURN [0, FALSE]; > END; I always avoided these nonstandard returns because they make it painful to drop in debug print statements. I would always slap in WRITELN(MYARGS) at the top, and WRITELN('Returning from FIND') at the bottom, and wonder why I never saw the 'Returning from FIND' output... If you are trying to find an infinite loop this can be really misleading. -- umd5.UUCP <= {seismo!umcp-cs,ihnp4!rlgvax}!cvl!umd5!zben Ben Cranston zben @ umd2.UMD.EDU Kingdom of Merryland Sperrows 1100/92 umd2.BITNET "via HASP with RSCS"
bzs@bu-cs.BU.EDU (Barry Shein) (08/09/86)
> for i in [l..h] until answer <> -maxint do > >I think (I am at home or I would check) that the language Mesa, >developed by Xerox, has a loop of this form... You will find a rich set of loop constructs like this in PL/I, eg: DO I = START TO END WHILE FLAG ^= FALSE ; etc etc. -Barry Shein, Boston University