Re: Ruminating RFC 93- alphabet-blind pattern matching
Um. Maybe it was just bad writing on my part, but it does not seem to me that what I already said about RFC 93 in A5 has sunk in at all. Larry
Re: Short-circuiting user-defined operators
On Tue, Apr 01, 2003 at 08:26:38PM -0500, Joe Gottman wrote:
:Is there any way to write a user-defined operator so that it
: short-circuits, like and || ? This might be function trait, for
: instance,
:
: sub infix:!! ($lhs, $rhs) is short_circuit {...}
Honestly, you guys. You make things so hard for yourselves. I don't
see why that wouldn't just be:
sub infix:!! ($lhs, rhs) is equiv(infix:||) {...}
All closures are lazy by definition, and the rhs forces the right
side of !! to be a closure. At worst, we'd have to change sub
to macro to give a special parsing rule to the right side.
Larry
Re: == vs. eq
On Tue, Apr 01, 2003 at 06:39:24PM -0500, Miko O'Sullivan wrote: : Of course, you can also cast the objects to change what type of comparison : you want. So, for example, C$a =:= $b compares the outputs of the : value_for_comparison methods, but C~$a =:= ~$b compares the numification : of the objects, or, to get into the guts of the matter, the objects are : evaluated in numeric context, which causes them to run their overflow : methods for numification, which returns number objects, which then call : their value_for_comparison methods, which return the numbers as : represented by some string which is formatted according to some : unambiguous rule (we already have those unabiguou rules). The problem with this approach is that it assumes you can efficiently return a string to be compared. I'm not sure this is even true of strings, let alone arrays and hashes. When you write: (1..Inf) equal (0..Inf) I'd like Perl to consider that false rather than having a blank look on its face for a long time. It's just a generalization of how eq and cmp give up as soon as they see two different characters in a string. So whatever equivalence and ordering operators we end up with, they had better be able to do lazy comparisons of characters or elements and give up as soon as they know the answer. In fact, they need to be smarter than that if we also want: (0..Inf) equal (0..Inf) to run in finite time. Lazy arrays need to delegate the operation to their underlying generators whenever possible. Larry
Re: == vs. eq
When you write: (1..Inf) equal (0..Inf) I'd like Perl to consider that false rather than having a blank look on its face for a long time. The price of that consideration would be to give the Mathematicians blank looks on *their* faces for a very long time instead. Certainly, they'll be quick to tell you there are just as many whole numbers as naturals. So they won't know what you mean by equal up there. The Engineers might also be perplexed if you make that false, but for rather different reasons. I think that you will have to define your equal operator in a way contrary to their respective expectations, because both have ways of thinking that could quite reasonably lead them to expect the answer to the expression above to come out to be false, not true. Practically speaking, I'm not sure how--even whether--you *could* define it. One is tempted to attempt something like saying that operator equal is true of a *lazy*, *infinite* list if and only if elements 0..N of both lists were each themselves equal, and then only blessedly finite values of N. But where then do you stop? If N is 1, then (1..Inf) and (1..Inf:2) are ok. If N is 2, meaning to check both the first pair from each list and also the second one, they aren't. However, if N is true, (1..Inf) and (1, 2..Inf:2) are certainly ok. In fact, that definition seems trivial to break. Given a known N steps of comparison, the lazy lists (1..Inf) and (1..N-1, (N..Inf:2)) would both test equal in the first N positions and differ in position N+1. Therefore, we can always break any operator that tests the first N positions of both lazy lists, and thus that definition would be wrong. The reason Mr Engineer might expect false would be if they thought you were eventually testing against Inf. Due to his experience in numerical programming, he sees NaN and Inf having certain behaviors that no pure mathematician would even countenance. On a system whose system nummifier knows things like Inf and NaN already, you see this happening even today. Witness real Perl: % perl -e 'printf %g\n, NaN' nan % perl -e 'printf %g\n, 1 + NaN' nan % perl -e 'printf %g\n, 42 * NaN' nan % perl -e 'printf %g\n, Nan == NaN' 0 % perl -e 'printf %g\n, 1+Nan == NaN' 0 % perl -le 'printf %g\n, Inf' inf % perl -le 'printf %g\n, 1+Inf' inf % perl -le 'printf %g\n, 2+Inf' inf % perl -e 'printf %g\n, Inf == Inf' 1 % perl -e 'printf %g\n, Inf == -Inf' 0 % perl -e 'printf %g\n, 1+Inf == Inf' 1 % perl -e 'printf %g\n, Inf + Inf' inf % perl -e 'printf %g\n, Inf * Inf' inf % perl -e 'printf %g\n, Inf / Inf' nan =begin ASIDE Yes, it's platform dependent what you'll get: mach1% perl -le 'printf On $^O, NaN == NaN is %g\n, Nan == NaN' On openbsd, NaN == NaN is 1 mach2% perl -le 'printf On $^O, NaN == NaN is %g\n, Nan == NaN' On linux, NaN == NaN is 0 I believe that's because the libc on openbsd doesn't nummify string NaN to any special IEEE float, whereas the redhate one did. I am truly hoping that on Perl6, comparing apples with greed will mean that you're testing NaN with itself, that testing NaN and *anything* including another Nan with == will get you into trouble no matter what your platform, and that that trouble will be the same irrespective of platform. =end ASIDE In other words, if you treat Inf as any particular number (which Mr Mathematician stridently yet somewhat ineffectually reminds you that are *not* allowed to do!), then you may get peculiar results. Heck, you could probably then get Mr Engineer to agree that the lazy lists (1..Inf) and (0..Inf) are the same in the *last* N positions for all values of N, and since you could just select N to be equal (ahem) to the length (ahem**Inf) of your list, they must be equal. :-) Mr Mathematician, purist that he is, has of course long ago thrown up his hands in disgust, contempt, or both, and stormed out of the room. To him, most of those Perl examples given above were utter nonsense: how can you say 1+Inf? It bothers him to talk about Inf+1, and 1..Inf will be problematic, too, since to say 1..Inf is also to say there must exist some number whose successor is Inf. And of course, there isn't. Which is why Inf is not a valid operand for numerical questions in Mr Mathematician's platonically purist world of ideas. But practical Mr Engineer has defined his own Inf in which you can do limited otherwise apparently numerical operations, because it was *practical* for him to do so. He had work to do, and needed some new rules. While Mr Mathematician won't put up with comparing numbers and infinities, he's quite comfortable with comparing *infinities* themselves. He's comfortable with infinite sets, and he's comfortable with infinite series, too, which is what these lists seem to be. I'm not sure that his experience with infinite series will help us much here, because you see, those
Re: == vs. eq
On Sat, Apr 05, 2003 at 03:22:17PM -0700, Tom Christiansen wrote: When you write: (1..Inf) equal (0..Inf) I'd like Perl to consider that false rather than having a blank look on its face for a long time. The price of that consideration would be to give the Mathematicians blank looks on *their* faces for a very long time instead. Certainly, they'll be quick to tell you there are just as many whole numbers as naturals. So they won't know what you mean by equal up there. Based on his description, he meant element-wise equality. And since the first element of (1..Inf) is 1, and the first element of (0..Inf) is 0, I agree with the result being false. So no blank stare from me (student of mathematics) The length of both will be Inf ofcourse (meaning countably infinite. I don't think we have a need for working with uncountably infinite sets in perl ;-) Practically speaking, I'm not sure how--even whether--you *could* define it. You can define is very easily: two lists are equal if the ith element of one list is equal to the ith element of the other list, for all valid indices i. As for whether you can *evaluate* this test in bounded time, that depends. Computers are incapable of storing truly infinite lists, so the lists will have finite internal representations which you can compare. As for two dynamically generated infinite lists (which you can't easily compare, for example if they're based on external input)... it will either return false in finite time, or spend infinite time on determining they're indeed equal. In other words, if you treat Inf as any particular number (which Mr Mathematician stridently yet somewhat ineffectually reminds you that are *not* allowed to do!), then you may get peculiar results. There is no problem with doing that, as long as you define what you want it to do. Remember, most of mathematics is just an invention of humans :) (crap about testing first/last N elements) testing the first/last N elements is not the same as testing the whole list for all N :) Mr Mathematician, purist that he is, has of course long ago thrown up his hands in disgust, contempt, or both, and stormed out of the room If he has, he's a very narrow-minded Mr Mathematician how can you say 1+Inf? Unless you're speech-impaired, it's not too hard and 1..Inf will be problematic, too, since to say 1..Inf is also to say there must exist some number whose successor is Inf. *cough*bullshit writing the interval 1..infinity is very common I've skipped the rest.. not in the mood... but you make many references to a Mr Mathematician I don't think I want to work with... luckily I haven't seen him around here at the maths faculty -- Matthijs van Duin -- May the Forth be with you!
Re: == vs. eq
On Sun, Apr 06, 2003 at 12:38:29AM +0200, Matthijs van Duin wrote: In other words, if you treat Inf as any particular number (which Mr Mathematician stridently yet somewhat ineffectually reminds you that are *not* allowed to do!), then you may get peculiar results. There is no problem with doing that, as long as you define what you want it to do. Actually, if you really want to do infinities the math-way, then just grab a book on set theory. one thing you might not like however is that when you go beyond the finite, it becomes necessary to differentiate between cardinal and ordinal numbers. That's probably something you don't want to do in perl The IEEE-float-style infinities are quite sufficient for most purposes One thing I agree is that writing 1..Inf is a *bit* sloppy since the range operator n..m normally produces the numbers i for which n = i = m while n..Inf gives n = i Inf but I can live with it -- Matthijs van Duin -- May the Forth be with you!
Re: == vs. eq
Tom Christiansen wrote:
[...]
The price of that consideration would be to give the Mathematicians
blank looks on *their* faces for a very long time instead. Certainly,
they'll be quick to tell you there are just as many whole numbers
as naturals. So they won't know what you mean by equal up there.
[...]
Unless I'm very wrong, there are more whole numbers than natural
numbers. An induction should prove that there are twice as many.
Steffen
--
@n=([283488072,6076],[2105905181,8583184],[1823729722,9282996],[281232,
1312416],[1823790605,791604],[2104676663,884944]);$b=6;@c=' -/\_|'=~/./g
;for(@n){for$n(@$_){map{$h=int$n/$b**$_;$n-=$b**$_*$h;[EMAIL PROTECTED]
0..11;[EMAIL PROTECTED],[EMAIL PROTECTED];[EMAIL PROTECTED]\n[EMAIL PROTECTED];
Re: == vs. eq
You can define is very easily: two lists are equal if the ith element of
one list is equal to the ith element of the other list, for all valid
indices i.
The problem is that you've slipped subtly from a well-known creature, like
1..10, a finite set of ten distinct integers, to a quite a different sort
of beast entirely, 1..Inf, which while notationally similar to the first,
does not share some very fundamental properties. For example, it no longer
has an integral membership count, that is, a length. This is problematic
if one is not quite careful.
As for whether you can *evaluate* this test in bounded time, that depends.
Computers are incapable of storing truly infinite lists, so the lists will
have finite internal representations which you can compare.
Is it possible that finite internal representations will differ in
internal representation yet produce identical series? It seems to me that
some meta-analsys would be required if this is possible. If it is not
possible, then that means that every distinct series has a distinct
internal representation. Certainly this is not true lexically: I can
use many variant lexical representations to produce the same infinite
series. For example:
(1 .. X, X+1 .. Inf)
(1 .. Y, Y+1 .. Inf)
Those define identical list, for any natural numbers X and Y, even as
compile-time constants. However, save for special case of X==Y, I do
not expect their internal representation to be the same.
As for two dynamically generated infinite lists (which you can't easily
compare, for example if they're based on external input)... it will either
return false in finite time, or spend infinite time on determining they're
indeed equal.
I suppose you could classify
(1 .. X, X+1 .. Inf)
(1 .. Y, Y+1 .. Inf)
as dynamically generated infinite lists, but again, given constants X and
Y, they really needn't be. Even a run-time thing like the list (1 .. $X)
shouldn't actually need to spend infinite time on determining its
equivalence to (1 .. $Y). However, there are more interesting
possibilities: generic iterator functions that you repeatedly call and
which produce successors that aren't generally recognizable. Remember the
old flipflop, as in
if ( 1 .. /^$/ ) { }
if ( /foo/ .. /bar/ ) { }
if ( f() .. g() ) { }
You could, a think, have an infinite list that was really some fancy
interface to a dynamic interator of some sort. I know it's interesting,
but whether this would be sufficiently useful to justify its complexity is
rather less obvious. But if you did have such a list, where stepping
down it implicitly called some sort of -ITER method or whatnot, then
for those I could see the intractability of finite evaluation, since it's
perfectly conceivable that it wouldn't terminate. Another pitfall is
non-reproduceability; think about readline() as an iterator on a stream
object whose underlying file descriptor is not seekable. But I'm not sure
that the any of the sorts of lists we've been talking about have to have
that problem. But I don't know whether we can be clever enough to step
around infinite evaluation through some sort of higher-level analysis.
A clever compiler could move things around. Maybe it could change
for ($i = 1; $i = 10_000; $i++)
into
for $i ( 1 .. 10_000 )
and then perhaps take advantage of that construct's lazy evaluation.
Given general purpose lazy evaluation, you could start doing things
like thinking of
for ($i = 1; $i = fn(); $i++)
for $i ( 1 .. fn() )
and making instead a list or array whose members are
( 1 .. fn() )
However, do you evaluate fn() only once or repeatedly?
Hm.
If it were repeatedly, then I do see what you mean by dynamically
generated infinite lists.
In other words, if you treat Inf as any particular number (which Mr
Mathematician stridently yet somewhat ineffectually reminds you that are
*not* allowed to do!), then you may get peculiar results.
There is no problem with doing that, as long as you define what you want
it to do.
Well, sure, you could let Inf = MAXINT + 1 for example, and then define
things as you want them to act, but that doesn't mean that this resulting
Inf is either what people think of as a Number nor what they think of as
Infinity. See below on IEEE, which found it very useful to something of
the like.
Remember, most of mathematics is just an invention of humans :)
I believe we are indeed trying to define what we want it to do, no?
So sure, you can create a new infinite set by conjoining some new elements
to an existing one. That's what all the numberic sets are, pretty much.
Do be careful that the result has consistent properties, though.
(crap about testing first/last N elements)
testing the first/last N elements is not the same as testing the whole list
for all N :)
Mr Mathematician, purist that he is, has of course long ago thrown up his
hands in disgust, contempt, or both, and stormed out of the room
Re: == vs. eq
Unless I'm very wrong, there are more whole numbers than natural numbers. An induction should prove that there are twice as many. We're probably having a language and/or terminology collision. By natural numbers, I mean the positive integers. By whole numbers, I mean the natural numbers plus the number zero. Since both sets have infinite members, each has just as many members as the other has. It just *looks* like the whole numbers have one more. But they don't, you know, because Inf+1 == Inf, as IEEE shows us in their seminal treatise on How to Lie With Computers under IEEE Floating Point. It's not really relevant to figuring out how to evaluate equality testing on unbounded lists in Perl, but I think that your inductive proof would lead you to conclude the opposite of what you're thinking. You can pick a first member of both sets. Then you can pick a second member of both sets. Then a third, then a fourth, and so and so forth for all cardinal numbers. Even though your list of pairings one from each set itself stretches to infinity (not that that means it actually stops somewhere, of course, as though infinity were a place; I mean it just stretches ever upwards without bound), then I think induction will convince you that in the resulting pair-list, there are no missed members from either set. So we are comfortable saying that there are just as many of one as the other; well, *I* am comfortable saying that, at least, and I hope you are, too. :-) It's initially a bit disturbing, though, when you realize that this necessarily leads to saying there are just as many multiple of two as there are of, oh, eight. Maybe that's why Cantor died mad. :-) --tom
Re: == vs. eq
The IEEE-float-style infinities are quite sufficient for most purposes One thing I agree is that writing 1..Inf is a *bit* sloppy since the range operator n..m normally produces the numbers i for which n = i = m while n..Inf gives n = i Inf but I can live with it I could sure save myself a lot of typing by reading ahead to message N+1 before answering message N. :-) --tom PS: For all N. :-):-)
Re: == vs. eq
On Sat, Apr 05, 2003 at 03:22:17PM -0700, Tom Christiansen wrote: : When you write: : : (1..Inf) equal (0..Inf) : : I'd like Perl to consider that false rather than having a blank look : on its face for a long time. : : The price of that consideration would be to give the Mathematicians : blank looks on *their* faces for a very long time instead. Certainly, : they'll be quick to tell you there are just as many whole numbers : as naturals. So they won't know what you mean by equal up there. Eh? Why should a mathematician jump to the conclusion that I'm comparing sizes of the ordered lists rather than comparing the individual elements? : The Engineers might also be perplexed if you make that false, but : for rather different reasons. I think that you will have to define : your equal operator in a way contrary to their respective : expectations, because both have ways of thinking that could quite : reasonably lead them to expect the answer to the expression above : to come out to be false, not true. Er, it *is* false, not true. I guess that makes me an Engineer. :-) : Practically speaking, I'm not sure how--even whether--you *could* : define it. One is tempted to attempt something like saying that : operator equal is true of a *lazy*, *infinite* list if and only : if elements 0..N of both lists were each themselves equal, and : then only blessedly finite values of N. : : But where then do you stop? If N is 1, then (1..Inf) and (1..Inf:2) : are ok. If N is 2, meaning to check both the first pair from each : list and also the second one, they aren't. However, if N is true, : (1..Inf) and (1, 2..Inf:2) are certainly ok. : : In fact, that definition seems trivial to break. Given a known N : steps of comparison, the lazy lists (1..Inf) and (1..N-1, (N..Inf:2)) : would both test equal in the first N positions and differ in position : N+1. Therefore, we can always break any operator that tests the : first N positions of both lazy lists, and thus that definition would : be wrong. You're assuming that the computer isn't smart about where the list of numbers goes from enumerated to rule-generated, and that rule generators can't be compared. And they can't, in general, but the .. operator is not general, but specific, and does know how to compare the abstractions. : The reason Mr Engineer might expect false would be if they thought you were : eventually testing against Inf. Due to his experience in numerical : programming, he sees NaN and Inf having certain behaviors that no pure : mathematician would even countenance. On a system whose system nummifier : knows things like Inf and NaN already, you see this happening even today. : Witness real Perl: : : % perl -e 'printf %g\n, NaN' : nan : % perl -e 'printf %g\n, 1 + NaN' : nan : % perl -e 'printf %g\n, 42 * NaN' : nan : % perl -e 'printf %g\n, Nan == NaN' : 0 : % perl -e 'printf %g\n, 1+Nan == NaN' : 0 : % perl -le 'printf %g\n, Inf' : inf : % perl -le 'printf %g\n, 1+Inf' : inf : % perl -le 'printf %g\n, 2+Inf' : inf : % perl -e 'printf %g\n, Inf == Inf' : 1 : % perl -e 'printf %g\n, Inf == -Inf' : 0 : % perl -e 'printf %g\n, 1+Inf == Inf' : 1 : % perl -e 'printf %g\n, Inf + Inf' : inf : % perl -e 'printf %g\n, Inf * Inf' : inf : % perl -e 'printf %g\n, Inf / Inf' : nan Yes, but now you're talking about Inf in the context of numeric operators rather than the .. range constructor, which knows better than to ever try to evaluate Inf. To the .. operator, Inf doesn't mean infinity. It means and so on In fact, as the design currently stands you can also write those as: (1...) equal (0...) There, no more infinities. :-) : In other words, if you treat Inf as any particular number (which Mr : Mathematician stridently yet somewhat ineffectually reminds you that are : *not* allowed to do!), then you may get peculiar results. Heck, you could : probably then get Mr Engineer to agree that the lazy lists (1..Inf) and : (0..Inf) are the same in the *last* N positions for all values of N, and : since you could just select N to be equal (ahem) to the length (ahem**Inf) : of your list, they must be equal. :-) Again, you seem to be thinking that Cequal would take the size of both sides as if they were arrays. I think of (1..Inf) more as a funny kind of arbitrarily extensible string, and Cequal as a comparison character by character, only they happen to be list elements instead. One could *almost* extend Ceq to have this semantics when applied to lists. But it breaks down when you recursively want to do polymorphic == vs eq. Whereas C $a equal $b would perhaps have a few smarts about comparing dissimilar types, though not as much as ~~ does. : Mr Mathematician, purist that he is, has of course long ago thrown up his : hands in disgust, contempt, or both, and stormed out of the room. To him, : most of those Perl
