Use Patterns

2/26/2006 6:34:15 AM

Use Patterns

The next version of C++0x introduces a new feature called “concepts” to improve template metaprogramming. Concepts are based on “use patterns,” a powerful yet simple technique for compilers writers to enhance a programming language easily without adding new syntax.

concept Mutable_fw<typename Iter, typename T> {
    Var<Iter> p; // a variable of type Iter.
    Var<const T> v; // a variable of type const T.
    Iter q = p; // an Iter must be copy-able 
    bool b = (p != q); // must support ‘‘!=’’ operation,
                       // and the resulting expression
                       // must be convertible to ‘‘bool’’
    ++p; // must support pre-increment, no
         // requirements on the result type
    *p = v; // must be able to dereference p,
            // and assign a ‘‘const T’’ to the
            // result of that dereference; no
            // requirements on the result type

A C++ concept indicates what operations must be supported by a type simply by its use within the body of the concept. The body of a concept is syntactically identical to that of a method. The compiler reuses the same rules for parsing methods to parse concepts and automatically infer constraints on types. The compiler defers processing of steps such as type checking until the type deriving from the concept is known. Once the type is known, the compiler confirms the type matches the concept by applying type-specific conversions (both inherited and custom) and method resolution.

The alternative of constructing explicit signatures leads to combinatorial explosion in the possible ways a compiler can match an expression. The C++ paper refers specifically to the various ways in which the plus operator can be invoked by a compiler.

+ // built-in operation for X
X operator+(X,X);
X operator+(const X&, const X&);
X X::operator+(const X&) const;
X X::operator+(X);
const X& X::operator+(const X&);
const N& operator+(const& N, const N&); // X converts to N
X operator+(X, N); // N converts to X

“Use patterns” reduces the complexity of compiler writing, but also benefits language consumers by providing a compact, natural and direct syntax with no new syntax or learning involved.

I have been relying on the technique of “use patterns” in my AI and natural language work, including my rules language in NStatic.

Indeed, it’s a common technique used in symbolic programming, which templates somewhat resembles because of the way functions contained within templates are invoked by name. Unification and pattern matching in Prolog(and other languages are fundamentally based on the notions of “use patterns.”

In my natural language work, the definitions of new words are automatically inferred from usage in a few different ways.

  1. From context. The meaning is automatically inferred from its use within a sentence by analyzing the semantic dependency graph generated from a parse of the sentence.
  2. From natural-language definition. Alternatively, a person (usually a template designer) can define a word using a plain, simple natural-language definition of the word, and the relationships and properties of the word are automatically inferred from the possible usage of the definition itself.

“Use patterns” in natural language programming means that the user never needs to know a special syntax, just English.






Net Undocumented is a blog about the internals of .NET including Xamarin implementations. Other topics include managed and web languages (C#, C++, Javascript), computer science theory, software engineering and software entrepreneurship.

Social Media