element - domain level decision

[Martin Rubey]

You "It is a design decision", but my question is what you gain doing
computations at type level as opposed to computiong at element level.

I'm not sure whether my previous post was overlooked or unclear. So, I repeat
it (below) and try to make it clearer by elaborating:

When Nicolas Thiery presented MuPAD Combinat (which is really a great piece of
software), a fundamental design problem became apparent.

* on the one hand, there are combinatorial objects which are *mainly* (at
least, at first sight) interesting for looking at them, eg. Dyck paths. It
does not seem worth the effort to have a domain "Dyck Path", just for
generating all the trees with 5 elements.

* on the other hand, there are some objects, which are very naturally elements
of a domain, like permutations, lists, or sets.

In MuPAD combinat, in the end they decided to go mainly for the first option:
there is a (huge) domain-package "DecomposableObjects", with a function that
takes a grammar and (roughly) returns the objects of the language the grammar
describes.

Ralf and I were not completely happy with this approach. It somehow didn't fit
our picture how design in Aldor should work. Then we discovered the species
framework, and found that it would fit quite well.

AFAICS at practical level you do not need sets: only number of elements
matter (plus ability to "lift" permutations). Numbers and permutations live
in ordinary world, so why you go to type level?

Hm, I think that's exactly what we do: permutations are elements of the domain
Permutation. This domain in turn is a species. I do not think that you
believe that, but just to make sure: we do not consider a single permutation as
a domain.

So, what do we gain by introducing the set of Dyck paths, or any other species,
as a separate domain instead of simply considering species as elements of a
single domain -- which we do additionally?

One advantage is that it's "nicer" and more uniform. To define binary trees,
you can write

macro {
X == SingletonSpecies;
+ == Plus;
* == Times;
}
B(L: LabelType): CombinatorialSpecies L == (X + B*B)(L) add;

structures(set [1,2,3,4])$B(Integer);
generatingSeries$B(Integer);

(side remark: I have not yet stopped thinking about allowing something like

generatingSeries$B

since obviously, the label type is irrelevant to the generatingSeries.)

That is, you can give your grammar at the top level. In the other approach,
you would have to give the grammar to a wrapper function, which then generates
the objects:

BinTree := grammar(B=X+B*B)

and you would then have methods to generate them, find the generating functions
etc.:

structures([1,2,3,4], BinTree)
generatingSeries(BinTree)

But this doesn't integrate nicely with permutations, lists or sets, where
natural Aldor/Axiom domains exist. (It can be done, as MuPAD-combinat shows,
just, it doesn't feel right to us.) Personally, I like it a lot that the data
structure is really part of the species, and that the operations on species do
not depend on this data structure.

Another advantage is that all the operations on species (Plus, Times,
Composition, Functorial Composition, etc.) can exist (more or less)
independently of each other. The programming becomes very modular, even in
practice: I hardly touched Functorial Composition, but put a lot of effort into
(partitional) composition. Nicolas Thiery told us that this became quite a
problem with their approach.


I should stress that I'm well aware of the fact that our approach is not the
only one and might not be the most efficient. But so far, it feels really
good. Especially to me (less so to Ralf), the two reasons I just gave were not
very convincing at the beginning. But I think it was the right decision. I'm
already very curious how I'll think about this when we have implemented
multivariate species...


Does this answer your question?

Martin

attached my previous post.

SemiRing():Category == ....
SpeciesRingCategory():Category == SemiRing with -- add extra
operations like composition and differential ....

That's only half of the story, namely where you regard the collection of all
on the one hand, I want to be able to work with objects that are permutations,
on the other hand, I want to work with the species of permutations as an
object. In our project, we reach this goal. In fact, we do have a proof of
concept implementation of SpeciesRing, where the objects are then the various
species, i.e., Rep is CombinatorialSpecies(L).

Also, it would help if you say what combinat can do. Looking at code
I see that it can compute generating functions. It seems that you
also have code to enumerate corresponding sets, but it is not clear
what is the result: if I have species of permutations can I compose
resulting permutations?

All of that. If you are not concerned about speed, you can define the domain
Permutation as Compose(SetSpecies, Cycle).
structures set [a,b,c,d]
will then give the 24 permutations. And it is not difficult to (aldor-)extend
this domain to include all the usual operations on permutations you want, like
composition, inversion, etc.

-------------------------------------------------------------------------
This SF.net email is sponsored by: Microsoft
Defy all challenges. Microsoft(R) Visual Studio 2008.
http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/

[Martin Rubey]

Post by Martin Rubey

AFAICS at practical level you do not need sets: only number of elements
matter (plus ability to "lift" permutations). Numbers and permutations
live in ordinary world, so why you go to type level?

Hm, I think that's exactly what we do: permutations are elements of the
domain Permutation. This domain in turn is a species. I do not think that
you believe that, but just to make sure: we do not consider a single
permutation as a domain.

We are talking about different things here. IIUC species are functors from
finite sets to finite sets.

Yes.

In particular they should act on morphims of category of finite sets. In
practice, isomorphism classes of finite sets are determined by cardinality (a
single number).

Yes.

To take into account isomorphims minimally one needs to look at images of
permutations of a single set. So permutations that I am talking about are at
least formally are quite different than the elements of domain Permutation --
they are morphims of the category of finite sets

... with bijections. Let's call this category B.

I wonder if Aldor combinat handles this aspect...

I have not yet *really* thought this through, but as far as I currently can
see, we do not consider the morphisms of B (i.e., relabellings of structures)
at all, right now. In principle, we want to, because for some operations on
species, most importantly functorial composition, we know of no algorithm to
generate the isomorphism classes of the structures, except the "stupid brute
force approach": generate all structures and throw away those that arise from a
relabelling. (If I recall correctly, one can do a little better, but not
much).

I do want to keep in mind that we might want to consider also actions on the
set of labels other than relabelling. But I must admit that I do not *really*
understand yet how to reconcile species and more general finite group actions,
as considered by Adalbert Kerber and his group.

Post by Martin Rubey
So, what do we gain by introducing the set of Dyck paths, or any other
species, as a separate domain instead of simply considering species as
elements of a single domain -- which we do additionally?

[...]

Post by Martin Rubey
That is, you can give your grammar at the top level. In the other
approach, you would have to give the grammar to a wrapper function, which
BinTree := grammar(B=X+B*B)
and you would then have methods to generate them, find the generating
structures([1,2,3,4], BinTree)
generatingSeries(BinTree)
But this doesn't integrate nicely with permutations, lists or sets, where
natural Aldor/Axiom domains exist.

SpeciesDomain(s : Species): SpeciesDomainCategory ==...

Hm, what would be Species and what would be SpeciesDomainCategory? What would
SpeciesDomain yield, eg., what's the result of SpeciesDomain BinaryTree
Integer?

Aldor with "fixed" types,
full Aldor and
Aldor types.
By "fixed" types I mean that all types should (at least in principle) be
determined at compile time. Aldor with "fixed" types is just a small subset
of full Aldor. In other words, we have "identity" embedding form Aldor with
"fixed" types to full Aldor.
Full Aldor looks much more powerful, because you can do at runtime
computations with types. But if you work only with types you are in the
third formal system: Aldor types.
Again Aldor types are just a small subset of full Aldor. My impression is
that Aldor types give you rather weak programming language (quite a lot of
things which work on elements do not work on types). This language is
different (not isomorphic to) than Aldor with "fixed" types, but I think that
it should be rather straightforward to express equivalent computation at
element level

That looks like a very good insight.

-- basically the only feature that types have and normal elements do not have
is lazy evaluation. But it is known (and used in Axiom/FriCAS) that if you
stick to apropriate protocol you can easily emulate lazy evaluation.
Put it differently: power of types come from interactions with elements. So
I was expecting something like "see, we compute this type, declare element
and get such and such behaviour -- you can not do this with elements alone".

OK, but that's what we do. Well, nearly: that's what we make possible, so far
we only provided the backbone. Here is some (slightly simplified) code (from
the iso-experiment branch, but it would work with all branches, except that
"struct$Plus: % -> Record(left, right) and right$Times, left$Times is needed):

ACBinaryTree(L: LabelType): CombinatorialSpecies L with {
height: % -> Integer;
} == Plus(SingletonSpecies, Times(ACBinaryTree, ACBinaryTree))(L) add {
Rep == Plus(SingletonSpecies, Times(ACBinaryTree, ACBinaryTree))(L);

height(x: %): Integer == {
import from Integer;
X := struct rep x;
-- if X is a Singleton, the height is zero
X case left => 0;
-- otherwise, we have to compare the height of the left and the right branch
1 + max(height left X.right, height right X.right);
}
};


Maybe this comes closer to being a justification of our approach. I guess you
can still do this if BinaryTree would be an element of a domain
"CombinatorialSpecies". In this case, you'd have

CombinatorialSpecies:

decomposableObject: Grammar -> %

structures: % -> List Object

But the type "Object" is not trivial to specify. In fact, we did do this, and
Object becomes a type very similar to the type described in the aldor user
guide, or, if you prefer, "Any" in Axiom. You can then implement "height" as a
function that takes an element of Object. We didn't like that so much.

Please keep asking, your questions are very good!

Martin


-------------------------------------------------------------------------
This SF.net email is sponsored by: Microsoft
Defy all challenges. Microsoft(R) Visual Studio 2008.
http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/

[Ralf Hemmecke]

Hi Waldek,

You are semi-right. This issue is perhaps not appropriate for this
thread. It is a design decision to construct species as domains (or
rather domain constructing functors). The reason was that we wanted to
be able to write something like L = 1 + X*L (as an Aldor expression) and
have support from the compiler to produce the right code.

You "It is a design decision", but my question is what you gain doing
computations at type level as opposed to computiong at element level.
Axiom and Aldor were designed to do rather trivial computations at type
level, so you are stretching Aldor and going beyond what Axiom can do
now. I suspect that resulting code is relatively inefficient (types
store _a lot_ of administrative data).

I guess, some aspects have already been answered by Martin.
Besides modularity, there was one important aspect that got the whole
thing started, namely to define a binary tree via an aldor expression
that looks like a grammar. So we wanted something like

B = 1 + X*B*B

and at the same time "inherit" (or rather construct) the representation
for B from the representations of 1 and X. Sure, that might be
inefficient, but it is very elegant and puts all the burden of dealing
with such recursive definitions onto the compiler and not to
aldor-combinat code.

So, I would like to understand gains: combinat looks like an
interestiong usage case.

Basically, we don't have to write a parser for these recursive (even
mutually dependent) species. Aldor does it for us.

And then look more closely at the implementation of the exponential
generating series and how it is defined in Plus and Times. There are
some tricks to make this work as nicely as one would like to have it.
Why?

Consider the above equation. For the series one has to encode that
equation into the datastructure, ie, first one has to create a record R
with dummy data and then fill that record with something reasonable
where somewhere during that process (in case of a recursive definition)
(the address of) R must be accessed.

In aldor if I define a constant

a: A == expr

(where a is *not* a domain) I have not been able to access a before the
expression expr is evaluated. I.e., if I write

a: A == 1 + x*a*a

then that (most probably) will compile, but the code will segfault,
because there is not yet space allocated for a if the right hand side of
the expression is evaluated. (That is my understanding, not a claim that
it really is so.)

Now if a is a domain, that equation actually becomes

a: A == 1 + x*a*a add;

and the "add" makes the difference, since the compiler seems to reserve
some space for a before it accesses the right hand side. (Again my guess.)

In the beginning we have been experimenting a lot and only this "add"
was the break-through that led us to our decision to try an approach
where species are domains and not elements.

In fact, I thought that according to the specification of Aldor and its
treatment of elements and types on (nearly) equal footing would not make
much of a difference. Of course, I know that adding two species
basically means creating a new domain for the sum of the species, but if
that cannot be done efficiently, then that should lead to research in
compiler design and not prevent me from following that (in my eyes more
natural) approach to species.

Species theory works on sets. But neither in Aldor nor in SPAD I will
ever have sets. What I can have are sets with elements of a particular
type. (OK, one could box up every type as something of type Object, but
that would mostly throw away all the typing beauty of Aldor.)
And if you speak about "classes" ... do you meant classes in the sense
of set theory? We don't really need that since, if F is a species then
the most important questions are, what are the structures with labels
{a_1, ..., a_n}? The input is a finite set and the output as well.

Yes, I meant classes in the sense of set theory. AFAICS at practical
level you do not need sets: only number of elements matter (plus ability
to "lift" permutations). Numbers and permutations live in ordinary
world, so why you go to type level?

I think that is again natural. I actually don't go higher. In
aldor-combinat a permutation is an element of

structures([1,2,3,4])$Permutation(Integer)

and that is exactly what species tell you. The above line is translated to

F[{1,2,3,4}]

where F is the species of permutations.

Of course, one can also say [1,2,3,4]$List(Integer) is the
representation of a permutation, but then the question arises of how to
convert it to something that lives in our species world.

We haven't done this, and actually, that is not so easy, because it has
to do with ranking and unranking which we have currently completely ignored.

Hope that helps.

Ralf

-------------------------------------------------------------------------
This SF.net email is sponsored by: Microsoft
Defy all challenges. Microsoft(R) Visual Studio 2008.
http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/

[Ralf Hemmecke]

We are talking about different things here. IIUC species are functors
from finite sets to finite sets. In particular they should act on
morphims of category of finite sets. In practice, isomorphism classes
of finite sets are determined by cardinality (a single number).
To take into account isomorphims minimally one needs to look at images
of permutations of a single set. So permutations that I am taking
about at least formally are quite different than the elements
of domain Permutation -- they are morphims of the category of
finite sets. I wonder if Aldor combinat handle this aspect...

Ehm, I don't think I got what you were trying to say. What permutations
are is clear. And we all agree that there are isomorphic representations
of permutations.

As I said before, aldor cannot deal with finite sets in general, only
with finite sets of elements of a particular type. But that is not
really a restriction.

So let's say you have a type L then aldor-combinats Permutation(L) gives
you a way to list all permutations on a fixed finite subset of L.

Of course, it gives you only one particular form/representation of such
a permutation.

Could you more clearly specify what you want or thought about. I already
have a vague feeling, but it's totally clear.

Post by Martin Rubey
That is, you can give your grammar at the top level. In the other approach,
you would have to give the grammar to a wrapper function, which then generates
BinTree := grammar(B=X+B*B)
and you would then have methods to generate them, find the generating functions
structures([1,2,3,4], BinTree)
generatingSeries(BinTree)
But this doesn't integrate nicely with permutations, lists or sets, where
natural Aldor/Axiom domains exist.

SpeciesDomain(s : Species): SpeciesDomainCategory ==...

Waldek, could you be more precise here. I don't understand what
SpeciesDomain is all about. What would be SpeciesDomainCategory? And why
would there be a parameter of type Species?

Partially. You feel that this way of programming works well
(better that what Mupad folks chose) -- that is clear. But
my point of view is that we have three formal systems: Aldor
with "fixed" types, full Aldor and Aldor types. By "fixed" types
I mean that all types should (at least in principle) be determined
at compile time. Aldor with "fixed" types is just a small
subset of full Aldor. In other words, we have "identity"
embedding form Aldor with "fixed" types to full Aldor.

Do I understand correctly that "fixed"-types Aldor is where
I am not allowed to *use* my own newly created _parametric_
domains/categories? A definition like

A: with {foo: Integer} == add {foo: Integer == 1}

should be OK, right?

Full Aldor looks much more powerful, because you can do
at runtime computations with types.

Would you say that the program below classifies as
Aldor with "fixed" types
?

aldor -grun -laldor aaa.as

#1 (Warning) The file `aaa' will now be out of date.
--- elements 1
(1 nil)

--- elements 2
(1 (2 nil))

--- elements 3
(1 (2 (3 nil)))

--- elements 4
(1 (2 (3 (4 nil))))

You certainly see that this can easily be extended to generate binary trees.

But if you work only
with types you are in the thired formal system: Aldor types.
Again Aldor types are just a small subset of full Aldor.
My impression is that Aldor types give you rather weak
programming language (quite a lot of things which work
on elements do not work on types). This language is
different (not isomorphic to) than Aldor with "fixed"
types, but I think that it should be rather strigtforward
to express equivalent computation at element level
-- basically the only feature that types have and
normal elements do not have is lazy evaluation.

Yep. Lazy evaluation is sometimes useful, but I don't want to call for
it on the element level since that has probably a lot of consequences.
Maybe one could think about a new keyword "lazy", but it should be well
thought of before it is introduced.

But
it is known (and used in Axiom/FriCAS) that if you
stick to apropriate protocol you can easily emulate
lazy evaluation.

Are you speaking about the "delay" keyword?
Aldor-combinat comes with a re-implementation of series and since I
wanted to define them recursively, I basically delayed computation by
putting it into a "generate" environment.

Put it differently: power of types come from interactions
with elements. So I was expecting something like "see,
we compute this type, declare element and get such and
such behaviour -- you can not do this with elements
- different (you feel that nicer) syntax
- solving recurences (which seem to be lazy evaluation)
In other words, it looks possible that you could keep most
of the code structure you have (with all its advantages) but
work at element level -- doing mostly local syntactical changes.
Now, to know for sure one would have to recode combinat
(which I am not going to do).

Waldek, could you give a suggestion of how you would define species (as
elements) so that you get from *one* equation like

b = 1 + x*b*b

(and not grammar("b=1+x*b*b")) not only an appropriate representation
for binary trees, but at the same time the generating series (plural).

What we want is that such an expression is to be handled by the
interpreter. (I know that doesn't work at the moment.) Why would one
want to have any other syntax?

I agree with you that computing with types might be an efficiency
problem, but do you see some theoretical reason why that cannot be
resolved in the future by a better compiler?

Ralf


---BEGIN aaa.as
#include "aldor"
#include "aldorio"
macro Z == Integer;
macro I == MachineInteger;
Cat: Category == OutputType with {elements: List Z -> Generator %}
1: Cat == add {Rep == List Z; import from I;
elements(l: List Z): Generator % == generate {if zero? #l then yield
per l}
(tw: TextWriter) << (x: %): TextWriter == tw << "nil";
}

X: Cat == add {Rep == List Z; import from Rep, Z, I;
elements(l: List Z): Generator % == generate {if one? #l then yield
per l}
(tw: TextWriter) << (x: %): TextWriter == tw << first rep x;
}

L: Cat == add {Rep == Union(left: 1, right: Record(fst: X, snd: L));
import from Rep;
elementsrec(l: List Z): Generator Record(fst: X, snd: L) == generate {
u: List Z := empty;
v: List Z := l;
while not empty? v repeat {
for x in elements(u)$X repeat for y in elements(v)$L repeat yield
[x, y];
u := cons(first v, u);
v := rest v;
}
for x in elements(u)$X repeat for y in elements(v)$L repeat yield
[x, y];
}
elements(l: List Z): Generator % == generate {
for u in elements(l)$1 repeat yield per union u;
for u in elementsrec(l) repeat yield per union u;
}
(tw: TextWriter) << (x: %): TextWriter == {
if rep x case left then tw << rep(x).left;
else {y := rep(x).right; tw << "(" << y.fst << " " << y.snd << ")"}
}
}

print(n: Z): () == {
import from L, Z, List Z;
l := [i for i in 1..n];
stdout << "--- elements " << n << newline;
for e in elements(l) repeat stdout << e << newline;
stdout << newline;
}

main(): () == {import from Z; for i in 1..4 repeat print i}
main();
---END aaa.as

-------------------------------------------------------------------------
This SF.net email is sponsored by: Microsoft
Defy all challenges. Microsoft(R) Visual Studio 2008.
http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/