The unification machinery relies on a template sub-language to express structural patterns containing unification variables. The template sub-language comprises several objects organized in a hierarchy that parallels most of the standard CL type hierarchy.

Unification Variables

Unification variables are symbols with a #\? as the first character of the name. This is a rather traditional choice, although a different one based on quoted symbols is possible. Therefore, the following are examples of variables.

  ?A ?s ?qwe ?42z ?a-variable-with-a-very-long-name ?_
There are two special variables, ?_ and _, which are used as anonymous place holders, they match anything, but never appear in a substitution.

Destructuring Template Lambda List

CL has the concept of destructuring lambda list which is used in conjunction with the form DSTRUCTURING-BIND, and, to some extent, with LOOP. The unifier machinery relies on a related notion dubbed destructuring template lambda list for lack of a better name.

A destructuring template lambda list (or just template lambda list) is just like a regular destructuring lambda list (ANSI 3.4.5) with a number of restrictions. The full syntax is the following.

  template-lambda-list ::= (<reqvars> <optvars> <restvar> <keyvars>)
                       |   (<reqvars> <optvars> . <template>)

  reqvars ::= <template>*

  optvars ::= [&optional <template>*]

  restvar ::= [&rest <template>]

  keyvars ::= [&key {<template> | ({<template> | (<keyword-name> <template>)})}*

Where <template> is either an object with syntax defined in the next section or it can be a normal CL object. The remaining non terminal grammar symbols have the usual CL interpretation.

Unification Templates

The unification templates are organized in an object hierachy. There is a standard CLOS class for each template kind. The hierarchy is shown below.

The template hierarchy is rooted at the TEMPLATE class. There are two kinds of templates: type templates, and expression templates. Type templates are used as patterns of regular objects. Expression templates are used to unify against a specific sub-structure of a given object.

The predefined templates are: