What's the latest on Iterators?
The various synopses contain many mentions of Iterators. These are used, for instance, to implement lazy lists so the expression 1..1_000_000 does not have to allocate a million element array. But as far as I can tell the term is never defined anywhere in the synopses. Is Iterator a role, and if so what methods is it required to have? Do functions like map and grep, which in Perl5 return lists, return Iterators in Perl6? Can an Iterator be passed to a function (like map and grep again) that requires a list as an input? Does an array or hash have only one Iterator or can it have several independent ones? Joe Gottman
Re: What's the latest on Iterators?
On 11/11/05, Joe Gottman [EMAIL PROTECTED] wrote:
The various synopses contain many mentions of Iterators. These are used,
for instance, to implement lazy lists so the expression 1..1_000_000 does
not have to allocate a million element array. But as far as I can tell the
term is never defined anywhere in the synopses. Is Iterator a role, and if
so what methods is it required to have? Do functions like map and grep,
which in Perl5 return lists, return Iterators in Perl6? Can an Iterator be
passed to a function (like map and grep again) that requires a list as an
input? Does an array or hash have only one Iterator or can it have several
independent ones?
I'm going to speculate on a few of these items.
Iterator most certainly will be a role, though that doesn't mean that
internal iterators will do this role. I expect they would, though. It
will probably have methods that do the following:
* next_item
* prev_item
* nth_item
* rewind
* has_next_item?
* has_prev_item?
I expect that lists will be convertable to iterators and vice-versa.
You can do this in P5 already:
sub create_iterator_from_list {
my @list = @_;
return sub {
return shift @list;
};
}
create_list_from_iterator {
my ($iterator) = @_;
my @list;
while ( my $item =$iterator-() ) {
push @list, $item;
}
return @list;
}
Of course, that's extremely inefficient. I expect that Perl6 will be a
little smarter, though it's not clear how much smarter it can be. For
one thing, Iterators will have to support two modes - one where the
list is frozen (the P5 version I posted above) so that changes to list
don't change the iterator and another where the iterator iterates into
the list as it stands, so that changes to the list are reflected in
the iterator immediately. The second mode has the possibility of being
unstable, but if you choose this mode (which wouldn't be the default),
then it's on your head.
As for multiple iterators, that's the point of having a separate
iterator object. Each iterator maintains its own state, allowing for
multiple traversals across the same set.
As for lazylists (1..Inf), they have to be implemented via iterators
(which is why I'm almost positive the two will be interchangeable).
And, if you pass (1..Inf) to map/grep/sort, it would HAVE to return an
iterator back, otherwise you'll hang at that instruction.
Of course, if you said while (my $n = 1..Inf) { }, it's on your head
to provide a last in there somewhere.
Rob
Re: Test Case: Complex Numbers
On Fri, Nov 11, 2005 at 06:21:53AM +, Luke Palmer wrote:
: Just some initial thoughts and syntax issues. I'll come back to it on
: the conceptual side a little later.
:
: On 11/10/05, Jonathan Lang [EMAIL PROTECTED] wrote:
:
: class complexRectilinear {
:has $.x, $.y;
:
: Hmm, that might need to be
:
: has ($.x, $.y);
:
: However, inlining hass isn't possible, so there's really no reason
: for that restriction. But it might be good just for consistency with
: my. But it also might not, because I'm always annoyed with those
: parentheses.
It's not about inlining in general, but particularly about the
relationship of precedence with assignment. And you presumably
*can* say:
has ($.x, $.y) = (1, 2);
to mean the same as:
has $.x = 1;
has $.y = 2;
Likewise
state ($.x, $.y) = (1, 2);
means
state $.x = 1;
state $.y = 2;
:method infix:+ ($a is complexRectlinear, $b is complexRectilinear)
:
: method infix:+ (complexRectilinear $a, complexRectilinear $b)
:
: returns complexRectilinear {
: return new complexRectilinear($a.x + $b.x, $a.y + $b.y);
:
: return new complexRectilinear: $a.x + $b.x, $a.y + $b.y;
rampantspeculation
Given the new relationship between
$obj.method(...)
and
$obj.method: ...,
I'm wondering if we can make the same relationship between
method $obj(...)
method $obj: ...
That is, : becomes more of a Haskellish $ operator. I speculated this
earlier when I wanted to change
$obj.method :{...}
into
$obj.method: {...}
But foo $bar(...) is probably too ambiguous with a possible foo list
operator unless we were to require : on all calls to list operators:
print: 1,2,3
That's likely to inspire mutiny. Though we could perhaps get away
with requiring the colon only on list operators that have more than
one argument, on the theory that
foo 1;
is always the same as
1.foo;
/rampantspeculation
: Hmm, that union looks like a backwards role. That is, you're creating
: a role complex and saying that the interface of that role is
: whatever is common between these two classes. Interesting idea... not
: sure how fruitful that is though.
:
: The idea of several isomorphic implementations of the same thing has
: occurred to me several times, but I never figured out how it might
: work. Let me think about that.
And what's the common role of a scalar that can have a string
implementation in several abstraction levels, plus any number of native
integer/float and bignum/bigfloat implementations hiding behind it?
Interesting question.
: If $b's real component is
: rational, it makes some sense to treat [-1] as the last element in the
: list, [-2] as the second-to-last, and so on; but if $b's real
: component is irrational, there _is_ no positive end to the list, and
: it would make sense if [-1] referred to the first result that you
: reach by rotating in the clockwise direction from the primary result.
: Can an infinitely long list be set up so that [-1] still has
: meaning?
:
: Hmm. I don't see why not. Though we haven't established the array
: laws yet, you're probably not breaking any of them by doing that.
: You can consider your array to be transfiniteish:
:
: [ a[1], a[2], ..., a[-2], a[-1] ]
:
: Understanding that no matter how long you iterate going forward,
: you'll never get to a[-1].
I believe we already said you could pop or refer to the end of an
infinite array in A6/Appendix B.
: As an example,
: let's say that $b = 0.5. This means that the first result is rotated
: zero radians counterclockwise from $a's direction, and corresponds to
: [0]. [1] would correspond to being rotated pi radians, and the length
: generator would say that there are only two elements in the list.
: Could you set things up so that you could nonetheless access [2]
: (which is rotated by 2*pi radians), [3] (rotated by 3*pi radians), or
: possibly even have [-1] represent a rotation by -pi radians?
:
: Well, it would certainly be okay to have an infinite list that had
: that property. However, having the list report that its length is,
: say, finite $n, and then having @list[$n] be something besides undef
: may be breaking some law (but maybe not[1]).
:
: What you're really doing is defining the indices mod $n. Maybe
: there's some way to tell the compiler that your indices are defined
: that way to allow this sort of behavior. Maybe you could make a
: subclass of Array called ModArray or something that allowed this.
: Maybe you're simply not allowed to use square brackets in a case where
: the list is finite but defined for all indices.
All is fair if you predeclare.
: But that's all theoretical formality. For the Perl practicioner, feel
: free to break the laws if it helps you get your job done. :-)
:
: Luke
:
: [1] I think I'm going to embark on writing down the laws for a few of
: our basic types so we can actually talk about this without
Re: What's the latest on Iterators?
On Fri, Nov 11, 2005 at 08:42:44AM -0500, Joe Gottman wrote:
: Do functions like map and grep, which in Perl5 return lists, return
: Iterators in Perl6?
A list may contain iterators. Lists don't eagerly flatten in Perl 6.
: Can an Iterator be passed to a function (like map and grep again)
: that requires a list as an input?
Certainly. You can pass as many iterators as you like. The range object
is your prototypical iterator, and you can say:
@results = grep {...} 0..9, 20..29, 40..49;
The list that grep is returning can also function as an iterator, so
@results isn't necessarily all there after the statement executes.
Though it's possible that = should put more COW requirements on the
right side than := would, so we at least maintain the appearance of
eager evaluation.
: Does an array or hash have only one Iterator or can it have several
: independent ones?
An array can have as many iterators as it likes, according to A6. There's
an underlying .specs objects that contains the specifications for how
to genererate missing values, and if the specs are smart enough, they
can be generated from either end.
Larry
Re: proposal: rename 'subtype' declarator to 'set'
On Wed, Nov 09, 2005 at 01:45:21PM +0100, TSa wrote:
: So, why not call the thing what it is---a set *type* declarator!
:
: set SmallInt of Int where { abs 10 };
:
: set SomeNums of Num = (3.14, 4, 89, 23.42);
:
: set Bit of Int = (0,1);
Interesting idea. I expect a bit of interference from the verb
to set, but that's probably not a showstopper, particularly since
the next token isn't a variable.
: Enumerations are then just sets of pairs
:
: set NumWords of Pair = { zero = 0, one = 1, two = 2, three = 3 };
: # or with ( ... ) instead?
:
: enum NumWords = zero one two three; # short form of the above
:
:
: Without the 'of' it doesn't look so good
:
: set Num SomeNums = (3.14, 4, 89, 23.43);
:
: but OTOH, it looks nicely like
:
: my Num @SomeNums = (3.14, 4, 89, 23.43);
:
: my Int %NumWords = { zero = 0, one = 1, two = 2, three = 3 };
:
: YMMV, though ;)
I'd like to lose the = if possible. We don't say
sub foo = { ... }
: Does that work? Perhaps even while maintaining compatibility with the
: set *value* creator sub that exists in Pugs, IIRC?
:
: my $x = set( 1, 2, 3 ); # $x contains a set reference at best
They can perhaps be unified, especially if we lose the = noise. Probably
have to require the parens syntactically though, just as though you'd said
my $x = my($a,$b,$c);
Larry
Re: proposal: rename 'subtype' declarator to 'set'
On 12/11/05, Larry Wall [EMAIL PROTECTED] wrote:
On Wed, Nov 09, 2005 at 01:45:21PM +0100, TSa wrote:
: So, why not call the thing what it is---a set *type* declarator!
:
: set SmallInt of Int where { abs 10 };
:
: set SomeNums of Num = (3.14, 4, 89, 23.42);
:
: set Bit of Int = (0,1);
Interesting idea. I expect a bit of interference from the verb
to set, but that's probably not a showstopper, particularly since
the next token isn't a variable.
I think 'subset' might be a nicer colour for this bikeshed. For an
extra three characters you lose the confusion with to set, and it
highlights the fact that you're (usually) declaring a *constrained*
subset of the original type.
Stuart
Re: Thoughs on Theory.pm
On 10/13/05, Dave Whipp [EMAIL PROTECTED] wrote:
(ref: http://svn.openfoundry.org/pugs/docs/notes/theory.pod)
theory Ring{::R} {
multi infix:+ (R, R -- R) {...}
multi prefix:- (R -- R){...}
multi infix:- (R $x, R $y -- R) { $x + (-$y) }
multi infix:* (R, R -- R) {...}
# only technically required to handle 0 and 1
multi coerce:as (Int -- R) {...}
}
This says that in order for a type R to be a ring, it must
supply these operations. The operations are necessary but
not sufficient to be a ring; you also have to obey some
algebraic laws (which are, in general, unverifiable
programmatically), for instance, associativity over
addition: C(a + b) + c == a + (b + c).
I started thinking about the in general, unverifiable programmatically
bit. While obviously true, perhaps we can get closer than just leaving
them as comments. It should be possible to associate a
unit-test-generator with the theory, so I can say:
I've been thinking about this. If we have a type inferencer, we know
that any function we define to be N,N-N will be that way. The only
items we have to show is for all a in N, there is a unique succesor
which is also in N and that for all b in N, b != 1, there is a unique
predecessor. If we have that, then we get the laws of arithmetic. Is
it possible to put that into the type inferencer if the types are
defined as iterators? Kind of like Church numbers, but in P6 notation.
I think that by defining our types as iterators, we can satisfy the
succ/pred requirements of Peano's, meaning we have the arithmetic
rules.
Rob
Re: Test Case: Complex Numbers
Luke Palmer wrote:
Just some initial thoughts and syntax issues. I'll come back to it on
the conceptual side a little later.
I'm looking forward to it.
Jonathan Lang wrote:
method coerce:complexPolar () returns complexPolar {
return new complexPolar ($.x * $.x + $.y * $.y, atn($.y / $.x) *
(sgn($.x) || sgn($.y)));
}
Hmm. I don't know why you marked this with coerce:?
Neither do I; I was assuming that the purpose of coerce: is to allow
implicit type conversions - that is, if I feed a complexRectilinear
object into an argument slot that's looking for a complexPolar object,
this method would be called implicitly and the result would be used
instead.
...
}
... and a similar definition for class polar.
(Technically, coerce:complexPolar and infix:+ are generators in the
sense that they create new instances of the class; but ISTR something
about generators not being allowed in classes.)
Ahh, you read that in theory.pod. It's not clear that the factory
and generator abstractions are all that useful (I'm still looking
for a good use though). I just included them for symmetry (like
Maxwell :-).
FWIW, I didn't read theory.pod as thoroughly as I probably should
have, nor did I grasp it as well as I would like. But when I looked
at the concept of virtual lists, the union/factory/generator triad
seemed to be, conceptually, a perfect fit: the virtual list is
actually a union, whose factory includes generators that produce
information about the list on demand. More generally, a union would
be the appropriate tool for the magic behind what Perl 5 used ties
for.
Don't think that you're not allowed to return instances of the class
you are defining from methods. You can. Generators are more
restrictive: they say that any subclass must return an instance of
*itself* from that method; i.e. it probably wouldn't be able to use
your implementation. But that breaks subclassing laws, which is why
they aren't allowed in classes.
I'm not sure I'm following this.
You should then be able to say:
union complex {
class complexRectilinear;
class complexPolar;
}
...or something of the sort. At this point, you have the ability to
freely represent complex numbers in either coordinate system and to
switch between them at will. Am I right so far?
Hmm, that union looks like a backwards role. That is, you're creating
a role complex and saying that the interface of that role is
whatever is common between these two classes. Interesting idea... not
sure how fruitful that is though.
That wasn't the intent; the intent was to define a
something-or-other Ccomplex that represents the fact that whatever
does this sometimes behaves like a complexRectilinear and other times
behaves like a complexPolar. Even the underlying information (the
attributes involved) may vary from role to role, though what those
attributes represent ought to be the same regardless of which role is
in use.
The idea of several isomorphic implementations of the same thing has
occurred to me several times, but I never figured out how it might
work. Let me think about that.
Cunion was probably a bad name for it, especially considering that
theory.pod already uses Cunion for a very specific purpose.
Cchoice might have been a better name.
However, if $b's real component isn't a rational number, you won't
have a finite number of elements in the list. Here's where I get a
little fuzzy: IIRC, there's some means of defining a list by providing
an element generator:
generator element($index) returns complex { ... }
Is there a way of setting things up so that an attempt to ascertain
the list's length would call a separate generator for that purpose?
generator length() returns complex { ... }
At any point above, am I abusing the concept of theories, or failing
to use them to their fullest extent?
Well, you're not using generator correctly.
You're really just trying to define a lazy list or an iterator, right?
That most likely involves implementing some role:
role ComplexPowers does Lazy {...}
or:
role ComplexPowers does Iterator {...}
And then creating one of those objects from within your pow function.
Nothing deeply type-theoretical going on here.
That's the most traditional way, yes; but is there anything wrong with
the concept of implementing it based on a factory instead of a role?
If $b's real component is
rational, it makes some sense to treat [-1] as the last element in the
list, [-2] as the second-to-last, and so on; but if $b's real
component is irrational, there _is_ no positive end to the list, and
it would make sense if [-1] referred to the first result that you
reach by rotating in the clockwise direction from the primary result.
Can an infinitely long list be set up so that [-1] still has
meaning?
Hmm. I don't see why not. Though we haven't established the array
laws yet, you're probably not
Re: proposal: rename 'subtype' declarator to 'set'
I think 'subset' might be a nicer colour for this bikeshed. For an extra three characters you lose the confusion with to set, and it highlights the fact that you're (usually) declaring a *constrained* subset of the original type. Stuart Ehh. By that definition arn't all sets subsets? Anyway I didn't see any confusion with to set at all. subset confused me quite a bit though. Besides it might not be a sub set at all. set types full half quarter jumbo automatic; You could call that a subset of words, but i think this has extra clarity over: subset types full half quarter jumbo automatic; First thing i think when seeing that is...subset of what? where is the larger set defined? Of course I have no knowledge of set theory at all, just a humble programming giving his input.
