Scheme
正規表現
2018-04-09

Scheme: 正規表現エンジンの原始的なやつ -- 拡張: 後方参照

≪前: Scheme: 正規表現エンジンの原始的なやつ -- 拡張: 汎用の要素クラス、汎用の位置指定メタ要素
次≫: Scheme: 正規表現エンジンの原始的なやつ -- 対象データの抽象化

「正規表現エンジンの原始的なやつ」をさらに拡張て後方参照の仕組みを入れた。事前に分かってたけどこの拡張はエンジン全体に影響する変更になった。

後方参照

ここで言う「後方参照」は既ににマッチしたものを後でまた使う仕組み全部のこと。《使う》には3種類ある。

  • 照合に使う —— 例: /(うち|よそ)\1/
  • 置換に使う —— 例: s/姓:"([^"]+)", 名:"([^"]+)"/&, 表示名:"\1 \2 様"/
  • 外で使う —— 例: $addr =~ /([^都道府県]+)[都道府県]/ ; $pref = $1 ; (Perl)

これを実現するにはパターン照合の途中過程のデータをどっかに保存しておいて、その後の照合処理で使えるようにしなきゃだ。

ぼくの正規表現エンジンの仕組み

今更だけどぼくの正規表現エンジンの仕組みを簡単に説明すると、ぼくの正規表現エンジンは基本的にはパターンの照合を複数の関数で分担してて、$\verb|Literal|$ 担当とか $\verb|Selective|$ 担当とか $\verb|At|$ 担当とかの関数があって、それらが仲人関数 Regex__match を介してお互いに委譲呼び出し(再帰呼び出し)してるんだ。

例えばこんなパターンの場合、

(
[Literal (#\鳴 #\か #\ぬ #\な #\ら)]
[Selective
  ([Literal (#\食 #\べ #\て #\し #\ま #\お #\う)])
  ([Literal (#\ヤ #\フ #\オ #\ク #\に #\出 #\そ #\う)])
  ([Literal (#\殺 #\し #\て #\し #\ま #\え)])
  ([Literal (#\鳴 #\か #\せ #\て #\み #\せ #\よ #\う)])
  ([Literal (#\鳴 #\く #\ま #\で #\待 #\と #\う)])
]
[Literal (#\ホ #\ト #\ト #\ギ #\ス)]
)

このパターンをリスト (#\鳴 #\か #\ぬ #\な #\ら #\鳴 #\か #\せ #\て #\み #\せ #\ #\よ #\う #\ホ #\ト #\ト #\ギ #\ス) に照合すると、こんな感じに移譲(再帰)呼び出しの連鎖になるんだ。

$$
\begin{array}\newline
{\tt Regex\_match}(入り口)\newline
\hspace{1cm}\rightleftharpoons\color{cyan}{\tt Regex\_\_match}\newline
\hspace{2cm}\rightleftharpoons\ {\tt Literal}\ 担当関数(鳴かぬなら、\color{blue}{局所的成功})\newline
\hspace{3cm}\color{blue}{\rightleftharpoons}\ \color{cyan}{\tt Regex\_\_match}\newline
\hspace{4cm}\rightleftharpoons\ {\tt Selective}\ 担当関数\newline
\hspace{5cm}\color{red}{\rightleftharpoons}\ \color{cyan}{\tt Regex\_\_match}\newline
\hspace{6cm}\color{red}{\rightleftharpoons}\ {\tt Literal}\ 担当関数(食べてしまおう、\color{red}{局所的失敗})\newline
\hspace{5cm}\color{red}{\rightleftharpoons}\ \color{cyan}{\tt Regex\_\_match}\newline
\hspace{6cm}\color{red}{\rightleftharpoons}\ {\tt Literal}\ 担当関数(ヤフオクに出そう、\color{red}{局所的失敗})\newline
\hspace{5cm}\color{red}{\rightleftharpoons}\ \color{cyan}{\tt Regex\_\_match}\newline
\hspace{6cm}\color{red}{\rightleftharpoons}\ {\tt Literal}\ 担当関数(殺してしまえ、\color{red}{局所的失敗})\newline
\hspace{5cm}\rightleftharpoons\ \color{cyan}{\tt Regex\_\_match}\newline
\hspace{6cm}\rightleftharpoons\ {\tt Literal}\ 担当関数(鳴かせてみせよう、\color{blue}{局所的成功})\newline
\hspace{7cm}\rightleftharpoons\ \color{cyan}{\tt Regex\_\_match}(入れ子の正規表現の終端、\color{blue}{局所的成功})\newline
\hspace{5cm}\color{blue}{\rightleftharpoons}\ \color{cyan}{\tt Regex\_\_match}\newline
\hspace{6cm}\rightleftharpoons\ {\tt Literal}\ 担当関数(ホトトギス、\color{blue}{局所的成功})\newline
\hspace{7cm}\color{blue}{\rightleftharpoons}\ \color{cyan}{\tt Regex\_\_match}(正規表現の終端、\color{blue}{大域的成功})\newline
\end{array}
$$

データは関数呼び出しで引数として与えるようになってて、大域変数は使わない(副作用のない純関数型)。それがぼくのエンジンの仕組みなんだ。

だもんで後方参照の機能を実現するときは、それまでの照合結果に自分が担当した照合の結果を書き加えた伝票みたいなデータ(オブジェクト)を次の委譲呼び出しの時に渡しさなきゃなんないの。つまり全部の関数の引数を一つ増やす必要があるんだ。

今回のエンジンでは伝票の内容はこんなだよっ。

  • カーソル位置
  • 以降は部分マッチの情報
    • 部分名1: (先頭位置1, 末尾位置1)
    • 部分名2: (先頭位置2, 末尾位置2)
      $\vdots$

実は、今回の拡張前までのエンジンは、担当関数はマッチの先頭位置を受け取ると自分のマッチした長さ(整数)を返すことになってて(マッチが失敗したときは ${\tt \#f}$ を返す)、呼び出した側で照合開始位置を足してマッチ範囲の末尾位置を計算してたんだ。だから入力と出力はどちらも整数型ではあるけど意味的には違うデータ型だった。

$$担当関数\ \ {\tt ::}\ \ カーソル位置 \longrightarrow マッチした長さ(または {\tt \#f})$$

それを今回は見直して、入力と出力どちらも同じ「伝票型」で意味的にも同じもの。

$$担当関数\ \ {\tt ::}\ \ 伝票 \longrightarrow 伝票(または {\tt \#f})$$

意図したわけぢゃないけど、この変更で各担当関数のコードもシンプルになった。${\tt Multiple}$ とか ${\tt Selective}$ みたいなコンテナ系のメタ要素は、自分自身で具体的なパターン照合作業をする性質のものぢゃないから、単に伝票をたらい回しするだけの形になった。

後方参照のメタ要素

世間一般の正規表現で後方参照する場合は参照したものを丸括弧 () でくくって、参照する時には参照したい先の開き丸括弧 ( の番号を使う。

だけどぼくの正規表現エンジンでは、参照したい先のパターンをメタ要素 ${\tt Let}$ に入れ子にして名前を付けておいて、それを参照するのにはメタ要素 ${\tt Ref}$ で名前を指定することにしたんだ。例えば最初に出した /(うち|よそ)は\1/ ならこんなふうになる。

(
[Let uchi-yoso 
    ([Selective
        ([Literal (#\う #\ち)])
        ([Literal (#\よ #\そ)])
    ])
]
[Literal (#\は)]
[Ref uchi-yoso]
)

Let 担当関数

まず、メタ要素 ${\tt Let}$ の形はこんなだよっ。

$${\tt((Let}\ \ name\ \ regex_{\tt Let}{\tt)\ \ .\ \ }tail_{\tt Let}{\tt)}$$

${\tt Let}$ 担当関数は、まず正規表現 $regex_{\tt Let}$ に下記のものを連結した正規表現を内々に生成する。

$${\tt((/Let\ \ }name{\tt\ \ }cusror_{\tt Let}{\tt)\ \ .\ \ }tail_{\tt Let}{\tt)}$$

$cusor_{\tt Let}$ てゆうのは ${\tt Let}$ 担当関数が呼び出された時点でのカーソル位置のことね。もし $regex_{\tt Let}$ が ${\tt(}regex_1^\mathrm{head}{\tt}\ \ \cdots\ \ {\tt}regex_n^\mathrm{head}{\tt)}$ であれば、連結して作った正規表現は、

$${\tt(}regex_1^\mathrm{head}{\tt}\ \ \cdots\ \ {\tt}regex_n^\mathrm{head}{\tt\ \ (/Let\ \ }name{\tt\ \ }cusor_{\tt Let}{\tt)\ \ .\ \ }tail_{\tt Let}{\tt)}$$

になるってゆうことだよっ。

んで、${\tt Let}$ 担当関数はこの正規表現の対象リストについての照合を Regex__match に委譲する。この時には自分が呼び出し元から受け取った伝票もそのまま渡す。

Regex__match が受け取った正規表現のリストを末尾に向かって順に評価していくと、そのうち ${\tt/Let}$ に到達するから、${\tt/Let}$ の担当関数が呼ばれる。

${\tt/Let}$ 担当関数は、$cusor_{\tt Let}$ と、その時点でのカーソル位置 $cursor_{\tt/Let}$(たいていの場合 ${\tt Let}$ 担当関数が呼び出された時点よりも進んでるはず)のふたつを、$name$ 名義で伝票に追記して、その伝票を使って後続する正規表現 $tail_{\tt Let}$ を残りの対象リストで照合してくれるように Regex__match に委譲する。

${\tt /Let}$ 担当関数は Regex__match の戻り値(伝票)を自分の戻り値として返して終了する。呼び出した順番を遡って、$regex_n^{head}$ の担当関数が、$regex_{n-1}^{head}$ の担当関数が、…、$regex_1^{head}$ の担当関数が、そして最後に ${\tt Let}$ 担当関数がその同じ値(伝票)を自分の戻り値として返して終了する。

Ref 担当関数

まず、メタ要素 ${\tt Ref}$ の形はこんなだよっ。

$${\tt((Ref\ \ }name{\tt)\ \ .\ \ }tail_{\tt Ref}{\tt)}$$

${\tt Ref}$ 担当関数は呼ばれると、呼び出し元から受け取った伝票の中で $name$ を探す。

伝票に記載がなければ、「失敗」を戻り値として担当関数は終了する。
伝票に記載があれば、担当関数はそれに紐付いたマッチング領域の情報を取り出す。そしてその領域にある部分リスト $sublist_{cusor_{\tt Let}\sim{}cursor_{\tt/Let}}$ をリテラルとして、かつ、後続する正規表現を $tail_{\tt Ref}$ とするところの ${\tt Literal}$ 正規表現を内々で生成する。

$${\tt((Literal\ \ }sublist_{cusor_{\tt Let}\sim{}cursor_{\tt/Let}}{\tt)\ \ .\ \ }tail_{\tt Ref}{\tt)}$$

生成したこの正規表現を対象リストで照合してくれるように Regex__match に委譲する。

${\tt Ref}$ 担当関数は、Regex__match の戻り値(伝票)を自分の戻り値として担当関数は終了する。

変更

今回の後方参照の導入で他の関数の仕様も少し変わったんだ。

照合系の関数

変更の一つ目は Regex_match 関数と Regex_matchAll 関数の戻り値のデータ型。これまでは全体としてのマッチ情報を Regex_Match 型データ(Regex_matchAll の場合は Regex_Match 型のリスト)を返してたけど、部分マッチのデータを返す必要が出てきたから、新たに定義した Regex.Result 型(Regex_matchAll の場合は Regex.Result 型のリスト)を返すようにした。正規表現がマッチしなかった場合はこれまでと同じで #f を返す。

Regex.Result 型はインターフェース関数で規定されたこんな抽象データ型だよっ(実際にはただの cons セルだけどねっ (^^))。

  • Regex.Result_getRange 関数 —— 全体マッチ範囲の情報(Regex.Range 型)を取り出す。
  • Regex.Result_getAList 関数 —— 部分マッチ範囲の情報(キーがシンボル型で値が Regex.Range 型の連想リスト)を取り出す。

そして、Regex.Range 型はインターフェース関数で規定されたこんな抽象データ型だよっ。

  • Regex.Range_getStart 関数 —— 範囲先頭の位置を返す。
  • Regex.Range_getEnd 関数 —— 範囲末尾の位置を返す。

置換系の関数

変更の二つ目は Regex_replaceByFunctionRegex_replaceAllByFunction の引数。置換する時に部分マッチの情報を使いたい場合があるよねっ。そんな場合はユーザーが引数として与える関数には、マッチ領域全体の情報だけでなくて部分マッチの情報も与える必要がある。だから、Regex_replaceByFunctionRegex_replaceAllByFunction に新しくオプション引数 useRef を追加して、この引数が真値の場合は、ユーザー関数には両方の情報を与える(2引数)ようにしたんだ。このオプション引数の既定値は #f で、ユーザ関数にはマッチ領域全体の情報だけ(1引数)が与えられる(つまりこれまでと同じ)。

ユーザ関数に与えられる二番目の引数は、便利が良いように考慮して連想リストでなくて関数にしたんだ。この関数は部分マッチの名前を与えると部分マッチのデータ(リスト)を返してくれる。もし定義されていない名前とかマッチしていない部分の名前が与えられたらこの関数は空リストを返すんだ。

使用例

下の例では、Regex_matchRegex.Result_getRangeRegex.Result_getAListRegex.Range_apply を使ってるよっ。

(define uy-text (string->list "父が言った「うちはうち、よそはよそぢゃけー」。"))

(define uy-regex
 '(
  [Let uchi-yoso
    ([Selective
      ([Literal (#\う #\ち)])
      ([Literal (#\よ #\そ)])
    ])
  ]
  [Literal (#\は)]
  [Ref uchi-yoso]
  )
)

(let*
  (
  (m (Regex_match uy-regex uy-text char<? char=?))
  (m_r (Regex.Result_getRange m))
  (m_a (Regex.Result_getAList m))
  )
  (display "range: ") (write m_r) (newline)
  (display "range in uy-text: ") (write (Regex.Range_apply m_r uy-text)) (newline)

  (display "alist: ") (write m_a) (newline)
  (for-each
    (lambda (e)
      (display "alist[") (write (car e)) (display "] in uy-text:")
      (write (Regex.Range_apply (cdr e) uy-text)) (newline)
    )
    m_a
  )
  (newline)
)

そしてこの出力がこうなる。

range: (6 11)
range in uy-text: (#\う #\ち #\は #\う #\ち)
alist: ((uchi-yoso 6 8))
alist[uchi-yoso] in uy-text:(#\う #\ち)

次のやつは Regex_matchAll を使ってるよっ。

(let ((ms (Regex_matchAll uy-regex uy-text char<? char=?)))
  (for-each
    (lambda (m)
      (let
        (
        (m_r (Regex.Result_getRange m))
        (m_a (Regex.Result_getAList m))
        )
        (display "range: ") (write m_r) (newline)
        (display "range in uy-text: ") (write (Regex.Range_apply m_r uy-text)) (newline)

        (display "alist: ") (write m_a) (newline)
        (for-each
          (lambda (e)
            (display "alist[") (write (car e)) (display "] in uy-text:")
            (write (Regex.Range_apply (cdr e) uy-text)) (newline)
          )
          m_a
        )
        (newline)
      )
    )
    ms
  )
)

そしてこれがその出力だよっ。

range: (6 11)
range in uy-text: (#\う #\ち #\は #\う #\ち)
alist: ((uchi-yoso 6 8))
alist[uchi-yoso] in uy-text:(#\う #\ち)

range: (12 17)
range in uy-text: (#\よ #\そ #\は #\よ #\そ)
alist: ((uchi-yoso 12 14))
alist[uchi-yoso] in uy-text:(#\よ #\そ)

代わって置換関数の例。JSON に「表示名:" 様"」を追加するやつねっ。もとの JSON の 姓:"", 名:"" の部分マッチング結果を使う必要があるから、Regex_replaceByFunction 関数を使うんだ。

(define json (string->list "{電話:\"XXX-XXX-XXXX\", 姓:\"鈴木\", 名:\"イチロー\", 趣味:\"野球\"}"))

(define seimei-regex
 '( 
  [Literal (#\姓 #\: #\")]
    [Let sei ([Multiple ([ElemSet #t [Enum #\"]]) 1])]
      [Literal (#\" #\,)]

  [Multiple ([ElemSet #f [Enum #\space]]) 1]

  [Literal (#\名 #\: #\")]
    [Let mei ([Multiple ([ElemSet #t [Enum #\"]]) 1])]
      [Literal (#\" #\,)]
  )
)

(display
  (list->string
    (Regex_replaceByFunction seimei-regex json char<? char=?
      (lambda (sublist ref)
        (append
          sublist
          (string->list " 表示名:\"")
          (ref 'sei) '(#\ ) (ref 'mei) (string->list "様\", ")
        )
      )
      #t ; ← 上の関数は Let のデータを使うから #t だよっ
    )
  )
)

そして、これがその出力結果。

{電話:"XXX-XXX-XXXX", 姓:"鈴木", 名:"イチロー", 表示名:"鈴木 イチロー様",  趣味:"野球"}

おわりに

この変更は案外大変だった。実はいちどは SRFI-69 のハッシュテーブルを使う実装をしてそれはそれで完成したんだけど、醜いコードになってしまったから、考え直して今回のコードになった。(*´ω`*)

だけどこのコードはふたつの意味で実用に耐えられない。

  • 対象データの型 —— 文字列を扱うにしてもベクターを扱うにしても一旦リストにしないとイケナイ。メモリー効率が悪いし、使う側としてもスゴクスゴク面倒くさいし、それに、
  • 速度の遅さ —— マッチング対象のデータが長くてバックトラックが多いような正規表現だと顕著になるんだけど、このエンジンは何せ遅い。

とゆうわけで、この問題を解決するのが次の課題なんだ。…って実はもう出来てるんだけど。その改良で長い文字列での実験で速度が1桁速くなったんだ。それもちかぢか記事にしまぁーすっ。(*^^*)


主な関数の一覧

関数形式 説明
(Regex_match this el e<? e=?) this で指定した正規表現を el で指定したリストに照会してみて、適合する最初の部分を Regex.Result 形式で返す。適合する部分がない場合は #f を返す。e<? には二つの要素の小なり比較に使う関数を、e=? には二つの要素の等価比較に使う関数を指定する。
(Regex_matchAll this el e<? e=? . nomatch) this で指定した正規表現を el で指定したリストに照会してみて、適合するすべての部分を Regex.Result データのリストとして返す。適合する部分がない場合は nomatch で指定された値を返す。nomatch は省略可能で規定値は #fe<? には二つの要素の小なり比較に使う関数を、e=? には二つの要素の等価比較に使う関数を指定する。
(Regex_replaceByLiteral this el e<? e=? literal) this で指定した正規表現を el で指定したリストに照会してみて、適合する最初の部分リストを literal で与えられたリスト・リテラルに置き換えたリストを作成して返す。適合する部分がない場合は el を返す。e<? には二つの要素の小なり比較に使う関数を、e=? には二つの要素の等価比較に使う関数を指定する。
(Regex_replaceByFunction this el e<? e=? function . useRef) this で指定した正規表現を el で指定したリストに照会してみて、適合する最初の部分リストを、当該部分リストを function で与えられた関数に与えて得られたリストに置き換えたリストを作成して返す。既定値を #f とするオプション引数 useRef#f の場合 function には当該部分リストのみが与えられるが、#f 以外の場合は function には当該部分リストの他に第二引数として名前を与えると部分マッチしたリスト返す関数が与えられる。Regex_replaceAllByFunction は適合する部分がない場合は el を返す。e<? には二つの要素の小なり比較に使う関数を、e=? には二つの要素の等価比較に使う関数を指定する。
(Regex_replaceByFunctionUsesRef this el e e=? function) (Regex_replaceByFunction this el e<? e=? function #t) と等価。
(Regex_replaceAllByLiteral this el e<? e=? literal) this で指定した正規表現を el で指定したリストに照会してみて、適合する部分リストすべてを literal で与えられたリスト・リテラルに置き換えたリストを作成して返す。適合する部分がない場合は el を返す。e<? には二つの要素の小なり比較に使う関数を、e=? には二つの要素の等価比較に使う関数を指定する。
(Regex_replaceAllByFunction this el e<? e=? function . useRef) this で指定した正規表現を el で指定したリストに照会してみて、適合する部分リストそれぞれについて、各部分リストを function で与えられた関数に与えて得られたリストに置き換えたリストを作成して返す。既定値を #f とするオプション引数 useRef#f の場合 function には各部分のリストのみが与えられるが、#f 以外の場合は function には各部分のリストの他に第二引数として名前を与えると部分マッチしたリスト返す関数が与えられる。Regex_replaceAllByFunction は正規表現に適合する部分がない場合は el を返す。e<? には二つの要素の小なり比較に使う関数を、e=? には二つの要素の等価比較に使う関数を指定する。
(Regex_replaceAllByFunctionUsesRef this el e e=? function) (Regex_replaceAllByFunction this el e<? e=? function #t) と等価。

コード

; ==============================================================================
; scheme.util.Regex
; ==============================================================================

(define (Regex__error . descs)
  (display "Regex: [Error] ") (for-each display descs) (newline)
  (exit)
)

;-------------------------------------------------------------------------------
; Regex.AList -- general association-list
;-------------------------------------------------------------------------------

(define (new_Regex.AList) '())

(define (Regex.AList_ref this k N/A)
  (let ((e (assq k this))) (if e (cdr e) N/A))
) ; define Regex.AList_ref

(define (Regex.AList_set this k v)
  (let* ((buffer (list #f)) (buffer_last buffer))
    (let trace ((ts this))
      (cond
        ((null? ts) (cons (cons k v) this))
        ((eq? k (caar ts))
          (set-cdr! buffer_last (cons (cons k v) (cdr ts)))
          (cdr buffer)
        )
        (else
          (set-cdr! buffer_last (list (car ts)))
          (set!     buffer_last (cdr buffer))
          (trace (cdr ts))
        )
      )
    )
  )
) ; define Regex.AList_set

;-------------------------------------------------------------------------------
; Regex.Result
;-------------------------------------------------------------------------------

; followings are public function

(define Regex.Result_getRange car)
(define Regex.Result_getAList cdr)

; following is for private use

(define (new_Regex.Result index slip)
  (cons
    (new_Regex.Range index (Regex._Slip_getIndex slip))
    (Regex._Slip_getAList slip)
  )
) ; define new_Regex.Result


;-------------------------------------------------------------------------------
; Regex.Range -- contains offset value and length value
;-------------------------------------------------------------------------------

;; followings are public function

(define Regex.Range_getStart car )
(define Regex.Range_getEnd   cadr)

(define (Regex.Range_apply this el)
  (let*
    (
    (buffer (list #f)) (buffer_last buffer)
    (this_offset (Regex.Range_getStart this))
    (this_length (- (Regex.Range_getEnd this) this_offset))
    )
    (do ((drop this_offset (- drop 1))) ((zero? drop))
      (set! el (cdr el))
    )
    (do ((take this_length (- take 1))) ((zero? take))
      (set-cdr! buffer_last (list (car el)))
      (set!     buffer_last (cdr buffer_last))
      (set! el (cdr el))
    )
    (cdr buffer)
  ) ; let*
) ; define Regex.Range_apply

;; following is for private use

(define new_Regex.Range list)

;-------------------------------------------------------------------------------
; <regex> := ()
; <regex> := ((<type> <attr> ... <attr>) . <regex>)
; 
; /r1r2r3/ <=> ((t1 a11 ... a1n) (t2 a21 ... a2m) (t3 a31 ... a2l))
;-------------------------------------------------------------------------------

;; followings are public function

(define Regex_getType caar)

(define Regex_getAttrs cdar)
(define (Regex_setAttrs! this attrs) (set-cdr! (car this) attrs) attrs)

(define Regex_getTail cdr)
(define (Regex_setTail! this another) (set-cdr! this another) another)

;; following is for private use

(define (Regex_isMalformed o)
  (let trace ((o o))
    (cond
      ((null? o) #f)
      ((not (pair? o)) (list "A Regex must be a list: " o))
      ((not (pair? (car o))) (list "car of a Regex must be a list: " (car o)))
      ((not (symbol? (caar o))) (list "caar of a Regex must be a symbol: " (caar o)))
      (else (trace (cdr o)))
    )
  )
) ; define Regex_isMalformed

;-------------------------------------------------------------------------------
; Regex._Slip -- this is private type, for internal information exchange
;-------------------------------------------------------------------------------

;; followings are for private use

(define new_Regex._Slip cons)

(define Regex._Slip_getIndex car)
(define Regex._Slip_getAList cdr)

(define (Regex._Slip_setIndex this i) (new_Regex._Slip i (Regex._Slip_getAList this)))
(define (Regex._Slip_setAList this a) (new_Regex._Slip (Regex._Slip_getIndex this) a))


;-------------------------------------------------------------------------------
; (Regex_match this el e<? e=?)
; 
; public function
; 
; this .. a Regex to match
; el .... a list to be matched
; e<? ... a function that determins element F < element L in form (e<? F L)
; e=? ... a function that determins element F = element L in form (e=? F L)
; 
; returns: Regex.Result data that describes matched region and named sub-regions
;-------------------------------------------------------------------------------

(define (Regex_match this el e<? e=?)
  (let* ((ev (list->vector el)) (ev_length (vector-length ev)))
    (let trace-ei ((ei 0))
      (and (<= ei ev_length)
        (let ((this_slip (Regex__match this el ev (new_Regex._Slip ei (new_Regex.AList)) e<? e=?)))
          (if this_slip
            (new_Regex.Result ei this_slip)
        ; else
            (trace-ei (+ ei 1))
          ) ; if
        ) ; let this_slip
      ) ; and
    ) ; let trace-ei
  ) ; ev, ev_length
) ; define Regex_match

;-------------------------------------------------------------------------------
; (Regex_matchAll this el e<? e=?)
; 
; public function
; 
; this ..... a Regex to match
; el ....... a list to be matched
; e<? ...... a function that determins element F < element L in form (e<? F L)
; e=? ...... a function that determins element F = element L in form (e=? F L)
; nomatch .. optional; a return value when nothing matched; default is #f
; 
; returns: list of Regex.Range data that describes matched region
;-------------------------------------------------------------------------------

(define (Regex_matchAll this el e<? e=?)
  (let* ((ev (list->vector el)) (ev_length (vector-length ev)))
    (let trace-ei ((ei 0) (results '()))
      (if (<= ei ev_length)
        (let ((this_slip (Regex__match this el ev (new_Regex._Slip ei (new_Regex.AList)) e<? e=?)))
          (if this_slip
            (trace-ei
              (max (+ ei 1) (Regex._Slip_getIndex this_slip))
              (cons (new_Regex.Result ei this_slip) results)
            )
        ; else
            (trace-ei (+ ei 1) results)
          ) ; if
        ) ; let this_slip
    ; else
        (reverse results)
      ) ; and
    ) ; let trace-ei
  ) ; let ev_length
) ; define Regex_matchAll

;-------------------------------------------------------------------------------
; (Regex_replaceByLiteral this el e<? e=? literal)
; 
; public function
; 
; this ...... a Regex to match
; el ........ a list to be matched
; e<? ....... a function that determins element F < element L in form (e<? F L)
; e=? ....... a function that determins element F = element L in form (e=? F L)
; literal ... a list to replace where matched region
; 
; returns: a list that first matched sub-list is replaced
;-------------------------------------------------------------------------------

(define (Regex_replaceByLiteral this el e<? e=? literal)
  (Regex_replaceByFunction this el e<? e=? (lambda _ literal))
) ; define Regex_replaceByLiteral

;-------------------------------------------------------------------------------
; (Regex_replaceByFunctionUsesRef this el e<? e=? function)
; 
; public function
; 
; this ...... a Regex to match
; el ........ a list to be matched
; e<? ....... a function that determins element F < element L in form (e<? F L)
; e=? ....... a function that determins element F = element L in form (e=? F L)
; function .. a function that returns a list to replace where matched region;
;             the function uses Let-refer function
; 
; returns: a list that first matched sub-list is replaced
;-------------------------------------------------------------------------------

(define (Regex_replaceByFunctionUsesRef this el e<? e=? function)
  (Regex_replaceByFunction this el e<? e=? function #t)
) ; define Regex_replaceByFunctionUsesRef

;-------------------------------------------------------------------------------
; (Regex_replaceByFunction this el e<? e=? function useRef)
; 
; public function
; 
; this ...... a Regex to match
; el ........ a list to be matched
; e<? ....... a function that determins element F < element L in form (e<? F L)
; e=? ....... a function that determins element F = element L in form (e=? F L)
; function .. a function that returns a list to replace where matched region
; useRef .. optional; #t if the function uses Let-refer function; #f default
; 
; returns: a list that first matched sub-list is replaced
;-------------------------------------------------------------------------------

(define (Regex_replaceByFunction this el e<? e=? function . useRef)
  (set! useRef (and (pair? useRef) (car useRef)))
  (let ((result (Regex_match this el e<? e=?)))
    (if result
      (let*
        (
        (m (Regex.Result_getRange result))
          (m_offset (Regex.Range_getStart m))
          (m_length (- (Regex.Range_getEnd   m) m_offset))
        (a (Regex.Result_getAList result))

        (buffer (list #f)) (buffer_last buffer)
        (el_ el)
        )
        (do ((take m_offset (- take 1))) ((zero? take))
          (set-cdr! buffer_last (list (car el_)))
          (set!     buffer_last (cdr buffer_last))
          (set! el_ (cdr el_))
        )
        (let* ((dropped (list #f)) (dropped_last dropped))
          (do ((drop m_length (- drop 1))) ((zero? drop))
            (set-cdr! dropped_last (list (car el_)))
            (set!     dropped_last (cdr dropped_last))
            (set! el_ (cdr el_))
          )
          (let
            ((literal
              (if useRef
                (function (cdr dropped)
                  (lambda (name)
                    (let ((m_ (Regex.AList_ref a name #f)))
                      (if m_ (Regex.Range_apply m_ el) '())
                    )
                  )
                ) ; function
            ; else
                (function (cdr dropped))
              ) ; if referes
            ))
            (do ((ls literal (cdr ls))) ((null? ls))
              (set-cdr! buffer_last (list (car ls)))
              (set!     buffer_last (cdr buffer_last))
            )
          ) ; literal
        ) ; let*
        (set-cdr! buffer_last el_)
        (cdr buffer)
      ) ; let* buffer, buffer_last, el_
  ; else
      el
    ) ; if
  )  ; let result
) ; define Regex_replaceByFunction

;-------------------------------------------------------------------------------
; (Regex_replaceAllByLiteral this el e<? e=? literal)
; 
; public function
; 
; this ...... a Regex to match
; el ........ a list to be matched
; e<? ....... a function that determins element F < element L in form (e<? F L)
; e=? ....... a function that determins element F = element L in form (e=? F L)
; literal ... a list to replace where matched region
; 
; returns: a list that all matched sub-lists are replaced
;-------------------------------------------------------------------------------

(define (Regex_replaceAllByLiteral this el e<? e=? literal)
  (Regex_replaceAllByFunction this el e<? e=? (lambda _ literal))
) ; define Regex_replaceAllByLiteral

;-------------------------------------------------------------------------------
; (Regex_replaceAllByFunctionUsesRef this el e<? e=? function)
; 
; public function
; 
; this ...... a Regex to match
; el ........ a list to be matched
; e<? ....... a function that determins element F < element L in form (e<? F L)
; e=? ....... a function that determins element F = element L in form (e=? F L)
; function .. a function that returns a list to replace where matched region;
;             the function uses Let-refer function
; 
; returns: a list that first matched sub-list is replaced
;-------------------------------------------------------------------------------

(define (Regex_replaceAllByFunctionUsesRef this el e<? e=? function)
  (Regex_replaceAllByFunction this el e<? e=? function #t)
) ; define Regex_replaceAllByFunctionUsesRef

;-------------------------------------------------------------------------------
; (Regex_replaceByAllFunction this el e<? e=? function useRef)
; 
; public function
; 
; this ...... a Regex to match
; el ........ a list to be matched
; e<? ....... a function that determins element F < element L in form (e<? F L)
; e=? ....... a function that determins element F = element L in form (e=? F L)
; function .. a function that returns a list to replace where matched region
; useRef ... optional; #t if the function uses Let-refer function; #f default
; 
; returns: a list that all matched sub-lists are replaced
;-------------------------------------------------------------------------------

(define (Regex_replaceAllByFunction this el e<? e=? function . useRef)
  (set! useRef (and (pair? useRef) (car useRef)))
  (let ((results (Regex_matchAll this el e<? e=?)))
    (if (pair? results)
      (let* ((buffer (list #f)) (buffer_last buffer) (el_ el) (ei 0))
        (for-each
          (lambda (result)
            (let*
              (
              (m (Regex.Result_getRange result))
                (m_offset (Regex.Range_getStart m))
                (m_length (- (Regex.Range_getEnd m) m_offset))
              (a (Regex.Result_getAList result))
              )
              (do ((take (- m_offset ei) (- take 1))) ((zero? take))
                (set-cdr! buffer_last (list (car el_)))
                (set!     buffer_last (cdr buffer_last))
                (set! el_ (cdr el_)) (set! ei (+ ei 1))
              )
              (let* ((dropped (list #f)) (dropped_last dropped))
                (do ((drop m_length (- drop 1))) ((zero? drop))
                  (set-cdr! dropped_last (list (car el_)))
                  (set!     dropped_last (cdr dropped_last))
                  (set! el_ (cdr el_)) (set! ei (+ ei 1))
                )
                (let
                  ((literal
                    (if useRef
                      (function (cdr dropped)
                        (lambda (name)
                          (let ((m_ (Regex.AList_ref a name #f)))
                            (if m_ (Regex.Range_apply m_ el) '())
                          )
                        ) ; lambda
                      ) ; function
                  ; else
                      (function (cdr dropped))
                    ) ; if useRef
                  ))
                  (do ((ls literal (cdr ls))) ((null? ls))
                    (set-cdr! buffer_last (list (car ls)))
                    (set!     buffer_last (cdr buffer_last))
                  )
                ) ; let literal
              ) ; let*
            ) ; let m, a
          ) ; lambda result
          results
        ) ; for-each
        (set-cdr! buffer_last el_)
        (cdr buffer)
      ) ; let* buffer, buffer_last, el_
  ; else
      el
    ) ; if
  ) ; let results
) ; define Regex_replaceAllByFunction

;===============================================================================




;===============================================================================
; followings are for private use
;===============================================================================

(define Regex__match_matchers '())

(define (Regex__match this el ev slip e<? e=?)
  (if (null? this)
    slip
; evse
    (let ((match (assq (Regex_getType this) Regex__match_matchers)))
      (and match
        ((cdr match) this el ev slip e<? e=?)
      )
    ) ; let
  ) ; if
) ; define Regex__match

;-------------------------------------------------------------------------------
; ([None] . <tail>)
;-------------------------------------------------------------------------------

(set! Regex__match_matchers
  (cons
    (cons 'None (lambda (this el ev slip e<? e=?)
      (Regex__match (Regex_getTail this) el ev slip e<? e=?)
    )) ; cons 'None
    Regex__match_matchers
  ) ; cons
) ; set! Regex__match_matchers

;-------------------------------------------------------------------------------
; ([Literal <literal>] . <tail>)
; 
; /abcde/ <=> ([Literal '(#\a #\b #\c #\d #\e)])
;-------------------------------------------------------------------------------

(set! Regex__match_matchers
  (cons
    (cons 'Literal (lambda (this el ev slip e<? e=?)
      (let*
        (
        (ev_length (vector-length ev))
        (ei (Regex._Slip_getIndex slip))

        (tail  (Regex_getTail  this))
        (attrs (Regex_getAttrs this))

        (literal (car attrs))
        (literal_length (length literal))
        )
        (and (<= (+ ei literal_length) ev_length)
          (let
            ((this_index
              (let trace ((this_index ei) (ls literal))
                (if (null? ls)
                  this_index
              ; evse
                  (and (e=? (car ls) (vector-ref ev this_index))
                    (trace (+ this_index 1) (cdr ls))
                  )
                ) ; if
              ) ; let trace
            )) ; this_index
            (and (integer? this_index)
              (Regex__match tail el ev (Regex._Slip_setIndex slip this_index) e<? e=?)
            ) ; and
          ) ; let this_index
        ) ; and
      ) ; let*
    )) ; cons 'Literal
    Regex__match_matchers
  ) ; cons
) ; set! Regex__match_matchers

;-------------------------------------------------------------------------------
; ([ElemSet <is-exclusive> <elem-spec> ... <elem-spec>] . <tail>)
; <is-exclusive> := <boolean>
; <elem-spec> := [Enum <elem-literal> ... <elem-literal>]
; <elem-spec> := [Range <elem-literal> <elem-literal>]
; <elem-spec> := [Pred <predicate-function>]
; 
; /[abcd-fg]/ <=> ([ElemSet #f [Enum #\a #\b #\c] [Range #\d #\f] [Enum #\g]])
; /[^abcd-fg]/ <=> ([ElemSet #t [Enum #\a #\b #\c] [Range #\d #\f] [Enum #\g]])
;-------------------------------------------------------------------------------

(set! Regex__match_matchers
  (cons
    (cons 'ElemSet (lambda (this el ev slip e<? e=?)
      (let*
        (
        (ev_length (vector-length ev))
        (ei (Regex._Slip_getIndex slip))
        (ei+1 (+ ei 1))

        (tail  (Regex_getTail  this))
        (attrs (Regex_getAttrs this))

        (isExclusive (car attrs))
        (elemSpecs   (cdr attrs))
        )
        (and (<= ei+1 ev_length)
          (let*
            (
            (e0 (vector-ref ev ei))
            (this_index
              (let ((return (if isExclusive `(#f . ,ei+1) `(,ei+1 . #f))))
                (let trace-elemSpecs ((elemSpecs elemSpecs))
                  (if (null? elemSpecs)
                    (cdr return)
                ; else
                    (case (caar elemSpecs)
                      ((Enum) ; [Enum <elem-literal> ... <elem-literal>]
                        (let trace-enum ((enum (cdar elemSpecs)))
                          (cond
                            ((null? enum) (trace-elemSpecs (cdr elemSpecs)))
                            ((e=? (car enum) e0) (car return))
                            (else (trace-enum (cdr enum)))
                          ) ; cond
                        ) ; let trace-enum
                      ) ; (Enum)
                      ((Range) ; [Range <elem-literal> <elem-literal>]
                        (let
                          ((min (cadar elemSpecs)) (max (caddar elemSpecs)))
                          (cond
                            ((and (e<? min e0) (e<? e0 max)) (car return))
                            ((or  (e=? min e0) (e=? e0 max)) (car return))
                            (else (trace-elemSpecs (cdr elemSpecs)))
                          ) ; cond
                        ) ; let
                      ) ; (Range)
                      ((Pred) ; [Pred <predicate-function>]
                        (let ((predicate (cadar elemSpecs)))
                          (cond
                            ((predicate e0) (car return))
                            (else (trace-elemSpecs (cdr elemSpecs)))
                          )
                        ) ; let
                      ) ; (Pred)
                      (else (Regex__error "Unknown component found in ElemSet: " (caar elemSpecs)))
                    ) ; case
                  ) ; if
                ) ; let trace-elemSpecs
              ) ; let return
            ) ; this_index
            )
            (and (integer? this_index)
              (Regex__match tail el ev (Regex._Slip_setIndex slip this_index) e<? e=?)
            ) ; and
          ) ; let*
        ) ; and
      ) ; let
    )) ; cons 'ElemSet
    Regex__match_matchers
  ) ; cons
) ; set! Regex__match_matchers

;-------------------------------------------------------------------------------
; ([AnyElem] . <tail>)
; 
; /./ <=> ([AnyElem])
;-------------------------------------------------------------------------------

(set! Regex__match_matchers
  (cons
    (cons 'AnyElem (lambda (this el ev slip e<? e=?)
      (let
        (
        (ev_length (vector-length ev))
        (ei (Regex._Slip_getIndex slip))
        )
        (and (<= (+ ei 1) ev_length)
          (Regex__match (Regex_getTail this) el ev (Regex._Slip_setIndex slip (+ ei 1)) e<? e=?)
        ) ; and
      )
    )) ; cons 'AnyElem
    Regex__match_matchers
  ) ; cons
) ; set! Regex__match_matchers

;-------------------------------------------------------------------------------
; ([Optional <regex>] . <tail>)
; 
; /regex?/ <=> ([Optional regex])
;-------------------------------------------------------------------------------

(set! Regex__match_matchers
  (cons
    (cons 'Optional (lambda (this el ev slip e<? e=?)
      (let*
        (
        (ei (Regex._Slip_getIndex slip))

        (tail  (Regex_getTail  this))
        (attrs (Regex_getAttrs this))

        (regex (car attrs))

        (more_slip (Regex__match regex el ev slip e<? e=?))
        )
        (if more_slip
          (or (Regex__match tail el ev more_slip e<? e=?)
            (Regex__match tail el ev slip e<? e=?)
          )
      ; else
          (Regex__match tail el ev slip e<? e=?)
        )
      ) ; let*
    )) ; cons 'Optional
    Regex__match_matchers
  ) ; cons
) ; set! Regex__match_matchers

;-------------------------------------------------------------------------------
; ([Multiple <regex> <least> <most>] . <tail>)
;   <least> is optional.
;   <most> is optional if <least> is specified.
;   <most> must not be specified if <least> isn't specified.
; 
; /regex{least:most}/ <=> ([Multiple regex least most]) 
; /regex+/            <=> ([Multiple regex 1]) 
; /regex*/            <=> ([Multiple regex 0]) 
; /regex*/            <=> ([Multiple regex]) 
;-------------------------------------------------------------------------------

(set! Regex__match_matchers
  (cons
    (cons 'Multiple (lambda (this el ev slip e<? e=?)
      (let*
        (
        (tail  (Regex_getTail  this))
        (attrs (Regex_getAttrs this))
        (attrs_length (length attrs))

        (regex (car attrs))
        (least (if (< attrs_length 2)  0 (cadr  attrs)))
        (most  (if (< attrs_length 3) -1 (caddr attrs)))
        )

        (if (negative? least) (set! least 0))
        (if (zero?     most ) (set! most -1))

        (and (not (and (positive? most) (< most least)))
          (let
            ((least_slip
              (let least_match ((l least) (s slip))
                (if (zero? l)
                  s
              ; else
                  (let ((s_ (Regex__match regex el ev s e<? e=?)))
                    (and s_
                      (least_match (- l 1) s_)
                    )
                  ) ; let s_
                ) ; if
              ) ; let least_match
            )) ; least_slip

            (and least_slip
              (let
                ((more_slips
                  (let more_match ((rest (- most least)) (ss (list least_slip)))
                    (if (zero? rest)
                      ss
                  ; else
                      (let ((s_ (Regex__match regex el ev (car ss) e<? e=?)))
                        (if s_
                          (more_match (- rest 1) (cons s_ ss))
                      ; else
                          ss
                        ) ; if
                      ) ; let
                    ) ; if
                  ) ; let more_match
                ))
                (let tail_match ((this_slips more_slips))
                  (and (pair? this_slips)
                    (or (Regex__match tail el ev (car this_slips) e<? e=?)
                      (tail_match (cdr this_slips))
                    )
                  ) ; and pair?
                ) ; let tail_match
              ) ; let more_slips
            ) ; and
          ) ; let least_slip
        ) ; and
      ) ; let
    )) ; cons 'Multiple
    Regex__match_matchers
  ) ; cons
) ; set! Regex__match_matchers

;-------------------------------------------------------------------------------
; ([Selective <regex> ... <regex>] . <tail>)
; 
; /(regex1|regex2|regex3)/ <=> ([Selective regex1 regex2 regex3])
;-------------------------------------------------------------------------------

(set! Regex__match_matchers
  (cons
    (cons 'Selective (lambda (this el ev slip e<? e=?)
      (let*
        (
        (tail  (Regex_getTail  this))
        (attrs (Regex_getAttrs this))

        (regexes attrs)
        )

        (let trace-regexes ((regexes regexes))
          (and (pair? regexes)
            (let ((this_slip (Regex__match (car regexes) el ev slip e<? e=?)))
              (or
                (and this_slip
                  (or (Regex__match tail el ev this_slip e<? e=?)
                    (trace-regexes (cdr regexes))
                  )
                )
                (trace-regexes (cdr regexes))
              )
            ) ; let this_slip
          ) ; and
        ) ; let trace-regexes
      ) ; let*
    )) ; cons 'Selective
    Regex__match_matchers
  ) ; cons
) ; set! Regex__match_matchers

;-------------------------------------------------------------------------------
; ([AtBegin] . <tail>)
; 
; /^regex/ <=> ([AtBegin] . regex)
;-------------------------------------------------------------------------------

(set! Regex__match_matchers
  (cons
    (cons 'AtBegin (lambda (this el ev slip e<? e=?)
      (and (zero? (Regex._Slip_getIndex slip))
        (Regex__match (Regex_getTail this) el ev slip e<? e=?)
      )
    )) ; cons 'AtBegin
    Regex__match_matchers
  ) ; cons
) ; set! Regex__match_matchers

;-------------------------------------------------------------------------------
; ([AtEnd] . <tail>)
; 
; /$/ <=> ([AtEnd])
;-------------------------------------------------------------------------------

(set! Regex__match_matchers
  (cons
    (cons 'AtEnd (lambda (this el ev slip e<? e=?)
      (and (= (vector-length ev) (Regex._Slip_getIndex slip))
        (Regex__match (Regex_getTail this) ev el slip e<? e=?)
      )
    )) ; cons 'AtEnd
    Regex__match_matchers
  ) ; cons
) ; set! Regex__match_matchers

;-------------------------------------------------------------------------------
; ([At <is-exclusive> <index-spec> ... <index-spec>] . <tail>)
; <is-exclusive> := <boolean>
; <index-spec> := [Enum <index-literal> ... <index-literal>]
; <index-spec> := [Range <index-literal> <index-literal>]
; <index-spec> := [Begin <predicate-function>]
;   where <predicate-function> is optional
; <index-spec> := [End <predicate-function>]
;   where <predicate-function> is optional
;-------------------------------------------------------------------------------

(set! Regex__match_matchers
  (cons
    (cons 'At (lambda (this el ev slip e<? e=?)
      (let*
        (
        (ev_length (vector-length ev))
        (ei (Regex._Slip_getIndex slip))

        (tail  (Regex_getTail  this))
        (attrs (Regex_getAttrs this))

        (isExclusive (car attrs))
        (indexSpecs  (cdr attrs))
        )

        (let
          ((this_index
            (let ((return (if isExclusive `(#f . ,ei) `(,ei . #f))))
              (let trace-indexSpecs ((indexSpecs indexSpecs))
                (if (null? indexSpecs)
                  (cdr return)
              ; else
                  (case (caar indexSpecs)
                    ((Enum) ; [Enum <index-literal> ... <index-literal>]
                      (let trace-enum ((enum (cdar indexSpecs)))
                        (cond
                          ((null? enum) (trace-indexSpecs (cdr indexSpecs)))
                          ((= (car enum) ei) (car return))
                          (else (trace-enum (cdr enum)))
                        ) ; cond
                      ) ; let trace-enum
                    ) ; (Enum)
                    ((Range) ; [Range <index-literal> <index-literal>]
                      (let
                        ((min (cadar indexSpecs)) (max (caddar indexSpecs)))
                        (cond
                          ((<= min ei max) (car return))
                          (else (trace-indexSpecs (cdr indexSpecs)))
                        ) ; cond
                      ) ; let
                    ) ; (Range)
                    ((Begin) ; [Begin <predicate-function>]
                      (let ((predicate (if (pair? (cdar indexSpecs)) (cadar indexSpecs) zero?)))
                        (cond
                          ((predicate ei) (car return))
                          (else (trace-indexSpecs (cdr indexSpecs)))
                        )
                      ) ; let
                    ) ; (Begin)
                    ((End) ; [End <predicate-function>]
                      (let ((predicate (if (pair? (cdar indexSpecs)) (cadar indexSpecs) zero?)))
                        (cond
                          ((predicate (- ev_length ei)) (car return))
                          (else (trace-indexSpecs (cdr indexSpecs)))
                        )
                      ) ; let
                    ) ; (End)
                    (else (Regex__error "Unknown component found in At: " (caar indexSpecs)))
                  ) ; case
                ) ; if
              ) ; let trace-indexSpecs
            ) ; let return
          )) ; this_index
          (and (integer? this_index)
          ; (Regex__match (Regex_getTail this) el ev (Regex._Slip_setIndex slip this_index) e<? e=?)
            (Regex__match (Regex_getTail this) el ev slip e<? e=?) ; this_index==ei
          ) ; and
        ) ; let
      ) ; let*
    )) ; cons 'At
    Regex__match_matchers
  ) ; cons
) ; set! Regex__match_matchers

;-------------------------------------------------------------------------------
; ([Let <name> <regex>] . <tail>)
;-------------------------------------------------------------------------------

(set! Regex__match_matchers
  (cons
    (cons 'Let (lambda (this el ev slip e<? e=?)
      (let*
        (
        (ei (Regex._Slip_getIndex slip))

        (tail  (Regex_getTail  this))
        (attrs (Regex_getAttrs this))

        (name  (car  attrs))
        (regex (cadr attrs))

        (tailored-regex
          (let* ((buffer (list #f)) (buffer_last buffer))
            (let copy-regex ((r regex))
              (and (pair? r)
                (begin
                  (set-cdr! buffer_last (list (car r)))
                  (set!     buffer_last (cdr buffer_last))
                  (copy-regex (cdr r)) ;; cdr == Regex_getTail
                )
              )
            ) ; let copy-regex
            (set-cdr! buffer_last (cons `[/Let ,name ,ei] tail))
            (cdr buffer)
          )
        ) ; tailored-regex
        )
        (Regex__match tailored-regex el ev slip e<? e=?)
      ) ; let*
    )) ; cond 'Let
    Regex__match_matchers
  ) ; cons
) ; set! Regex__match_matchers

(set! Regex__match_matchers
  (cons
    (cons '/Let (lambda (this el ev slip e<? e=?)
      (let*
        (
        (ei (Regex._Slip_getIndex slip))

        (tail  (Regex_getTail  this))
        (attrs (Regex_getAttrs this))

        (name   (car  attrs))
        (Let.ei (cadr attrs))

        ; make a new slip in which the matched result is added
        (this_slip
          (Regex._Slip_setAList slip
            (Regex.AList_set (Regex._Slip_getAList slip)
              name
              (new_Regex.Range Let.ei ei)
            )
          )
        )
        )
        (Regex__match tail el ev this_slip e<? e=?)
      ) ; let*
    )) ; cond '/Let
    Regex__match_matchers
  ) ; cons
)

;-------------------------------------------------------------------------------
; ([Ref <name>] . <tail>)
;-------------------------------------------------------------------------------

(set! Regex__match_matchers
  (cons
    (cons 'Ref (lambda (this el ev slip e<? e=?)
      (let*
        (
        (tail  (Regex_getTail  this))
        (attrs (Regex_getAttrs this))

        (name  (car attrs))

        (match (Regex.AList_ref (Regex._Slip_getAList slip) name #f))
        )
        (and match
          (let*
            (
            (literal `([Literal ,(Regex.Range_apply match el)] . ,tail))
            (this_slip (Regex__match literal el ev slip e<? e=?))
            )
            (and this_slip
              (Regex__match tail el ev this_slip e<? e=?)
            ) ; and
          ) ; let* literal*, this_slip
        ) ; and match
      ) ; let*
    )) ; cond 'Ref
    Regex__match_matchers
  ) ; cons
) ; set! Regex__match_matchers
;===============================================================================