Numbers

[hamsterman]

Write classes Z, Q, R, C (integer, rational, real, complex) and operators or functions +, -, * such that each class is closed under each operation and Z + R = R, etc. in a way that does not keep dynamic type information and does not introduce tight coupling. Use a language of your choice.

You may use basic types present in that language to implement the classes. You may use built-in operators (int, int) => int, etc. and type conversion functions int => float, etc. You may not, however use operators (int, float) => float, etc.

I hope I've put it clearly enough. I hope I'm not being silly. I find this to be a very hard task. It requires much reasoning about the type structure and other static things.

I tried to write this with Scala, but I'm not too good at it. Now I'm thinking that some C++ macro/template hack is more likely to work, I'll have to give that a try.

[Peter87]

I don't think macro/template hacks are necessary. Just create four classes and overload operator+,operator- and operator* for all the combinations of arguments.

// Z + R = R
R operator+(const Z& z, const R& r)
{
	// somehow add z and r and return an R
}

[hamsterman]

<...> and does not introduce tight coupling

This is as tight as it gets.

[Peter87]

hmm. You are right.

What if you define the operators only for the same types and have constructors that can construct an object from objects of another type.

class R
{
public:
	R(const Z& z);
	...
};
R operator+(const R& r1, const R& r2);

Or is this also tight coupling? I guess the classes get quite closely coupled but the operators are not coupled at all.

[hamsterman]

Well, this still doesn't work. Z + R is okay, but Z + C needs too many conversions. C++ only allows a couple of implicit constructor calls like this.
I do feel bad about not considering this one before though..

[Cubbi]

Z + C needs too many conversions.

Why many? It needs only one conversion, from Z to C, which is mathematically reasonable.
Or no conversions at all: op+(C, Z) and op+(Z, C).
Or, considering there is also R, and given C->R conversion, op+(R, Z) and op+(Z, R), which is exactly the approach found in C++.

[hamsterman]

I know it can be done in general. The point of the exercise is to do it in an extensible way. To append a more general set to the list, it should be enough to implement the set itself and to write one conversion from a less general one. Although to have several constructors is not unbearable.

What I was hoping to find was a class structure that would make sense in this case. The sets have a strange relation. All integers are valid complex numbers, but to make integer a child of complex is a bit absurd.

[m4ster r0shi]

Ta daaa!!!

#include <boost/mpl/vector.hpp>
#include <boost/mpl/find.hpp>
#include <boost/mpl/bool.hpp>
#include <boost/mpl/int.hpp>
#include <boost/mpl/at.hpp>
#include <boost/mpl/if.hpp>

#include <iostream>

struct Z { Z() {}                                       };
struct Q { Q() {} Q(Z) { std::cout << "[Z -> Q]... "; } };
struct R { R() {} R(Q) { std::cout << "[Q -> R]... "; } };
struct C { C() {} C(R) { std::cout << "[R -> C]... "; } };
struct B { B() {} B(C) { std::cout << "[C -> B]... "; } };
struct A { A() {} A(B) { std::cout << "[B -> A]... "; } };

Z operator + (Z, Z) { std::cout << "Z + Z stuff" << std::endl; }
Q operator + (Q, Q) { std::cout << "Q + Q stuff" << std::endl; }
R operator + (R, R) { std::cout << "R + R stuff" << std::endl; }
C operator + (C, C) { std::cout << "C + C stuff" << std::endl; }
B operator + (B, B) { std::cout << "B + B stuff" << std::endl; }
A operator + (A, A) { std::cout << "A + A stuff" << std::endl; }

typedef boost::mpl::vector<Z, Q, R, C, B, A> types;

const char * typeId2char = "ZQRCBA";

template <class T1, class T2>
typename
    boost::mpl::if_<
        boost::mpl::bool_<
            (boost::mpl::find<types, T1>::type::pos::value <
             boost::mpl::find<types, T2>::type::pos::value)>,
        T2,
        T1
    >::type
operator + (T1 n1, T2 n2)
{
    const int pos1 = boost::mpl::find<types, T1>::type::pos::value;
    const int pos2 = boost::mpl::find<types, T2>::type::pos::value;

    std::cout << typeId2char[pos1] << " + "
              << typeId2char[pos2] << " stuff" << std::endl;

    typedef typename
        boost::mpl::if_<
            boost::mpl::bool_<(pos1 < pos2)>,
            typename
                boost::mpl::at<types, boost::mpl::int_<pos1 + 1> >::type,
            T1
        >::type LeftType;

    typedef typename
        boost::mpl::if_<
            boost::mpl::bool_<(pos1 > pos2)>,
            typename
                boost::mpl::at<types, boost::mpl::int_<pos2 + 1> >::type,
            T2
        >::type RightType;

    return LeftType(n1) + RightType(n2);
}

int main()
{
    Z() + Z();
    Q() + Q();
    R() + R();
    C() + C();
    B() + B();
    A() + A();

    std::cout << std::endl;

    Z() + A();

    std::cout << std::endl;

    A() + Z();
}

Z + Z stuff
Q + Q stuff
R + R stuff
C + C stuff
B + B stuff
A + A stuff

Z + A stuff
[Z -> Q]... Q + A stuff
[Q -> R]... R + A stuff
[R -> C]... C + A stuff
[C -> B]... B + A stuff
[B -> A]... A + A stuff

A + Z stuff
[Z -> Q]... A + Q stuff
[Q -> R]... A + R stuff
[R -> C]... A + C stuff
[C -> B]... A + B stuff
[B -> A]... A + A stuff

[Cubbi]

Nice one

[m4ster r0shi]

Thank you

[JLBorges]

Yes! Ta daaa!!! indeed. Nice one indeed.

I suppose one could also use the Boost.NumericConversion library, writing a few custom conversion_traits<> As would be expected, the innards of the library use Boost.MPL.

[hamsterman]

Awesome.

I think some code could be saved if you gave each class a static const int N (Z.N = 0, Q.N = 1, ...) and wrote global functions Lift (Q Lift(Z), R Lift(Q), ... and probably A Lift(A)). Then + would be

template <class T1, class T2>
typename boost::mpl::if_< boost::mpl::bool_<(T1.N < T2.N)>, T2, T1 >::type
operator + (T1 n1, T2 n2)
{
    if (T1.N < T2.N) return Lift(n1) + n2;
    else if (T2.N < T1.N) return n1 + Lift(n2);
    else return n1 + n2;
}

Although I'm just guessing. I've never used mpl and don't have boost to try it. Also, apart from lines of code, it's hard to tell if this improves anything..
edit: nope, that didn't work out well..

Now, how to go about this is a language that doesn't allow magic? (Java/Scala/C#, I think)

[m4ster r0shi]

No, you're right, it's perfectly doable. I just wanted to do it in a non-intrusive way.

Also, you can use the built-in branching statements, but then you instantiate more
functions than you actually need (but this is not a real problem here, of course...).

#include <boost/mpl/bool.hpp>
#include <boost/mpl/if.hpp>

#include <iostream>

#define TYPE_INFO(Set, Num) typedef struct Set Next; static const int Id = Num;

struct Z { Z() {}                                       TYPE_INFO(Q, 0) };
struct Q { Q() {} Q(Z) { std::cout << "[Z -> Q]... "; } TYPE_INFO(R, 1) };
struct R { R() {} R(Q) { std::cout << "[Q -> R]... "; } TYPE_INFO(C, 2) };
struct C { C() {} C(R) { std::cout << "[R -> C]... "; } TYPE_INFO(B, 3) };
struct B { B() {} B(C) { std::cout << "[C -> B]... "; } TYPE_INFO(A, 4) };
struct A { A() {} A(B) { std::cout << "[B -> A]... "; } TYPE_INFO(A, 5) };

Z operator + (Z, Z) { std::cout << "Z + Z stuff" << std::endl; }
Q operator + (Q, Q) { std::cout << "Q + Q stuff" << std::endl; }
R operator + (R, R) { std::cout << "R + R stuff" << std::endl; }
C operator + (C, C) { std::cout << "C + C stuff" << std::endl; }
B operator + (B, B) { std::cout << "B + B stuff" << std::endl; }
A operator + (A, A) { std::cout << "A + A stuff" << std::endl; }

const char * typeId2char = "ZQRCBA";

template <class T1, class T2>
typename
    boost::mpl::if_<
        boost::mpl::bool_<(T1::Id < T2::Id)>,
        T2,
        T1
    >::type
operator + (T1 n1, T2 n2)
{
    std::cout << typeId2char[T1::Id] << " + "
              << typeId2char[T2::Id] << " stuff" << std::endl;

    if     (T1::Id < T2::Id)   return typename T1::Next(n1) + n2;
    else /* T1::Id > T2::Id */ return n1 + typename T2::Next(n2);
}

int main()
{
    Z() + Z();
    Q() + Q();
    R() + R();
    C() + C();
    B() + B();
    A() + A();

    std::cout << std::endl;

    Z() + A();

    std::cout << std::endl;

    A() + Z();
}

I'll try Scala next. But I don't think I'll do much...

EDIT: Heh... Looks like this functionality comes (almost) out-of-the-box with Scala...
http://stackoverflow.com/questions/5332801/how-can-i-chain-implicits-in-scala

[hamsterman]

I was hoping to write in a way that would not require to change the contents of the top class to add another one.

edit: I can't get specialization working. I want a template function

template<class Res, class Op>
Res LiftSome(Op o) {
   return LiftSome<Res>(Lift(o));
}

And a special case

template<class Res>
Res LiftSome<Res, Res>(Res r) {
   return r;
}

As for scala, it does have implicit casts, but the problem is in function definition. I tried doing this.

trait GroupUnderAddition[T] {
  def + (t : T) : T
}

case class Real(d : Double) extends GroupUnderAddition[Real] {
  def + (r : Real) = Real(d + r.d)
}

case class Complex(re : Double, im : Double) extends GroupUnderAddition[Complex] {
  def + (c : Complex) = Complex(re + c.re, im + c.im)
}

object Test {
  implicit def real_to_complex(r : Real) = Complex(r.d, 0)

  def test[G <: GroupUnderAddition[G]](a : G, b : G) = a + b

  def main(args : Array[String]) {
    println(test(Real(5), Real(2)))
  }
}

If I passed Complex and Real to test(), scala wouldn't know what G is.

[JLBorges]

> edit: I can't get specialization working. I want a template function ...
> And a special case ...

Function templates can't have partial specializations. They can be overloaded though.

template< class Res, class Op > Res LiftSome( Op o )
{ return LiftSome<Res>(Lift(o)); }

template<class Res> Res LiftSome (Res r) { return r ; }

which on reflection won't meet your needs.


A class template (with a static member function) which is partially specialized is possible and workable:

template< class Res, class Op > struct LiftSome
{ static Res do_it( Op o ) { return LiftSome< Res, decltype(Lift(o)) >::do_it( Lift(o) ); } } ;

template<class Res> struct LiftSome<Res,Res>
{ static Res do_it(Res r) { return r ; } } ;

Note: This lift (cascaded upcast) mechanism would also be required in m4ster r0shi's code samples to make them compilable. (Along with return statements in the operator+ functions).

[hamsterman]

Finally.

#include <iostream>
 
template<bool C, class A, class B>
struct If{
   typedef A Type;
};
 
template<class A, class B>
struct If<0, A, B>{
   typedef B Type;
};
 
template<int M>
struct G{
   static const int N = M;
};
 
struct Z : G<0> {};
struct Q : G<1> {};
struct R : G<2> {};
 
Q Lift(Z) { std::cout << "Z->Q\n"; return Q(); }
R Lift(Q) { std::cout << "Q->R\n"; return R(); }
 
Z operator + (Z, Z) { std::cout << "Z+Z\n"; return Z(); }
Q operator + (Q, Q) { std::cout << "Q+Q\n"; return Q(); }
R operator + (R, R) { std::cout << "R+R\n"; return R(); }
 
template<class R, class O>
struct Lifter{
   static R Up(O o){
      return Lifter<R, decltype(Lift(o))>::Up(Lift(o));
   }
};
 
template<class R>
struct Lifter<R, R>{
   static R Up(R r){
      return r;
   }
};
 
template<class A, class B>
typename If<(A::N > B::N), A, B>::Type operator + (A a, B b) {
   typedef typename If<(A::N > B::N), A, B>::Type HI;
   return Lifter<HI, A>::Up(a) + Lifter<HI, B>::Up(b);
}
 
int main() {
  Z z;
  R r;
  R res = z + r;
}

Thanks, JLBorges.

The next step is to eliminate N, or at least move somewhere so that one could write Complex Lift(float) and have it working...

[JLBorges]

> The next step is to eliminate N, or at least move somewhere so that one could write Complex Lift(float) and have it working...

@hamsterman,
Are you following this up? If you have abandoned it, I'd like to post a solution (C++11, without boost).

[hamsterman]

Are you following this up?

I'm not sure. The way I see it, I'd have to write a graph search algorithm in C++ templates, which should be entirely possible, but very painful.
Though if you find this interesting, you should definitely post your work, regardless of what I'm doing.

[JLBorges]

#include <iostream>
#include <typeinfo>
#include <functional>
#include <tuple>
#include <type_traits>
using namespace std ;

//////////////////////////////////////////////////////////////////////////////////////////

// types S (short integer), I (integer), L(long integer), R (rational), F (real), Z (imaginary)
// defined conversions: S=>I, I=>L, L=>R, R=>F, F=>Z
struct S {}; S operator+ (S,S) { cout << "S+S\n" ; return S(); }
struct I { I() {} I(S) { cout << "S => I : " ; } }; I operator+ (I,I) { cout << "I+I\n" ; return I(); }
struct L { L() {} L(I) { cout << "I => L : " ; } }; L operator+ (L,L) { cout << "L+L\n" ; return L(); }
struct R { R() {} R(L) { cout << "L => R : " ; } }; R operator+ (R,R) { cout << "R+R\n" ; return R(); }
struct F { F() {} F(R) { cout << "R => F : " ; } }; F operator+ (F,F) { cout << "F+F\n" ; return F(); }
struct Z { Z() {} Z(R) { cout << "R => Z : " ; } }; Z operator+ (Z,Z) { cout << "Z+Z\n" ; return Z(); }

//////////////////////////////////////////////////////////////////////////////////////////

// typelist with functionality to retrieve the next type in the list
template< typename... TYPES > struct typelist {};

template< unsigned int N, typename... TYPES > struct at {} ;
template< unsigned int N, typename... TYPES > struct at< N, typelist<TYPES...> >
{ typedef typename tuple_element< N, tuple<TYPES...> >::type type ; };

template< typename T, typename U, int N = 0 > struct indexof ;
template< typename T, int N > struct indexof< T, typelist<>, N > { enum { value = -1 } ; };
template< typename T, typename FIRST, typename ...REST, int N >
struct indexof< T, typelist<FIRST,REST...>, N >
            : conditional< is_same<T,FIRST>::value,
                                integral_constant<int,N>,
                                indexof< T, typelist<REST...>, N+1 > >::type {} ;

template < typename T, typename TLIST > struct next_wider_type
{ typedef typename at< indexof<T,TLIST>::value+1, TLIST >::type type ; } ;

// our typelist is ordered as S,I,L,R,F,Z in the order of conversions narrower type => wider type
typedef typelist<S,I,L,R,F,Z> TYPELIST ;

////////////////////////////////////////////////////////////////////////////////////////////

// cascaded upcast from SRCE => DEST - if there is a direct convesion from SRCE=>DEST, use it
template < typename SRCE, typename DEST, typename TLIST = TYPELIST >
DEST lift( SRCE s,
           typename enable_if< is_convertible<SRCE,DEST>::value, void >::type* = nullptr )
{ return DEST(s) ; }

// if not, cast SRCE up by one level to the next wider type and try again
template < typename SRCE, typename DEST, typename TLIST = TYPELIST >
DEST lift( SRCE s,
           typename enable_if< !is_convertible<SRCE,DEST>::value, void >::type* = nullptr )
{
    typedef typename next_wider_type<SRCE,TLIST>::type wider_type ;
    return lift< wider_type, DEST, TLIST >( wider_type(s) ) ;
}

// helper to determine the wider type
template< typename A, typename B > struct wider_type
{
    typedef typename conditional< ( indexof<A,TYPELIST>::value > indexof<B,TYPELIST>::value ),
                                    A, B >::type type ;
};

//////////////////////////////////////////////////////////////////////////////////////////////

template< typename A, typename B > inline
typename wider_type<A,B>::type operator + ( A a, B b )
{
   typedef typename wider_type<A,B>::type type ;
   return lift<A,type>(a) + lift<B,type>(b);
}

///////////////////////////////////////////////////////////////////////////////////////////////

int main() // perfunctory test driver
{
  cout << "S+Z : " ; Z z1 = S() + Z() ;
  cout << "Z+S : " ; Z z2 = Z() + S() ;
  cout << "I+R : " ; R r1 = I() + R() ;
  cout << "R+F : " ; F f1 = R() + F() ;
}