Объединение структурных особенностей в миниканрен - PullRequest
Новая
       53

Объединение структурных особенностей в миниканрен

0 голосов
/ 22 ноября 2018

Как можно определить объединение структур объектов и их использование в миниканренах, если мы представим структуры объектов со списками?

Общее поведение будет примерно таким (Я думаю): 

(run* (q) (unifyo '(a b) '(a b) q))) => (a b)

(run* (q) (unifyo '(x (a b)) '(x (c d)) q)) => (x (a b) (c d)) (x (c d) (a b))

(run* (q) (unifyo '(x (a b)) '(x (a d)) q)) => ()      ; fails because '(a b) is 
                                                       ; incompatible with '(a d)
(run* (q) 
    (fresh (y) (unifyo '(x (a b)) `(x ,y) q)) => (x (a b)))

(run* (q) (unifyo q '(x (a b)) '(x (a b) (c d)))) => (x (c d))

Следующий код вроде работает, но обратное объединение застревает при запуске с помощью run *: 

;; unifies f1 with l2
(define unify-f-with-list°
  (lambda (f1 l2 out)
    (conde
     [(== '() l2) (== `(,f1) out)]
     [(fresh (la ld a2 d2 a1 d1 res)
         (=/= '() l2)
         (== `(,la . ,ld) l2)
         (== `(,a2 . ,d2) la)
         (== `(,a1 . ,d1) f1)
         (conde
          [(== a2 a1)
           (== `(,res . ,ld) out)
           (unify° f1 la res)]
          [(fresh ()
              (=/= a2 a1) ;; if not
              (== `(,la . ,res) out)
              (unify-f-with-list° f1 ld res))]))])))

(define unify-list-with-list°
  (lambda (l1 l2 out)
    (conde
     [(== '() l1) (== l2 out)]
     [(== '() l2) (== l1 out)]
     [(fresh (a1 d1 res)
         (=/= '() l1)
         (== `(,a1 . ,d1) l1)
         (unify-f-with-list° a1 l2 res)
         (unify-list-with-list° d1 res out))])))

(define unify°
  (lambda (f1 f2 out)
    (conde
     [(== f1 f2) (== f1 out)]
     [(fresh (a1 d1 a2 d2)
         (=/= f1 f2)        
         (== `(,a1 . ,d1) f1)
         (== `(,a2 . ,d2) f2)
         (== a1 a2)
         (fresh (res)
            (unify-list-with-list° d1 d2 res)
            (== `(,a1 . ,res) out)))])))

1 Ответ

0 голосов
/ 09 декабря 2018

Вы можете реализовать это, изменив код для объединения в вашей реализации minikanren.

Я бы порекомендовал не использовать списки для представления структур объектов, вместо этого вы можете определить новый тип записи, а не список, который всегдаоканчивается новой переменной, и одна из них будет представлять структуру объекта.Тогда вы все еще можете использовать списки и другие объекты, а также иметь доступ к этим новым объектам.

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

...