How to use multi-constraint generics to implement reusable numeric algorithms

mtn — Thu, 30 Nov 2006 09:01:54 -0800

Introduction

The goal of this tutorial is to show you how you can harness the power of multi-constraint generic type parameters to implement versatile numerical algorithms.

If you write algorithms in a generic way you can reuse them and create instances of the same algorithm parametrized with different types. This way the reuse of your code can be maximized. For numeric applications one obvious need is the ability to chose between REAL_32 and REAL_64. If your algorithms become more abstract they might be applied to vectors, polynomials or to any other mathematical construct which satisfies the given constraints.

First trial

Our first attempt looks somehow like this

class EXAMPLE [G -> NUMERIC]

create

   default_create

feature -- Numeric algorithms

   compute_sum (n1, n2: G): G is

         -- Computes the sum of `n1' and `n2'

      do

         Result := n1 + n2

      end

end

This code works perfectly well with any descendant of NUMERIC. As the class NUMERIC defines a deferred infix `+' operation each descendant has to implement it accordingly.

example_feature is

      -- Example usage

   local

      l_exmpl: EXAMPLE [INTEGER_64]

      l_integer: INTEGER_64

   do

      create l_exmpl

      l_integer := l_exmpl.compute_sum (11, 31)

      io.put_integer (l_integer)

   end

This is already pretty powerful and one can for example write VECTOR classes in a generic way using NUMERIC as a constraint.

More sophisticated example

If you want to program more sophisticated algorithms you soon run into problems because many algorithms require an order relation, meaning some kind of comparison function like smaller as (<). The problem is that the class NUMERIC has no feature to compare to numbers. Classes like INTEGER and REAL inherit this feature from the class COMPARABLE. Once again Eiffel provides a neat way to resolve the issue: We simply add a second constraint to our generic type parameter G.

class EXAMPLE [G -> {COMPARABLE, NUMERIC}]

end

G is now called a multiple constrained formal type parameter. This means that any valid type for G has to be conform to COMPARABLE and NUMERIC. This perfectly suits our purpose because all common used descendands of NUMERIC like INTEGER and REAL also inherit from COMPARABLE.

Now we are able to use the order relations defined in COMPARABLE:

class EXAMPLE [G -> {COMPARABLE, NUMERIC}]

create

   default_create

feature -- Numeric algorithms

   absolute_value (n1, n2: G): G is

         -- Example usage

         -- This is not the best way to compute the absolute value :)

      do

          if n1 > n2 then

             Result := n1 - n2

          else

             Result := n2 - n1

          end

      end

end

Renaming for multi-constraint generics

But watch out! As some features are inherited twice, like is_equal we have to resolve this name clash by a renaming in the following way:

class EXAMPLE [G -> {COMPARABLE, NUMERIC rename is_equal as is_equal_numeric end}]

-- ...

end

If you want to be able to create instances of G you should also set a creation constraint:

class EXAMPLE [G -> {

                     COMPARABLE

                        rename

                            default_create as default_create_comparable

                        end,

                     NUMERIC

                        rename

                            is_equal as is_equal_numeric

                        end

                    } create default_create end]

end

Again we use a renaming to resolve the name conflict because both classes provide default_create.

Inversion

If you need inversion the following hack can help you to achive your goal:

class EXAMPLE [G -> {COMPARABLE, NUMERIC}]

feature

    inversion (a_g: G)

            -- Inverts `a_g'.

        do

            Result := a_g.one / a_g

        end

end

We use the feature one from NUMERIC to achieve our goal. Consider storing this object to a local variable to speed up things a little. There is also a feature zero available for usage. Now you may ask: How can I multiply by three? Well, I leave that to your imagination how one could achieve that goal. I think it's ugly. I know that some more specialized algorithms might have the need for it. But unless we get a better abstracted mathematical class hierarchy we are stuck to ugly hacks. And by the way don't forget to check the precondition every time you divide something! But apart from issues like that, you can build wonderful reusable algorithms at little or no additional cost! To end our little tour (haha :-) let's have a look at a useful example: