For any result of grepping (1..) (with a predicate which always> terminates, say), you can do this. If C<grep { g($_) } (1..)> is> nonempty, then it has a first element; we can find this first element> by running essentially this:>
for(my $n=1; ; $n++) {> last if g($n)> }>
Note that this even works if g(n) is true for infinitely many> (positive) values of n.>
And so you can say for (..-1): for(my $n=-1; ; $n--) { last if g($n); }
Of course, perl has to know this is a list with no left operand (rather than no right operand), so any ordering has to be reversed at the end.
Now, note that _both_ these pieces of code fail to work if: - grep is called not in a boolean context, but in a list context... how do we know when we've found the last valid item? - the test is never true, such as grep __<-1 (1..)
There is nothing fundamentally different about the two cases. If I haven't convinced you yet, consider that you can _always_ map (where $y>$x): push @i, $_ if f($_) for ($y..$x); to: reverse (push @i, $_ if f($_) for ($x..$y)); and then consider that: (..-1) == map -__ (1..); as you've noted yourself previously. Therefore there is a one to one mapping between implementations of (1..) and (..-1).
So to summarise my last few posts, my argument goes: - If you can implement (1..) then you can implement (..-1) - If you can implement (..-1) then you can implement (..) - Damian says that we can implement (1..) (although there's more RFCs coming to confirm this). Let's assume he's right - Therefore we can implement (..) - Perl should work how you expect - If (1..) works, you expect (..-1) to work - If (1..) and (..-1) work, you expect (..) to work - Therefore RFC 24 should be adjusted to propose semi-finite lists with either operand to '..' missing, and infinite lists with both operands missing.
Feel free to email me directly if you want clarification of any of this argument.
That really confuses me. If the sequence (-4..-1) is (-4, -3, -2, -1) then I don't see how your semantics are consistent. I'll admit (reverse map -__ (1..)) is the same as (..-1) but reverse on a stream is undefined. (It should be a run-time error.)
Streams must have a head. Infinite sequences in general don't need a head, but streams IMHO aren't general infinite sequences.
One thing that would make sequences composed with .. more useful would be to allow the right hand side to be a function of one argument. Then the set of all negative numbers is (-1..__-1) which is the same as map -__ (1..). The set of all integer powers of two is (1..__*2). (But map __*2 (1..) is the set of all positive even numbers.) Another cool sequence is (1..__*-1+1) which alternates (1, 0, 1, 0, 1, ...). (Damian probably already thought of this though. I should go read RFC 24.)
Ken Fox wrote:> Jeremy Howard wrote:> > (..-1) == map -__ (1..);>
That really confuses me. If the sequence (-4..-1) is (-4, -3,> -2, -1) then I don't see how your semantics are consistent. I'll> admit (reverse map -__ (1..)) is the same as (..-1) but reverse> on a stream is undefined. (It should be a run-time error.)>
Yes, they're not identical. What I mean of course is: (..-1) == reverse(map -__ (1..));
But my point is that the programmer shouldn't have to bother with this detail. If you write (..-1) perl knows what you mean.
Streams must have a head. Infinite sequences in general don't need> a head, but streams IMHO aren't general infinite sequences.>
I know MJD talked of streams and infinite lists as being interchangable concepts, but the notion that @list = ($head, promise()) is just one potential implementation. We _can_not_ actually use an infinite (or semi-finite) list until we reduce it (through filtering [eg grep], or mathematical combination [eg sum], or some combination). We can only reduce an infinite list under one of the following restrictions: 1- We know the domain under which the predicate used in the filter is true, or 2- We know a mathematical 'short-cut' such as 'sum of a geometric series = a/(1-r)'
There is no general way of finding a 'short-cut' for reduce(f(__,__), @a), so we can't expect perl to deal with (2) for us. Therefore (1) is the only restriction we can use, and therefore: * We can not use an infinite list until we define a finite domain of its indexes.
We can define this domain through some kind of 'stopping criteria'. Possible criteria types include: - Define the range of the indexes to test - Define the number of items to return - Define the time to search for.
If you accept that we need to define a domain to reduce a list, then you can see that we can usefully talk of reverse(map -__ (1..)), because reverse() is evaluated lazily and can be applied once the finite domain is known.
Note that under my definition of what you can do to a list (you must reduce it before you output it), the following is not valid perl: print (1..); # Error, attempt to output infinite list
You could argue that, procedurally speaking, this has some meaning because you can signal to perl when you want it to stop outputting. But this argument comes from thinking of (1..) as a stream, which it's not, it's a list.
One thing that would make sequences composed with .. more useful> would be to allow the right hand side to be a function of one> argument. Then the set of all negative numbers is (-1..__-1) which> is the same as map -__ (1..). The set of all integer powers of two> is (1..__*2). (But map __*2 (1..) is the set of all positive even> numbers.) Another cool sequence is (1..__*-1+1) which alternates> (1, 0, 1, 0, 1, ...). (Damian probably already thought of this> though. I should go read RFC 24.)>
I certainly think it would be nice to say: (1..:3) where ':3' defines a step size. But then I guess you're saying this generalises to: (i0..:f(__)) == i0, f(i0), f(f(i0), ... (Note that I'm keeping the ':' notation, because then it's clear that we're talking about a generation rule, not an upper bound). Now I write it like this, wouldn't it be nice if we could also say: (1..:f(__)) == apply(f(__), (1..); # But I digress!
(Note that I'm keeping the ':' notation, because then it's clear that
we're> talking about a generation rule, not an upper bound). Now I write it like> this, wouldn't it be nice if we could also say:> (1..:f(__)) == apply(f(__), (1..); # But I digress!> Correction (sorry). This should be: (1..:f()) == (1) . map {apply(f(__), (1..$_))} (1..);
Anyway, just ignore this nomenclature for a moment. Christian Soeller has got an RFC coming up on slicing semantics from which I've developed some better ideas on creating generating functions. I'll post these as replies to that RFC when it appears.
This is another straightforward "forwards list"; it has the order type> of (1..), not of (..-1).>
Please post examples of places where "generalised lists" of other> order types are useful.>
OK, give me a moment. I'm writing an RFC for list generators with some of the PDL folk, and I'll make sure there's a "backwards list" example in there. It's no big deal though, I don't mind writing: reverse (map {-$_} (1..)); if I have too.
<...>>
MJD has a perl5 package which does memoization; this is exactly what> you want.>
There seems to be an opportunity to integrate generators, iterators, memoizaion and lists nicely, with very little new syntax. This is what I'm trying to investigate here. Also, perl might be able to do some optimisations for us (such as the 'Orcish maneuver') if it knew about this stuff.
Damian Conway sent the following bits through the ether:
Rather than continue to argue the details, why don't people post some> examples of code where they feel these lazy lists might be useful, and> let's see if there aren't already good alternatives.
It should be noted that "infinite" lazily-evaluated lists can be used in Perl 5 in a perlish way with careful use of Tie::Array and closures.
I've got an example of this in my poorly-coded Functional module[1], which allows things like:
take(10, filter("prime", integers))
[yes, that is perl ;-] ... (which is done lazily)
Anything to make this easier to do in Perl 6 is welcomed
John Porter wrote:> Jeremy Howard wrote:> > Yes, they're not identical. What I mean of course is:> > (..-1) == reverse(map -__ (1..));>
WHAT? So the semantics of .. are magically different in the context> of (..$n) so as to produce numbers in descending order?
Both of those expressions are the infinite list (-infinity..-1). I have no idea how to write that properly 'cause I'm not a math guy. These things aren't streams (infinite queues) -- they're infinite stacks. I'm not sure they have a name in computer science.
Somebody proposed that we have lists that are infinite in both directions, but I'm having trouble understanding how those would be useful. Anybody want to take a few minutes to teach the math-impaired among us?
Ken Fox wrote:> John Porter wrote:> > Jeremy Howard wrote:> > > Yes, they're not identical. What I mean of course is:> > > (..-1) == reverse(map -__ (1..));> >
WHAT? So the semantics of .. are magically different in the context> > of (..$n) so as to produce numbers in descending order?>
No. They're in ascending order.
map {-$[0]} (1..)
is in descending order. That's way the reverse() is there.
Both of those expressions are the infinite list (-infinity..-1). I have> no idea how to write that properly 'cause I'm not a math guy. These> things aren't streams (infinite queues) -- they're infinite stacks. I'm> not sure they have a name in computer science.>
In functional programming they're just called 'lists'!
Somebody proposed that we have lists that are infinite in both> directions, but I'm having trouble understanding how those would be> useful. Anybody want to take a few minutes to teach the math-impaired> among us?>
'Twas me! Mathematicians don't restrict themselves to working with the natural numbers... we like numbers less than zero too! (...and rationals, complex numbers, etc...) Sometimes these numbers are a set, and sometimes they're an ordered list. These lists or sets need not be finite in size (in fact no mathematician would be caught dead discussing finite numbers
Maybe this will all make sense next Monday when PDL-Porters submit their Numerical Perl RFCs... One of those RFCs (if I get my way!) will propose a more general mechanism for generating lists that extends the '..' operator.
<Warning: lengthy spiel coming...>
When it comes down to it, anything you can do with a list, you can do with a function. A list is really a mapping of the natural numbers on to some range, and a function is a description of a mapping too (although their domain is not restricted to natural numbers). For instance:
TMTOWTDI! We already know finite lists are nice to have though, because they allow more compact and intuitive notation than using functions all the time, and they allow perl to do all kinds of optimisations. Of course, a nice side effect of lists is that we can do stuff to all of them at once:
@b = map {$_+1} @a;
Which with a subroutine requires explicitly stating the domain by creating a loop:
Many mathematical algorithms deal with many different domains of the same infinite list while they're doing their thing. This kind of notation makes these algorithms much easier to write.
Another side effect of lists generated by a function is that even although they're lazily evaluated (they have to be, or it takes a little to long to create an infinite list!), they guarantee that their results are stable. That is, if $a[2] == 3 at one point, is will continue to equal 3 as long as @a is not redefined. This means that generated lists can be automatically memoized, which is a big win for many algorithms.
Both of those expressions are the infinite list (-infinity..-1). I have> no idea how to write that properly 'cause I'm not a math guy. These> things aren't streams (infinite queues) -- they're infinite stacks. I'm> not sure they have a name in computer science.
O.k., here's the basic question. (If someone has already answered this, I didn't find it satisfactorily comprehensible. Assume I'm an idiot.)
What would be the output of the following program:
$\ = "\n"; $i = 0; for ( .. -1 ) { $i++; last if $i > 2; print }
If the answer is (as I suspect), "This never prints anything; it goes into an infinite loop just trying to generate the first number", then the proposal is absurd and should be scrapped.
What would be the output of the following program:> >
$\ = "\n";> > $i = 0;> > for ( .. -1 ) {> > $i++;> > last if $i > 2;> > print > > }> >
If the answer is (as I suspect), "This never prints anything; it goes> > into an infinite loop just trying to generate the first number", then> > the proposal is absurd and should be scrapped.>
By my understanding (which is definitely not very thorough), the output would> be a run-time error.
If the answer is (as I suspect), "This never prints anything; it goes> > > into an infinite loop just trying to generate the first number", then> > > the proposal is absurd and should be scrapped.> >
By my understanding (which is definitely not very thorough), the output would> > be a run-time error. >
What error message? "Program never halts!" ???
. I don't know, really. This proposal, while interesting to me, isn't mine and is pretty much a new thought. My guess would be that the actual list implementation would be to not unroll anything until it was needed and so the print or the for would notice that the output is still based on "coming from infinity" and would die.
I understand very well the concern. I, for one, don't agree that having (1..) in the language implies that having (..-1) is possible (though it does make sense to me that having (1..) and (..-1) would imply having (..)). After all, if I were to write
for (1..) { print; }
I would get an infinite loop, but one which was doing something, whereas
for (..-1) { print; }
would either have to error out, count backwards from -1 or go into an infinite loop trying to find the beginning. Perhaps one of the proponents can enlighten us. After all, even mathematical induction cannot generate all the elements of (..-1) unless it starts at -1 and goes backward.
Ted -- Ted Ashton (ashted@southern.edu), Info Sys, Southern Adventist University ========================================================== Whereas at the outset geometry is reported to have concerned herself with the measurement of muddy land, she now handles celestial as well as terrestrial problems: she has extended her domain to the furthest bounds of space. -- Frankland, W.B. ========================================================== Deep thoughts to be found at http://www.southern.edu/~ashted
Tangentialy, can I suggest that a nicer synthax might be -Inf..-1 / 1..Inf, etc.
Assuming that we end up supporting full IEEE floats, this becomes the "obvious" synthax, and I find C<(-Inf..Inf)> to be far more clear then C<(..)>. We've got plenty of puncuation already, thank you very much.
Also, can someone please suggest a reasonable implementation of (-Inf...-1)? If not, can I suggest that we require that if one of the arguments to (list) .. s +/-infinity, it be the second one, and additionaly say that a..b is the list , a+1, a+2, ... b if b>a, and a, a-1, a-2, ... b if a>b. This would allow the full expressiveness of both (-inf..0) and (0..inf) without ever having an infinite starting point to a list.
(If a..b where a==b, then we get the list containing only a.)
In any case, (-inf...-1) would "obviously" either: begin with the smallest negitive integer representable, or begin with the IEEE -inf. If it begins with the IEEE -inf, then it has to continue with an infinite number of -infs, since -inf+1=-inf (a rule of IEEE arithmitic).
Ergo, it is useless to begin at -inf unless perl6 becomes _very_ good at finding out what you "really" meant. OTOH, having it begin with the smallest non-(negitive)infinite value means that it becomes non-infinite, IE scalar((-inf..0)) != inf. This is obviously a Bad Thing. Also, if bignums are intergrated (as has been proposed), then there is no smallest representable integer.
(This assumes that the float synthax will be extended to include "NaN" and "Inf" as valid floating-point numbers. (This does take away from non-reserved namespace.) Has this been proposed yet?)
Jeremy Howard 10 August 2000 00:40:19 [ permanent link ]
Ted Ashton wrote:> Thus it was written in the epistle of John Porter,> > Ken Fox wrote:> > >
Both of those expressions are the infinite list (-infinity..-1). I
have> > > no idea how to write that properly 'cause I'm not a math guy. These> > > things aren't streams (infinite queues) -- they're infinite stacks. I'm> > > not sure they have a name in computer science.> >
O.k., here's the basic question. (If someone has already answered this,> > I didn't find it satisfactorily comprehensible. Assume I'm an idiot.)> >
What would be the output of the following program:> >
$\ = "\n";> > $i = 0;> > for ( .. -1 ) {> > $i++;> > last if $i > 2;> > print> > }> >
If the answer is (as I suspect), "This never prints anything; it goes> > into an infinite loop just trying to generate the first number", then> > the proposal is absurd and should be scrapped.>
By my understanding (which is definitely not very thorough), the output
would> be a run-time error.
That's my understanding too. I'm trying to pull together a more complete proposal that describes under what conditions a list can or can not be used without specifying its domain (amongst other things). Bear with me for a day or two...
Jeremy Howard 10 August 2000 00:52:15 [ permanent link ]
Ted Ashton wrote:> I understand very well the concern. I, for one, don't agree that having> (1..) in the language implies that having (..-1) is possible (though it does> make sense to me that having (1..) and (..-1) would imply having (..)). After> all, if I were to write>
for (1..) {> print;> }>
I would get an infinite loop, but one which was doing something, whereas>
for (..-1) {> print;> }>
The reason that having (1..) implies having (..-1) is that if you allow (1..), then this is a valid construct:
@dot_dot_neg_one = reverse (map {-$_} (1..));
which is identical to (..-1)! So scrapping (..-1) doesn't actually win you anything, in terms of avoiding 'impossible loops'.
The only way around all this, IMO, is to require that the domain of indexes of an infinite loop be specified before the list is output in any way. 'Output' includes reduction of the list (see RFC 76). The domain could be specified explicitly, or could in some cases be derived by Perl implicitly from the context of the expression.
Thus it was written in the epistle of Jeremy Howard,> The reason that having (1..) implies having (..-1) is that if you allow> (1..), then this is a valid construct:>
@dot_dot_neg_one = reverse (map {-$_} (1..));>
which is identical to (..-1)! So scrapping (..-1) doesn't actually win you> anything, in terms of avoiding 'impossible loops'.>
The only way around all this, IMO, is to require that the domain of indexes> of an infinite loop be specified before the list is output in any way.> 'Output' includes reduction of the list (see RFC 76). The domain could be> specified explicitly, or could in some cases be derived by Perl implicitly> from the context of the expression.
I'm looking forward to the upcoming writeup .
Ted -- Ted Ashton (ashted@southern.edu), Info Sys, Southern Adventist University ========================================================== If others would but reflect on mathematical truths as deeply and as continuously as I have, they would make my discoveries. -- Gauss, Karl Friedrich (1777-1855) ========================================================== Deep thoughts to be found at http://www.southern.edu/~ashted
Thus it was written in the epistle of Damian Conway,> > I'm looking forward to the upcoming writeup .>
I'm thinking of recanting the whole RFC!
<*checking etymology*> hmmm . . . "recant" . . . "recant" . . . doesn't that mean to sing the whole thing over again?
, Ted
P.S. Seems to me that while putting hooks in the core to allow this sort of thing might be worthwhile, infinite lists are not likely to be commonly used and so probably should go into a module. -- Ted Ashton (ashted@southern.edu), Info Sys, Southern Adventist University ========================================================== You know that I write slowly. This is chiefly because I am never satisfied until I have said as much as possible in a few words, and writing briefly takes far more time than writing at length. -- Gauss, Karl Friedrich (1777-1855) ========================================================== Deep thoughts to be found at http://www.southern.edu/~ashted
Damian Conway 10 August 2000 01:34:16 [ permanent link ]
I'm thinking of recanting the whole RFC! >
<*checking etymology*> hmmm . . . "recant" . . . "recant" . . . > doesn't that mean to sing the whole thing over again?
Literally: "to sing a different tune".
Seems to me that while putting hooks in the core to allow this sort > of thing might be worthwhile, infinite lists are not likely to be > commonly used and so probably should go into a module.
Agreed. I hereby bequeath the rewrite to someone else.
Jeremy Howard wrote:> The reason that having (1..) implies having (..-1) is that if you allow> (1..), then this is a valid construct:>
@dot_dot_neg_one = reverse (map {-$_} (1..));>
which is identical to (..-1)!
No, NOT identical. The same set of numbers, yes, but generated in the opposite order. (..-1) should generate -INF first, but obviously it can't do that. (..$n) is an impossible construct, and should be a fatal error -- presuming it even gets past the lexer...
Jeremy Howard 11 August 2000 01:34:50 [ permanent link ]
John Porter wrote:> Jeremy Howard wrote:> > The reason that having (1..) implies having (..-1) is that if you allow> > (1..), then this is a valid construct:> >
@dot_dot_neg_one = reverse (map {-$_} (1..));> >
which is identical to (..-1)!>
No, NOT identical. The same set of numbers, yes, but generated in> the opposite order. (..-1) should generate -INF first, but obviously> it can't do that. (..$n) is an impossible construct, and should be> a fatal error -- presuming it even gets past the lexer...>
Well, maybe... If you think the idea of 'generation order' is meaningful. I would have thought that it should look like all the elements are generated together--since I don't think we want to confuse lists and streams.
Anyhow, maybe this is a moot point. Damian's recanted his RFC, and I'm still trying to decide whether this is important enough to finish off a redraft of it that I started...
If you would like to report an abuse of our service, such as a spam message, please . Если Вы хотите пожаловаться на содержимое этой страницы, пожалуйста .
