что такое формализованный подход

Большая Энциклопедия Нефти и Газа

Формализованный подход

Формализованный подход позволяет избежать ошибок субъективизма, обязательных при неформализованном подходе. [2]

Формализованные подходы к алгоритмам в информатике обладают высокой образовательной ценностью. [4]

Децентрализация управления требует формализованного подхода к организационной структуре компании, охватывающего все структурные единицы сверху донизу и определяющего место каждого подразделения ( отделения, сегмента) с точки зрения делегирования ему определенных полномочий и ответственности. [8]

В монографии излагается общий формализованный подход к математическому моделированию сложных химических равновесий любого состава и механизма. Впервые физико-химические и математико-статистиче-ские аспекты проблемы равновесий представлены в системном целенаправленном объединении, рассматриваются оригинальные теоретические выводы и практические результаты, полученные авторами. Монография дает возможность читателю практически полностью овладеть арсеналом средств математического моделирования химических равновесий с использованием современных ЭВМ. [9]

Покажем, как развитый выше формализованный подход может быть использован в задаче, связанной с оптимизацией одной из химико-технологических схем. [11]

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

Для создания графического диалога предлагается формализованный подход к описанию параметров чертежей, который дает возможность создавать иерархическую структуру, положенную в основу программных средств, реализующих взаимодействие человека с ЭВМ и отображение графических объектов. [13]

В настоящее время нет единого формализованного подхода к проектированию процесса крепления скважин, поэтому не сформулировано четкого понятия способа крепления. Существуют указания [29], что скважина крепится обсадными колоннами, спускаемыми целиком и секциями ( хвостовиками), а колонны, в свою очередь, цементируются различными способами: сплошным, в две или несколько ступеней с разрывом во времени, двумя или более секциями, обратным способом. [15]

Источник

Большая Энциклопедия Нефти и Газа

Формализованный подход

Для решения сформулированной выше задачи создания АСУ на базе формализованного подхода надо выполнить по крайней мере следующие работы: провести исходную формализацию ( постановку) задачи синтеза алгоритма управления, разработать соответствующие алгоритмы контроля и управления с проверкой их на ЭВМ, подобрать рациональную структуру технических и программных средств, реализующих принятые алго-ритмьг; смонтировать эти средства и провести всестороннее опробование разработанной АСУ на реальном объекте. [18]

САПР устройств СВЧ необходимо преодолеть много трудностей объективного характера: отсутствие обоснованного формализованного подхода к проектированию структурных схем устройств СВЧ; малая точность и большая сложность математических моделей элементов устройств СВЧ и связанная с этим проблема создания банков и баз данных. [20]

В отличие от очного обучения, при использовании дистанционных технологий появляется необходимость более формализованного подхода к построению учебного плана и системы изучаемых курсов. Это связано и с более четкими требованиями к описаниям курсов, системе оценки их усвоения, асинхронностью учебного процесса и особенностями взаимодействия преподавателя и студентов. [21]

Это позволяет применить для описания и анализа указанных цепей аппарат теории графов и дать систематический и формализованный подход к исследованию механических цепей. [22]

Этот метод формирования следует использовать только в общей части, поскольку он предназначен в основном для формализованных подходов и, в частности, для компьютерного метода синтеза. [23]

Эффективность введения маскирующих агентов зависит, как правило, от равновесных констант комплексообразования этих лигандов с мешающими ионами, однако такой формализованный подход к выбору оптимального лиганда, основанный только на сравнении прочности комплексов, не всегда приводит к желаемым результатам. [25]

Альтернативой к такому формализованному подходу является экспертный метод, при котором разбивка объектов на классы производится геологами-петрологами, тектонистами, геохимиками, геофизиками и другими на основании профессиональных знаний, опыта, интуиции. [28]

Применительно к такому подразделению от предприятия могут быть выделены активы и результаты операций по основной и прочей деятельности в целях формирования финансовой отчетности. Децентрализация управления требует более формализованного подхода к организационной структуре предприятия, охватывающей все структурные единицы сверху донизу и определяющей место каждой структурной единицы ( подразделения, отделения, сегмента) с точки зрения делегирования ей определенных полномочий и ответственности. [29]

Возможные варианты конфигураций и схем электрических сетей зависят от многих факторов: географических условий территории, мест расположения источников энергии и предполагаемых потребителей и др. Поэтому число вариантов развития сети может быть очень большим. Для отбора ряда наиболее экономичных вариантов на основе формализованного подхода к построению конфигурации сети предлагаются специальные оптимизационные модели. [30]

Источник

Apr. 25th, 2011

— теоретико-игровая формализация
— игровая формализация

Формализация исследование логических особенностей, дедуктивных и выразительных возможностей

Формализация как способ

Формализация как подход

Формализация как метод

Формализация как отображение

Стандартизация

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

Стандартизация = формализация. Аналогия между стандартизацией и формализацией становится понятной, если следовать следующему определению формализации (опять же, одному из многих возможных):

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

Еще одна трансформация основана на том, что понятие формализации уже было введено.

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

Приняв это определение, мы подтверждаем, что стандартизация есть специальный вид формализации.

Цели и адекватность стандартизации. Стандартизация, трактуемая как формализация, наследует все основные особенности этой деятельности. В частности, должны быть весьма четко описаны объекты, к которым относится тот или иной процесс стандартизации. Для оценки качества стандартизации необходимо четко сформулировать ее цель и проверять, достигается ли эта цель в результате стандартизации. Если стандартизация позволяет достичь поставленной цели, то ее можно назвать адекватной этой цели. Адекватность и является главным критерием качества стандартизации.

Некоторые из возможных целей приведены, в обобщенном виде, в определении из Закона «О стандартизации». Если внимательнее посмотреть на эти цели, то легко увидеть, что для одного и того же вида могут понадобиться несколько стандартов: например, один для обеспечения информационной совместимости, а другой – для удовлетворения требованиям безопасности. Эта ситуация характерна для построения формальных описаний сложных систем вообще: никакая достаточно сложная система, особенно живая, не может быть формально описана одним способом, пригодным на все случаи жизни.

Пример. Стандарт HL7. Широко известный и распространенный стандарт обмена медицинскими документами до HL7. Объект стандартизации – электронный формат документа. Цель – обеспечить интероперабельность программных систем, работающих с медицинскими документами. Стандарт описывает, прежде всего, события, которые приводят к появлению медицинских документов и необходимости обмена ими между различными системами. Примеры таких событий – это поступление и выбытие пациентов из медицинского учреждения, подача заявки на исследование и т.п. В привязке к событиям определяются виды документов. Внутренняя структура документов регламентируется лишь в той степени, которая необходима для идентификации самого документа, его назначения, отправителя и получателя, пациента. В частности, весьма детально разработаны форматы демографических данных. Формат же медицинского содержания документов практически не регламентирован.

Об адекватности стандарта HL7 говорит тот факт, что он принят и используется подавляющим большинством производителей медицинских программных систем. Среди требований к медицинским программным системам фигурируют, как правило, возможность экспорта/импорта данных в формате стандарта HL7. И, несмотря на то, что в официально признанных версиях HL7 используется устаревший, с точки зрения современных программных технологий, способ представления данных, он остается адекватным поставленным целям.

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

+ Математизация и формализация в современной науке

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

Математическое кодирование явлений природы и общества позволяет понимать, управлять и предсказывать ход реальных процессов. В истории культуры это первым осознал выдающийся древнегреческий мыслитель и математик Пифагор. Он обнаружил, что высота музыкального тона инструмента связана числовой зависимостью с ее длиной. Более того, он считал, что простые числа и геометрические фигуры, заключающие в себе соразмерность, или гармонии, являются началами мира. Эти идеи через Платона, Коперника и Дж.Бруно подхватил и развил один из основателей классической механики Г.Галилей. Галилей подчеркивал, что ученый, который пожелает решить проблемы естествознания, без математики столкнется с непреодолимой задачей. Тем не менее, нельзя абсолютизировать роль математики в естествознании. Математические формулы сами по себе абстрактны и лишены конкретного содержания. Только согласованные с научным наблюдением и экспериментом научные исследования наполняют математические формулы конкретным содержанием.

В эпоху бурного развития естествознания в конце XIX – начале XX века математика стала служить средством получения простых (изящных, красивых) законов о сложных явлениях природы. В ХХ веке, когда естествоиспытатели столкнулись со сложными закономерностями микромира, математика стала для них средством проведения эксперимента. Если физический объект правильно выражен формулой и если правила математических преобразований согласованы с изучаемыми физическими процессами, то физические преобразования объектов могут быть заменены математическими преобразованиями исходных формул. В этом случае результаты математических преобразований будут как бы автоматически соответствовать физическим экспериментам, то есть математика выполняет в научном познании эвристическую, познавательную функцию.

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

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

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

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

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

Для построения любой формальной системы необходимо:

а) задание алфавита, т.е. определенного набора знаков;

б) задание правил, по которым из исходных знаков этого алфавита могут быть получены «слова», «формулы»;

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

Возможность представить те или иные теоретические положения науки в виде формализованной знаковой системы имеет большое значение для познания. Но при этом следует иметь в виду, что формализация той или иной теории возможна только при учете ее содержательной стороны. Только в этом случае могут быть правильно применены те или иные формализмы. Голое математическое уравнение еще не представляет научной теории. Чтобы получить научную теорию, необходимо придать математическим символам конкретное эмпирическое содержание.

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

Расширяющееся использование формализации как метода теоретического познания связано не только с развитием математики. В химии, например, соответствующая химическая символика вместе с правилами оперирования ею явилась одним из вариантов формализованного искусственного языка. Все более важное место метод формализации занимал в логике по мере ее развития. Труды Лейбница положили начало созданию метода логических исчислений. Последний привел к формированию в середине XIX века математической логики, которая во второй половине ХХ столетия сыграла важную роль в развитии кибернетики, в появлении электронных вычислительных машин, в решении задач автоматизации производства и т.д.

Язык современной науки существенно отличается от естественного человеческого языка. Он содержит много специальных терминов, выражений, в нем широко используются средства формализации, среди которых центральное место принадлежит математической формализации. Исходя из потребностей науки, создаются различные искусственные языки, предназначенные для решения тех или иных задач. Все множество созданных и создаваемых искусственных формализованных языков входит в язык науки, образуя мощное средство научного познания.
Создание какого-то единого формализованного языка науки не представляется возможным. Дело в том, что даже достаточно богатые формализованные языки не удовлетворяют требованию полноты, т.е. некоторое множество правильно сформулированных предложений такого языка (в том числе и истинных) не может быть выведено чисто формальным путем внутри этого языка. Данное положение вытекает из результатов, полученных в начале 30-х годов XX столетия австрийским логиком и математиком Куртом Гёделем. Знаменитая теорема Гёделя утверждает, что ни одна содержательная теория не может быть полностью формализована, в ней всегда останется неформализуемый остаток, т.е. возможности любого формализованного языка остаются принципиально ограниченными. Таким образом, Гёдель дал строго логическое обоснование невыполнимости идеи Р.Карнапа о создании единого, универсального, формализованного «физикалистского» языка науки.

Формализованные языки не могут быть единственной формой языка современной науки. В научном познании необходимо использовать и неформализованные системы. Но тенденция к возрастающей формализации языков всех и особенно естественных наук является объективной и прогрессивной.

Источник

Почему люди не используют формальные методы?

На Software Engineering Stack Exchange я увидел такой вопрос: «Что мешает широкому внедрению формальных методов?» Вопрос был закрыт как предвзятый, а большинство ответов представляли собой комментарии типа «Слишком дорого. » или «Сайт — это не самолёт. » В каком-то смысле это верно, но мало что объясняет. Я написал эту статью, чтобы дать более широкую историческую картину формальных методов (FM), почему они на самом деле не используются и что мы делаем для исправления ситуации.

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

Также следует уточнить тип программного обеспечения, которое мы формализуем. Большинство людей неявно выделяют высоконадёжные программы, такие как медицинские устройства и самолёты. Люди предполагают, что для них формальные методы широко используются, а для остального не нужны. Это слишком оптимистичный взгляд: в большинстве высоконадёжного ПО не используются формальные методы. Вместо этого мы сосредоточимся на «обычном» софте.

Наконец, дисклеймер: я не профессиональный историк, и хотя пытался тщательно проверить информацию, в статье могут быть ошибки. Кроме того, я специализируюсь на формальной спецификации (DS и DV), поэтому больше вероятность ошибки там, где я говорю о верификации кода. Если увидите, пишите мне, я исправлю (и ещё: я зарабатываю на проведении семинаров по TLA+ и Alloy, поэтому очень предвзято отношусь к этим языкам; я пытаюсь быть максимально объективным, но сами понимаете: предвзятость — это предвзятость).

Формальное программирование

Получение спецификации

Спецификации кода делятся на три основных вида:

Если присмотреться, то эти три формы спецификации кода сопоставляются с тремя основными областями автоматической проверки корректности: тестами, контрактами и типами. Это не совпадение. Корректность — это широкий диапазон, а формальная верификация — одна из его крайностей. По мере уменьшения строгости (и усилий) верификации мы получаем более простые и узкие проверки, будь то ограничение исследуемого пространства состояний, использование более слабых типов или принудительную проверку во время выполнения. Тогда любое средство полной спецификации превращается в средство частичной спецификации, и наоборот: многие считают Cleanroom техникой формальной верификации, где код-ревью выходит далеко за рамки человеческих возможностей.

Какие спецификации правильные?

Верификация проверяет, что код соответствует спецификации. Возникает вопрос: откуда мы знаем, что у нас правильная спецификация? Поиск правильной спецификации — одна из самых больших проблем в формальных методах. Это также одно из главных возражений против них. Но скептики подразумевают здесь не совсем то, что имеют в виду специалисты по формальным методам.

Когда посторонние спрашивают «Как ты получишь верные спецификации?», то обычно думают о валидации, то есть спецификациях, которые не соответствуют требованиям клиента. Если вы формально докажете, что ваш код сортирует список, а клиент на самом деле хочет Uber для супов ™, вы просто потратили кучу времени. Мол, только быстрые итерации и короткие циклы обратной связи способны подтвердить ваши требования.

Это правда, что верификация кода не валидирует его. Но с этим аргументом есть две проблемы. Первая заключается в том, что этап применения формальных методов просто переносится, но не исчезает полностью. После всех этих быстрых итераций, вероятно, вы уже имеете представление, чего хочет клиент. И тогда начинаете верификацию кода. Во-вторых, хотя мы не знаем, чего именно хочет клиент, но можем предположить, чего он точно не хочет. Например, чтобы программное обеспечение случайно падало. Им не нужны дыры в безопасности. С этим все согласны: в конце концов, никто не говорит, что нужно пропустить модульные тесты во время итераций. Так что хотя бы убедитесь, что ваша система контроля версий не удаляет случайные данные пользователя (примечание: не думайте, что я озлоблен или что-то в этом роде).

Проблема с поиском правильной спецификации более фундаментальна: мы часто не знаем, что туда записать. Мы думаем о наших требованиях в человеческих, а не математических терминах. Если я говорю: «Программа должна отличать деревья от птиц», то о чём идёт речь? Я могу объяснить человеку, показав кучу фотографий деревьев и птиц, но это лишь конкретные примеры, а не описание идеи. На самом деле, чтобы перевести это в формальную спецификацию, нужно формализовать человеческие концепции, а это серьезная проблема.

Не поймите меня неправильно. Здесь можно определить соответствующие спецификации, и эксперты делают это всё время. Но написание соответствующих спецификаций — навык, который нужно развивать, также как навыки программирования. Вот почему многие из последних успехов верификации кода объясняются чётким отображением того, что мы хотим, в то, что мы можем выразить. Например, CompCert — формально верифицированный компилятор C. Спецификация для него: «Не допускать ошибок компиляции».

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

Доказательство спецификации

Первое в истории средство верификации кода — это метод в стиле Дейкстры «подумайте о том, почему это правда», который в основном предназначен для ALGOL. Например, я могу следующим образом «доказать» правильность сортировки методом вставки:

В то же время мы изучали способы автоматического доказательства математических теорем. Первая программа для доказательства теорем вышла в 1967 году. В начале 1970-х такие программы начали использовать для проверки кода на Pascal, а в середине десятилетия появились специальные формальные языки. Программист формулирует некие свойства кода, а затем создаёт проверяемое доказательство, что у кода есть эти свойства. Первые программы для доказательства теорем просто помогали людям проверять доказательства, а более сложные инструменты могли самостоятельно доказать части теоремы.

Что приводит к следующей проблеме.

Доказательства трудно получить

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

Далее, нужно получить само доказательство. Можете поручить это программе или написать самостоятельно. Обычно автоматическое определение доказательства неразрешимо. Для чрезвычайно узких случаев, таких как логика высказываний или проверка типов HM, оно «всего лишь» NP-полное. По сути мы сами пишем бóльшую часть доказательства, а компьютер проверяет его правильность. Это означает, что вам нужно хорошо знать:

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

У формальных верификаторов возникает дилемма: чем выразительнее язык, тем труднее на нём что-то доказать. Но чем менее выразителен язык, тем сложнее на нём писать. Первые рабочие формальные языки являлись очень ограниченными подмножествами более выразительных языков: ACL2 был подмножеством Lisp, Euclid был подмножеством Pascal и т. д. И ничто из того, что мы обсуждали до сих пор, на самом деле не доказывает реальные программы, это лишь попытки подступиться к написанию доказательств.

Доказательства трудны. Но становятся проще. Исследователи в данной области добавляют новые эвристики, библиотеки теорем, предварительно проверенные компоненты и т. д. Помогает и технический прогресс: чем быстрее компьютеры — тем быстрее поиск.

Революция SMT

Одной из инноваций в середине 2000-х годов стало включение SMT-решателей в состав программ для доказательства теорем. В широком смысле, SMT-решатель может превратить (некоторые) математические теоремы в проблемы соблюдения ограничений. Это превращает творческую задачу в вычислительную. Возможно, вам всё ещё понадобится снабжать его промежуточными проблемами (леммами) как шаги в теореме, но это лучше, чем доказывать всё самостоятельно. Первые SMT-решатели появились примерно в 2004 году, сначала как академические проекты. Пару лет спустя Microsoft Research выпустила Z3, готовый SMT-решатель. Большим преимуществом Z3 было то, что он стал намного удобнее в использовании, чем другие SMT, которые, честно говоря, практически ничего не говорили. Microsoft Research использовала его внутри компании, чтобы помочь доказать свойства ядра Windows, поэтому они не ограничились минимальным UX.

Зачем это нужно?

Самое время отступить назад и спросить: «В чём смысл?» Мы пытаемся доказать, что какая-то программа соответствует какой-то спецификации. Корректность — это диапазон. Есть две части верификации: насколько объективно «правильна» ваша программа и насколько тщательно вы проверили правильность. Очевидно, что чем больше проверено, тем лучше, но проверка стоит времени и денег. Если у нас есть несколько ограничений (производительность, время выхода на рынок, стоимость и т. д.), полная проверка корректности не обязательно является оптимальным вариантом. Тогда возникает вопрос, какая минимальная проверка нам нужна и чего это стоит. В большинстве случаев вам достаточно, например, 90% или 95% или 99% корректности. Может, стоит потратить время на улучшение интерфейса, а не на проверку оставшегося 1%?

Тогда вопрос: «Действительно ли проверка 90/95/99% значительно дешевле, чем 100%?» Ответ «да». Вполне комфортно говорить, что кодовая база, которую мы хорошо протестировали и хорошо типизировали, в основном корректна кроме нескольких исправлений в продакшне, и мы даже пишем больше четырёх строчек кода в день. Фактически, подавляющее большинство сбоев в работе распределённых систем можно было бы предотвратить чуть более полным тестированием. И это просто расширение тестов, не говоря уже о фаззинге, тестировании на основе свойств или тестировании модели. Вы можете получить действительно выдающийся результат с этими простыми трюками без необходимости добиваться полного доказательства.

Что, если типизация и тесты не обеспечивают достаточной верификации? Всё равно гораздо легче перейти от 90% до 99%, чем от 99% до 100%. Как упоминалось ранее, Cleanroom — это практика разработчиков, включающая всестороннюю документацию, тщательный анализ потока и обширный код-ревью. Ни доказательств, ни формальной проверки, ни даже модульного тестирования. Но правильно организованный Cleanroom уменьшает плотность дефектов до менее чем 1 бага на 1000 строк кода в продакшне (примечание: цифры из исследования Стэвли в работе Toward Zero-Defect Programming> но лучше всегда относитесь скептически и проверяйте первоисточники). Программирование Cleanroom не замедляет темп разработки, и уж точно идёт быстрее, чем 4 строчки в день. И сам по себе Cleanroom — лишь один из многих методов разработки высоконадёжного ПО, которые находится посредине между обычной разработкой и верификацией кода. Вам не нужна полная верификация, чтобы написать хороший софт или даже почти идеальный. Есть случаи, когда она необходима, но для большинства отраслей это пустая трата денег.

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

Частичная верификация кода

Для повседневных задач слишком дорого делать полную проверку. Как насчёт частичной? Ведь можно получить пользу от доказательства некоторых свойств отдельных фрагментов кода. Вместо доказательства, что моя функция всегда правильно сортирует числа, я могу хотя бы доказать, что она не петляет вечно и никогда не выходит за пределы диапазона. Это тоже очень полезная информация. Так, даже самые простые доказательства для программ на C — отличный способ устранить огромную часть неопределённого поведения.

Проблема в доступности. Большинство языков спроектированы или для полной верификации, или вообще её не поддерживают. В первом случае вам не хватает многих хороших функций из более выразительных языков, а во втором случае нужен способ доказать вещи на языке, который враждебен самой концепции. По этой причине большинство исследований по частичной верификации сосредоточено на нескольких высокоприоритетных языках, таких как C и Java. Многие работают с ограниченными подмножествами языков. Например, SPARK является ограниченным подмножеством Ada, поэтому вы можете писать критичный код на SPARK и взаимодействовать с менее критичным кодом Ada. Но большинство этих языков довольно нишевые.

Спецификация дизайна

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

Для пример, возьмём процедуру с грубой спецификацией «если она вызывается, то делает системный вызов для сохранения данных в хранилище и обрабатывает системные ошибки». Свойства проверить сложно, но вполне понятно, как это сделать. Правильно ли сериализуются данные? Нарушаются ли наши гарантии из-за некорректного ввода? Обрабатываем ли мы все возможные способы сбоя системного вызова? Теперь сравните систему логов высокого уровня со спецификацией «все сообщения записываются в лог» и ответьте на такие вопросы:

Так же, как мы используем языки программирования для представления кода, мы используем языки спецификаций для представления проектов. Языки спецификаций обычно ориентированы на спецификации дизайна, а не спецификации кода, хотя некоторые языки можно использовать для обоих случаев (примечание: процесс сопоставления спецификаций дизайна со спецификациями кода называется уточнением).В дальнейшем я буду называть языки спецификаций языками дизайна (DL), чтобы свести к минимуму путаницу (опять же, это не распространённая терминология; большинство людей используют «язык спецификаций», но я хочу четко разграничить спецификации кода и спецификации дизайна).

Вероятно, первым полным DL стал VDM примерно в 1972 году. С тех пор мы видели огромное разнообразие различных языков спецификаций. Пространство DL гораздо более разнообразно и фрагментировано, чем у языков верификации кода (CVL). Грубо говоря, люди изобрели DL как средство достижения цели, а CVL — как саму цель. Поскольку на них сильно влияют конкретные проблемные области, в DL реализованы всевозможные идеи и семантика. Вот очень, очень краткий обзор некоторых первых DL:

Поскольку DL обычно создаются для решения конкретных проблем, большинство из них имеют по крайней мере два или три реальных применения. Как правило, результаты очень положительные. Практикующие специалисты говорят, что DL даёт понимание проблем и облегчает поиск решений. Долгое время главным чемпионом был Praxis (теперь Altran), который применял «исправления-по-конструкции» — комбинацию Z-конструкций и кода SPARK — для создания критических систем безопасности. Спецификации экономят время и деньги, потому что вы не обнаружите ошибки дизайна на поздней стадии проекта.

Памела Зейв экспериментировала с Alloy и обнаружила фундаментальный баг в Chord, одной из основных распределённых хэш-таблиц. AWS начала находить 35-шаговые критические ошибки, написав спецификации TLA+. По моему опыту, когда люди пытаются писать спецификации, они очень скоро становятся большими поклонниками этого дела.

Но поклонники формальных методов и люди со стороны совершенно по-разному оценивают ценность написания спецификаций. Для поклонников самым большим преимуществом является то, что сам процесс написания дизайна заставляет вас понять, что вы пишете. Когда вам нужно формально выразить то, что делает ваша система, то множество неявных ошибок внезапно становятся болезненно очевидными. Это совершенно не могут понять посторонние. Если хотите дать кому-то попробовать DL, у человека должен быть способ проверить, что дизайн действительно обладает свойствами, которые он хочет.

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

Проверка моделей

Как и в случае с кодом, мы можем проверить дизайн, написав теоремы. К счастью, у нас есть ещё один трюк: можно использовать программу проверки моделей (model checker). Вместо составления доказательства, что дизайн правильный, мы просто брутфорсим пространство возможных состояний и смотрим, существует ли в нём неправильное состояние. Если ничего не найдём, то всё в порядке (примечание: программы проверки модели также используются для верификации кода, как JMBC, но в верификации дизайна намного чаще используется проверка модели, чем верификация кода).

У проверки моделей масса преимуществ. Во-первых, не нужно писать доказательства, что экономит много времени и усилий. Во-вторых, не нужно учиться писать доказательства, поэтому барьер входа намного ниже. В-третьих, если дизайн сломан, проверка модели даст явный контрпример. Это гораздо, гораздо упрощает исправление ошибки, особенно если для её воспроизведения нужно 35 шагов. Попробуйте найти это самостоятельно.

Есть и пара недостатков. Во-первых, эти инструменты не такие мощные. В частности, вы можете столкнуться с беспредельной (unbounded) моделью, у которой бесконечное количество разных состояний. Например, вы определяете обработчик очереди сообщений: он нормально работает со списком из десяти сообщений. Но если нужно поверить его на любом списке… ну, их бесконечное количество, поэтому в модели бесконечное количество состояний. У большинства инструментов для проверки моделей есть различные приёмы для подобных ситуаций, такие как определение классов эквивалентности или симметрии, но каждый случай отличается.

Но в то же время есть ещё один способ справиться со взрывом пространства состояний: бросить на него больше оборудования. Самая большая проблема для проверки модели — «всего лишь» проблема производительности, а мы очень хорошо решаем проблемы производительности. Большинство (но не все) проверок моделей легко распараллеливаются. После оптимизации модели и проверки её с небольшими параметрами можно развернуть кластер AWS и запустить его с большими параметрами.

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

Проблема со спецификациями дизайна

Таким образом, верификация дизайна проще и быстрее, чем верификация кода, и продемонстрировала много впечатляющих успехов. Так почему люди ей не пользуются? Проблема с DV гораздо коварнее. Верификация кода — это техническая проблема, а верификация дизайна — проблема социальная: люди просто не видят смысла.

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

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

Похоже, программисты просто не верят, что от спецификаций есть какая-то польза. По моему опыту, они предполагают, что текущих инструментов (псевдокод, диаграммы, TDD) более чем достаточно для правильного проектирования. Я не знаю, насколько распространённым является это мнение и не могу его объяснить ничем, кроме общего консерватизма.

Но точно такие жалобы есть у каждого сообщества методологии, которое я знаю: сторонники TDD жалуются, что программисты не хотят пробовать TDD, Фанаты Haskell жалуются, что программисты не думают о статической типизации и так далее.

Я слышал аргумент, что Agile не приемлет заранее продуманный дизайн, поэтому никто не хочет делать формальную спецификацию. Может быть. Но многие из тех, кого я встречал, отвергают и Agile, и FM. Ещё один аргумент заключается в том, что исторически формальные методы постоянно переоценивались и не выполняли обещанное. Это тоже возможно, но большинство людей даже не слышали о формальных методах, а уж тем более об их истории.

Просто очень трудно заставить людей волноваться о том, чего они ещё не делают, даже если признают преимущества.

Резюме

Верификация кода — трудная задача. В это вовлекается всё больше людей, хотя программы для доказательства теорем и SMT-решатели становятся всё более сложными. Но всё-таки в обозримом будущем, наверное, это останется уделом специалистов.

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

Надеюсь, эта статья чуть лучше объясняет, почему формальные методы так редко используются. По крайней мере, это лучшее объяснение, чем обычный аргумент «веб — это же не самолёт». Не стесняйтесь кричать, если увидите какие-то очевидные ошибки.

Источник