Bytecode

[Pippijn van Steenhoven]

Hi,

currently, the Aldor compiler uses its own backend for writing data in a
platform independent format. Maintaining this for many platforms is a
pain, because new platforms keep emerging and the compiler code is
complex already.

In 1987, RFC1014 was created, describing a format known as XDR (eXternal
Data Representation). It supports all vital C datatypes and is directly
supported by many operating systems, notably POSIX compliant ones. There
are various toolkits around for windows.

If we really have to port to platforms for which no XDR libraries exist,
it is probably trivial to create or port one.


Another part of the compiler is the big integer arithmetic class. I would
very much like to move this to GMP. I didn't find any optimisations that
are done based on intimate knowledge of the bigint representation, but
maybe Stephen can comment on that.

Whether we can indeed move big integers to GMP is uncertain. Aldor byte
code encodes big integers as list of limbs of a certain size. They are
copied directly into the internal bigint representation as "places".
(This makes it impossible to make BInt abstract, by the way.) I'm not
sure how this can be done with GMP, which is not abstract either, but the
representation is implementation defined and may differ between versions.

I would also like to remove garbage collection from the compiler itself
and use it only for the runtime. The collector works fine but relies
heavily on platform dependent behaviour. This would result in removing
the garbage collector and memory map retrieval from the compiler code
entirely and put it into its own, separate, library.

I am rather reluctant to move Aldor to C++, because of the lack of C++
compilers on certain platforms (such as Minix 3 (where GCC is available,
but not well tested), which uses the Amsterdam Compiler Kit).


The main reason for me to "outsource" parts of the compiler is that I
eventually want to verify the compiler. That means, I want to prove that
all algorithms used terminate and yield correct results. Currently, the
compiler is wrong. It does not always terminate and does not yield
correct results. In parallel, I want to add microtests that check whether
the functions do what they are supposed to do for all (valid and invalid)
input.

I don't know whether it is possible to "fix" the compiler so it can be
formally proved right, but I'm getting a bit frustrated with it.
Theoretically no-op changes breaking everything, parts relying on
undefined or platform-specific behaviour, etc. are deadly. As a
compiler of a mathematical language, I think it is unacceptable to be
broken like this.


A (probably quite good) reason not to switch to XDR is that it would
probably break old bytecode. It might be possible to design an XDR
interface such that it is binary compatible with the Aldor bytecode, but
it would be a huge mess, because Aldor bytecode supports 16 bit integers
whereas XDR has only 32 and 64 bit integers. Also, Aldor stores floating
point numbers in its own (XFloat) format. I think this is the same as
IEEE floating point format also used by XDR. All things considered, it is
unfeasible to support the Aldor bytecode format with XDR.
It would be easy (through not trivial, it would take some time) to write
a converter for Aldor bytecode to XDR.

Now the question remains: do we want to move to XDR?


Last but not least, I would like to attend everybody to the following
mailing list items I need more feedback on:
http://www.nabble.com/Abstract-Data-Types-td20205068.html
http://www.nabble.com/Calling-ptrCanon-twice-td18987511.html
http://www.nabble.com/Internal-data-types-td19000983.html
http://www.nabble.com/Layering-in-the-compiler-td19002005.html


I would appreciate any thoughts, comments and/or suggestions to my
proposal.

Regards,

--
Pippijn van Steenhoven


_______________________________________________
Aldor-l mailing list
Aldor-l@...
http://aldor.org/mailman/listinfo/aldor-l_aldor.org

[Martin Rubey]

Dear Pippijn,

although I do not understand much about compilers, and although I really would
rather like to have FriCAS - SPAD improved to become Aldor, since Aldor will
probably never be GPL-compatible software,

I absolutely endorse every step you take that modernizes and modularizes the
compiler.

Since there are currently roughly 10 users of Aldor (and Aldor is not "make"),
I think breaking bytecodes is a non-issue.  I do not know whether FriCAS relies
on some bytecodes, but if it does, this should probably not be too difficult to
change, I hope.  (Actually, I cannot imagine it.)

I'm sorry not to be able to help more,

Martin


_______________________________________________
Aldor-l mailing list
Aldor-l@...
http://aldor.org/mailman/listinfo/aldor-l_aldor.org

[Ralf Hemmecke]

On 12/09/2008 09:58 PM, Martin Rubey wrote:
> Dear Pippijn,
>
> although I do not understand much about compilers, and although I really would
> rather like to have FriCAS - SPAD improved to become Aldor, since Aldor will
> probably never be GPL-compatible software,

But Stephen Watt proposed nearly *5 month ago* that he will work in this
direction.
Stephen? Can you confirm that you are heading for "GPL-compatible"?
(Everything else is probably as uninteresting as APL2.)

> I absolutely endorse every step you take that modernizes and modularizes the
> compiler.

Exactly.

> Since there are currently roughly 10 users of Aldor

That is one order of magnitude too high. ;-)

> (and Aldor is not "make"), I think breaking bytecodes is a non-issue.

Exacly. If there were legacy code that people are interested in, then
somebody would certainly start to raise his/her voice here on aldor-l.

 > I do not know whether FriCAS relies on some bytecodes,

The panAxiom byte-code is LISP (or rather FASL format). Connection from
Aldor to FriCAS is done via LISP. Byte-code format of Aldor is therefore
irrelevant for fricas.

Ralf

_______________________________________________
Aldor-l mailing list
Aldor-l@...
http://aldor.org/mailman/listinfo/aldor-l_aldor.org

[Ralf Hemmecke]

> Another part of the compiler is the big integer arithmetic class. I
> would very much like to move this to GMP. I didn't find any
> optimisations that are done based on intimate knowledge of the bigint
> representation, but maybe Stephen can comment on that.

I really would like GMP underneath, but I guess there is some issue with
foam and with the interface of BigInt.

First of all, there must be a reason, why BigInt is deeply planted into
the language. If I recall correctly then BigInt is also part of FOAM. So
it is a very abstract thing. Of course, the language then must define
what functionality such a BigInt should have. Unfortunately, the current
interface is not rich enough. For example, suppose x and y are BigInt's and
   z = BigInt_gcd(x,y)
   a = x/z
   b = y/z
In case one knows (as in this case) that z divides x then the division
can be done in half of the time. That algorithm is implemented in GMP,
but even if GMP where the underlying machinery of Aldor, there would be
no way to call 'exact_division' since it is not part of the
specification of BigInt.

So there is more than just moving to GMP. In fact, I think, one should
make the BigInteger machinery pluggable. From what I see from the aldor
sources, there were already attempts to use GMP.

Ralf

_______________________________________________
Aldor-l mailing list
Aldor-l@...
http://aldor.org/mailman/listinfo/aldor-l_aldor.org