What is struct NIL { typedef NIL Head; }?

Question

I am reading about template metaprogramming. I could not understand what these lines mean; the following code concerns about doing metaprogramming on a linked list.

struct NIL {
typedef NIL Head;
typedef NIL Tail;
};

template <typename H, typename T=NIL> struct Lst {
    typedef H Head;
    typedef T Tail;
};

template <int N> struct Int{ static const int result = N; };
typedef Lst< Int<1>, Lst< Int<2>, Lst< Int<3> > > > OneTwoThree;

The above is coming from https://monoinfinito.wordpress.com/series/introduction-to-c-template-metaprogramming/ . I would greatly appreciate any guidance as to what it means to have struct NIL, which has typedef NIL Head, and typedef NIL Tail. Nil is a type, sure, but if I have typedef NIL Head, for example, does it mean i have another recursive Head and Tail within each Head?

Hull

There's a joke to be made about NILism in here somewhere. – Kenner

I've seen some bad names in my time, but NIL is right up there as award-winningly bad. That name is astonishingly misleading. Anyone who recommends doing this is a mad scientist, and I don't mean the good kind. – Steeple

Presumably it stands for Node in List, but you're far better off spelling it out as NodeInList rather than NIL – Ownership

@Steeple it's actually a pretty common name for NULL-like stuff, it's used in LISP and Lua (although here the inspiration is clearly LISP). – Superposition

In C++11 and later one typically uses std::tuple instantiations as type lists. The techniques from Modern C++ (and the Loki library) are no longer very relevant. You would do well to get a book from after 2011. – Cartoon

@Steeple "Nil" has been the established name for the empty list for well over fifty years. – Donate

@Ownership No, it means "nothing", and has for over five hundred years. – Donate

@Donate Exactly why making a class called NIL that is not that is a bad idea. – Steeple

@MatteoItalia This class is not in any way a "NULL-like" anything, that's why it's a bad idea. – Steeple

@Steeple It's a type that represents the empty (type-level) list of types, so it's a good name. Of course, Lst should be renamed Cons, and Head and Tail should be Car and Cdr... – Donate

Answer 1

No, typedef NIL Head; doesn't mean you have a NIL within each NIL.

It simply means NIL::Head is another name for NIL. Ditto for NIL::Tail.

This does mean you can write the types recursively, for example NIL::Head::Tail::Tail::Tail::Head::Head is also a name for NIL. However there's no actual recursive type here.

Dochandorrach

FYI @Hull if you feel this answer answers your completely unequivocally, you can mark it as the accepted answer by pressing the tick. – Ownership

Answer 2

NIL is just another name for nothing.

It isn't NULL because that was taken.

Here, we are creating a LISP like linked list of "head" and "tail". To represent the end of the list, place a NIL.

NIL satisfies the layout of a list, but one with both head and tail being NIL. Myself I'd be tempted to have written:

struct NIL;

template <typename H, typename T=NIL> struct Lst {
  typedef H Head;
  typedef T Tail;
};

struct NIL:Lst{};

to make NIL as the name of the empty list more clear.

By making NIL have head & tail, some template metaprogramming becomes easier (and some becomes harder). The fact that they are the same type does mean that in one sense the NIL list has an infinite length; but in another sense it has zero length, as we define length to be the distance until we reach NIL.

typedefs are not "within" the type, they are defined inside like how data members are. They are more like pointers than members. In non template metaprogramming:

struct node {
  node* head, *tail;
};
struct NIL:node{
  NIL() : node{this, this} {}
};

Crocus

It's "nil" because "nil" is a noun and "null" is an adjective. – Donate