Рекурсивное программирование на ЛИСП – решатель формул

    Решатель формул сам по себе очень интересная тренировка, и в определённый момент эта тренировка может очень пригодиться в другой задаче – конструировании новой формулы, автоматической её проверке (погрешность, просчёт значений по списку координат)… И excel вам не поможет, да и неспортивно.


    Сразу оговорюсь — код сделан для ЛИСПа образца 87 года, и свежий Common LISP его категорически не поймёт, что печально… Но — 2 шага от ЛИСП-кода до понимания, как то же самое написать в более пристойном для практической задаче С# или Delphi, в ЛИСПе даётся более милое моему сердцу и глазу исполнение)

    Ввод формулы с клавиатуры, против жёсткого задания в коде, имеет массу плюсов. Как осуществить его программист задумывался, пожалуй, со школьного железного стула. Задача велика, и кажется невыполнимой, но главное – начать. Начинаем>>

    1. Как будет записываться формула?


    Обычная запись для первого шага излишне сложна. Польская форма записи – воспользуемся ей. И операции над числами запишутся в виде списков, которыми можно задать самое сложное математическое выражение:
    #
    2+3->(+ 2 3)
    2-3->(- 2 3)
    2*3->(* 2 3)
    2/3->(/ 2 3)
    2+3+5->(+ 2 3 5)
    2+3*5->(+ 2 (* 3 5))
    (2+3)*5->(* (+ 2 3) 5)


    2. Как оно будет работать? (простые формулы)



    Напишем решатель (solver) в рево… рекурсивном духе ЛИСПа: он будет хватать из списка первый элемент голову, и далее обрабатывать хвост в соответствии со значением головы. На вход решатель получает каждый раз формулу (a), результат предыдущего действия (b), знак © и, если предусмотреть это заранее, то и значения неизвестных параметров (xx).

    (defun solver (a b c xx)
    ((null a) b)
    ((equal (searchx a) NIL) (solver (presolver a NIL xx) T c xx))
    ((eq (atom a) T) a)
    ((equal c NIL) (solver (cdr (cdr a)) (car (cdr a)) (car a) xx))
    ((equal c ps) (solver (cdr a) (+ b (car a)) c xx))
    ((equal c ms) (solver (cdr a) (- b (car a)) c xx))
    ((equal c mu) (solver (cdr a) (* b (car a)) c xx))
    ((equal c di) (solver (cdr a) (/ b (car a)) c xx))
    )


    Неизвестные параметры, указанные в формуле своими именами # (+ x 5)) должна заменить на значения соответствующая функция. Причём до решателя. Обзовём её предрешатель (presolver), на вход ей подаём формулу, результат (при вызове из решателя – NIL) и значение неизвестной для подстановки на место элемента ‘х’ (выделяю здесь это специально, ибо ЛИСП не различает, хвала Господу, типов данных)

    (defun presolver (a b xx)
    ((null a) (revers b))
    ((eq (car a) x) (presolver (cdr a) (cons xx b) xx))
    ((eq (equal (car a) x) NIL) (presolver (cdr a) (cons (car a) b) xx))
    )


    И – наличие неизвестных ещё нужно подтвердить. Рождается функция поиска неизвестной, searchx, a заодно и функция реверса списка revers, ибо результат presolver-a по-умолчанию выходит задом наперёд.

    (defun searchx (a)
    ((null a) T)
    ((equal (car a) x) NIL)
    (searchx (cdr a))
    )


    (defun revers (a b)
    ((null a) b)
    (revers (cdr a) (cons (car a) b))
    )


    Запускаем-проверяем-

    (solver '(ps x 2 3) NIL NIL 5)

    -ура-работает. Но – только на простых формулах, со списками без вложенных списков, с элементами-атомами.

    3. Как оно будет работать-2? (сложные формулы)



    Можно долго думать, каким интересным образом превратить простой солвер в сложный, но мы пойдём более рациональным путём – не будем трогать работающий кусок, а станем заниматься проектом solver2 – решателем сложных формул.

    (defun solver2 (a xx)
    ((eq (iseasy a) T)
    (solver a NIL NIL xx))
    ((eq (atom (car a)) T)
    (solver (cons (car a) (solver2 (cdr a) xx)) NIL NIL xx))
    ((eq (iseasy (car a)) T)
    (cons (solver (car a) NIL NIL xx) (solver2 (cdr a) xx)))
    ((eq (iseasy (car a)) NIL)
    (cons (solver2 (car a) xx) (solver2 (cdr a) xx)))
    )


    Каждая сложная формула содержит в себе хотя бы один элемент-список. Но начнём с проблемы совместимости, чтобы новая функция работала хотя бы для простых вычислений. Для этого нужно формулу на вход проверить на простоту, и если простая – отправить к solver-у, а вот если сложная – подумать над ней ещё немного.

    Определить прост список или не совсем поможет функция iseasy с единственным входным параметром – собственно формулой. Iseasy видит элемент не-атом – и выпадает с ответом NIL

    (defun iseasy (a)
    ((null a) T)
    ((equal (atom (car a)) Nil) NIL)
    (iseasy (cdr a))
    )


    Далее всё просто, и одновременно изящно-непонятно. Правильность работы функции очевидна, но неочевиден алгоритм. Он же таков:
    — Сначала solver2 проверяет формулу целиком на простоту. Если формула проста целиком, её можно и нужно решить solver-ом.
    — Далее идёт проверка – «а не атом ли голова у формулы ‘а’?» Если голова – атом бренный, то отправляем solver-у конструктор из этого атома и хвоста, требующего повторного рассмотрения solver2
    — Если первые 2 проверки не прошли, что-то с формулой определённо не так (кажется и мне через 2 года после написания кода), то мы должны проверить голову формулы на простоту, и если таковая проста (НО не атом! – а значит список), отправим запустившей solver2 функции конструкцию из решённой головы и рассмотренного повторно solver2 хвоста формулы. Например, «на экран»… Наверное, это какой-то bugreport?
    — Если первые 3 проверки не прошли (совсем беда, это значит что формула не проста, в голове этой формулы стоит не атом (т.е. не знак ±/*/:), и даже не список из атомов, выдадим «на экран» конструкцию из просмотренной повторно solver2 головы и хвоста, также с ревизией solver2

    Запустите…
    (solver2 '(mu (ps x 2 3) (ms x 5)) 10)
    Удивитесь

    4. Почему оно работает? (заключение)



    Очевидно, что solver2 в приведённом коде умеет считать простые формулы. Но как, запустив его, он считает и сложные? Зрение в рекурсивном программировании весьма обманчиво.

    Каждая правильная формула начинается с атома операции. Проследи за действиями ЛИСПа, читатель: solver2 начинает решать правильную сложную формулу, и отправляет на решатель конструкцию из головы этой формулы (знак), и… пересмотренного хвоста в самом себе. Хвост приходит на solver2 и, естественно, не содержит в голове атома операции. Поэтому заслуженно отправляется на дальнейшее упрощение solver2…

    В чём его суть, что он делает, этот solver2? В общем-то ничего, ещё проще — он берёт список и заменяет его на число… В конце концов любая сколь угодно длинная формула, даже с 10-кратной вложенностью свернётся до простого списка, со знаком в голове и с хвостом, состоящим из одних только атомов, причём все атомы будут числами. Красиво, и абсолютно непостижимо по коду, непостижимо и на первом шаге написания функции)… За что РП и люблю.
    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 10

      +1
      Хорошая статья. Неплохо бы в блог lisp перенести
        –1
        Капитан такой капитан.
          0
          Насколько я понимаю (писал то же самое, называлось Миксима, на первом курсе в 2002 году на современный лисп), этот код просто выдран из книги какого-то лохматого года (книга с тонком переплёте, иностранный дядя писал).

          Было бы лучше, если бы Вы переписали на современный лисп, что когда-то у далось мне с напарником по индивидуальной.
            +1
            Вот книга. Глава 4.2 www.zodchii.ws/books/info-505.html
              0
              Неправда ваша, код самолично писан с 1 до последней скобки весной-осенью 2007года)… Конечно не уникальная это задача, но первенство в её открывании/решении ничьё не оспариваю. Хотя бы то, что не самым оптимальным образом она решена — моё оправдание)
                0
                :) не буду спорить. Готов поверить, ибо действительно, задача распространённая. Правда в коде не разирался, ибо я не помню уже лисп. Поэтму и не мог знать о неоптимальности решеия ;)
                  0
                  Всегда считал кривым своё решение из-за 4 условий в solver2… По хорошему, ИМХО, он должен искать первый попавшийся простой список и отдавать его на решение solver, и так крутить, пока… в общем, эту идею я тогда так и не воплотил, и получилось 4-вариантное нечто))… Наверное, можно предположить, что выход из рекурсии должен осуществляться по проверке ((eq (atom a) T) a)…

                  Как-то так) За ссылки кстати спс, у меня есть небольшая библиотека электронной литературы по ИИ, теперь и 2 тома Хьювенена там)
                    0
                    Да не за что, я помню, как в читальном зале университета переписывал нужные мне главы с кодом из этой книги. Книга старая, поэтому не давали её копировать :)
            +1
            Скажите, в лиспе так принято — называть все параметры у функций буквами a, b, c? Я еще не знаю лиспа но с точки зрения «нормального» программирования это как-то дико.
              0
              если программа мала и служит «лабораторно-испытательной установкой» — почему нет? Тем более что это не объектное программирование, ассоциаций с объектами реального мира мало)

              Тем не менее, оченно ценное замечание. Попробую на досуге переделать код так, чтобы переменные обрели смысл — и сравним)

            Only users with full accounts can post comments. Log in, please.