Hi Waldek,
On 05/22/2008 03:58 PM, Waldek Hebisch wrote:
> Ralf Hemmecke wrote:
>> 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/
_______________________________________________
Aldor-combinat-devel mailing list
Aldor-combinat-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/aldor-combinat-devel
