Emacs LISP - DeMorgan'ify a list

Я нахожусь в курсе искусственного интеллекта, и нам была дана программа для написания. Программа, по-видимому, проста, и все остальные ученики сделали это в java. Однако я знаю, что это можно сделать в LISP с меньшим количеством работы. Что ж. Меньше печатать. Но я читал о LISP уже неделю, и я поражен этим. Я полна решимости узнать больше и использовать LISP намного больше, чем просто этот класс. Мне 23 года, и я изучаю язык, образованный в 1958 году. Это романтично. Я получаю много удовольствия, избегая моей мыши, как чума.Emacs LISP - DeMorgan'ify a list

Пример, который он дает, рассказывает всю программу. Он отмечает, что он использует рекурсию, а не прог. Я понимаю, что это значит, по крайней мере.

(rewrite '(or a (and b (not (or c d))))) 

--> (OR A (AND B (AND (NOT C) (NOT D)))) 

(rewrite '(and a (or b (not (and c (and d e)))))) 

--> (AND A (OR B (NOT C) (OR (NOT D) (NOT E)))))

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

(not (or a b))

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

(defun boom (sexp) 

    (let ((op (car (car (cdr sexp)))) 

    (operands (cdr (car (cdr sexp)))))) 

    (if (equal op 'and) 

     (setcar sexp 'or) 

    (setcar sexp 'and)) 

    (print operands) 

    (print sexp)) 

       ;end boom

Я печатаю в конце для отладки. Изменения в списке операндов не отражают изменения в оригинальном sexp (огромная подставка для меня).

Скажите мне, что у меня есть подделка, и направляйте меня.

источник

2016-02-09 kaleoh

Вы говорите «DeMorgan-ify»; это точка только для распределения «не» над внутренним «или» или «и»? –

Основываясь на его выходе, это то, что кажется. Например, «и» и «или» могут просто быть «foo» и «bar». Логика, похоже, не играет никакой роли. – kaleoh

Работа с искусственным интеллектом заставляет меня думать об использовании предикатов, я имею в виду, что ваша программа должна сначала изучить некоторые знания (например, как интерпретировать разные операторы в соответствии с законами ДеМоргана), а затем она может оценить все ваше выражение, используя его базу знаний (т.е. привязка предикатов на лету) - см. пример предикатов ниже – floppy12

Emacs Lisp решение с использованием сопоставления с образцом, на основе Rainer Joswigs Common Lisp решения:

(defun de-morgan (exp) 
    (pcase exp 
    ((pred atom) exp) 
    (`(not (and ,a ,b)) `(or ,(de-morgan `(not ,a)) 
          ,(de-morgan `(not ,b)))) 
    (`(not (or ,a ,b)) `(and ,(de-morgan `(not ,a)) 
          ,(de-morgan `(not ,b)))) 
    (x (cons (car x) (mapcar #'de-morgan (rest x)))))) 

(de-morgan '(not (or 1 2))) ; => (and (not 1) (not 2)) 
(de-morgan '(not (and 1 2))) ; => (or (not 1) (not 2)) 
(de-morgan '(or a (and b (not (or c d))))) ; => (or a (and b (and (not c) (not d))))

источник

2016-02-09 16:56:45 jkiiski

Я понимаю, что делает комбинация backquote и comma. Во всяком случае, я пытаюсь понять. Позвольте мне спросить, правильно ли я это: '(не (или, a, b))' (и (не, (demorgan a) (не, (demorgan b) В основном вы говорите, если оно соответствует (не (или ...)), вы запускаете a и b как через функцию демона. Ваша последняя строка меня озадачила, есть ли все, что вы можете объяснить? Что именно связано с x? – kaleoh

@kaleoh На последнем строка, 'x' привязана к соответствующему выражению (то же, что и' exp'). В основном это предложение «в противном случае», которое будет соответствовать чему-либо, если другие шаблоны не сработают. – jkiiski

Если он соответствует одному атому, то этот атом сохраняется Если он совпадает с символом '(не (и/или, a, b)), то он заменяется на' (или/и (не ...)) и запускает a и b как через функции, блестящие. n, если у него нет «нет», он будет снова проталкивать остальные через функцию, оставляя то, что он только что проверил, как есть. Brilliant! Это было именно мое намерение, и теперь я знаю инструмент, который, как мне хотелось бы знать неделю назад. – kaleoh

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

(defun demorganify (formula) 
    (if (atom formula) 
     formula 
    (let ((operator (first formula))) 
     (case operator 
     ((and or) 
     (list* operator (mapcar 'demorganify (rest formula)))) 
     ((not) 
     (let ((subformula (second formula))) 
      (if (atom subformula) 
       formula 
      (let* ((suboperator (first subformula)) 
        (new-suboperator (case suboperator 
             ((not) 'not) 
             ((and) 'or) 
             ((or) 'and))) 
        (demorganify-and-negate (lambda (f) 
               (demorganify (list 'not (demorganify f)))))) 
       (list* new-suboperator (mapcar demorganify-and-negate (rest subformula)))))))))))

Это, безусловно, может быть сделано немного чище.

источник

2016-02-09 16:00:29

(demorganify '(не (или (не a) (не b))))? –

@RainerJoswig Упс, добавлено сейчас не случай. ОП не сказал, следует ли удалять двойные отрицания или нет. –

Не было инструкции относительно двойных отрицаний, поэтому я думаю, что это открыто. – kaleoh

Эти две функции должны распределить not в скобках:

(defun de-morgan (formula) 
    (if (listp formula) 
     (let ((op (first formula))) 
     (case op 
      (and `(and ,(de-morgan (second formula)) ,(de-morgan (third formula)))) 
      (or `(or ,(de-morgan (second formula)) ,(de-morgan (third formula)))) 
      (not (de-morgan-negate (second formula))))) 
    formula)) 

(defun de-morgan-negate (formula) 
    (if (listp formula) 
     (let ((op (first formula))) 
     (case op 
      (and `(or ,(de-morgan-negate (second formula)) ,(de-morgan-negate (third formula)))) 
      (or `(and ,(de-morgan-negate (second formula)) ,(de-morgan-negate (third formula)))) 
      (not (de-morgan (second formula))))) 
    `(not ,formula))) 



(de-morgan 'a) 
(de-morgan '(not a)) 
(de-morgan '(not (not a))) 
(de-morgan '(and a b)) 
(de-morgan '(not (and a b))) 
(de-morgan '(not (or a b))) 
(de-morgan '(not (and (and (not a) b) (not (or (not c) (not (not d)))))))

источник

2016-02-09 16:00:41 choroba

Вы не должны указывать аргументы в ** случае **. '(case 'quote (' и 'match) (t no-match))' возвращает ** совпадение **, потому что '' и 'является сокращением для' (quote and) 'и ** case ** ожидает указатель для списка форм ключей. Вы предоставляете список из двух символов: ** quote ** и ** и **. –

@JoshuaTaylor: Спасибо, это показывает, как редко я люблю в эти дни. – choroba

Common Lisp, без упрощения:

(defun de-morgan (exp) 
    (cond ;; atom 
     ((atom exp) exp) 
     ;; (not (and p q)) or (not (or p q)) 
     ((and (consp exp) 
       (equal (car exp) 'not) 
       (consp (cadr exp)) 
       (or (equal (caadr exp) 'and) 
        (equal (caadr exp) 'or))) 
     (list (case (caadr exp) 
       (and 'or) 
       (or 'and)) 
       (de-morgan (list 'not (car (cdadr exp)))) 
       (de-morgan (list 'not (cadr (cdadr exp)))))) 
     ;; otherwise some other expression 
     (t (cons (car exp) (mapcar #'de-morgan (rest exp))))))

источник

2016-02-09 16:24:28

Я думаю, что это будет немного чище с сопоставлением с образцом (через optima). Я думаю, что Emacs Lisp также имеет некоторый тип соответствия шаблону с 'pcase', но я не использовал это достаточно, чтобы знать, будет ли это работать для этого. – jkiiski

@jkiiski: yep, библиотека, соответствующая шаблону, поможет много. А не будет писать код без него, кроме как для крошечных упражнений. –

Emacs LISP - DeMorgan'ify a list

ответ

Смежные вопросы