RE: [Axiom-developer] Re: libaxiom.a

[Page, Bill]

On Friday, March 24, 2006 8:50 AM Ralf Hemmecke wrote:
> 
> On 03/24/2006 10:44 AM, Page, Bill wrote:
> > On Wednesday, March 22, 2006 5:26 AM you wrote:
> 
> Maybe I should be quiet, but I have a vision for Axiom and
> that simply says: Use higher level language constructs
> instead of lower level ones.

No you should not be quiet! I think this is an important
subject - and not just because I happen to agree with you.
:) And I do agree. In fact I have argued exactly the same
thing in the past so it seems a little ironic to me that
I am now defending the use of Lisp (in this very specific
way).

> It also says that people contributing to Axiom should
> write in Aldor (or any even higher level language). Lower
> level constructs would only be accepted, if there is no
> way to do it in Aldor. I don't think that idea is so bad.

I think it is not bad but perhaps overly idealistic. I
think it is something that we can aim for but probably not
something that we can easily achieve. Axiom is a very large
system and we need a way to get from where we are today
to were we want to be in a more or less incremental fashion,
i.e. by taking a large number of small steps.

Also the idea of the "level" of language is a rather hard
thing to define rigourously. While I can agree informally
that it is reasonable to consider Aldor a higher-level
language than Lisp, I do not know of any metric that would
allow me to measure this in an unambiguously way and I am
sure that there are some people (e.g. experienced Lisp
programmers) who would disagree for a variety of reasons.

> 
> And for the library to make it "cleaner", I think it's
> cleaner if all the lowlevel stuff is concentrated in a
> few files. Don't you agree?

First we have to agree on how to define low-level. ;)

> 
> Think of it from the point of view of people who think
> that Axiom is in some sense great and they now decide
> to contribute to it. If they delve deeper and find that
> besides Aldor they have to learn SPAD, BOOT, LISP,
> in order to understand existing code and in order to 
> contribute, then I am sure that many people simply look
> for something simpler and turn their back to Axiom.

I agree. :( I am proposing just Aldor and Lisp - just that
part of Lisp that is convenient for historical compatibility
and particular functionality. The Lisp package appears at
the *same* level as other domains in the library - as just
some abstract data structure (S-expressions) and operations
on that structure. It's primary application is as the
underlying representation of other domains. But of course
one can use any available domain or set of domains as a
representation of some new domain.

> 
> I don't say that Lisp is bad, but it should be mostly
> hidden from the final user/contributer to the algebra
> library. People should not need to care how the underlying
> things are implemented until they want to contribute there,
> too. I just argue against Lisp (or C or Fortran or ...)
> in any **higher layer** of the Axiom library.

I think this is the same problem that one finds in the rest
of the library: Many domains seem complex and unnecessary
until we learn to appreciate how they can be used. For example
something as "mathematically obvious" as a the implementation
of a polynomial domain can have subtle and complex implications
when we consider how it interacts with other domains as some
of our early discussions here showed. S-expressions as an
abstract data structure are no different in principle.

> 
> > One can think of $Lisp as a package that naturally
> > accompanies the SExpression domain.
> 
> Well, if I look at it from an Aldor point of view it IS a 
> package call. As you said, Aldor allows "import ... from
> Foreign Lisp" where "..." list the functions that are to be
> imported. (Unfortunately, I haven't seen an import from
> "Foreign Lisp",

Here is an example (unfortunately not a very good example):

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

...

      import {
              BOOT_:_:devaluate: SExpression -> SExpression;
      } from Foreign Lisp;
      local devaluate(s: SExpression): SExpression == {
              BOOT_:_:devaluate(s);
      }

Please don't be worried about the prefix BOOT here. That is
just the Lisp package name not the BOOT language.

> 
> > The SExpression is a very important domain for Axiom.
> 
> Sorry, I cannot say much about it, but I just looked at it. 
> It seems to me that this should be the abstraction from the
> underlying Lisp that I was talking about.

Yes, it is - more or less. It is the domain whose memebers
are S-expressions and a limited number of operations of that
type.

> 
> But $Lisp is something else. In SPAD it allows to access
> any Lisp function.

Yes. Lisp appears as one *big* package. But in Lisp all
functions operation on s-expressions. In fact, functions
themselves *are* s-expressions...

> In Aldor that looks like a package call so it must be a
> package call (not a foreign function call --- maybe it
> is possible to write "osCpuTime()$Foreign(C)"). In other
> words, if you want that code to compile in Aldor, you have
> to make a package "Lisp" that exports ALL the functions
> that are ever used in the Axiom library (including NIL).

That is one way to do it, but not the only way. One could
continue to simply declare those Lisp functions where and
when one need them. It is just that in SPAD you do not need
to declare them explicitly.

> 
> > Maybe more of the commonly used Lisp constructs could
> > be implemented in SExpression, but the change would be
> > mostly cosmetic at the expense of some function call
> > overhead.
> 
> Well, shouldn't that "expense" depend on optimisations that 
> the compiler can perform?

Yes of course it does.

> 
> > Your argument might be that $Lisp is "too powerful" as a
> > package since it implements a complete, albeit lower-level,
> > symbolic programming language in itself. As such it allows
> > programmers to abuse this flexibility and write programs
> > that are more difficult to maintain.
> 
> Why was Aldor invented then? Why do people invent something 
> like BOOT or RLISP (the Reduce Lisp without brackets?)? Code
> written in higher level languages are easier to maintain,
> IMHO.

I agree. But there are compromises to be made in any large
system design.

> 
> >> For example, I see "NIL$Lisp" all over the place
> >> (153 times). Brrrhh. Wouldn't just "nil" do?
> 
> > Well, no. NIL$Lisp is of type SExpression but nil is
> > of type List. Maybe NIL should really be a constant
> > defined in SExpression.
> 
> For the latter, I would think so. The first is maybe true
> for the Axiom library, but is false in general. "nil" is
> just an identifier, it could denote anything.

Of course. My point was only that it has an associated
type so just "nil" is not enough you need to make a package
call or declare an import or something ... but you know
that.

> > 
> > I am not sure I understand what you mean by a "pointer
> > view". SExpression is a domain within SPAD whose
> > representation is provided by Lisp. NIL is a name for
> > the empty SExpression just like 'nil' is a name for the
> > empty List.
> 
> The constant for the empty list in libaldor is "empty".
> Isn't that more intuitive? If you have never come across
> LISP in your career, would you know what NIL stands for?

'empty()' is used in SPAD List domain. It happens to have
the same definition as 'nil'. These are just two names
for the same thing.

> ...
> Nobody (except the implementor) needs to know about the
> internal representation of lists. Suppose I want to
> implement the List interface by an array? Should that
> be wrong? Do you have an idea what NIL could mean then?
> All that a user of LIST needs to know is in the interface 
> (the category). The nasty details should be hidden.

Yes I agree and that is how it is now in SPAD. NIL$Lisp
is only used in the context of SExpressions. In the case
of the 'List Integer' domain we have, for example:
'empty()$List Integer' or equivalently 'nil$List Integer'.

> ... I am proposing to remove NIL (or at least to hide it
> in some low level library), since in my eyes that sounds
> not very mathematical. If I want an empty list, it is 
> much better to say "empty$List(...)" than "NIL$Lisp".
> Don't you agree?

Sure. It's only a name. Maybe the notation:

  []$List(...)

is even better? (We can hope the compiler optimizes this too.)

> > 
> > Could say a little more about the Aldor Pointer domain?
> > How is it used?
> 
> And I know that Manuel Bronstein introduced "address@hidden"
> in order to avoid "nil$Pointer pretend Record(...)" in
> some places. Sometimes "nil" is good for efficiency reasons.
> But maybe even that should be re-thought.

This sounds like the same kind of compromise to which I
referred above.

So 'nil$Ptr' is a member of some primitive type in Aldor -
probably not so different than NIL$Lisp except not connected
with S-expressions.

> 
> > I tend to think of NIL as equivalent to emtpy() for
> > a list.
> 
> That is thinking in terms of implementation.

No. My point is only that NIL has no intrinsic primitive
meaning. I guess I said that badly but I think we agree
on that.

> But if I implement
> 
> MyList(T: Type): ListType T == add {
>    Rep == Record(numEntries: Integer, l: List T);
>    ...
>    nil: % == per [0, empty$List(T)];
> }
> 
> wouldn't that make a perfect list?

Yes.

> > ... 
> > It seems to me that only thing really "Lisp'ish" about
> > this is the use of SExpression as one of the fundamental
> > data structures.
> 
> How can SExpression be so fundamental, if it doesn't even 
> exist in the libalgebra library of Aldor and one could
> still do symbolic computation? Are you saying SExpression
> is fundamental to the interpreter? Or fundamental to
> symbolic domains that are not yet in libalgebra? (I doubt 
> the latter one.)
> 

No. I am only claiming that S-expressions are fundamental
to this particular design of Axiom. Yes they are certainly
used in the interpreter but also in many places in the Axiom
library (as your grep '$Lisp' showed). As Tim said earlier:
the design of the Axiom library *assumed Lisp*. Using S-
expressions is certainly not the only way to do symbolic
computations but it is one very well understood way. Axiom
also uses several other representations such as records,
arrays etc. for different purposes.

Maybe S-expression can be defined in Aldor without imports
from foreign lisp something like this (very roughly):

  SExpression: with {
        eq:        (%,%) -> Boolean;
          ++ eq(s, t) is true if s=t (in the sense of Lisp).
        atom?:     % -> Boolean;
          ++ atom?(s) is true if s is an atom.
        coerce:   List % -> %;
          ++ convert([a1,...,an]) returns the S-expression
\spad{(a1,...,an)}.
        coerce:   Symbol   -> %;
          ++ convert(x) returns the atom x.
        coerce:   Integer    -> %;
          ++ convert(x) returns the atom x.
        car:       % -> %;
          ++ car((a1,...,an)) returns a1.
        cdr:       % -> %;
          ++ cdr((a1,...,an)) returns \spad{(a2,...,an)}.
        "#":       % -> Integer;
          ++ #((a1,...,an)) returns n.
        nil: %;
        ... etc...
  } == add {
        REP == Record(first:Union(atom:Union(sym:Symbol,int:Integer)),
list:%), rest:%);

        nil == nil$Ptr pretend Record ... ;
        coerce(x:Symbol):% == per [x,nil];
        coerce(x:Integer):% == per [x,nil];
        coerce(x:List %):% == {
          #x=0 => nil;
          #x=1 => per [x,nil];
          per [x,coerce(rest x)];
        };
        atom?(x:%):Boolean == x case atom;
        car(x:%):% == per rep(%).first;
        cdr(x:%):% == per rep(%).rest;

  etc. etc.

-----------

But then you would just be re-inventing part of Lisp inside
Aldor and there doesn't seem to be much point since you can
get all this from Lisp for "free". Aldor is designed to
compile to Lisp as one option. It is natural to continue to
use this in Axiom.

Regards,
Bill Page.