5

I'm writing a library¹ in F# that provides some bitwise operations, and I want to make sure as many of my functions as possible are inline let bindings with static type parameters (this allows me to write one function and use it for int16, int32, and maybe even bignum with little overhead). This route will certainly fail to work at some point. Some of the functionality provided by said library is somewhat complicated.

¹Note: I'm aware of the issues of exposing inline let bindings via a public interface.

However, I want to stretch this to the furthest extent it can go. Right now, I'm trying to write the population count algorithm in this form, and I'm facing a problem. I'm not sure how to encode the masks, e.g. 0x3333..., that appear in these algorithms. I can get around shift constants and similar using some extra bit trickery.

Is there any trick I can use, whether via F#'s type inference and static type parameters, or via bit-twiddling, to write the algorithm the way I want? Is there any way I can encode these sorts of constants in the statically generic function?

A more vague question: are there some specific things I can rely on to utilize static type parameters to their fullest, especially in the context of numerics? For example, I heavily use GenericOne and GenericZero. Are there more things like this, that I might have missed?

Guy Coder
  • 24,501
  • 8
  • 71
  • 136
GregRos
  • 8,667
  • 3
  • 37
  • 63
  • 2
    Regarding resources, one useful trick is to define generic numerals so that you can write i.e. `42G` (see http://stackoverflow.com/questions/4732672/how-to-write-a-function-for-generic-numbers). I also wrote an article with some more information, but I think you probably won't find much new there (see http://tomasp.net/blog/fsharp-generic-numeric.aspx). – Tomas Petricek Oct 22 '12 at 17:40
  • Using the generic numeric literal, you can write i.e. `let inline shift a = (a &&& 8G) <<< 2`, but I suppose that is not the answer to your question (because you could do that with `GenericOne`). So, do you have any specific more complex example where the direct approach does not work for you? – Tomas Petricek Oct 22 '12 at 17:43
  • 3
    `0x33...` is `'signedtype'.MaxValue / 5 * 2 + 1`, does that help? – harold Oct 22 '12 at 17:53
  • @harold at first I didn't think it helped, but... hmm... it actually does, sort of. You've given me a terrific idea. – GregRos Oct 22 '12 at 18:06

1 Answers1

5

First, you can use numeric literals to avoid ugly uses of GenericOne and GenericZero. Here is a brief example:

module NumericLiteralG = begin
  let inline FromZero() = LanguagePrimitives.GenericZero
  let inline FromOne() = LanguagePrimitives.GenericOne
  let inline FromInt32 (n:int) =
        let one : ^a = FromOne()
        let zero : ^a = FromZero()
        let n_incr = if n > 0 then 1 else -1
        let g_incr = if n > 0 then one else (zero - one)
        let rec loop i g = 
            if i = n then g
            else loop (i + n_incr) (g + g_incr)
        loop 0 zero 
end

// Usage
let inline ten() = 10G
ten() + 1
ten() + 2L

Second, F# doesn't seem to support generic hexa numeric literals. One trick is to use double backticks so that you have indicative names:

let inline shift x = 
    let ``0x33333333G`` = 858993459G
    ((x >>> 2) &&& ``0x33333333G``) + (x &&& ``0x33333333G``)

// Usage
shift 20
shift 20L
shift 20uy

There are a few nice questions on SO about numeric literals. I give some references in case you go that route:

Community
  • 1
  • 1
pad
  • 41,040
  • 7
  • 92
  • 166
  • That's interesting. I'll read into numeric literals like these, and also look into the SO questions you mentioned. I'd like to point out though, that in general, there is no problem with hex numeric literals in F#. Maybe there is an issue with you use `G` literals... – GregRos Oct 22 '12 at 17:47
  • Yes, because `0x33333333I` doesn't work (which makes sense), I don't expect `0x33333333G` to work either. – pad Oct 22 '12 at 17:49
  • Thanks :) This answer helped me a lot. Also, I'd like to point out that the algorithm for `FromInt` isn't very efficient. [Here](https://snipt.net/GregRos/-1040/) is a better implementation, though it only works for integers. – GregRos Oct 23 '12 at 18:10