The UNIFICATION TEMPLATES Sub-language
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>)})}*
[&allow-other-keys]]
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: