Re: reduce metaoperator on an empty list
On Thursday 09 June 2005 12:21, John Macdonald wrote:
On Thu, Jun 09, 2005 at 06:41:55PM +0200, TSa (Thomas Sandla
wrote:
Edward Cherlin wrote:
That means that we have to straighten out the functions
that can return either a Boolean or an item of the
argument type. Comparison functions = = = != should
return only Booleans,
I'm not sure but Perl6 could do better or at least trickier
;) Let's assume that = = when chained return an
accumulated boolean and the least or greatest value where
the condition was true. E.g.
0 2 3 returns 0 but true
1 2 1 returns 1 but false
4 5 2 returns 2 but false
Then the reduce versions [] and [=] naturally come out as
min and strict min respectively.
Is it correct that [min] won't parse unless min is declared
as an infix op, which looks a bit strange?
if 3 min 4 { ... }
That's how it was done in APL. In fact, that's how every dyadic
(two-argument) function was done in APL. It looks strange at
first, but the syntax is simpler.
I eat my peas with honey.
I've done it all my life.
It makes them taste real funny,
But it keeps them on the knife.
The natural method of implementation would imply that the
final is returned:
0 2 3 returns 3 but true
1 2 1 returns 1 but false
4 5 2 returns 2 but false
The application of each stage of the chain has to remember
the right hand value (for the next stage of the comparison)
as well as the accumulated boolean result. When the boolean
result is true, that has and = returning the max, and and
= returning the min - the opposite of what you asked above.
In J one can do ()/ 0 1 1, evaluated as
0(11)
00
0
Then, since 00 is 0, and 01 is 1, 0 is a left identity of
(restricted to Booleans), and /'' is defined to be 0.
I don't suppose anybody here cares, but it turns out that Boolean
scans have a variety of uses, such as running parity, locating
transitions, and Gray Code to binary conversion, and Boolean
identity elements have their uses within these schemes.
--
Edward Cherlin
Generalist activist--Linux, languages, literacy and more
A knot! Oh, do let me help to undo it!
--Alice in Wonderland
http://cherlin.blogspot.com
Re: reduce metaoperator on an empty list
On Tuesday 07 June 2005 08:08, Larry Wall wrote: Okay, I've made up my mind. The err option is not tenable because it can cloak real exceptions, and having multiple versions of reduce is simply multiplying entities without adding much power. So let's allow an optional identvalue trait on operators. If it's there, reduce can use it. If it's not, reduce returns failure on 0 args. Built-in addition will have an identity value of 0, while multiplication will have an identity value of 1. String concatenation will have . The table of Iverson's chosen identities in J is at http://www.jsoftware.com/books/help/dictionary/d420.htm He uses _ for +Inf and __ for -Inf and does cover and . We can go as far as having -Inf on [] and +Inf on [], but maybe that means we have to define values that are positive and negative infinity on strings so we can get [gt] and [lt] indentity values. Those might be useful in any event. My Second System alarm is going off. What is the result of (-Inf)~(+Inf) or whatever the syntax would be? Or indeed (-Inf)~$String for any string? I know what it means to say that +Inf is the identity for a numeric min function, and -Inf for max, but an infinite string value baffles me. It would have to satisfy -Inf le , right? But with no values in between? When considering what extensions to make in APL and J, Iverson always asked what identities could be preserved at the boundaries. Thus if C is identical to A,B (APL catenation) with neither A nor B empty, then f/C is identical to (f/A)f(f/B). So using identity elements, we can extend this identity to some functions, and to arrays within their domains. What identities did you have in mind for string infinities? What sort of reduction can you do on Hello, ~(+Inf)~world? How does it print? What good is it at all? -- Edward Cherlin Generalist activist--Linux, languages, literacy and more A knot! Oh, do let me help to undo it! --Alice in Wonderland http://cherlin.blogspot.com
Re: reduce metaoperator on an empty list
On Tuesday 07 June 2005 22:35, Sam Vilain wrote:
Let's look at the type of one of the many `reduce' variants in
Haskell;
foldr1 :: (a - a - a) - [a] - a
This is the Perl6ish;
sub reduce( ::Code{( ::(someType), ::(someType) ) returns
::(someType)} $func, Array of ::(someType) ) returns
::(someType);
ie, the function $func supplied must take and return arguments
of a single type. So you have come to the same conclusion as
the FP folk :-).
I agree with that from the APL, J, Haskell, and FP directions and
several more.
That means that we have to straighten out the functions that can
return either a Boolean or an item of the argument type.
Comparison functions = = = != should return only Booleans,
IMHO, and the same for the string functions lt and gt and the
rest. It also means that we need primitive functions (operators)
like max and min that only return one of the arguments, and that
can also be used with a reduction operator (metaoperator).
--
Edward Cherlin
Generalist activist--Linux, languages, literacy and more
A knot! Oh, do let me help to undo it!
--Alice in Wonderland
http://cherlin.blogspot.com
Re: reduce metaoperator on an empty list
On Wednesday 01 June 2005 17:18, Deborah Pickett wrote: You haven't convinced me, but rather than flog a dead horse, I'll just suggest that we both reserve the right to say I told you so when there are several years' worth of Perl 6 code out there, and we see how common our respective examples are. No need to wait. There is a ton of APL and J code to inspect. Having predefined identity elements for reductions on empty arrays is widely exploited. -- Edward Cherlin Generalist activist--Linux, languages, literacy and more A knot! Oh, do let me help to undo it! --Alice in Wonderland http://cherlin.blogspot.com
Re: reduce metaoperator on an empty list
On Thursday 19 May 2005 20:42, Andrew Rodland wrote: On Thursday 19 May 2005 10:51 pm, Sam Vilain wrote: Edward Cherlin wrote: Here is the last answer from Ken Iverson, who invented reduce in the 1950s, and died recently. file:///usr/share/j504/system/extras/help/dictionary/intro 28.htm [snip] Thanks for bringing in a little history to the discussion. Those links are all local to your system; do you have internet reachable versions of them? These seem to be the original sources: http://www.jsoftware.com/books/help/dictionary/intro28.htm http://www.jsoftware.com/books/help/dictionary/d420.htm and so on. Front page is at http://www.jsoftware.com/books/help/dictionary/title.htm . I still haven't figured out what J is though. It's an enhanced APL without the funny characters. -- Edward Cherlin Generalist activist--Linux, languages, literacy and more A knot! Oh, do let me help to undo it! --Alice in Wonderland http://cherlin.blogspot.com
Re: reduce metaoperator on an empty list
On Friday 20 May 2005 07:18, John Macdonald wrote: Is there a built-in operator that doesn't have a meaningful identity value? Certainly. I first thought of exponentiation, but it has an identity value of 1 - you just have to realize that since it is a right associative operator, the identity has to be applied from the right. I suspect that if people ever get into writing code that works on operators instead of data, there would be additional uses found for the identity attribute (and there may be additional operator attributes that make sense there too, although none come immediately to mind). APL and J programmers have lots of examples. -- Edward Cherlin Generalist activist--Linux, languages, literacy and more A knot! Oh, do let me help to undo it! --Alice in Wonderland http://cherlin.blogspot.com
Re: reduce metaoperator on an empty list
On Friday 20 May 2005 08:11, TSa (Thomas Sandla) wrote:
John Macdonald wrote:
... (and there may be additional
operator attributes that make sense there too, although none
come immediately to mind).
Well, I wonder why people neglect the fact that the
neutral/identity element is not a property of the operator
alone?! Besides the associativity and commutativity of the
operator the inverse element---or the left and right
one---with respect to the underlying representation come at
least to my mind :)
Yes, a number of operators have an inverse on Boolean 0 and 1
only.
This would give an axiomatic type system:
class Num does Group[Num,+,0] {...}
class Num does Field[Num,+,0,*,1] {...}
class Str does Monoid[Str,~,''] {...}
class Complex does Field[Array[2] of Num,+,[0,0],*,[1,0]]
{...}
class 3DVector does VectorSpace[Array[3] of Num,+,[0,0,0]]
{...}
And it provides valuable information to the optimizer.
--
Edward Cherlin
Generalist activist--Linux, languages, literacy and more
A knot! Oh, do let me help to undo it!
--Alice in Wonderland
http://cherlin.blogspot.com
Re: Complex Arithmetic
On Thursday 19 May 2005 09:39, Luke Palmer wrote: On 5/19/05, Edward Cherlin [EMAIL PROTECTED] wrote: It turns out that the domain and range and the location of the cut lines have to be worked out separately for different functions. Mathematical practice is not entirely consistent in making these decisions, but in programming, there seems to be widespread agreement that the shared definitions used in the APL, Common LISP, and Ada standards are the best available. Do we want to get into all of this in Perl6? I'm not really sure I know what you mean by do we want to get into all of this?. If we're going to have a Complex class, we have to. But getting into it might involve saying that APL, CL, and Ada are the best, so we use those. This is the kind of problem where, if someone wants to get more precise, they turn to CPAN. Luke Math::Complex - complex numbers and associated mathematical functions http://cpan.uwinnipeg.ca/htdocs/perl/Math/Complex.html lists the complex functions, but with no information given there on domain, range (principal values), and branch cuts. The APL standard costs $350 from ANSI or 260 Swiss Francs from ISO, but the Common Lisp Hyperspec is available online for free. http://www.lispworks.com/documentation/HyperSpec/ as is the Ada Reference Manual. The CL and Ada definitions are incomplete. I'll have to find a copy of the APL standard. log(z) CL Hyperspec: The branch cut for the logarithm function of one argument (natural logarithm) lies along the negative real axis, continuous with quadrant II. The domain excludes the origin. Thus the range would be defined as -pi Im(log(z)) = pi sin(z) CL Hyperspec: Not defined for complex arguments. Ada RF says: The functions have their usual mathematical meanings. However, the arbitrariness inherent in the placement of branch cuts, across which some of the complex elementary functions exhibit discontinuities, is eliminated by the following conventions: (13) * The imaginary component of the result of the Sqrt and Log functions is discontinuous as the parameter X crosses the negative real axis. (14) * The result of the exponentiation operator when the left operand is of complex type is discontinuous as that operand crosses the negative real axis. (15) * The real (resp., imaginary) component of the result of the Arcsin and Arccos (resp., Arctanh) functions is discontinuous as the parameter X crosses the real axis to the left of -1.0 or the right of 1.0. (16) * The real (resp., imaginary) component of the result of the Arctan (resp., Arcsinh) function is discontinuous as the parameter X crosses the imaginary axis below -i or above i. (17) * The real component of the result of the Arccot function is discontinuous as the parameter X crosses the imaginary axis between -i and i. (18) * The imaginary component of the Arccosh function is discontinuous as the parameter X crosses the real axis to the left of 1.0. (19) * The imaginary component of the result of the Arccoth function is discontinuous as the parameter X crosses the real axis between -1.0 and 1.0. (20) The computed results of the mathematically multivalued functions are rendered single-valued by the following conventions, which are meant to imply the principal branch: (21) * The real component of the result of the Sqrt and Arccosh functions is nonnegative. (22) * The same convention applies to the imaginary component of the result of the Log function as applies to the result of the natural-cycle version of the Argument function of Numerics.Generic_Complex_Types (see G.1.1). (23) * The range of the real (resp., imaginary) component of the result of the Arcsin and Arctan (resp., Arcsinh and Arctanh) functions is approximately -Pi/2.0 to Pi/2.0. (24) * The real (resp., imaginary) component of the result of the Arccos and Arccot (resp., Arccoth) functions ranges from 0.0 to approximately Pi. (25) * The range of the imaginary component of the result of the Arccosh function is approximately -Pi to Pi. -- Edward Cherlin Generalist activist--Linux, languages, literacy and more A knot! Oh, do let me help to undo it! --Alice in Wonderland http://cherlin.blogspot.com
Re: hyperoperators and multi-dimensional datastructures
On Thursday 19 May 2005 12:48, Uri Guttman wrote: LP == Luke Palmer [EMAIL PROTECTED] writes: LP On 5/18/05, Anthony Heading [EMAIL PROTECTED] wrote: Is there a way to target hyperoperators at different axes of a multi-dimensional array? This is an attractive feature of various APL-like languages, viz. e.g. in J: a =. 2 5 $ i. 7 - a simple 2-by-5 array a 0 1 2 3 4 - like this 5 6 0 1 2 +/1 a - sum reduce over axis 1 10 14 That is, break the array into rows, and reduce each row. LP [+] @a +/2 a - sum reduce over axis 2 5 7 2 4 6 Actually, that's sum reduce over planes, which gives the default behavior when applied to a single plane, of breaking the plane into rows, and adding the rows to each other. The result is the same as from +/a . The rank conjunction () is tersely explained at http://www.jsoftware.com/books/help/dictionary/intro20.htm and more fully in The J Primer, J for C Programmers, and other online publications at http://www.jsoftware.com/publications_books.htm LP Can't think of any for this one. Or maybe it's this one that I can LP think of it for, and the other one which I can't. i can't spit out the syntax but here is the conceptual way i would do it. we do have multidimensional slices so we could grab each slice (maybe with zip?) and pass that to [+] and then grab the list of results back into a array/matrix with one less dimension than the original. Exactly how Iverson conceived rank for reduction. so it would be something like this: (very wacko pseudo code): @in[ * ; 2 ; * ] == map [+] == @out that was an (bad) attempt to slice the third entry in the second dimension to be summed. You might find it useful to examine this published source code for an early version of J http://www.math.uwaterloo.ca/apl_archives/j/early_j/src/j7/ to see how Iverson's crew implemented rank. The numbering is confusing, because they restarted at some point, so J5.0.4 is current. LP I think we're beginning to re-invent PDL. APL and J, too. Poorly. Amen. but is there a p6 pdl yet? they may not need much with multi-dim ops, slices, hyper and reduce all built in! also with type int (patform ints), they can get the dense storage needed (but losing any dimensional flexibility). uri -- Edward Cherlin Generalist activist--Linux, languages, literacy and more A knot! Oh, do let me help to undo it! --Alice in Wonderland http://cherlin.blogspot.com
Re: [unclassified] Re: reduce metaoperator on an empty list
On Thursday 19 May 2005 19:51, Sam Vilain wrote: Edward Cherlin wrote: Here is the last answer from Ken Iverson, who invented reduce in the 1950s, and died recently. file:///usr/share/j504/system/extras/help/dictionary/intro28 .htm http://www.jsoftware.com/books/help/dictionary/intro28.htm Sorry. It's exactly the same material the provide with their software, so I got confused. [snip] Thanks for bringing in a little history to the discussion. Those links are all local to your system; do you have internet reachable versions of them? Cheers, Sam. -- Edward Cherlin Generalist activist--Linux, languages, literacy and more A knot! Oh, do let me help to undo it! --Alice in Wonderland http://cherlin.blogspot.com
Re: reduce metaoperator
On Sat, May 07, 2005 at 010008PM -0700, Larry Wall wrote: On the other hand, since we've distinguished hyperops on infixes from hyperops on unaries, maybe an infix hyperop in unary position just does the thing to itself: @squares = * @list; which gives us a sum-of-squares that looks like this: @sumofsquares = [+] * @list; On the gripping hand, I can't think of any other operators I'd be likely to want to do that to, Ken Iverson had the same problem in the beginning. http://www.vector.org.uk/typography/pview.htm Even after tasting the fruits of generalizing the notation of mathematics to the form f/ that permitted the use of functions other than addition, it took some time before I recognized the advantages of a corresponding generalization of the inner or matrix product to allow the use of functions other than addition and multiplication. so forget it. Not worth teaching people. In languages that have reduce, scan, and inner product, it turns out that there are a number of other useful cases besides sum and sum of products. Minimax and maximin in game theory, for example. Boolean inner products on incidence matrices give a result showing which points are connected by paths of length two, and higher powers give connectedness on paths of length 'n', up to the point at which all path-connected components have been completely identified. 'And of equals' matches vectors (lists) against rows or columns of a table, depending on the order of the arguments. There are a number of others in the literature, some of them quite common in use. Once reduce, scan, and inner product can apply to user-defined functions, the possibilities open wide. Scan is an extension of reduce. It takes every initial segment of its vector argument, and does a reduce on it. (For right-to-left evaluation as in APL and J, this requires order N squared time on non-commutative functions.) J has extended scan to a version that operates on final segments. Examples at file:///usr/share/j504/system/extras/help/dictionary/intro14.htm This paper applies scans to inner product functions. http://portal.acm.org/citation.cfm?id=882077 The inner-product scan allows a straight-forward calculation of interest-bearing accounts or annuities without a loop in APL. Larry -- Edward Cherlin Generalist activist--Linux, languages, literacy and more A knot! Oh, do let me help to undo it! --Alice in Wonderland http//cherlin.blogspot.com
Complex Arithmetic
There was a discussion of the principal value of square root on this list some time back, making the point that for positive real numbers the positive square root is the value of the standard function. In the complex plane it is desirable to define the principal value at every point so as to produce a minimum of surprises, such as sudden jumps at discontinuities. However, there must necessarily be a line of discontinuity. Similarly for other complex-valued functions, particularly the trig and inverse trig functions, some of which are infinite-valued. It turns out that the domain and range and the location of the cut lines have to be worked out separately for different functions. Mathematical practice is not entirely consistent in making these decisions, but in programming, there seems to be widespread agreement that the shared definitions used in the APL, Common LISP, and Ada standards are the best available. Do we want to get into all of this in Perl6? -- Edward Cherlin Generalist activist--Linux, languages, literacy and more A knot! Oh, do let me help to undo it! --Alice in Wonderland http://cherlin.blogspot.com
Re: reduce metaoperator on an empty list
On Wednesday 18 May 2005 17:57, Matt Fowles wrote:
All~
What does the reduce metaoperator do with an empty list?
Here is the last answer from Ken Iverson, who invented reduce in
the 1950s, and died recently.
file:///usr/share/j504/system/extras/help/dictionary/intro28.htm
Identity Functions and Neutral
The monads 0+ and 1* are identity functions, and 0 and 1 are
said to be identity elements or neutrals of the dyads + and *
respectively. Insertion on an empty list yields the neutral of
the dyad inserted. For example:
+/ i.0 +/'' +/0{. 2 3 5
0 0 0
*/i.0 */'' */0{. 2 3 5
1 1 1
my @a;
[+] @a; # 0? exception?
[*] @a; # 1? exception?
[] @a; # false?
[||] @a; # false?
[] @a; # true?
Also if it magically supplies some correct like the above, how
does it know what that value is?
Thanks,
Matt
The page
file:///usr/share/j504/system/extras/help/dictionary/d420.htm
gives examples, unfortunately not easily readable ones.
If y has no items (that is, 0=#y), the result of u/y is the
neutral or identity element of the function u. A neutral of a
function u is a value e such that x u e x or e u x x, for
every x in the domain (or some significant sub-domain such as
boolean) of u . This definition of insertion over an argument
having zero items extends partitioning identities of the form
u/y (u/k{.y) u (u/k}.y) to the cases k e. 0,#y .
The identity function of u is a function ifu such that ifu y
u/y if 0=#y .
[The following table is greatly simplified by listing identity
elements rather than identity functions. Some are only left
identities, and some only right identities.]
Identity elementFor
0 + - +. ~: | (2 4 5 6 b.)
1 = : : * % *. %: ^ ! (1 9 11 13 b.)
_ .
__ .
'' ,
[and a few more that I will not explain here]
Glossary
J Description
+. or
~: objects are identical
| remainder, defined so that 0|N is N
b. Boolean functions from table
: less than or equal, restricted to Booleans here
(1:0 is 0, 1:1 is 1)
: greater than or equal, restricted to Booleans here
* times, restricted to Booleans here
% divide
*. and
%: root
^ exponential
! combinations
. minimum
. maximum
'' empty vector, list of length 0
, catenate, join lists
_ infinity
__ negative infinity
So (_ . N) is N, as is (__ . N).
All of these functions are defined in detail but quite tersely in
the J Dictionary, indexed on the page
file:///usr/share/j504/system/extras/help/dictionary/vocabul.htm
For examuple, the Boolean function b. is defined on the page
file:///usr/share/j504/system/extras/help/dictionary/dbdotn.htm
--
Edward Cherlin
Generalist activist--Linux, languages, literacy and more
A knot! Oh, do let me help to undo it!
--Alice in Wonderland
http://cherlin.blogspot.com
