Re: [Aldor-l] [Axiom-developer] spad: language and compiler

[Ralf Hemmecke]

On 08/31/2006 05:20 AM, Page, Bill wrote:
> On Wednesday, August 30, 2006 7:05 PM Ralf Hemmecke wrote:
> > ... 
> > As you know Record and Cross are two ways in Aldor to construct
> > heterogeneous tuples. The problem is that both must have a 
> > certain fixed length when you write them into your program.
> > ...
>
> What does "fixed" mean in this context?

If you write Cross(A1, A2, ..., Ak) in your program with k types 
A1,...,Ak then the the k must be a natural number. Of course you can write

Cross(A1);
Cross(A1, A2);
Cross(A1, A2, A3);

but you cannot write

Cross [x for x in g]

for some Generator G and an appropriate definition of bracket.

Oh... maybe one can... but I am too lazy to check that you can write a 
bracket: Generator Type -> Tuple Type
and hand the result to Cross.

Anyway it doesn't solve the problem of having to generate the value and 
the type at the same time.


> > Martin's line contained a "for n in primes(1,100)" iterator, 
> > so the type would only be known if the compiler were able to
> > evaluate "primes(1,100)" at compile time.
>
> > From our earlier discusion of 'random()' in the context of
> Aldor types that are determined at compile-time, it seems
> clear that it should be no problem to define a constant such
> as
>
>   P:List Integer == primes(1,100);
>
> In fact, 'primes(1,100)' is a constant expression. As we
> discovered, although P is a constant it's actual *value* is
> only determined during run-time initialization, and then it
> is fixed for the duration of the program execution. I recall
> that you demonstrated in several programs that types in Aldor
> (which must be constant) are also evaluated in exactly this
> way.

Oh, yes. Good remark.

> At first I found this very surprising but now I am pretty
> happy about it. :) That this is the case should not really
> be so surprising considering that one of the target runtime
> environments for Aldor is lisp!
>
> Anyway I see no reason in principle for Aldor to reject
> something like:
>
>   [f(100,n) for n in P]::Cross(PF(n) for n in P)
>
> where the bracket function is define by the Cross domain
> constructor.

Interesting. That looks good, but is terribly wrong. Why? Because
   for n in P
accesses P destructively. Depending on what is evaluated first, either 
the Cross is essentially Cross() or the bracket is []. What language 
specification tells you the compiler should produce? (And both would be 
wrong anyway.)

> > > > I cannot believe that a construction like
> > > >
> > > > [f(100, n) for n in [2,3,5]$List(Integer)]
> > > >
> > > > would work.
> > > The main reason why it is not working presently is because
> > > we have not constructed cartesian product over an arbitrary
> > > set of domains. But nothing in the language (even Spad)
> > > seems to prevent one from doing this.
>
> I am afraid that there may indeed be such a restriction --
> at least in SPAD. The problem is how and when the arity of
> functions is decided. The arity is actually encoded into
> the names given to the functions and as far as I know these
> names *must* be decided strictly at compile-time.

This is exactly what I meant by "fixed length" above.

> > Oh, yes, of course it is possible (even now) to construct a 
> > heterogeneous tuple type via Generator.
>
> Really?

You want me to produce code, right? ;-)

> > But Martin's construction would mean to construct the type
> > AND the element at the same time. And that (I believe) is
> > impossible.
> > ... 
> > But I still cannot make
> >
> > [f(100, n) for n in [2,3,5]$List(Integer)]
> >
> > into valid Aldor code if f is the function given by Martin.

> Probably what we need is some kind of recursive type constructor.
> See for example:
>
> http://www.cs.kent.ac.uk/people/staff/sjt/Atypical/AldorExs/vector.as
>
> Something like ... ?
>
> PFCartesian(k: Integer): Type 
>     == if k<=1 then PF(1) else Record(fst:PF(k),rst:PFCartesian(k-1));

Oh! Although it is done a bit different, you should take a look at the 
definition of RecursiveMultivariatePolynomial0. Do you have the sources 
of Aldor's LibAlgebra?

> See also section 23.8 "Recursive Strurctures" page 324 of the
> Axiom Library Compiler Users Guide, 1994:

> www.ph.ed.ac.uk/~bj/paraldor/WWW/docs/documentation/axlugII.pdf

> I hope to have more time some to work with these examples.

Oh, a definition of Tree... Not very exciting. We now have a way to 
construct a binary tree as a combinatorial species in aldor-combinat

svn co svn://svn.risc.uni-linz.ac.at/hemmecke/combinat/trunk

Look at the end of the file src/species.as.nw and you'll find the 
following definition for a tree...

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

But I have the suspicion that it is not the right code to construct 
heterogeneous products. Anyway, the interesting part in the BinaryTree 
definition is that at the same time of constructing the tree you get a 
function that generates all (labelled) trees of a given size and a 
function that counts trees of a given size (the generating function).

Ralf