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

[William Sit]

On Wed, 30 Aug 2006 13:35:55 +0200
 Ralf Hemmecke <address@hidden> wrote:
> > > > > f(m: INT, n: INT): PF n == m::PF(n)
Martin's expression:
> > > > > [f(100, n) for n in primes(1,100)]
> > I would think it is an element (not a list) in a 
> > cartesian product of #primes(1,100) prime fields.
>
> OK, if you like. But then I would like to see the 
> definition of the bracket function. Can you give that?

One main difference between list of mathematical objects 
and say C++ objects is that the former is often 
homogeneous (elements of the list are of the same type) 
but the latter is often heterogeneous (elements need not 
be of the same type). In Axiom, all lists are homogeneous 
(even List Any) by definition of the domain List (or the 
domain Tuple). A variant that allows hetergeneous objects 
in a "list" is the domain Record. The bracket constructor 
is by default the list constructor but can be used to 
construct elements of Record. But since Record must have 
pre-defined named fields, Martin's line could not have 
meant a Record element. It certainly is not a list in the 
Axiom sense. So the remaining possibility is an element of 
a cartesian product. Axiom currently has a constructor for 
cartesian product of two sets: Product, where elements are 
constructed using the function makeprod. But here, we are 
not discussing existing domains, but rather whether 
Martin's expression is mathematically meaningful and 
whether the language allows its construction in Aldor. 

Getting back to your question, it is up to the programmer 
to define the bracket function for the domain where 
Martin's expression lives. Even though it may not be 
possible in Axiom to directly program tuples of 
heterogeneous domains, such tuples are present in most 
function signatures like foo:(INT, Boolean)->INT. I would 
expect Aldor therefore to be able to directly program 
tuples of heterogeneous domains. Thus Martin's expression, 
perhaps using round parentheses instead of brackets, 
should work in Aldor.

> I strongly believe you can't, because that would require 
> Aldor to compute "primes(1,100)" at compile time. Which 
> is currently not possible and if the compiler is allowed 
> to evaluate it then it might run into an infinite loop 
> (at compile time) since the "primes" function does not 
> terminate as you would expect. Compile time evaluation in 
> full generality introduces a way make it really hard to 
> find bugs.

I don't know how "primes" is implemented but it is 
probably a built-in using both a table for lower range and 
some sophisticated algorithms for higher ones. I am not 
suggesting compile time evaluation be extended to all 
static computations, but my guess is "primes" is special. 
A bit of compiler optimization would probably evaluate 
expressions like 2+3, so why not primes(1,100)? Obviously, 
compile time evaluation should be severely restricted 
(otherwise many programs may compile to just the output if 
no input is required).

> But anyway, maybe Aldor should allow compile time 
> evaluation.
>
> > > > Ask yourself, what type that list will have and you 
> > > > realise that 
> > > > Aldor will
> > > > reject that its compilation.
> > > Excuse me, Gaby. Sorry about being so stupid.
> >
> > It's a perfectly good mathematical object in a cartesian 
> > product.
>
> William is right, but 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.

> [f(100, n), f(100, n), f(100, n)]

You meant: [f(100,2), f(100,3), f(100,5)], I assume.

> should be easily definable and give an element in the 
> cartesian product of   PF(2), PF(3), and PF(5). But that 
> is a finite construct and not done via Generator as 
> above.

As discussed above, what is missing is cartesian product 
over an arbitrary set of domains. If domains are first 
class objects, we should be able to construct sets of 
them, even via Generator, and hence also cartesian 
product. At the very least, one should be able to form a 
set or list of domains of the same category (which IS 
homogeneous). Something like:

Product(A: List PrimeField, B: List) 

where B is the index "set." Or, as you did below, using an 
anonymous function as the argument.

> > > > > [a::P for P in L]
> > > > That is as problematic as the first list.
> > > "problematic" is an understatement. Sorry.
> >
> > Ditto. The only problem I see that can't be handled is if 
> > you make it into a function of k:
>
> > [f(100, n) for n in primes(1,k)]
>
> Initially, I believe, Martin wanted lists. What you are 
> calling for is a cartesian product constructor of the 
> form.
>
> PFCartesian(k: Integer): with {
>     coerce: ((n: Integer) -> PF(n)) -> %;
>     ...
> }== add {
>     ...
> }

I am not following. Is PFCartesian(k) a cartesian product 
of the first k prime fields, like PFCartesian(3) is PF(2) 
x PF(3) x PF(5)? Then given a function (n:Integer)->PF(n) 
(basically, an sequence of elements, one from each PF(n), 
and n better be a prime! but let's pretend we interpret 
PF(n) as Integer mod n), the coerce function maps the 
anonymous function to PFCartesian(k) by using the first k 
elements in the sequence?

> Then instead of [f(100, n) for n in primes(1,k)] it would 
> be more appropriate to define
>
> k: Integer == << stdin; -- read from standard input and 
> make it constant
> foo(m: Integer)(n: Integer): PF(n) == m :: PF(n);
> import from PFCartesian(k);
> z := foo(42) :: PFCartesian(k);
>
> Such a construction would work, but it does not involve a 
> Generator or something that you must compute at compile 
> time.

The construction of the domain PFcartesian(k) might, even 
when k is given at instantiation time, depending on the 
meaning of that domain.

William