What are the final words on GMP, BigNums and *BooleanArrays ?????????????

0 views
Skip to first unread message

Karl Forner

unread,
Oct 9, 2006, 10:26:40 AM10/9/06
to Internals List
Hi,

It's not that easy to contribute to parrot development.
I got into that by picking a TODO task about *BooleanArrays, that seemed
appropriate for a Parrot newbie that
knows a bit about algorithmics and Data structures.

Answering one of my mail, Bernhard raised the question of using a common
implementation for strings, boolean arrays.
And that maybe this implementation could be borrowed from the Perl5
Bit::Vector library.

It reminded me of something I read on this list, about the GMP library.
So I checked the GMP website, ok looks great.
I've also noted that there are some GMP-based implementations and GMP stuff
in Parrot, and a GMP test.

But a priori not a word in the specifications and the design documents.
So I tried to track all the GMP related threads, and that's not that easy,
for instance there does not seem to be a "search" feature on the nntp
archive. I tried using some news readers then found my happiness with Google
Groups (always Google). But there's also some materials in the blogs for
example.

So what did I found, among other stuff ?

in Joshua Gatcomb mail, 2004-07-31
> The "make ICU optional"
> was supposed to read "make ICU like GMP" - autodetect
> it if present, but do not force it upon the user.

in the Perl 6 Summary for the week ending 2004-07-18:
> GMP Licensing
> Armin Obersteiner reported his investigations into the licensing
> requirements of the GMP maths library. It appears that the FSF's 'GPL

> Compliance Engineer' reckons we won't need to include the GMP's
source
> code with binary distributions. We just have to make it available
from
> the same source as the distribution. Which is handy.

A thread "GMP's license looks Parrot-compatible" starting on 2004-06-30

SO MY POINT IS:

1) it seems that a decision has been made, but that it not written anywhere,
and at least not on the parrot site.
This decision is, in my understanding, to use an internal fall-back poor
man's implementation.

2) Nor could I find the rationale for that decision. I've read some IMHO
good arguments for including or for linking, but not a definitive summary,
because from the last stuff I read, it seems that the Licensing issues are
not blocking

3) I spent more time trying to figure out the right thing to do than in my
opinion coding something useful.

WHAT I'D LIKE:

* Some place, in the docs/ part of the parrot website, where that kind of
decision is recorded, along with pointers to relevant information.
A kind of proceedings, or critical review, I'm not sure about the word in
English.

* The particular details for the GMP decision.

AND YET OTHER QUESTIONS

* What is the intended usage, or in other words, the usefulness of the
*BooleanArrays ?

I'm somewhat puzzled, because there is no API for using these boolean arrays
(a la Bit::Vector for example)

* If it's just a kind of storage, I can go on and implement it with a
custom, simple and small implementation, but I've still 2 solutions for
Resizables :
- either grow smartly only on the right (push, pop), an alloc/copy when
changes are needed on the left (that saves on INTVAL attribute)
- allocate a third INTVAL attribute on the heap, and grows smartly in both
directions

Thank you very much for your attention

Karl Forner

Jerry Gay

unread,
Oct 9, 2006, 11:17:56 AM10/9/06
to Karl Forner, Internals List
On 10/9/06, Karl Forner <karl....@gmail.com> wrote:
> Hi,
>
> It's not that easy to contribute to parrot development.
> I got into that by picking a TODO task about *BooleanArrays, that seemed
> appropriate for a Parrot newbie that
> knows a bit about algorithmics and Data structures.
>
thank you for your enthusiasm, and apologies for our lack of prompt
response. we'll work on correcting this (and i'll start now,) as it
would be a shame to lose a valuable contributor due to our inaction.

> Answering one of my mail, Bernhard raised the question of using a common
> implementation for strings, boolean arrays.
> And that maybe this implementation could be borrowed from the Perl5
> Bit::Vector library.
>

yes, a common implementation would be wonderful, but any core
committer would be happy to apply a patch of a working implementation.
there's no need to optimize this prematurely--there will be plenty of
time for that later, when the core of parrot is fully implemented, and
we're closer to release.

> It reminded me of something I read on this list, about the GMP library.
> So I checked the GMP website, ok looks great.
> I've also noted that there are some GMP-based implementations and GMP stuff
> in Parrot, and a GMP test.
>
> But a priori not a word in the specifications and the design documents.
> So I tried to track all the GMP related threads, and that's not that easy,
> for instance there does not seem to be a "search" feature on the nntp
> archive. I tried using some news readers then found my happiness with Google
> Groups (always Google). But there's also some materials in the blogs for
> example.
>
> So what did I found, among other stuff ?
>

[skip to the point :) ]

> SO MY POINT IS:
>
> 1) it seems that a decision has been made, but that it not written anywhere,
> and at least not on the parrot site.
> This decision is, in my understanding, to use an internal fall-back poor
> man's implementation.
>
> 2) Nor could I find the rationale for that decision. I've read some IMHO
> good arguments for including or for linking, but not a definitive summary,
> because from the last stuff I read, it seems that the Licensing issues are
> not blocking
>

(addressing 1 and 2): parrot's goal of a virtual machine that runs
everywhere perl5 runs makes it difficult to use external libraries,
which are usually not nearly as portable. i don't know specifics of
gmp's portability, so i can't comment on whether it's an appropriate
solution. this decision applies to unicode as well; the current icu
implementation is there to get something working, the final
implementation will likely be homegrown.

> 3) I spent more time trying to figure out the right thing to do than in my
> opinion coding something useful.
>
> WHAT I'D LIKE:
>
> * Some place, in the docs/ part of the parrot website, where that kind of
> decision is recorded, along with pointers to relevant information.
> A kind of proceedings, or critical review, I'm not sure about the word in
> English.
>

a decision like that is recorded in the parrot design documents.
unfortunately, the document you require is either in draft, or
non-existant. this must be fixed, and *is* on the TODO list.

> * The particular details for the GMP decision.
>

i believe i've outlined the general direction above. to be clear:
external library usage is fine, if there's an external library
available on the system. if not, a fallback implementation is
required. feel free to start your effort either way.

> AND YET OTHER QUESTIONS
>
> * What is the intended usage, or in other words, the usefulness of the
> *BooleanArrays ?
>

i see boolean arrays used as bit vectors. using an efficient storage
mechanism, offering useful bit-twiddling operations, and operating on
contained data as quickly as possible. that's waving my hands
somewhat, and i don't know if it helped.

> I'm somewhat puzzled, because there is no API for using these boolean arrays
> (a la Bit::Vector for example)
>

the design document for base pmcs is unfinished, and way out of date.
it's on allison's list, but right now she's working on exceptions and
i/o.

> * If it's just a kind of storage, I can go on and implement it with a
> custom, simple and small implementation, but I've still 2 solutions for
> Resizables :
> - either grow smartly only on the right (push, pop), an alloc/copy when
> changes are needed on the left (that saves on INTVAL attribute)
> - allocate a third INTVAL attribute on the heap, and grows smartly in both
> directions
>

my advice: do whatever seems easiest. extend/refactor as needed.
document your decisions to benefit future coders. note: i don't always
follow my own advice :)

> Thank you very much for your attention
>

you're quite welcome.
~jerry

Leopold Toetsch

unread,
Oct 9, 2006, 2:05:57 PM10/9/06
to perl6-i...@perl.org
Am Montag, 9. Oktober 2006 16:26 schrieb Karl Forner:
> AND YET OTHER QUESTIONS
>
> * What is the intended usage, or in other words, the usefulness of the
> *BooleanArrays ?

A *BooleanArray *does* array[1] and it's storage size is one bit per item.

[1] the current array interface isn't much more than:

Fixed:
ar = 1e9 # fill it with 0
b = ar[idx] # get bit
ar[idx] = b # set bit
delete, exists

Resizable additionally:
b = {pop,shift} ar
{push,unshift} ar, b
splice

To me it doesn't make much sense to provide all possible conversions from/to
num & string, PMC is debatable.

For usage see e.g.: examples/shootout/nsieve*.pir

> I'm somewhat puzzled, because there is no API for using these boolean
> arrays (a la Bit::Vector for example)

We don't have an array API yet, nor a pdd. But some methods like sort() are
implemented for some arrays. fill() aka memset() would be another candidate.
And of course more on demand.

> * If it's just a kind of storage, I can go on and implement it with a
> custom, simple and small implementation, but I've still 2 solutions for
> Resizables  :
>   - either grow smartly only on the right (push, pop), an alloc/copy when
> changes are needed on the left (that saves on INTVAL attribute)
>   - allocate a third INTVAL attribute on the heap, and grows smartly in
> both directions

You can provide smart growing in both directions with the mentioned strategy
with just 2 int_val fields.

> Thank you very much for your attention
>
> Karl Forner

leo

Reply all
Reply to author
Forward
0 new messages