Заметки о структурном программировании, структурных и минимальных тестах
В статье рассматриваются способы формального построения тестов и задача минимизации их количества. Приводится пример применения классического метода построения минимального набора тестов и более простой способ — метод нейтрального значения. Статья может быть интересна широкому кругу читателей из области информационных технологий, специалистам по тестированию.
Оглавление
Предпосылки
К написанию этой заметки побудили результаты проверки студенческих решений следующей задачи:
реализуйте поиск медианы из трех чисел, используя только операторы структурного программирования.
Это наблюдение может быть интересно скорее начинающим программистам, чем более опытным, так как вопросы сложности кода, при наличии должного опыта, могут быть решены на уровне интуиции.
Изначально задача для студентов была сформулирована мной некорректно, а именно говорилось, что можно использовать только “стандартные возможности языка программирования”, без расшифровки что это обозначает. Действительно, не ясно что является стандартной возможностью, а что — нет, однако интуитивно может быть ясно, что требовалось использовать только:
последовательность подпрограмм,
цикл и
ветвление.
Как следует из теоремы Бёма — Якопини (теорема о структурном программировании), с помощью этих управляющих структур возможно реализовать любую программу, которая представима в виде блок схемы (исполняемого алгоритма). И здесь, определенно, алгоритм поиска медианы не является исключением.
В структурном программировании выделяют семь принципов:
следует отказаться от использования оператора безусловного перехода goto;
любая программа строится из трёх базовых управляющих конструкций: последовательность, ветвление, цикл;
в программе базовые управляющие конструкции могут быть вложены друг в друга произвольным образом;
повторяющиеся фрагменты программы можно оформить в виде подпрограмм (процедур и функций);
каждую логически законченную группу инструкций следует оформить как блок;
все перечисленные конструкции должны иметь один вход и один выход;
разработка программы ведётся пошагово, методом “сверху вниз”.
Конечно, в решениях студентов я не нашел использование goto, все прислали свои решения на Python, в котором эта управляющая конструкция просто отсутствует, однако большинство решений нарушали шестой принцип, а именно — содержали проблему раннего выхода (early exit). Ну и что дальше? — может спросить читатель.
В текущее десятилетие развитие экосистемы вокруг Python-совместимых сред разработки привело к тому, что большая часть этапа прототипирования, в особенности в области анализа данных и машинного обучения, производится в так называемых тетрадках (notebooks) — написание и исполнение кода в которых существенно далеко от принципов структурного программирования. Все это в комплексе, особенно часто — у неопытных и неаккуратных разработчиков, приводит к затруднениям:
невозможности повторить предыдущий результат исполнения программы, так как непонятно в каком порядке исполнялись блоки программы ранее - в процессе разработки и отладки;
большому количеству ошибок, связанных со злоупотреблением глобальными переменными, которые могут определяться и переопределяться в любом блоке “тетрадки”;
необходимости отладки блоков программы средствами функции print;
“я запутался” потому что не выделил блоки/функции/процедуры и не написал unit-тесты до или сразу после реализации.
Кажется, что notebooks парадигма привнесла больше плохого чем хорошего, с одной стороны — время прототипирования существенно уменьшается за счет:
снижения порога входа,
отсутствия необходимости настраивать окружение исполняемого кода,
самодокументируемости программного кода и др,
с другой стороны — программисту дается возможность разрабатывать и исполнять код, нарушая седьмой принцип структурного программирования — “сверху вниз”. И в коммерческой разработке это создает существенные сложности, особенно при совместной разработке и поддержке больших объемов довольного сложного и насыщенного зависимостями кода, который часто разрабатывается в тетрадках и без дополнительных изменений может переноситься в продакшн. Но, вернемся к нашей задаче.
Медиана трех чисел
На всякий случай определим что такое медиана — центр вариационного ряда, и в отличии от среднего обладает довольно любопытным свойством — медиана по определению принадлежит выборке, тогда как это совсем не обязательно для среднего значения. Таким образом, в этой задаче для трех чисел требовалось найти такое число 
, что
Здесь сразу напрашивается очевидное решение вида
Однако это решение абсолютно бесполезно и, не только, в целом, с дидактической но и с методологической — точек зрения в преподавании, но, безусловно, подобная реализация будет отвечать всем принципам структурного программирования и имеет при этом минимальную цикломатическую сложность.
Я был удивлен, интересным подходом в одном из решений, когда арифметика удачно совмещается с логикой, и ведь, действительно, число b — есть медиана тогда и только тогда, когда следующее неравенство верно
На основании этого теста можно и построить своеобразный алгоритм, в рамках которого достаточно протестировать всего два числа из трех, что и сделал один из студентов.
Рассмотри тривиальную реализацию нужной нам функции, используя только сравнения в конструкции if/else. Такому алгоритму присвоим условный код “10” и его реализация представлена ниже, а также - здесь.
Для расчета сложности, удобно представить данную программу в виде блок-схемы, интерпретируя которую как ориентированный граф и условно соединяя единственный выход со входом, под цикломатической сложностью можно понимать количество линейно независимых циклов или контурный ранг графа, здесь таких циклов шесть. Граф и перечисление всех циклов представлены на рисунке ниже.
С другой стороны, в такой постановке под цикломатической сложностью программы понимают цикломатическое число ей эквивалентного графа, в котором каждый выход связан ребром со входом, а именно
Для нашей реализации алгоритма “10” получаем что
Что совпадает с количеством линейно независимых циклов и количеством точек ветвлений (у нас 5 использований условного оператора) + 1. А это означает, что для тестирования корректности работы данной функции нам потребуется не менее 6 тестов, здесь очевидно, что каждый из таких тестов будет являться перестановкой чисел a,b,c. Очевидно, что таких перестановок 3! = 6.
Рассмотрим другую реализацию, идея которой основана на применении нескольких шагов алгоритма сортировки пузырьком, и может быть реализована при наличии заранее определенной функции swap. Дадим этому алгоритму условный код “20”.
И для нашей реализации получаем, что
И здесь было бы не верно думать, что количество тестов которые необходимы для тестирования корректности работы данной реализации уменьшилось до четырех, нам все попрежнему необходимо не менее шести тестов. Цикломатическая сложность показывает нам лишь нижнюю границу для количества тестов обеспечивающих только покрытие точек ветвления.
Еще одной из полезных метрик оценки качества реализации может быть банальная средняя длина метода (при наличии культурных ограничений на длину строки программы):
в реализации “10” у нас всего один метод и его длина 17 строк,
а в реализации “20” у нас два метода, с длинами 1 и 8 строк соответсвенно, и средняя длина равна 4.5 строки.
Безусловно расчет таких и подобных метрик вручную затруднителен и, для автоматизации этого процесса, принято использовать различные вспомогательные программы.
Утилита RADON
Утилита Radon позволяет вам проанализировать ваш python-код и автоматически вычислить большое количество метрик качества кода, такие как:
цикломатическая сложность,
метрики Хальстеда,
метрику поддерживаемости,
и др.
Установить утилиту Radon так же просто
как и пользоваться результатами ее работы. Я собрал все предложенные студентами реализации решения задачи поиска медианы трех чисел и воспользовался автоматическим расчетом метрик утилиты Radon. В первую очередь нас интересует цикломатическая сложность, вычислить которую для каждой функции из любой тетрадки (в данном случае тетрадка называется median_list.ipynb) можно выполнив следующую команду:
и, в результате, получить следующий вывод, в котором для каждой, используемой в тетрадке функции, оценивается цикломатическая сложность
здесь же, помимо сложности (указывается числом в скобках), каждая реализация (нас интересуют только функции начинающиеся с префикса median) ранжирована согласно следующей таблице
Тестирование
Вопросы количества тестов достаточных для надежного тестирования программного обеспечения безусловно связаны не только с количество ветвлений и вычисления контурного ранга графа. Часто мы имеем дело со сложными логическими функциями в точках ветвления, гораздо сложнее чем можно себе представить для рассматриваемой в статье задачи. И здесь будет интересен пример из книги [3] в котором для анализа необходимого количества тестов и непосредственного их конструирования приводится реальный пример метода добавляющего объект в структуру типа дерево. Далее продемонстрирована часть кода этого метода.
![Рисунок 8— Первые 10 строк кода из Figure 2–18 Code for structure-based exercise [3]](https://habrastorage.org/r/w1560/getpro/habr/upload_files/cb6/0d9/50c/cb60d950c649063e86f9bb407665a92b.png "Рисунок 8— Первые 10 строк кода из Figure 2–18 Code for structure-based exercise [3]")
Мы видим ранний выход из метода по сложному логическому условию, которое, скорее всего, здесь оправдано из соображений удобочитаемости кода. И, в целом, здесь же мы имеем ветвление по логическому условию определяемому пятью состояниями. Не сложно подсчитать что это требует от нас 2⁵=32 наивных тестов. Боюсь, что полное покрытие в этом случае будет избыточно и очень трудозатратно, или нет? Ответьте на этот вопрос сейчас и дальнейшее изложение вас может удивить.
Для удобства дальнейшего изложения обозначим эти пять состояний, определяемых функциями isReq(), isBeq(), isNort(), isFlat(), isFreq() атомами x, y, z, w, t, соответсвенно, которые принимают булево значение - 0 или 1. Безусловно, не имея информации о работе этих функций мы не можем понять о достижимости всех 2⁵ состояний, и это еще больше усложняет нашу задачу. Тогда наше ветвление будет осуществляться по значениям следующей булевой функции
Эту функцию можно визуализировать на уровне функциональной и контактной схемы, последняя нам пригодится для дальнейших рассуждений. Сразу стоит отметить, что построение контактных схем по булевой функции представляет отдельную задачу и она не всегда является тривиальной, но, — не здесь. Для удобства дальнейшего изложения, мы рассмотрим другую функцию, убрав глобальное отрицание, которое мне, как и вам, и, как и авторам в [3] доставит только лишнюю головную боль без особого влияния на результат
Контактной схемой называется неориентированный граф, каждому ребру (контакту) которого приписан символ переменной или ее отрицания и выделены две вершины, которые называются полюсами.
На этом этапе неподготовленный читатель рискует сильно зависнуть — возьмите большой лист в клеточку и повторяйте шаги по мере чтения.
Пример из общей теории построения тестов
Здесь представленная последовательность действий приводится по примеру из книги [2]. Для нашей функции f соответствующая контактная схема представлена на рисунке 10: каждому контакту сопоставлена своя переменная x, y, z, w, t, а структура контактов определяется двумя полюсами и наличием параллельной связи, обусловленной наличием логической операцией “или”: z или (w и t).
Пронумеровав контакты мы уже выполнили первую часть алгоритма в нашем поиске минимального теста. Этот этап будет иметь особый смысл, если в логическом выражении будут участвовать отрицания — они будут представлены отдельными контактами.
Далее мы рассмотрим все такие наборы x, y, z, w, t на которых функция f принимает истинные значения и представим их в виде следующей таблицы-заготовки.
В таблице наверху мы не можем не обратить внимание что появились дополнительные функции f с индексами 0,1,2,3,4,5. Будем считать, что функция с индексом ноль обозначает исправную реализацию контактной схемы, а реализации с номерами 1,2,3,4,5 — с неисправным контактом с соответствующим номером.
Следующий шаг нашего алгоритма состоит в том, что мы должны определить все значения функций 1,2,3,4,5 на указанном наборе значений x, y, z, w, t. Отключите немного мозг, и просто повторите то что написано здесь — потому что заполнять Таблицу 2 мы будем по строкам.
Заполнять таблицу в дидактических целях начнем снизу, так должно быть понятнее. Последний набор (x, y, z, w, t)=(1,1,1,1,1). Соответствующая реализация контактной схемы для него выглядит так же как и на Рисунке 9 — все контакты соединены, разрывы отсутсвуют. Теперь ответим на вопрос — разрыв каких контактов в этом случае разорвет путь от одного полюса до другого? Очевидно, что разывая ровно один из контактов 1 или 2 (см. Рисунок 9) путь между полюсами разорвется. Это означает в соответствующих клетках таблицы в колонках значений функций 1, 2 мы поставим цифру 0, а в остальных клетках для нашего набора — единицы.
Продолжим в этом же духе. Возьмем предпоследний набор аргументов (x, y, z, w, t)=(1,1,1,1,0). Нарисуем для него реализацию соответсвующей контактной схемы.
Ответим на тот же вопрос, что и на прошлом шаге — разрыв каких контактов в этом случае разорвет путь от одного полюса до другого? Теперь так же очевидно, что разрывая один из контактов 1,2 или 3 мы разорвем путь между полюсами. Аналогично в этих колонках поставим нули.
Постройте для наборов аргументов (x, y, z, w, t)=(1,1,1,0,1) и (x, y, z, w, t)=(1,1,1,0,0) соответсвующие контактные схемы и обратите внимание, что ваш вывод будет таким же: разрыв контактов 1,2,3 приведет к разрыву всего пути между полюсами. Что отобразится в таблице следующим образом.
Нам осталось заполнить значения для первого набора (x, y, z, w, t)=(1,1,0,1,1). Составим соответсвующую контактную схему.
Мы видим, что разрывая один из контактов 1,2,4 или 5 путь между полюсами так же разорвется. В этих колонках поставим ноль. В итоге наша таблица-заготовка полностью заполнена. Полученная таблица называется “таблицей неисправностей”.
Далее, если есть такие наборы (x, y, z, w, t) на которых мы имеем одинаковые значения функций 0,1,2,3,4,5 то оставим только один такой набор. Видим, что на на наборах аргументов (1,1,1,0,0), (1,1,1,0,1), (1,1,1,1,0) в таблице у нас одинаковые строки вида (1,0,0,0,1,1). Оставим в таблице только один такой набор, пусть это будет (1,1,1,0,0,1). Тогда таблица сократится на две строки, а оставшимся наборам присвоем номера.
В этой таблице мы видим, что некоторые столбцы совпадают (они выделены цветом), что означает, что неисправности типа размыкания одного контакта неотличимы в случае разомкнутости 1-ого или 2-ого контактов или в случае разомкнутости 4-ого или 5-ого контактов.
Это еще далеко не конец! Теперь мы должны объединить неотличимые неисправности в так называемые классы неисправностей. Для нашего случая мы имеем 4 класса неисправностей, обозначим их следующим образом
Составим новую таблицу, где будут участвовать только наши выделенные четыре класса неисправностей.
Мы уже заканчиваем. В результате выполнения этих хитрых манипуляций мы получили три набора аргументов (x, y, z, w, t) для нашего теста на неисправность вида разрыва одного контакта. Но можно ли сделать еще чуть меньше?
Выпишем всевозможные! сочетания классов g и заготовим для этого специальную таблицу.
Далее, для каждого сочетания мы указываем номера наборов аргументов на которых значения в классах отличаются. Например, для первого паросочетания в таблице 9 все значения отличаются на всех трех наборах, что эквивалентно символической дизъюнкции этих наборов: 1 или 2 или 3. А для второго паросочетания отличается значение только на втором наборе. Продолжая так рассуждать мы заполняем таблицу 10 окончательно.
Заканчивая наше исследование по поиску минимального теста мы должны составить символическую конъюктивно нормальную форму из наших дизъюнкций из Таблицы 10.
И здесь следует вспомнить законы поглощения, использовав которые все становится существенно проще, а именно мы получим вырожденную дизъюнктивно нормальную форму для этого выражения
можем взять любую символическую конъюнкцию из этой дизъюнктивной нормальной формы — а она у нас всего одна. Поэтому и минимальный тест в нашем случае будет состоять только из первого и второго набора аргументов. А именно для переменных (x, y, z, w, t) возьмем следующие наборы: 11011 и 11100. Контактные схемы для которых мы изобразим далее.
Закончить столь длинное рассуждение можно формулой нашего минимального теста, включающего первый и второй набор аргументов
Обратите внимание, последний этап нам снизил количество тестов с трех (наборы 11011, 11100, 11111) до двух, убрав из теста набор 11111.
Кажется, что результат получился абсолютно логичным, мы получили пару критических путей на которых, если наше логическое выражение выдает истину — то можно не беспокоится. И действительно, достаточно получить положительные тесты на наборах 11011 и 11100 чтобы утверждать что на наборе 11111 тест также будет пройден.
Но что если в схеме произошло не размыкание на которое мы тестировали, а, наборот — замыкание?
И здесь мы оставим этот классический подход и отошлем любопытного читателя к фундаментальной работе о логических способах контроля электрических схем, а так же общей теории построении тестов [1] — И. А. Чегис, С. В. Яблонский, “Логические способы контроля работы электрических схем”, Сборник статей по математической логике и ее приложениям к некоторым вопросам кибернетики, Тр. МИАН СССР, 51, Изд-во АН СССР, М., 1958, 270–360.
Обратите внимание, что никаких электрических схем ни в предпосылках к расчетам, ни в их процессе не появлялось. У читателя точно возникнет много вопросов при попытке повторить эти действия для какого-то другого логического условия: начиная от построения самой контактной схемы, нумерации контактов, составления таблиц и заканчивая символическими КНФ/ДНФ, которые были использованы без дополнительных пояснений. Для прояснения данных моментов лучше обратиться к списку использованных источников.
Далее я покажу существенно более простой метод построения подобных тестов как на размыкание так и на замыкание. Этот метод обозначим под кодовым названием “neutral-value design technique”.
Neutral-value design technique
Здесь мы рассмотрим пример из книги [3] в рамках которого предлагается рассмотреть тот же самый кусочек кода на Рисунке 8. Название этого метода можно перевести как “Метод нейтрального значения”.
Для фиксированного набора аргументов (x*,y*,z*,w*,t*) булевой функции f нейтральным элементом будем называть такой элемент этого фиксированного набора при изменении которого на противоположенное значение — значение функции изменяется на это противоположенное значение. Например, для нашей функции (выпишите ее на листочек — будет полезно обращаться к ней дальше)
рассмотрим набор аргументов 11001. Для этого набора нейтральным элементом является w, и действительно, — на наборе 11011 функция принимает значение истина. Следующая таблица демонстрирует это.
Конечно для одного фиксированного набора может быть несколько так называемых нейтральных элементов. Первый шаг работы по методу нейтрального значения заключается в составлении двух таблиц-заготовок, с каждой из которых ведется отдельная работа.
Каждая из таблиц заполняется построчно и заключается поиске такого набора (x*,y*,z*,w*,t*) для которого элемент на диагонали таблицы является нейтральным: в случае первой таблицы (слева) изменение значения на диагонали в ноль должно приводить к изменению значения функции в ноль, а в случае второй таблицы — изменение значения на диагонали в единицу должно приводить к изменению значения функции в единицу.
Например, заполним третью строку в первой таблице и первую строку — во второй.
И, действительно:
Для набора 11100 нейтральным является z. И значения функции f(11100)=1 но, f(11000)=0.
Для набора 01111 нейтральным является x. И значения функции f(01111)=0 но, f(11111)=1.
В тоже время мы могли выбрать и другие наборы, например, подобное заполнение так же оказывается правильным.
И, действительно:
Для набора 11101 нейтральным является z. И значения функции f(11101)=1 но, f(11001)=0.
Для набора 01100 нейтральным является x. И значения функции f(01100)=0 но, f(11100)=1.
Использование данного метода не предполагает наличие алгоритма, это как раз то, что называют “способом”, на каждом шаге вы можете выбрать “не совсем тот” набор для нейтрального элемента и в конечном счете не получить минимальный набор тестов. Однако используя эту технику несколько раз, приобретя опыт ее использования — у вас все будет получаться.
Продолжая рассуждать подобным образом, мы получим следующие таблицы
Что же мы получили в конце: в таблице слева - те же самые два теста на разрыв контакта. Метод нейтрального элемента это скорее прием, выбрав другие наборы мы бы не пришли к этому результату.
Больше интересных техник, а так же о том как к этому подходят в NASA вы можете узнать из книги [4].
Материалы и рекомендуемые источники
Mitchell, Jamie L., and Rex Black. Advanced software testing-vol. 3: Guide to the istqb advanced certification as an advanced technical test analyst. Rocky Nook, Inc., 2015.
