30 декабря 2011

Common Lisp. Embeddable Maxima #2.

С наступившим новым годом, друзья!

Updated 01.01.2012

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

В заметке используется слово "лисп", которое означает словосочетание "common lisp" :)

Максима умеет математику решать в символьном виде.

Как я уже говорил, Максиму на данный момент лучше взять в моем репозитарии ветку quicklisp:

https://github.com/filonenko-mikhail/embeddable-maxima/tarball/quicklisp или так:
git clone http://github.com/filonenko-mikhail/embeddable-maxima
git checkout quicklisp
или так добавить в оригинальный репозитарий:
 git remote add fm_github http://github.com/filonenko-mikhail/embeddable-maxima.git
 git fetch --depth 1 fm_github quicklisp:refs/remotes/quicklisp
 git checkout -b quicklisp --track fm_github/quicklisp

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

Кстати, вот экономический вопрос: что дешевле: научить пользователей предметно-ориентированному языку или подмножеству функций и конструкций хост-языка? Может проще научить математиков префиксной нотации, чем запиливать под них трансляторы, интепретаторы, компиляторы?

Теперь, собственно, код. Все выражение вводимые в Максиму транслируются в AST. AST - это дерево. Дерево в Лиспе представляется списками, элементы которых могут быть списками. Затем данное дерево интерпретируется так, как это реализовано в Максиме. Таким образом, кстати, реализован движок cl-closure-templates, где на основе AST, получаемого при разборе шаблона, генерируется лисповый генератор и с помощью parenscript javascript'овый.

Решение СЛАУ на Лиспе

Запуск окружения, все как обчыно:

emacs
 M+x slime
  (pushnew "/path/to/maxima/" asdf:*central-registry*)
  (ql:quickload :embeddable-maxima)
  ;; переходим в пакет максимы так как из нее ничего не экспортируется
  (in-package :maxima)

Допустим у нас есть список уравнений на языке Максима:

[2*x + y - z = 8, -3*x - y + 2*z = -11, -2*x + y + 2*z = -3]
Посмотрим как он выглядит в лисповом варианте. Для этого у Максимы есть лисповый макрос #$expr$:
#$[2*x + y - z = 8, -3*x - y + 2*z = -11, -2*x + y + 2*z = -3]$

((MLIST SIMP)
 ((MEQUAL SIMP) ((MPLUS SIMP) ((MTIMES SIMP) 2 $X) $Y ((MTIMES SIMP) -1 $Z)) 8)
 ((MEQUAL SIMP)
  ((MPLUS SIMP) ((MTIMES SIMP) -3 $X) ((MTIMES SIMP) -1 $Y)
   ((MTIMES SIMP) 2 $Z))
  -11)
 ((MEQUAL SIMP) ((MPLUS SIMP) ((MTIMES SIMP) -2 $X) $Y ((MTIMES SIMP) 2 $Z))
  -3))
Теперь давайте вызовем максимовскую функцию solve для решения системы уравнений. В лисповом окружении она имеет имя $solve:
($solve #$[2*x + y - z = 8, -3*x - y + 2*z = -11, -2*x + y + 2*z = -3]$)

((MLIST) ((MLIST) ((MEQUAL) $Z -1) ((MEQUAL) $Y 3) ((MEQUAL) $X 2)))
Для того, чтобы перевести лисповое выражение обратно в максимовское можно воспользоваться лисповой функцией displa, напрмер так:
(displa '((MLIST) ((MLIST) ((MEQUAL) $Z -1) ((MEQUAL) $Y 3) ((MEQUAL) $X 2))))

[[z = - 1, y = 3, x = 2]]
Неполное описание AST.
MLIST - является списком
SIMP - упрощено. (FIXME?)
MEQUAL - равенство из двух элементов
MPLUS - сумма
MTIMES - произведение
MDEFINE - определение функции
MPROGN - progn
$SOME_FUNCTION - вызов функции SOME_FUNCTION
....

Вызов функции определенной во время работы Максимы рекомендуют делать через mfuncall, однако функция $solve определена в Лиспе в исходниках, поэтому ее можно вызвать, как регулярную.

Теперь вы можете использовать чистый Лисп для символьных вычислений. Один способ, использовать макрос #$expr$ и функцию displa, другой - имитировать максимовскую AST с помощью обычных списков.

Дифференцирование в Лиспе

Давайте найдем производную функции:

1/3*x^3 + 1/2*x^2 + 1

Для этого используется функция diff.

($diff #$1/3*x^3 + 1/2*x^2 + 1$ #$x$)

((MPLUS SIMP) $X ((MEXPT SIMP) $X 2))

Или же в более читабельном виде:

(displa '((MPLUS SIMP) $X ((MEXPT SIMP) $X 2)))

 2
x  + x

Интегрирование в лиспе

Интеграл от предыдущей функции:

x^2 + x

Функция integrate:

($integrate #$x^2 + x$ #$x$)

((MPLUS SIMP) ((MTIMES SIMP) ((RAT SIMP) 1 2) ((MEXPT SIMP) $X 2))
 ((MTIMES SIMP) ((RAT SIMP) 1 3) ((MEXPT SIMP) $X 3)))

Читабельный вид:

(displa '((MPLUS SIMP) ((MTIMES SIMP) ((RAT SIMP) 1 2) ((MEXPT SIMP) $X 2))
 ((MTIMES SIMP) ((RAT SIMP) 1 3) ((MEXPT SIMP) $X 3))))

 3    2
x    x
-- + --
3    2

Кстати не отобразил свободный член (+C). Данная константа появляется при использовании равенства, а не выражения.

(displa ($integrate #$x^2 = - x$ #$x$))

 3          2
x          x
-- = %c2 - --
3          2

Вспомогательные материалы из справки Максима

37 Program Flow

37.1 Lisp and Maxima

Так как Максима написана на Лиспе, то в ней легко получать доступ к функциям и переменным Лиспа, и наоборот из Лиспа можно использовать функции и переменные определенные на языке Максима. Символы Лиспа и Максимы отличаются с помощью правил наименования. Символы лиспа, что начинаются со знака доллара "$" доступны из Максимы, как символы без знака доллара.

Символы Максимы, что начинаются со знака вопроса "?" доступны в Лиспе под именем без знака вопроса. Например, символ Максима foo доступен в Лиспе, как $FOO, тогда как символ Максима ?foo доступен в Лиспе, как FOO. Следует отметить, что ?foo пишеться без пробела между ? и foo, иначе будет ошибка.

Когда дефис "-", знак умножения "*" и другие специальные знаки для Лиспа, встречаются в символах Максимы они должны быть экранированы с помощью обратного слеша "\". Например: лисповый идентификатор *foo-bar* должен быть записан в Максиме так: ?\*foo\-bar\*.

Код на Лиспе может быть вызван из сессии Максимы. Однострочный код (содержащий одну и более форм) может быть вызван с помощью специальный команды Максимы: :lisp. Например: (%i1) :lisp (foo $x $y) вызывает функцию Лиспа foo с переменными из Максимы x и y в качестве аргументов. Конструкция :lisp может использоваться в интерактивной командной оболочке или в файле обрабатываемом с помощью batch или demo, но не с помощью load, batchload, translate_file или compile_file. Функция to_lisp открывает интерактивный командную оболочку Лиспа. Вызов (to-maxima) закрывает оболочку Лиспа и возвращает в оболочку Максимы.

Функции и переменные Лиспа, которые должны быть доступны в Максиме без изменений в названиях должны иметь символы, начинающиеся со знака доллара "$".

Максима чувствительна к регистру и различает прописные и строчные буквы в идентификаторах. Вот некоторые правила трансляции имен между Лиспом и Максимой.

1. Идентификатор в Лиспе, не заключенный в вертикальные скобки, преобразуется в идентификатор Максима в нижнем регистре вне зависимости от регистра символов. Например: лисповые $foo, $FOO и $Foo все преобразуются в foo. Это потому, что лисп ридер не различает регистр и все получаемое возводит в верхний регистр.

2. Лисповый идентификатор, содержащий все буквы или в верхнем, или в нижнем регистре и облаченный в вертикальные скобки преобразуется в символ максимы в противоположном регистре. Например: лисповые |$FOO| и |$foo| преобразуются в foo и FOO соответственно.

3. Лисповый идентификатор содержащий микс из регистров и заключенный в вертикальные скобки транслируется в максиму без преобразований. Например: лисповый |$Foo| транслируется в Foo.

Вот теперь самое важное и удобное, с помощью чего можно проводить эксперименты.

Лисповый макрос #$ позволяет использовать выражения Максимы в лисповом коде. #$expr$ разворачивает выражение Максимы в выражение на Лиспе.

Примеры:

(msetq $foo #$[x, y]$)
<=>
(%i1) foo: [x, y];

Лисповая функция displa выводит выражение в формате Максимы.

(%i1) :lisp #$[x, y, z]$
((MLIST SIMP) $X $Y $Z)
(%i1) :lisp (displa ’((MLIST SIMP) $X $Y $Z))
[x, y, z]
NIL

Функции определенные в Максиме не являются обычными лисповыми функциями. mfuncall вызывает функции Максимы. Например:

(%i1) foo(x,y) := x*y$
(%i2) :lisp (mfuncall ’$foo ’a ’b)
((MTIMES SIMP) A B)

Некоторые лисповые функции скрыты в пакете максимы, а именно:

complement   continue    //      
float        functionp   array   
exp          listen      signum  
atan         asin        acos    
asinh        acosh       atanh   
tanh         cosh        sinh    
tan          break       gcd     

Функция solve

solve (expr, x)
solve (expr)
solve ([eqn 1, . . . , eqn n], [x 1, . . . , x n])

Решает алгебраическое уравнение expr для переменной x и возвращает список решений. Если expr не является уравнение, предполагается равенство его нулю expr = 0. x может являтся функцией (например: f(x)) или другим не-атомным выражением, кроме суммы или произведения. x может быть опущен, если expr содержит только одну переменную. expr может быть рациональным выражение и может содержать тригонометрические функции, экспонентциальные и т.п.

solve ([eqn 1, ..., eqn n], [x 1, ..., x n]) решает системы simultaneuos (совместных?) (линейных и нелинейных) полиноминальных уравнений с помощью функций linsolve или algsolve и возвращает список решений. Функция принимает два аргумента. Первый - это список уравнений. Второй - список неизвестных переменных. Если число неизвестных совпадает со числом уравнений, второй аргумент может быть опущен.

10 комментариев:

  1. Спасибо, как всегда отличная статья!
    С наступающим, успехов во всех начинаниях!!!

    P.S. По поводу "конечный автомат никем не используется" добавлю свои 5 копеек:

    В ASDF в весьма ответственном месте использовался конечный автомат. И в нём был некий баг. С моей подачи исправили этот баг и заодно убрали конечный автомат нахрен и заменили на гораздо более прозрачный и вменяемый код.

    --------------
    LinkFly

    ОтветитьУдалить
  2. > Сначала было хотел написать аналитическую статью..
    хорошая тема. надеюсь еще напишите) дайте две!

    З.Ы. круто. а на сколько сложнее такое делается с оригинальной максимой?

    ОтветитьУдалить
  3. Во, спасибо, как раз недавно начал использовать максиму для расчетов, и сразу захотелось задействовать лисп для написания скриптов. А тут такая полезная статья :) И Вас с наступающим!

    ОтветитьУдалить
  4. Круто. Надо найти задачу чтобы использовать это. Rigidus

    ОтветитьУдалить
  5. @LinkFly: да поэтому и решил пока не браться, надо продумать.

    @anton0xf Хороший вопрос. вот здесь оригинальная максима, ветка quicklisp:
    https://github.com/filonenko-mikhail/orig-maxima
    возможно у меня получится модифицировать код сохранив историю git'а.

    @Дож Спасибо

    @Rigidus Можно spreadsheet сделать, этакий с символьными возможностями. Можно генератор математических задач для школьников.

    ОтветитьУдалить
    Ответы
    1. Окончательный репозитарий:
      https://github.com/filonenko-mikhail/embeddable-maxima

      Удалить
  6. Фух, вообще перерефакторил весь проект с сохранением истории. Теперь можно взять обычный репозитарий максимы и слить туда ветку quicklisp из моего.
    Как забрать обновлено в статье.

    Усиленно лоббирую свои интересы в списке рассылки максимы. С каждым письмом разочарование в опенсорсе возрастает все больше.

    В любом маломальском предприятии должен быть лидер. Или группа их, с чередованием ответственностей в времени. И вообще должен быть кто-то, кто будет получать *лей за каждую некрасивую строчку кода. А то развели там нюни, видите ли код старый, видите ли кроссплатформенность, разработчиков не хватает. Да там у максимы инфраструктура вообще нулевая, математика сильна не спорю. Но инфраструктурный код оброс наколенными решениями.

    Накипело...

    ОтветитьУдалить
  7. Глупый вопрос от несведущего. Пытаюсь вызвать так:

    CL-USER> (displa ($solve #$[2*x*x+x=0]$))

    Говорит мол "undefined function: $SOLVE", "undefined function: DISPLA". Из (in-package :maxima) работает, но мне нужно именно из CL-USER запускать...
    Думаю ладно, укажу пакет:

    CL-USER> (maxima:displa (maxima:$solve #$[2*x*x+x=0]$))

    Вопит мол "The symbol "DISPLA" is not external in the MAXIMA package", "The symbol "$SOLVE" is not external in the MAXIMA package" - и висит пока дважды не подтвердить "Use symbol anyway", как сделать чтоб молча считал и не ругался?

    ОтветитьУдалить
    Ответы
    1. Символы не являются внешними. В таком случае доступ к ним осуществляется с помощью двух двоеточий:

      (maxima::displa (maxima::$solve #$[2*x*x+x=0]$))

      Удалить
    2. Благодарю) Кстати через import тоже работает, тока подтверждения хотит (на всякий случай):

      (import 'maxima:displa)
      (import 'maxima:$solve)
      (displa ($solve #$[2*x*x+x=0]$))

      Удалить