[Axiom-math] What is the "+/" operator?

[Igor Khavkine]

Can someone explain this syntax? Looking at the Axiom .spad files, I
see that it has general usage +/[...some list construction...]. But,
AFAIK, it is not documented anywhere. Is it available only in .spad
files or also at the interpreter level?

Thanks.

Igor

[Martin Rubey]

Hi Igor,

nice to read from you!

Post by Igor Khavkine
Can someone explain this syntax? Looking at the Axiom .spad files, I
see that it has general usage +/[...some list construction...].

It is old syntax for reduce and should go away.

Martin

[Bill Page]

Post by Martin Rubey
...

Post by Igor Khavkine
Can someone explain this syntax? Looking at the Axiom .spad files,
I see that it has general usage +/[...some list construction...].

It is old syntax for reduce and should go away.

Rather, I think it is the equivalent BOOT syntax for reduce (right,
Gaby?) and I think it should stay in BOOT where there is no static
type checking. But I agree that it should not appear directly in SPAD
files. This expression returns a syntax error in the Axiom interpreter.

If I recall correctly, there a few other places in the Axiom library code
where old BOOT syntax appears (perhaps for efficiency or to avoid
awkard type manipulations) but should be really be replaced by a
more appropriate Spad idiom.


Regards,
Bill Page.

[Ralf Hemmecke]

Post by Martin Rubey

Post by Igor Khavkine
Can someone explain this syntax? Looking at the Axiom .spad files,
I see that it has general usage +/[...some list construction...].

It is old syntax for reduce and should go away.

I very much agree. The reason is that one should give an initial value
otherwise you might be surprised.

woodpecker:~/scratch>aldor -fx -laldor aaa.as
woodpecker:~/scratch>aaa
Sum: 29
Prod: 0

But if you like the

f/[a,b,c]

syntax, you can actually define a similar things in Aldor. (I guess,
SPAD would be just the same.)

Ralf

---BEGIN aaa.as
#include "aldor"
#include "aldorio"

macro Z == Integer;

Pkg: with {
/: ((Z, Z) -> Z, List Z) -> Z;
} == add {
(f: (Z, Z) -> Z) / (l: List Z): Z == {
empty? l => 0;
f(first l, f/(rest l));
}
}

main(): () == {
import from Pkg;
l1: List Z := [2,4,6,8,3,5,1];
sum: Z := (+)/l1;
prod: Z := (*)/l1;
stdout << "Sum: " << sum << newline;
stdout << "Prod: " << prod << newline;
}

main();
---END aaa.as

[Bill Page]

Post by Ralf Hemmecke
...
But if you like the
f/[a,b,c]
syntax, you can actually define a similar things in Aldor. (I guess,
SPAD would be just the same.)

That's cool, Ralf.

Take a look at this in the Axiom interpreter:

(1) -> Z ==> Integer
Type: Void

(2) -> /: ((Z, Z) -> Z, List Z) -> Z
Type: Void

(3) -> _/(f: (Z, Z) -> Z,l: List Z): Z == ( empty? l => 0; f(first l, f/(rest
l)))
Function declaration ?/? : (((Integer,Integer) -> Integer),List
Integer) -> Integer has been added to workspace.
Type: Void

(4) -> (+)/[1,2,3]
Compiling function / with type (((Integer,Integer) -> Integer),List
Integer) -> Integer

(4) 6
Type: PositiveInteger

--------

Regards,
Bill Page.

[Gabriel Dos Reis]

Ralf Hemmecke <***@hemmecke.de> writes:

| On 05/23/2007 06:50 PM, Bill Page wrote:
| > Quoting Martin Rubey <***@univie.ac.at>:
| >
| >> ... Igor Khavkine writes:
| >>
| >>> Can someone explain this syntax? Looking at the Axiom .spad files,
| >>> I see that it has general usage +/[...some list construction...].
| >>
| >> It is old syntax for reduce and should go away.
|
| I very much agree. The reason is that one should give an initial value
| otherwise you might be surprised.

I don't see why there should be a surprise.

Reduction through "/" is a functional on monoid operations, so one
should expect to give a unit element.

reduce on the other hand would want an initial value, or a value to
return when the list of operand is empty.



-- Gaby

[Ralf Hemmecke]

Post by Gabriel Dos Reis
| >
| >>
| >>> Can someone explain this syntax? Looking at the Axiom .spad files,
| >>> I see that it has general usage +/[...some list construction...].
| >>
| >> It is old syntax for reduce and should go away.
|
| I very much agree. The reason is that one should give an initial value
| otherwise you might be surprised.
I don't see why there should be a surprise.
Reduction through "/" is a functional on monoid operations, so one
should expect to give a unit element.

Sure. So whoever (which means a program) deals with "/" should first
check whether the second argument is a List over a monoid and that the
first argument is exactly *the* corresponding binary operation of that
particular monoid.

If I look at it that way, then "/" should be a unary operation since
what one currently writes as its first argument in

(+)/[1,2,3]

is redundant information. The monoid is specified by the argument of
List. (The problem arises if a set has two (or more) monoid structures
implemented, like Integer.)

Or are you saying that you have a domain (like Integer) and the first
argument then selects the monoid structure? What if I give a binary
function as the first argument which doesn't make the underlying set
into a monoid? That error cannot even be caught at runtime.

I am talking here about the compiler. If you have different plans with
the interpreter, I don't care at the moment, but for the compiler I see
no point why this form of "/" should be build into the (SPAD) language.

Post by Gabriel Dos Reis
reduce on the other hand would want an initial value, or a value to
return when the list of operand is empty.

At least we agree on this.

Ralf

[Gabriel Dos Reis]

On Thu, 24 May 2007, Ralf Hemmecke wrote:

| On 05/24/2007 01:23 AM, Gabriel Dos Reis wrote:
| > Ralf Hemmecke <***@hemmecke.de> writes:
| >
| > | On 05/23/2007 06:50 PM, Bill Page wrote:
| > | > Quoting Martin Rubey <***@univie.ac.at>:
| > | >
| > | > > ... Igor Khavkine writes:
| > | > >
| > | > > > Can someone explain this syntax? Looking at the Axiom .spad files,
| > | > > > I see that it has general usage +/[...some list construction...].
| > | > >
| > | > > It is old syntax for reduce and should go away.
| > |
| > | I very much agree. The reason is that one should give an initial value
| > | otherwise you might be surprised.
| >
| > I don't see why there should be a surprise.
| >
| > Reduction through "/" is a functional on monoid operations, so one
| > should expect to give a unit element.
|
| Sure. So whoever (which means a program) deals with "/" should first check
| whether the second argument is a List over a monoid and that the first
| argument is exactly *the* corresponding binary operation of that particular
| monoid.

Or, since we're in the realm of algebraic computation, make sure that the
functional "/" is declared to have the "right" type.

This somehow brings us back to my beef with the way Axiom currently handle
mathematical structures (the old Monoid debate).

| If I look at it that way, then "/" should be a unary operation since what one
| currently writes as its first argument in
|
| (+)/[1,2,3]
|
| is redundant information.

You know, any n-ary operator can be thought of as a unary operator :-)

| The monoid is specified by the argument of List.
| (The problem arises if a set has two (or more) monoid structures implemented,
| like Integer.)

Yes, and we are back to the old "monoid debate".

When it is "clear from context" which monoid structure is meant, then there
should be no need to explicitly specify the structure. Of course, deduction
does not always work, and in the case where there are ambiguities one should
be given a mean to disambiguate (using the current System F style notation).

| Or are you saying that you have a domain (like Integer) and the first argument
| then selects the monoid structure? What if I give a binary function as the
| first argument which doesn't make the underlying set into a monoid? That error
| cannot even be caught at runtime.

Think of it this way: What does reduction "/" need to work with?
A sequence of values and operation that happens to be a monoid operation
over the element type of the list. So, assume that from the context of use,
the compiler or interpreter (it does not matter which one) can deduce that the
operation + in

"+"/[1, 2, 3]

is a monoid operation integers -- because it has seen a prior statement to
that effect. What will be wrong?

-- Gaby

[Ralf Hemmecke]

Post by Gabriel Dos Reis
Or, since we're in the realm of algebraic computation, make sure that the
functional "/" is declared to have the "right" type.
This somehow brings us back to my beef with the way Axiom currently handle
mathematical structures (the old Monoid debate).

Of course, and we should leave it at that for the moment.

Post by Gabriel Dos Reis
Think of it this way: What does reduction "/" need to work with?
A sequence of values and operation that happens to be a monoid operation
over the element type of the list. So, assume that from the context of use,
the compiler or interpreter (it does not matter which one) can deduce that the
operation + in
"+"/[1, 2, 3]
is a monoid operation integers -- because it has seen a prior statement to
that effect. What will be wrong?

Nothing is wrong if the monoid structure can be figured out.

Just another remark about the statement above.
Even if that is common in the current SPAD code, I don't like to see
quotes around the +. Quotes should be reserved to produce strings.

You probably know that quotes in Aldor mean to call the function

string: Literal -> SomeType

So with a little work the above statement could be made litterally
working in Aldor, but for my taste I would rather like to write

(+)/[1,2,3]

since the parentheses let the + forget about its infixedness (see AUG).

Writing _+ (underscore plus) would be better, but also doesn't look very
attractive to me.

Ralf

[Gabriel Dos Reis]

On Thu, 24 May 2007, Ralf Hemmecke wrote:

| Just another remark about the statement above.
| Even if that is common in the current SPAD code, I don't like to see quotes
| around the +. Quotes should be reserved to produce strings.

that is a syntax issue, not semantics. :-)

I would not engage on syntax at this moment

| You probably know that quotes in Aldor mean to call the function
|
| string: Literal -> SomeType

Yes.

| So with a little work the above statement could be made litterally working in
| Aldor, but for my taste I would rather like to write
|
| (+)/[1,2,3]
|
| since the parentheses let the + forget about its infixedness (see AUG).

I know -- same in Haskell (and Boot).

| Writing _+ (underscore plus) would be better, but also doesn't look very
| attractive to me.

As I said, we're going there into syntax discussion, not semantics :-)

-- Gaby

[Gabriel Dos Reis]

"Bill Page" <***@synthesis.anikast.ca> writes:

| Quoting Martin Rubey <***@univie.ac.at>:
|
| > ... Igor Khavkine writes:
| >
| >> Can someone explain this syntax? Looking at the Axiom .spad files,
| >> I see that it has general usage +/[...some list construction...].
| >
| > It is old syntax for reduce and should go away.
|
| Rather, I think it is the equivalent BOOT syntax for reduce (right,
| Gaby?) and I think it should stay in BOOT where there is no static
| type checking.

Yes, and yes.

| But I agree that it should not appear directly in SPAD
| files.

Why?

| This expression returns a syntax error in the Axiom
| interpreter. If I recall correctly, there a few other places in the
| Axiom library code
| where old BOOT syntax appears (perhaps for efficiency or to avoid
| awkard type manipulations) but should be really be replaced by a
| more appropriate Spad idiom. Regards,

The interpreter uses the new parser, and I do not seem to see that
production there. I would like us to move to the new parser.
For leess confusion.

-- Gaby

[Gabriel Dos Reis]

Martin Rubey <***@univie.ac.at> writes:

| Hi Igor,
|
| nice to read from you!
|
| "Igor Khavkine" <***@gmail.com> writes:
|
| > Can someone explain this syntax? Looking at the Axiom .spad files, I
| > see that it has general usage +/[...some list construction...].
|
| It is old syntax for reduce and should go away.

Why should it go away?

-- Gaby

[Bill Page]

| >
| >> Can someone explain this syntax? Looking at the Axiom.spad
| >> files, I see that it has general usage +/[...list construction...].
| >
|
| > It is old syntax for reduce and should go away.
...
| But I agree that it should not appear directly in SPAD
| files.

Ralf Hemmecke writes:

| I very much agree. The reason is that one should give an initial value
| ...

Why?
Reduction through "/" is a functional on monoid operations,
so one should expect to give a unit element.

Ok, as Ralf showed it is possible in Axiom to write / as
such a functional:

1) -> Z ==> Integer

(2) -> /: ((Z, Z) -> Z, List Z) -> Z

(3) -> _/(f: (Z, Z) -> Z,l: List Z): Z == ( empty? l => 0; f(first l,
f/(restl)))
Function declaration ?/? : (((Integer,Integer) -> Integer),List
Integer) -> Integer has been added to workspace.

(4) -> (+)/[1,2,3]
Compiling function / with type (((Integer,Integer) -> Integer),List
Integer) -> Integer

Based on this I tentatively withdraw my object. However as you
point out:

empty? l => 0

is bogus. What we want is something like:

empty? l => Unit(f)

where f(x,Unit f) = x.

Unfortunately this returns to the old problem that Axiom's library
does not fully abstract 'Moniod'

http://wiki.axiom-developer.org/SandBoxMonoid

It defines another peculiar and parallel construct 'AbelianMonoid'
(that does not inherit from Monoid) in order to avoid the conflict of
names of operation associated with these separate monoid
structures:

)show Monoid
)show AbelianMonoid

Note the defintions of:

?*? : (%,%) -> %

and

?+? : (%,%) -> %

respectively, but:

(12) -> AbelianMonoid has Monoid

(12) false
Type: Boolean

Anyway we might write:

Unit(f) ==
f=(+)$Integer => 0
f=(*)$Integer => 1

So but maybe we could at least abstract the monoid 'Unit' by
overloading such functionals as 'Unit' and '/' defined in Monoid
and AbelianMonoid? Not perfect but ...

reduce on the other hand would want an initial value, or a value
to return when the list of operand is empty.

Indeed there are such variants of the 'reduce' operator in
Axiom, e.g.

)show FiniteLinearAggregate

Regards,
Bill Page.

[Gabriel Dos Reis]

On Wed, 23 May 2007, Bill Page wrote:

| (4) -> (+)/[1,2,3]
| Compiling function / with type (((Integer,Integer) -> Integer),List
| Integer) -> Integer
|
| Based on this I tentatively withdraw my object. However as you
| point out:
|
| empty? l => 0
|
| is bogus. What we want is something like:
|
| empty? l => Unit(f)
|
| where f(x,Unit f) = x.

Yes.

That should not come as a surprise to Axiomatizers. Here is why: List T is a
monoid with
(*) append as the monoid operation,
(*) and the empty list being the unit.

Consequently, sum or product, etc. are just *catamorphisms" you would express
naturally through the reduction functional (also known as "fold" in the
functional programming community). There is a good paper that should probably
be linked from Axiom's website:

"Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire"
Erik Meijer, Maarten Fokkinga, and Ross Paterson

http://wwwhome.cs.utwente.nl/~fokkinga/index.html#detail_0000003415



I must admit that where I first realized (four years ago) that Aldor (and
Spad) actually have the tokens "(|", "|)", "[|, "|]", "{|", and "|}",
I thought they were to support that kind of algebraic programming. However,
The Aldor manual just says they are reserved for future use without saying
much.

-- Gaby

[Bill Page]

Post by Gabriel Dos Reis
...
Consequently, sum or product, etc. are just *catamorphisms" you would
express naturally through the reduction functional (also known as "fold"
in the functional programming community). There is a good paper that
"Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire"
Erik Meijer, Maarten Fokkinga, and Ross Paterson
http://wwwhome.cs.utwente.nl/~fokkinga/index.html#detail_0000003415

Excellent, thanks!

I'll trade you another one (which it turns out actually references
Meijer, et al. :-)

"Fast and loose reasoning is morally correct"
by Nils Anders Danielsson, John Hughes, Patrik Jansson and
Jeremy Gibbons

http://doi.acm.org/10.1145/1111037.1111056

Post by Gabriel Dos Reis
I must admit that where I first realized (four years ago) that Aldor
(and Spad) actually have the tokens "(|", "|)", "[|, "|]", "{|", and "|}",
I thought they were to support that kind of algebraic programming.
However, the Aldor manual just says they are reserved for future
use without saying much.

.. interesting.

Regards,
Bill Page.

[Gabriel Dos Reis]

On Wed, 23 May 2007, Bill Page wrote:

| I'll trade you another one (which it turns out actually references
| Meijer, et al. :-)
|
| "Fast and loose reasoning is morally correct"
| by Nils Anders Danielsson, John Hughes, Patrik Jansson and
| Jeremy Gibbons
|
| http://doi.acm.org/10.1145/1111037.1111056

Thanks!

Actually, I already that one simply because I also had a paper POPL'06 on C++
concepts -- which is on how to design a type system that effectively supports
algebraic and generic programmming, which is somehow related to the paper you
cited above.

-- Gaby