Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!caip!sri-spam!mordor!lll-crg!seismo!umcp-cs!chris
From: chris@umcp-cs.UUCP (Chris Torek)
Newsgroups: net.lang.pascal
Subject: Re: Linear search again
Message-ID: <2785@umcp-cs.UUCP>
Date: Thu, 7-Aug-86 17:54:55 EDT
Article-I.D.: umcp-cs.2785
Posted: Thu Aug  7 17:54:55 1986
Date-Received: Sat, 9-Aug-86 07:37:59 EDT
References: <871@minster.UUCP>
Reply-To: chris@maryland.UUCP (Chris Torek)
Organization: University of Maryland, Dept. of Computer Sci.
Lines: 67

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