[Axiom-developer] What is SubDomain (was: non extending category)

[Bill Page]

On February 12, 2006 7:05 PM Ralf Hemmecke wrote:
> ... 
> No I did not check. I don't speak "BOOT".

I don't speak "BOOT" either but I am slowly learning to read it a
little. :) I agree that in the absence of any documentation, this
is quite obscure. This is the kind of "source code archaeology"
that Tim Daly has referred to in the past. Tim has proposed re-
writing this in Lisp, but I am convinced this would only make
things worse.

I think the main missing information is the specific details
about the internal representation of domains and the mechanics
of how this all works. Some of this can be deduced from another
very important module written in BOOT:

http://wiki.axiom-developer.org/axiom--test--1/src/interp/InteropBoot

Would you prefer perhaps to read this coding in Lisp? Not me.

I learned a little about this from Peter Broadbery. See

http://wiki.axiom-developer.org/209TheFunctionDomainIsUndefined

also

http://lists.nongnu.org/archive/html/axiom-developer/2005-09/msg00250.html

> Now I checked and I know as much as I knew before. That code is not 
> understandable to me. Although I tend to say that in
> 
> coerceSubset([x,m,e],m') ==
>    isSubset(m,m',e) or m="Rep" and m'="$" => [x,m',e]
>    m is ['SubDomain,=m',:.] => [x,m',e]
>    (pred:= LASSOC(opOf m',get(opOf m,'SubDomain,e))) and 
> INTEGERP x and
>       -- obviously this is temporary
>      eval substitute(x,"#1",pred) => [x,m',e]
>    (pred:= isSubset(m',maxSuperType(m,e),e)) and INTEGERP x -- again 
> temporary
>      and eval substitute(x,"*",pred) =>
>        [x,m',e]
>    nil
> 
> (which is the only place where "SubDomain" appears) that does 
> not look like a DEFINITION of "SubDomain", more like USE.

Actually the "definition" of 'SubDomain' appears to be spread over
several modules. The search:

http://wiki.axiom-developer.org/axiom--test--1/src/interp/FrontPage/searchwi
ki?expr=subdomain

show that it occurs in 33 modules in the interp source code, but
I think not all of these are relevant because there are actually
two different versions of the SPAD compiler (or at least part of two)
in the source distribution and only one is actually used. But it
still seems like an amazing amount of code for something that it
really only used once in the Axiom algebra. Some of this code has
dates going back to 1986... so at least initially it must have been
anticipated that the concept of SubDomain was going to be important.

For example:

http://wiki.axiom-developer.org/axiom--test--1/src/interp/BuildomBoot

contains the comment:

-- This file contains the constructors for the domains that cannot
-- be written in ScratchpadII yet. They are not cached because they
-- are very cheap to instantiate.
-- SMW and SCM July 86
SETANDFILEQ($noCategoryDomains, '(Domain Mode SubDomain))
SETANDFILEQ($nonLisplibDomains,
APPEND($Primitives,$noCategoryDomains))

-----------

SCM: Do you happen to remember what you wrote 20 years ago? :)

> 
> >> If I compile just with the Aldor compiler, then the SPAD
> >> compiler is not involved.
> 
> > But src/algebra/integer.spad is involved indirectly through
> > the Axiom library interface, I think.
> 
> That should certainly be true, but that code does not contain
> a definition of SubDomain. It must be defined somewhere else 
> and that code must live in libaxiom.al since that is the only
> data that Aldor sees from Axiom.

'libaxiom.al' is a binary file so I can't see easily what is in
that file but I don't think there is any explicit code for
SubDomain here. Rather, it seems to me that the SPAD compiler
internally implements whatever it needs to compile this primitive
construct directly to Lisp. As far as I understand it 'libaxiom.al'
provides the interface to the Axiom modules written in SPAD, so
Aldor never has to worry about the implementation of SubDomain
as such.

> 
> >> So if the Aldor compiler does not complain, it must find
> >> "SubDomain" in libaxiom.al. I am pretty sure that the Aldor
> >> compiler does NOT know of "SubDomain" by itself.
> 
> > Perhaps it is true that stand alone Aldor does implement
> > something like SubDomain in the algebra.
> 
> There are three relevant libraries around
> 1) libaldor.al (aldor.org)
> 2) libalgebra.al (aldor.org)
> 3) libaxiom.al (AXIOM)
> 
> Since I have access to the sources of the first two libraries,
> I can assure you that there is no definition of "SubDomain"
> there.

The third one is built by Peter Broadbery's make script as part
of the Axiom/Aldor interface. I guess we would have to dig into
that code to see exactly what is in this library.

> 
> > Aldor, in a sense, is a more "primitive" compiler than SPAD,
> > i.e. with fewer things built-in and more of "SPAD" actually
> > coded in Aldor.
> 
> Right. That is the reason why it is actually easy to learn 
> Aldor. There are only a few language constructs that you have
> to remember. It is much harder to learn what is available
> through libraries. Unfortunately, there are several libraries
> around and except that libalgebra.al builds upon libaldor.al,
> there are many incompatibilities between libaxiom and
> libalgebra.

In Axiom I think we only get to use libaxiom. Using the Aldor
native library would be very complicated because of differing
internal implementations. Right?

> ...
> >> In integer.spad it says
> >>
> >> NonNegativeInteger: ...
> >>    == SubDomain(Integer, #1 >= 0) add ...
> >>
> ... 
> OK. '#1 >= 0' is depending on the first argument of SubDomain. 
> Otherwise, nobody could find out what the symbol '0' actually
> stands for. So I guess then an Aldor definition would look like
> 
> SubDomain: (T: Type, isElement?: T -> Boolean): ??? == { ... }
> 
> where ??? is some category that is quite hard to guess.
> And the second entry of SubDomain is a Boolean valued
> function (ie. '#1 >= 0' is a function).
> 
> >> But what does SubDomain return?
> 
> > SubDomain is an expression that defines a new domain.
> 
> That is a good guess. ;-)
> 
> >> And a much more interesting question: how does this work?
> 
> > For that you must consult the undocumented interp/compiler.boot
> > source code. :(
> 
> Since SubDomain is not clearly defined, nobody will be able to
> use it properly except those few people who know about its 
> semantics. For all the others it is guesswork and that totally
> contradicts the goal of Axiom to support a clear type hierarchy.

I agree. This seems to be something that should be corrected.
Perhaps, because it is actually so little used, it could even
discarded all together. Maybe this was the strategy taken when
Aldor was designed?

I think it should be possible to implement NNI (NonNegative
Integer) and PI (Positive Integer) without the use of SubDomain.
Maybe just an import of Integer would do? I do not know of any
specific case where the knowledge that NNI and PI are "subdomains"
of Integer is actually used.

> 
> >> If I see Integer, than that is a blackbox for me. I only
> >> know the interface, ie, its type or its category.
> >>
> >> Now what should SubDomain do? It takes, for example, the 
> >> implementation of a function *: (%, %) -> % from Integer
> >> and returns another implementation that checks whether the
> >> input arguments are non-negative and the result is non-negative.
> > 
> > No. I think it simply lifts all operations from Integer to NNI.
> 
> That is what I feared. It is like a hidden "pretend" somewhere.
> 
> In Aldor one could write it like
> 
> NNI: SomeCategory == Integer add {
>    Rep == Integer;
>    -- remaining functions
> }
> 
> NNI then inherits anything from Integer that it does not explicitly 
> override. So for example, if SomeCategory contains
> 
> -: (%, %) -> %
> 
> and NNI does not explicitly override it, then it is the - 
> from Integer. But that would clearly not be the intend of the
> programmer, since 3-4 is not a NNI. So one has to override it.
> 
> (a: %) - (b: %): % == {
>    c: Rep := rep a - rep b;
>    if c < 0 then throw NoNonNegativeIntegerException;
>    per c;
> }
> 

You are right that it is not that simple. In the Axiom interpreter
the commands:

  )sh NNI
  )sh PI

show that '-' is not defined in either domain. But I believe that
is because of the categories used in the definition of these
domains and not a consequence of the SubDomain specification.
See

http://wiki.axiom-developer.org/axiom--test--1/src/algebra/IntegerSpad

> I guess, what SubDomain does, is to add to each function that returns 
> "%" (i.e. a NNI) a check that is given through the second argument of 
> SubDomain.
> 
> That looks inefficient, given that there is no need for a 
> check for the addition function. :-(

No, this does not happen. But NNI does add a new function named
subtractIfCan that returns 'Union(%, "Failed")'.

> ...

Regards,
Bill Page.