Back to Questions
2.0k
views3
comments
Parameterising a function over all integral types
f#

Hi,

I have some code which I parameterize over a record of functions. In one application I would like to use the basic integer types while for another a specialized version based on arrays.

I have something working but it's not quite as neat as I would like it to be. Here's the type I am using for the parameterization:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

type 'a SimData = 


{


  create : int -> 'a;


  set_zero : 'a -> int -> unit;


  set_const : 'a -> string -> unit;


  to_int : 'a -> int;


  copy : 'a -> 'a -> int -> unit;


  mask : 'a -> int -> unit;


  sign_extend : 'a -> int -> unit;


  unop : unop_t -> 'a -> 'a -> int -> unit;


  shop : shop_t -> 'a -> 'a -> int -> int -> unit;


  binop : binop_t -> 'a -> 'a -> 'a -> int -> int -> unit;


  sel : 'a -> 'a -> int -> int -> unit;


}

For a UInt32 type I can implement this as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

let simDataUint32 = 
{
  create = (fun n -> ref 0ul);
  set_zero = (fun a n -> a := 0ul);
  set_const = (fun data s ->
    for i = 0 to String.length s - 1 do
      data := (!data lsl 1) + (if s.[ i ] = '1' then 1ul else 0ul)
    done);
  to_int = (fun a -> UInt32.to_int !a);
  copy = (fun a b w -> a := !b);
  mask = (fun a w -> a := !a land (lnot ((lnot 0ul) lsl w)));
  sign_extend = (fun a w -> if 0ul = (!a land (1ul lsl (w-1))) then a := !a lor (0xFFFFFFFFul lsl w));
  unop = (fun op r a w -> r := lnot !a);
  binop = (fun op r a b wa wb -> 
    r := match op with
      | B_add -> !a + !b
      | B_sub -> !a - !b
      | B_mulu -> !a * !b
      | B_muls -> 
        let se a w = if 0ul = (a land (1ul lsl (w-1))) then a lor (0xFFFFFFFFul lsl w) else a in
        (se !a wa) * (se !b wb)
      | B_and -> !a land !b
      | B_or -> !a lor !b
      | B_xor -> !a lxor !b
      | B_eq -> if !a <> 0ul then 1ul else 0ul
      | B_lt -> if !a < !b then 1ul else 0ul
      | B_cat -> !b lor (!a lsl wb)); 
  shop = (fun op r a b w -> 
    r := match op with
      | S_sll -> !a lsl b
      | S_srl -> !a lsr b
      | S_sra -> 
        let se d w = 
          let sb = d land (1ul lsl (w-1)) in
          if sb <> 0ul then d lor ((lnot 0ul) lsl w) else d in
        (se !a w) asr b); 
  sel = (fun r a hi lo -> r := (!a lsr lo)); 
}

Currently I have this repeated for int, uint32 and uint64 with minor modifications.

I thought I would be able to do the following to tidy this up:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

let simDataSimpleType zero one to_int = 
  let mask = lnot zero in
  let sign_extend a w = if zero = (a land (one lsl (w-1))) then a lor (mask lsl w) else a in
  {
    create = (fun n -> ref zero);
    set_zero = (fun a n -> a := zero);
    set_const = (fun data s ->
      for i = 0 to String.length s - 1 do
        data := (!data lsl 1) + (if s.[ i ] = '1' then one else zero)
      done);
    to_int = (fun a -> to_int !a);
    copy = (fun a b w -> a := !b);
    mask = (fun a w -> a := !a land (lnot (mask lsl w)));
    sign_extend = (fun a w -> a := sign_extend !a w);
    unop = (fun op r a w -> r := lnot !a);
    binop = (fun op r a b wa wb -> 
      r := match op with
        | B_add -> !a + !b
        | B_sub -> !a - !b
        | B_mulu -> !a * !b
        | B_muls -> (sign_extend !a wa) * (sign_extend !b wb)
        | B_and -> !a land !b
        | B_or -> !a lor !b
        | B_xor -> !a lxor !b
        | B_eq -> if !a <> zero then one else zero
        | B_lt -> if !a < !b then one else zero
        | B_cat -> !b lor (!a lsl wb)); 
    shop = (fun op r a b w -> 
      r := match op with
        | S_sll -> !a lsl b
        | S_srl -> !a lsr b
        | S_sra -> 
          let se d w = 
            let sb = d land (one lsl (w-1)) in
            if sb <> zero then d lor ((lnot zero) lsl w) else d in
          (se !a w) asr b); 
    sel = (fun r a hi lo -> r := (!a lsr lo)); 
  }

let simDataInt = simDataSimpleType 0 1 (fun x -> x)
let simDataUInt32 = simDataSimpleType 0ul 1ul UInt32.to_int
let simDataUInt64 = simDataSimpleType 0UL 1UL UInt64.to_int

However, the simDataUInt32 and simDataUInt64 applications dont work. It seems the type of the record generated by simDataSimpleType is implicitly an "int" rather that something that can be specialized to any integral type.

Is something like this possible in F#?

Cheers,

Andy

.

What are you trying to do can be done quite well using <i>type classes<i>. First-order type classes can be emulated in F# using interfaces. First write SimData as an interface type 'a SimData = interface abstract create : int -> 'a abstract binop : binop_t -> 'a -> 'a -> 'a -> int -> int -> unit // ... end F# already has some "type class" interfaces for numeric types in Microsoft.FSharp.Math.Types, in particular INumeric. Now it is possible to write a function that produces an instance of SimData given an instance of INumeric. E.g., let f (num : 'a INumeric) = { new ('a ref) SimData with create n = ref num.Zero and binop op r a b wa wb = r := match op with | B_add -> num.Add (!a, !b) // ... } Of course for your problem you need more operations than the INumeric type class defines (e.g., bitwise operations) so you could extend INumeric with a sub-interface that supports these operations. You can build instances of SimData like so (N.B. I think the typeof function is deprecated but fslib is still using it for this function getNumericAssociation) let getSimData () = getNumericAssociation (typeof () : 'a typ) |> Option.get |> f let simDataInt32 : (Int32 ref) SimData = getSimData () let simDataUInt64 : (UInt64 ref) SimData = getSimData ()

By on 9/26/2006 8:17 PM ()

Going back to the original code, the problem stems from the fact that overloaded operators are resolved statically in F#. That is, 

1
2
3
4
5
6
7
8

 

let simDataSimpleType zero one = 
  let mask = ~~~ zero in 
  let sign_extend a w = if zero = (a &&& (one <<< (w-1))) then a ||| (mask <<< w) else a in
  (mask,sign_extend)

does not give rise to a function that is generic over the type of integers used. This is why Greg passes in a dictionary of operations that represents the implementation of not only zero and one, but also all related operations such as <<< and &&&.

(nb. I've used the F# symbolic names for these operators since I find it many times clearer than the OCaml names, which we only recommend for use when cross-compiling F# code).

Don

By on 9/26/2006 11:03 PM ()

Thanks for the info.

Looking back at the manual I think it pretty much says what has been summerized here, though I must say I find it rather heavy going.

V. much looking forward to one of those f# books that are in the pipeline which I've no doubt will make all this much clearer.

Cheers,

Andy

By on 9/28/2006 6:07 AM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper