Личный сайт Алексея Григорьева

SICP: Pattern Matching and Rule-based Substitution

Сопоставление с образцом (англ. Pattern matching) — метод анализа списков или других структур данных на наличие в них заданных образцов. В отличие от распознавания образов — образец в данном случае задан жёстко, к примеру с помощью регулярных выражений. [...] (википедия)

Ниже — конспект лекции на тему Pattern Matching и реализация этого метода на языке программирования Scheme.

SICP: Pattern Matching and Rule-based Substitution

Рассмотрим процедуру вычисления производной

(define (deriv exp var)
    (cond 
        ((number? exp) 0)
        ((variable? exp)
            (if (same-variable? exp var) 1 0))
        ((sum? exp) 
            (make-sum (deriv (addend exp) var)
                      (deriv (augend exp) var)))
        ((product? exp)
            (make-sum
                (make-product (multiplier exp)
                              (deriv (multiplicand exp) var))
                (make-product (deriv (multiplier exp) var)
                              (multiplicand exp))
            )
        )
        ((exponentiation? exp)
            (make-product 
                (exponent exp)
                (make-product 
                    (make-exponentiation (base exp) (- (exponent exp) 1))
                    (deriv (base exp) var)
                )
            )
        )
        (else 
            (error "unknown expression type -- DERIV" exp))
    )
)

Код выше представляет собой набор проверок, а после каждой проверки — следствие, то, что должно быть выполнено, если нужное условие удовлетворено. Т.е. группы проверка-следствие представляют собой набор правил типа «если данные А — то делать В». Все правила имеют две части: первая, то чему выражение должно соответствовать, а второе — следствие, то, чем выражение должно стать.

Это код можно обобщить — отделить правила от кода, проверяющего эти правила.

Рассмотрим правила дифференцирования функций, которые реализует процедура deriv:

Запишем эти правила в виде списка «Pattern — Skeleton»:
(Pattern — слева, Skeleton — справа)

(define deriv-rules '(
    ((dd (?c c) (? v))             0)
    ((dd (?v v) (? v))             1)
    ((dd (?v u) (? v))             0)
    ((dd (+ (? x1) (? x2)) (? v))  (+ (dd (: x1) (: v))
                                      (dd (: x2) (: v))))
    ((dd (* (? x1) (? x2)) (? v))  (+ (* (: x1) (dd (: x2) (: v)))
                                      (* (dd (: x1) (: v)) (: x2))))
    ((dd (** (? x) (?c n)) (? v))  (* (* (: n) (+ (: x) (: (- n 1))))
                                   (dd (: x) (: v))))
))

Синтаксис

Pattern:
foo соответствует foo
(f a b) соответствует списку (f a b)
(? x) соответствует чему угодно, создает x со значением, содержащимся на месте x
(?c x) соответствует только константе, создает x
(?v x) соответствует только переменной, создает x

Skeleton:
foo остается foo
(f a b) остается списком (f a b)
(: x) заменяется на значение переменной x
(: (expression)) выполняет выражение expression


Pattern создает Skeleton, если он соответствует выражению Expression.
Skeleton преобразуется в Target Expression — конечный результат.


Pattern Matching

Pattern Matching работает следующим образом

Есть набор правил (Rule), и у каждого правила есть Pattern, которому выражение может соответствовать, и Skeleton — то, во что выражение преобразуется, если правило соответствует выражению.

Matcher проверяет, соответствует ли выражение паттерну, и если соответствует, подготавливает некоторое множество переменных из паттерна, сопоставленных с их значениями из выражения.

Instantiator преобразует исходное выражение, используя Skeleton и словарь данных, возвращая новое выражение, которое опять поступает на вход в Matcher.


Matcher

Matcher — процедура, принимающая на вход expression, pattern, dictionary и возвращающая dictionary.

expression — выражение, которое должно быть сопоставлено паттерну
pattern — паттерн для сопоставления выражению
dictionary — словарь, в котором перечислены переменные из паттерна, и соотвествующие им значения из выражения — { x: value x }

Результат работы матчера — дополненный словарь, содержащий значения переменных, полученным на данном шагу, или ключевой символ failure, если паттерн не соответствует выражению.

Метод выглядит следующим образом:

(define (match pat exp dict)
    (cond
        ((and (null? pat) (null? exp)) dict)
        ((eq? dict FAILED) FAILED)
        ((atom? pat) *** atomic part ***)
        (*** pattern variable clauses ***)
        ((atom? exp) FAILED)
        (else
            (match (cdr pat) (cdr exp)
                (match (car pat) (car exp) dict)
            )
        )
    )
)

Рассмотрим следующие выражения:

(+ (* (? x) (? y)) (? y))
(+ (* 3 x) x)
(+ (* 3 x) 4)

Паттерн находится в первой строке и два выражения во второй и третьей. Выражение во второй строке соответствует паттерну, в третьей — нет.

Нужно просматривать одновременно два дерева — дерево паттернов и дерево выражения, и сравнить каждый элемент первого с каждым элементом второго.

Если на текущем этапе попадается сложное выражение, то процедура match для него запускается рекурсивно, используя в качестве словаря результат, полученный от рекурсивного запуска процедуры match для всего остального дерева.

Если в паттерне ожидается переменная, то расширяем текущий словарь, добавляя в него значение, обнаруженное на этом месте. Например, для выражения (+ (* 3 x) x) переменной x соовествует значение 3, а переменной y — значение x.

При попытке добавить в словарь переменной, уже существующей в нем, проверяется, равны ли значения этих переменных, и если нет, возвращается символ failure. Для выражении (+ (* 3 x) 4) в переменную делается попытка запомнить значение y, в то время, как она уже содержит другое значение 4 (или наоборот, 4 и y).

Рассмотрим по частям каждый кусок процедуры match:

((eq? dict FAILED) FAILED)
(match 
    ; сравнивает текущий элемент паттерна и текущий элемент выражения
    (cdr pat) (cdr exp) 
    ; и в качестве словаря использует словарь, полученный на предыдущих шагах
    (match (car pat) (car exp) dict)
)
; *** atomic part ***
; если текущие элементы оба простые,
((atom? pat)
    (if (atom? exp)
        ; и равны друг другу, то продолжаем обход дальше
        (if (eq? pat exp)
            ; (т.е. возвращаем текущий словарь неизмененным)
            dict
            FAILED
        )
        FAILED
    )
)
; *** pattern variable clauses ***
; константа? (?c x)
((arbitrary-constant? pat) 
    (if (constant? exp exp)
        ; если в выражении константа, то добавляем ее в словарь
        (extend-dict pat exp dict)
        FAILED
    )
)
((arbitrary-variable? pat)
    (if (variable? exp)
        ; если в выражении переменная, то добавляем ее в словарь
        (extend-dict pat exp dict)      
        FAILED
    )
)
((arbitrary-expression? pat)
    (extend-dict pat exp dict)
)
; extend-dict возвращает FAILURE, если

Целиком:

(define (match pat exp dict)
    (cond
        ((and (null? pat) (null? exp)) dict)
        ((eq? dict FAILED) FAILED)
        ((atom? pat)
            (if (atom? exp)
                (if (eq? pat exp)
                    dict
                    FAILED
                )
                FAILED
            )
        )
        ((arbitrary-constant? pat) 
            (if (constant? exp exp)
                (extend-dict pat exp dict)
                FAILED
            )
        )
        ((arbitrary-variable? pat)
            (if (variable? exp)
                (extend-dict pat exp dict)      
                FAILED
            )
        )
        ((arbitrary-expression? pat)
            (extend-dict pat exp dict)
        )
        ((atom? exp) FAILED)
        (else
            (match 
                (cdr pat) (cdr exp) 
                (match (car pat) (car exp) dict)
            )
        )
    )
)

Instantiator

Instantiate — процедура, принимающая на вход словарь dictionary — результат выполнения процедуры match и skeleton, обозначенный в правиле и преобразует выражение, используя значения переменных из словаря

(define (instantiate skeleton dict)
    (define (loop s)
        (cond
            ((null? s) null)
            ((atom? s) s)
            ((skeleton-evaluation? s)
                (evaluate (eval-exp s) dict)
            )
            (else
                (cons (loop (car s)) (loop (cdr s))))
        )
    )
    (loop skeleton)
)

Процедура evaluate вычисляет результирующее выражение, используя словарь. Если передан простой объект, то возвращается значение из словаря, или сам объект, если для этой переменной в словаре нет значения. Если же объект сложный, то это значит, что его нужно вычислить. (Это может быть правило (: (+ x y)) — сложение двух чисел из переменных x и y.)

(define (evaluate form dictionary)
    (if (atom? form)
        (lookup form dictionary)
 
        (apply 
            (eval (lookup (car form) dictionary) ns)
            (map (lambda (v) (lookup v dictionary))
                 (cdr form))
        )
    )
)

Чтобы понять, как именно вычисляется выражение в evaluate, рассмотрим следующий код

(define ns (make-base-namespace))
(apply (eval '+ ns) '(1 2 3))

Процедура eval выполняет переданный кусок кода, используя заданный контекст для поиска определений (в данном случае make-base-namespace). (eval '+ ns) возвращает процедуру «+«, которая вызывается с параметрами 1 2 3 процедурой apply.
Т.е. приведенный выше фрагмент выполняет (+ 1 2 3) и возвращает число 6.

Garbage-in/Garbage-out simplifier, GIGO*

Simplifier — процедура, которая принимает в качестве параметра список правил, и возвращает процедуру, которую далее можно использовать для преобразования выражений.

(define (simplifier the-rules)
    (define (simplify-exp exp)
        ***
    )
    (define (try-rules exp)
        ***
    )
    simplify-exp
)
(define (simplify-exp exp)
    (try-rules 
        (if (compound? exp)
            (map simplify-exp exp)
            exp
        )
    )
)
(define (try-rules exp)
    (define (scan rules)
        (if (null? rules)
            exp
            (let 
                ((dictionary 
                    (match (pattern (car rules))
                           exp
                           (make-empty-dictionary))))
                (if (eq? dictionary FAILED)
                    ; если правило не подошло, попробовать следующее
                    (scan (cdr rules))
                    (simplify-exp 
                        (instantiate (skeleton (car rules)) dictionary))
                )
            )
        )
    )
    (scan the-rules)
)

Процедура try-rules один за одним перебирает все правила. Для каждого из выражений берется правило. Если оно не подходит (matcher вернул failure), то берется следующее. Если подходит, то правило применяется, а полученное выражение обрабатывается процедурой simplify-exp по-новой.

Dictionary

extend-dict используется процедурой match при расширении словаря переменных. При добавлении, переменная сначала ищется в списке. Если переменная не найдена, возвращаем словарь с ней. Если же найдена, то производится проверка на равенство нового значения переменной со значением, которое хранится в словаре. При совпадении значений словарь возвращается нетронутым, иначе — возвращается ошибка.

(define (extend-dict pat dat dict)
    (let
        ((name (variable-name pat)))
        (let
            ((v (assq name dict)))
            (cond
                ((null? v) (cons (list name dat) dict))
                ((eq? (cadr v) dat) dict)
                (else
                    FAILED)
            )
        )
    )
)
 
(define (lookup var dict)
    (let 
        ((v (assq var dict)))
        (if (null? v) 
            var
            (cadr v)
        )
    )
)

Применение

(define dsimp (simplifier deriv-rules))
(dsimp '(dd (+ x y) x))

Однако, полученная процедура dsimp возвращает неупрощенные выражения. Для упрощения будем использовать следующий набор алгебраических правил:

(define algebra-rules '(
    (((? op) (?c c1) (?c c2))                (: (op c1 c2)))
    (((? op) (?  e ) (?c c))                 ((: op) (: c) (: e)))
    ((+ 0 (? e))                             (: e))
    ((* 1 (? e))                             (: e))
    ((* 0 (? e))                             0)
    ((* (?c c1) (* (?c c2) (? e )))          (* (: (* c1 c2)) (: e)))
    ((* (?  e1) (* (?c c ) (? e2)))          (* (: c ) (* (: e1) (: e2))))
    ((* (* (? e1) (? e2)) (? e3))            (* (: e1) (* (: e2) (: e3))))
    ((+ (?c c1) (+ (?c c2) (? e )))          (+ (: (+ c1 c2)) (: e)))
    ((+ (?  e1) (+ (?c c ) (? e2)))          (+ (: c ) (+ (: e1) (: e2))))
    ((+ (+ (? e1) (? e2)) (? e3))            (+ (: e1) (+ (: e2) (: e3))))
    ((+ (* (?c c1) (? e)) (* (?c c2) (? e))) (* (: (+ c1 c2)) (: e)))
    ((* (? e1) (+ (? e2) (? e3)))            (+ (* (: e1) (: e2))))
))

Теперь процедуру deriv, аналогичную приведенной в самом начале, можно получить следующим образом:

(define dsimp (simplifier deriv-rules))
(define alsimp (simplifier algebra-rules))
 
(define (deriv exp)
    (alsimp (dsimp exp))
)
(equal? (deriv '(dd (+ x y) x))          1)
(equal? (deriv '(dd (* x y) x))         'y)
(equal? (deriv '(dd (+ (* x y) x) x))   '(+ 1 y))

Код полностью

Источники и материалы

Lecture
Transcription
Source from the lection

Working Through SICP Pattern Matching and Rule-based Substitution Lecture With MIT Scheme
Running SICP Pattern Matching Rule Based Substitution Code

Далее:

Среда, 11 Июл 2012 в 22:30. Вы можете следить за комментариями к этой статье через RSS 2.0.