规范的match-letrec实现是如何工作的？

Question

我目前正在将几乎所有Scheme实现都使用的Alex Shinn's canonical implementation of match for Scheme移植到另一个Lisp。

我和match-letrec遇到了一堵墙。在the simplified version of his implementation中，它的定义如下：

(define-syntax match-let
  (syntax-rules ()
    ((_ ((pat expr)) . body)
     (match expr (pat . body)))
    ((_ ((pat expr) ...) . body)
     (match (list expr ...) ((pat ...) . body)))
    ((_ loop . rest)
     (match-named-let loop () . rest))
    ))

(define-syntax match-letrec
  (syntax-rules ()
    ((_ vars . body) (match-letrec-helper () vars . body))))

(define-syntax match-letrec-helper
  (syntax-rules ()
    ((_ ((pat expr var) ...) () . body)
     (letrec ((var expr) ...)
       (match-let ((pat var) ...)
         . body)))
    ((_ (v ...) ((pat expr) . rest) . body)
     (match-letrec-helper (v ... (pat expr tmp)) rest . body))
    ))

以下是它在使用时的外观示例(Guile 1.8)：

(match-letrec (((x y) (list 1 (lambda () (list a x))))
               ((a b) (list 2 (lambda () (list x a)))))
  (append (y) (b))
=> (2 1 1 2)

我很难理解这到底是如何工作的。当我手动将其扩展到match时，我得到了以下代码(带有由#{g...}指示的自动符号)：

(letrec ((#{g1} (list 1 (lambda () (list a x))))
         (#{g2} (list 2 (lambda () (list x a)))))
  (match (list #{g1} #{g2}) (((x y) (a b)) (append (y) (b))))

自动符号由match-letrec-helper的第二个规则中的tmp替换生成。这种扩展意味着在绑定x和a之前对lambda表达式进行求值，因此无法捕获它们。

有人能解释一下这个语法是如何正确扩展的吗？我错过了什么？

Answer 1

你的例子

(match-letrec (((x y) (list 1 (lambda () (list a x))))
               ((a b) (list 2 (lambda () (list x a)))))
  (append (y) (b))
=> (2 1 1 2)

缺少右括号。

在修复之后，将会发生以下情况：

> (match-letrec (((x y) (list 1 (lambda () (list a x))))
               ((a b) (list 2 (lambda () (list x a)))))
  (append (y) (b)))
. match: syntax error in pattern in: ((x y) (a b))

甚至match-let也不起作用

> (match-let (((x y) (list 1 2)))
    x)
. match: syntax error in pattern in: (x y)

下面是如何修复它：

(define-syntax match-let
  (syntax-rules (list)
    ((_ ((pat expr)) . body)
     (match expr (pat . body)))
    ((_ ((pat expr) ...) . body)
     (match (list expr ...) ((pat ...) . body)))
    ((_ loop . rest)
     (match-named-let loop () . rest))
    ))

现在你可以这样做了：

> (match-let (((list x y) (list 1 2)))
    (list x y))
'(1 2)

letrec仍然不起作用

> (match-letrec (((list x y) (list 1 (lambda () (list a x))))
                 ((list a b) (list 2 (lambda () (list x a)))))
  (append (y) (b)))
. match: syntax error in pattern in: ((list x y) (list a b))

但这应该会让你更近一步，一旦你理解了这些变化，你可以自由地问一个新的问题和工作代码示例。