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

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.

CL Extensions: CONTROL FLOW Home \| Downloads \| Links
	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.

© 2003-2011, Marco Antoniotti, all rights reserved.