Тестовое программирование (введение в проблему)

© 2003 г. Б. П. Кузнецов

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

В настоящее время наиболее распространены компьютеры, основанные на двоичной логике [1], на нечеткой логике [2] и нейрокомпьютеры [3]. Последние используют принцип самообучения для реализации однозначного соответствия выходных сигналов входным сигналам. При этом самообучение заключается в самонастройке (по заданному алгоритму) параметров элементов внутренней структуры нейрокомпьютера путем многократного предъявления тестовых последовательностей [3]. Компьютеры на нечеткой логике пока не рассматриваем. Однако, для компьютеров с двоичной логикой имеет место парадоксальная ситуация, состоящая в следующем. Фактически функционирование подлежащей разработке программы мыслится как набор соответствий (Х Y) выходных (Y) и входных (Х) последовательностей (причем такой набор может включать и математические формулы). Процесс программирования заключается в том, что вручную, в большинстве случаев интуитивно, строится алгоритм преобразования входных последовательностей в выходные (X Y_a); далее полученный алгоритм кодируется в текст программы (X Y_п) и преобразуется компилятором в машинный код загружаемой в компьютер (исполняемой) программы. После этого компьютеру предъявляется указанный выше набор Х входных последовательностей, и проверяется на равенство формируемый компьютером набор Y_п выходных последовательностей и заданный (исходный) набор Y, что называется тестированием [4], в том числе автоматическим [5]. Как правило, во время первых испытаний программы имеет место неравенство Y_п Y, и выполняется отладка программы путем исправления алгоритма (X Y_a) и/или текста программы (X Y_п) и повторной компиляции и тестирования с целью достижения совпадения Y_a = Y_п = Y. Таким образом, парадокс состоит в том, что, имея в начале процесса соответствие (Х Y) мы вынуждены ожидать то же соответствие в конце процесса программирования. Поэтому возникает законный вопрос: не проще ли поручить процесс программирования компьютеру.

Автор видит задачу автоматического программирования следующим образом: по заданному соответствию (Х Y), вводимому в компьютер, автоматически получить программу, реализующую реакцию Y на входное воздействие Х согласно указанному соответствию. Другими словами, используя только тестовые последовательности Х и Y (записываемые на специальном, понятном компьютеру языке, подлежащем еще разработке) получить код программы, реализующей соответствие (Х Y) при минимальном участии математиков и программистов, задача которых может сводиться только к декомпозиции исходного теста. При этом, вместо ранее разрабатываемой программы, предполагается наличие некоторого унифицированного интерпретатора, оперирующего с некоторой унифицированной структурой данных, отображающей соответствие (Х Y) возможно в минимизированном представлении. Таким образом, задача компьютера – автоматически упаковать исходное соответствие (Х Y) в указанную структуру, что и будет заменять традиционное программирование. Затем это же соответствие предъявить компьютеру для проверки созданной автоматически программы. В этом и состоит принцип самообучения двоичного компьютера, который подтверждается еще и тем, что при недостаточности последовательности тестов, последняя дополняется необходимым образом, а компьютер автоматически достраивает исходное соответствие без особых проблем.

Первичность тестов в создании программ продекларирована в технологии Test-Driven-Development (TDD) [6]. Однако в TDD тесты всего лишь служат для создания традиционного кода программы вручную, что является основанием считать данную технологию первой ласточкой к реализации подхода, предлагаемого автором данной статьи.

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

Поясним сущность рассматриваемого соответствия (Х Y). Автор считает, что это должна быть суперпозиция тестов, а именно: элементы Х могут быть как значениями входных данных реализуемого алгоритма, так и результатами выполнения «вложенного» набора тестов; аналогично – элементами Y могут быть как значения выходных данных алгоритма, так и обозначения вызываемых на исполнение «вложенных» наборов тестов. Таким образом, по аналогии с понятиями «условие» и «действие» в программах, предполагается иметь «условные» и «безусловные» вложенные тестовые наборы, обеспечивающие суперпозицию соответствия (Х Y).

Помимо суперпозиции, следует реализовать и принцип параллелизма тестов. При этом будем считать, что строгая последовательность пар «x --> y», исключающая перестановки во времени выполнения (по условию реализуемой задачи), является элементарным тестом. Совокупность элементарных тестов может быть реализована в произвольной последовательности. Буквами элементарных тестов, или в целом пара «x --> y», может быть вложенная совокупность элементарных тестов и так далее. Примем также для упрощения, что всякий элементарный тест однозначно реализует путь от оператора начала до оператора конца традиционного программного модуля, описываемого либо граф-схемой, либо (путь от начальной до конечной вершины) диаграммой переходов конечного автомата [7].

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

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

Обозначим x_i – букву входного алфавита X_IX , а y_j – букву выходного алфавита Y_OY тестового соответствия (Х Y), которое подлежит программной реализации. При этом должно иметь место разбиение входного алфавита на непересекающиеся группы, для каждой из которых выполняется условие вида (1) x_g1 x_g2 … x_gG 1, где g – номер группы, G – число букв в группе g. Положим для упрощения, что каждый элементарный тест (X_k a Y_k), из набора тестов (Х Y), представляющий собой строго упорядоченную последовательность пар вида (x_ki, y_kj), является бесповторным. Напомним, что элементарный тест однозначно соответствует пути в традиционном программном модуле от его начального до конечного оператора. Можно показать, что смысл создания традиционной программы заключается в объединении совокупности элементарных тестов в структуру типа дерево или сеть путем введения дополнительных переменных, склеивающих элементарные тесты, в результате чего образуется либо структурированная программа [10], либо одна из многочисленных программных реализаций (например, через оператор множественного выбора [9] или таблицу [11]) конечного автомата. Таким образом, сущность традиционного программирования сводится к совместной минимизации элементарных тестов путем задания схемы реализации (графической или табличной и искусственным введением дополнительных переменных, в том числе переменной искусственных состояний конечного автомата. Тем более, по мнению автора, данную реализацию можно поручить машине.

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

Поэтому простейшим решением проблемы предлагаемого тестового программирования является запись каждого элементарного теста в строку таблицы, которую назовем таблицей реализации тестов (ТРТ). В n-й столбец k-й строки ТРТ автоматически записывается очередная n-ая пара (x_ki, y_kj) из k-го элементарного теста. Полученные таким образом строки ТРТ сортируются по буквам входного алфавита, начиная с первого столбца. Очевидно, что ТРТ способна таким образом реализовать произвольное соответствие (Х Y), что и обеспечивает ее универсальность.

Универсальная интерпретация ТРТ состоит в следующем. Пусть на вход ТРТ поступила первая входная буква одного из элементарных тестов (из числа заданных). Пусть это будет буква x_ki. Интерпретатор ищет данную букву в первом столбце ТРТ, начиная с первой строки, и формирует выходную букву y_kj, из первого столбца найденной строки, подтверждая тем самым начало прохождения элементарного теста. Далее, на вход ТРТ поступает следующая входная буква данного элементарного теста. Если это не повтор первой буквы, то во втором столбце ТРТ ищется данная буква начиная с текущей строки и ниже. При нахождении этой буквы из второго столбца ТРТ формируется соответствующая выходная буква; и так далее, до конца входной последовательности элементарного теста (признак конца теста и действия, связанные с реализацией выходной буквы, не обсуждаем).

Автор видит также возможность сократить при необходимости затраты ресурсов «время-память» ТРТ путем введения служебных универсальных букв, позволяющих реализовывать деревья и сети, в том числе и диаграммы переходов конечных автоматов.

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

Обозначим входными буквами а₀ - а₇ управляющего автомата некоторого программного модуля восемь различных логических условий, а выходными его буквами с₀, с₁, с₂, с₃ - четыре некоторые действия, реализуемые модулем. Условия и действия связаны между собой в соответствие Х Y, образующее следующий набор элементарных тестов:

1) а₀с₀;
2) а₁с₂, а₃с₀;
3) а₁с₂, а₅с₀;
4) а₁с₂, а₂с₂, а₃с₀;
5) а₁с₂, а₂с₂, а₅с₀;
6) а₁с₂, а₂с₂, а₄с₃, а₇с₀;
7) а₁с₂, а₂с₂, а₄с₃, а₆с₃, а₇с₀;
8) а₁с₂, а₄с₃, а₇с₀;
9) а₁с₂, а₄с₃, а₆с₃, а₇с₀;
(Букву с₁ пока намеренно не упоминаем).

При этом входные буквы образуют следующие группы:

а₀ а₁ = 1,
а₂ а₃ а₄ а₅ = 1,
а₆ а₇ = 1.

Простейшая ТРТ, реализующая представленное соответствие (набор из девяти элементарных тестов) выглядит следующим образом:

В представленной таблице символом z указан конец вычислений. Пусть последовательность входных букв имеет следующий вид: а₁а₂а₂а₅а₀. Букве а₁ соответствуют строки 2-9 ТРТ по первому столбцу, при этом в первом такте реализуется выходная буква с₂. Следующей букве а₂ соответствуют строки 4-7 ТРТ по второму столбцу (из диапазона строк 2 - 9), и во втором такте реализуется выходная буква с₂. На вторичное и последующие повторы буквы, в данном случае а₂, повторно реализуется и соответствующая выходная буква, в данном случае с₂. Следующей букве а₅ соответствует строка 5 ТРТ по третьему столбцу (из диапазона строк 4 - 7), в третьем такте реализуется буква с₀. В четвертом такте вычисления по последней строке ТРТ не выполняются по признаку z (элементарный тест выполнен) и далее в том же четвертом такте, который уже считаем первым, снова анализируем очередную букву а₀ по первому столбцу ТРТ – это ее первая строка с выходной буквой с₀. Следующий такт свидетельствует о том, что очередной элементарный тест реализован (z - во втором столбце рассматриваемой строки). Таким же образом распознается произвольная последовательность входных букв из представленного соответствия. При этом элементарные тесты могут быть заданы и реализованы в произвольной последовательности с произвольными повторами (однако сами элементарные тесты – не расчленимы). Из этого примера можно представить универсальный алгоритм реализации управляющих автоматов на базе ТРТ. (Детали распознавания входных букв, перемещения по ТРТ и реализации выходов - опускаем).

Таким образом, ТРТ отображает параллельную структуру простейших линейных последовательностей действий, выбираемых на основе входных последовательностей. Естественно, что такая структура имеет избыточность.

Построим дерево ветвлений, соответствующее ТРТ (набору элементарных тестов):

Корень дерева соответствует начальному оператору, а свободно висячие концы стрелок соответствуют конечному оператору традиционной программы. По данному дереву можно построить обычную граф-схему структурированной программы, выполнив несложную работу по замене множественных ветвлений на последовательности парных ветвлений и добавив операторы действия, присоединяя операторы, соответствующие выходным буквам. Однако, такая граф-схема будет содержать явную избыточность, которая устраняется следующим образом. Во-первых, две дуги а₄ ведут к двум одинаковым фрагментам (а₇а₆а₇), из которых оставляем только один и к которому направляем обе дуги а₄ (по аналогии с методом минимизации граф-схем, предложенным А.Ш.Блохом [12]) Во-вторых, в оставшемся фрагменте (а₇а₆а₇) дважды встречается дуга а₇. Поэтому дугу а₆ заменяем петлей и исключаем лишнюю дугу а₇. Поступая аналогично с другими фрагментами и дугами исходного дерева ветвлений получим склеенное дерево или минимизированную сеть следующего вида:

Данной сети также соответствует структурированная программа, в которой присутствуют циклические участки, реализующие петли а₂с₂ и а₆с₃ (подробности опускаем).

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

Таким образом, мы показали на простом примере, что грамотно составленный набор элементарных тестов служит достаточным основанием для формального синтеза как граф-схем структурированных программ, так и для графов переходов конечных автоматов, а дальше – хоть SWITCH [9] , хоть FSA [13] – дело вкуса и привязанностей. По мнению автора - все указанные преобразования с синтезом текста программы можно поручить машине. Тем не менее, отметим, что представленная ТРТ также является формальной моделью конечного автомата, и, следовательно претендует на свое место в жизни. Предложенная структура ТРТ - примитивна, но работоспособна. Возможно море вариантов ее конкретного воплощения и алгоритмов ее работы. Пожалуйста - предлагайте. В принципе возможна новая структура ЭВМ на базе предлагаемой технологии. При этом самой серьезной проблемой является задание тестов с учетом декомпозиции, суперпозиции и параллелизма. (Кстати параллельная реализация при использовании ТРТ сводится к параллельной (независимой) работе фрагментов ТРТ, реализующих тестовые наборы параллельно выполняемых модулей).

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

Заинтересовавшихся проблемой тестового программирования читателей, в том числе желающих принять активное участие в проектировании и развитии предлагаемой технологии, просьба обращаться к автору по E-mail: kbp@rednet.ru - Борис Кузнецов

октябрь 2003 Санкт-Петербург

ЛИТЕРАТУРА

1. Брукшир Дж. Гленн. Введение в компьютерные науки. Общий обзор. - М. «Вильямс». 2001.

2. Прикладные нечеткие системы / Под ред. Т Тэрано, К. Асаи. - М.Сугэно. М.: Мир. 1993.

3. Круглов В.В., Борисов В.В. Искусственные нейронные сети. Теория и практика. – М.: Горячая линия - Телеком. 2001.

4. Липаев В.В. Тестирование программ. - М.: Радио и связь. 1986.

5. Бек К. Экстремальное программирование. - СПб.: Питер. 2002.

6. Бек К. Экстремальное программирование: разработка через тестирование. - СПб.: Питер. 2003.

7. Хопкрофт Дж., Мотвани Р., Ульман Дж.. Введение в теорию автоматов, языков и вычислений. М.: «Вильямс». 2002.

8. Липаев В.В. Качество программного обеспечения. М.: Финансы и статистика. 1983.

9. Шалыто А.А. SWITCH-технология. Алгоритмизация и программирование задач логического управления. СПб.: Наука. 1998.

10. Йодан Э. Структурное проектирование и конструирование программ. М.: Мир. 1979.

11. Берлин А.Н. Универсальная программа и принципы ее применения. - СПб.: «ПЕТЕРКОН». 2001.

12. Блох А.Ш. Синтез переключательных схем. Минск: Наука и техника. 1966.

13. Любченко В.С. О бильарде с Microsoft C++5.0 // Мир ПК. 1998. № 1.