[Axiom-math] Re: [fricas-devel] Re: iterators and cartesian product.

"Bill Page" <***@newsynthesis.org> writes:

| On 22 Oct 2007 13:40:26 +0200, Martin Rubey wrote:
| >
| > Francois Maltey writes:
| >
| > > > [matrix [[a,b,15-a-b],[c,d,15-c-d]] _
| > > > for (a,b,c,d) in CartesianProduct([1..9, 1..9, 1..9, 1..9])]
| >
| >
| > > But what is the signature of this function CartesianProduct ?
| >
| > Sorry, I didn't bother to think about a good way to specify the Cartesian
| > product itself, but I think what Bill showed was quite good.
| >
|
| I would like to consider what is?
|
| 1..9
|
| Right now in Axiom this is evaluated as a member of 'Segment
| PositiveInteger', i.e. the domain of all such segments. But in general
| I think I would prefer if '1..9' actually denoted a domain - a subset
| of the Positive Integers - with members 1, 2, 3 ... etc.

Couold you elaborate on why `1..9' should denote a domain, and what
the benefits would be?

| I am having a little trouble actually articulating the difference
| between these two. It seems somewhat artificially imposed by Axiom's
| type hierarchy that does not easily allow domains to be members of
| domains. (Domains belong to categories, not other domains.).

In fact, that is not so clear. If you ask the interpreter what is the
type of Domain, it would answer 'SubDomain Domain'. And don't go query
the type of SubDomain Domain :-/

| We want to be able to write:
|
| DirectProduct(4,1..9)
|
| but this does not work because '1..9' is not a type - it is an object
| of 'Segment PositiveInteger'.

If it worked, what would you have liked the mathematical meaning to
be, and why?

[I'm not being facetious, I'm trying to understand your perspectives]

| Another example of this in Axiom that *does* work right now is:
|
| DirectProduct(4,OrderedVariableList [a,b,c])
|
| OrderedVariableList is a domain constructor that takes something of
| List Symbol as a parameter. In order to introduce '1..9' as a domain
| it would be possible to introduce new domain constructor like
|
| )abbrev domain INTS IntegerSegment
| IntegerSegment(S:Segment Integer): with Finite ...
|
| that takes something of 'Segment Integer' as a parameter. Do we want
| 'IntegerSegment' to also be a subdomain of Integer?. In any case,
| then we could write:

I do not see obvious reasons why I would want IntegerSegment to be a
subdomain of Integer.

| DirectProduct(4,IntegerSegment 1..9)
|
| But somehow the distinction between '1..9' and 'IntegerSegment 1..9'
| and '[a,b,c]' and 'OrderedVariableList [a,b,c]' seems artificial.
|
| It occurs to me that one might like at least the Axiom interpreter to
| perform some kind of automatic coercion from 'x' in a domain like
| 'Segment Integer' into the *category* consisting of domains
| 'IntegerSegment(x)'.
|
| I think Gaby recently referred to this preference for things like
| '1..9' and [a,b,c] to also
| represent domains as a more "categorical" approach.

In general, I would like OpenAxiom to take a more categorial approach
to almost everything -- in particular `cross'.
However, I'm interested in some of you ideas here. Please, could you
elaborate, and if possible, give some use cases?

-- Gaby

Bill Page

2007-10-22 16:03:50 UTC

Post by Gabriel Dos Reis
...
|
| I would like to consider what is?
|
| 1..9
|
| Right now in Axiom this is evaluated as a member of 'Segment
| PositiveInteger', i.e. the domain of all such segments. But in general
| I think I would prefer if '1..9' actually denoted a domain - a subset
| of the Positive Integers - with members 1, 2, 3 ... etc.
Couold you elaborate on why `1..9' should denote a domain, and what
the benefits would be?

Well, for one I could then write the cross-product of such domains:

Product(1..9,1..4)

and iterate over them like this

for i in expand()$Product(1..9,1..4)

where 'expand' (or whatever we decide we want to call this operator
from the category Finite). Or even better if the generator 'expand'
also is implicit for any domain in Finite so that we could write:

for i in Prooduct(1..9,1..4)

Of course we could also simply define some new 'CrossProduct' domain
constructor that takes as argument something of type 'Segment Integer'
but this seems considerably less general.

Post by Gabriel Dos Reis
| I am having a little trouble actually articulating the difference
| between these two. It seems somewhat artificially imposed by Axiom's
| type hierarchy that does not easily allow domains to be members of
| domains. (Domains belong to categories, not other domains.).
In fact, that is not so clear. If you ask the interpreter what is the
type of Domain, it would answer 'SubDomain Domain'. And don't go query
the type of SubDomain Domain :-/

Yes. As I have said several times before (e.g. in an exchange a few
years with Peter Broadbery), I think this upper part of the Axiom
domain/category type system is a little messed up. I believe Aldor
presents one possible solution to these problems but there may be
other solutions.

Post by Gabriel Dos Reis
|
| DirectProduct(4,1..9)
|
| but this does not work because '1..9' is not a type - it is an object
| of 'Segment PositiveInteger'.
If it worked, what would you have liked the mathematical meaning to
be, and why?

I would like the result to be a finite domain. More interesting
perhaps is if I wrote

DirectProduct(4, PrimeField 7)

and then the result domain inherits a lot of structure from such fields.

Post by Gabriel Dos Reis
[I'm not being facetious, I'm trying to understand your perspectives]

Good! :-)

Post by Gabriel Dos Reis
|
| DirectProduct(4,OrderedVariableList [a,b,c])
|
| OrderedVariableList is a domain constructor that takes something of
| List Symbol as a parameter. In order to introduce '1..9' as a domain
| it would be possible to introduce new domain constructor like
|
| )abbrev domain INTS IntegerSegment
| IntegerSegment(S:Segment Integer): with Finite ...
|
| that takes something of 'Segment Integer' as a parameter. Do we want
| 'IntegerSegment' to also be a subdomain of Integer?. In any case,
I do not see obvious reasons why I would want IntegerSegment to be a
subdomain of Integer.

Well for example, maybe I would want to write:

x:IntegerSegment 1..9
y:=x + 1

where the type of 'y' might be Union(IntegerSegment 1..9,"failed").

Post by Gabriel Dos Reis
| DirectProduct(4,IntegerSegment 1..9)
|
| But somehow the distinction between '1..9' and 'IntegerSegment 1..9'
| and '[a,b,c]' and 'OrderedVariableList [a,b,c]' seems artificial.
|
| It occurs to me that one might like at least the Axiom interpreter to
| perform some kind of automatic coercion from 'x' in a domain like
| 'Segment Integer' into the *category* consisting of domains
| 'IntegerSegment(x)'.
|
| I think Gaby recently referred to this preference for things like
| '1..9' and [a,b,c] to also
| represent domains as a more "categorical" approach.
In general, I would like OpenAxiom to take a more categorial approach
to almost everything -- in particular `cross'.

Great. One should probably try to be more specific here about what one
means by a "categorical approach". You could mean for example trying
to provide mathematical semantics based on category theory. I have
discussed before how one really should define 'cross' as a categorial
limit in terms of the existence of the unique (universal) operation:

product: (A:Type, A->X,A->Y) -> (A->%)

See: http://wiki.axiom-developer.org/SandBoxLimitsAndColimits

Post by Gabriel Dos Reis
However, I'm interested in some of you ideas here. Please, could you
elaborate, and if possible, give some use cases?

Do you mean use cases for operations like 'product' above or use cases
of the domain 'Product' or use cases of the domain 'IntegerSegment'?
:-)

Regards,
Bill Page.

Gabriel Dos Reis

2007-10-22 16:20:16 UTC

On Mon, 22 Oct 2007, Bill Page wrote:

|
| On 22 Oct 2007 10:16:33 -0500, wrote:
| > Bill Page writes:
| > ...
| > |
| > | I would like to consider what is?
| > |
| > | 1..9
| > |
| > | Right now in Axiom this is evaluated as a member of 'Segment
| > | PositiveInteger', i.e. the domain of all such segments. But in general
| > | I think I would prefer if '1..9' actually denoted a domain - a subset
| > | of the Positive Integers - with members 1, 2, 3 ... etc.
| >
| > Couold you elaborate on why `1..9' should denote a domain, and what
| > the benefits would be?
| >
|
| Well, for one I could then write the cross-product of such domains:
|
| Product(1..9,1..4)

What would be its meaning?
The reason I'm after the meaning is that once I figured out what you
really want to express -- not the syntax -- then I can figure out
how to work on the syntax.

| and iterate over them like this
|
| for i in expand()$Product(1..9,1..4)
|
| where 'expand' (or whatever we decide we want to call this operator
| from the category Finite). Or even better if the generator 'expand'
| also is implicit for any domain in Finite so that we could write:
|
| for i in Prooduct(1..9,1..4)
|
| Of course we could also simply define some new 'CrossProduct' domain
| constructor that takes as argument something of type 'Segment Integer'
| but this seems considerably less general.

If we introduce a Cross domain, I would expect it to take a sequence
(e.g. List) of domain as argument. Why would that be less general?

| > | I am having a little trouble actually articulating the difference
| > | between these two. It seems somewhat artificially imposed by Axiom's
| > | type hierarchy that does not easily allow domains to be members of
| > | domains. (Domains belong to categories, not other domains.).
| >
| > In fact, that is not so clear. If you ask the interpreter what is the
| > type of Domain, it would answer 'SubDomain Domain'. And don't go query
| > the type of SubDomain Domain :-/
| >
|
| Yes. As I have said several times before (e.g. in an exchange a few
| years with Peter Broadbery), I think this upper part of the Axiom
| domain/category type system is a little messed up. I believe Aldor
| presents one possible solution to these problems but there may be
| other solutions.

Well, my own opinions are not definite yet, but I do see some value to
the `domain theoretic' approach to this matter. In that scheme
`Categories' are left to just to ensure the availability of certain
operators to help the compiler in semantics analysis and efficient
code-generation.

Bill Page

2007-10-22 16:48:33 UTC

Post by Gabriel Dos Reis
...
|
|
| Product(1..9,1..4)
What would be its meaning?
The reason I'm after the meaning is that once I figured out what you
really want to express -- not the syntax -- then I can figure out
how to work on the syntax.

You mean that was not clear in what followed in my previous message?
As I said, I want

Product(1..9,1..4)

to be a domain - the cross-product of two other domains.

Post by Gabriel Dos Reis
| and iterate over them like this
|
| for i in expand()$Product(1..9,1..4)
|
| where 'expand' (or whatever we decide we want to call this operator
| from the category Finite). Or even better if the generator 'expand'
|
| for i in Prooduct(1..9,1..4)
|
| Of course we could also simply define some new 'CrossProduct' domain
| constructor that takes as argument something of type 'Segment Integer'
| but this seems considerably less general.
If we introduce a Cross domain, I would expect it to take a sequence
(e.g. List) of domain as argument. Why would that be less general?

What I call 'Product' you can call 'Cross', I have no problem with the
name. If you want 'Cross' to have a signature like:

Cross(x:List Type): with ... appropriate access operations

that is fine. But still you would not be able to write:

Cross [1..9,1..4]

Post by Gabriel Dos Reis
...
|
| Yes. As I have said several times before (e.g. in an exchange a few
| years with Peter Broadbery), I think this upper part of the Axiom
| domain/category type system is a little messed up. I believe Aldor
| presents one possible solution to these problems but there may be
| other solutions.
Well, my own opinions are not definite yet, but I do see some value to
the `domain theoretic' approach to this matter. In that scheme
`Categories' are left to just to ensure the availability of certain
operators to help the compiler in semantics analysis and efficient
code-generation.

Gabriel Dos Reis

2007-10-22 17:03:08 UTC

On Mon, 22 Oct 2007, Bill Page wrote:

| As I said, I want
|
| Product(1..9,1..4)
|
| to be a domain - the cross-product of two other domains.

I do not think

I want 1..9 to be a domain so that I can write
Product(1..9, 1..4) to be a cross product of two domains

is an explanation of why `1..9' should be a domain. I would like a
mathematical meaning so that I would not have to tell students

`1..9' is a domain because Bill Page wanted to write Product(1..9, 1..4)
as a Catersian product of two domains.

That is why I'm after the semantics.

-- Gaby

Bill Page

2007-10-22 18:06:01 UTC

Post by Gabriel Dos Reis
| As I said, I want
|
| Product(1..9,1..4)
|
| to be a domain - the cross-product of two other domains.
I do not think
I want 1..9 to be a domain so that I can write
Product(1..9, 1..4) to be a cross product of two domains
is an explanation of why `1..9' should be a domain.

As I said earlier, I think the semantics of Product should be given
categorically by the existence of the unique operation

Product(X:Type, Y:Type): with ...

product: (A:Type, A->X,A->Y) -> (A->%)

as a categorical limit.

Regards,
Bill Page.

Gabriel Dos Reis

2007-10-22 18:10:44 UTC

Bill Page

2007-10-31 16:29:50 UTC

Bill,
you probably mean something like
map(product(wholePart, sin), [1.1,2.2,3.3])
right?

No. The signature must include a dependent type, like this:

product: (A:Type, A->X,A->Y) -> (A->%)

wholePart: Float -> Integer
sin: Float -> Float; -- I don't like Float, by the way... ;-)
[1.1,2.2,3.3]: List Float
So we must have
product: (Float -> Integer, Float -> Float) ->
(Float -> Product(Integer, Float))
and a corresponding signature for map. You surely believe that I can
program exactly that in Aldor.

To define 'product' in general (i.e. as a categorical limit) for any
domain Product(A,B) and domain C we must have

product(C,f,g):C->Product(A,B)

defined for any functions

f:C->A
g:C->B

I don't think you can do that without passing the independent domain C.

But I guesss that is not your point. Your point is (please correct) that
you want a categorical definition of "Product".
Product(A, B) should automatically export
product: (A, B) -> %

No, this is not well defined.

as well as
product: (X -> A, X -> B) -> X -> %.

What is X above?

You don't want to write down that function definition yourself, right?

Well, I would actually expect it to be exported by a basic built-in
domain like 'Record' since that is what most directly corresponds to
categorical Product. If this was made sufficiently general, there
would be no need for a separately programmed domain in the library.

In terms of Aldor, we have Product = Cross and that is a built-in type.
So it should be possible (and perhaps be reasonable to extend Cross
through the compiler, ie, give it a few more exports than it has now.

Yes exactly, although I am not sure why we need both Cross and Record.

But maybe your proposal goes further and you want to be able to define
domains/functors through categorical limit constructions. So, in fact,
you want to enrich Aldor/SPAD by new keywords "Limit" and "CoLimit" and
make "Cross" a library defined type.

Yes, maybe. What might be even nicer is if it were possible to
implement adjoint functors as described by Saul Youssef as an even
more basic concept in Aldor/SPAD. He shows how to define Limits and
CoLimits in this more fundamental way.

If that is what you think/want, then I can somehow understand you and
would even support it. But to my taste that was not clear enough yet in
all the previous discussions.
(I have no problem if you forward this and/or my previous mail to the
lists.)

Ok, thanks.

Regards,
Bill Page.

Ralf Hemmecke

2007-10-31 16:47:53 UTC

Post by Bill Page
Yes exactly, although I am not sure why we need both Cross and Record.

Elements of Record are mutable, elements of Cross are not.

Ralf

PS: Shouldn't this discussion go to axiom-developer instead of axiom-math?

Bill Page

2007-10-31 17:16:32 UTC

Post by Bill Page
Yes exactly, although I am not sure why we need both Cross and Record.

Elements of Record are mutable, elements of Cross are not.

Ok, thanks. I am not so sure how to deal with that distinction in a
"categorical" manner. I suppose mutability is an imperative-style
programming notion. I think the lack of mutability in functional
languages like Haskell is one of the harder things to get used to but
at the same time one of it's greatest strengths. In general I would
like Aldor/SPAD to promote a more functional style without necessarily
requiring it.

Post by Ralf Hemmecke
PS: Shouldn't this discussion go to axiom-developer instead of axiom-math?

Maybe you are right but recently I have been avoiding axiom-developer
since Tim made it clear that the Axiom project per se was interested
primarily in documentation and the "30 year horizon". I originally
included axiom-math because I thought there might still be some people
subscribed there who are interested in more immediate issues in Axiom
and about category theory in Axiom/Aldor. But I have to admit that the
profusion of email lists about Axiom, it's forks and Aldor is
confusing to me and probably to our collective disadvantage.

Regards,
Bill Page.

Gabriel Dos Reis

2007-10-31 23:58:41 UTC

On Wed, 31 Oct 2007, Bill Page wrote:

| I think the lack of mutability in functional
| languages like Haskell is one of the harder things to get used to but
| at the same time one of it's greatest strengths.

Haskell has imperative skin -- check out `monad'.

-- Gaby

Bill Page

2007-11-01 00:39:29 UTC

Post by Gabriel Dos Reis
| I think the lack of mutability in functional
| languages like Haskell is one of the harder things to get used
| to but at the same time one of it's greatest strengths.
Haskell has imperative skin -- check out `monad'.

Yes, I think that is a very good point and it does soften my point
above a little. "lack of mutability" is misleading. Mutable structures
can be modeled in Haskell as a derived concept. For example:

http://en.wikipedia.org/wiki/Monads_in_functional_programming

(See especially references at the end of the article.)

Using a purely functional language does not mean that imperative-style
programming is impossible in that language. It might even be
interesting to consider implementing something akin to monads in
Aldor/SPAD, but I think you will agree that fundamentally these
languages were not designed to be purely functional.

Regards,
Bill Page.

Gabriel Dos Reis

2007-11-01 01:11:18 UTC

On Wed, 31 Oct 2007, Bill Page wrote:

|
| On 10/31/07, Gabriel Dos Reis wrote:
| >
| > On Wed, 31 Oct 2007, Bill Page wrote:
| >
| > | I think the lack of mutability in functional
| > | languages like Haskell is one of the harder things to get used
| > | to but at the same time one of it's greatest strengths.
| >
| > Haskell has imperative skin -- check out `monad'.
| >
|
| Yes, I think that is a very good point and it does soften my point
| above a little. "lack of mutability" is misleading. Mutable structures
| can be modeled in Haskell as a derived concept. For example:
|
| http://en.wikipedia.org/wiki/Monads_in_functional_programming
|
| (See especially references at the end of the article.)
|
| Using a purely functional language does not mean that imperative-style
| programming is impossible in that language.

Note however that some functional programming evangelists consider the
'monad' solution to the state problem as a `grotesques hack': If you
use a state in your function, all the callers will be infected.

| It might even be
| interesting to consider implementing something akin to monads in
| Aldor/SPAD,

There already existe a domain called Monad in the Axiom family -- it
is a well mathematically defined notion.

I do not however see myself implement the Haskell solution for Axiom.
I would prefer a more powerful effect system for OpenAxiom.

| but I think you will agree that fundamentally these
| languages were not designed to be purely functional.

I do not see `purely functional' as as necessity.

-- Gaby

Bill Page

2007-11-01 01:42:14 UTC

...
| It might even be interesting to consider implementing
| something akin to monads in Aldor/SPAD,
There already existe a domain called Monad in the Axiom family --
it is a well mathematically defined notion.

Perhaps I am being dense but I do not see what this has to do with the
concept of Monad in Haskell. Could you please explain?

++ Description:
++ Monad is the class of all multiplicative monads, i.e. sets
++ with a binary operation.

)show Monad
Monad is a category constructor
Abbreviation for Monad is MONAD
This constructor is exposed in this frame.
Issue )edit /usr/local/lib/axiom/target/i686-suse-linux/../../src/algebra/MONAD.spad
to see algebra source code for MONAD

------------------------------- Operations --------------------------------
?*? : (%,%) -> % ?**? : (%,PositiveInteger) -> %
?=? : (%,%) -> Boolean coerce : % -> OutputForm
hash : % -> SingleInteger latex : % -> String
?~=? : (%,%) -> Boolean
leftPower : (%,PositiveInteger) -> %
rightPower : (%,PositiveInteger) -> %

-----

I think what is required "mathematically" for Haskell-like monads in
Axiom is something more related to the concept of monad in category
theory. Ref:

http://en.wikipedia.org/wiki/Monad_%28category_theory%29

perhaps implemented in the style promoted by Saul Youssef in his
article about category theory in Aldor.

I do not however see myself implement the Haskell solution
| for Axiom. I would prefer a more powerful effect system for
| OpenAxiom.

Could you describe what you mean by "effect system"?

| but I think you will agree that fundamentally these
| languages were not designed to be purely functional.
I do not see `purely functional' as as necessity.

In that case what is wrong with effects as implemented in SPAD's
imperative-style programming right now?

I am sorry. I don't mean to sound rude, but I just don't understand
where your comments lead. Could you say something more about what you
are considering for implemention in OpenAxiom?

Regards,
Bill Page.

Gabriel Dos Reis

2007-11-01 01:55:10 UTC

On Wed, 31 Oct 2007, Bill Page wrote:

| On 10/31/07, Gabriel Dos Reis wrote:
| >
| > On Wed, 31 Oct 2007, Bill Page wrote:
| > ...
| > | It might even be interesting to consider implementing
| > | something akin to monads in Aldor/SPAD,
| >
| > There already existe a domain called Monad in the Axiom family --
| > it is a well mathematically defined notion.
| >
|
| Perhaps I am being dense but I do not see what this has to do with the
| concept of Monad in Haskell.

They are the same categorial notion. What youhave in Haskell is a
computer scientist application of the categorial notion of `monad'.
Haskell's take derive from Moggi's work on applying monads to defined
program semantics. See his seminal work. And it is also true that you
don't need to understand category theory before using `monad's in
Haskell. Which makes some haskellers say that they did a really bad job
at picking the name.

[...]

| > I do not however see myself implement the Haskell solution
| > | for Axiom. I would prefer a more powerful effect system for
| > | OpenAxiom.
| >
|
| Could you describe what you mean by "effect system"?

http://www.irisa.fr/prive/talpin/papers/jfp92.pdf

| > | but I think you will agree that fundamentally these
| > | languages were not designed to be purely functional.
| >
| > I do not see `purely functional' as as necessity.
| >
|
| In that case what is wrong with effects as implemented in SPAD's
| imperative-style programming right now?

I did not make a statement to that effect, so I do not exactly what
you mean. Could you clarify?

| I am sorry. I don't mean to sound rude, but I just don't understand
| where your comments lead. Could you say something more about what you
| are considering for implemention in OpenAxiom?

Among other things, a type and effect system so that I can know which
domain are purely functional -- therefore the caching implementation
technique is sound for them -- and which have effects, therefore
should not be cached.

-- Gaby

Bill Page

2007-11-01 02:29:45 UTC

Post by Gabriel Dos Reis
| >
| > ...
| > | It might even be interesting to consider implementing
| > | something akin to monads in Aldor/SPAD,
| >
| > There already existe a domain called Monad in the Axiom family --
| > it is a well mathematically defined notion.
| >
|
| Perhaps I am being dense but I do not see what this has to do with the
| concept of Monad in Haskell.
They are the same categorial notion.

That is not clear to me.

Post by Gabriel Dos Reis
What you have in Haskell is a computer scientist application of the
categorial notion of `monad'.

Agreed.

Post by Gabriel Dos Reis
Haskell's take derive from Moggi's work on applying monads to defined
program semantics. See his seminal work.

Yes.

Post by Gabriel Dos Reis
And it is also true that you don't need to understand category
theory before using `monad's in Haskell.

I don't think that is extraordinary. One doesn't need to know much
about formal semantics of programming languages in general before
starting to program. And more relevant to this thread: I don't think
you need to know anything about category before using Record or Cross
in Axiom/Aldor either, but I would still insist that to describe it
formally as a limit in category theory adds something to the issue of
language and library design.

Post by Gabriel Dos Reis
Which makes some haskellers say that they did a really bad job
at picking the name.

Well, the language is called *Haskell* afterall. Do those haskellers
who think monad is a bad name even remember who Haskell Curry was!?
;-) [Rhetorical, don't answer that ...]

Ok, thanks. This quote from the article:

"Similar to types, effects describe how expressions affect the store
in a functional language extended with imperative constructs. Types
and effects can be statically computed by algebraic reconstruction
[Jouvelot]."

makes it more clear to me.

Your reference above makes it more clear to me what you might have in
mind. Perhaps you are thinking that it might be possible to give a
formal description of effects related to the imperative constructs in
SPAD as it exists now (or perhaps some subset of the imperative part
of the language). I am sceptical but I really don't know enough to
comment further.

Post by Gabriel Dos Reis
| I am sorry. I don't mean to sound rude, but I just don't understand
| where your comments lead. Could you say something more about
| what you are considering for implemention in OpenAxiom?
Among other things, a type and effect system so that I can know which
domain are purely functional -- therefore the caching implementation
technique is sound for them -- and which have effects, therefore
should not be cached.

I think that is a very worthwhile goal. Thanks for explaining.

Regards,
Bill Page.

Gabriel Dos Reis

2007-11-01 02:54:51 UTC

On Wed, 31 Oct 2007, Bill Page wrote:

|
| On 10/31/07, Gabriel Dos Reis wrote:
| >
| > On Wed, 31 Oct 2007, Bill Page wrote:
| >
| > | On 10/31/07, Gabriel Dos Reis wrote:
| > | >
| > | > On Wed, 31 Oct 2007, Bill Page wrote:
| > | > ...
| > | > | It might even be interesting to consider implementing
| > | > | something akin to monads in Aldor/SPAD,
| > | >
| > | > There already existe a domain called Monad in the Axiom family --
| > | > it is a well mathematically defined notion.
| > | >
| > |
| > | Perhaps I am being dense but I do not see what this has to do with the
| > | concept of Monad in Haskell.
| >
| > They are the same categorial notion.
|
| That is not clear to me.
|
| > What you have in Haskell is a computer scientist application of the
| > categorial notion of `monad'.
|
| Agreed.

I cannot reconcile both your statements.

Anyway, check out

"Comprehending Monads", by Philip Wadler
Proceedings of the 1990 ACM conference on LISP and functional
programming

[...]

| > Which makes some haskellers say that they did a really bad job
| > at picking the name.
| >
|
| Well, the language is called *Haskell* afterall. Do those haskellers
| who think monad is a bad name even remember who Haskell Curry was!?
| ;-) [Rhetorical, don't answer that ...]

http://research.microsoft.com/~simonpj/papers/haskell-retrospective/HaskellRetrospective.pdf

skip to page 40.

-- Gaby

Bill Page

2007-11-01 03:13:43 UTC

I mean: What does Monad as defined in the Axiom library right now:

++ Monad is the class of all multiplicative monads, i.e. sets
++ with a binary operation.

have to do with Monads in Haskell? Isn't that what you implied by your comment?

"There already existe a domain called Monad in the Axiom family -- it
is a well mathematically defined notion."

Or did you just mean that if one implemented Haskell-style monads in
Axiom, one should use a different name?

Post by Gabriel Dos Reis
http://research.microsoft.com/~simonpj/papers/haskell-retrospective/HaskellRetrospective.pdf
skip to page 40.

Oh yah, I remember that. I suppose we could use that name for monad in Axiom:

)abbrev domain WarmFuzzyThing WFT
...
;-)

Regards,
Bill Page.

Gabriel Dos Reis

2007-11-01 03:16:52 UTC

On Wed, 31 Oct 2007, Bill Page wrote:

|
| On 10/31/07, Gabriel Dos Reis wrote:
| >
| > On Wed, 31 Oct 2007, Bill Page wrote:
| > ...
| > | > |
| > | > | Perhaps I am being dense but I do not see what this has to do with the
| > | > | concept of Monad in Haskell.
| > | >
| > | > They are the same categorial notion.
| > |
| > | That is not clear to me.
| > |
| > | > What you have in Haskell is a computer scientist application of the
| > | > categorial notion of `monad'.
| > |
| > | Agreed.
| >
| > I cannot reconcile both your statements.
| >
|
| I mean: What does Monad as defined in the Axiom library right now:
|
| ++ Monad is the class of all multiplicative monads, i.e. sets
| ++ with a binary operation.
|
| have to do with Monads in Haskell?

That is explained in the reference to Philip Wadler's paper I pointed
to in my earlier message.

| Isn't that what you implied by your comment?

Yes.

-- Gaby

Bill Page

2007-11-01 04:16:43 UTC

Post by Gabriel Dos Reis
| ...
|
| ++ Monad is the class of all multiplicative monads, i.e. sets
| ++ with a binary operation.
|
| have to do with Monads in Haskell?
That is explained in the reference to Philip Wadler's paper I pointed
to in my earlier message.

Philip Wadler's paper is well known and was published in 1992. The
Axiom category

)abbrev category MONAD Monad
++ Authors: J. Grabmeier, R. Wisbauer
++ Date Created: 01 March 1991
++ Date Last Updated: 11 June 1991

and the associated domains:

AlgebraicGivenbyStructuralConstants
AssociatedJoranAlgebra
AssociatedLieAlgebra
FreeNilpotentLie
GenericNonAssociativeAlgebra
LieSquareMatrix

seem to me to refer to subjects very different than Philip Wadler's
paper. I do not see any higher-order functions like 'map', 'unit' or
'join' defined here at all. Certainly Axiom does have various forms of
list comprehensions and functions like 'map' defined for many domains
but I do not see that generalized in any way in the existing Monad
category and associated domains.

Please, what do you see that I am missing?

Post by Gabriel Dos Reis
| Isn't that what you implied by your comment?
Yes.

Sorry, I don't understand that at all. Maybe this discussion is best
saved for another time after I have had more time to think about how
to do these things in Axiom.

Regards,
Bill Page.

Gabriel Dos Reis

2007-11-01 12:50:35 UTC

On Thu, 1 Nov 2007, Bill Page wrote:

|
| On 10/31/07, Gabriel Dos Reis wrote:
| >
| > On Wed, 31 Oct 2007, Bill Page wrote:
| > | ...
| > | I mean: What does Monad as defined in the Axiom library right now:
| > |
| > | ++ Monad is the class of all multiplicative monads, i.e. sets
| > | ++ with a binary operation.
| > |
| > | have to do with Monads in Haskell?
| >
| > That is explained in the reference to Philip Wadler's paper I pointed
| > to in my earlier message.
| >
|
| Philip Wadler's paper is well known and was published in 1992.

Then, I'm surprised you do not see they are the same categorial notion.
It is not that I'm unwilling to explain what it is. I just don't have
the time right now. However, since I do have references to existing
explanations, I can point you there. Wadler's paper is one of the
simplest explanations. Or, you can go directly read Moggi's paper.
If you still disagree, then, let stop it at there.

-- Gaby

Francois Maltey

2007-11-01 08:31:46 UTC

I like this discuss about mutable variables.

You know I also teach caml. I notice that the 2 manners "mutable data"
and "not-mutable" data must be separate.
If not, everybody make a lot of errors.

Functional languages, mathematics and not-mutable datas are very close.

What do you think about this concrete matrix example ?

A := matrix [[1,2],[3,4]]
fct A == .... A.(1,1) := 10 .... and the result is a number or others.

Mathematics say that both 3*A matrices bellow are equal :
The variable A is the same and we don't see any assin command.

3*A
fct A
3*A --- ve verify the matrix.

We don't understand why A changes.
First we think about the result of fct, not about the manner we get it.

Is it possible to have an automatic copy of the variables in a function ?

On the other hand, if we want to code a matrix sequence we write :
M := matrix [[...]]
fct A == ...A.(1,1):=A.... A -- this A is the result, the new matrix.
M := fct M
M := fct M -- to iterate.

The time for copying data-structure isn't so long that we must think
everytime about it. Axiom is designed for mathematics.

Axiom Guru's find obvious to code
fct M == A:=copy M ... .... in the first case.
fct A == A.(1,1) := 12 .... A in the second case.
and it's a little faster.

But that forces to teach what are mutable/not-mutable data
in the first courses of axiom.
This isn't the aim of axiom which is a mathematical language.

fct A == ... .... axiom copy the matrix.
fct A == A.(1,1) := 12 .... A the outer M := explains the matrix change.

Maple use a silly evalm matrix command.
And I never get difficult with mupad which copy data structure by default.

And what do you think about lists ?
My first thought for mathematics thinks that lists aren't mutable.
But list becomes mutable with L.3 := 33. This assign command is too easy.

A setelt! (L, 3, 33) doesn't hide the same difficult.

Francois.

Ralf Hemmecke

2007-10-31 17:06:20 UTC

Hello Bill,

Bill,
you probably mean something like
map(product(wholePart, sin), [1.1,2.2,3.3])
right?

product: (A:Type, A->X,A->Y) -> (A->%)

Of course the A must come from somewhere, but who would like to write a
cross of two functions in that way?

I would better have something like

cross: (A: Type) -> (A->X,A->Y) -> (A->%)

later say

product == cross(Integer)

and then use "product" as I did above.

And since this A is actually part of the Limit definition there should
rather be something like (dream dream ...)

Limit(A: Type): ... {-- this introduces A
Product(X: Type, Y: Type): with {...} == add {...}
}

within "with {..}" and "add {...}" there would be no need to say
anything about "product", since it would come through the Limit
construction.

Oh, that is not well thought of... How would the compile know that the
function is called "product"? Hmmmmm.....

To define 'product' in general (i.e. as a categorical limit) for any
domain Product(A,B) and domain C we must have
product(C,f,g):C->Product(A,B)
defined for any functions
f:C->A
g:C->B
I don't think you can do that without passing the independent domain C.

No, of course not. But I would have hidden it in Product(C)(A,B). But
also that looks ugly.

But I guesss that is not your point. Your point is (please correct) that
you want a categorical definition of "Product".
Product(A, B) should automatically export
product: (A, B) -> %

No, this is not well defined.

as well as
product: (X -> A, X -> B) -> X -> %.

What is X above?

All-quantified. In fact, I was thinking that the compiler would silently
introduce this "Limit(X)" from above.

You don't want to write down that function definition yourself, right?

I think I can support this.

Ralf

Bill Page

2007-10-31 18:36:56 UTC

Post by Ralf Hemmecke
...
Of course the A must come from somewhere, but who would like to write a
cross of two functions in that way?
I would better have something like
cross: (A: Type) -> (A->X,A->Y) -> (A->%)
later say
product == cross(Integer)
and then use "product" as I did above.

Ok, that's fine.

Post by Ralf Hemmecke
And since this A is actually part of the Limit definition there should
rather be something like (dream dream ...)
Limit(A: Type): ... {-- this introduces A
Product(X: Type, Y: Type): with {...} == add {...}
}
within "with {..}" and "add {...}" there would be no need to say
anything about "product", since it would come through the Limit
construction.
Oh, that is not well thought of... How would the compile know that the
function is called "product"? Hmmmmm.....

The domain constructor 'Limit', as a generalization of 'Product' needs
to be defined over both a set of domains and some arrows (functions)
involving those domains

Limit(A,B,C, ... A->B, B->C, ... )

then 'limit', as a generalization of 'product' is the following
uniquely defined exported operation

limit(X:Type,f:X->A,g:X->B, h:X->C, ... ): X -> %

for any X, f, g, h, ... such that everything commutes. But I am not
sure how best to write the signature of 'Limit'. It requires both a
Tuple(Type) and a Tuple of maps involving (possibly just some of)
those Type. A reasonable general syntax probably requires an extension
of the compiler but special cases can be easily defined, e.g.

Equalizer(A:Type,B:Type,p:A->B,q:A->B)

equalizer(X:Type,f:X->A):Union(X->%,"failed")

where "failed" is returned in the case p f ~= q f

http://en.wikipedia.org/wiki/Equalizer_%28mathematics%29
http://en.wikipedia.org/wiki/Limit_(category_theory)

product: (X -> A, X -> B) -> X -> %.

What is X above?

All-quantified. In fact, I was thinking that the compiler would silently
introduce this "Limit(X)" from above.

It might be nice to define such generic operations where any domain X
(or other implicit types required for "unification") is deduced from
context. I guess this would be a natural generalization concept of a
"mode" in the Axiom interpreter where a type place marker can be
denoted by '?', but I am not sure if this belongs in the compiler or
not.

You don't want to write down that function definition yourself, right?

I think I can support this.

Great. :-)

Regards,
Bill Page.

Francois Maltey

2007-10-31 18:23:44 UTC

Hello,

map(product(Float,wholePart,sin),[1.1,2.2,3.3])
versus
[makeprod(wholePart x, sin x)$Product(Integer,Float) for x in [1.1,2.2,3.3]]

And what do you think about a map as :

map (t +-> [|wholePart t, sin t|], [1.1,2.2,3.3])

where [|....|] creates a makeprod with right types.

It's a good thing that record will remain mutable and the other
structure product won't be mutable. So there is no ambiguity.

Have a nice day !

F. the naive guy.

Bill Page

2007-10-31 18:42:46 UTC

Post by Francois Maltey
map (t +-> [|wholePart t, sin t|], [1.1,2.2,3.3])
where [|....|]creates a makeprod with right types.

It's ok, but way should we require the dummy variable 't' when we can
operate directly on functions with the higher-order function
'product'? I think

t +-> [|wholePart t, sin t|]

is just a slightly awkward way to write:

product(wholePart,sin)

Post by Francois Maltey
It's a good thing that record will remain mutable and the other
structure product won't be mutable. So there is no ambiguity.

Maybe there should be both 'Record' and 'Record!' where as usual the !
denotes mutability?

Regards,
Bill Page.

Francois Maltey

2007-10-31 19:38:43 UTC

Hello, again

Post by Bill Page
It's ok, but way should we require the dummy variable 't' when we can
operate directly on functions with the higher-order function
'product'? I think
t +-> [|wholePart t, sin t|]
product(wholePart,sin)

Is it the reason why you want a ?function? product (A->X, A->Y, ...) ?

Post by Francois Maltey
It's a good thing that record will remain mutable and the other
structure product won't be mutable. So there is no ambiguity.

Maybe there should be both 'Record' and 'Record!' where as usual the !
denotes mutability?

I'm mot sure : mathematics don't speak about record but product
or << couples or triplets or n-uplet in French >> or Tupple ?

And Record! is the most logic, but perhaps not usable because everybody
think << Record >>.

Bill Page

2007-10-31 20:29:05 UTC

Post by Francois Maltey
Hello, again

Is it the reason why you want a ?function? product (A->X, A->Y, ...) ?

No, not the real reason. My main reason for wanting the higher-order
function (i.e. functional? or maybe sometimes called functor?) is that
such functions arise naturally when you try to given the formal
(categorical) semantics of exactly what you mean by the domain called
Product (or Record).

Post by Francois Maltey

Post by Francois Maltey
It's a good thing that record will remain mutable and the other
structure product won't be mutable. So there is no ambiguity.

Maybe there should be both 'Record' and 'Record!' where as usual the !
denotes mutability?

I'm mot sure : mathematics don't speak about record but product
or << couples or triplets or n-uplet in French >> or Tupple ?

You are right. Now Axiom and Aldor has a confusing mixture of
terminology about Product, DirectProduct, Tuple, Cross, Record, ...
All of these are (almost) the same kind of thing.

Post by Francois Maltey
And Record! is the most logic, but perhaps not usable because everybody
think << Record >>.

I think it is good if 'Record' is not mutable by default and one is
required to use a slightly more exotic name if you want mutability.

Regards,
Bill Page.

Ralf Hemmecke

2007-11-02 13:55:27 UTC

Post by Bill Page
You are right. Now Axiom and Aldor has a confusing mixture of
terminology about Product, DirectProduct, Tuple, Cross, Record, ...
All of these are (almost) the same kind of thing.

Please don't put types that are build into the language and library
defined types together.

Tuple, Cross, Record are language defined, the others are not. The first
three have a clear semantics according to the Aldor User Guide.

I agree that there are too many product-like types, but I think that it
is mainly the library/libraries that is/are not built in a minimal fashion.

Ralf

Ralf Hemmecke

2007-11-02 13:43:48 UTC

Post by Francois Maltey
map (t +-> [|wholePart t, sin t|], [1.1,2.2,3.3])
where [|....|]creates a makeprod with right types.

It's ok, but way should we require the dummy variable 't' when we can
operate directly on functions with the higher-order function
'product'? I think
t +-> [|wholePart t, sin t|]
product(wholePart,sin)

Exactly.

Post by Bill Page
Maybe there should be both 'Record' and 'Record!' where as usual the !
denotes mutability?

Oh, as far as I know "!" stands for "be aware that something strange can
happen" or "if I use this function, I know what I do". Usually, of
course, it is connected to destructive operations and thus to
mutability, but I wouldn't say that could be the only purpose.

And additionally, the ! is a *convention*, that should not be build-in
into the language. I rather live with Cross and Record than with Record
and Recort!.

Ralf

Gabriel Dos Reis

2007-11-02 13:48:40 UTC

On Fri, 2 Nov 2007, Ralf Hemmecke wrote:

| And additionally, the ! is a *convention*, that should not be build-in
| into the language.

I agree it should not be built into the language; but the current systems
seem have support for it -- in determining side effect free functions.

-- Gaby

Bill Page

2007-10-31 16:30:26 UTC

---------- Forwarded message ----------
From: Ralf Hemmecke <***@hemmecke.de>
Date: Oct 30, 2007 4:58 PM
Subject: Re: [open-axiom-devel] [fricas-devel] Re: [fricas-devel]
Re: iterators and cartesian product.
To: Bill Page <***@newsynthesis.org>

Hi Bill,

this goes offlist since I don't want to spam them...

As I said earlier, I think the semantics of Product should be given
categorically by the existence of the unique operation
Product(X:Type, Y:Type): with ...
product: (A:Type, A->X,A->Y) -> (A->%)
as a categorical limit.

As you know I like the categorical approach, but I don't understand,
what a definition like your "product" has anything to do with how the
"for" loop is traversed?

You certainly know that a function

product: (A:Type, A->X,A->Y) -> (A->%)

is easily implemented (in Aldor, I don't know for spad).
But I really don't see the connection to the "for".

Ralf

Bill Page

2007-10-31 16:31:13 UTC

---------- Forwarded message ----------
From: Bill Page <***@newsynthesis.org>
Date: Oct 31, 2007 10:54 AM
Subject: Re: [open-axiom-devel] [fricas-devel] Re: [fricas-devel] Re:
iterators and cartesian product.

Post by Ralf Hemmecke
Hi Bill,
this goes offlist since I don't want to spam them...

Ok if you like, but I think other people on this list probably have
similar questions as you do so it would probably be of interest to
them too even though this thread is already quite long.

As I said earlier, I think the semantics of Product should be given
categorically by the existence of the unique operation
Product(X:Type, Y:Type): with ...
product: (A:Type, A->X,A->Y) -> (A->%)
as a categorical limit.

As you know I like the categorical approach, but I don't understand,
what a definition like your "product" has anything to do with how the
"for" loop is traversed?
You certainly know that a function
product: (A:Type, A->X,A->Y) -> (A->%)
is easily implemented (in Aldor, I don't know for spad).
But I really don't see the connection to the "for".

The main issue has to do with programming style. The for-loop is a
construction from imperative-style programming. Operations like
'product' above operate directly on functions and return functions.
This is most common in a functional-programming style and might be
used for example in conjuction with another operation such as 'map' to
produce the same results a a for-loop constrcut:

map(product(Float,wholePart,sin),[1.1,2.2,3.3])

versus

[makeprod(wholePart x, sin x)$Product(Integer,Float) for x in [1.1,2.2,3.3]]

The functional-style has no dummy variables and no explicit for-loop.
In general one might view imperative-style programming as inherently
more "primitive" than functional programming so I think it should be
"allowed" because it is sometimes convenient but not encouraged. Aldor
and Spad usually provide both options. But the point with respect to
category theory is really that because the operation 'product' exists
and is uniquely defined (as a limit), it actual defines exactly what
is meant by the domain constructor Product, i.e. it provides the
semantics of Product. This has nothing directly to do with for-loops.

Regards,
Bill Page.

Gabriel Dos Reis

2007-10-22 17:11:12 UTC

On Mon, 22 Oct 2007, Bill Page wrote:

| What I call 'Product' you can call 'Cross', I have no problem with the
| name. If you want 'Cross' to have a signature like:

I believe Cross has a good pedigree in the Axiom family.

| Cross(x:List Type): with ... appropriate access operations
|
| that is fine. But still you would not be able to write:
|
| Cross [1..9,1..4]

Yes, but why would I have to write that what would be the meaning?

Again, I'm not saying it is bad. I'm after the semantics.

I can (mathematically) explain that

cross [l1, l2]

computes the a sequence listing of the elements of the cross product
of the sequence l1 and l2.

I can (mathematically) explain that

cross [Integer, Float]

returns the cross product of Integer by Float.

How do you matematically explain that, 1..9 is a domain, and still I
can write

for i in 1..9 repeat
-- ...

and I do not get a type error?

Again, I'm after the semantics.

-- Gaby

Gabriel Dos Reis

2007-10-22 17:15:08 UTC

On Mon, 22 Oct 2007, Bill Page wrote:

| Yes, that is the point. Apparently Stephen Watt's answer in Aldor is
| that allow the domain of 'Domain' to be 'Domain' is ok provided we are
| careful exactly what operations we expect to provide in 'Domain'.

Domain:Domain introduces an inconsistency at its Curry-Howard logic
level, so I'm nervous about that. A solution, adopted by Coq, is that
even though the interface would display Type:Type, what it really does
it that it has an infinite hierarchy of universes Type(k), where
Type(i) : Type(j), for i < j, starting from 0.

-- Gaby

Gabriel Dos Reis

2007-10-22 17:23:14 UTC

On Mon, 22 Oct 2007, Bill Page wrote:

| > | > | We want to be able to write:
| > | > |
| > | > | DirectProduct(4,1..9)
| > | > |
| > | > | but this does not work because '1..9' is not a type - it is an object
| > | > | of 'Segment PositiveInteger'.
| > | >
| > | > If it worked, what would you have liked the mathematical meaning to
| > | > be, and why?
| > | >
| > |
| > | I would like the result to be a finite domain.
| >
| > that says what property the result would have, but it does not tell me
| > what the meaning of the result is. I would like to underdstand
| > the mathematical meaning.
| >
|
| I think the concept of an interval (segment) on the domain Integer is
| a fairly well-defined concept, no?

The notion of interval domain is well-understood. But, the algebra you
presented in not one of the well-understood algebra I can link to.
So, I would appreciate your effort in elaborating on what you have ini mind.

The Segment (and UniversalSegment) domain is already in the Axiom
faimily, but you seem to be wanting something else. So, yes, the
`concept of segment' may be a fairly well-defined concept;
apparently you're considering a different definition. I would like to
understand it.

-- Gaby

Gabriel Dos Reis

2007-10-22 17:32:51 UTC

On Mon, 22 Oct 2007, Bill Page wrote:

| > [...]
| > |
| > | Well for example, maybe I would want to write:
| > |
| > | x:IntegerSegment 1..9
| > | y:=x + 1
| > |
| > | where the type of 'y' might be Union(IntegerSegment 1..9,"failed").
| >
| > So, you are actually after a domain that constrains all operations on
| > the values of its objects to deliver a value in a specified bound. I
| > can be persuaded that IntegerSegment convays such meaning, but I'm not
| > sure the notation `1..9' is intuitive to me, given its other existing
| > meaning.
|
| Do you have another suggestion?

Until I fully understand what you want and its meaning, and why, my
suggestion would be to keep things simple and explore what (e.g. the
abstractions) you want to express and why you can't express it with
the current lanaguage.

| > ...
| > I'm specifically after `1..9' that you would want to be a domain
| > and the various constructs you based on it.
| >
|
| Ok. Well as I said, I am willing to live with '1..9' being a member of
| the domain 'Segment PositiveInteger' provided that there is also a
| coercion of such objects to an equivalent Finite domain so then at

Would you be happy if we added something like

if S has impliesFiniteSegment then Finite

where impliesFiniteSegment is some predefined attribute? Or do you
really insist on a coerce? If so, how different would the target
domain be?

-- Gaby

Ralf Hemmecke

2007-10-23 00:47:27 UTC

Post by Gabriel Dos Reis
|
| > ...
| > |
| > | I would like to consider what is?
| > |
| > | 1..9
| > |
| > | Right now in Axiom this is evaluated as a member of 'Segment
| > | PositiveInteger', i.e. the domain of all such segments. But in general
| > | I think I would prefer if '1..9' actually denoted a domain - a subset
| > | of the Positive Integers - with members 1, 2, 3 ... etc.

Bill, you don't want 1..9 to be a domain. Of course, you can have it if
you really want, but that just sounds like a domain of the set (or list)
of the first 9 numbers. What would be the exports of this domain?

Maybe this one....

Post by Gabriel Dos Reis
aldor -laldor -fx mycross.as
mycross

1, 11
1, 12
2, 11
2, 12
3, 11
3, 12

One can certainly do with the LibAldor IntegerSegment instead of
Segment(X), but I've just included it for illustration that ".." as well
as "by" are just functions.

Ralf

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

macro OrdMonoid == with {
1: %;
<=: (%, %) -> Boolean;
+: (%, %) -> %;
}
Segment(T: OrdMonoid): with {
..: (T, T) -> %;
by: (%, T) -> %;
generator: % -> Generator T;
} == add {
Rep == Record(lo: T, hi: T, st: T);
import from Rep;
(s: T) .. (t: T): % == per [s, t, 1];
(x: %) by (t: T): % == per [rep(x).lo, rep(x).hi, t];
generator(x: %): Generator T == generate {
(l, h, s) := explode rep x;
while l <= h repeat {
yield l;
l := l+s;
}
}
}

Product(A: OrdMonoid, B: OrdMonoid): with {
*: (Segment A, Segment B) -> Generator Cross(A,B);
} == add {
(x: Segment A) * (y: Segment B): Generator Cross(A,B) == generate {
for a in x repeat for b in y repeat yield (a,b);
}
}

Z ==> Integer;
main(): () == {
import from Z, Product(Z, Z);
s1: Segment Z := 1..3;
s2: Segment Z := 11..12;
for ab in s1 * s2 repeat {
(a, b) := ab;
stdout << a << ", " << b << newline;
}
}

main();
---END mycross.as

Gabriel Dos Reis

2007-10-23 10:24:53 UTC

On Tue, 23 Oct 2007, Ralf Hemmecke wrote:

| > What would be its meaning?
|
| Maybe this one....

[aldor code]

Am I the only one here who believes that 'meaning' has to be given
mathematically, indenpendent of syntax, and typing rules must also be
given too?

-- Gaby

Ralf Hemmecke

2007-10-23 10:35:32 UTC

Post by Gabriel Dos Reis
| > What would be its meaning?
|
| Maybe this one....
[aldor code]
Am I the only one here who believes that 'meaning' has to be given
mathematically, indenpendent of syntax, and typing rules must also be
given too?

Well, I only wanted to demonstrate that Bill might have had the wrong
idea when he wanted 1..9 to be a domain instead of an element.
It seems that was not clear. Sorry.

Ralf

Gabriel Dos Reis

2007-10-23 10:43:26 UTC

On Tue, 23 Oct 2007, Ralf Hemmecke wrote:

| On 10/23/2007 12:24 PM, Gabriel Dos Reis wrote:
| > On Tue, 23 Oct 2007, Ralf Hemmecke wrote:
| >
| > | > What would be its meaning?
| > |
| > | Maybe this one....
| >
| > [aldor code]
| >
| > Am I the only one here who believes that 'meaning' has to be given
| > mathematically, indenpendent of syntax, and typing rules must also be
| > given too?
|
| Well, I only wanted to demonstrate that Bill might have had the wrong idea
| when he wanted 1..9 to be a domain instead of an element.
| It seems that was not clear. Sorry.

No need to apologize. I just feel like I have been asking for
`meaning', and I almost always get back more codes without semantics I
was looking for. If every body agrees that that is a construct we
don't have a clear semantics for, then I'll just shut up.

-- Gaby

Bill Page

2007-10-24 00:00:12 UTC

Yes, under this proposal '1..9' would be a domain consisting of the
set of the first 9 positive integers. I want to consider the view that
this is the same as thinking of 'PositiveInteger' as a sub-domain of
'Integer'. So like 'PositiveInteger', '1..9' would inherit some of the
structure of Integer, specifically 'OrderedSet', plus exports from
'Finite' and the operations 'high', 'low' and 'incr' of
'SegmentCategory'. However 'SEGMENT', 'BY' and 'convert' of the
existing 'SegmentCategory' would have to become domain constructors.

In general I am wondering about "set-like" objects and whether these
should always be modeled as domains.

If '1..9' and '1..4' are domains then the meaning of 'Product' is
already given by the existing domain constructor 'Product' in the
Axiom library

Regards,
Bill Page.

Ralf Hemmecke

2007-10-24 00:10:38 UTC

Post by Gabriel Dos Reis
| Product(1..9,1..4)
What would be its meaning?

If '1..9' and '1..4' are domains then the meaning of 'Product' is
already given by the existing domain constructor 'Product' in the
Axiom library

Seems OK, but, of course the _domain_ 1..9 is then inappropriate in a
construction like

for i in 1..9 repeat ...

don't you agree?

Ralf

Bill Page

2007-10-24 00:20:43 UTC

Post by Gabriel Dos Reis
| Product(1..9,1..4)
What would be its meaning?

If '1..9' and '1..4' are domains then the meaning of 'Product' is
already given by the existing domain constructor 'Product' in the
Axiom library

Seems OK, but, of course the _domain_ 1..9 is then inappropriate in a
construction like
for i in 1..9 repeat ...
don't you agree?

No. My proposal also includes the idea that the construct

for i in X repeat

should expect X to be any domain that supplies a generator (like Aldor).

Regards,
Bill Page.

Ralf Hemmecke

2007-10-24 00:44:42 UTC

Post by Ralf Hemmecke
Seems OK, but, of course the _domain_ 1..9 is then inappropriate in a
construction like
for i in 1..9 repeat ...
don't you agree?

No. My proposal also includes the idea that the construct
for i in X repeat
should expect X to be any domain that supplies a generator (like Aldor).

In Aldor, at the place of X there must be an element of type
"Generator(Something)", not a domain. Well, if you have somewhere a
function

generator: T -> Generator(Something)

(where T is the type of X) around, then Aldor should be able to silently
insert that function for you.

I must say, I am totally happy with just *one* "for" construction. I am
currently not seeing much use in the domain 1..9, i.e. the finite set
{1, ..., 9}.

Ralf

Bill Page

2007-10-24 01:07:01 UTC

Post by Ralf Hemmecke
Seems OK, but, of course the _domain_ 1..9 is then inappropriate in a
construction like
for i in 1..9 repeat ...
don't you agree?

No. My proposal also includes the idea that the construct
for i in X repeat
should expect X to be any domain that supplies a generator (like Aldor).

In Aldor, at the place of X there must be an element of type
"Generator(Something)", not a domain.

Can you give an example of an "element of type Generator(Something)"
that is not a domain?

Post by Ralf Hemmecke
Well, if you have somewhere a function
generator: T -> Generator(Something)
(where T is the type of X) around, then Aldor should be able to silently
insert that function for you.

I said only "like Aldor". In my proposal for an extension of Spad and
the Axiom interpreter, I expect that X must supply this generator
(iterator), i.e. satisfy some specific language-defined category that
includes this export.

Post by Ralf Hemmecke
I must say, I am totally happy with just *one* "for" construction.

That is exactly what I am suggesting. There should be no special cases
of the "for" construct - only one, where X is as I describe.

Post by Ralf Hemmecke
I am currently not seeing much use in the domain 1..9, i.e. the finite set
{1, ..., 9}.

The point of this whole thread is discussion of suggested constructions like

[ f(i,j) for i in 1..9 repeat for j in 1..4 ]

i.e. some kind of "cross-product" extension of the for-loop iteration
such as the CROSS construction that Gaby described in Boot. Rather
than extending the language with this sort of imperative syntax, I
would like to write this in a more "functional" manner instead:

[ f(x.1,x.2) for x in Product(1..9,1..4) ]

(Right now Product provides only 'selectfirst' and 'selectsecond'
instead of .1 and .2 but that is easily fixed.)

Or better

map(f,expand()$Product(1..9,1..4))

which requires some slightly more general implementation of function
application over such domains.

Regards,
Bill Page.

Ralf Hemmecke

2007-10-24 01:24:17 UTC

Post by Ralf Hemmecke
Seems OK, but, of course the _domain_ 1..9 is then inappropriate in a
construction like
for i in 1..9 repeat ...
don't you agree?

No. My proposal also includes the idea that the construct
for i in X repeat
should expect X to be any domain that supplies a generator (like Aldor).

In Aldor, at the place of X there must be an element of type
"Generator(Something)", not a domain.

Can you give an example of an "element of type Generator(Something)"
that is not a domain?

g: Generator(Integer) := generate {yield 0}

Take g.

Post by Ralf Hemmecke
I must say, I am totally happy with just *one* "for" construction.

That is exactly what I am suggesting. There should be no special cases
of the "for" construct - only one, where X is as I describe.

Post by Ralf Hemmecke
I am currently not seeing much use in the domain 1..9, i.e. the finite set
{1, ..., 9}.

The point of this whole thread is discussion of suggested constructions like
[ f(i,j) for i in 1..9 repeat for j in 1..4 ]
i.e. some kind of "cross-product" extension of the for-loop iteration
such as the CROSS construction that Gaby described in Boot. Rather
than extending the language with this sort of imperative syntax, I
[ f(x.1,x.2) for x in Product(1..9,1..4) ]
(Right now Product provides only 'selectfirst' and 'selectsecond'
instead of .1 and .2 but that is easily fixed.)
Or better
map(f,expand()$Product(1..9,1..4))
which requires some slightly more general implementation of function
application over such domains.
Regards,
Bill Page.

Hmmm, didn't you like

http://lists.gnu.org/archive/html/axiom-math/2007-10/msg00023.html

main(): () == {
import from Z, Product(Z, Z);
s1: Segment Z := 1..3;
s2: Segment Z := 11..12;
for ab in s1 * s2 repeat {
(a, b) := ab;
stdout << a << ", " << b << newline;
}
}

???

What you want is available now and no need of 1..9 being a domain.

Ralf

Bill Page

2007-10-24 01:56:44 UTC

Post by Ralf Hemmecke
Seems OK, but, of course the _domain_ 1..9 is then inappropriate in a
construction like
for i in 1..9 repeat ...
don't you agree?

No. My proposal also includes the idea that the construct
for i in X repeat
should expect X to be any domain that supplies a generator (like Aldor).

In Aldor, at the place of X there must be an element of type
"Generator(Something)", not a domain.

Can you give an example of an "element of type Generator(Something)"
that is not a domain?

g: Generator(Integer) := generate {yield 0}
Take g.

Ok, yes I see what you mean. But this requires some new basic
functionality in the language, right? Contrast this with 'Stream' in
Axiom which (so far as I understand) does not require such an
extension of Spad.

Post by Ralf Hemmecke
...
Hmmm, didn't you like
http://lists.gnu.org/archive/html/axiom-math/2007-10/msg00023.html
main(): () == {
import from Z, Product(Z, Z);
s1: Segment Z := 1..3;
s2: Segment Z := 11..12;
for ab in s1 * s2 repeat {
(a, b) := ab;
stdout << a << ", " << b << newline;
}
}

Yes, that is "ok" but ... we already have a domain construction
Product in the Axiom library that takes two *domains* as it's
parameters.

Post by Ralf Hemmecke
???
What you want is available now and no need of 1..9 being a domain.

I did not intend to introduce any new constructor for Product.

Regards,
Bill Page.

Martin Rubey

2007-10-24 08:03:15 UTC

Post by Bill Page
Can you give an example of an "element of type Generator(Something)"
that is not a domain?

g: Generator(Integer) := generate {yield 0}
Take g.

Ok, yes I see what you mean.

Just curious: can something of type Generator(Something) ever be a domain?
(Probably yes...)

Post by Bill Page
But this requires some new basic functionality in the language, right?

YES. But, it is one of the goals to improve SPAD anyway. OK, I can only hope
that our compiler gurus have already enough expertise. The only thing I can do
is to advertise the language design of Aldor...

I was looking into how generators are implemented in lisp. One of the most
promising links I found is

http://groups.google.com/group/comp.lang.lisp/browse_thread/thread/fbda37620268811/c558bf7e6feb5d55?hl=en&lnk=st&q=generator+monadic+continuations+defun#

The code in the final message looks really short, but I did not yet understand
it.

Martin

Gabriel Dos Reis

2007-10-24 12:16:12 UTC

On Wed, 24 Oct 2007, Martin Rubey wrote:

| The only thing I can do is to advertise the language design of Aldor...

I suspect that the compiler gurus already know Aldor's design choices.
It may be that they don't want to replicate, or they would like to
make slighly different choices...

-- Gaby

Gabriel Dos Reis

2007-10-24 12:37:52 UTC

On Wed, 24 Oct 2007, Martin Rubey wrote:

| Gabriel Dos Reis <***@cs.tamu.edu> writes:
|
| > On Wed, 24 Oct 2007, Martin Rubey wrote:
| >
| > | The only thing I can do is to advertise the language design of Aldor...
| >
| > I suspect that the compiler gurus already know Aldor's design choices.
| > It may be that they don't want to replicate, or they would like to
| > make slighly different choices...
|
| Yes. But I have the impression that so far the compiler gurus did not write
| much mathematical code in Aldor or SPAD.

Thanks for the credit.

-- Gaby

Martin Rubey

2007-10-24 13:41:46 UTC

Post by Gabriel Dos Reis
| Yes. But I have the impression that so far the compiler gurus did not
| write much mathematical code in Aldor or SPAD.
Thanks for the credit.

Since this seems to imply that I'm mistaken, I apologize. So far, I thought
you contributed a lot to the build system, to analyzing the compiler and the
language. These are all things I could not possibly do, I do not have the
expertise. I didn't see much algebra code by Waldek, either. (I am not
speaking of fixing bugs, he fixed many many many. I was only speaking of the
design of new packages / domains / etc.) Still, you probably know that I value
Waldek as one of the most important axiom contributors. And I'm pretty sure
that, once time is ripe, Waldek or his students will provide important
contributions, it suffices to look at his "literature" webpage. Same goes for
you.

I did certainly not want to insult anybody. If I did, I apologize. I tried to
reply to

Post by Gabriel Dos Reis
| The only thing I can do is to advertise the language design of Aldor...
I suspect that the compiler gurus already know Aldor's design choices. It
may be that they don't want to replicate, or they would like to make slighly
different choices...

as well as I could, and obviously, I failed miserably.

Just curious, could you please refresh my memory?

Martin

Martin Rubey

2007-10-24 12:37:42 UTC

Post by Gabriel Dos Reis
| The only thing I can do is to advertise the language design of Aldor...
I suspect that the compiler gurus already know Aldor's design choices.
It may be that they don't want to replicate, or they would like to
make slighly different choices...

Yes. But I have the impression that so far the compiler gurus did not write
much mathematical code in Aldor or SPAD. Of course, this does *not* mean that
I believe they wouldn't like to, or they would not know how to or some such.

All I'm saying is: I believe that I have a little experience to judge the
abilities and shortcomings of Aldor and SPAD when used as a tool for
implementing certain mathematics.(*)

I found, that I can live with the shortcomings of Aldor I encountered so far
(**), but I cannot really live with the shortcomings of SPAD. Mostly, I miss
types being truly first class objects.

So far, I dislike most extensions to the language presented so far in the
mailing list, since what they provide, Aldor provides easily, or no real use
cases were given. And, I should hurry to add, I personally also made proposals
that I find very stupid meanwhile. Christian Aistleitner's insights helped a
lot here.

If you would like to make different choices, I'd very much like to know why.
If you have an idea why the Aldor (language, not compiler!) designers didn't
take that choice, even better.

Martin

* I wrote the guessing package, which seems to work pretty well and outperforms
all other similar packages so far.

Together with Ralf, I wrote a pretty large library covering a lot of ground
in combinatorial generation.

During the workshop this year, we designed the basic structure for a package
dealing with lambda rings, symmetric functions, and Hopf algebras.

** These would be, for example:

+ the impossibility to have an AbelianMonoid be a Monoid
+ certain shortcomings of Tuples, as pointed out by Ralf
+ certain problems with dynamically creating new domains - although the
current compiler allows it, only the language doesn't :-)

Bill Page

2007-10-24 14:49:41 UTC

Martin,

Post by Martin Rubey
...
During the workshop this year, we designed the basic structure for a package
dealing with lambda rings, symmetric functions, and Hopf algebras.
...

I would be very interested in hearing more about this when you have time.

Regards,
Bill Page.

Ralf Hemmecke

2007-10-24 21:55:28 UTC

Post by Martin Rubey
Just curious: can something of type Generator(Something) ever be a domain?
(Probably yes...)
aldor -fx -laldor aaa.as
aaa

MachineInteger
123

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

CAT ==> OutputType with {integer: Literal -> %}
g(): Generator(CAT) == generate {
yield MachineInteger;
-- yield Integer;
}

foo(D: CAT): () == {
import from D, TextWriter, String, Character;
stdout << name(D)$Trace << newline;
stdout << (***@D) << newline;
}

for D in g() repeat foo(D);
---END aaa.as

But don't remove the -- before "yield Integer", because then the
compiler tells you... :-(

"aaa.as", line 5: g(): Generator(CAT) == generate {
................................^
[L5 C33] #1 (Fatal Error) Compiler bug: no exit list for terrorSequence
(ooops).

Since in Aldor domains are first class, it should be possible to return
them by a generator. (Compare to lists of domains.)

However, your question asks whether g is a domain if

g: Generator(Something)

and I would tend to say that this is not a domain. Why? Well,
"Generator(Something)" should be a category then, right? But if you look
int sal_gener.as you clearly see that Generator(T) is a domain.

Ralf

Gabriel Dos Reis

2007-10-24 11:59:52 UTC

On Tue, 23 Oct 2007, Bill Page wrote:

|
| On 10/23/07, Ralf Hemmecke wrote:
| >
| > On 10/24/2007 03:07 AM, Bill Page wrote:
| > > On 10/23/07, Ralf Hemmecke wrote:
| > >>>> Seems OK, but, of course the _domain_ 1..9 is then inappropriate in a
| > >>>> construction like
| > >>>>
| > >>>> for i in 1..9 repeat ...
| > >>>>
| > >>>> don't you agree?
| > >>>>
| > >>> No. My proposal also includes the idea that the construct
| > >>>
| > >>> for i in X repeat
| > >>>
| > >>> should expect X to be any domain that supplies a generator (like Aldor).
| > >> In Aldor, at the place of X there must be an element of type
| > >> "Generator(Something)", not a domain.
| > >
| > > Can you give an example of an "element of type Generator(Something)"
| > > that is not a domain?
| >
| > g: Generator(Integer) := generate {yield 0}
| >
| > Take g.
| >
|
| Ok, yes I see what you mean. But this requires some new basic
| functionality in the language, right?

I find semi co-coroutines a possibility for Spad.

| Contrast this with 'Stream' in
| Axiom which (so far as I understand) does not require such an
| extension of Spad.

Stream is an *example* of a generator like domain. I would not want
to turn my BinaryTree into a Stream before iterating over it.

-- Gaby

Bill Page

2007-10-24 14:07:20 UTC

Post by Gabriel Dos Reis
...
Stream is an *example* of a generator like domain. I would not want
to turn my BinaryTree into a Stream before iterating over it.

It seems very natural to me to write:

t:BinaryTree Integer
t:= ...
for i in t repeat ...

but perhaps the meaning is not so clear. Over exact what objects are
we iterating? There are several operations in BinaryTree(S) that
produce 'List S' or 'List %' output, for example:

leaves : % -> List S
nodes : % -> List %
children : % -> List %
members : % -> List S
parts : % -> List S

In any case right now in Axiom you are forced to turn your binary tree
into a List which is surely worse then returning a Stream, no?

Unfortunately there is a bug in 'members':

(1) -> t:BinaryTree(Integer)
Type: Void
(2) -> t:=binaryTree(10)

(2) 10
Type: BinaryTree Integer
(3) -> t:=binaryTree(t,3,binaryTree 20)

(3) [10,3,20]
Type: BinaryTree Integer
(4) -> members t
Function: parts : % -> List Integer is missing from domain: BinaryTree Integer
Internal Error
The function parts with signature (List (Integer))$ is missing from
domain BinaryTree(Integer)

--------

Regards,
Bill Page.

Gabriel Dos Reis

2007-10-24 14:16:33 UTC

On Wed, 24 Oct 2007, Bill Page wrote:

|
| On 10/24/07, Gabriel Dos Reis wrote:
| > ...
| > Stream is an *example* of a generator like domain. I would not want
| > to turn my BinaryTree into a Stream before iterating over it.
| >
|
| It seems very natural to me to write:
|
| t:BinaryTree Integer
| t:= ...
| for i in t repeat ...
|
| but perhaps the meaning is not so clear.

I don't see the `natural'-ness since a BinaryTree Integer has many
traversal views, with 3 of them being very popular. Which one is more
natural than the others and why?

-- Gaby

Gabriel Dos Reis

2007-10-24 14:19:12 UTC

On Wed, 24 Oct 2007, Bill Page wrote:

| In any case right now in Axiom you are forced to turn your binary tree
| into a List which is surely worse then returning a Stream, no?

Yes, but I never argued that was right or ideal.

| Unfortunately there is a bug in 'members':

this we want to fix, independently of whether the interface is ideal
or not. are you willing to open an issue for this? Thanks!

-- Gaby

Ralf Hemmecke

2007-10-24 21:11:45 UTC

Hi Bill,

Post by Ralf Hemmecke
Seems OK, but, of course the _domain_ 1..9 is then inappropriate in a
construction like
for i in 1..9 repeat ...
don't you agree?

No. My proposal also includes the idea that the construct
for i in X repeat
should expect X to be any domain that supplies a generator (like Aldor).

In Aldor, at the place of X there must be an element of type
"Generator(Something)", not a domain.

Can you give an example of an "element of type Generator(Something)"
that is not a domain?

g: Generator(Integer) := generate {yield 0}
Take g.

Ok, yes I see what you mean. But this requires some new basic
functionality in the language, right?

I cannot live anymore without "Generator". And I very much hope it will
make it into SPAD.

Post by Bill Page
Contrast this with 'Stream' in
Axiom which (so far as I understand) does not require such an
extension of Spad.

For me a stream is like a generator with memory. If I step a generator
then I can never repeat that step. Take (Aldor)

g: Generator Integer := generate yield 1;

l1: List Integer := [x for x in g];
l2: List Integer := [x for x in g]

that yields l1=[1] and l2=[].

If you replace g by

s: Stream(Integer) := ...

you would probably expect that also l2=[1]

Oh, I am totally wrong. Streams are always infinite, Generators are not.
So I would have to write

[x for x in s for i in 1..1]

Post by Ralf Hemmecke
Hmmm, didn't you like
http://lists.gnu.org/archive/html/axiom-math/2007-10/msg00023.html
main(): () == {
import from Z, Product(Z, Z);
s1: Segment Z := 1..3;
s2: Segment Z := 11..12;
for ab in s1 * s2 repeat {
(a, b) := ab;
stdout << a << ", " << b << newline;
}
}

Yes, that is "ok" but ... we already have a domain construction
Product in the Axiom library that takes two *domains* as it's
parameters.

OK if you like that so much then OK. As Martin said, that is very much
what we do in Aldor-combinat. There is a Product functor that takes two
species and produces the product species. Each species comes with a function

structures: SetSpecies L -> Generator %;

So for us it would mean

for s in structures([1,2,3,4])$Times(F, G)(Integer) repeat ...

where F and G would be the species corresponding to 1..9 and 1..4.
I don't see that this makes life easier.

I am sure one could simplify some libraries so that you end up with

for s in generator()$Product(1..9, 1..9) repeat

where 1..9 should be interpreted as a domain that also provides a function

generator: () -> Generator %

Fine. But look closer and you see that I build again on the concept of
Generator.

If I understand you correctly, you basically want to have the same
functions but like the compiler to allow you to write

for s in Product(1..9, 1..9) ...

as syntactic sugar for my line above.

I hopefully don't introduce too much confusion here. I don't know enough
of the limitations of SPAD.

Ralf

Bill Page

2007-10-25 16:40:32 UTC

Post by Ralf Hemmecke
...
I cannot live anymore without "Generator". And I very much hope it will
make it into SPAD.

Post by Bill Page
Contrast this with 'Stream' in
Axiom which (so far as I understand) does not require such an
extension of Spad.

For me a stream is like a generator with memory.

It is not my intention to sound critical but I would like to
understand better this distinction. If Stream is a generalization of
Generator, why do we need Generator?

Post by Ralf Hemmecke
If I step a generator then I can never repeat that step. Take (Aldor)
g: Generator Integer := generate yield 1;
l1: List Integer := [x for x in g];
l2: List Integer := [x for x in g]
that yields l1=[1] and l2=[].
If you replace g by
s: Stream(Integer) := ...
you would probably expect that also l2=[1]
Oh, I am totally wrong. Streams are always infinite, Generators are not.

No, there are finite Streams. For example:

(1) -> s:=construct([1,2,3])$Stream(Integer)

(1) [1,2,3]
Type: Stream Integer
(2) -> possiblyInfinite? s

(2) false
Type: Boolean
(3) -> explicitlyFinite? s

(3) true
Type: Boolean
(4) -> t:=expand(1..)

(4) [1,2,3,4,5,6,7,8,9,10,...]
Type: Stream Integer
(5) -> possiblyInfinite? t

(5) true
Type: Boolean
(6) -> explicitlyFinite? t

(6) false
Type: Boolean
(7) -> u:=repeating [1,2,3]

_____
(7) [1,2,3]
Type: Stream PositiveInteger
(8) -> possiblyInfinite? u

(8) true
Type: Boolean
(9) -> explicitlyFinite? u

(9) false
Type: Boolean

Post by Bill Page
Yes, that is "ok" but ... we already have a domain construction
Product in the Axiom library that takes two *domains* as it's
parameters.

OK if you like that so much then OK.

Hmmm.... I didn't say that I like it. ;-) I said that is the way it
works now and in Spad there is no way to overload domain names.

Post by Ralf Hemmecke
As Martin said, that is very much what we do in Aldor-combinat.
There is a Product functor that takes two species and produces
the product species. Each species comes with a function
structures: SetSpecies L -> Generator %;
So for us it would mean
for s in structures([1,2,3,4])$Times(F, G)(Integer) repeat ...
where F and G would be the species corresponding to 1..9 and
1..4. I don't see that this makes life easier.

Well, that *is* exactly the model that I am considering. I like the
way Aldor-combinat works and I think it would be great if this could
be fully supported in Axiom.

The larger question remains however: When to use a domain to directly
model something that is "set-like" and when to define a higher-order
domain whose objects are "set-like"? To me this is not clear in either
Spad or Aldor.

Post by Ralf Hemmecke
I am sure one could simplify some libraries so that you end up with
for s in generator()$Product(1..9, 1..9) repeat
where 1..9 should be interpreted as a domain that also provides a function
generator: () -> Generator %
Fine. But look closer and you see that I build again on the concept of
Generator.

Yes, certainly. 'generator' is also an operation available in Axiom
for constructing objects of type 'Stream'.

Post by Ralf Hemmecke
If I understand you correctly, you basically want to have the same
functions but like the compiler to allow you to write
for s in Product(1..9, 1..9) ...
as syntactic sugar for my line above.

Yes, I think that is accurate and essentially the way Aldor works now,
right? One might also choose a slightly more primitive solution with a
lower-level interface such as the one Gaby recently described for C++.
In any case, I think one does want to make this the responsibility of
the programmer of the domain. One could probably define a particular
built-in category known to the compiler and the interpreter with a
default implementation for 'generator'. A good candidate for such a
category would be StepThrough (although I consider that a rather dumb
name... ).

Post by Ralf Hemmecke
I hopefully don't introduce too much confusion here. I don't know enough
of the limitations of SPAD.

Well of course this thread is primarily about Spad and the possible
(re-)design of the existing Axiom library. Since Aldor is not (at
least not yet) an integral part of any version/fork of Axiom, Aldor is
useful as an inspiration but not for actual implementation.

Regards,
Bill Page.

Ralf Hemmecke

2007-10-27 18:22:18 UTC

Post by Ralf Hemmecke
...
I cannot live anymore without "Generator". And I very much hope it will
make it into SPAD.

Post by Bill Page
Contrast this with 'Stream' in
Axiom which (so far as I understand) does not require such an
extension of Spad.

For me a stream is like a generator with memory.

It is not my intention to sound critical but I would like to
understand better this distinction. If Stream is a generalization of
Generator, why do we need Generator?

Let me cite the documentation from stream.spad.pamphlet

++ A stream is an implementation of an infinite sequence using
++ a list of terms that have been computed and a function closure
++ to compute additional terms when needed.

First, a stream is an infinite sequence. If we get

(6) -> s:=construct([1,2,3])$Stream(Integer)
(6) ->
(6) [1,2,3]
Type: Stream
Integer
(7) -> s.4
7) ->
elt: no such element

Then there is either something wrong with the code or with the
documentation.

Second, according to the documentation a Stream is a pair (A,B) where A
is a list of precomputed functions and B is a function that computes the
next value.

If you would like to know the difference between Stream and Generator,
then think of a Generator as the B part above.

In fact, in aldor-combinat, I have implemented a "DataStream" which has
representation:
Rep == Record(
gen: Generator T,
cache: PrimitiveArray T,
size: I,
numberOfElements: I,
constant?: Boolean
);

In more simpler terms, my A is Array and my B is Generator. Does that help?

Post by Bill Page
The larger question remains however: When to use a domain to directly
model something that is "set-like" and when to define a higher-order
domain whose objects are "set-like"? To me this is not clear in either
Spad or Aldor.

I don't think you gain very much if you only consider set-like domains.
If, however, you are looking at finite fields, for sure, you will think
of a domain, since it is more important that there are some operations
that connect the elements.

Ralf

Bill Page

2007-10-28 21:37:38 UTC

Post by Ralf Hemmecke
Let me cite the documentation from stream.spad.pamphlet
++ A stream is an implementation of an infinite sequence using
++ a list of terms that have been computed and a function closure
++ to compute additional terms when needed.
First, a stream is an infinite sequence. If we get
(6) -> s:=construct([1,2,3])$Stream(Integer)
(6) ->
(6) [1,2,3]
Type: Stream Integer
(7) -> s.4
7) ->
elt: no such element
Then there is either something wrong with the code or with the
documentation.

I think it is the documentation. Given the exports of Stream, it
obviously should say only "potentially infinite".

Post by Ralf Hemmecke
Second, according to the documentation a Stream is a pair (A,B) where A
is a list of precomputed functions and B is a function that computes the
next value.
If you would like to know the difference between Stream and Generator,
then think of a Generator as the B part above.

Ok.

So you say it is natural to define "PrimeField 7" as a domain itself
rather than defining a general domain of "PrimeFields" and
constructing "PrimeField 7" as an element of that domain? Yes, I think
that makes sense. But there are of course some operations that connect
elements of any well defined set, no? If it is only a matter of
degree, then I still think it is rather confusing that Axiom (and
Aldor) provides these two rather different alternative implementation
of something that is essentially the same.

I suppose what I am saying is that (maybe) there should really be no
distinction between domains and members of domains (objects) - that
all objects should also be domains in and of themselves. But of course
that is not the way Axiom was designed.

Regards,
Bill Page.

Ralf Hemmecke

2007-10-29 00:53:32 UTC

Post by Ralf Hemmecke
Let me cite the documentation from stream.spad.pamphlet
++ A stream is an implementation of an infinite sequence using ++ a
list of terms that have been computed and a function closure ++ to
compute additional terms when needed.
First, a stream is an infinite sequence. If we get
(6) -> s:=construct([1,2,3])$Stream(Integer) (6) -> (6) [1,2,3]
Type: Stream Integer (7) -> s.4 7) ->
elt: no such element
Then there is either something wrong with the code or with the
documentation.

I think it is the documentation. Given the exports of Stream, it
obviously should say only "potentially infinite".

Hmmm, I think, now we can start fighting. ;-)

I would be in favour of letting Stream(T) encode the

T^N

where N is the natural numbers.
It seems that you want Stream(T) to denote

T^N union T^(N)

where the second thing denotes the set of finite sequences (which is
actually already modelled by List or Array).

I have nothing against a domain that models the above union, but I would
like to start with basic domains and then build on them. And I would
reserve the name "Stream" for the infinite thing.

Post by Bill Page
The larger question remains however: When to use a domain to
directly model something that is "set-like" and when to define a
higher-order domain whose objects are "set-like"? To me this is
not clear in either Spad or Aldor.

I don't think you gain very much if you only consider set-like
domains. If, however, you are looking at finite fields, for sure,
you will think of a domain, since it is more important that there
are some operations that connect the elements.

So you say it is natural to define "PrimeField 7" as a domain itself
rather than defining a general domain of "PrimeFields" and
constructing "PrimeField 7" as an element of that domain?

Honestly, I don't see much of a difference. In your and my view
"PrimeField 7" is a domain, which exports certain functions.
Nobody forbids me to create a domain whose elements are domains. (Maybe
SPAD does forbid...) But I think "PrimeFields" is a rather uninteresting
domain. What exports should it have?

Post by Bill Page
Yes, I think that makes sense. But there are of course some
operations that connect elements of any well defined set, no?

Which? (Sorry, but I really cannot think of one.)

Post by Bill Page
I suppose what I am saying is that (maybe) there should really be no
distinction between domains and members of domains (objects) - that
all objects should also be domains in and of themselves.

Let's go on with your thoughts. Could you tell me what operation the
integer 2 (considered as a domain) should export?

Ralf

Bill Page

2007-10-30 16:53:31 UTC

Post by Ralf Hemmecke
Let me cite the documentation from stream.spad.pamphlet
++ A stream is an implementation of an infinite sequence using ++ a
list of terms that have been computed and a function closure ++ to
compute additional terms when needed.
First, a stream is an infinite sequence. If we get
(6) -> s:=construct([1,2,3])$Stream(Integer) (6) -> (6) [1,2,3]
Type: Stream Integer (7) -> s.4 7) ->
elt: no such element
Then there is either something wrong with the code or with the
documentation.

I think it is the documentation. Given the exports of Stream, it
obviously should say only "potentially infinite".

Hmmm, I think, now we can start fighting. ;-)

Good. :-) I am thinking in particular about the use and meaning of the
operation 'explicitlyFinite?'.

Post by Ralf Hemmecke
I would be in favour of letting Stream(T) encode the
T^N
where N is the natural numbers.
It seems that you want Stream(T) to denote
T^N union T^(N)
where the second thing denotes the set of finite sequences (which is
actually already modelled by List or Array).

No, I am only talking about the way it is implemented now.

Post by Ralf Hemmecke
I have nothing against a domain that models the above union, but I would
like to start with basic domains and then build on them. And I would
reserve the name "Stream" for the infinite thing.

I am not sure whether I would expect STREAM to always be infinite or
not. Maybe you are right since this would be the case if we wanted to
have the semantics of STREAM given by a greatest fixed point solution
(corresponding to List as least fixed point solution) of some
recursive type equation.

Post by Bill Page
The larger question remains however: When to use a domain to
directly model something that is "set-like" and when to define a
higher-order domain whose objects are "set-like"? To me this is
not clear in either Spad or Aldor.

I don't think you gain very much if you only consider set-like
domains. If, however, you are looking at finite fields, for sure,
you will think of a domain, since it is more important that there
are some operations that connect the elements.

So you say it is natural to define "PrimeField 7" as a domain itself
rather than defining a general domain of "PrimeFields" and
constructing "PrimeField 7" as an element of that domain?

Gaby has shown how to define something of type 'List Domain' in Spad e.g.

[Integer,Float,String]

which I suppose must qualify as a domain that has at least lists of
domains as elements. But I think a domain that actually has *domains*
as elements is something different, i.e a list of domains is not
itself a domain, as for example a Union or Product of domains would
be.

Post by Ralf Hemmecke
But I think "PrimeFields" is a rather uninteresting domain. What
exports should it have?

Post by Bill Page
Yes, I think that makes sense. But there are of course some
operations that connect elements of any well defined set, no?

Which? (Sorry, but I really cannot think of one.)

Ok maybe I should have said OrderedSet, then elements are at least
connected by some ordering.

Let's go on with your thoughts. Could you tell me what operation the
integer 2 (considered as a domain) should export?

In a pure object-oriented language (which really Spad and Aldor are
not), the objects inherit operations so that the constant '2' "knows"
how to add (+) another object.

But I think I want to withdraw my comment.

Ralf Hemmecke

2007-10-24 01:29:35 UTC

Post by Bill Page
[ f(x.1,x.2) for x in Product(1..9,1..4) ]

Take my implementation from

http://lists.gnu.org/archive/html/axiom-math/2007-10/msg00023.html

then I don't see a reason (in Aldor) why it shouldn't even be possible
to say

[f x for x in (1..9)*(1..4)]

where f: (Integer, Integer) -> Something.

Ralf

Bill Page

2007-10-24 02:13:09 UTC

Post by Bill Page
[ f(x.1,x.2) for x in Product(1..9,1..4) ]

Take my implementation from
http://lists.gnu.org/archive/html/axiom-math/2007-10/msg00023.html
then I don't see a reason (in Aldor) why it shouldn't even be possible
to say
[f x for x in (1..9)*(1..4)]
where f: (Integer, Integer) -> Something.

Yes, this would be (almost) possible now in Axiom/Spad if we allow the
'* to be an export of Segment and the signature of '*' to be:

* : (%,%) - > List DirectProduct(2,S)

Let's also provide

*:(List DirectProduct(2,S),%) -> List DirectProduct(3,S)

etc. I think the implementation is fairly obvious.

Not such a bad idea!

In the Axiom interpreter (but not in Spad?) we can also write a Stream
as an iterator, e.g.

(1) -> x:=repeating [1,2,3]

_____
(1) [1,2,3]
Type: Stream PositiveInteger
(2) -> [i for i in x]

(2) [1,2,3,1,2,3,1,2,3,1,...]
Type: Stream PositiveInteger

So it would be possible to replace List DirectProduct ... with Stream
DirectProduct.

But as I said earlier in this thread, this sort of construction is not
as general as I would hope for. How would I write for example?

[i for i in Product(OVAR [a,b,c], 1..3)]

[ (a,1), (a,2), (a,3), (b,1), ... ]

Regards,
Bill Page.

Gabriel Dos Reis

2007-10-24 12:02:35 UTC

On Tue, 23 Oct 2007, Bill Page wrote:

| But as I said earlier in this thread, this sort of construction is not
| as general as I would hope for. How would I write for example?
|
| [i for i in Product(OVAR [a,b,c], 1..3)]
|
| [ (a,1), (a,2), (a,3), (b,1), ... ]

My fundemantal issue to understand is making 1..9 a domain. I'm fine
with no having the most general construct, but I'm concerned with
semantics and typeing rules. In general, I'm suspicious of any
extension that is driven by just syntax.

-- Gaby

Bill Page

2007-10-24 14:23:31 UTC

Post by Gabriel Dos Reis
| But as I said earlier in this thread, this sort of construction is not
| as general as I would hope for. How would I write for example?
|
| [i for i in Product(OVAR [a,b,c], 1..3)]
|
| [ (a,1), (a,2), (a,3), (b,1), ... ]
My fundemantal issue to understand is making 1..9 a domain. I'm fine
with no having the most general construct, but I'm concerned with
semantics and typeing rules. In general, I'm suspicious of any
extension that is driven by just syntax.

I understand your suspicion however I do believe (as you may also
believe) that syntax is quite critical - particularly in *mathematics*
where I think it has often been demonstrated that proper notation is
90% (99% ?) of the problem. A good notation should help "suggest" a
solution and the language itself should be economical and dense in the
sense that almost everything that you *can* write that is
syntactically correct should have some presumably sensible and useful
meaning. Attempting to find the most general construct (: As abstract
as possible but not abstract nonsense :) is one way to approach this.

Earlier in this thread I suggested introducing a new domain I called
'IntegerSegment(S)' abbreviated INTS that would be the domain
equivalent to a given 'S:Segment(Integer)'. Then we could write:

[i for i in Product(OVAR [a,b,c], INTS 1..3)]

This does not require that '1..3' denote a domain although it does
seem less "economical".

Regards,
Bill Page.

Gabriel Dos Reis

2007-10-24 14:58:52 UTC

On Wed, 24 Oct 2007, Bill Page wrote:

|
| On 10/24/07, Gabriel Dos Reis wrote:
| >
| > On Tue, 23 Oct 2007, Bill Page wrote:
| >
| > | But as I said earlier in this thread, this sort of construction is not
| > | as general as I would hope for. How would I write for example?
| > |
| > | [i for i in Product(OVAR [a,b,c], 1..3)]
| > |
| > | [ (a,1), (a,2), (a,3), (b,1), ... ]
| >
| > My fundemantal issue to understand is making 1..9 a domain. I'm fine
| > with no having the most general construct, but I'm concerned with
| > semantics and typeing rules. In general, I'm suspicious of any
| > extension that is driven by just syntax.
| >
|
| I understand your suspicion however I do believe (as you may also
| believe) that syntax is quite critical - particularly in *mathematics*
| where I think it has often been demonstrated that proper notation is
| 90% (99% ?) of the problem.

Yes. Syntax matters.

But mathematical notations are also very deceptive and ambiguous.
As of today, we don't have universal, unambiguous, mathematical
notation used by everybody. Rather, we have variations used by
communities, with varying meanings. Therefore, we must be very
careful in putting syntax before semantics, especially for a
programming language for writing mathematical software. For a programming
language, we cannot just rely on the `common sense' of the compiler,
as we would in a casual mathematical conversation between
mathematicians.

Syntax matters. I know this from concrete experience. I'm directly
involved in the design (and implementation) of a programming language
used by over 3 millions of progammers on the planet. And, having that
huge number of users means that one get lot of feedback, suggestions,
complaints, etc., especially on syntax (if the language is believed to
have terrible syntax for bad or good). That I believe, provides
quite a unique experience from the field.

Let me cast my suspicion this way: I would like first to understand
what people want to express -- I believe I understand the simplest of
what people want to express. Once, we think we understand the
semantics and its implications well enough. How to express it should
follow. Once thing that this discussion has revealed is that we don't
seem to understand well enough the semantics.

| A good notation should help "suggest" a solution

A good notation should reflect semantics.

I'm skeptical in the efficacy of putting the cart before the horse.

[...]

| Earlier in this thread I suggested introducing a new domain I called
| 'IntegerSegment(S)' abbreviated INTS that would be the domain
| equivalent to a given 'S:Segment(Integer)'. Then we could write:
|
| [i for i in Product(OVAR [a,b,c], INTS 1..3)]
|
| This does not require that '1..3' denote a domain although it does
| seem less "economical".

It is certainly be a good thing to have an implementation of that
domain and see how much we can learn from it.

-- Gaby

Bill Page

2007-10-24 15:33:06 UTC

Post by Gabriel Dos Reis
...
| A good notation should help "suggest" a solution
A good notation should reflect semantics.

Yes. I think that is a better way of saying what I was trying to say. Thanks.

Post by Gabriel Dos Reis
I'm skeptical in the efficacy of putting the cart before the horse.

Ok, but I tend to thing of this as more of a systemic thing without
one necessarily leading the other.

Post by Gabriel Dos Reis
[...]
| Earlier in this thread I suggested introducing a new domain I called
| 'IntegerSegment(S)' abbreviated INTS that would be the domain
|
| [i for i in Product(OVAR [a,b,c], INTS 1..3)]
|
| This does not require that '1..3' denote a domain although it does
| seem less "economical".
It is certainly be a good thing to have an implementation of that
domain and see how much we can learn from it.

One thing to note is that the above construction still requires an
extension of Spad and the Axiom Interpreter syntax and semantics to
allow a domain to follow 'in'. Right now one would actually be forced
to write:

[i for i in expand()$Product(OVAR [a,b,c], INTS 1..3)]

I posted a patch for the Product domain to provide such an 'expand'
operation (maybe a better name is desirable) and also to provide
'expand' for any domain in the Finite category. But converting a
domain (Product) to a List just to iterate over it seems like a waste
and is still less economical. I would like the compiler to make this
operation transparent and more efficient.

Regards,
Bill Page.

Gabriel Dos Reis

2007-10-24 15:56:06 UTC

On Wed, 24 Oct 2007, Bill Page wrote:

| But converting a
| domain (Product) to a List just to iterate over it seems like a waste
| and is still less economical. I would like the compiler to make this
| operation transparent and more efficient.

Iteration is an old topic -- did I say that SIMULA had coroutines?
This problem has been studied to depth, with lots of solutions. As
Waldek would say, a variety of solutions is an indication that
opinions are split over which is better.

I do fully agree that it does not make much sense, from efficiency
point of view, to make a list just be to able to iterate over elments
of Product. There are various solutions to that problem. One being
generartors -- or coroutines or semi-coroutines. Another, quite
effective, is the notion of `iterator' in used the C++ Standard Template
Library.

http://www.sgi.com/tech/stl/

It relies on semantics description of iterators, along with hierarchical
categorisations of algorithms and containers bases on complexity and
semantics description of iterators. Note that STL is the result of a
long term project, some of the earlier description may be found here

http://www.stepanovpapers.com/

Basically, a domain that whish to be iterated over provides two
operations -- begin() and end() -- that people use to initiate/end
iteration over data structures. That does not require coroutines.
It can be made to work in Spad if we had good support for nested
domains.

Now, you may say that you really want begin() and end() to be implicit
in some cases, that can be made to work too -- just like generate() is
implicitly called in Aldor. For C++, there is a well-advanced
proposal for C++0x to make that work:

vector<int> v;
// ...
for (int x: v)
// ...

would be roughly equivalent to

for (auto p = v.begin(); p != v.end(); ++p) {
int x = *p;
// ...
}

Notice that this solution, when applied to BinaryTree, does not
require one to first construct a List and then iterate, and finally
throw it away. One caniterate over BinaryTree without recursion.

-- Gaby

Ralf Hemmecke

2007-10-30 16:53:00 UTC

Dear Gaby,

I've read the Wikipedia articles about Generator and Iterator, but
somehow their difference is not completely clear to me. Seemingly a
generator is more general than an iterator.

But now, coming to SPAD, do you think it is worthwhile to think of an
implementation (for SPAD) of the Iterator concept a la C++? Wouldn't the
Generator thing be enough? Or is there no plan to introduce Generator to
SPAD?

Ralf

PS: I would vote for Generator instead of Iterator (a la C++).

Post by Gabriel Dos Reis
| But converting a
| domain (Product) to a List just to iterate over it seems like a waste
| and is still less economical. I would like the compiler to make this
| operation transparent and more efficient.
Iteration is an old topic -- did I say that SIMULA had coroutines?
This problem has been studied to depth, with lots of solutions. As
Waldek would say, a variety of solutions is an indication that
opinions are split over which is better.
I do fully agree that it does not make much sense, from efficiency
point of view, to make a list just be to able to iterate over elments
of Product. There are various solutions to that problem. One being
generartors -- or coroutines or semi-coroutines. Another, quite
effective, is the notion of `iterator' in used the C++ Standard Template
Library.
http://www.sgi.com/tech/stl/
It relies on semantics description of iterators, along with hierarchical
categorisations of algorithms and containers bases on complexity and
semantics description of iterators. Note that STL is the result of a
long term project, some of the earlier description may be found here
http://www.stepanovpapers.com/
Basically, a domain that whish to be iterated over provides two
operations -- begin() and end() -- that people use to initiate/end
iteration over data structures. That does not require coroutines.
It can be made to work in Spad if we had good support for nested
domains.
Now, you may say that you really want begin() and end() to be implicit
in some cases, that can be made to work too -- just like generate() is
implicitly called in Aldor. For C++, there is a well-advanced
vector<int> v;
// ...
for (int x: v)
// ...
would be roughly equivalent to
for (auto p = v.begin(); p != v.end(); ++p) {
int x = *p;
// ...
}
Notice that this solution, when applied to BinaryTree, does not
require one to first construct a List and then iterate, and finally
throw it away. One caniterate over BinaryTree without recursion.
-- Gaby

Gabriel Dos Reis

2007-10-30 15:57:39 UTC

On Tue, 30 Oct 2007, Ralf Hemmecke wrote:

| Dear Gaby,
|
| I've read the Wikipedia articles about Generator and Iterator, but somehow
| their difference is not completely clear to me. Seemingly a generator is more
| general than an iterator.

Yes, generator -- based on co-routines -- is more general than
iterator -- which is based on functions. But the generality comes at
a price. Furthermore, I do not believe that they are mutually exclusive.

|
| But now, coming to SPAD, do you think it is worthwhile to think of an
| implementation (for SPAD) of the Iterator concept a la C++?

It depends on people.

Gabriel Dos Reis

2007-10-24 11:50:35 UTC

Bill Page

2007-10-24 13:51:35 UTC

'1..' is another (better?) name for PositiveInteger

So under my proposal 'for i in PositiveInteger repeat' should function
identically to the way

for i in 1.. repeat

works now in the interpreter where '1..' denotes an object of
'UniversalSegment PositiveInteger'.

Regards,
Bill Page.

Gabriel Dos Reis

2007-10-24 14:13:33 UTC

On Wed, 24 Oct 2007, Bill Page wrote:

| On 10/24/07, Gabriel Dos Reis <***@cs.tamu.edu> wrote:
| > On Tue, 23 Oct 2007, Bill Page wrote:
| >
| > | On 10/23/07, Ralf Hemmecke wrote:
| > | >
| > | > >>> | Product(1..9,1..4)
| > | > >>> What would be its meaning?
| > | > >
| > | > > If '1..9' and '1..4' are domains then the meaning of 'Product' is
| > | > > already given by the existing domain constructor 'Product' in the
| > | > > Axiom library
| > | >
| > | > Seems OK, but, of course the _domain_ 1..9 is then inappropriate in a
| > | > construction like
| > | >
| > | > for i in 1..9 repeat ...
| > | >
| > | > don't you agree?
| > | >
| > |
| > | No. My proposal also includes the idea that the construct
| > |
| > | for i in X repeat
| > |
| > | should expect X to be any domain that supplies a generator (like Aldor).
| >
| > so what wouold
| >
| > for i in PositiveInteger repeat
| >
| > does concretely?
| >
|
| '1..' is another (better?) name for PositiveInteger

No, it is not. Both behave quite differently in many situations.

| So under my proposal 'for i in PositiveInteger repeat' should function
| identically to the way
|
| for i in 1.. repeat

so you want to treat a domain as being identical to its ordered list
of values. But, a domain is not (just) its set of values. About
about

for i in List(Integer) repeat

or

for n in BinaryTree(Integer) repeat

| works now in the interpreter where '1..' denotes an object of
| 'UniversalSegment PositiveInteger'.

But UniversalSegment is a *particular traversal view* of PositiveInteger.

-- Gaby

Bill Page

2007-10-24 15:03:21 UTC

Actually I agree with you. But what I should have said is that the
domain PositiveInteger can subsume the operations of '1..'.

Post by Gabriel Dos Reis
| So under my proposal 'for i in PositiveInteger repeat' should function
| identically to the way
|
| for i in 1.. repeat
so you want to treat a domain as being identical to its ordered list
of values. But, a domain is not (just) its set of values.

Of course you are right. I do *not* want to treat a domain as being
identical to it's ordered list of values. A domain is many other
things besides that. However I see no reason why most domains (at
least those in the categories Finite and StepThrough) should not
provide a standard mechanism for doing such iterations.

Post by Gabriel Dos Reis
About about
for i in List(Integer) repeat
or
for n in BinaryTree(Integer) repeat

Yes, List and BinaryTree should be able to provide such iterators.
Sometimes (in particular in these cases) it is difficult to define a
"standard" ordering but the particular default ordering that is chosen
in each case can be easily documented and the alternatives produced by
some auxillary operation or coercion.

Post by Gabriel Dos Reis
| works now in the interpreter where '1..' denotes an object of
| 'UniversalSegment PositiveInteger'.
But UniversalSegment is a *particular traversal view* of PositiveInteger.

Yes, I agree. Why not make in it the "standard" one for PositiveInteger?

Regards,
Bill Page.

Gabriel Dos Reis

2007-10-24 15:09:38 UTC

On Wed, 24 Oct 2007, Bill Page wrote:

| > | So under my proposal 'for i in PositiveInteger repeat' should function
| > | identically to the way
| > |
| > | for i in 1.. repeat
| >
| > so you want to treat a domain as being identical to its ordered list
| > of values. But, a domain is not (just) its set of values.
|
| Of course you are right. I do *not* want to treat a domain as being
| identical to it's ordered list of values. A domain is many other
| things besides that. However I see no reason why most domains (at
| least those in the categories Finite and StepThrough) should not
| provide a standard mechanism for doing such iterations.

I'm NOT arguing that there should not be convenient ways to define
iterations over domains. I'm just pointing out some specific
suggestions have problems and we should first try to understand the
problem deeper. Once, I get to office, I'll provide links to some
recent work on iterating over some combinatorial structures and their
complexities.

| > About about
| >
| > for i in List(Integer) repeat
| >
| > or
| >
| > for n in BinaryTree(Integer) repeat
| >
|
| Yes, List and BinaryTree should be able to provide such iterators.

In this example, what would they be? What be the values iterated on?

| Sometimes (in particular in these cases) it is difficult to define a
| "standard" ordering but the particular default ordering that is chosen
| in each case can be easily documented and the alternatives produced by
| some auxillary operation or coercion.

You see, we have not reached understanding on the semantics and its
implications. And we can't just rely on `document the choice' to
solve the problem. I would have a problem with that if we were just
fiddling with a small scripting language that will die in a week.

-- Gaby

Ralf Hemmecke

2007-10-24 22:25:32 UTC

Post by Gabriel Dos Reis
| '1..' is another (better?) name for PositiveInteger
No, it is not. Both behave quite differently in many situations.

What?

Suppose I have given

PositiveIntegerCategory

and suppose

PositiveInteger: PositiveIntegerCategory == add {...}

then

(..)(i: Integer): PositiveIntegerCategory == PositiveInteger

For simplicity I simply ignore the parameter and in the following I
simply use an existing "IntegerType" from LibAldor.

---BEGIN aaa.as
#include "aldor"
#include "aldorio"
PositiveInteger: IntegerType == Integer add;
(..)(i: Integer): IntegerType == PositiveInteger add;
one:*Integer == 1$Integer;
import from one..;
stdout << 3 << newline;
---END aaa.as

(I don't import from Integer since I use ":*" instead of ":". Remove the
* and see what the compiler tells you.)

Add the line

for i in one.. repeat stdout << i << newline;

to the program above and try to compile. Of course it must fail.

Post by Gabriel Dos Reis
aldor -fx -laldor aaa.as

"aaa.as", line 9: for i in one.. repeat stdout << i << newline;
....^.......^
[L9 C5] #2 (Error) No meaning for identifier `i'.
[L9 C13] #1 (Error) Argument 1 of `generator' did not match any possible
parameter type.
The rejected type is
IntegerType with
== Posi....
Expected type String.

Since there is no function (..) which returns a Generator(Something).

But still, I cannot see, why

one..

behaves in any way different from PositiveInteger.

OK, you speak of SPAD and I demonstrated Aldor, so I should be quiet.

Ralf

Bill Page

2007-10-25 16:50:14 UTC

Post by Gabriel Dos Reis
| '1..' is another (better?) name for PositiveInteger
No, it is not. Both behave quite differently in many situations.

What?
Suppose I have given
PositiveIntegerCategory
and suppose
PositiveInteger: PositiveIntegerCategory == add {...}

In the existing Axiom library PositiveInteger is a subdomain of
Integer. The Axiom interpreter infers the following domain

UniversalSegment PositiveInteger

of the expression '1..'. 'UniversalSegment(S)' includes an operation
'expand' that returns a Stream(S) provided S had OrderedRing.

Post by Ralf Hemmecke
then
(..)(i: Integer): PositiveIntegerCategory == PositiveInteger
For simplicity I simply ignore the parameter and in the following I
simply use an existing "IntegerType" from LibAldor.
---BEGIN aaa.as
#include "aldor"
#include "aldorio"
PositiveInteger: IntegerType == Integer add;
(..)(i: Integer): IntegerType == PositiveInteger add;
one:*Integer == 1$Integer;
import from one..;
stdout << 3 << newline;
---END aaa.as
(I don't import from Integer since I use ":*" instead of ":". Remove the
* and see what the compiler tells you.)
Add the line
for i in one.. repeat stdout << i << newline;
to the program above and try to compile. Of course it must fail.

Post by Gabriel Dos Reis
aldor -fx -laldor aaa.as

"aaa.as", line 9: for i in one.. repeat stdout << i << newline;
....^.......^
[L9 C5] #2 (Error) No meaning for identifier `i'.
[L9 C13] #1 (Error) Argument 1 of `generator' did not match any possible
parameter type.
The rejected type is
IntegerType with
== Posi....
Expected type String.
Since there is no function (..) which returns a Generator(Something).
But still, I cannot see, why
one..
behaves in any way different from PositiveInteger.

The point is that '1..' as a 'UniversalSegment' provides only certain
specific exports which differ from those available in
'PositiveInteger'. In my previous reply to Gaby I admitted that what I
probably want is that all of the (or equivalent) exports of
'UniversalSegment(PositiveInteger)' should already be available in
'PositiveInteger' as the "standard" method of implementing what is now
available via 'StepThrough'.

Post by Ralf Hemmecke
OK, you speak of SPAD and I demonstrated Aldor, so I should be quiet.

I do really appreciate your comments. Thanks.

Regards,
Bill Page.

Ralf Hemmecke

2007-10-27 18:29:06 UTC

Post by Gabriel Dos Reis
| '1..' is another (better?) name for PositiveInteger
No, it is not. Both behave quite differently in many situations.

What?
Suppose I have given
PositiveIntegerCategory
and suppose
PositiveInteger: PositiveIntegerCategory == add {...}

In the existing Axiom library PositiveInteger is a subdomain of
Integer. The Axiom interpreter infers the following domain
UniversalSegment PositiveInteger
of the expression '1..'. 'UniversalSegment(S)' includes an operation
'expand' that returns a Stream(S) provided S had OrderedRing.

Post by Gabriel Dos Reis
aldor -fx -laldor aaa.as

"aaa.as", line 9: for i in one.. repeat stdout << i << newline;
....^.......^
[L9 C5] #2 (Error) No meaning for identifier `i'.
[L9 C13] #1 (Error) Argument 1 of `generator' did not match any possible
parameter type.
The rejected type is
IntegerType with
== Posi....
Expected type String.
Since there is no function (..) which returns a Generator(Something).
But still, I cannot see, why
one..
behaves in any way different from PositiveInteger.

The point is that '1..' as a 'UniversalSegment' provides only certain
specific exports which differ from those available in
'PositiveInteger'.

I think, you are confusing the element-domain difference. If you say

'1..' as a 'UniversalSegment'

that can only mean that

1..

is of *type*

UniversalSegment

Now, UniversalSegment(T) is a domain, so "1.." is an elment and thus
"1.." does not export anything. (That is in total contrast to what I
have constructed above. "one.." is a *domain* or type IntegerType.)

Ralf

Gabriel Dos Reis

2007-10-22 16:40:32 UTC

"Bill Page" <***@newsynthesis.org> writes:

[...]

| > | Another example of this in Axiom that *does* work right now is:
| > |
| > | DirectProduct(4,OrderedVariableList [a,b,c])
| > |
| > | OrderedVariableList is a domain constructor that takes something of
| > | List Symbol as a parameter. In order to introduce '1..9' as a domain
| > | it would be possible to introduce new domain constructor like
| > |
| > | )abbrev domain INTS IntegerSegment
| > | IntegerSegment(S:Segment Integer): with Finite ...
| > |
| > | that takes something of 'Segment Integer' as a parameter. Do we want
| > | 'IntegerSegment' to also be a subdomain of Integer?. In any case,
| > | then we could write:
| >
| > I do not see obvious reasons why I would want IntegerSegment to be a
| > subdomain of Integer.
| >
|
| Well for example, maybe I would want to write:
|
| x:IntegerSegment 1..9

BTW, a general approach I have been working on for some time now is to
have a domain ParseForm, for parse forms i.e. parse trees after they
have been property annotated, at the Spad level, and define a
protocol to construct new entities out of ParseForms. This ParseForm
domain is different from InputForm (which represents only expressions).
That way people can extend the interpreter in ways unimagined by
OpenAxiom developers, and move lot of code out of the interpreter itself.
The tricky part, of course, is to nail down the protocol so that it is
both useful and safe enough.

-- Gaby

Francois Maltey

2007-10-22 16:31:13 UTC

For me it's an exercice I give to my students in maple :
create the list of all matrices which can be magic.
They are a subset of this list :

[matrix [[a,b,15-a-b],[c,d,15-c-d],[15-a-c,15-b-d,15-a-d]]
for << all the (a,b,c,d) in 2..8 x 1..9 x 1..9 x 2..8 >> ]

My first query was about this real exercice : create this list of matrices.
(and then extract the magic ones)

mupad syntax is
[matrix [[a,b,15-a-b],[c,d,15-c-d],[15-a-c,15-b-d,15-a-d]]
$a=2..8 $b=1..9 $c=1..9 $d=2..8]

maple syntax is
['''matrix [[a,b,15-a-b],[c,d,15-c-d],[15-a-c,15-b-d,15-a-d]]
$a=2..8' $b=1..9' $c=1..9' $d=2..8]

So I'm looking for a pretty syntax in order to enumerate a cartesian Product
of lists or of segments.

There are 3 possible methods :

// A //

Today we can use

L := [1,3,5,7,9]
concat [concat [[100*a+10*b+c for a in 1..2] for b in 0..9] for c in L]

I don't find fair many concat.

Of corse
Union_{c in C} (Union_{b in B} {F(a,b,c) for c in C})
= {F(a,b,c) for (a,b,c) in AxBxC}

I write the second terms in mathematics,
and so I prefer to have this second syntax in axiom,
and the concat command looks like an union.

// B //

Concerning more general problem: I think that we also need other approaches.
More precisely, it would be good to add better iteration constructs, which
[[a, b] for a in 1..10 repeat for b in 1..5]
Well, concat version creates intermediate lists and concatenates them.
Psychologically double iteration is an atomic operation,
so it is easier (at least for some folks) to think about.

// C //

Martin seems to prefer :

L := [1,3,5,7,9]
[100*a+10*b+c for (a,b,c) in Product (1..2,0..9,L)]

I don't disapprove this point of view.
The magic [function|domain] Product generates the list
of all the possibilities.

but I'm really waiting for automatic coerces in order to have
a light command in the interpreter because this construct is (for me)
very common. So I don't want to add a lot of $... and @... everytime.

In this case the "keyword" Product has various arguments :
List or Segment. All terms don't have necessary the same type.

An other example :
LP is a list of Lagrange polynoms, Lx is the list of associated values.
I could test :
test (set [eval (P, x) for (P,x) in Product (LP, Lx)] = set [0,1])
test (set [eval (P, x) for (P,x) in Product (LP, 1..8)] = set [0,1])
even if it is better to test with a matrix.
test (matrix [[eval (P, x) for P in LP] for x in Lx] = identity(n))

F.

Martin Rubey

2007-10-22 15:19:35 UTC

It seems somewhat artificially imposed by Axiom's type hierarchy that does
not easily allow domains to be members of domains. (Domains belong to
categories, not other domains.).

Aldor does not have this problem at all. As far as I remember, even axiom's
interpreter understands such constructions, if they are implemented in Aldor.

I.e., in Aldor, you can have

define CombinatorialSpecies(L: LabelType): Category == with {
<<exports: CombinatorialSpecies>>
default {
<<defaults: CombinatorialSpecies>>
}
}

CS == (L: LabelType) -> CombinatorialSpecies L;
CombinatorialSpeciesAlgebra: with {
1: %;
X: %;
+: (%, %) -> %;
coerce: CS -> %;
coerce: % -> CS;
} == add {
Rep == CS;
coerce(cs: CS): % == per cs;
coerce(x: %): CS == rep x;
1: % == per EmptySetSpecies;
X: % == per SingletonSpecies;
(x: %) + (y: %): % == per Plus(rep x, rep y);
}

In order to introduce '1..9' as a domain it would be possible to introduce
new domain constructor like
)abbrev domain INTS IntegerSegment
IntegerSegment(S:Segment Integer): with Finite ...
that takes something of 'Segment Integer' as a parameter. Do we want
'IntegerSegment' to also be a subdomain of Integer?. In any case, then we
DirectProduct(4,IntegerSegment 1..9)
But somehow the distinction between '1..9' and 'IntegerSegment 1..9'
and '[a,b,c]' and 'OrderedVariableList [a,b,c]' seems artificial.

I think it's OK.

It occurs to me that one might like at least the Axiom interpreter to perform
some kind of automatic coercion from 'x' in a domain like 'Segment Integer'
into the *category* consisting of domains 'IntegerSegment(x)'.

You could do this with dependent types:

coerce: (s: Segment Integer) -> IntegerSegment s;

This problem pops up in many many many places: look at the series operations:

series(sin x, x=0)

we really would like to have something like (I substitute values for parameters
of the package for clarity)

series: (EXPR INT, eq: EQ EXPR INT) -> UPXS(EXPR INT, lhs eq, rhs eq)

instead we have

series: (EXPR INT, eq: EQ EXPR INT) -> Any

I'd also like to have a retraction from Matrix to RectangularMatrix:

retractIfCan: (m: Matrix INT) -> Union("failed", SquareMatrix(INT, nrows m)

instead, this retraction seems to be built into the interpreter, and cannot be
used in SPAD code.

Martin

Waldek Hebisch

2007-10-24 00:06:31 UTC

Post by Gabriel Dos Reis
BTW, a general approach I have been working on for some time now is to
have a domain ParseForm, for parse forms i.e. parse trees after they
have been property annotated, at the Spad level, and define a
protocol to construct new entities out of ParseForms. This ParseForm
domain is different from InputForm (which represents only expressions).
That way people can extend the interpreter in ways unimagined by
OpenAxiom developers, and move lot of code out of the interpreter itself.
The tricky part, of course, is to nail down the protocol so that it is
both useful and safe enough.

I wonder how do you want to handle typechecking: is ParseForm intended
to be essentially untyped representation which is passed instead of
strings to evaluator (which annotates it with types)? Or is ParseForm
(including its evaluation) intended to obey normal Spad type rules?

--
Waldek Hebisch
***@math.uni.wroc.pl

Gabriel Dos Reis

2007-10-24 11:49:31 UTC

On Wed, 24 Oct 2007, Waldek Hebisch wrote:

|
| Gabriel Dos Reis wrote:
| >
| > BTW, a general approach I have been working on for some time now is to
| > have a domain ParseForm, for parse forms i.e. parse trees after they
| > have been property annotated, at the Spad level, and define a
| > protocol to construct new entities out of ParseForms. This ParseForm
| > domain is different from InputForm (which represents only expressions).
| > That way people can extend the interpreter in ways unimagined by
| > OpenAxiom developers, and move lot of code out of the interpreter itself.
| > The tricky part, of course, is to nail down the protocol so that it is
| > both useful and safe enough.
| >
|
| I wonder how do you want to handle typechecking:

That is part of the protocol.

| is ParseForm intended
| to be essentially untyped representation which is passed instead of
| strings to evaluator (which annotates it with types)?

It is a a partially typed abstract syntax tree (like InputForm), and
operations that take ParseForm are responsible to conduct the typing
and return something of a domain that be used for further typing.

| Or is ParseForm
| (including its evaluation) intended to obey normal Spad type rules?

-- Gaby

Waldek Hebisch

2007-10-24 01:17:09 UTC

Post by Bill Page
Yes, under this proposal '1..9' would be a domain consisting of the
set of the first 9 positive integers. I want to consider the view that
this is the same as thinking of 'PositiveInteger' as a sub-domain of
'Integer'. So like 'PositiveInteger', '1..9' would inherit some of the
structure of Integer, specifically 'OrderedSet', plus exports from
'Finite' and the operations 'high', 'low' and 'incr' of
'SegmentCategory'. However 'SEGMENT', 'BY' and 'convert' of the
existing 'SegmentCategory' would have to become domain constructors.
In general I am wondering about "set-like" objects and whether these
should always be modeled as domains.

I must say that I find this idea very problematic. Why? It seems
that you require automatic convertions between normal data and types.
Even if you can avoid convertions (say by working excusively with
types) you are likely to need overloaded operations on types.
It looks that you want violate what I consider to be very useful
limitation of Spad (see below). You can avoid most problems
working with objects as demostrated by Aldor generators (general
generators are hard to implement efficiently, but at least can be
implemented and difficulties are well understood).

Now, why I do not want to allow overloading of Spad that constructors
(one may think that builtin constructors are overloaded, but builtins
are special, and they are really not overloaded but rather variadic).
This restriction means that overloads can be statically determinded
by a rather simple algorithm working separately on each function.
With overloaded types it seems only global constraint solving
could work, which is much more complex. One might think that
difficulties of implementation could be ignored. But I am affraid
that humans may have even more problems with overloaded types.

--
Waldek Hebisch
***@math.uni.wroc.pl

Bill Page

2007-10-24 01:46:26 UTC