%% $Id$ %% ACM SIGPLAN Notices, nov 1989 \documentclass[a4paper,11pt]{article} \usepackage[a4paper,hmargin=2cm,vmargin=2.5cm]{geometry} \usepackage{amsmath} \usepackage{amssymb} \title{Recursive Pattern Matching on Concrete Data Types \\ \emph{with appendix}} \author{\emph{Pierre Jouvelot} \\ CAI, Ecole des Mines de Paris, Fontainebleau (F.) \\ LCS, Massachusetts Institute of Technology, Cambridge (U.S.A.) \\ ({\small E-mail: \texttt{jouvelot@\{fremp11.bitnet,brokaw.lcs.mit.edu\}}}) \\ \\ \emph{Babak Dehbonei} \\ Corporate Research Center, BULL, Louveciennes (F.) \\ ({\small E-mail: \texttt{Babak.Dehbonei@crg.bull.fr}})} \date{ACM SIGPLAN Notices, Vol 24, Issue 11, Nov 1989, pp 84--91} \newcommand{\rpm}{\texttt{rpm}} \newcommand{\E}{\mbox{${\cal E}$}} \newcommand{\C}{\mbox{${\cal C}$}} \renewcommand{\P}{\mbox{${\cal P}$}} \newcommand{\dbl}[1]{\mbox{$\lbrack\!\lbrack$~\texttt{#1}~$\rbrack\!\rbrack$}} \newcommand{\Exp}{{\rm Expression}} \newcommand{\Ide}{{\rm Identifier}} \newcommand{\Cl}{{\rm Clause}} \newcommand{\Pat}{{\rm Pattern}} \newcommand{\QED}{\hfill\(\Box\)} \begin{document} \maketitle \section{Introduction} The functional programming model favors recursive definitions of functions by structural induction over user-defined concrete data types. Most functional languages (e.g., Lisp, ML, Miranda, Haskell) offer powerful programming constructs that ease the writing of programs based on this idea; destructuring \texttt{let}, {\tt multiple-value-bind},... We propose an extension to the usual notion of pattern-matching, called \emph{Recursive Pattern Matching}. Our motivation is based on the observation that most real-life data types are recursive, e.g. abstract syntax trees, control graphs, ... Consequently, many functions that manipulate these data types are recursive. The RPM technique combines pattern-based dispatching and recursive function calls on subcomponents of complex values. This technique has been successfully used on a large scale inside the Velour project. This vectorizing and parallelizing compiler is 11,000 LeLisp lines long and most of its modules use recursive pattern matching on abstract syntax trees. Compared to a first version of Velour that didn't use recursive pattern matching, we observed a 20 to 30 per cent decrease\footnote{This imprecision comes from the fact that the second version of Velour also introduced numerous enhancements that influenced the code size.} in the size of the code, without significant performance penalty. Like any structuring concept, we also noticed that its usage entailed a substantial reduction in the number of design and coding errors. In the remainder of this paper, we survey the related work (section 2), define precisely the notion of recursive pattern matching (section 3), give a set of simple examples (section 4), investigate further improvements (section 5) and conclude (section 6). An appendix provides a complete CommonLISP implementation of RPM. \section{Related Work} Pattern matching is an important facility provided by many modern programming languages. Basically, once a given data type (seen in this framework as a set of functions that allow the manipulation of values of this type) has been defined, patterns (i.e., expressions that involve data type functions and unbound variables) can appear as left hand sides of any binding construct; the net effect is to bind the variables to the corresponding values in the right hand side. The right hand side value has to match the corresponding pattern. The simplest way of using this technique is given in many widely used imperative languages. In Pascal [JW85], the \texttt{case} command allows the programmer to execute statements according to the value of an integer or an enumerated variable. In the C programming language [KR78], an equivalent treatment is performed on integer expressions using the \texttt{switch} statement. However, these matching possibilities are not sufficiently powerful to be applied on more abstract data. In Lisp-like languages [St84], a flavor of abstract pattern matching is present for structured lists or trees. This is performed on function calls or macro expansions with the dotted notation or the CommonLISP keywords (e.g., \texttt{\&rest}, \texttt{\&optional}). A more sophisticated technique is used in the ML functional language [M83]. It is performed on expressions that have (possibly recursive) sum types over a set of available types. An example will clarify this approach: \begin{verbatim} #rectype Num = # zero | # succ of Num ;; \end{verbatim} The recursive \texttt{Num} type denotes the set of positive or null integers. We can then define a function \texttt{Add} that computes the sum of two values (given in a pair argument) of type \texttt{Num}. \begin{verbatim} #letrec sum = fun # (zero,Y). Y | # (succ X,Y). sum (X, succ Y) ;; \end{verbatim} The matching is performed on the two type constructors \texttt{zero} and \texttt{succ} of \texttt{Num}; this is usually implemented by a one-way unification routine. The mechanism of \emph{views} has been proposed for matching expression that have an abstract data type [W87]. This allows the programmer to use pattern-matching without losing the abstraction. Changing the implementation of an abstract data type won't require any modification of programs that import this type (this wouldn't be the case with the ML kind of matching which is concrete). An external (resp. internal) description of an abstract value is given through the attribute {\em out} (resp. \emph{in}) in the data type definition. For instance, an integer can be seen as: \begin{verbatim} view int ::= Zero | Succ int in n = Zero if n=0 = Succ(n-1) if n > 0 out Zero = 0 out (Succ n) = n+1 \end{verbatim} In this example, the abstract definition of an integer has a concrete description that is the corresponding integer number. The pattern matching is performed on this concrete version of the data type via the abstract functions. A very similar notion to our pattern facility has been recently introduced in [J87]. This approach is based on the attribute grammar paradigm applied to LML, a lazy version of ML. A recursive control structure called \texttt{case rec} is introduced to traverse concrete data structures and compute attributes; this construct is complex (not restricted to non-circular grammars) and was not implemented at that time. Furthermore, it relies heavily on the laziness of LML since it doesn't restrict the attributes computation in the way our construct does. Several other studies have also been made in the context of actor languages. These languages define pattern matching operators as higher level objects. Backtracking is also allowed in this scheme to accomodate constraints that might be defined on patterns. %For instance, suppose %that instead of matching the first element of a list, the last element %is matched. A lisp simulated form of this example is: %\begin{verbatim} %(defun foo ((l x) y) % (..)) %\end{verbatim} %where the function \texttt{l} represents the last element of a list. The %matching is performed by multiple visits over the structure of the %calling argument. This search can be successfully terminated or can %lead to a fail on the structure of the calling argument. \section{Recursive Pattern Matching} Recursive pattern matching is a language-independant notion. It can be used in any functional language that supports structured concrete data types. \subsection{Type Notation} A concrete type \texttt{T} can either be a basic type (like \texttt{Int} or \texttt{Bool}) or a constructed type. A constructed type is a sum of product types (i.e., disjoint unions of structures with multiple members like \texttt{t1:T1 + t2:(T2 $\times$ T3)}). We assume that each value of sum type \texttt{T} with tag \texttt{t} satisfies the run-time predicate $has\_tag_t$; this means that tags (representing types) are carried around by the underlying implementation. For every sum type \texttt{T}, the function \emph{untag} retrieves the untagged component of the value. For every product type \texttt{T} that has {\tt T1} as component, there exists a function \texttt{T\_T1} that retrieves the component of type \texttt{T1} in an object of type \texttt{T}. \subsection{Definition of RPM} The core of the RPM technique is a special form, called \rpm. Its BNF syntax is the following: \begin{tabbing} \texttt{rpm}~~~~~~\=::= \texttt{(rpm} root Clause*\texttt{)} \\ root \>::= Expression \\ Clause \>::= \texttt{(}Pattern body\texttt{ )} \\ Pattern \>::= \texttt{(}head member*\texttt{)} \\ head \>::= Identifier \\ member \>::= Identifier \\ body \>::= Expression* \end{tabbing} where \emph{item}* represents a non-empty list of \emph{item}, Identifier is a Lisp symbol and Expression any Lisp expression. Recursive pattern matching performs a recursive traversal of a tree-shaped concrete data type. The fundamental characteristic of \rpm\ is to hide the recursive invocations inside the very definition of the patterns. Namely, whenever a member appears in a clause, then its value in the corresponding body is the result of the recursive call on the member instead of the more usual member value. The informal semantics of an \rpm\ expression is the following. First, the root expression is evaluated; its value $v$ is a structured value of type $t$ which has to be one of the different heads of the list of clauses. Each clause with pattern $p$ is successively checked to see whether $t$ matches $p$, i.e. the head $h$ of $p$ equals $t$. The first clause $c$ that succeeds is chosen (if none, an error is reported). The result of the evaluation of the list of expressions inside $c$ in an augmented environment is returned. The augmented environment is defined as follows: $h$ is bound to $(untag v)$ and each member $m$ is bound to the result of the recursive evaluation of the whole process on the value \texttt{($h$\_$m$ $(\emph{untag} v$))} where {\tt $h$\_$m$} is the function that retrieves the $m$ component of a value of type $h$. The formal semantics of \rpm\ is given below with a denotational flavor; without loss of generality, we used a restricted version of \rpm\ that limits the number of clauses to two and allows only one member in a pattern and one expression in each clause. The standard direct semantics $\E$ of any functional language is extended with the semantics of \rpm. It uses a function \C\ that takes two continuations: the first one is used once a pattern matches with the value and the second one allows the trial of subsequent clauses (or failure). The semantics of the pattern matching process is the function $\P$. We give below the types of these functions: \begin{eqnarray*} &&\E : \Exp \rightarrow Store \rightarrow Result \\ &&\C : \Cl \times \Cl \rightarrow Value \rightarrow Cont \rightarrow Cont \rightarrow Store \rightarrow Result \\ &&\P : \Pat \rightarrow Value \rightarrow (\Ide \times \Ide \times Value) \\ &&Cont : Value \rightarrow Store \rightarrow Result \\ && Result : (Value + {\bf error}) \end{eqnarray*} The semantic equations are the following: \begin{tabbing} $\E\dbl{rpm E C1 C2}s = \C\dbl{C1 C2}(\E\dbl{E}s)(\lambda vs.v)(\lambda vs.{\bf error})s $\\ $\C\dbl{C1 C2}vk_1k_2s = \C\dbl{C1}v$\=$(\lambda vs.\C\dbl{C1 C2}vk_1k_2s)$ \\ \>$(\lambda vs.\C\dbl{C2}v(\lambda vs.\C\dbl{C1 C2}vk_1k_2s) (\lambda vs.{\bf error}))s$ \\ $\C\dbl{P E}vk_1k_2s =$ \=${\rm let}~\texttt{Id1},\texttt{Id2},a = \P\dbl{P}~{\rm in}$\\ \>${\rm if}~has\_tag_{Id1}(v)~{\rm then}~ \E\dbl{E}[\emph{untag}~v/\texttt{Id1}][k_1 (a(\emph{untag}~v)) s/\texttt{Id2}]s~ {\rm else}~k_2 v s$ \\ $\P\dbl{(Id1 Id2)} = \texttt{Id1}, \texttt{Id2}, \texttt{Id1\_Id2}$ \end{tabbing} where \texttt{Id1\_Id2} is the function that returns the \texttt{Id2} member of a value of type \texttt{Id1}. Note the recursive behavior of \rpm\ pictured in the use of $\C\dbl{C1 C2}$ in its own definition. \subsection{RPM Computes Primitive Recursive Functions} The purpose of this section is to prove that the RPM technique has the expressive power of primitive recursion. ~~~\\ ~~~\\ \noindent {\bf Definition} [C87]. A function $f$ of arity $n$ is defined by \emph{primitive recursion} over the functions $g$ and $h$ if and only if: \begin{itemize} \item $f(x_1,...,x_ n) = g(x_1,...,x_n)$ if $x_n = 0$, \item $h(x_1,...,x_n,f(x_1,...,x_n-1)$ otherwise \end{itemize} \noindent {\bf Theorem} \emph{Any primitive recursive function f can be encoded with \rpm\ without recursion.} ~~\\ ~~\\ \noindent {\bf Proof}. Let \texttt{Num} be the recursive concrete type {\tt Zero + Succ:Num}. %% Let $f'$ be the curried function such that $f'(x_n)(x_1,..,x_{n-1}) = f(x_1,...,x_n)$. By definition, if $x_n$ is \texttt{Zero} we have: \[f'(x_n) = \lambda x_1,..,x_{n-1} . g(x_1,..,x_n)\] and if $x_n$ is the successor of $y$ (i.e., $y = \texttt{Num-Succ}~ x_n$): \[f'(x_n) = \lambda x_1,..,x_{n-1} . h(x_1,...,x_n,f'(y)(x_1,...,x_{n-1})) \] Thus, by definition of \rpm: \begin{tabbing} $f'(x_n) = \rpm~$\=$x_n$ \\ \>$((\texttt{Zero})~ \lambda x_1,..,x_{n-1} . g(x_1,..,x_n))$ \\ \>$((\texttt{Succ~Num})~ \lambda x_1,..,x_{n-1} . h(x_1,...,\texttt{Succ},\texttt{Num}(x_1,...,x_{n-1})))$ \end{tabbing} Inside the body of the second clause, \texttt{Succ} is bound to the current value of $x_n$ and \texttt{Num} denotes the result of the recursive invocation of $f'$ on $y$ if $y = \texttt{Num-Succ}~x_n$. We can define $f$ in the following way: \begin{tabbing} $f(x_1,...,x_n) = (\rpm~$\=$x_n$ \\ \>$((\texttt{Zero})~ \lambda x_1,..,x_{n-1} . g(x_1,..,x_n))$ \\ \>$((\texttt{Succ~ Num})~ \lambda x_1,..,x_{n-1} . h(x_1,...,\texttt{Succ},{\tt Num}(x_1,...,x_{n-1})))$ \\ \> $x_1 ... x_{n-1})$ \end{tabbing} The formal proof of equivalence between these two forms is straightforward and left to the reader. \QED Note that we supposed that concrete types were not circular. If we relax this restriction (i.e., we quit the pure functional paradigm) or allow abstract types instead of concrete types, then partial recursion can be encoded with \rpm. The idea is to use the potentially infinite traversal on a circular value to implement the minimization operator of partial recursion. Recall that any recursive function (i.e., partial recursive) can be coded with composition of functions, projections, primitive recursion and minimization. Thus, \rpm\ codes for any recursive function. \subsection{RPM with CPS} RPM allows the recursive definition of expressions where more than one argument is needed. The trick to adapt \rpm\ to this requirement is to use higher-order functions in a way reminiscent of the Continuation Passing Style [St77]. Basically, each clause returns a function that is abstracted over these arguments and it is up to the caller (i.e., the previous clause in the dynamic call sequence) to provide the appropriate parameter values. This can also be used each time a clause treatment requires some inherited values from its caller. The very definition of \rpm\ is bottom-up and using this ``CPS''-like programming paradigm is a way to simulate a top-down behavior. We found this twist very successful in our practical experiments and easy to use (once assimilated by programmers !). \section{Examples} In the sequel, we will use the CommonLISP notation; product types are coded by \texttt{defstruct}, sum types by a corresponding \texttt{deftype} with an \texttt{or} constructor and basic types by the underlying implementation. We present three simple examples that use the \rpm\ package provided in the Appendix: a factorial function, the computation of the free variables of a $\lambda$-expression and a Lambda-Calculus evaluator. \subsection{Factorial} The computation of the factorial of an integer number is an elementary example where the power of our \rpm\ function is shown. Let us first define the type of integer numbers and some functions on them: \begin{verbatim} (defsum num zero succ) (defproduct zero) (defproduct succ (of :type num)) (defconstant num-1 (make-succ :of (make-zero))) (declare (function num-product (num num) num)) \end{verbatim} where \texttt{num} is either a \texttt{zero} or a \texttt{succ} with a unique member \texttt{of} which is a \texttt{num}. For convenience, we defined \texttt{num-1} and declared the product function on \texttt{nums} (the code of which is left as an exercise to the reader). The \rpm\ version of factorial on values of type \texttt{num} is the following: \begin{verbatim} (defun factorial (num) (rpm num ((zero) num-1) ((succ of) (num-product succ of)))) \end{verbatim} which can be used in the following way : \begin{verbatim} -> (fact (make-succ :of (make-succ :of (make-zero)))) #(succ #(succ #(zero))) \end{verbatim} Note that unlike other programming techniques, there is no explicit recursive call to \texttt{factorial}; it is embedded inside the \rpm\ macro. \subsection{Free Variables of Lambda Expressions} The Lambda-Calculus manipulates $\lambda$-expressions. Its syntax is : \begin{verbatim} (defsum lambda-expression variable application abstraction) (defproduct variable (name :type string)) (defproduct application (operator :type lambda-expression) (operand :type lambda-expression)) (defproduct abstraction (variable :type variable) (body :type lambda-expression)) (declare (function variable= (variable variable) t)) \end{verbatim} A $\lambda$-expression is either a variable, an application of two $\lambda$-expressions or an anonymous function with a bound variable as formal argument and a $\lambda$-expression as body (abstraction). We introduce the notion of a free variable in a $\lambda$-expression by structural induction on the domain of $\lambda$-expressions: {~~~~~}\\ ~~~~~\\ \noindent{\bf Definition} [S77] A variable \texttt{x} \emph{occurs free} in a $\lambda$-expression \texttt{E} if and only if: \begin{itemize} \item \texttt{E} is \texttt{x}, \item \texttt{E} is \texttt{(E${}_1$ E${}_2$)} and \texttt{x} occurs free in \texttt{E${}_1$} or \texttt{E${}_2$} \item \texttt{E} is \texttt{(lambda V E)}, \texttt{x} and \texttt{V} are different and \texttt{x} occurs free in \texttt{E} \end{itemize} \noindent We define the function that computes the set of all free variables present in a $\lambda$-expression: \begin{verbatim} (defun free-variables (expression) (rpm expression ((variable) `(,variable)) ((application operand operator) `(,@operand ,@operator)) ((abstraction body) (remove (abstraction-variable abstraction) body :test #'variable=)))) \end{verbatim} Each clause returns a list of variables after applying the appropriate treatment (e.g., removing the bound variable from the list of free variables of the body of an abstraction). \subsection{A Lambda-Calculus Evaluator} We will use the previous data type and associated functions to write a simple evaluator of $\lambda$-expressions. This will be the occasion of using higher order functions as a means to deal with arguments; the \texttt{evaluate} function takes, beside the expression, a \texttt{store} that maps variables to \texttt{num} values (for instance). We used the \texttt{[} macro character to wrap the special form \texttt{funcall} around the arguments (see Appendix). They wouldn't be required if we used a one-namespace language like Scheme. \begin{verbatim} (defun update-store (value variable store) #'(lambda (v) (if (variable= v variable) value [store v]))) (defun evaluate (expression store) [(rpm expression ((variable) #'(lambda (store) [store variable])) ((application operand operator) #'(lambda (store) [[operator store] [operand store]])) ((abstraction body) #'(lambda (store) #'(lambda (value) [body (update-store value (abstraction-variable abstraction) store)])))) store]) \end{verbatim} The function \texttt{update-store} updates the store (which is a function) to bind the value to the variable. The constant \texttt{init-store} denotes an empty store. The core function \texttt{evaluate} evaluates an expression in a given store. The key idea is that each clause in the \rpm\ macro returns a function that maps stores to values. We give below a simple example that evaluates \texttt{((lambda (x) x) 1)} in an empty initial store: \begin{verbatim} -> (let* ((x (make-variable :name "x")) (y (make-variable :name "y")) (f (make-abstraction :variable x :body x))) (evaluate (make-application :operator f :operand y) (update-store num-1 y #'(lambda (variable) :unbound)))) #(succ #(zero)) \end{verbatim} \section{Future Work} There are many improvements that can be added to this current definition of the \rpm\ special form: \begin{itemize} \item multiple values could be returned by \rpm. Actually the extended version of \rpm\ used in the Velour project allows such an extension. \item more general patterns that are not limited to direct subcomponents could be introduced. For instance, one might want to perform the recursive calls on specific deeper subtrees instead of being limited to just a one-level recursion. The implementation provided in the Appendix includes a limited version of this idea; if a subcomponent on which a recursive call has to be performed happens to be a list, the recursive process is mapped on each element of the list and a list of results is returned. This could also be applied to vectors. \item a default pattern could be introduced (\emph{a la} \texttt{\_} of ML) to trap the values that didn't match any of the clauses. \end{itemize} \section{Conclusion} Recursive Pattern Matching is a programming technique that combines the advantages of simple pattern matching on structured values and recursive function definition. It has been widely used in the development of a vectorizing compiler prototype and proved quite powerful and useful. A portable CommonLISP implementation of \rpm\ is provided. \section*{Acknowledgements} We would like to thank Vincent Dornic for pointing out the quite relevant paper [J87]. \section*{References} \begin{description} \item[\mbox{[C87]}] Cohen, D.E \emph{Computability and Logic}. Ellis Horwood, Halstead Press, J.Wiley and Sons, New York 1987 \item[\mbox{[JW85]}] Jensen, K., and Wirth, N. \emph{The Pascal User Manual and Report}. Third Edition, Springer-Verlag, New York 1985 \item[\mbox{[J87]}] Johnsson, T. Attribute Grammars as a Functional Programming Paradigm. In the \emph{Proceedings of the 1987 Int. Conf. on Func. Prog. Lang. and Comp. Arch.}, Portland, 1987 \item[\mbox{[M83]}] Milner, R. A Proposal for Standard ML. \emph{Polymorphism Letters I}, Bell Labs, 1983. \item[\mbox{[KR78]}] Kernighan, B., and Ritchie, D. \emph{The C Programming Language}. Prentice-Hall, 1978. \item[\mbox{[S77]}] Stoy, J. E. \emph{Denotational Semantics: the Scott-Strachey Approach to Programming Language Theory}. MIT Press, 1977. \item[\mbox{[St84]}] Steele, G. L., Jr. \emph{CommonLISP: The Language}. Digital Press, 1984. \item[\mbox{[St77]}] Steele, G.L., Jr. \emph{Rabbit}. MS Thesis, MIT AI Lab, 1977 \item[\mbox{[W87]}] Wadler, P. Views: A way for pattern matching to cohabit with data abstraction. In \emph{Proceedings of the Conference on Principles Of Programming Languages}. ACM, Munich, 1987. \end{description} \newpage \section*{Appendix: A CommonLISP Implementation of \rpm} {\small \begin{verbatim} ;; The "rpm" (Recursive Pattern Matching) macro package. ;; ;; IMPORTANT NOTE: The rpm macro can only be used on CommonLISP structures ;; that are implemented as named vectors. Use the following declaration ;; for that purpose: (defstruct (foo (:type vector) :named) ...). Without ;; this definition, the rpm package may (or may not) work depending on ;; a particular implementation of structures. We provide DEFSUM and ;; DEFPRODUCT macros that introduce these particular declarations. ;; ;; This software is provided without any guarantee. Any trouble can be ;; reported to jouvelot@brokaw.lcs.mit.edu or Babak.Dehbonei@crg.bull.fr. ;; ;; Copyright (C) 1989 - Pierre Jouvelot & Babak Dehbonei. (provide :rpm) (in-package :rpm) (export '(rpm defsum defproduct)) (deftype base-type () "The type of values that are self evaluating." '(or symbol integer float character string)) (defmacro defproduct (type &rest domains) "TYPE is the product domain of DOMAINS" `(defstruct (,type (:type vector) :named) ,@domains)) (defmacro defsum (type &rest domains) "TYPE is the sum domain of DOMAINS" `(deftype ,type '(or ,@domains))) ;; [ ... ] are used to hide funcalls. ;; (set-macro-character #\[ #'(lambda (stream char) `(funcall ,@(read-delimited-list #\] stream t)))) (set-macro-character #\] (get-macro-character #\) nil)) (defmacro rpm (object &rest clauses) "To recurse on the value OBJECT with the recursive pattern matching CLAUSES, use the following syntax: (rpm (( ... ) ) ...) Inside , is bound to the current value and to to i-th recursive call result of rpm on - on the current Newgen object. If the member is a list, then a list of results is returned." (let ((loop (gensym)) (obj (gensym))) `(labels ((,loop (,obj) (etypecase ,obj (base-type ,obj) (cons (mapcar #',loop ,obj)) (vector (cond ,@(rpm-clauses obj clauses loop)))))) (,loop ,object)))) (defun rpm-clauses (obj clauses loop) "Tests all the CLAUSES to find the first one that matches the type of the value OBJ. The recursive function to use for members is LOOP." `(,@(mapcar #'(lambda (clause) (let* ((pattern (car clause)) (head (car pattern))) `((,(intern (concatenate 'string (symbol-name (intern head)) "-P")) ,obj) (let ((,head ,obj) ,@(recurse-members head obj (cdr pattern) loop)) ,@(or (cdr clause) `((declare (ignore ,@pattern)))))))) clauses) (t (error "rpm: unknown value ~D" ,obj)))) (defun rpm-members (head obj members loop) "Creates the bindings of each element of MEMBERS to the return of the recursive call of LOOP on the MEMBER of OBJ (which is of type HEAD)." (mapcar #'(lambda (member) `(,member (,loop (,(intern (concatenate 'string (symbol-name (intern head)) "-" (symbol-name (intern member)))) ,obj)))) members)) \end{verbatim}% } \end{document}