Control Flow

In order to make the use of the UNIFICATION library easier, a few utility macros are provided. The macros MATCH, MATCHING, and MATCH-CASE can be used to unify two (or more) objects and then to build a lexical environment where the variables present in the to objects (or templates) are bound to the values resulting from the application of UNIFY.

• MATCH is a "single shot" macro. It does one unification and executes forms in an appropriate lexical environment.
• MATCH-CASE is equivalent to CASE. It tries to match a single object (or template) against a set of clauses. The forms associated to the first clause for which there is a successful unification, are then executed within an appropriate lexical environment.
• MATCHING is equivalent to COND. Each clause contains a head

  Examples

  These macros allow the construction of interesting pattern matching like code.

    (defun factorial (x)
      (match-case (x)
        (0 1)
        (#T(number ?n) (* ?n (factorial (1- ?n))))
        (otherwise (error "Incorrect match for ~S." x))))
    

  Or consider the more interesting piece of code from a not-so hypothetical Red-Black tree implementation (cfr. [O98].) The function BALANCE is the key part of the rebalancing act played by Red-Black trees.

    (defstruct (tree-node (:conc-name tn-)
                          (:constructor mk-tn (color left elem right)))
       color
       left
       elem
       right)
  
    (defun balance (&rest balancing-arguments)
      (match-case (balancing-arguments)
        ((:black #T(tree-node tn-color :red
                              tn-left #T(tree-node tn-color :red
                                                   tn-left ?a
                                                   tn-elem ?x
                                                   tn-right ?b)
                              tn-elem ?y
                              tn-right ?c)
                 ?z
                 ?d)
          (mk-tn :red (mk-tn :black ?a ?x ?b) ?y (mk-tn :black ?c ?z ?d)))
        ((:black #T(tree-node tn-color :red
                              tn-left ?a
                              tn-elem ?x
                              tn-right #T(tree-node tn-color :red
                                                    tn-left ?b
                                                    tn-elem ?y
                                                    tn-right ?c))
                 ?z
                 ?d)
          (mk-tn :red (mk-tn :black ?a ?x ?b) ?y (mk-tn :black ?c ?z ?d)))
        ((:black ?a
                 ?x
                 #T(tree-node tn-color :red
                              tn-left #T(tree-node tn-color :red
                                                   tn-left ?b
                                                   tn-elem ?y
                                                   tn-right ?c)
                              tn-elem ?z
                              tn-right ?d))
          (mk-tn :red (mk-tn :black ?a ?x ?b) ?y (mk-tn :black ?c ?z ?d)))
        ((:black ?a
                 ?x
                 #T(tree-node tn-color :red
                              tn-left ?b
                              tn-elem ?y
                              tn-left #T(tree-node tn-color :red
                                                   tn-left ?c
                                                   tn-elem ?z
                                                   tn-right ?d)))
          (mk-tn :red (mk-tn :black ?a ?x ?b) ?y (mk-tn :black ?c ?z ?d)))
        ((?color ?left ?elem ?right)
          (mk-tn ?color ?left ?elem ?right))))
    

  This version of BALANCE is more verbose than the one given in [O98], but it preserves the general elegance of the ML implementation.

  Control Flow Dictionary

  • Macro MATCH
  • Macro MATCHING
  • Macro MATCH-CASE

  Notes

  Other Forms

  It would be obvious to add the macros EMATCH-CASE and CMATCH-CASE, for symmetry with ECASE and CCASE. Also, MATCHING could be renamed to MATCH-COND.

  Current Implementation Details

  The current implementations of MATCHING and MATCH-CASE do not handle user supplied environments yet.

  References

  [O98] C. Okasaki, Purely Functional Data Structures, Cambridge University Press, 1998.

  Site Map

  Enjoy!

  ---

  Questions? Queries? Suggestions? Comments? Please direct them at me.