Как работает каноническая реализация match-letrec? - PullRequest
Новая
       54

Как работает каноническая реализация match-letrec?

2 голосов
/ 19 сентября 2019

В настоящее время я портирую Каноническую реализацию Алекса Шинна match для Схемы , которая используется почти во всех реализациях Схемы, на другой Лисп.

Я столкнулся с итогомстена с match-letrec.В упрощенной версии его реализации она определяется следующим образом: 

(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))))

Автоматические символы генерируются заменой tmp ввторое правило match-letrec-helper.Это расширение означает, что лямбда-выражения вычисляются до того, как x и a связаны, и поэтому не могут их захватить.

Может кто-нибудь объяснить, как этот синтаксис должен быть правильно расширен?Что я пропустил?

1 Ответ

0 голосов
/ 22 сентября 2019

В вашем примере 

(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))

но это должно сделать вас на шаг ближе, не стесняйтесь задавать новый вопрос с примером рабочего кода, как только вы поймете эти изменения.

...