Dependent template name argument substitution

Question

I'm not sure how to explain this, so I'll give the code.

I'm trying to encode (for fun, also to help me understand template metaprogramming) Chuch numerals using C++ templates.

struct Z {
  static constexpr unsigned int n = 0;

  template<typename T>
  using replace = T;
};

template<typename T>
struct S {
  static constexpr unsigned int n = T::n + 1;

  template<typename U>
  // using replace = T::replace<U>;
  using replace = typename T::template replace<U>;
};

So, I tried using replace = T::replace<U>, which really didn't work, and I had no idea why (I was using GCC), ~~and I'd appreciate if someone could explain why to me~~ (see link below). When I tried compiling with Clang, it gave me a nice error message:

First, use 'template' keyword to treat 'replace' as a dependent template name, then template argument for template type parameter must be a type; did you forget 'typename'?...

Then I managed to make using replace = typename T::template replace<U> compile, this seems legal.

But what I actually needed was something like S<T::replace<U>>, which I found no way to make work.

I tried changing this to T::replace<U>::succ as well, and defining succ to be S<Z> on Z and S<S<T>> on S, but I couldn't make it work either...

Any ideas? :(

Have you read [Where and why do I have to put the “template” and “typename” keywords?](http://stackoverflow.com/questions/610245/where-and-why-do-i-have-to-put-the-template-and-typename-keywords) as suggested in the Related bar (now linked)? — dyp, Feb 13 '14 at 15:46
@dyp, I actually read that, but didn't manage to make it work anyways. And @Jarod42, `S>` didn't compile, and that's what I didn't understand why. — paulotorrens, Feb 13 '14 at 15:49
Can you provide the context of how and where you use `S>`? Preferably as an [SSCCE](http://sscce.org). — dyp, Feb 13 '14 at 15:50
@dyp, here: http://pastebin.com/swHVyzCB. I read some posts here on Stackoverflow, like the one you gave, but I still don't understand why `S>` won't work there. — paulotorrens, Feb 13 '14 at 15:55
Problem is somewhere different: http://coliru.stacked-crooked.com/a/f8b1b778f3a2e4db You forgot the `replace` inside `I` — dyp, Feb 13 '14 at 15:58
Oh God, you're right! My code would work if I did _2::replace<_2>, and would correctly sum to 4. I just got so confused by the errors the compiler gave me that forgot to check what I really wanted... embarassing. If you post an answer, I will accept it. And thanks for the help! :) — paulotorrens, Feb 13 '14 at 16:01
@PauloTorrens That shouldn't be embarrassing, understanding error messages related to templates can be hard ;) — dyp, Feb 13 '14 at 16:02
@PauloTorrens: An alternative to dyp's solution: http://coliru.stacked-crooked.com/a/b146d7835ab5dd9f. So `S::replace` is removed by SFINAE. — Jarod42, Feb 13 '14 at 16:23

ecatmur · Answer 1 · 2014-02-13T16:02:41.257

Church numerals have an arity of 2; they take a functor and a value and apply the functor n times to the value. In metaprogramming, this can be expressed as a template with 2 template parameters, the first of which is a template template parameter:

struct Z {
  template<template<typename> class F, typename x>
  using replace = x;
};

template<typename T>
struct S {
  template<template<typename> class F, typename x>
  using replace = F<typename T::template replace<F, x>>;
};

We can test this with F as the successor function on integral_constants (which aren't really values in the lambda calculus, but it doesn't care about that):

#include <type_traits>
template<typename N> using s = typename std::integral_constant<typename N::value_type, N::value + 1>;
static_assert(S<S<Z>>::replace<s, std::integral_constant<int, 2>>::value == 4, "arithmetic!");

If you want to curry replace, the syntax becomes somewhat more complex:

struct Z {
  template<template<typename> class F> struct replace {
    template<typename x> using apply = x;
  };
};

template<typename T>
struct S {
  template<template<typename> class F> struct replace {
    template<typename x> using apply = F<typename T::template replace<F>::template apply<x>>;
  };
};

Strictly speaking, by taking template template parameters we're introducing a distinction (between functors and values) that is absent in the untyped lambda calculus. The way to fix that is to have our functors as typename parameters containing the application machinery:

struct Z {
  template<typename F> struct replace {
    template<typename x> using apply = x;
  };
};

template<typename T>
struct S {
  template<typename F> struct replace {
    template<typename x> using apply = typename F::template apply<typename T::template replace<F>::template apply<x>>;
  };
};

And the demonstration:

#include <type_traits>
struct s { template<typename N> using apply = typename std::integral_constant<typename N::value_type, N::value + 1>; };
static_assert(S<S<Z>>::replace<s>::template apply<std::integral_constant<int, 2>>::value == 4, "arithmetic!");

Though you are right, my doubt was really about why I couldn't use `S>`, and @dyp just showed me that, although the error messages said something different, the error was because I was trying to use a class without replace<>. Thanks anyway, you got an interesting answer. :) — paulotorrens, Feb 13 '14 at 16:04

Dependent template name argument substitution

1 Answers1