Функция сопоставления с образцом в Scheta Meta Circular Evaluator

Question

Я пытаюсь добавить функцию сопоставления с образцом в существующую схему мета круговой оценки (это домашнее задание), и я немного растерялся в формулировках инструкций. Я надеялся, что кто-то более опытный в этом отношении сможет помочь мне интерпретировать это.

Синтаксис для соответствия должен выглядеть следующим образом: (match a ((p1 v1) (p2 v2) (p3 v3)))

И это можно использовать, чтобы найти длину следующим образом:

(define length (lambda (x)
   (match x (('() 0)
             (('cons a b) (+ 1 (length b))))))

Язык шаблонов в функции должен содержать числовые константы, константы в кавычках, переменные и минусы. Если шаблоны исчерпаны без нахождения соответствия, должна быть выдана ошибка.

Я думал, что понял концепцию сопоставления с образцом, но реализация этого в функции таким образом меня немного отбросила. Кто-нибудь захочет объяснить, что делает приведенный выше синтаксис (в частности, как используется длина соответствия, приведенная выше), чтобы я мог лучше понять, что должна делать эта функция?

Answer 1

(match x (('() 0)
          (('cons a b) (+ 1 (length b)))))

Может оказаться наиболее полезным рассмотреть, во что этот код нужно будет расширить. Для каждого шаблона вам понадобится тест, чтобы определить, соответствует ли объект, который вы пытаетесь сопоставить, и код, чтобы выяснить, как связать переменные с его частями. В этом случае вы хотите расширение примерно так:

(if (equal? '() x)
    0
    (if (pair? x)
        (let ((a (car x))
              (b (cdr x)))
          (+ 1 (length b)))
        ;; indicate failure to match
        'NO-MATCH))

Конечно, вы могли бы написать это и с помощью cond, но если вам придется процедурно расширять это, было бы проще использовать вложенные формы if.

Если вы на самом деле реализуете это как функцию (а не как макрос (т. Е. Преобразование исходного кода), то вам необходимо точно указать, как вы можете работать со средами и т. Д.

Answer 2

Я предлагаю вам прочитать четвертую главу " Структурированные типы и семантика сопоставления с образцом" из книги "Реализация функциональных языков". Глава написана Саймоном Л. Пейтоном Джонсом и Филиппом Уодлером.