パターンマッチみたいなことをするプログラムを書いてみた。

Common Lispです。
パターンマッチといっても、束縛する値のリストを連想リストとして返すだけなので、プログラムに応用するにはもう少し工夫が必要かもしれません。
できるだけ簡潔に書こうと思っていましたが、結局長くなってしまいました。

(defun zip-with (f a b)
  (if (or (null a) (null b))
    '()
    (cons (funcall f (car a) (car b)) (zip-with f (cdr a) (cdr b)))))

(defun any (f l)
  (if (null l)
    nil
    (if (funcall f (car l))
      t
      (any f (cdr l)))))

(defun flatten (x)
  (cond ((null x) nil)
        ((atom x) (list x))
        ((and (listp x) (not (listp (cdr x)))) (list x))
        (t (append (flatten (car x)) (flatten (cdr x))))))

(defun match-value (pat data)
  (cond ((symbolp pat)
         (cons pat data))
        ((and (atom pat) (atom data))
         (if (eql pat data) nil 'fail))
        ((and (listp pat) (listp data))
         (if (= (length pat) (length data))
           (zip-with #'match-value pat data)
           'fail))
        (t
          'fail)))

(defun match (pat data)
  (let ((result (match-value pat data)))
    (if (not (listp result))
      'fail
      (if (any (lambda (x) (eql 'fail x)) result)
        'fail
        (flatten result)))))

コードの説明

必要になったので、リスト操作関係の関数をいくつか作っています。もしかしたら標準ライブラリにもあったかもしれません。
関数zip-withは、二つのリストのそれぞれの要素に関数を適用して一つのリストを作る関数です。
anyは、リストの中に一つでも条件に合う要素があればt、一つも無ければnilを返す関数です。
flattenは少しだけオリジナル仕様です。ネストしたリストを平坦なリストにしますが、cdrがリストではないドット対はそのままにします。

match-valueがパターンマッチの本体ですが、返すリストはそのままでは使えないので、
match関数で連想リストに直しています。

使う

* (match '(1 2 a) '(1 2 3))

((A . 3))
* (match '(1 2 3) '(1 2 3))

NIL
* (match '(1 2 3) '(4 5 6))

FAIL
* (match '(1 (2 a) b (c d 3)) '(1 (2 1) 2 (3 4 3)))

((A . 1) (B . 2) (C . 3) (D . 4))

こんな感じです。成功した場合は連想リストかnil、失敗した場合はfailを返します。

追記

「(match '(a b) '(1 (2 3)))」のように、データのほうがネストしている場合に変なことになるというミスがありました。今度修正します