C++ concepts and Haskell type classes

Motivation

GCC 6.1 Released with C++ concept support (-fconcepts)
A lot of questions about difference between this two features
- How are C++ concepts different to Haskell type classes?
- A Comparison of C++ Concepts and Haskell Type Classes
- Concepts for C++1y: The Challenge
Docendo discimus (by teaching, we learn)

The problem with C++ templates

The programmer has a set of problems and he decides to use C++

class Problem {
public:
    // ...
};

int main() {
    set<Problem> to_do;

    to_do.insert(Problem{});

    return 0;
}

this is sparta problem!

In file included from /usr/include/c++/6/bits/stl_tree.h:65:0,
                 from /usr/include/c++/6/set:60,
                 from SetOfProblems.cpp:1:
/usr/include/c++/6/bits/stl_function.h: In instantiation of ‘constexpr bool std::less<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = Problem]’:
/usr/include/c++/6/bits/stl_tree.h:1806:11:   required from ‘std::pair<std::_Rb_tree_node_base*, std::_Rb_tree_node_base*> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_get_insert_unique_pos(const key_type&) [with _Key = Problem; _Val = Problem; _KeyOfValue = std::_Identity<Problem>; _Compare = std::less<Problem>; _Alloc = std::allocator<Problem>; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::key_type = Problem]’
/usr/include/c++/6/bits/stl_tree.h:1859:28:   required from ‘std::pair<std::_Rb_tree_iterator<_Val>, bool> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_insert_unique(_Arg&&) [with _Arg = Problem; _Key = Problem; _Val = Problem; _KeyOfValue = std::_Identity<Problem>; _Compare = std::less<Problem>; _Alloc = std::allocator<Problem>]’
/usr/include/c++/6/bits/stl_set.h:492:40:   required from ‘std::pair<typename std::_Rb_tree<_Key, _Key, std::_Identity<_Key>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator, bool> std::set<_Key, _Compare, _Alloc>::insert(std::set<_Key, _Compare, _Alloc>::value_type&&) [with _Key = Problem; _Compare = std::less<Problem>; _Alloc = std::allocator<Problem>; typename std::_Rb_tree<_Key, _Key, std::_Identity<_Key>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator = std::_Rb_tree_const_iterator<Problem>; std::set<_Key, _Compare, _Alloc>::value_type = Problem]’
SetOfProblems.cpp:15:27:   required from here
/usr/include/c++/6/bits/stl_function.h:387:20: error: no match for ‘operator<’ (operand types are ‘const Problem’ and ‘const Problem’)
       { return __x < __y; }
                ~~~~^~~~~
In file included from /usr/include/c++/6/bits/stl_algobase.h:64:0,
                 from /usr/include/c++/6/bits/stl_tree.h:63,
                 from /usr/include/c++/6/set:60,
                 from SetOfProblems.cpp:1:
/usr/include/c++/6/bits/stl_pair.h:369:5: note: candidate: template<class _T1, class _T2> constexpr bool std::operator<(const std::pair<_T1, _T2>&, const std::pair<_T1, _T2>&)
     operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
     ^~~~~~~~

/usr/include/c++/6/bits/stl_pair.h:369:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/6/bits/stl_tree.h:65:0,
                 from /usr/include/c++/6/set:60,
                 from SetOfProblems.cpp:1:
/usr/include/c++/6/bits/stl_function.h:387:20: note:   ‘const Problem’ is not derived from ‘const std::pair<_T1, _T2>’
       { return __x < __y; }
                ~~~~^~~~~
In file included from /usr/include/c++/6/bits/stl_algobase.h:67:0,
                 from /usr/include/c++/6/bits/stl_tree.h:63,
                 from /usr/include/c++/6/set:60,
                 from SetOfProblems.cpp:1:
/usr/include/c++/6/bits/stl_iterator.h:298:5: note: candidate: template<class _Iterator> bool std::operator<(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_Iterator>&)
     operator<(const reverse_iterator<_Iterator>& __x,
     ^~~~~~~~
/usr/include/c++/6/bits/stl_iterator.h:298:5: note:   template argument deduction/substitution failed:
In file included from /usr/include/c++/6/bits/stl_tree.h:65:0,
                 from /usr/include/c++/6/set:60,
                 from SetOfProblems.cpp:1:
/usr/include/c++/6/bits/stl_function.h:387:20: note:   ‘const Problem’ is not derived from ‘const std::reverse_iterator<_Iterator>’
       { return __x < __y; }
                ~~~~^~~~~
In file included from /usr/include/c++/6/bits/stl_algobase.h:67:0,
                 from /usr/include/c++/6/bits/stl_tree.h:63,
                 from /usr/include/c++/6/set:60,
                 from SetOfProblems.cpp:1:

SOS!

ConceptOfProblems.cpp: In function ‘int main()’:
ConceptOfProblems.cpp:28:16: error: template constraint failure
     set<Problem> to_do;
                ^
ConceptOfProblems.cpp:28:16: note:   constraints not satisfied
ConceptOfProblems.cpp:28:16: note:   concept ‘LessComparable<Problem>()’ was not satisfied

template<typename T>
concept bool LessComparable()
{
  return requires (T a, T b)
  {
    { a < b } -> bool;
  };
}

Hmm... I guess I saw this before in Haskell

class LessComparable a where
    (<) :: a -> a -> Bool

Polymorphism

	Static	Dynamic
C++	templates	virtual functions
Haskell	forall	type classes

Find the difference

C++ style

// Concept
template<class T> concept bool Stringable = 
    requires(const T& a) {
        {to_string(a)} -> string;
    };
// Modelling
class Person {
    //...
    friend string to_string(const Person&);
};
// Algorithm
string bold(const Stringable& s) {
    return "<b>" + to_string(s) + "</b>";
}
// Instantiation
cout << bold(Person{"John", "Smith"}) << endl;

Templates instantiation

Code after concept check

// Modelling
class Person {
    //...
    friend string to_string(const Person&);
};
// Algorithm
string bold(const Person& s) {
    return "<b>" + to_string(s) + "</b>";
}
// Instantiation
cout << bold(Person{"John", "Smith"}) << endl;

Try and see

https://gcc.godbolt.org/

g++-6.1 -S -fconcepts -O0 -fverbose-asm stringable.cpp | c++filt

std::__cxx11::basic_string<...> bold<Person>(Person const&):
        push    rbp     
        mov     rbp, rsp  
        push    rbx     
        sub     rsp, 88   
        ; ...
        call    to_string[abi:cxx11](Person const&)     
        ; ...
        mov     rax, QWORD PTR [rbp-88]   #, <retval>
        add     rsp, 88   
        pop     rbx       
        pop     rbp       
        ret

Haskell style

-- Type class
class Stringable a where
    toString :: a -> String

data Person = Person {firstname :: String, lastname :: String}

-- Instance
instance Stringable Person where
    toString p = take 1 (firstname p) ++ ". " ++ lastname p

-- Algorithm
bold :: Stringable a => a -> String
bold a = "<b>" ++ toString a ++ "</b>"

--Instantiation
putStrLn $ bold $ Person "John" "Smith"

Dictionary passing

data Stringable a = Stringable { toString :: a -> String }

data Person = Person { firstname :: String, lastname :: String }

personToString :: Person -> String
personToString p = take 1 (firstname p) ++ ". " ++ lastname p

dStringablePerson :: Stringable Person
dStringablePerson = Stringable { toString = personToString }

bold :: Stringable a -> a -> String -- '=>' became '->'
bold dStringlable a = "<b>" ++ toString dStringlable a ++ "</b>"

-- the context is now a parameter!
putStrLn $ bold dStringablePerson $ Person "John" "Smith"

Type classes are a way to pass instance dictionaries implicitly

We need to go deeper

ghc -ddump-inlinings -ddump-simpl -dsuppress-module-prefixes \
    -dsuppress-idinfo -dsuppress-coercions \
    -dsuppress-type-applications -fforce-recomp -O0 main.hs

toString :: forall a_alG. Stringable a_alG => a_alG -> String
toString = \ (@ a_alG) (tpl_B1 :: Stringable a_alG) ->
    case tpl_B1 of tpl_B1 { D:Stringable tpl_B2 tpl_B3 -> tpl_B2 }

bold :: forall a. Stringable a => a -> String
bold = \ (@ a) ($dStringable :: Stringable a) (a1 :: a) ->
    ++
      (unpackCString# "<b>"#)
      (++ (toString $dStringable a1) (unpackCString# "</b>"#))
$fStringablePerson :: Stringable Person
$fStringablePerson = D:Stringable $ctoString $cfromString

putStrLn
    (bold
       $fStringablePerson
       (Person (unpackCString# "John"#) (unpackCString# "Smith"#)))

Comparison

Haskell type classes:
- Generic
- Compile-time checks
- Runtime polymorphism
C++ concepts:
- Generic
- Compile-time checks
- Function overloading (compile-time polymorphism)

What is the analogue in C++ for type classes?

C++ parameterized abstract class

template<typename T> struct Stringable {
    virtual string to_string(const T&) const = 0;
};

template<typename T> struct StringablePerson;
template<> struct StringablePerson<Person>: Stringable<Person> {
    string to_string(const Person& p) const override {
        return p.firstname().substr(0, 1) + ". " + p.lastname();
    }
};

StringablePerson<Person> dStringable;

template<typename T>
string bold(const Stringable<T>& dict, const T& a) {
    return "<b>" + dict.to_string(a) + "</b>";
}

cout << bold(dStringable, Person{"John", "Smith"}) << endl;

Conclusions

C++ concepts and Haskell type classes just look the same
But:
- they have different scope
- and different purpose
Nearest analogue to type classes in C++ is parameterized abstract classes

References

ISO/IEC JTC1 SC22 WG21 N 4377 IT -- Programming Languages — C++ Extensions for Concepts - Paper
Александр Фокин, От Concepts к Concepts Lite - Video
Andrew Sutton, Defining Concepts - Blogpost
Tom Honermann, Why Concepts didn't make c++17 - Blogpost
Andrew Sutton, Origin - Source
How are C++ concepts different to Haskell typeclasses? - SO
Miran Lipovača, Learn You a Haskell for Great Good! - eBook

More references

OOP vs Type classes - Blogpost
Implementing, and Understanding Type Classes - Blogpost
Parametric Polymorphism in Haskell, Ben Deane - Slides
Understanding C++ Concepts through Haskell Type Classes, Bartosz Milewski - Video
A comparison of C++ concepts and Haskell type classes, Jean-Philippe Bernardy and others - Paper
Concepts for C++1y: The Challenge, B. Stroustrup - Slides
Instances and Dictionaries, Jonathan Fischoff - Blogpost

Thank you for your attention!

Contacts:

email	Pavel.Filonov@kaspersky.com
github	sdukshis
skype	filonovpv
twitter	@filonovpv