Q: unboxed values and polymorphism

Q: unboxed values and polymorphism

[Hannes Haug]

Hi,

I'm new to Ada and have a questions on polymorphism. The standard
way to have polymorphism in Ada are tagged records. But for my needs
this requires too much space. List cells would have a size of 3 words
instead of 2. I'd also have to put integers in records. This would
require too much time and space. I'd like to convert access values to
integers and do my own tagging. I could simply translate my C code.
But it would be nice to see how an experienced Ada programmer would do
this in Ada. Can I find some code that does this somewhere ? 

Thanks

 - hannes

Re: Q: unboxed values and polymorphism

[Robert Dewar]

Hannes asks

"I'm new to Ada and have a questions on polymorphism. The standard
way to have polymorphism in Ada are tagged records. But for my needs
this requires too much space. List cells would have a size of 3 words
instead of 2. I'd also have to put integers in records. This would
require too much time and space. I'd like to convert access values to
integers and do my own tagging. I could simply translate my C code.
But it would be nice to see how an experienced Ada programmer would do
this in Ada. Can I find some code that does this somewhere ?"

Use variant records. This is a very standard technique which you can
find described in any standard Ada text book, I would recommend
Barnes. Translating your C code would surely result in a horrible
montrosity! No respectable Ada programmers would convert access
values to integers except for very special low level purposes.

Re: Q: unboxed values and polymorphism

[Jon S Anthony]

In article <uvvyblp84l7.fsf@chaq.informatik.uni-tuebingen.de> Hannes Haug <Hannes.Haug@Student.Uni-Tuebingen.de> writes:

> I'm new to Ada and have a questions on polymorphism. The standard
> way to have polymorphism in Ada are tagged records. But for my needs

If it helps, it also works this way in C++, Eiffel, Sather, and any
other "statically" typed OO language.

> this requires too much space.

Then you are in trouble no matter what.

> require too much time and space. I'd like to convert access values to
> integers and do my own tagging. I could simply translate my C code.

This sounds like a _really_ _really_ bad idea.  In your C, are you
using "meta" bits (ala' Lisp impls) or what?


> But it would be nice to see how an experienced Ada programmer would do
> this in Ada. Can I find some code that does this somewhere ? 

I'm not sure what it is you are trying to do.  Make a list?  Make
a generic list?  Make a typed polymorphic list?  Make an untyped
uncheckd programmer beware list?  What?

/Jon
-- 
Jon Anthony
Organon Motives, Inc.
1 Williston Road, Suite 4
Belmont, MA 02178

617.484.3383
jsa@organon.com

Re: Q: unboxed values and polymorphism

[Hannes Haug]

>>>>> "Jon" == Jon S Anthony <jsa@organon.com> writes:

    Jon> In article <uvvyblp84l7.fsf@chaq.informatik.uni-tuebingen.de>
    Jon> Hannes Haug <Hannes.Haug@Student.Uni-Tuebingen.de> writes:
    >> I'm new to Ada and have a questions on polymorphism. The
    >> standard way to have polymorphism in Ada are tagged
    >> records. But for my needs

    Jon> If it helps, it also works this way in C++, Eiffel, Sather,
    Jon> and any other "statically" typed OO language.

    >> this requires too much space.

    Jon> Then you are in trouble no matter what.

But the trouble is not that big.


    >> require too much time and space. I'd like to convert access
    >> values to integers and do my own tagging. I could simply
    >> translate my C code.

    Jon> This sounds like a _really_ _really_ bad idea.  In your C,
    Jon> are you using "meta" bits (ala' Lisp impls) or what?

Sort of. Fixnums are integers in the range -2^30 ... 2^30-1. Other
integers are interpreted as pointers to (or indices in arrays of)
bignums or list cells. And it is not a bad idea.


    >> But it would be nice to see how an experienced Ada programmer
    >> would do this in Ada. Can I find some code that does this
    >> somewhere ?

    Jon> I'm not sure what it is you are trying to do.  Make a list?
    Jon> Make a generic list?  Make a typed polymorphic list?  Make an
    Jon> untyped uncheckd programmer beware list?  What?

I need it for my computer algebra nucleus. I need lisp-like dynamic
typing. I cannot use tagged records. This would make a list cell 50%
bigger. This would mean 33% less list cells. And this would mean 50%
more garbage collections. I also need the type information on the stack
for my garbage collector. I cannot use records for fixnums either. This
would mean a "new" for every operation. My nagation takes ca. 20 nsec
for fixnums on a 90MHz hyperSPARC. With a "new" this would be a not so
little bit slower. Perhaps the usage of records for fixnums would even
make some functions too big for inlining.

 - hannes

Re: Q: unboxed values and polymorphism

[Tucker Taft]

Hannes Haug (Hannes.Haug@Student.Uni-Tuebingen.de) wrote:

: ...
: Sort of. Fixnums are integers in the range -2^30 ... 2^30-1. Other
: integers are interpreted as pointers to (or indices in arrays of)
: bignums or list cells. And it is not a bad idea.

:     Jon> I'm not sure what it is you are trying to do.  Make a list?
:     Jon> Make a generic list?  Make a typed polymorphic list?  Make an
:     Jon> untyped uncheckd programmer beware list?  What?

: I need it for my computer algebra nucleus. I need lisp-like dynamic
: typing. I cannot use tagged records. This would make a list cell 50%
: bigger. This would mean 33% less list cells. And this would mean 50%
: more garbage collections. I also need the type information on the stack
: for my garbage collector. I cannot use records for fixnums either. This
: would mean a "new" for every operation. My nagation takes ca. 20 nsec
: for fixnums on a 90MHz hyperSPARC. With a "new" this would be a not so
: little bit slower. Perhaps the usage of records for fixnums would even
: make some functions too big for inlining.

Rather than tagged records, which allow for "unbounded" polymorphism,
you might want to simply use a variant record.  By using an appropriate
record representation clause, you should be able to keep your list
cells down to 2 words.  You might still find a use for unbounded
polymorphism (i.e. tagged records), when you point to larger objects 
which are not simply composted of list cells.  However, if you
are essentially implementing a variant of Lisp, then I doubt if
tagged records will do much for you.  Tightly encoded variant records
seem more likely to be the answer.

:  - hannes

-Tucker Taft   stt@inmet.com   http://www.inmet.com/~stt/
Intermetrics, Inc.  Cambridge, MA  USA

Re: Q: unboxed values and polymorphism

[Tucker Taft]

Tucker Taft (stt@henning.camb.inmet.com) wrote:
: ...You might still find a use for unbounded
: polymorphism (i.e. tagged records), when you point to larger objects 
: which are not simply composted of list cells.
                       ^^^^^^^^^  Oops, "composed" (not decomposed ;-)

-Tucker Taft   stt@inmet.com   http://www.inmet.com/~stt/
Intermetrics, Inc.  Cambridge, MA  USA

Re: Q: unboxed values and polymorphism

[Tucker Taft]

One other thought...

Hannes Haug (Hannes.Haug@Student.Uni-Tuebingen.de) wrote:

: ...
: Fixnums are integers in the range -2^30 ... 2^30-1. Other
: integers are interpreted as pointers to (or indices in arrays of)
: bignums or list cells. And it is not a bad idea.

One of the nice things about Ada is that a private type can
be implemented with any sort of type.  So you could declare a private
type to represent one of these 32-bit multi-purpose number/pointers,
define "safe" operations in the visible part for using the type 
appropriately, and still implement it internally with a regular Integer 
(or whatever works best).  

Other OOP languages usually force all abstract data types to be
implemented using a record type, often with some "tag"-like overhead
(e.g. pointer to virtual function table, etc.).  

In a case like yours, a private type implemented with an Integer
would seem to give you the space efficiency you desire, and by
inlining the "access" subprograms you should be able to get the
necessary time efficiency, without sacrificing safety.

:  - hannes

-Tucker Taft   stt@inmet.com   http://www.inmet.com/~stt/
Intermetrics, Inc.  Cambridge, MA  USA

Re: Q: unboxed values and polymorphism

[Hannes Haug]

Hi,

>>>>> "TT" == Tucker Taft <stt@henning.camb.inmet.com> writes:

    TT> Rather than tagged records, which allow for "unbounded"
    TT> polymorphism, you might want to simply use a variant record.
    TT> By using an appropriate record representation clause, you
    TT> should be able to keep your list cells down to 2 words.  You
    TT> might still find a use for unbounded polymorphism (i.e. tagged
    TT> records), when you point to larger objects which are not
    TT> simply composted of list cells.  However, if you are
    TT> essentially implementing a variant of Lisp, then I doubt if
    TT> tagged records will do much for you.  Tightly encoded variant
    TT> records seem more likely to be the answer.

But will this give me unboxed integers and type information on the stack ?
I'd try a private type that's actually an integer. I'd use half of this
integers (-2**30 ... 2**30-1) for my fixnums. Values outside this range
would be indices in arrays of bignums or list cells. So I'd have unboxed
integers and type information on the stack.

 - hannes

Re: Q: unboxed values and polymorphism

[Fergus Henderson]

Hannes Haug <Hannes.Haug@Student.Uni-Tuebingen.de> writes:

>> "TT" == Tucker Taft <stt@henning.camb.inmet.com> writes:
>
>    TT> Tightly encoded variant records seem more likely to be the answer.
>
>But will this give me unboxed integers and type information on the stack ?

I'm no Ada expert, but I think that the theoretical answer is "it
depends on the compiler" and that the practical answer is that existing
Ada compilers won't be able to pack pointers and tag bits into a single
word.  (Ada afficionados, please correct me if I'm wrong!)

It's definitely possible for a compiler to do this sort of packing of
variant records; the compiler for Mercury does this in many cases.
(I know this because I wrote quite a bit of the code that does it ;-)

--
Fergus Henderson <fjh@cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3         |     -- the last words of T. S. Garp.

Re: Q: unboxed values and polymorphism

[Robert Dewar]

Hannes says

"But will this give me unboxed integers and type information on the stack ?
I'd try a private type that's actually an integer. I'd use half of this
integers (-2**30 ... 2**30-1) for my fixnums. Values outside this range
would be indices in arrays of bignums or list cells. So I'd have unboxed
integers and type information on the stack."

You are encoding at a very low level, appropriate for C (since it is the
only way to do things), but totally inappropriate for Ada. You need a
variant record with a discriinant to indicate whether you have fixnums
or indices. The discriminant would be a single bit.

Re: Q: unboxed values and polymorphism

[Robert A Duff]

In article <dewar.835121144@schonberg>, Robert Dewar <dewar@cs.nyu.edu> wrote:
>You are encoding at a very low level, appropriate for C (since it is the
>only way to do things), but totally inappropriate for Ada. You need a
>variant record with a discriinant to indicate whether you have fixnums
>or indices. The discriminant would be a single bit.

And the pointer would be 31 bits, so the whole thing fits in 32?  Quite
reasonable, except that I've never heard of an Ada compiler that can
support that kind of packing.  Certainly, the RM does not require
support for that sort of packing.

No, I think the low-level technique used to do this in C is exactly the
same low-level technique that is necessary in Ada.  The nice thing about
Ada is that it allows you to isolate such low-level stuff from the bulk
of your application.

- Bob

Re: Q: unboxed values and polymorphism

[Robert Dewar]

Robert Duff said

"And the pointer would be 31 bits, so the whole thing fits in 32?  Quite
reasonable, except that I've never heard of an Ada compiler that can
support that kind of packing.  Certainly, the RM does not require
support for that sort of packing."

It does not need to be a pointer, it can be an index, or simply an 
encoded pointer (you can certainly encode the pointer). I still prefer
the abstraction of a variant record here, although I agree that if you
hide the low level representation under the covers it does not matter
that much.

If you use the approach of a pointer with its low order bit fudged to
flag the integer case (i.e. the hardware structure used on the Sparc),
then you still have to do unchecked mucking to get the pointer anyway.

So it seems to me preferable to encode the pointer in 31 bits, and the
discriminant in 1 bit. You need to do equivalent unchecked mucking to
encode the pointer, but the structure is still preferable.

P.S. in assembly language, I usually use a slightly different approach here
of putting the flag bit in the sign bit and having the remainder of the
word be the pointer divided by two. That way you should the whole word
left one bit, and the flag is now in the carry bit, and the pointer is
correct in the register. You can actually persuade gcc to generate code
that is equivalent if you are VERY careful to state things right (that's
an odd style of code which happens some times, really you are writing
assembly language, but you are forced to play a delicate balancing game
between some high level language and its optimizing compiler -- not the
sort of thing one generally wants to encourage :-)

Re: Q: unboxed values and polymorphism

[Hannes Haug]

>>>>> "Robert" == Robert Dewar <dewar@cs.nyu.edu> writes:

    Robert> Hannes says "But will this give me unboxed integers and
    Robert> type information on the stack ?  I'd try a private type
    Robert> that's actually an integer. I'd use half of this integers
    Robert> (-2**30 ... 2**30-1) for my fixnums. Values outside this
    Robert> range would be indices in arrays of bignums or list
    Robert> cells. So I'd have unboxed integers and type information
    Robert> on the stack."

    Robert> You are encoding at a very low level, appropriate for C
    Robert> (since it is the only way to do things), but totally
    Robert> inappropriate for Ada. You need a variant record with a
    Robert> discriinant to indicate whether you have fixnums or
    Robert> indices. The discriminant would be a single bit.

Absolutely not. On the stack I have words and not records. I work at a
low level because it is necessary. I really don't want to have a explicit
bit. I don't want to wrap/unwrap my data. Otherwise I would choose the low
bits as tag bits. This has nothing to do with C or Ada. It has to do with
costs of type checks, tagging, untagging and arithmetic on tagged integers.
If you keep telling people that this is evil they will never implement lisp,
prolog, ... in Ada.

 -hannes

Re: Q: unboxed values and polymorphism

[Robert Dewar]

Hannes says

"Absolutely not. On the stack I have words and not records. I work at a
low level because it is necessary. I really don't want to have a explicit
bit. I don't want to wrap/unwrap my data. Otherwise I would choose the low
bits as tag bits. This has nothing to do with C or Ada. It has to do with
costs of type checks, tagging, untagging and arithmetic on tagged integers.
If you keep telling people that this is evil they will never implement lisp,
prolog, ... in Ada.

 -hannes"

No one is saying it is evil, just that your low level approach sounds
inappropriate. Write some EXACT low level code of the type you are
suggesting, with the operations that go with it, and let's see what
it looks like. The "costs of type checks etc. etc." that you refer
to should be zero as far as I can see, but we really need exact code
to proceed usefully in this discussion.

You can perfectly well implement Lisp in Ada using an appropriate level
abstraction without any unaccptable overhead!

Re: Q: unboxed values and polymorphism

[Robert Dewar]

Hannes said

"Let's assume your fixnums have the low bits `00' as tags. To add
two fixnums, you would extract them from the word, perform the
usual addition and put the result in a variant record? I'd just
add the words."

So what, you would get the same code!

Re: Q: unboxed values and polymorphism

[Fergus Henderson]

dewar@cs.nyu.edu (Robert Dewar) writes:

>Hannes said
>
>"Let's assume your fixnums have the low bits `00' as tags. To add
>two fixnums, you would extract them from the word, perform the
>usual addition and put the result in a variant record? I'd just
>add the words."
>
>So what, you would get the same code!

That's presuming the compiler is smart enough, which is a very big IF.
Have you tried this with GNAT?

I tried a simple example in C, and found that GNU C on an Alpha
generated worse code using bitfields than using the approach
suggested by Hannes above; in particular, it does not avoid the
unnecessary shifts on the operands and result of the addition.
I doubt if GNAT would do any better.

(The test case I used is available on request, should anyone wish
to duplicate the results of my experimentation.)

--
Fergus Henderson <fjh@cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3         |     -- the last words of T. S. Garp.

Re: Q: unboxed values and polymorphism

[Jon S Anthony]

In article <uvv7mt7ubgd.fsf@chaq.informatik.uni-tuebingen.de> Hannes Haug <Hannes.Haug@Student.Uni-Tuebingen.de> writes:

> >>>>> "Jon" == Jon S Anthony <jsa@organon.com> writes:
> 
>     Jon> In article <uvvyblp84l7.fsf@chaq.informatik.uni-tuebingen.de>
>     Jon> Hannes Haug <Hannes.Haug@Student.Uni-Tuebingen.de> writes:
>     >> I'm new to Ada and have a questions on polymorphism. The
>     >> standard way to have polymorphism in Ada are tagged
>     >> records. But for my needs
> 
>     Jon> If it helps, it also works this way in C++, Eiffel, Sather,
>     Jon> and any other "statically" typed OO language.
> 
>     >> this requires too much space.
> 
>     Jon> Then you are in trouble no matter what.
> 
> But the trouble is not that big.

OK, I had two strikes against me, this one looks like I managed a
"foul ball".


>     >> require too much time and space. I'd like to convert access
>     >> values to integers and do my own tagging. I could simply
>     >> translate my C code.
> 
>     Jon> This sounds like a _really_ _really_ bad idea.  In your C,
>     Jon> are you using "meta" bits (ala' Lisp impls) or what?
> 
> Sort of. Fixnums are integers in the range -2^30 ... 2^30-1. Other
> integers are interpreted as pointers to (or indices in arrays of)
> bignums or list cells. And it is not a bad idea.

Aha.  Yes, this is not so bad an idea.  I thought you meant "tagging"
in the Ada sense of "tagged types" and you were going to do your own
"subclassing" and dispatching stuff, but thought just maybe you had
the "meta bit" stuff in mind.  Well, I'm not completely dead yet.

In this case, you might get away with unchecked conversion.  It will
basically give you the same as you had in your C.  The question, of
course, is this safe?  If integers and access types are not "just 32
bit [or 64 bit] units" you will be in trouble.  This would be true
even in the case where access values were "just addresses" and
addresses did not have the same machine level representation as
integers (basically n-bit "words")


>     Jon> I'm not sure what it is you are trying to do.  Make a list?
>     Jon> Make a generic list?  Make a typed polymorphic list?  Make an
>     Jon> untyped uncheckd programmer beware list?  What?
> 
> I need it for my computer algebra nucleus. I need lisp-like dynamic
> typing. I cannot use tagged records. This would make a list cell 50%
> bigger. This would mean 33% less list cells. And this would mean 50%

Yes, I've been here before.  This is not an easy nut to crack in
order to have something really satisfactory.  I did not use tagged
types for the cells either.


> more garbage collections. I also need the type information on the stack
> for my garbage collector. I cannot use records for fixnums either. This
> would mean a "new" for every operation. My nagation takes ca. 20 nsec
> for fixnums on a 90MHz hyperSPARC. With a "new" this would be a not so
> little bit slower. Perhaps the usage of records for fixnums would even
> make some functions too big for inlining.

Yes, all of these are real issues and keep leading down various rat-holes.
The problem is that you really can't do a _nice_ job of what you want
to do _in the language_.  It just doesn't have quite the support.  To
get close, you will probably have to define your own storage pools and
allocation and get this hooked into your GC.  But of course this means
that at the _client_ level, some tagged types will likely be running
around (for finalization of stack allocated stuff...)

What I ended up doing was making the client level list "not just"
carcdr cell.  The actual carcdr implementation was a hidden attribute
which for all its cells always use my internal storage pool machinery.
The client level list type had enough brains to "do the right thing"
at finalization (mostly for stack allocation reasons), had the overhead
of a tagged type but removed this overhead from the carcdr cells and
their allocation/deallocation (which used a scavenging GC algorithm)

You'd probably have to extend this scenario some to accomodate the
requirements of your fixnums.


Well, I'm not sure if I managed to get out of this or not!  Strike
three?

/Jon
-- 
Jon Anthony
Organon Motives, Inc.
1 Williston Road, Suite 4
Belmont, MA 02178

617.484.3383
jsa@organon.com

Re: Q: unboxed values and polymorphism

[Hannes Haug]

>>>>> "Jon" == Jon S Anthony <jsa@organon.com> writes:
    
    Jon> In this case, you might get away with unchecked conversion.
    Jon> It will basically give you the same as you had in your C.
    Jon> The question, of course, is this safe?  If integers and
    Jon> access types are not "just 32 bit [or 64 bit] units" you will
    Jon> be in trouble.  This would be true even in the case where
    Jon> access values were "just addresses" and addresses did not
    Jon> have the same machine level representation as integers
    Jon> (basically n-bit "words")

But I can convert pointers to System.Storage_Elements.Integer_Address.
But this could be a modular integer type. :-( If Integer_Address is a
signed integer type I can just use this for my pointers and fixnums.

    [...]

    Jon> Yes, all of these are real issues and keep leading down
    Jon> various rat-holes.  The problem is that you really can't do a
    Jon> _nice_ job of what you want to do _in the language_.  It just
    Jon> doesn't have quite the support.  To get close, you will
    Jon> probably have to define your own storage pools and allocation
    Jon> and get this hooked into your GC.  But of course this means
    Jon> that at the _client_ level, some tagged types will likely be
    Jon> running around (for finalization of stack allocated stuff...)

    Jon> What I ended up doing was making the client level list "not
    Jon> just" carcdr cell.  The actual carcdr implementation was a
    Jon> hidden attribute which for all its cells always use my
    Jon> internal storage pool machinery.  The client level list type
    Jon> had enough brains to "do the right thing" at finalization
    Jon> (mostly for stack allocation reasons), had the overhead of a
    Jon> tagged type but removed this overhead from the carcdr cells
    Jon> and their allocation/deallocation (which used a scavenging GC
    Jon> algorithm)

    Jon> You'd probably have to extend this scenario some to
    Jon> accomodate the requirements of your fixnums.

You have certain controll over your pointers if you allocate the list cells
in a mmaped region. That's what I've done in C. So my pointers will never
be in the range of my fixnums. You can even make shure that this pointers
have a unique bit pattern. So I have real fixnums and real pointers. There
are no `explicit' tags. Most of the time I even don't have to do an exact
type check in my gc. That's only necessary while scanning the stack. When
I'm traversing a list the checks can be a little bit simpler and faster.
But I'm not shure if the whole thing is worth the trouble.

 - hannes