henry@utzoo.UUCP (Henry Spencer) (10/05/83)
Bill Wulf suggested some years ago that in addition to the FOR loop,
which is good for operating on all elements of a data structure, there
ought to be a FIRST loop for searching data structures:
FIRST i IN something-that-generates-a-sequence-of-values
SUCHTHAT condition
DO
found it
ELSE
not found
END
(Ignore the exact punctuation, it was something like that.) I always
thought this was a pretty neat idea. It's far too late to retrofit
it to C, of course.
--
Henry Spencer @ U of Toronto Zoology
{allegra,ihnp4,linus,decvax}!utzoo!henrydixon@ihuxa.UUCP (10/07/83)
The following article arrived here yesterday: =============================================================================== >>From ihnp4!clyde!floyd!whuxlb!gummo!harpo!decvax!linus!utzoo!henry Wed Dec 31 18:00:00 1969 >>Relay-Version: version B 2.10.1 7/20/83; site ihuxa.UUCP >>Posting-Version: version B 2.10 5/3/83; site utzoo.UUCP >>Path: ihuxa!ihnp4!clyde!floyd!whuxlb!gummo!harpo!decvax!linus!utzoo!henry >>From: henry@utzoo.UUCP (Henry Spencer) >>Newsgroups: net.lang.c >>Subject: the 'broken' statement >>Message-ID: <3232@utzoo.UUCP> >>Date: Tue, 4-Oct-83 18:17:02 CDT >>Article-I.D.: utzoo.3232 >>Posted: Tue Oct 4 18:17:02 1983 >>Date-Received: Thu, 6-Oct-83 01:05:18 CDT >>References: <322@ucbcad.UUCP> >>Organization: U of Toronto Zoology >>Lines: 18 >> >>Bill Wulf suggested some years ago that in addition to the FOR loop, >>which is good for operating on all elements of a data structure, there >>ought to be a FIRST loop for searching data structures: >> >> FIRST i IN something-that-generates-a-sequence-of-values >> SUCHTHAT condition >> DO >> found it >> ELSE >> not found >> END >> >>(Ignore the exact punctuation, it was something like that.) I always >>thought this was a pretty neat idea. It's far too late to retrofit >>it to C, of course. >>-- >> Henry Spencer @ U of Toronto Zoology >> {allegra,ihnp4,linus,decvax}!utzoo!henry >> >> ============================================================================= This proposed construct can be implemented in C as follows: for(first-value-in-sequence-of-values; ;advance-to-next-value) { if(condition) { found it; break; /*stop loop when first value is found *such that 'condition' is satisfied */ } else not found; } This code requires the same number of constructs as that used in the above article and is reasonably straight forward. So, the construct 'FIRST i IN' ... provides only a small marginal gain over existing C features. Maybe this marginal gain is not worth the complications it would add to the C compiler. D A Dixon ihuxa!dixon BTL - IH
guy@rlgvax.UUCP (Guy Harris) (10/10/83)
I suspect the construct
FIRST i IN something-that-generates-a-sequence-of-values
SUCHTHAT condition
DO
found it
ELSE
not found
END
was supposed to be equivalent to
for (first value; ;next value) {
if (condition)
goto found;
}
not found;
goto join;
found:
found it;
join:
not to:
for(first value; ;next value) {
if (condition) {
found it;
break; /*stop loop when first value
*is found such that 'condition'
*is satisfied
*/
} else
not found;
}
I.e., the "found it" and "not found" clauses are executed when the loop
is finished; the first is executed if the loop terminated because the object
was found, and the second is executed if the loop terminated because it ran
out of values. It does require a bunch of "goto"s and is a bit of a pain
to code (no claim is made here whether adding it to C would be a bigger or
smaller pain).
Guy Harris
{seismo,mcnc,we13,brl-bmd,allegra}!rlgvax!guyhenry@utzoo.UUCP (Henry Spencer) (10/12/83)
Alas, Mr. Dixon, you have misunderstood Wulf's "FIRST" loop. The
"not found" part is not executed for each iteration where the
condition is not satisfied -- it is executed ONCE if the loop ends
without finding anything that satisfies the condition. You can't
do this in C without using a goto, introducing an auxiliary variable,
or breaking the whole thing out into a separate function so you can
use return. As I said, it is far too late to introduce this into C,
which is how I feel about most of the suggested changes to C.
--
Henry Spencer @ U of Toronto Zoology
{allegra,ihnp4,linus,decvax}!utzoo!henryaaw@pyuxss.UUCP (10/13/83)
the reasonable extension to C semantics would be:
if ( for (first(); cond(); next();) )
succeed();
else
fail();
with all statements returning a value. sounds real scary -functional
programming anyone- how about:
if (if (a)
b();
else
c();
)
else
0;
Aaron Werman
{eagle|ariel}!pyuxss!aawessick@uiuccsb.UUCP (10/14/83)
#R:utzoo:-323200:uiuccsb:9000003:000:946
uiuccsb!essick Oct 13 13:34:00 1983
Seems to me that the easiest way to implement the "first i in list"
construct in C is the following:
for ( i=0;i < Limit; i++) /* check the candidates */
if ( condition )
break;
if ( i == Limit ) /* or whatever it asumes */
{ /* when it overruns the list */
not found;
}
else
{
found; /* and it is element "i" */
}
If the collection of items to be checked is a linked list, change
the appropriate for conditions and make the found/notfound test
a comparison to NULL.
How would you specify the list? Is it always an array? a linked list?
a binary tree? a completely specified list of simple [== non array]
variables? Have the compiler understand about all these data structures?
Blech.
The only case I can think where this might help is in PASCAL where
you don't have a break statement; PASCAL would benefit more from
adding a break statement than adding this construct.
-- Ray Essick, University of Illinoisguy@rlgvax.UUCP (Guy Harris) (10/14/83)
This message is empty.
henry@utzoo.UUCP (Henry Spencer) (10/16/83)
"How would you specify the list? Is it always an array? a linked list?
a binary tree? a completely specified list of simple [== non array]
variables? Have the compiler understand about all these data structures?
Blech."
Agreed. One of the major weaknesses of the FOR loop in languages like
Pascal is that it cannot be used to scan a non-trivial user-specified
data structure. Both FOR and FIRST loops work much better in a language
like CLU or ALPHARD which explicitly recognizes that such a "scanning"
operation is an important part of a user-constructed data type, and needs
to be explicitly provided for. The preferred approach is to be able to
define "generators" which scan a data structure and feed elements to a
FOR/FIRST loop for processing. E.g., for a tree structure:
FOR element in preorder(treevariable)
...
FIRST element in postorder(treevariable)
...
Note that the generators are defined as part of the data type, and hence
you don't need to retype them (and introduce amusing new bugs) every time
you want them.
If one wanted to introduce the FIRST loop to C (an idea I oppose, on
the grounds that it's a bit late), one could use the same approach as
C's FOR:
first (x = 1; x < TOP; x++)
...
Generators are better, but retrofitting a whole abstract-datatype system
to C is such a major operation that it's hard to call the result C.
--
Henry Spencer @ U of Toronto Zoology
{allegra,ihnp4,linus,decvax}!utzoo!henryandree@uokvax.UUCP (11/03/83)
#R:mi-cec:-17400:uokvax:3000006:000:666 uokvax!andree Nov 1 14:08:00 1983 Dan - Yes, LISP falls into this category. So do BCPL and ALGOLW, for that matter. (How Wirth every managed to fall from ALGOLW to Pascal in one step, I'll never know!). I agree with you about the beauty of this technique. Now, if only I could get one language with clean structure (C & BCPL & BLISS), reasonable typing (ALGOLW & C & some lisps) and this feature. But come, tell us why the C optimizer isn't an optimizer! I know it isn't a global optimizer, but it would seem to be an adequate window optimizer. Don't tell me that you can't do a global optimizer for C; that I know. I'd like to know why the window optimizer isn't an optimizer. Have Fun, <mike