SRFI-151 (Bitwise Operations) Implementation

SRFI-151 (Bitwise Operations) Implementation

[Frank Terbeck]

Hey Guilers!

Since I got  a project that uses (potentially large)  integers to encode
bits in registers,  I was looking at  SRFIs that deal with  that type of
domain. The most recent entry is SRFI-151, which is in final status.

Since Guile currently doesn't have an implementation of this SRFI, I fi-
gured I might as well add one.

I tried to reuse as many facilities  that are already in Guile to get to
a complete implementation. So it reuses  stuff from the R6RS bitwise li-
brary, as well as SRFI-60 (which is titled “Integers as Bits”) and other
functions from Guile's core.

SRFI-151 has one  API that returns a SRFI-121 generator¹  to traverse an
integer. Since Guile currently  doesn't have a SRFI-121 implementation²,
this function³ is missing from this implementation.

The implementation can be found here:     https://gitlab.com/ft/srfi-151

The test-suite  reproduces the examples  from the specification,  plus a
couple of additional ones.  Maybe this is useful for someone.


Regards, Frank

¹ http://srfi.schemers.org/srfi-121/srfi-121.html
² https://www.mail-archive.com/guile-devel@gnu.org/msg14950.html
³ make-bitwise-generator

-- 
In protocol design, perfection has been reached not when there is
nothing left to add, but when there is nothing left to take away.
                                                  -- RFC 1925

Re: SRFI-151 (Bitwise Operations) Implementation

[Zelphir Kaltstahl]

Hello Frank,

I think I might find good use for this library in one of my projects!
Thanks for sharing!

Regards,
Zelphir

On 09.01.2020 05:28, Frank Terbeck wrote:
> Hey Guilers!
>
> Since I got  a project that uses (potentially large)  integers to encode
> bits in registers,  I was looking at  SRFIs that deal with  that type of
> domain. The most recent entry is SRFI-151, which is in final status.
>
> Since Guile currently doesn't have an implementation of this SRFI, I fi-
> gured I might as well add one.
>
> I tried to reuse as many facilities  that are already in Guile to get to
> a complete implementation. So it reuses  stuff from the R6RS bitwise li-
> brary, as well as SRFI-60 (which is titled “Integers as Bits”) and other
> functions from Guile's core.
>
> SRFI-151 has one  API that returns a SRFI-121 generator¹  to traverse an
> integer. Since Guile currently  doesn't have a SRFI-121 implementation²,
> this function³ is missing from this implementation.
>
> The implementation can be found here:     https://gitlab.com/ft/srfi-151
>
> The test-suite  reproduces the examples  from the specification,  plus a
> couple of additional ones.  Maybe this is useful for someone.
>
>
> Regards, Frank
>
> ¹ http://srfi.schemers.org/srfi-121/srfi-121.html
> ² https://www.mail-archive.com/guile-devel@gnu.org/msg14950.html
> ³ make-bitwise-generator
>

Re: SRFI-151 (Bitwise Operations) Implementation

[Linus Björnstam]

I have a port of the SRFI code as well, using renaming of guile and srfi-60 procedures as necessary. It has the make-bitwise-generator from srfi-151.

https://bitbucket.org/bjoli/guile-srfi-151/

I will move all that code to sourcehut whenever I have the time since bitbucket is shutting down HG support.

It passes all of John's tests.

-- 
  Linus Björnstam

On Thu, 9 Jan 2020, at 05:28, Frank Terbeck wrote:
> Hey Guilers!
> 
> Since I got  a project that uses (potentially large)  integers to encode
> bits in registers,  I was looking at  SRFIs that deal with  that type of
> domain. The most recent entry is SRFI-151, which is in final status.
> 
> Since Guile currently doesn't have an implementation of this SRFI, I fi-
> gured I might as well add one.
> 
> I tried to reuse as many facilities  that are already in Guile to get to
> a complete implementation. So it reuses  stuff from the R6RS bitwise li-
> brary, as well as SRFI-60 (which is titled “Integers as Bits”) and other
> functions from Guile's core.
> 
> SRFI-151 has one  API that returns a SRFI-121 generator¹  to traverse an
> integer. Since Guile currently  doesn't have a SRFI-121 implementation²,
> this function³ is missing from this implementation.
> 
> The implementation can be found here:     https://gitlab.com/ft/srfi-151
> 
> The test-suite  reproduces the examples  from the specification,  plus a
> couple of additional ones.  Maybe this is useful for someone.
> 
> 
> Regards, Frank
> 
> ¹ http://srfi.schemers.org/srfi-121/srfi-121.html
> ² https://www.mail-archive.com/guile-devel@gnu.org/msg14950.html
> ³ make-bitwise-generator
> 
> -- 
> In protocol design, perfection has been reached not when there is
> nothing left to add, but when there is nothing left to take away.
>                                                   -- RFC 1925
> 
>

Re: SRFI-151 (Bitwise Operations) Implementation

[Frank Terbeck]

Hi Linus!

Linus Björnstam wrote:
> I have a port of the SRFI code as well, using renaming of guile and srfi-60
> procedures as necessary.

I see! I did mine from scratch, while reading the spec.


> It has the make-bitwise-generator from srfi-151.

Interesting. I thought  the generators were part of  some disjoint type.
After seeing  the iterator you  implemented, I  actually took a  look at
SRFI-121 and indeed: “They are just procedures that conform to a calling
convention, so you can construct a generator with lambda.”

I guess I'll do the same for now! Thanks for letting me know. :)


Regards, Frank

Re: SRFI-151 (Bitwise Operations) Implementation

[Linus Björnstam]

Your bitwise-nand etc takes more arguments than they have to. They are 2-argument procedures according to the spec, which gives you better performance than the apply-dance you are doing now. Maybe have a bitwise-nand and a bitwise-nand*?
-- 
  Linus Björnstam

On Thu, 9 Jan 2020, at 10:10, Frank Terbeck wrote:
> Hi Linus!
> 
> Linus Björnstam wrote:
> > I have a port of the SRFI code as well, using renaming of guile and srfi-60
> > procedures as necessary.
> 
> I see! I did mine from scratch, while reading the spec.
> 
> 
> > It has the make-bitwise-generator from srfi-151.
> 
> Interesting. I thought  the generators were part of  some disjoint type.
> After seeing  the iterator you  implemented, I  actually took a  look at
> SRFI-121 and indeed: “They are just procedures that conform to a calling
> convention, so you can construct a generator with lambda.”
> 
> I guess I'll do the same for now! Thanks for letting me know. :)
> 
> 
> Regards, Frank
>

Re: SRFI-151 (Bitwise Operations) Implementation

[Frank Terbeck]

Linus Björnstam wrote:
> Your bitwise-nand etc takes more arguments than they have to. They are
> 2-argument procedures according to the spec, which gives you better performance
> than the apply-dance you are doing now. Maybe have a bitwise-nand and a
> bitwise-nand*?

Yeah, I did that on purpose. The performance argument is probably valid,
though. However,  I don't want  to extend the API.  Maybe I'll put  in a
case-lambda there.

Thanks for taking a look!


Regards, Frank
-- 
In protocol design, perfection has been reached not when there is
nothing left to add, but when there is nothing left to take away.
                                                  -- RFC 1925

Re: SRFI-151 (Bitwise Operations) Implementation

[John Cowan]

On Thu, Jan 9, 2020 at 7:55 AM Frank Terbeck <ft@bewatermyfriend.org> wrote:

Linus Björnstam wrote:
> > Your bitwise-nand etc takes more arguments than they have to. They are
> > 2-argument procedures according to the spec, which gives you better
> performance
> > than the apply-dance you are doing now. Maybe have a bitwise-nand and a
> > bitwise-nand*?
>
> Yeah, I did that on purpose. The performance argument is probably valid,
> though. However,  I don't want  to extend the API.  Maybe I'll put  in a
> case-lambda there.
>

The reason bitwise-nand and friends have only two arguments (and this comes
from Olin's original) is that they aren't associative:  it's ambiguous
whether (bitwise-nand a b c) means (bitwise-nand (bitwise-nand a b) c) or
(bitwise-nand a (bitwise-nand b c)), and these are *not* equivalent.
Rather than choosing one of these arbitrarily, users have to say what they
mean.



John Cowan          http://vrici.lojban.org/~cowan        cowan@ccil.org
Any sufficiently-complicated C or Fortran program contains an ad-hoc,
informally-specified bug-ridden slow implementation of half of Common Lisp.
        --Greenspun's Tenth Rule of Programming (rules 1-9 are unknown)

Re: SRFI-151 (Bitwise Operations) Implementation

[Frank Terbeck]

John Cowan wrote:
[...]
> The reason bitwise-nand and friends have only two arguments (and this comes
> from Olin's original) is that they aren't associative:  it's ambiguous
> whether (bitwise-nand a b c) means (bitwise-nand (bitwise-nand a b) c) or
> (bitwise-nand a (bitwise-nand b c)), and these are *not* equivalent.
> Rather than choosing one of these arbitrarily, users have to say what they
> mean.

Well, how about that. :)

That is a great argument. I'll make those two binary then, as the spec
suggests. Thanks!


Regards, Frank
-- 
In protocol design, perfection has been reached not when there is
nothing left to add, but when there is nothing left to take away.
                                                  -- RFC 1925

Re: SRFI-151 (Bitwise Operations) Implementation

[Linus Björnstam]

Hey again!

I just re-read my message and noticed it could come off as somewhat dismissive. Ah, the joys of not having English as a first language while being a tired father :)

I looked through your code. It is nicer than mine, but why did you chose to not just re-export bindings that are available in srfi60? I don't know the practical implications of not doing so, but I read in another thread of potential cross-module Inlining, and helping that optimization in every way you can would be a great thing for low level stuff like bit fiddling :)

If you want you can just copy it from my module declaration. You can have it, no attribution required. Or you could just do the renaming in the #:re-export clause. 



-- 
  Linus Björnstam

On Thu, 9 Jan 2020, at 13:52, Frank Terbeck wrote:
> Linus Björnstam wrote:
> > Your bitwise-nand etc takes more arguments than they have to. They are
> > 2-argument procedures according to the spec, which gives you better performance
> > than the apply-dance you are doing now. Maybe have a bitwise-nand and a
> > bitwise-nand*?
> 
> Yeah, I did that on purpose. The performance argument is probably valid,
> though. However,  I don't want  to extend the API.  Maybe I'll put  in a
> case-lambda there.
> 
> Thanks for taking a look!
> 
> 
> Regards, Frank
> -- 
> In protocol design, perfection has been reached not when there is
> nothing left to add, but when there is nothing left to take away.
>                                                   -- RFC 1925
>

Re: SRFI-151 (Bitwise Operations) Implementation

[Frank Terbeck]

Hi,

Linus Björnstam wrote:
> I just re-read my message and noticed it could come off as somewhat dismissive.
> Ah, the joys of not having English as a first language while being a tired
> father :)

Didn't strike me particularly as such. So, all is good.


> I looked through your code. It is nicer than mine, but why did you chose to not
> just re-export bindings that are available in srfi60? I don't know the

I actually didn't think about it too  much. I was more focused on making
the implementation  match the  order used in  the specification  and add
documentation to  all API so  it can be  followed in a  straight forward
manner.


> practical implications of not doing so, but I read in another thread of
> potential cross-module Inlining, and helping that optimization in every way you
> can would be a great thing for low level stuff like bit fiddling :)

Sure. I must admit that I haven't  really played a lot with Guile's com-
piler and  optimiser. I wonder what  the impact would be  here. Remember
the subject of said thread?


Regards, Frank
-- 
In protocol design, perfection has been reached not when there is
nothing left to add, but when there is nothing left to take away.
                                                  -- RFC 1925

Re: SRFI-151 (Bitwise Operations) Implementation

[Linus Björnstam]

To clarify: guile does not yet do cross module inlining. It was mentioned as a potential thing in the thread about native guile SHA2(?) implementation. As such there is nothing to learn about it. Potential heuristics and how to make it clear to the optimizer what is simple re-exports I leave to Andy, Ludo, and Mark, but I feel safe saying that #:re-export is the safest bet.

-- 
  Linus Björnstam

On Fri, 10 Jan 2020, at 06:15, Frank Terbeck wrote:
> Hi,
> 
> Linus Björnstam wrote:
> > I just re-read my message and noticed it could come off as somewhat dismissive.
> > Ah, the joys of not having English as a first language while being a tired
> > father :)
> 
> Didn't strike me particularly as such. So, all is good.
> 
> 
> > I looked through your code. It is nicer than mine, but why did you chose to not
> > just re-export bindings that are available in srfi60? I don't know the
> 
> I actually didn't think about it too  much. I was more focused on making
> the implementation  match the  order used in  the specification  and add
> documentation to  all API so  it can be  followed in a  straight forward
> manner.
> 
> 
> > practical implications of not doing so, but I read in another thread of
> > potential cross-module Inlining, and helping that optimization in every way you
> > can would be a great thing for low level stuff like bit fiddling :)
> 
> Sure. I must admit that I haven't  really played a lot with Guile's com-
> piler and  optimiser. I wonder what  the impact would be  here. Remember
> the subject of said thread?
> 
> 
> Regards, Frank
> -- 
> In protocol design, perfection has been reached not when there is
> nothing left to add, but when there is nothing left to take away.
>                                                   -- RFC 1925
>