суббота, 4 ноября 2017 г.

muParser

Вычисление строковых выражений

Юрий “yurembo” Язев

Не так давно передо мной встала задача вычисления математических выражений. Конечно, обычно записанное выражения вида: a = (4 + 6) – 4 * 2 вычисляется в 2 счета стандартными средствами любого языка программирования. Однако, когда выражение принимает вид: “a = (4 + 6) – 4 * 2”, то есть передается, как строка, ситуация усложняется. Никакой язык программирования не понимает выражения внутри строки. Такая задача распространена и достаточно часто встречается. Например, пользователь вводит в программу выражение целиком, или приложение читает выражение из файла, строки ввода или другого источника.

Первая приходящая в этом случае идея – написать свой парсер, который бы разбирал строку на операторы, операнды и осуществлял вычисления. И это вполне возможно. Между тем, стоит учесть большое количество математических операций, кроме вездесущих: +, –, *, / в математике есть: cos, sin, tan, asin, acos, log, sqrt, exp, etc., плюс логические операции: and, or, ==, <= и великое множество других. Прибавь к этому скобки и порядок вычисления. Из всего этого задача написания собственного парсера теперь не кажется простой. Еще к этому стоит прибавить необходимость удовлетворительной скорости парсинга, иначе перебор строк будет занимать долгое время.

Компиляция библиотеки и подключение ее к проекту


Решение – воспользоваться готовой библиотекой для парсинга математических выражений. Сделав небольшой ресерч, я остановил свой выбор на muParser. Во-первых, muParser – это проект с открытым исходным кодом, он обладает высокопроизводительным парсером для разбора строк и создания выражений, учитывая, как стандартные математические функции, так и пользовательские; в процесс вычисления можно добавить кастомные переменные и константы. Библиотека написана на C++, компилируется с любым современным компилятором. Имеет обертки для C и C#. Но последнее нам, в данном случае, не особо интересно, потому что мы будем использовать C++.

Давай откомпилируем либу из исходников, подключим ее к новому проекту, разберемся в ее возможностях более подробно и напишем  примерчик. muParser хоститься на GitHub, кроме того у либы есть своя страничка. Скачай с GitHub репозиторий muParser, распакуй его в удобный каталог. В подкаталоге build открой подпапку msvc2013. Я использую Visual Studio 2015, но проблем не обнаружил. В текущей папке открой решение muparser.sln. Согласись на обновление библиотек. В результате откроются 3 проекта: собственно, muparser, example1, example2, активным из которых будет первый. Из ниспадающего списка цели компиляции выбери Release Static. Я решил использовать статичную линковку в итоговом проекте, если у тебя другие планы, заюзай динамическую – Release DLL. Построй решение. Вместе с muparser будет скомпилирован example1. Можешь запустить последний и посмотреть его вывод. Кроме того, это приложение позволяет вводить любые математические выражения и получать соответствующие результаты. В подпапке lib будет создана итоговая статическая либа – muParser32.lib.

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


Параметры создания проекта можно оставить по умолчанию.


Надо подключить muParser к нашему проекту. Открой свойства проекта. В ниспадающем списке Configuration выбери All Configuration. Далее добавь пути к папкам с заголовочными файлами muparser и библиотечными файлами (в пункте VC++ Directories). 


Разверни свиток Linker перейди на пункт Input. В списке справа строку Additional Dependencies дополни именем подключаемой библиотеки: muparser32.lib; (перед Additional Dependencies). Щелчком по кнопке OK окно можно закрыть. Не забудь из ниспадающего списка цели проекта выбрать Release, поскольку у нас релизная библиотека. Если тебе понадобится дебажный проект, тогда надо собрать дебажную версию либы. На этом настройка проекта окончена.

Ознакомление с функционалом muParser


Основной алгоритм работы с либой заключается в объявлении переменных, функций и вычислении итогового выражения. У нас есть 2 способа работы с библиотекой: посредством класса и с помощью DLL-интерфейса. Для меня удобнее первый, кстати, поэтому я и сделал статическую линковку. Он позволяет использовать функциональность либы через методы объекта. Во втором случае, либа используется посредством прямого вызова функций. Для наглядности рассмотрим пример:

#include "stdafx.h"
#include <iostream>
#include "muParser.h"

// Function callback
double MySqr(double a_fVal)
{
    return a_fVal*a_fVal;
}

// main program
int main(int argc, char* argv[])
{
    using namespace mu;

    try
    {
        double fVal = 1;
        Parser p;
        p.DefineVar(L"a", &fVal);
        p.DefineFun(L"MySqr", MySqr);
        p.SetExpr(L"MySqr(a)*_pi+min(10,a)");

        for (std::size_t a = 0; a < 100; ++a)
        {
            fVal = a;  // Change value of variable a
            std::cout << p.Eval() << std::endl;
        }
    }
    catch (Parser::exception_type &e)
    {
        std::cout << e.GetMsg().c_str() << std::endl;
    }
    return 0;
}

Это стандартный пример с официальной страницы muParser, немного дополненный для возможности компиляции в Visual Studio 2015. Центральное место занимает объект класса Parser. Собственно, с его помощью выполняются все действия по инициализации и вычислению выражения. Вначале в программе определяется функция обратного вызова MySqr, которая будет использована в вычислении. Затем, уже в функции main() после определения переменной fVal, значение которой так же использующееся в вычислении, объявляется объект Parser пространства имен mu. Так как мы создали его в стеке, нам не понадобится удалять его, с другой стороны, при его создании/удалении в куче нам послужат new/delete. 

При вычислении строкового выражения математический аппарат muParser работает в своем пространстве, которое содержит константы, переменные, функции и выражения. Чтобы они там оказались, предварительно их надо туда добавить. Для этого служит внушительный набор функций и методов. Чтобы добавить в математический аппарат переменную, надо вызвать метод DefineVar объекта класса Parser:

p.DefineVar(L"a", &fVal);

Как видно в примере, метод принимает 2 параметра: имя переменной, используемой в аппарате – строкового типа mu:string_type. Этот тип muPaser соответствует стандартному строковому типу широких символов, от чего предваряется литерой L. Вторым параметром передается указатель на ранее объявленную и инициализированную переменную в C++-коде. muParser поддерживает переменные только типа double. Между тем, математический аппарат работает со своим универсальным типом данных: value_type, который соответствует числу с плавающей точкой единичной или двойной точности.
Константы внутри математического аппарата могут быть двух типов: double и string. Значения констант, в отличие от значений переменных, хранятся в байт-коде и не ссылаются на значения извне аппарата. Чтобы добавить в аппарат константу первого типа, участвующую в вычислении, надо вызвать метод DefineConst с теми же двумя параметрами, что в предыдущем случае. Для добавления константы типа string, надо вызвать метод DefineConst, он принимает строку – имя константы и строку – ее значение.
Кроме добавления переменных и констант в аппарат, их можно оттуда удалить. Для удаления именованной переменой достаточно вызывать метод RemoveVar, который принимает название удаляемой переменной. Чтобы удалить из аппарата все переменные надо вызвать метод ClearVar. С другой стороны, ClearConst удаляет все константы.
Для объявления пользовательской функции достаточно вызвать метод DefineFun с двумя параметрами: именем функции, по которому она будет вызываться внутри аппарата, и именем ранее объявленной в C++-коде функции:

p.DefineFun(L"MySqr", MySqr);

MySqr – ранее объявленная функция для вычисления квадрата параметра:

double MySqr(double a_fVal)
{
    return a_fVal*a_fVal;
}

После определения переменных, констант и функций внутри аппарата, можно в него передать выражение для вычисления. Это осуществляется с помощью метода: SetExpr:

p.SetExpr(L"MySqr(a)*_pi+min(10,a)");

Он принимает один параметр – строковое выражение, где могут быть использованы константы, переменные и функции, объявленные в аппарате ранее.

Когда все готово для вычисления математического выражения, для получения его результата достаточно вызвать метод Eval объекта класса Parser. Он ничего не принимает. В зависимости от того, какое выражение задано, в итоге, метод возвращает или значение типа double, или указатель на массив значений типа value_type. В первом случае, это стандартное выражение, возвращающее один результат, такое, как представлено выше. Во втором случае, это несколько выражений, записанных через запятую, например: sin(x),y+x,x*x. То есть каждое из них выдает свой результат, из чего формируется массив значений value_type, указатель на который возвращается перегруженной функцией Eval.

Приложение в работе

Как видно в примере выше: в математическом аппарате может возникать свой ряд исключений, принадлежащих типу Parser::exception_type. У этого типа существуют функции для получения различных сведений о произошедшей проблеме:
  • exception.GetMsg() – возвращает сообщение об ошибке;
  • exception.GetExpr() – возвращает текущую формулу, в которой произошло исключение;
  • exception.GetToken() – возвращает лексему, соответствующую данной ошибке;
  • exception.GetPos() – возвращает позицию в текущей формуле;
  • exception.GetCode() – возвращает код ошибки;

После того, как математический аппарат будет укомплектован, во время компиляции C++-кода, сформированное в muParser выражение будет преобразовано в byte-код. Дальнейшие вычисления производятся не с помощью строк, а в байт-коде. От этого вычисление выражения в итоговой программе выполняется очень быстро. Если при следующей компиляции выражение будет изменено, то байт-код будет перекомпилирован.

суббота, 2 сентября 2017 г.

Проектирование программного обеспечения

Юрий “yurembo” Язев

В идеале проектирование ПО, процесс, предшествующий непосредственно кодированию, должен по времени занимать столько же, сколько программирование. Этапы: проектирование, кодирование, тестирование, развертывание и поддержка составляют разработку.
В идеальном случае прежде, чем переходить к написанию кода, мы должны четко представлять цель программы: для чего она создается, кто ее будет использовать, в каких условиях, представлять дальнейшие стадии развития и усовершенствования. Каждый участник группы разработки должен обладать полным набором сведений о создаваемом программном продукте. Каждый конкретный разработчик должен обладать узкоспециализированными сведениями и целями о разрабатываемом им модуле или компоненте общей системы. В дополнение к этому должны быть согласованы и определены выполняемые задачи на высшем уровне, объявлены интерфейсы, через которые будут взаимодействовать подсистемы программного продукта, созданы абстрактные классы. В результате, для создания законченного проекта после проектирования программисту останется добавить реализацию заготовленных классов и объектов, что, в итоге, и составит 50% работы.
Между тем, в подавляющем большинстве отечественных проектов программного обеспечения к этапу проектирования относятся, как к необязательному и проводят поверхностно, ошибочно сразу переходя к кодированию, на ходу придумывая систему. Из-за такого отношения подсистемы получаются несовместимыми, задачи выполняются некорректно, компоненты не согласованы и другие фундаментальные проблемы. При переделке появляются новые несовместимости. Ком ошибок растет. В итоге получается говнокод с костылями.
Поэтому при разработке программного обеспечения рекомендуется не пропускать этап проектирования. Нужен системный подход к вопросу, иначе ничего спроектировано не будет.

ООАП

Существует замечательная книжка «Объектно-ориентированный анализ и проектирование» авторов: Б. Маклафин, Г. Поллайс, Д. Уэст, издательства O’Reilly, серии Head First. В книге подробно на примерах разжевывается техника проектирования программ, она полна полезных советов в различных областях разработки программного обеспечения. Мне понравилась данная книга, и я хочу в переосмысленном виде выписать из нее несколько вдохновивших меня моментов. В конце статьи для примера приведу проект своей программы, разработанный согласно описанным в книге методам.
Методология «Объектно-ориентированный анализ и проектирование» включает широкий ряд шагов для создания не только полной и расширяемой архитектуры, но и законченного программного продукта. Под архитектурой программного обеспечения понимается организационная структура системы, которая выделяет важнейшие части приложения и отношения между ними. С этих важнейших частей, собственно, стоит начинать разработку.

3 основных шага

За проектом любой программы стоят 3 основных шага:
  1. Первое – будь человеком. Пойми ближнего своего, то бишь заказчика. Необходимо убедиться, что ты понимаешь цель программы ровно так же, как заказчик. В его роли может выступить начальник и другие жаждущие нового ПО лица.
  2. Применяй базовые принципы объектно-ориентированного проектирования для повышения гибкости программного продукта.
  3. Всегда помни, что качественное ПО разрабатывается не один раз. Мы ведь говорим о программах промышленного уровня. Поэтому через определенный промежуток времени после выпуска первой версии приложения, к нему надо будет вернуться для доработки, улучшения, внесения изменений и модификации.

Как быть программистом и человеком одновременно?

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

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

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

Что за базовые принципы объектно-ориентированного проектирования?

ОО-принципы с пояснениями

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

  1. Делегируйте (поручайте) выполнение некоторой операции другому классу или методу.

  1. Программируйте для интерфейса, а не для реализации.
Приложение становится более гибким. Вместо работы с одним конкретным субклассом вы сможете работать с общим интерфейсом. Следовательно, ваш код сможет работать с любым субклассом.
Программирование для интерфейса (а не для реализации) упрощает расширение ваших программ. При программировании для интерфейса ваш код будет работать со всеми субклассами этого интерфейса, даже с теми, которые еще не созданы.
Абстрактные классы могут рассматриваться, как условные «представители» конкретных классов реализации. Абстрактный класс определяет поведение, а субклассы это поведение реализуют.

  1. Каждый класс в приложении должен иметь только одну причину для изменения.
Таким образом сводится к минимуму вероятность изменения класса. Если класс имеет более одной причины для изменения, то скорее всего, он пытается делать слишком много всего сразу. Тогда надо разбить его функциональность на несколько классов, чтобы каждый класс делал что-то одно, а, следовательно, имел одну причину для изменения.

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

  1. Классы должны быть открыты для расширения, но закрыты для изменения (OCP).

  1. Избегайте дублирования кода, абстрагируя общие аспекты классов и размещая их в одном месте (DRY).

  1. Каждый объект в системе должен иметь одну обязанность, и вся работа объекта должны быть сосредоточена на выполнении этой единственно обязанности (SRP).


  1. Замена базового типа субтипом не должна отразиться на работе программы (LSP).

Еще об объектно-ориентированном анализе

Большинство хороших структур строится на основе анализа плохих структур. Не бойтесь совершать ошибки и исправлять их.

Сцепление – степень логического сопряжения элементов одного модуля, класса или объекта. Чем выше сцепление программного продукта, тем четче определены обязанности каждого класса приложения. Каждый класс обеспечивает выполнение четко определенного набора взаимосвязанных действий. Класс с высоким сцеплением хорошо делает что-то одно и не пытается делать что-то другое.

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

Применение проверенных принципов ОО-проектирования улучшает гибкость, удобство сопровождения и расширения программы.

Принципы проектирования

  1. Принцип открытости/закрытости (OCP – Open\Closed Principle). Классы должны быть открыты для расширения, но закрыты для изменения. Этот принцип допускает изменения, но только те, которые предотвращаю необходимость переписывания существующего кода.

  1. Не повторяйтесь (Don’t Repeat Yourself). Избегайте дублирования кода, абстрагируя общие аспекты и размещая их в одном месте. Суть принципа DRY в том, что каждый блок информации и поведения в системе должен существовать в одном разумно выбранном месте.

  1. Принцип единственной обязанности (SRP – Single Responsibility Principle). Каждый объект в системе должен иметь единственную обязанность, и все действия объекта должны быть сосредоточены на ее выполнении. Если в этой обязанности что-то изменится, вы будете точно знать, где следует внести изменения в коде.

  1. Принцип подстановки Лисков (LCP – Liskov Substitutional Principle). Замена базового типа субтипом не должна отражаться на работе программы. Суть принципа LCP заключается в правильно спроектированной иерархии наследования.

Отношения классов

  1. Наследованием называется реализация субтипом открытой и защищенной функциональности супертипа.

  1. Делегированием называется поручение выполнения некоторой операции другому классу или методу.
Если вам потребуется использовать функциональность другого класса без его изменения, рассмотрите использование делегирования вместо наследования.

  1. Композиция позволяет использовать поведение из семейства других классов и изменять это поведение на стадии выполнения.

  1. Агрегирование – использование одного класса как части другого с возможностью существования за его пределами.

  1. Наследование относится к отношениям типа «является».
  2. Отношения «сдержит» относятся к композиции и агрегированию.

Итеративная разработка

Этап проектирования


Во время проектирования классов надо сначала выполнить текстологический анализ варианта использования, найти существительные, которые являются кандидатами для классов, затем глаголы – кандидаты для операций.

  1. Список функциональных возможностей.
Определите, что должно делать ваше приложение на высоком уровне.
  1. Диаграммы вариантов использования.
Выделите масштабные процессы, выполняемые приложением, и все задействованные внешние факторы.
  1. Разбиение задачи.
Разбейте приложение на функциональные модули и решите, в каком порядке вы будете их рассматривать.
  1. Требования.
Сформулируйте отдельные требования для каждого модуля и убедитесь в том, что они соответствуют общей картине.

Варианты использования отражают типичное использование, а функциональные возможности — функциональность приложения.

Функциональные возможности — это описание того, что делает система. Они не всегда напрямую отражаются в вариантах использования. Функциональные возможности и варианты использования работают вместе, но это не одно и то же.

Этап написания кода

  1. Хорошие программы пишутся методом итераций.
  2. Поработай над общей картиной.
  3. А потом над каждым фрагментом приложения.

  1. Анализ предметной области. Определите соответствия между вариантами использования и объектами приложения. Убедитесь в том, что представления заказчика совпадают с вашими.

  1. Предварительное проектирование. Заполните подробную информацию об объектах, определите отношения между объектами, примените принципы и паттерны.

  1. Реализация. Напишите код, протестируйте его и убедитесь в том, что он работает. Проделайте это для каждого аспекта поведения, каждой функциональной возможности, каждого варианта использования и каждой задачи, пока реализация приложения не будет завершена.

  1. Публикация. Готово! Выпустите в свет свой продукт, представьте счета к оплате и получите деньги.

Методы итеративной разработки

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

  1. При функционально-ориентированной разработке вы работаете над одной функциональной возможностью и полностью программируете ее поведение. Только после завершения можно переходить к следующему аспекту приложения.

  1. При разработке через тестирование сначала пишутся тесты для функционального блока и только потом программируется сама функциональность.

Хорошо организованный процесс разработки обычно включает все эти модели на разных стадиях цикла разработки.

Углубление итераций: 2 основных варианта

  1. Функционально-ориентированная разработка: вы выбираете конкретную функциональную возможность приложения, планируете, анализируете и разрабатываете ее до завершения.

  1. Сценарно-ориентированная разработка: вы выбираете конкретный сценарий в варианте использования и пишете код реализации этого сценария в варианте использования.

Разработка через тестирование направлена на реализацию правильного поведения классов.

Существует 2 методологии безопасного программирования

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

Цель ООАП — обилие возможностей. У задачи никогда не существует единственно правильного решения, поэтому чем больше у вас возможностей, тем выше вероятность того, что вам удастся найти хорошее решение.


Итог: разработка в стиле ООАП

  1. Беседа с заказчиком. Выявление всех требований к приложению.
  2. Список функциональных возможностей. Определите, что должно делать ваше приложение на высоком уровне.
  3. Диаграммы вариантов использования. Выделите масштабные процессы, выполняемые приложением, и все задействованные внешние факторы.
  4. Разбиение задачи. Разбейте приложение на функциональные модули и решите, в каком порядке вы будете их рассматривать.
  5. Требования. Сформулируйте отдельные требования для каждого модуля и убедитесь в том, что они соответствуют общей картине.

Пример проекта программы

LearnFillWordsConstructor


Беседа с заказчиком

Нужна программа для подготовки уровней для игры LearnFillWords. Эта игра представляет собой типичные филворды, т.е. составление слов путем выбора букв на клетчатой доске, где в каждой клетке находится определенная буква. Только в нашей игре игроку дается задание на нахождение определенного слова. А именно, показывается слово на русском или английском языках, после чего пользователь должен найти перевод на противоположном языке для показанного слова. Уровень может содержать одно или более слов.

Функциональные возможности

  1. Приложение создает уровни для игры LearnFillWords.
  2. Приложение открывает ранее созданные уровни для игры LearnFillWords.
  3. Приложение позволяет задать количество ячеек по вертикали и горизонтали.
  4. Приложение позволяет настроить свойства для каждой ячейки.
  5. Приложение сохраняет уровень в файл.

Варианты использования

  1. Level-designer создает новый уровень
    1. Level-designer открывает ранее созданный уровень
  2. Level-designer модифицирует уровень
    1. Выбирает количество клеточек
    2. Назначает клеточкам буквы
    3. Назначает клеточкам загаданное слово
    4. Устанавливает порядок выбора клеточек для составления слова
    5. Задает общие свойства для уровня
      1. Фоновая текстура
      2. Загаданное слово/слова
  3. Level-designer сохраняет уровень в файл

Разбиение задачи

  1. Модуль для работы с уровнем: создание, сохранение, загрузка.
  2. Модуль для работы с ячейками: задание их свойств.

Определение требований

  1. Оконное приложение, имеющее графический интерфейс, должно работать в ОС Windows, поддержка других ОС не нужна.
  2. Приложение позволяет создать уровень с количеством клеточек по ширине и длине от 1 до 16.
  3. Задание свойств ячеек.
  4. В зависимости от режима игры (русский или английский) создаются соответствующие буквы.
  5. Буква представляет собой растр.
  6. Некоторые свойства уровня:
    1. Количество ячеек по горизонтали
    2. Количество ячеек по вертикали
    3. Фон (растр)
    4. Загаданное слово/слова
  7. Некоторые свойства ячеек:
    1. Буква
    2. Слово, в которое входит буква
    3. Порядковый номер в слове
  8. Сохранение файла уровня в XML-формате

А потом начинается итеративная разработка, на каждом этапе которой приведенные шаги повторяются для выяснения подробностей.