16Typeclasses and provisos

The symbol + works for Integer, UInt#(8), and Int#(16), but those types do not share one adder implementation. BSV uses typeclasses to name groups of overloaded operations, instances to supply the implementation for a particular type, and provisos to state which implementations a generic definition needs. All three are handled during type checking and elaboration; the running circuit contains no logic for choosing an instance. This chapter covers §8 of the BSV Language Reference Guide and the polymorphic types, provisos, and numeric-type functions of its §4. You need widths, pack, and unpack from Types, widths and explicit conversion, enums, structs, and deriving from User-defined types, and the way a declared type selects a Literal instance from Variables, loops, and the context of a literal.

1. Overloading and typeclasses

1.1 Polymorphism versus overloading

The two ideas look alike but are different.

A typeclass is a name for a group of overloaded operations. Eq groups == and /=, Bits groups pack and unpack, and Arith groups arithmetic such as +, -, and *. An instance defines how one particular type implements the operations of a typeclass.

1.2 Type variables

A polymorphic type uses a type variable in place of a concrete type. Each use settles the variable to exactly one type.

Vector#(n, t)   // n elements, all of the same type t
List#(List#(b)) // a list whose elements are lists of b

A type variable starts with a lowercase letter, like the n in Bit#(n) and the t above, and is settled by the context where it is used. Nothing about a type variable is decided while the circuit runs.

1.3 What happens at compile time

When you call a definition that carries provisos, bsc resolves instances in these steps:

1. Infer type variables and widths from the call's arguments and result.
2. Collect the requirements introduced by overloaded operations and provisos.
3. Match each requirement with an instance or a known numeric relation.
4. If a matched instance has requirements of its own, check those too.
5. Specialize the definition with the chosen implementations and continue elaboration.

None of this is a rule guard or a simulation event. No tag, multiplexer, or virtual call is added to the circuit. When the instances are found, only the chosen implementations contribute hardware; when one is missing, compilation stops before simulation.

2. Declaring a typeclass

2.1 Typeclass syntax

Syntax

typeclass ClassName#(type typeVariable);
  memberDeclaration;
  ...
endtypeclass

typeclass Describe#(type t);
  function Bit#(4) code(t value);
endtypeclass

Members may be functions, modules, or plain values. A typeclass declaration contains no implementation of its own.

2.2 Superclass requirements

Adding provisos to a typeclass declaration means every instance of that class must also satisfy another class.

Syntax

typeclass ClassName#(type t) provisos (SuperClass#(t));
  ...
endtypeclass

typeclass Ranked#(type t) provisos (Eq#(t));
  function Bit#(2) rank(t x);
endtypeclass

Any type with a Ranked instance must also have an Eq instance. When bsc resolves instances, it follows these requirements transitively.

3. Declaring instances

3.1 Instance syntax

An instance defines every member of a typeclass for one particular type.

Syntax

instance ClassName#(ConcreteType);
  memberDefinition;
  ...
endinstance

instance Describe#(Bool);
  function Bit#(4) code(Bool value);
    return value ? 4'h1 : 4'h0;
  endfunction
endinstance

3.2 Defining operator members

Operators such as == are defined with escaped identifiers: names that start with a backslash and end with whitespace. The two members of Eq are \== and \/=.

typedef struct { Bit#(4) v; } Code deriving (Bits);

instance Eq#(Code);
  function Bool \== (Code a, Code b) = a.v == b.v;
  function Bool \/= (Code a, Code b) = a.v != b.v;
endinstance

Note. The space after \== is part of BSV syntax: it ends the identifier. Write \==(Code a, ...) without it and the parenthesis is swallowed into the identifier, giving parse error P0005.

4. Constraining polymorphic functions with provisos

4.1 Proviso syntax

If you do not know what t is, you also do not know which operations t supports. A polymorphic function that uses an overloaded operation must therefore declare, with provisos, that it only accepts types providing that operation.

Syntax

function ReturnType name(arguments) provisos (Class#(typeVariable), ...);
  ...
endfunction

function Bool same(t a, t b) provisos (Eq#(t));
  return a == b;
endfunction

Eq#(t) does not create comparison for every type. It is a contract: each call of same must pass a type that already has an Eq instance. Because of that contract, the body may use == while staying generic.

A proviso can tie a width to the type variable as well:

function Bit#(n) bitsOf(t x) provisos (Bits#(t, n));
  return pack(x);
endfunction

Bits#(t, n) means "t has an n-bit representation, so pack and unpack are available". Leave it out and nothing justifies pack(x): compilation fails with T0030, and the message lists Bits#(t, n) as the needed proviso.

4.2 Example: one function, many types

bitsOf in Polymorphism.bsv accepts any type with a Bits instance and returns its bit representation. The rule calls it once each with a Bool, a UInt#(3), and a Bit#(4).

Predict before you run. What do t and n become at each call, and how many bits does each line show?

package Polymorphism;

// No concrete type here. The proviso supplies pack and names the width n.
function Bit#(n) bitsOf(t x) provisos (Bits#(t, n));
  return pack(x);
endfunction

(* synthesize *)
module mkTop(Empty);

  rule show;
    Bool     flag   = True;
    UInt#(3) reading = 5;
    Bit#(4)  nibble = 4'b1010;

    // Each call site settles t on its own, and the width follows from it.
    $display("Bool     -> %b", bitsOf(flag));
    $display("UInt#(3) -> %b", bitsOf(reading));
    $display("Bit#(4)  -> %b", bitsOf(nibble));
    $finish(0);
  endrule

endmodule

endpackage

Check the result.

There is one definition, but t and n are settled separately at every call. The width from the first call does not carry over to the next.

Try it yourself. Pass an Integer to bitsOf. Integer has no Bits instance, so compilation fails with T0031, reporting that no Bits#(Integer, ...) instance exists. Editing the function body cannot fix that; the argument must have a bit representation.

4.3 Example: the argument type picks the instance

PriorityInstance.bsv defines a Priority typeclass, two instances, and a polymorphic function requestPriority with a proviso. Read it in this order:

1. The Priority declaration and its member priorityOf
2. The Bool instance and the RequestKind instance
3. provisos (Priority#(value_type)) on requestPriority
4. The two calls in show

Predict before you run.

1. Which instance does each of requestPriority(Write) and requestPriority(True) use?
2. What priority does each line print?
3. Can the instance choice change while the circuit is running?

package PriorityInstance;

typedef enum { Reset, Read, Refresh, Write } RequestKind
  deriving (Bits, Eq, FShow);

// Priority groups one overloaded operation. Every instance must
// implement priorityOf for its own type.
typeclass Priority#(type value_type);
  function Bit#(2) priorityOf(value_type value);
endtypeclass

// Two concrete instances give the same operation name different
// type-specific behavior.
instance Priority#(Bool);
  function Bit#(2) priorityOf(Bool value);
    return value ? 2'd3 : 2'd0;
  endfunction
endinstance

instance Priority#(RequestKind);
  function Bit#(2) priorityOf(RequestKind value);
    case (value)
      Refresh: return 2'd0;
      Read:    return 2'd1;
      Write:   return 2'd2;
      Reset:   return 2'd3;
    endcase
  endfunction
endinstance

// One polymorphic body uses whichever Priority instance its argument
// type selects.
function Bit#(2) requestPriority(value_type value)
  provisos (Priority#(value_type));
  return priorityOf(value);
endfunction

(* synthesize *)
module mkTop(Empty);
  rule show;
    $display("Write priority = %0d", requestPriority(Write));
    $display("True priority  = %0d", requestPriority(True));
    $finish(0);
  endrule
endmodule

endpackage

Check the result.

Each call was specialized to a different implementation at compile time. At runtime rule show simply performs operations that were already chosen; there is no circuit that selects an instance.

Try it yourself.

Changing the value keeps the same instance and changes only its result; changing the type changes which instance is needed.

5. Width-relation provisos

5.1 Stating relations between widths

Some typeclasses express equations between numeric types instead of supplying function bodies. A signature uses them to state how input and output widths relate. They relate numeric types, not run-time values.

Syntax

function Bit#(m) name(Bit#(n) x) provisos (Add#(n, k, m));

function Bit#(m) twice(Bit#(n) x) provisos (Mul#(n, 2, m));
  return {x, x};
endfunction

Receiving twice(3'b101) into a Bit#(6) fixes n = 3 and m = 6; Mul#(3, 2, 6) holds, and the result is 101101.

function Bit#(m) pad0101(Bit#(n) x) provisos (Add#(n, 4, m));
  return { x, 4'b0101 };
endfunction

Read this signature as a width equation: the result width m is four more than the argument width n.

Note. To compute a width inside a type, use type functions such as TAdd#(n, 1) or TMul#(n, 2). A proviso requires a relation as a condition; a type function builds the resulting type directly.

5.2 Example: a result width that follows the argument

WidthProviso.bsv of the types set calls pad0101 once with the 4-bit nibble and once with the 2-bit pair.

Predict before you run. What is m at each call, and on which side of the result does 0101 land?

package WidthProviso;

// The proviso pins m to n + 4, so the return width comes from the argument.
function Bit#(m) pad0101(Bit#(n) x) provisos (Add#(n, 4, m));
  return { x, 4'b0101 };
endfunction

(* synthesize *)
module mkTop(Empty);

  rule show;
    Bit#(4) nibble = 4'b1100;
    Bit#(2) pair   = 2'b11;

    // n is 4 on the first call and 2 on the second, so m is 8 and then 6.
    Bit#(8) widened = pad0101(nibble);
    Bit#(6) shorter = pad0101(pair);

    $display("pad0101(%b) = %b", nibble, widened);
    $display("pad0101(%b)   = %b", pair, shorter);
    $finish(0);
  endrule

endmodule

endpackage

Check the result.

In both results the argument takes the high bits and 0101 the low four.

Try it yourself.

The definition stays valid. The error belongs to the call, which asks for an m that cannot satisfy both Add#(2, 4, m) and m = 8.

5.3 Example: a fixed receiving width

appendTag in the WidthProviso.bsv of the typeclasses-and-provisos set appends a 4-bit tag to a value. Read the signature before the concatenation, then the receiving declaration Bit#(7) result in show.

Predict before you run.

1. What are n, the tag width, and m?
2. Which relation must bsc establish?
3. What is the 7-bit value of 101 followed by 1010, in hexadecimal?

package WidthProviso;

function Bit#(m) appendTag(Bit#(n) value, Bit#(4) tag)
  provisos (Add#(n, 4, m));
  return { value, tag };
endfunction

(* synthesize *)
module mkTop(Empty);
  rule show;
    Bit#(7) result = appendTag(3'b101, 4'ha);
    $display("tagged = %h", result);
    $finish(0);
  endrule
endmodule

endpackage

Check the result.

Try it yourself.

6. Turning numeric types into values

6.1 SizeOf and valueOf

Syntax

SizeOf#(Type)          // the type's bit width, as a numeric type
valueOf(numericType)   // a numeric type turned into an Integer value

Integer w = valueOf(SizeOf#(Bit#(12)));   // 12

stringOf does the same for string types, producing a String value. The spellings valueof/valueOf and stringof/stringOf are both accepted.

6.2 Example: printing type widths

TypeSize.bsv computes three widths with valueOf(SizeOf#(...)) and displays them. Read each expression from the inside out.

Predict before you run. How many bits do Bool, Bit#(12), and UInt#(5) occupy?

package TypeSize;

(* synthesize *)
module mkTop(Empty);

  rule show;
    // SizeOf#(T) is a type, not a number. valueOf brings it down to an Integer.
    $display("Bool     occupies %0d bit(s)", valueOf(SizeOf#(Bool)));
    $display("Bit#(12) occupies %0d bit(s)", valueOf(SizeOf#(Bit#(12))));
    $display("UInt#(5) occupies %0d bit(s)", valueOf(SizeOf#(UInt#(5))));
    $finish(0);
  endrule

endmodule

endpackage

Check the result.

$display could print these only because valueOf turned each numeric type from SizeOf into an Integer.

Try it yourself. Delete valueOf from one line and pass SizeOf#(Bool) directly. A type appears where an expression must go, so parsing fails with P0005.

7. Reading typeclass diagnostics

7.1 Diagnostic versus missing fact

Rewrite the type and proviso in an error message as a concrete requirement first. Similar-looking messages point to different missing facts and different fixes.

7.2 Same name, different cause

A requirement that still mentions a type variable, such as Priority#(t), usually means the generic definition itself is missing a proviso. A requirement with a concrete type, such as Priority#(UInt#(8)), means the type is already known and has no instance. Add#(3, 4, 8) is not ambiguous at all; it is a fully determined but false relation.

Bit#(4) y = 3;
Bit#(4) x = truncate(zeroExtend(y));   // T0035: the middle width is unknown

Nothing states the result width of zeroExtend, so the width between zeroExtend and truncate cannot be determined, and bsc reports T0035.

Apply the table to a generic function before you compile it.

function t largerOf(t a, t b);
  return (a > b) ? a : b;
endfunction

8. Hand-written Bits instances

8.1 The Bits typeclass

Bits#(value_type, width) ties a semantic type to one bit width and defines conversion in both directions.

Syntax

instance Bits#(Type, width);
  function Bit#(width) pack(Type value);
    ...
  endfunction
  function Type unpack(Bit#(width) bits);
    ...
  endfunction
endinstance

Knowing value_type fixes width, but not the other way round: UInt#(16) is 16 bits wide, yet many other types are 16 bits wide too.

8.2 When to write one yourself

deriving (Bits) numbers enum labels from 0 upward and lays out struct fields in the compiler's order. When that layout is fine, derive; when an external protocol or external hardware fixes different codes, write the instance yourself.

Note. A type without Bits is still legal, but it cannot be stored in a Reg or cross the interface of a separately synthesized module.

8.3 Example: a protocol encoding

Command in CustomBits.bsv does not derive Bits; its instance defines pack and unpack by hand. Read the two case statements as the two directions of one protocol table.

Predict before you run.

1. What does pack(Stop) print?
2. Which label does unpack(2'b10) produce?

package CustomBits;

// This enum does not derive Bits because the wire protocol fixes
// different codes.
typedef enum { Idle, Start, Stop } Command deriving (Eq, FShow);

instance Bits#(Command, 2);
  // pack maps semantic values to the protocol encoding.
  function Bit#(2) pack(Command value);
    case (value)
      Idle:  return 2'b01;
      Start: return 2'b10;
      Stop:  return 2'b11;
    endcase
  endfunction

  // unpack defines the reverse mapping. The unused code becomes Idle.
  function Command unpack(Bit#(2) bits);
    case (bits)
      2'b10:  return Start;
      2'b11:  return Stop;
      default: return Idle;
    endcase
  endfunction
endinstance

(* synthesize *)
module mkTop(Empty);
  rule show;
    Command decoded = unpack(2'b10);
    $display("Stop code = %b", pack(Stop));
    $display("10 means  = ", fshow(decoded));
    $finish(0);
  endrule
endmodule

endpackage

Check the result.

Type checking confirms only that both functions use two bits. It does not check that the two tables are inverses. Whether unpack(pack(c)) == c holds for every Command value c is something you must verify separately.

Try it yourself.

1. Change unpack(2'b10) to unpack(2'b00). The protocol never uses that code, so the default arm runs and the output shows Idle.
2. If you want an unused code to be an error instead of Idle, plain Command cannot express it. Representing both a valid command and a decode failure needs a tagged-union result type such as Maybe#(Command).

9. deriving and isomorphic wrappers

9.1 Instances you can derive

For enums, structs, and tagged unions, deriving generates instances with the language's standard behavior.

Combine them as in deriving (Bits, Eq, FShow). The runnable example for typedef and deriving is in User-defined types.

9.2 Isomorphic wrappers

A one-field struct or one-member tagged union carries the same information as its contents while remaining a distinct type; it is an isomorphic wrapper. BSV can derive the contents' instances for such a wrapper.

Syntax

typedef struct { InnerType field; } WrapperName deriving (..., Literal, Arith);

Literal gives the wrapper integer literals, and Arith gives it arithmetic, both borrowed from the inner type.

9.3 Example: integers with a unit

Credits in IsomorphicWrapper.bsv is a struct wrapping one UInt#(8) field. Read the deriving list on Credits first.

Predict before you run.

1. Can a literal be assigned directly, as in Credits first = 5;?
2. What are the type and value of first + second?

package IsomorphicWrapper;

// A one-field struct is isomorphic to its field type, so compatible
// instances can be derived through the wrapper.
typedef struct {
  UInt#(8) amount;
} Credits deriving (Bits, Eq, FShow, Literal, Arith);

(* synthesize *)
module mkTop(Empty);
  rule show;
    // Credits is distinct from UInt#(8), but literals and arithmetic
    // reuse the field's behavior.
    Credits first = 5;
    Credits second = 7;
    Credits total = first + second;
    $display("total = ", fshow(total));
    $finish(0);
  endrule
endmodule

endpackage

Check the result. The output line shows the type name Credits, the field name amount, and the value 12 together. The literals 5 and 7 became Credits values, and their sum keeps the Credits type, because the derived Literal and Arith instances reuse the behavior of the inner UInt#(8).

Try it yourself. Replace Credits first = 5; with the two lines UInt#(8) raw = 5; and Credits first = raw;. Compile error T0020 reports the expected type Credits against the inferred UInt#(8). The wrapper shares literals and arithmetic, but the two types still do not mix.

10. Choosing an implementation strategy

A broad typeclass bundles unrelated operations into one contract and can force callers to provide instances they never use. Small classes and narrow provisos let a generic function apply to more types.

11. Common mistakes

11.1 Leaving a proviso off a polymorphic function

// Wrong: the body uses priorityOf, but the signature does not require it
function Bit#(2) requestPriority(value_type value);
  return priorityOf(value);
endfunction

// Right
function Bit#(2) requestPriority(value_type value)
  provisos (Priority#(value_type));
  return priorityOf(value);
endfunction

// Wrong: pack on a type variable with nothing to justify it, T0030
function Bit#(n) bitsOf(t x);
  return pack(x);
endfunction

// Right
function Bit#(n) bitsOf(t x) provisos (Bits#(t, n));
  return pack(x);
endfunction

Error T0030 says the provisos are too general and names the needed requirement, Priority#(value_type) or Bits#(t, n), along with where it was introduced. Operations on a type variable must be declared as provisos; the message prints the proviso it needs, so add exactly that one to the signature.

11.2 Changing only the result width

// Wrong: Add#(3, 4, 8) is false
Bit#(8) result = appendTag(3'b101, 4'ha);

// Right: choose input widths that make the relation hold
Bit#(8) result = appendTag(4'b1101, 4'ha);

A width-relation proviso has no automatic extension or truncation. If you want a zero-padded 8-bit value, receive the result as Bit#(7) and widen it with zeroExtend.

11.3 Passing a type that has no instance

// Wrong: there is no Priority#(UInt#(8)) instance
$display("%0d", requestPriority(UInt#(8)'(5)));

// Right: if you really need that type, define the instance
instance Priority#(UInt#(8));
  function Bit#(2) priorityOf(UInt#(8) value) = truncate(pack(value));
endinstance

When T0031 names a concrete type, the type is missing an instance; the function is fine. Adding unrelated provisos to the generic function will not help.

11.4 Misspelling an operator member

// Wrong: Eq has no member named \!=
function Bool \!= (Code a, Code b) = a.v != b.v;

// Right
function Bool \/= (Code a, Code b) = a.v != b.v;

The inequality member of Eq is \/=. Writing \!= gives T0016, saying != is not a field of Eq. Leaving out the space after an escaped identifier gives parse error P0005.

11.5 Assigning the inner type to an isomorphic wrapper

// Wrong
UInt#(8) raw = 5;
Credits c = raw;

// Right: wrap it with a struct expression
Credits c = Credits { amount: raw };

The wrapper is a different type from its contents, so this is error T0020. Preventing exactly this kind of mixing is why you use a wrapper.

11.6 Using a numeric type without valueOf

// Wrong: a type where a value is expected, P0005
$display("%0d", SizeOf#(Bool));

// Right
$display("%0d", valueOf(SizeOf#(Bool)));

A numeric type is a type. To use it in an expression, turn it into an Integer with valueOf.

12. Summary

13. Check your understanding

1. When is Priority#(RequestKind) selected, and does that create a circuit that chooses instances at runtime?

   Show answer

   It is selected during type checking and elaboration, from the argument type RequestKind. Only the chosen implementation becomes hardware, so there is no runtime selection circuit.

2. How does Bits#(t, n) constrain both an operation and a width?

   Show answer

   It makes pack and unpack available for t, and it ties the width of t's representation to n. That is how a Bit#(n) return type gets its width from the argument type at each call.

3. How does Add#(n, 4, m) differ from simply writing the result type as Bit#(7)?

   Show answer

   Bit#(7) allows only one width. Add#(n, 4, m) requires the relation "result width is input width plus four" for any n, so the same function works for many input widths.

4. Storing pad0101(pair) in a Bit#(8) fails. Where, and with what error?

   Show answer

   At the call, not in the definition, with T0031. With n = 2, Add#(2, 4, m) requires m = 6, while the target requires m = 8.

5. Where do you fix a T0030, and where do you fix a T0031 that names a concrete type?

   Show answer

   T0030 means a generic definition does not require an operation its body uses, so add the proviso to that definition. A T0031 with a concrete type means that type has no instance, so use another type or define the instance.

6. Why can't SizeOf#(T) be passed straight to $display?

   Show answer

   SizeOf#(T) is a numeric type, not a value. $display takes values, so the width must first become an Integer through valueOf.

7. For a hand-written Bits instance, what does type checking guarantee, and what does it not?

   Show answer

   It guarantees that pack and unpack use the declared width. It does not guarantee that they are inverses, that is, unpack(pack(c)) == c, which you must verify separately.

8. When is deriving Literal and Arith on an isomorphic wrapper the right choice?

   Show answer

   When you want the type system to keep a unit separate from plain numbers, but its arithmetic should mean exactly what the inner type's arithmetic means. If the arithmetic must behave differently, write the instance yourself.

The Practice problems of this chapter follow the polymorphism, instance-selection, width-proviso, and Bits instance examples. The first asks you to complete a polymorphic function constrained by a Bits proviso. The second asks you to define the priority behavior of RequestKind used through the polymorphic Priority proviso. The third asks you to complete a concatenation whose result width is fixed by an Add proviso. In the fourth, the decoding contradicts the protocol encoding chosen by pack. For each, decide first whether the error or wrong output comes from an instance, a width relation, or a semantic contract.