Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.perl.misc > #8795

Re: names, values, boxes and microchips

Show all headers | View raw

Ben Morrow <ben@morrow.me.uk> writes:
> Quoth Rainer Weikusat <rweikusat@mssgmbh.com>:
>> Ben Morrow <ben@morrow.me.uk> writes:

[...]

>> This is a simple, well-known algorithm which is part of an elementary
>> sorting algorithm first published 68 years ago and I absolutely don't
>> think inventing a more complicated 'new one', especially if that is
>> also very likely going to be 'less efficient' in the sense that it
>> does more comparisons and/or move operations is appropriate.
>
> I have never questioned the appropriateness of the algorithm. My latest
> example uses the *same* algorithm, it is just (IMHO) a great deal
> clearer about what is happening.

Including the 'shift_while' I counted no less than six loops or 'loopy
constructs' in there. I have - plainly - no idea what this code does
(or would do) and I'm not really interested in determining that,
either: It is exceedingly unlikely that it is an improvement of the von
Neumann algorithm and even if it was, all the complications in order
to avoid something as simple as an addition, a comparison and an
assignment would hardly be worth the effort.

[...]

>> These are not 'callbacks' as they're not passed to other code which
>> 'calls back into the calling code', they're lexicially scoped
>> subroutines performing a part of the algorithm whose details don't
>> matter for 'the main loop', namely, "move to the next item in this
>> list if there is one, otherwise, terminate the loop" which exist so
>> that the same (or an 'almost same') code sequence isn't contained in
>> there in three different places. Instead, it is 'called upon'
>> using a sensible name, ie, 'step_in' for 'step the in list' or
>> 'step_filter' for 'step the filter list'. The names may not be all
>> that sensible but if so, that's because of my lacking English, not
>> because of deficiencies of the idea itself.
>
> Let's look at the main loop from your original post:
>
>     LOOP: {
> 	($rc) = $in_item->net_compare($filter_item);
>
> 	p_alloc('in %s, filter %s, rc %u',
> 		$in_item, $filter_item, $rc);
> 	
> 	given ($rc) {
> 	    when (R_AFTER) {
> 		push(@out, $in_item);
> 		&$step_in;
> 	    }
>
> 	    when ([R_BEFORE, R_SUB]) {
> 		&$step_filter;
> 	    }
>
> 	    when ([R_SAME, R_SUPER]) {
> 		p_alloc('%s: dropping %s (%s)', __func__,
> 			$in_item, $filter_item);
> 		
> 		&$step_in;
> 	    }
> 	}
>
> 	redo;
>     }
>
> When does it terminate? How does it make progress?

In the appropriate way, as indicated by the auxilary subroutines. The
details of 'the appropriate way' don't matter for this loop which is
closer to the abstract algorithm than it could have been when
repeating the mechanics three times.

> It's not even immediately clear it's a *loop*:

With a block label of 'LOOP:' that shouldn't be to difficult to guess.

> while (1) or for (;;) are the conventional idioms.

I've had people complaining about that in the past as well: "But
that's not the way how I would have done it!" is a powerful impediment
to understanding: The guy who always writes for (;;;) will freak out
when seeing 'while (1)' simply because it looks different. Actually,
the guy who always writes 'for (...)' will freak out upon encountering
a loop using while for the first time and will be more strongly inclined to
'fix' the code by bringing it in line with his style of writing than
come to the conclusion that his knowledge of $language is less
complete than it ought to be[*].

[*] I had an excursion into a Lisp implementation written by someone
to support his 'web application development' business a while ago
(incredible as it may sound) and this code was written in a completely
alien style to me. Nevertheless, after understanding what it was doing
for which reasons, I came to the conclusion that - while I would
never write anything in this way - there were no objective reasons for
doing so, just a set of radically different but equally sensible
conventions colliding with some of my (unjustified) prejudices.

> Probably it would have helped to use an ordinary sub with arguments
> rather than trying to be clever with closures, and a return value rather
> than an implicit last. With a call like
>
>     step_array $in, \$in_pos, \$in_item
>         or last;

These aren't closures, either: They exist inside a certain, lexical
environment but don't 'capture' any part of it beyond its 'natural
lifetime'. The fact that the lists this algorithm works with are
represented as arrays are as irrelevant to it as the names of the
variables used to step through them: This is the 'abstraction' you've
repeatedly judged me of being incapable of understanding. It means
leaving out irrelevant details in favor of concentrating on a
higher-level description of what is going on: &$step_in instead of

last LOOP if ++$in_pos == @$in;
$in_item = $in->[$in_pos]

Perl 5.18 adds explicit support for lexically-scoped subroutines
without having to resort to references to anonymous subroutines so
constructs of this kind should become more common in future (IMHO,
they're rarely useful but this case happens to be one of the
exceptions).

[...]

> Even then, this is so close to just being 'shift' that it
> seems like unnecessary reinvention;

'shift' destroys the arrays it works with. I have to keep them intact.

> in fact, I think it's equivalent to
>
>     ($in_pos, $in_item) = each @$in
>         or last;

For the perl I'm mostly interested in (5.10.1), this complains loudly
about the fact that @$in is not a hash. Also, the index variables are
solely used to step through the arrays in a non-destructive way and
since they do make the implementation more complicated, being able to
get rid of them would be good.

Back to comp.lang.perl.misc | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

names, values, boxes and microchips Rainer Weikusat <rweikusat@mssgmbh.com> - 2013-07-16 21:45 +0100
  Re: names, values, boxes and microchips Ben Morrow <ben@morrow.me.uk> - 2013-07-19 17:07 +0100
    Re: names, values, boxes and microchips Rainer Weikusat <rweikusat@mssgmbh.com> - 2013-07-19 17:38 +0100
      Re: names, values, boxes and microchips Rainer Weikusat <rweikusat@mssgmbh.com> - 2013-07-19 19:28 +0100
        Re: names, values, boxes and microchips Ben Morrow <ben@morrow.me.uk> - 2013-07-20 00:11 +0100
          Re: names, values, boxes and microchips Rainer Weikusat <rweikusat@mssgmbh.com> - 2013-07-20 15:02 +0100
            Re: names, values, boxes and microchips Ben Morrow <ben@morrow.me.uk> - 2013-07-20 16:45 +0100
            Re: names, values, boxes and microchips Rainer Weikusat <rw@sapphire.mobileactivedefense.com> - 2013-07-21 11:15 +0100
              Re: names, values, boxes and microchips gamo@telecable.es - 2013-07-21 12:47 +0000
                Re: names, values, boxes and microchips Shmuel (Seymour J.) Metz <spamtrap@library.lspace.org.invalid> - 2013-07-23 07:14 -0400
                Re: names, values, boxes and microchips gamo@telecable.es - 2013-07-23 20:43 +0000
                Re: names, values, boxes and microchips Rainer Weikusat <rweikusat@mssgmbh.com> - 2013-07-24 11:23 +0100
                Re: names, values, boxes and microchips Ben Morrow <ben@morrow.me.uk> - 2013-07-23 23:10 +0100
              Re: names, values, boxes and microchips Ben Morrow <ben@morrow.me.uk> - 2013-07-21 18:01 +0100
                Re: names, values, boxes and microchips Rainer Weikusat <rweikusat@mssgmbh.com> - 2013-07-21 20:53 +0100
                Re: names, values, boxes and microchips Ben Morrow <ben@morrow.me.uk> - 2013-07-21 22:51 +0100
                Re: names, values, boxes and microchips Charles DeRykus <derykus@gmail.com> - 2013-07-21 16:29 -0700
                Re: names, values, boxes and microchips Rainer Weikusat <rweikusat@mssgmbh.com> - 2013-07-22 01:20 +0100
                Re: names, values, boxes and microchips Rainer Weikusat <rweikusat@mssgmbh.com> - 2013-07-22 01:06 +0100
                [OT] naming conventions Rainer Weikusat <rweikusat@mssgmbh.com> - 2013-07-22 10:35 +0100

csiph-web