"Bill Page" <[EMAIL PROTECTED]> writes:
| On Thu, Apr 3, 2008 at 11:13 AM, Gabriel Dos Reis wrote:
| >
| > Bill Page writes:
| >
| > | On Thu, Apr 3, 2008 at 10:58 AM, Gabriel Dos Reis wrote:
| > | >
| > | > Bill Page writes:
| > | >
| > | > | I don't think 'reduce(+,[])' requires too much magic - at least in
| > | > | the interpreter. Try:
| > | > |
| > | > | (1) -> myreduce(f,x)==(#x>1 => f(first x,myreduce(f,rest x)); #x=1
=> first x; f=_+ => 0; f=_* => 1;error "use: reduce(op,list,id)")
| Type: Void
| > | > ...
| > | > | (5) -> myreduce(+,[])
| > | > | Compiling function myreduce with type (Variable +,List None) ->
| > | > | NonNegativeInteger
| > | > |
| > | > | (5) 0
| > | > | Type:
NonNegativeInteger
| > | >
| > | > I'm very surprised you find that result OK.
| > | >
| > |
| > | I expect that
| > |
| > | reduce(+,A) + reduce(+,B) == reduce(+,concat(A,B))
| > |
| > | so what else could it be?
| >
| > So, you expect that reducing addition operator over a List None should
| > yield a NonNegativeInteger? I'm awfully surprised.
| >
|
| Well I *am* quite surprised by the signature that the interpreter
| chooses for this function:
|
| (Variable +,List None) -> NonNegativeInteger
The interpreter type-checks/infers argument types (separately) and then
do something (not always sensible). In this case, it could not find
ways to assign a type to '+', so it decided that it must be a
variable named '+'. Second, it looks at '[]' and sees that it is list
of something. It does not know what that something is (the notation
is ambiguous). So it decided that it is a list of nothing -- which is
utterly wrong. It should have been
forall(T: Type) . List T
but we don't have universal quantification yet. Now, from a variable
'+' and a list of nothing, it returns integer 0. I believe everybody
must reject that answer, even it beaned some vague resemblance to the
expected answer, because we don't just want the `right answer'. We
want the correct answer.
The notion of reduction is that:
(1) one can left- or right- reduce a magma operation non non-empty
sequences of items;
(2) or just reduce (left or right does not matter) an
associative operation on non-empty sequence of items;
(3) or just reduce (left or right does not matter) a monoid
operation on a possibly empty sequence of items.
In all causes, the type of the result is the type of the items in the
sequence. So, getting NonNegativeInteger 0 from List None reduction
must look wrong -- just like it is wrong for systems to return integer
0 and two matrices are subtracted.
The truth is that
reduce(+,[])
is doubly ambiguous: there are at least a dozen of stuff called '+'.
And [] is the empty list of type any type. I don't see how 0 could be
seen as the result.
| and as I said previously, I find it a little "magic" that the
| expression 'f(first x,myreduce(f,rest x))' apparently compiles as the
| naive user might expect.
a very special naive user then :-)
| Really should have written '_+$Integer'
| instead of just '+'
|
| (2) -> myreduce(_+$Integer,[])
| Compiling function red with type (((Integer,Integer) -> Integer),
| List None) -> Integer
|
| (2) 0
| Type: NonNegativeInteger
Even there, I would have expected a type error. The type of the
operation does not match the type of the contained element (None).
|
| But now perhaps equally "magic" is that 'f=_+ => 0' again naively just works
...
|
| In the library code what I really wanted was something like this
| modification to ListAggregate:
|
| reduce(f, x) ==
| if empty? x then
| if S has AbelianMonoid then
| f=_+$S => 0$S
| if S has Monoid then
| f=_*$S => 1$S
| error "reducing over an empty list needs the 3 argument form"
| reduce(f, rest x, first x)
|
| since presumably then we are checking the specific algebraic
| properties of the operation. But this does not compile in Spad.
Yeah.
-- Gaby
-------------------------------------------------------------------------
Check out the new SourceForge.net Marketplace.
It's the best place to buy or sell services for
just about anything Open Source.
http://ad.doubleclick.net/clk;164216239;13503038;w?http://sf.net/marketplace
_______________________________________________
open-axiom-devel mailing list
open-axiom-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/open-axiom-devel
