Re: Infinite lists (was Re: RFC 24 (v1) Semi-finite (lazy) lists)
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...
--
John Porter
Re: Infinite lists (was Re: RFC 24 (v1) Semi-finite (lazy) lists)
Ted Ashton wrote:
John Porter:
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.
What error message? "Program never halts!" ???
--
John Porter
Re: Infinite lists (was Re: RFC 24 (v1) Semi-finite (lazy) lists)
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 ba, and a, a-1, a-2, ... b if ab. 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?) -=- James Mastros, In slightly over his head.
Re: Infinite lists (was Re: RFC 24 (v1) Semi-finite (lazy) lists)
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...
Re: Infinite lists (was Re: RFC 24 (v1) Semi-finite (lazy) lists)
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.
Re: Infinite lists (was Re: RFC 24 (v1) Semi-finite (lazy) lists)
I'm looking forward to the upcoming writeup :-). I'm thinking of recanting the whole RFC! :-) Damian
Re: Infinite lists (was Re: RFC 24 (v1) Semi-finite (lazy) lists)
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 ([EMAIL PROTECTED]), 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
Re: Infinite lists (was Re: RFC 24 (v1) Semi-finite (lazy) lists)
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. Damian
Re: Infinite lists (was Re: RFC 24 (v1) Semi-finite (lazy) lists)
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:
@a = (-2,4,10);
maps 1--2, 2-4, 3-10. Or as a function:
$a = sub {$[0]==0 ? -2 : $[0]==1 ? 4 : $[0]==2 ? 10 : die};
or as a higher order function (with shiny new prefixes!):
$a = ^_ == 0 ? -2 : ^_ == 1 ? 4 : ^_ == 2 ? 10 : die;
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:
for ($i=0; $i++; $i=2) {
$b[$i] = $a-($i) + 1;
}
The same argument is true of infinite lists:
@a = (1..:3);
might create an infinite list (1,4,7,...) if we allow slicing syntax. Then
most conveniently we can say:
@firstColOfMatrix = @Some3ColMatrix(@a);
without having to loop explicitly. That's still a list of positive integers,
of course, but we need not restrict ourselves:
@a = (-1..:-0.1); # (-1, -1.1, -1.2, ...)
and later we can reduce this neatly:
$sumOf1st10 = sum(@a, 0, 9); # Assumes sum(@list,$startIdx,$endIdx)
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.
Re: Infinite lists (was Re: RFC 24 (v1) Semi-finite (lazy) lists)
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 ;-)
Leon
[1] http://www.astray.com/Functional/
--
Leon Brocard.http://www.astray.com/
yapc::Europe - September 22-24 London - http://yapc.org/Europe/
... Error 404: .signature generator ran out of tuits
Re: Infinite lists (was Re: RFC 24 (v1) Semi-finite (lazy) lists)
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? I don't think so. -- John Porter
Infinite lists (was Re: RFC 24 (v1) Semi-finite (lazy) lists)
For any result of grepping (1..) (with a predicate which always
terminates, say), you can do this. If Cgrep { 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.
Re: Infinite lists (was Re: RFC 24 (v1) Semi-finite (lazy) lists)
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! Yes, that would be pretty cool.
Re: Infinite lists (was Re: RFC 24 (v1) Semi-finite (lazy) lists)
I think I opened a bigger can of worms than I intended :-) As MJD as pointed out to me in private email, if we are serious about this feature, we probably want to go the whole hog and look at Haskell's notion of list comprehensions. See http://www.haskell.org/tutorial/goodies.html specifically, section 2.4.1. NOTE: MJD didn't *support* any of this, he merely pointed it out. Personally, I intend only to update the RFC to include the *possibility* of (..$x) and (..). I'm reasonably sure Larry will kill the whole thing -- I think I might too, were I in his place ;-) 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. Damian
Re: Infinite lists (was Re: RFC 24 (v1) Semi-finite (lazy) lists)
(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.
Re: Infinite lists (was Re: RFC 24 (v1) Semi-finite (lazy) lists)
Damian Conway wrote: I think I opened a bigger can of worms than I intended :-) Yes, sorry about the overload of email you must of got from me on this, this morning ;-) As MJD as pointed out to me in private email, if we are serious about this feature, we probably want to go the whole hog and look at Haskell's notion of list comprehensions. See http://www.haskell.org/tutorial/goodies.html Exactly right. Haskell provides some great ideas, although there's more perlish ways of thinking about it (give me a moment, I'll get back to them...) Personally, I intend only to update the RFC to include the *possibility* of (..$x) and (..). I'm reasonably sure Larry will kill the whole thing -- I think I might too, were I in his place ;-) Now don't encourage its death already! Still, I'm glad you're prepared to keep it open. 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. OK, you're on. But infinite lists (can I say that?... 'semi-finite' is a bit weird) are one part of a bigger picture, so let me show you some code that also incorporates higher-order functions, and an extension to Christian Soeller's upcoming RFC on notation for slicing. @matrix = (1,3,4,2,6,7); # actually a flattened version of [[1,3,4],[2,6,7]] @column1of3 = (1:3:); # Creates an infinite list (1,4,7,...) print sum(@matrix[@column1of3]); # Prints 3 @matrix2 = readReallyBig3ColumnMatrixFromSomewhere(); $column1Sum = sum(@matrix2[@column1of3]); # Handy, no need to redefine our slice! So, it provides some nice slicing notation. Note that more complex slicing, masking, and indirection across n-dimensional tensors would make the win of not having to respecify the indexes more substantial. But I'm trying to keep the examples simple here... Another win is in evaluation of lists constructed by generator functions: # ($start: f(__): $end) == ($start, f($start), f(f($start)), ...) @powersOf2 = (1:__*2:); # (1, 2, 4, 8, ...) @first10PowersOf2 = @powersOf2[0..9]; # Calculates 1st 10 powers of 2 # ...interesting manipulation of @first10PowersOf2... @first20PowersOf2 = @powersOf2[0..19] # Calculates 2nd 10 powers of 2 (1st 10 are already computed!) The real difference between an infinite list and a function with a domain of the integers (other than notation) is that an infinite list is a guarantee of stability. If we've already calculated @powersOf2[9], we don't have to do it again when we next want it. The same is not true of 2^__, since perl can't know that it returns the same result for every evaluation (for instance, what if it was ^__ ?) You could argue that we could achieve the same with an attribute of a sub, such as 'stable'. This would guarantee that this function returns the same result each time it's called with the same arguments. Then perl would be smart enough to cache the result of calls to this sub to avoid recalculating it again later. Personally, however, I find this approach less intuitive.
Re: Infinite lists (was Re: RFC 24 (v1) Semi-finite (lazy) lists)
"Jeremy Howard" [EMAIL PROTECTED] writes: Damian Conway wrote: [...] Personally, I intend only to update the RFC to include the *possibility* of (..$x) and (..). I'm reasonably sure Larry will kill the whole thing -- I think I might too, were I in his place ;-) Now don't encourage its death already! Still, I'm glad you're prepared to keep it open. Please somebody post some sane semantics for lazy "generalised lists" with any (computable) countable order type. That way lies madness (and no applications that I can think of). 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. OK, you're on. But infinite lists (can I say that?... 'semi-finite' is a bit weird) are one part of a bigger picture, so let me show you some code that also incorporates higher-order functions, and an extension to Christian Soeller's upcoming RFC on notation for slicing. @matrix = (1,3,4,2,6,7); # actually a flattened version of [[1,3,4],[2,6,7]] @column1of3 = (1:3:); # Creates an infinite list (1,4,7,...) print sum(@matrix[@column1of3]); # Prints 3 @matrix2 = readReallyBig3ColumnMatrixFromSomewhere(); $column1Sum = sum(@matrix2[@column1of3]); # Handy, no need to redefine our slice! This is a straightforward "forwards list"; it has the order type of (1..), not of (..-1). [...] Another win is in evaluation of lists constructed by generator functions: # ($start: f(__): $end) == ($start, f($start), f(f($start)), ...) @powersOf2 = (1:__*2:); # (1, 2, 4, 8, ...) @first10PowersOf2 = @powersOf2[0..9]; # Calculates 1st 10 powers of 2 # ...interesting manipulation of @first10PowersOf2... @first20PowersOf2 = @powersOf2[0..19] # Calculates 2nd 10 powers of 2 (1st 10 are already computed!) 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. The real difference between an infinite list and a function with a domain of the integers (other than notation) is that an infinite list is a guarantee of stability. If we've already calculated @powersOf2[9], we don't have to do it again when we next want it. The same is not true of 2^__, since perl can't know that it returns the same result for every evaluation (for instance, what if it was ^__ ?) You could argue that we could achieve the same with an attribute of a sub, such as 'stable'. This would guarantee that this function returns the same result each time it's called with the same arguments. Then perl would be smart enough to cache the result of calls to this sub to avoid recalculating it again later. Personally, however, I find this approach less intuitive. MJD has a perl5 package which does memoization; this is exactly what you want. -- Ariel Scolnicov|"GCAAGAATTGAACTGTAG"| [EMAIL PROTECTED] Compugen Ltd. |Tel: +972-2-6795059 (Jerusalem) \ We recycle all our Hz 72 Pinhas Rosen St.|Tel: +972-3-7658514 (Main office)`- Tel-Aviv 69512, ISRAEL |Fax: +972-3-7658555http://3w.compugen.co.il/~ariels
