Re: PDL-P: Re: Reduce [was: Re: Random items (old p5p issues)]
Tuomas Lukka [EMAIL PROTECTED] writes:
On 4 Aug 2000, Ariel Scolnicov wrote:
Karl Glazebrook [EMAIL PROTECTED] writes:
OK I will raise to the bait
I think it's a bit unfair to say that PDL people have failed to 'bite',
there was quite a bit of discussion on our list after your post. Also
some concern about how much of perl6 is vapourware.
I am game to take part in discussions.
It has always been apparent to me that Numerical Python is better integrated
than PDL. Some language changes in core python WERE made to accomodate it,
also Python had less syntax clutter to get around.
I definitely support embedding many of the key PDL ideas into the language
- they key one is a much easier syntax for a multi-dim slice. We are currently
driven to
$a-slice("10:100,30:200");
compared to IDL AND NumPy: a[10:100,30:200]
Perl doesn't have multi-dimensional arrays (yet, I hope), but it
*does* spell `:' as "..", even today. @x[7..9] is a 3-element list,
which I don't see as any different from @x[7:9]. Does the slice share
the elements of @a in your example?
Well, first of all,
10:100, 30:200
is not the same: in Perl it comes out as
10..100, 30..200
10, 11, ... , 100, 30, 31, .., 200
whereas what we want is
Span(10, 100), Span(30, 200)
where Span is some suitable object telling that this span is a parameter.
There are also other syntaxes for slice we would like to have but these
can probably be kludged.
I think we're confusing 2 separate issues here. PDL seems to deal
with both, but let's keep them separate:
(1) Decent span objects for generating subarrays (e.g. 1:10:3 (which
should probably be 1..10:3, or whatever the iterator sequence
works out as).
(2) Multidimensional arrays. Today Perl does *not* have these. As
Tuomas points out, the `,' operator is already too overloaded to
separate indices. Note: I say the Perl has no multidimensional
arrays. A list-of-lists is *not* a multidimensional array. A
multidimensional array can be *implemented* as a list-of-lists,
but not efficiently.
Naturally, there are interesting interactions between (1) and (2),
e.g. when slicing a multidimensional array (consider, for instance,
what an operator should look like that returns the diagonal of a
square matrix).
A third issue:
(3) An "rvalue" slice is a *copy* of the elements sliced from the
array; an "lvalue" slice consists of the elements themselves, with
a different indexing scheme. Naturally, Perl should have both...
[...]
Regarding multi-dimensional arrays, the PDL porters are undoubtable
champions; what is required?
Well, the PDL distro is our answer to that ;) ;)
But Shirley Perl could make your job a little less horrible? At the
very least, if `:' were a binary operator, you could overload it to
generate non-string slice indices.
--
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
Re: Reduce [was: Re: Random items (old p5p issues)]
On Fri, Aug 04, 2000 at 08:16:17AM +1000, Jeremy Howard wrote: Martyn J. Pearce wrote: ... what I would like to discuss adding to the language is 1) a means to signal an early exit to the iterator, 2) a means to tell we're at the end of a list without having to evaluate the list length as we start 3) a much more lightweight, and language built-in, mechanism for currying these functions. Would the changes you're discussing support: - Infinite lists I certainly hope so - Reducing to an array rather than a scalar? Thinks Yes; the example of zip has previously been mentioned, and that would. The first of these is pretty obvious--sometimes you want to define a mapping without restricting the domain. Indeed. The second is about writing something like: @a = sumover(@b[$index::j] to get column sums. $index::j is in this case an iterator defined as operating over the second index of an array. Of course you can always do this with a loop, but to me the whole point of adding iterators, matrix ops, and reduce/fold is that you can write your code the way a mathematician writes a function. Having to put explicit loops in is a bit messy. Yup. BTW, I'd like to see a more lightweight currying mechanism too. The challenge is to find a 'perlish' but not heavyweight approach... Ah, good. I assume that having established the challenge, you'll be rising to it? :-) Mx. -- See, the stars are shining bright Everything's all right tonight -- (Martin L. Gore, Never Let Me Down Again)
Re: PDL-P: Re: Reduce [was: Re: Random items (old p5p issues)]
OK I will raise to the bait
I think it's a bit unfair to say that PDL people have failed to 'bite',
there was quite a bit of discussion on our list after your post. Also
some concern about how much of perl6 is vapourware.
I am game to take part in discussions.
It has always been apparent to me that Numerical Python is better integrated
than PDL. Some language changes in core python WERE made to accomodate it,
also Python had less syntax clutter to get around.
I definitely support embedding many of the key PDL ideas into the language
- they key one is a much easier syntax for a multi-dim slice. We are currently
driven to
$a-slice("10:100,30:200");
compared to IDL AND NumPy: a[10:100,30:200]
I'd propose simply building the a:b syntax into the core of Perl6. It's
convenient and almost standard.
perl6 should provide simple arrays, but they should be allowed to be
replaced with objects with no change of syntax. So
@a[10:100,30:200];
Would work whether @a was a perl list of lists or a PDL compact array.
So would @a * @b
Loop unrolling sounds really good, their should be hooks for objects to
provide their own implementation. Proper overloading and ability to
overload by arg type are required, i.e.
sub myfunc{ float x, complex y }
sub myfunc{ float x, float y }
Their should also be hooks for slices, for example if one is implementing
a complex objects (e.g. representing a map) - one might want a slice in
physical units instead of array indices.
I'd even propose getting rid of @a for arrays and $a for scalars and just
making the "a". I've never really liked that feature of perl - I am sure
some users agree and some disagree - might be worth taking a straw poll.
In this age where everything may (or may not) be an object are $ and @ really
required? There are too many objects types and not enough funny symbols..
even with Unicode.
Karl Glazebrook
Jeremy Howard wrote:
BTW, I'd like to see a more lightweight currying mechanism too. The
challenge is to find a 'perlish' but not heavyweight approach...
Ah, good. I assume that having established the challenge, you'll be
rising to it? :-)
Yes of course. But I want to first of all see the following RFCs from Damian
he's promised:
* Built-ins: min() and max() functions and acceptors
* Built-ins: reduce() function
* Data structures: Semi-finite (lazy) lists
* Subroutines: higher order functions
* Subroutines: lazy evaluation of argument lists
* Superpositions: vector operations via superpositions
Damian is likely to write these in a way that is nicely integrated together,
based on past experience. What I'd then like to do is to see how these fit
together to fill in the stuff I mentioned earlier today:
quote
- Matrix ops
- Support for lazy evaluation
- Compile time expression unrolling (e.g. so that $a = sum(@b*@c+@d) does
just one loop and no memory copy, as would occur with expression templates
in C++)
- Ability to specify infinite lists (e.g. like in Haskell)
- Generic programming (iterators, algorithms, etc, eg. like in the STL)
/quote
I think the way I'd like to do this is to try and implement a couple of
interesting bits of code that I've found are good tests of numerical
programming environments. Stuff that just looks beautiful in Mathematica
(which supports functional, rule-based, and procedural programming), but is
full of loops and control structures in most languages. That way any bits
that are missing will be pretty obvious (at least bits that matter to me!)
I've tried to get input from PDL porters by cross-posting a couple of times,
but haven't got much of a bite yet. I'm nervous about finding that we either
reinvent the wheel, or break useful stuff that they've done... Are there any
PDL gurus here who are interested in getting involved in some of these
perl6-language issues?
Re: PDL-P: Re: Reduce [was: Re: Random items (old p5p issues)]
Also on the issue of loop unrolling and efficient looping.
PDL has what we call 'threading'.
This allows a C-level function to specify the dimensionality of
the arguments it accepts. For example a function addtoline() which
hyptheticaly adds a constant to a row vector might
have a 'signature'
a(n); b(); [o]c(n);
So a(n) is a 1D input, b() is a scalar (0D) which addtoline might add
to all the elements of a(n) and c(n) is the output 1D.
What is really useful is that if you add extra dimensions they
get looped over automatically, at the C-level so really fast.
e.g. a(100,10), b(10), c(100,10)
- adds to all 10 rows of a.
ALSO they way it is implemented is the array pointers are calculated
by C macros in such a way as to support transpositions and slicing
with zero memory overhead. Thus if I want to add one to every *column*
of a, in a slice:
addtoline $a-xchg(0,1)-slice("10:20,20:40"), 10, $c
here xchg creates a virtual transposition of the first two dims, and slice
creates a virtual slice. This is all done by storing extra info in the
$a object.
I think these ideas would be of use in any discussion of perl6 numerical
efficiency - there are other ways I guess. The core idea is to try and stay
in compiled loops.
The other advantage of this 'threading' is that it then automatically parallelizes
the problem - we even have an experimental PDL implementation which can use
multiple CPUs to do 'threads'.
One problem we are continually faced in PDL is we do all this at the C-level
- but then we run into problems where if we have pure-perl PDL functions they
can't do these tricks.
Another problem though is while one can usually write many complicated multi-dim
problems with threading tricks, and avoid loops, it is sometimes a bit taxing
on the brain! One often wishes one could just write it as C/fortran style
loops and have the language figure out how to do the loops efficiently.
Anyway some integration of concepts for handling large numerical computation
into the core would definitely be a good thing.
Karl Glazebrook
Re: PDL-P: Re: Reduce [was: Re: Random items (old p5p issues)]
On Fri, 4 Aug 2000, Tuomas Lukka wrote: On 4 Aug 2000, Ariel Scolnicov wrote: Well, first of all, 10:100, 30:200 is not the same: in Perl it comes out as 10..100, 30..200 10, 11, ... , 100, 30, 31, .., 200 Additionally, generically it would not necessarily have to be a range of integers. The range could be specified as floating point if we are specifying a slice in physical coordinates. -- Tim Jenness JCMT software engineer/Support scientist http://www.jach.hawaii.edu/~timj
Re: Reduce [was: Re: Random items (old p5p issues)]
On Wed, Aug 02, 2000 at 07:36:09PM +0100, Tom Hughes wrote: In message [EMAIL PROTECTED] Gisle Aas [EMAIL PROTECTED] wrote: The upcoming Python (v2.0) introduces a builtin called zip() that does the same thing: for a,b,c in zip(aa,bb,cc): ... There are also question on how long the resulting list should be if @a, @b, @c is not of the same length. I think zip() was defined to stop when the first list runs out. I believe zip is quite a common name for this operation in functional languages. Certainly Miranda uses it to turn a tuple of lists into a list of tuples, stopping as soon as any of the lists runs out. I was simply repeating a conversation. I was not implying any name. If many other languages call it zip() then lets call it zip() Python also has a map function that can take multiple lists and iterate over them in sync. E.g. map(func, list1, list2, list3) where 'func' must be a function taking 3 arguments. Can't see how to easily extend perl's map in that way. Perhaps we could introduce map2, map3,... builtins? :-) This is what Miranda calls zipwith. Combined with reduce you can do things like scalar products very simply: reduce(plus, zipwith(multiply, list1, list2)) Maybe we should call it something like mapzip, zipmap, zmap, mapz ... as it does seem to be a combination of both zip and map Note that Miranda actually calls reduce fold though - well actually foldl or foldr depending on which end of the list you start at. Many other have brought up this. But I ask the question "do we need two operators" foldr can be done with reduce reverse @list where reverse could be inteligent and create an iterator which itterates over the list backwards. But on the other hand having foldl and foldr may be being consistent with other languages. I will leave that to Larry to decide. Graham.
Re: Reduce [was: Re: Random items (old p5p issues)]
On Thu, Aug 03, 2000 at 06:31:38AM +, Martyn J. Pearce wrote:
And I feel that by being able to iterate over lists with map, grep,
fold[rl]/reduce{,_r}, whatever, _without pre-flattening the list_, we
could drastically increase the applicability of these constructs.
Having iterators avaliable in the language and being able to say that
a sub takes an iterator could be a great advantage. Also being able
to create iterators.
ie being able say
sub reduce (+) { ...}
where + is an iterator and have an iterator context so
reduce { ... } some_func()
and have some_func know it is being called in an iterator context
and be able to create it's own iterator. foldr could then be
done as
reduce { ... } reverse some_func()
which could create a reverse iterator.
So there probably should be an RFC to add iterators to the language and
be avaliable from perl, not just C. But I have no idea how they
should look etc.
However, and I am makeing an assumption here, probably the most common
use of reduce is with one of the + - / * operators. So it would be nice
to be able to optimize these, maybe to a separate op. There is two ways
we can do that.
1) Allow a syntax for it
reduce (+) @list;
2) Detect and optimize like we do now for sort.
reduce { $a + $b } @list;
But to be able to do either require reduce to be in the perl core
rather than a module as it requires either the lexer or optimizer
to know about reduce.
Graham.
Re: Reduce [was: Re: Random items (old p5p issues)]
Graham Barr said: ... So there probably should be an RFC to add iterators to the language and be avaliable from perl, not just C. But I have no idea how they should look etc. More generally, I wonder whether there should be an RFC on the changes required to make perl a more friendly environment to numerical programming (both in terms of speed and elegance)... Or at least close collabaration to ensure that the end result creates a coherent whole. Some of the issues that come to mind are: - Matrix ops - Support for lazy evaluation - Compile time expression unrolling (e.g. so that $a = sum(@b*@c+@d) does just one loop and no memory copy, as would occur with expression templates in C++) - Ability to specify infinite lists (e.g. like in Haskell) - Generic programming (iterators, algorithms, etc, eg. like in the STL) But I also don't know how this should look, or quite where to start tackling it from. I suspect PDL provides a lot of useful ideas, but I haven't really used it enough... However, and I am makeing an assumption here, probably the most common use of reduce is with one of the + - / * operators. So it would be nice to be able to optimize these, maybe to a separate op. Well, maybe. But don't forget about min and max and everything in between, which always seem to cause grief for reduce/fold implementations.
Re: Reduce [was: Re: Random items (old p5p issues)]
Graham Barr wrote: I was simply repeating a conversation. I was not implying any name. If many other languages call it zip() then lets call it zip() No, we can't call it zip, because that's what python calls it; and that would make perl equivalent to python.* [*being facetious. hopefully the other guy who made an argument like this in seriousness earlier gets the point...] -- John Porter
Re: Expanding the language primitives (was: Re: Reduce [was: Re: Random items (old p5p issues)])
Dan Sugalski [EMAIL PROTECTED] writes: More importantly, the more primitives that perl provides, the wilder and more useful things people will be able to do. Not quite. Its the functions that are provided that matter, not whether they are primitives or not[1]. A small set of primitives with a large set of functions is more powerful than just a moderate set of primitives. Compare with Emacs: a relatively small set of powerful built-ins and a plethora of lisp functions for everything else. -- Johan [1] Tentative terminology: primitive: a function built directly into perl function: a function loadable into perl module:a (collection of) functions written in Perl
Re: Reduce [was: Re: Random items (old p5p issues)]
On Tue, Aug 01, 2000 at 10:27:08PM +0300, Ariel Scolnicov wrote:
multimap operation list-of-lists # uurgh.
This made me think of something else that came up in a discussion with Larry
after the conference.
The discussion started off with the ability to do
for ($a,$b) (@list) { ... }
and go through the list in steps of two, or whatever the number of vars were.
But then went onto interators and something like
@list = interleave(@a,@b,@c);
which would interleave the lists given, and
foreach ($a,$b,$c) (interleave(@a,@b,@c))
which would iterate around all lists at the same time, but without flattening
the list. Maybe through some kind of hierarchy of iterators or something
Graham.
I really should get all these ideas into an RFC.
Re: Reduce [was: Re: Random items (old p5p issues)]
hi,
Why not some sort of functionality like LISP/Prolog i.e. working with lists.
("a",@x,"b",%y) - the list
head ("a",@x,"b",%y) # "a"
head(tile("a",@x,"b",%y)) #@x
head(head(tile("a",@x,"b",%y))) #$x[0]
head(tile(tile("a",@x,"b",%y))) #"b"
if you like it then "splice" etc... can this be done in the moment ??
I think moto of the Perl6, should be "Steal with Style" :")
On Tue, Aug 01, 2000 at 10:27:08PM +0300, Ariel Scolnicov wrote:
multimap operation list-of-lists # uurgh.
This made me think of something else that came up in a discussion with
Larry
after the conference.
The discussion started off with the ability to do
for ($a,$b) (@list) { ... }
and go through the list in steps of two, or whatever the number of vars
were.
But then went onto interators and something like
@list = interleave(@a,@b,@c);
which would interleave the lists given, and
foreach ($a,$b,$c) (interleave(@a,@b,@c))
which would iterate around all lists at the same time, but without
flattening
the list. Maybe through some kind of hierarchy of iterators or something
Graham.
I really should get all these ideas into an RFC.
Re: Reduce [was: Re: Random items (old p5p issues)]
Graham Barr wrote:
But then went onto interators and something like
@list = interleave(@a,@b,@c);
which would interleave the lists given, and
foreach ($a,$b,$c) (interleave(@a,@b,@c))
sub interleave(\@;\@\@\@\@\@\@\@\@) {
my $m = -1;
for ( @_ ) { $m $#{$_} and $m = $#{$_} }
map { my $i = $_; [ map { $_-[$i] } @_ ] } 0..$m;
}
for ( map { @$_ } interleave( @a, @b, @c ) )
Gisle Aas wrote:
Python also has a map function that can take multiple lists and iterate
over them in sync. E.g.
map(func, list1, list2, list3)
where 'func' must be a function taking 3 arguments. Can't see how to
easily extend perl's map in that way. Perhaps we could introduce
map2, map3,... builtins? :-)
sub mapf(;\@\@\@\@\@\@\@\@\@) {
my $cr = shift;
my $m = -1;
for ( @_ ) { $m $#{$_} and $m = $#{$_} }
map { my $i = $_; $cr-( map { $_-[$i] } @_ ) } 0..$m;
}
I guess my question is, why do these need to be builtins?
There is no limit to the funky algorithms one can come up with;
not everyting should go in the core.
--
John Porter
Aus tiefem Traum bin ich erwacht.
Re: Reduce [was: Re: Random items (old p5p issues)]
On Wed, Aug 02, 2000 at 10:43:37AM -0600, Tom Christiansen wrote:
sub mapf(;\@\@\@\@\@\@\@\@\@) {
Steal from lisp:
map
maap
maaap
mapp
mappp
maappp
dwim
:)
Graham.
Re: Reduce [was: Re: Random items (old p5p issues)]
Tom Christiansen wrote:
sub mapf(;\@\@\@\@\@\@\@\@\@) {
Steal from lisp:
map
maap
maaap
mapp
mappp
maappp
...
Should be feasible with an AUTOLOAD that takes a certain kind of regular
expression...
sub AUTOLOAD /^ma+p+$/ {
}
Some for the 'car' and 'cdr' variants, of course...
Hildo
Re: Reduce [was: Re: Random items (old p5p issues)]
Graham Barr wrote:
The upcoming Python (v2.0) introduces a builtin called zip() that does
the same thing:
for a,b,c in zip(aa,bb,cc):
...
There are also question on how long the resulting list should be if
@a, @b, @c is not of the same length. I think zip() was defined to
stop when the first list runs out.
I am sure that will be a debate. My first thought was to continue for the
longest and return undef's for the others. I am sure someone would suggest
use aa other cc and many more.
If this is implemented someone will just have to decide what make most sense
and implement that.
stopping at the shortest doesn't permit useful operations on the remainder of the
longer list entries.
Stopping at the longest with undef's seems more general, and people who want the
shorter could
for $a, $b, $c in zip (@aa, @bb, @cc)
{
last if ! defined $a || ! defined $b || ! defined $c;
}
--
Glenn
=
There are two kinds of people, those
who finish what they start, and so
on... -- Robert Byrne
___
Why pay for something you could get for free?
NetZero provides FREE Internet Access and Email
http://www.netzero.net/download/index.html
Re: Reduce [was: Re: Random items (old p5p issues)]
In message [EMAIL PROTECTED] Gisle Aas [EMAIL PROTECTED] wrote: The upcoming Python (v2.0) introduces a builtin called zip() that does the same thing: for a,b,c in zip(aa,bb,cc): ... There are also question on how long the resulting list should be if @a, @b, @c is not of the same length. I think zip() was defined to stop when the first list runs out. I believe zip is quite a common name for this operation in functional languages. Certainly Miranda uses it to turn a tuple of lists into a list of tuples, stopping as soon as any of the lists runs out. Python also has a map function that can take multiple lists and iterate over them in sync. E.g. map(func, list1, list2, list3) where 'func' must be a function taking 3 arguments. Can't see how to easily extend perl's map in that way. Perhaps we could introduce map2, map3,... builtins? :-) This is what Miranda calls zipwith. Combined with reduce you can do things like scalar products very simply: reduce(plus, zipwith(multiply, list1, list2)) Note that Miranda actually calls reduce fold though - well actually foldl or foldr depending on which end of the list you start at. Tom -- Tom Hughes ([EMAIL PROTECTED]) http://www.compton.nu/ ...Hacking's just another word for nothing left to kludge.
Re: Reduce [was: Re: Random items (old p5p issues)]
On Wed, Aug 02, 2000 at 12:22:10PM -0400, John Porter wrote:
sub interleave(\@;\@\@\@\@\@\@\@\@) {
...
}
sub mapf(;\@\@\@\@\@\@\@\@\@) {
...
}
I guess my question is, why do these need to be builtins?
sub push (\@@) { @{$_[0]} = (@{$_[0]}, @_[1..@_]); }
--
Addi Just imagine we are meeting the aliens for the first time.
ton Most people would just shoot them to see how many points they are
worth.
