Если вы изучили формальные методы для программного обеспечения, насколько вы нашли это полезным?

17

Если вы были обучены использованию формальных методов (FM) для программирования:

  • Насколько полезный ты нашел это?
  • Что включает в себя ваше FM-обучение (например, курс, книга)?
  • Какие инструменты FM вы используете?
  • Какие преимущества в скорости / качестве это дает вам по сравнению с не использовать FM?
  • Какое программное обеспечение вы создаете с FM?
  • А если вы прямо сейчас не используете FM, стоило ли это хотя бы учиться?

Мне любопытно услышать столько опыта / мнений о FM, сколько можно найти в этом сообществе; Я начинаю читать об этом и хочу знать больше.

Фон

Программирование и разработка / проектирование программного обеспечения являются одними из новейших человеческих навыков / профессий на Земле, поэтому неудивительно, что эта область является незрелой, что отражается в основном выводе нашей области в виде кода, который обычно запаздывает и подвержен ошибкам. Отраслевая незрелость также демонстрируется широкой разницей (по крайней мере, 10: 1) в производительности между средним и лучшим программистами. Такие мрачные факты хорошо освещены в литературе и представлены такими книгами, как «Полный код» Стива Макконнелла .

Использование формальных методов (FM) было предложено крупными фигурами в области программного обеспечения / CS (например, покойный Э. Дейкстра ) для устранения (одной из) основных причин ошибок: отсутствия математической строгости в программировании. Дейкстра, например, выступал за то, чтобы студенты вместе разрабатывали программу и ее доказательство .

FM, кажется, намного более распространен в учебных программах CS в Европе по сравнению с США. Но в последние несколько лет новые «легкие» FM-подходы и инструменты, такие как Alloy , привлекли некоторое внимание. Тем не менее, FM далеко не общепринятый в промышленности, и я надеюсь, что некоторые отзывы здесь о том, почему.

Обновить

На данный момент (14.10.2010) из 6 ответов, приведенных ниже, никто четко не высказался за использование FM в работе «реального мира». Мне действительно любопытно, если кто-то может и будет; или, возможно, FM действительно иллюстрирует разрыв между научными кругами (FM - это будущее!) и промышленностью (FM в основном бесполезен).

limist
источник
Что касается вашего обновления, возможно, никто не спорил об использовании FM в работе «в реальном мире», потому что их очень мало в реальной работе
Richard

Ответы:

8

Абсолютно бесполезен для всего нетривиального.

У меня был курс под названием «Формальные методы», который был сфокусирован на Alloy - я не вижу возможности использовать его где-либо. Был еще один класс, который фокусировался на параллельном моделировании с помощью LTSA - в равной степени бесполезен.

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

Fishtoaster
источник
Спасибо, что поделился; Вы сказали бы, что обучение в FM было, по крайней мере, полезным для вашей дальнейшей работы, например, помогло ли вы мыслить более четко? Или не?
Limist 7.10.10
@limist: я действительно так не думаю. Я имею в виду, что мне немного понравился Alloy, но я не думаю, что это было полезно, даже просто чтобы расширить то, как я думаю.
Fishtoaster
2
Это именно тот ответ, который я бы дал. Самый бесполезный урок, который я посещал в университете, а не то, на что я когда-либо оглядывался назад и был рад, что выучил его. Я думаю, корень проблемы в том, что формальная спецификация должна быть более сложной, чем код, чтобы правильно ее смоделировать, поэтому для любого удаленно сложного кода это чрезвычайно сложная задача - создать ее формальную модель, до такой степени, что я могу не представляю, чтобы кто-то вне аппаратного дизайна или такой же бесповоротной работы хотел или мог это сделать.
Гленатрон
1
Это разочаровывает. Я думал, что это может быть полезно для проверки того, что у вас была достаточно полная модель; в то время как фактические ошибки чаще всего были бы ниже модели (испортить мьютексы или что-то еще), я предположил, что было бы полезно использовать Alloy, чтобы найти недостатки в самой модели. (Интуитивно менее вероятно, что будет полезно попытаться использовать помощника по проверке; я ожидаю, что контрпримеры будут более полезными, и это больше относится к таким вещам, как Alloy (хотя в идеале я думаю, что было бы хорошо иметь возможность приблизиться к обоим в одной системе).)
Брюс Стивенс
7

У меня есть опыт работы в CSP (передача последовательных процессов). Не говоря уже о моем собственном гудке, но я написал магистерскую диссертацию по Timed CSP, в частности, «компилируя» спецификации, написанные формальными методами, в исполняемый C ++. Я могу сказать, что у меня есть некоторый опыт работы с формальными методами. После того, как я получил степень и получил работу в отрасли, я вообще не использовал формальные методы. Формальные методы все еще слишком теоретичны, чтобы их можно было применять в промышленности. Формальные методы нашли некоторое практическое применение в области встроенных систем. Например, НАСА использует формальные методы в своих проектах. Я бы предположил, что формальные методы очень далеки от широкого применения в отрасли. Просто не имеет смысла писать спецификации программного обеспечения в формальных методах, а затем «интерпретировать» их людьми в соответствии с вашими предпочтениями. Обычный английский и диаграммы работают для этого лучше, в то время как модульные и интеграционные тесты неплохо справляются с «проверкой» правильности кода. я думаюформальные методы останутся в научном мире еще некоторое время .

ysolik
источник
Спасибо, что поделились, я попрошу повторение повторения часто по этому вопросу. В: Вы сказали бы, что обучение в FM было, по крайней мере, полезным для вашей дальнейшей работы, например, помогло ли вы мыслить более четко? Или не?
Limist 7.10.10
Поздравляю ваших мастеров!
Крис
@limist: Я бы сказал, что это был очень хороший теоретический опыт, но я нашел очень мало практического применения в отрасли.
ysolik
4

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

mouviciel
источник
4

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

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

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

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

Дэвид Торнли
источник
4

Я прошел аспирантуру по формальному анализу программ, где мы сосредоточились на операционной семантике. Я сделал свой последний документ об усилиях seL4, рассматривая формальные методы, которые они использовали. Мой основной вывод с точки зрения практичности заключался в том, что он имеет предельную ценность. Вы должны не только написать программу, вы должны написать доказательство. Вау. Два источника ошибок. Не только один. Кроме того, на сам код накладывалось огромное количество ограничений. Очень сложно описать физический компьютер, включая ввод / вывод.

Пол Натан
источник
Однажды я увидел, как описывается ввод / вывод в стиле ленты. У автора не было решений для формального описания файлов произвольного доступа, и он довольствовался ругательствами по ним.
Дэвид Торнли
1
@ Дэвид: эти файлы с произвольным доступом. Плохие новости. Вы не хотите их использовать. =)
Пол Натан
3

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

Языки спецификаций более выразительны, чем языки программирования. Например, вот (очень) простая спецификация PlusCal для распределенного хранилища данных:

process node \in 1..5 \* Nodes
variables online = TRUE,
          stored \in SUBSET data; \* Some set
begin 
  Transfer:
    either
      with node \in Nodes, datum \in stored do
        node.stored := node.stored \union {datum};
      end
    or \* crash
      online := FALSE;
    end either;
end process;

Этот фрагмент указывает пять одновременно работающих узлов, выполняющих передачи в произвольном порядке, где каждая передача представляет собой произвольный фрагмент данных в произвольный узел. Кроме того, мы указали, что любая передача может завершиться сбоем и вызвать сбой узла. И мы можем смоделировать все эти поведения в программе проверки модели TLA +! Таким образом, мы можем проверить, что независимо от порядка, частоты отказов и т. Д. Наши требования остаются в силе. Говоря об этом, давайте добавим пару требований. Во-первых, мы никогда не передаем данные на автономный узел:

[][\A node \in Nodes: ~online => UNCHANGED node.stored]_vars

В нашей упрощенной версии средство проверки модели обнаружит состояние сбоя. Мы также можем указать «любой данный фрагмент данных находится хотя бы в одном онлайн-узле»:

\A d \in data: \E n \in Nodes: n.online /\ d \in n.stored

Что тоже не удастся. Удачи, проверяя это с помощью модульного теста!

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

Hovercouch
источник
1

Я работал в отделе в ICL, прежде чем они были скуплены Fujitsu. У них было несколько крупных правительственных контрактов, которые требовали доказательства того, что программное обеспечение работало так, как рекламируется, поэтому они создали машину, которая будет принимать формальную спецификацию, написанную на Z, и проверять код во время работы с большим зеленым или красным светом для прохода / провал.

Это было удивительно, но, как отмечает уважаемый @FishToaster , это было бесполезно для чего-то нетривиального.

JBRWilkinson
источник
0
  1. " Насколько полезный ты нашел это? "

Применение сетей Петри к компьютерному программированию очень полезно. Я создал «Сетевые элементы и аннотации», метод, основанный на сетях Петри (Chionglo, 2014). С 2014 года я применяю этот метод для написания программ на JavaScript, использующих Acrobat / JavaScript API для приложений форм PDF.

  1. « Что включало ваше FM-обучение (например, курс, книга)? »

Я «тренировался» на сетях Петри через самообучение. Я прочитал главы о сетях Петри из учебника «Сети Петри и Графсет: инструменты для моделирования систем дискретных событий» (David and Alla, 1992). Я также читал исследовательские работы по сетям Петри. После создания и документирования «Сетевых элементов и аннотаций» я практиковался в применении этого метода в течение нескольких недель.

  1. « Какие инструменты FM вы используете? »

Я рисую диаграммы Петри, используя PowerPoint. Я создаю вид аннотаций в форме, используя Word. Я создаю токены как приложения в форме PDF, используя Acrobat и Notepad. После добавления записей в форму перевод этих записей в код JavaScript является систематическим. Таким образом, должна быть возможность автоматизировать перевод. Если «записи» были добавлены к графическим объектам в PowerPoint, то также должна быть возможность систематически переводить их в код JavaScript и автоматизировать этот перевод. Я также использую набор инструментов для незавершенного производства, которые выполняют эти переводы и для создания дополнительных ресурсов для создания приложений в форме PDF (Chionglo, 2018; 2017).

  1. « Какие преимущества в скорости / качестве он дал вам по сравнению с тем, что вы не используете FM? »

Я могу писать программы на JavaScript с использованием «Сетевых элементов и аннотаций» быстрее, чем написание программ на JavaScript без использования «Сетевых элементов и аннотаций». А для больших программ я могу прекратить кодирование и вернуться к кодированию позже (или намного позже), не задаваясь вопросом, где продолжить (Chionglo, 2019). В некоторых случаях я могу писать программы на JavaScript с использованием «Сетевых элементов и аннотаций», но не могу писать программы на JavaScript без использования «Сетевых элементов и аннотаций». Например, я не смог бы создать нерекурсивные реализации рекурсивных функций без использования «Сетевых элементов и аннотаций» (Chionglo, 2019b; 2018b; 2016). Они верны с или без инструментов незавершенного производства.

  1. " Какое программное обеспечение вы создаете с помощью FM? "

Я использую «Сетевые элементы и аннотации» для создания программ JavaScript, которые используют Acrobat / JavaScript API для приложений форм PDF. Я также могу применить этот метод для создания программ JavaScript для документов HTML и создания эскизов Arduino (Chionglo, 2019c; 2019d).

  1. « А если вы прямо сейчас не используете FM, стоило ли это хотя бы учиться? » Не применимо.

Ссылки

Чионгло, JF (2019b). Вычисление N-го члена рекурсивного отношения: использование нерекурсивной функции - ответ на вопрос в математике Stack Exchange. < https://www.academia.edu/38496025/Computing_the_N-th_Term_of_a_Recursive_Relation_Using_a_Non-Recursive_Function_A_Reply_to_a_Question_at_Matочек_Stack_Exchange >.

Чионгло, JF (2019c). Логика, симуляция и эскиз управления эффектом пламени: ответ на запрос на форуме сообщества Arduino. https://www.academia.edu/40342956/Flame_Effect_Control_Logic_Simulation_and_Sketch_A_Reply_to_a_Request_at_the_Arduino_Community_Forum .

Чионгло, JF (2019). Как продолжить кодирование приложения после длительного перерыва? Ответьте «Как вы узнали, где вы остановились в своих кодах после двухнедельного перерыва?» - Software Engineering Stack Exchange. https://www.academia.edu/39705042/How_I_Continue_Coding_an_Application_after_a_Long_Break_Reply_to_How_do_you_know_where_you_stopped_in_your_codes_after_a_2-week_break_Software_Engineering_Stack_Exchange .

Чионгло, JF (2019d). Логика управления Show-and-Hide: вдохновлена ​​вопросом при переполнении стека. < https://www.academia.edu/40283015/Show-and-Hide_Control_Logic_Inspired_by_a_Question_at_Stack_Overflow >.

Чионгло, JF (2018b). Модель сети Петри для факториала числа: и нерекурсивная функция JavaScript для ее вычисления. <>.

Чионгло, JF (2018). Создайте Hyper Form ™ - рабочий процесс в процессе: обновление в Net Programming Research. https://www.academia.edu/37697498/Create_Hyper_Form_-A_Workflow_in_Progress_Update_on_the_Net_Programming_Research .

Чионгло, JF (2017). Чистое программирование: исследовательское предложение: для разработки приложений в форме PDF с помощью PowerPoint и Acrobat. https://www.academia.edu/33374809/Net_Programming_A_Research_Proposal_For_Developing_PDF_Form_Applications_with_PowerPoint_and_Acrobat. ,

Чионгло, JF (2016). Модель сети Петри для вычисления числа Фибоначчи. https://www.academia.edu/31748108/A_Petri_Net_Model_for_Computing_the_Fibonacci_Number.

Чионгло, JF (2014). Сетевые элементы и аннотации для компьютерного программирования: вычисления и взаимодействия в PDF. https://www.academia.edu/26906314/Net_Elements_and_Annotations_for_Computer_Programming_Computations_and_Interactions_in_PDF .

Дэвид Р. и Х. Алла. (1992). Сети Петри и Grafcet: инструменты для моделирования дискретных событий. Верхнее Седло, Нью-Джерси: Прентис Холл.

Джон Фредерик Чионгло
источник