Generic Programming 2.0 with Concepts and Ranges

“Generic Programming 2.0 with Concepts and Ranges” is a two-day training course with programming exercises taught by Christopher Di Bella. It is offered at the Meydenbauer Conference Center from 9AM to 5PM on Saturday and Sunday, September 29th and 30th (immediately after the conference). Lunch is included.

Course Description

Templates are a powerful tool that helps your code become expressive and robust, but making clear, concise, and correct generic interfaces can be a challenge.

Concepts — which have been over twenty years in the making — are a refinement over templates, allowing you to constrain your types to more specific interfaces; thereby almost completely eliminating the need for SFINAE. To paraphrase a committee member, concepts are not immediately useful without library support. This is where Ranges come in: the new Ranges library is a first step toward a new C++ standard library, that provides Standard concepts for you to use out of the box, more expressive algorithms (that better diagnose incorrect usage), and even more expressive ways to compose your operations.

Writing effective, general-purpose concepts for your domain is a skill that takes time to learn. We’ll spend some time initially exploring how to take advantage of the new library features and how to adapt your existing code to take advantage of their availability. We’ll then focus on showing you how to design and express concepts, so that you can refine your libraries and programs as clearer, more usable expressions of intent.

Prerequisites

This course assumes familiarity with the following:

  • C++14 core language features
  • Templates and generic programming
  • First-year university mathematics for computer science (we will cover all necessary material in class, but you’ll need experience with uni maths to keep pace)
  • Git

Familiarity with any of the following is advantageous, but not completely essential:

  • C++17 core language features
  • C++ Standard Library
  • Abstract algebra
  • Reading technical papers such as C++ Standard proposals
  • CMake

Preparation

Please ensure that you have installed and configured Docker as per the class installation instructions prior to attending the class.

Course Topics

The first day is dedicated to looking at the problems C++ programmers face when writing generic code using modern C++, and how we can leverage the Concepts TS to address these problems. By analysing hand-written algorithms from open-source projects — and understanding how to transform them into robust, generic data structures and algorithms that work for type genera (concepts) — we’ll explore why the Concepts TS isn’t immediately useful without the Ranges TS, and how the Ranges library can provide you with more composable, readable descriptions of your intent. Time will be set aside for you to practice using the Concepts TS and Ranges TS.

Day two will focus on modeling a real-world concept. Not everything deserves to be a concept: the C++ Standards Committee advises that we model concepts to reason about the meaning of your code, rather than getting your code to compile. This is not an easy skill to learn: a ‘good’ concept needs well-thought-out design requirements, and may need to have mathematical modeling. We will spend sufficient time talking about when we should write such concepts, the requirements that they need, and how to draw upon abstract algebra and logic to prove that our concept describes the constraint that we actually desire. It isn’t always possible to write a ‘good’ concept: sometimes we may find ourselves writing ‘dirty’ concepts to get the job done (concepts that reason about syntax only), so we’ll cover how to approach writing ‘dirty’ concepts. Finally, testing that concepts actually constrain types that model the concept is very important, so we’ll spend some time discussing how to test our own concepts.

  • Course aim
    • This course aims to develop students’ skills and understanding for modeling their interfaces’ type requirements.

 

Course objectives Course outcomes
Students will develop A student
1. knowledge and understanding about why concepts are necessary for constraining generic interfaces
  • CR1.1
    • determines when it is necessary to use concepts with generic code
  • CR1.2
    • determines when concepts are not appropriate to use in a generic context
2. knowledge and understanding about why implementing concepts is a non-trivial task
  • CR2.1
    • assesses contexts to determine if a situation requires a custom concept
  • CR2.2
    • analyses the requirements for the types their generic context
  • CR2.3
    • models the requirements on semantics rather than syntax
3. knowledge and understanding of the rationale and mathematics behind the concepts prescribed by the Ranges TS
  • CR3.1
    • uses Standard concepts over writing custom concepts
  • CR3.2
    • relies on Standard concepts as a basis for their own concepts
  • CR3.3
    • models their requirements on the mathematics of the Ranges TS
  • CR3.4
    • understands:
      • linear orderings,
      • ordered algebraic structures,
      • rearrangements,
      • partitioning, and
      • merging
4. skills in using constraints to specify requirements for generic code
  • CR4.1
    • identifies which constraints their data structures and algorithms require
  • CR4.2
    • properly adds constraints to their generic code to prevent implementation leakage
  • CR4.3
    • uses concepts and requires-clauses as a clean way to express constraints
  • CR4.4
    • describes algorithm and data structure requirements
  • CR4.5
    • deduces algorithm logic and data structures from the interface requirements
 5. skills in using Standard concepts to model requirements
  • CR5.1
    • understands:
      • values,
      • objects,
      • regular types, and
      • functions, regular functions, predicates, and relations,
      • basic foundations of linear orderings and ordered algebraic structures,
      • iterators, sentinels, ranges, and coordinate structures
      • copyable types
  • CR5.2
    • chooses appropriate Standard concepts to constrain generic code
 6. skills in using Ranges TS to simplify (and generify) handwritten algorithms
  • CR6.1
    • identifies handwritten algorithms in open-source projects that can be converted to Standard algorithms
  • CR6.2
    • modifies handwritten algorithms so they take advantage of Standard algorithms
  • CR6.3
    • considers Standard algorithms before hand-writing an algorithm
  • CR6.4
    • considers Standard algorithms during code reviews
  • CR6.5 (extension, depends on Parallel Ranges development)
    • considers Standard parallel algorithms in appropriate situations
 7. skills in refining Ranges TS concepts
  • CR7.1
    • understands what it means to refine a concept
  • CR7.2
    • refines Standard concepts, so that they do not need to build concepts from the ground up
 8. skills in writing non-Standard concepts
  • CR8.1
    • understands the difference between a concept and a ‘dirty’ concept
  • CR8.2
    • understands when it is okay to write a ‘dirty’ concept
  • CR8.3
    • understands when it is necessary to write a non-Standard concept
  • CR8.4
    • understands the basics of algebraic structures such as:
      • rings,
      • semirings,
      • fields,
      • monoids,
      • groups, and
      • semigroups
  • CR8.5
    • understands the basics of number theory
  • CR8.6
    • uses algebraic structures and number theory to model requirements for concepts
  • CR8.7
    • develops concepts that model semantics, not syntax
9. skills in writing tests for concept-checked code
  • CR9.1
    • develops tests that check concepts constrain types via positive testing
  • CR9.2
    • develops tests that check concepts constrain types via negative testing
  • Assessment There will be no formal assessments such as exams or assignments in this course. The course will have exercises that students will be given time to solve on both days that students can use to gauge how well they are following along with the material being taught. All exercises will have solutions that will be released a few days after the course has concluded.

Course Instructor

Christopher Di Bella

Christopher Di Bella is a Staff Software Engineer for Codeplay’s ComputeCpp Runtime Technology. He is a strong proponent for having the Concepts TS and the Ranges TS in C++20. Chris spends his days working on ComputeCpp, Codeplay’s implementation of SYCL; the Khronos implementation for the Parallel STL (using SYCL); and researching Parallel Ranges, which is an attempt to bring the aforementioned Ranges TS together with the parallel algorithms. He was previously a software developer for Nasdaq, and a tutor for UNSW Australia’s COMP6771 Advanced C++ Programming course in Sydney, Australia. In his spare time, Chris enjoys snowboarding, playing games, and watching films.