ПРИНЦИП НЕОПРЕДЕЛЕННОСТИ ПРОГРАММИРОВАНИЯ

ПРИНЦИП НЕОПРЕДЕЛЕННОСТИ ПРОГРАММИРОВАНИЯ

Валерий Очков

Мне вспоминается мультфильм о козленке, который научился считать и всех встречных-поперечных пересчитывал: «Я – это раз, петух – это два, свинья – это три» и т.д. У козленка из-за этого со всей пересчитанной живностью были крупные неприятности («Ах! Ты меня пересчитал. Ну, держись!»). Но все кончилось хорошо. На то она и сказка.

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

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

Три мои статьи, опубликованные в разное время и в разных местах, имели следствия, которые я и не ожидал. Ко мне приходят письма (и на бумаге и через E-mail) даже из-за рубежа. В одном из них, вылившемся в статью [4], мой оппонент упрекает меня в «людоедском» подходе к языкам программирования. Дескать, я пытаюсь изъять из языков все алгоритмические конструкции, кроме цикла с выходами из середины, который есть d языке BASIC, но которого нет ни в Pascal’е, ни в C.

Я надеюсь, что данная статья не просто поставит точку в споре о правильности основной структурной теоремы, но и вскроет более глубинные противоречия самого программирования, покажет, какой кризис грозит этой научной дисциплине, и... Чуть было не написал “покажет пути его преодоления”. Здесь пусть сам читатель даст свою оценку.

В любой книге за исключением [5], где излагаются азы структурного программирования, можно прочесть: "Алгоритм любой сложности можно реализовать, используя только три конструкции: следование, повторение (цикл) и выбор (альтернатива)".

Реальных алгоритмических управляющих конструкций, конечно, больше трех. Есть еще и неполная альтернатива, процедура, функция пользователя, множественное ветвление и т.д. Но все они объявляются вспомогательными (следствие основы структурной теоремы), облегчающими и ускоряющими кодирование алгоритмов, но без которых при особом желании (как в программах статьи [2]) можно обойтись. Кроме того, из всех разновидностей циклов главным объявляется цикл с предпроверкой, а остальные (цикл с постпроверкой, цикл с параметром, и цикл с выходом из середины и др.) опять же считаются вспомогательными.

Из основной структурной теоремы вытекает, что в языках BASIC, Pascal, C и в других просматривается некая избыточность, направленная на повышение удобства программирования. В своих статьях я показал, что конструкция выбор также избыточна: цикл (как и переход к метке, кстати говоря) это средство ускоренного перемещения по программе в обе стороны (в начало и в конец), выбор же – только в одну (в конец).

С другой стороны, в [1] и [2] я отметил также и недостаточность управляющих конструкций языков Pascal и C, заключающуюся помимо прочего в отсутствии цикла со множеством выходов из середины и со "словами прощания", а также в отсутствии расширенного оператора CASE, о котором будет сказано ниже.

В недостаточности можно упрекнуть и всеядный язык BASIC. Если мы попробуем написать в среде MS-DOS QBasic классическую программу анализа квадратного уравнения, то соответствующий простейший алгоритм прийдется "насиловать" одним из трех способов:

Способ 1: Вложенные альтернативы

' Программа 1

INPUT "Введите через запятую значения A, B и C "; A, B, C

IF A=0 AND B=0 AND C=0 THEN

Ans$="Корни – любое значение"

ELSE

IF A=0 AND B=0 THEN

Ans$="Уравнение вырождено"

ELSE

IF A=0 THEN

Ans$="Это линейное уравнение"

ELSE

IF C=0 THEN

Ans$="Корни действительные X1=0 X2<>0"

ELSE

D=B * B – 4 * A * C

IF D>0 THEN

Ans$="Корни действительные X1<>X2"

ELSE

IF D=0 THEN

Ans$="Корни действительные X1=X2"

ELSE

Ans$="Корни комплексные"

END IF

PRINT Ans$

Программа 1 похожа на гармонь с растянутыми до предела и провисшими мехами. Восклицание Козьмы Пруткова, "Где начало того конца, которым оканчивается начало?!", можно отнести и к кружеву альтернатив программы 1. В этом заключается, если так можно выразится, практический ее недостаток: никогда нет полной уверенности, что плечи альтернатив стоят там, где надо, и программист не запутался в трех соснах ключевых слов IF-THEN-ELSE. Кроме того, из программы 1 трудно выудить ее алгоритм: компьютер, конечно, в ней разберется, но человек же, не знающий методику решения квадратного уравнения, вряд ли. Несколько сжать "гармошку" программы 1 можно за счет ключевого слова ELSEIF, но оно часто только еще больше путает программиста: в четырех соснах заблудишься быстрее, чем в трех.

Для решения проблемы вложенных альтернатив в языки введена конструкция CASE (множественное ветвление), но она бессильна перед нашей простейшей задачей, так как ветвление ведется не по одному, а по нескольким выражениям – и по булевым, и по алгебраическим.

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

Способ 2: Организация функции с досрочными выходами

Споры о том, является ли процедура-функция наряду с циклом и альтернативой основной структурной управляющей конструкцией, до сих пор не утихают. В работе [6], например, приведен ряд блок-схем, которые по мнению Н.Брусенцова нельзя реализовать без привлечения аппарата процедур. Об этом я напоминаю, чтобы еще раз обратить внимание читателей на проблематичность основной структурной теоремы: многие исследователи триаду «следование – повторение – выбор», заменяют на тетраду «следование – повторение – выбор – процедура». На досрочном выходе из процедуры (функции) работают, кстати говоря, рекурсивные алгоритмы, где за досрочным выходом из процедуры-функции следует вход в ту же процедуру (функцию), но на ином уровне.

' Программа 2

DECLARE FUNCTION Ans$ (A!, B!, C!)' Объявление функции

INPUT "Введите через запятую значения A, B и C "; A, B, C

PRINT Ans$(A, B, C)' Вызов функции

END

FUNCTION Ans$ (A, B, C)' Описание функции

IF A=0 AND B= 0 AND C=0 THEN Ans$="Корни – любое значение": EXIT FUNCTION

IF A=0 AND B=0 THEN Ans$="Уравнение вырождено": EXIT FUNCTION

IF A=0 THEN Ans$="Это линейное уравнение": EXIT FUNCTION

IF C=0 THEN Ans$="Корни действительные X1=0, X2<>0": EXIT FUNCTION

D=B * B – 4 * A * C

IF D>0 THEN Ans$="Корни действительные X1<>X2": EXIT FUNCTION

IF D=0 THEN Ans$="Корни действительные X1=X2": EXIT FUNCTION

Ans$="Корни комплексные": EXIT FUNCTION

END FUNCTION

Программа 2 также не выдерживает критики – на пустом месте городят «функционально-процедурный огород» только на студенческих семинарах. Нам же программа 2 подскажет третий – простой и структурированный способ решения задачи.

Способ 3: Использование цикла DO-LOOP со множеством выходов из середины (EXIT DO) и со словами прощания (Ans$="Это линейное уравнение")

' Программа 3

INPUT "Введите через запятую значения A, B и C "; A, B, C

IF A=0 AND B=0 AND C=0 THEN Ans$="Корни – любое значение": EXIT DO

IF A=0 AND B=0 THEN Ans$="Уравнение вырождено": EXIT DO

IF A=0 THEN Ans$="Это линейное уравнение": EXIT DO

IF C=0 THEN Ans$="Корни действительные X1=0, X2<>0": EXIT DO

D=B * B – 4 * A * C

IF D>0 THEN Ans$="Корни действительные X1<>X2": EXIT DO

IF D=0 THEN Ans$="Корни действительные X1=X2": EXIT DO

Ans$="Корни комплексные": EXIT DO

LOOP

PRINT Ans$

Если из программы 3 убрать первое слово DO, слова EXIT DO заменить на GOTO Label, а слово LOOP – на Label:, то мы получим программу с переходами к метке Label, от которых программисты бегут как черт от ладана.

Остается только ввести в языки новую управляющую конструкцию – расширенный оператор CASE, чтобы «и овцы были целы и волки сыты» – чтобы удовлетворить и сторонников и противников структурного программирования. При этом даже не нужно будет расширять и без того непомерно раздутый список ключевых слов языка BASIC – достаточно только разрешить в программе 3 вместо DO писать IF.

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

«Теоретическая» недостаточность традиционных циклов с пред- и постпроверкой заключается в том, что циклов со множеством выходов из середины не избежать, когда управляющая ими переменная меняется вне цикла. Такие элементы параллельного программирования есть и в простейшем QBasic'е (механизм системных переменных) и в Visual Basic [6], куда заложена технология обработки событий вызовом соответствующих процедур.

Булевые выражения программ 1-5 переключают наше внимание на триаду (NOT-AND-OR), где также несложно подметить избыточную недостаточность.

В математике насчитывается семь (запомните эту цифру – мы до нее еще доберемся) двухместных булевых операций: конъюнкция (AND), дизъюнкция (OR), импликация (IMP), эквиваленция (EQV), разделительная дизъюнкция (XOR), антиконъюнкция, антидизъюнкция и одна одноместная операция отрицание (NOT). Целых восемь операций! Этого, конечно, многовато (избыточно) – в скобках даны имена шести соответствующих булевых операций языка QBasic, где без антиконъюнкции и без антидизъюнкции как-то обходятся. Но на практике оставляют и того меньше – только триаду NOT-AND-OR. Но и она избыточна: в качестве базиса можно оставить только две операции – конъюнкцию (AND) и антиконъюнкцию (, например – дописано уже после опубликования статьи – все мы крепки задним умом). Дадим ей имя antiAND. Выражение A antiAND B эквивалентно выражению NOT(A AND B).

Действительно, выражение NOT A можно заменить на выражение A antiAND A, а выражение A OR B – на выражение (A antiAND A) antiAND (B antiAND B). Остальное (IMP, EQV и XOR) также несложно смоделировать. Вот вам и избыточность вышеназванной булевой восьмерки, проанализировав которую, можно предложить игру «Булевый тетрис». В ящик падают логические элементы: отрицание (квадратик с одним входом и одним выходом), конъюнкция (квадратик с двумя входами и одним выходом) и прочие аналоги двухместных логических элементов. Игрок должен, направляя их, добиваться взаимного уничтожения (NOT падает на NOT, например, и оба этих элемента пропадают на дисплее).

(Можно оставить в базисе только одну двуместную функцию: функцию Пирса (antiOR) или функцию Шеффера (antiAND) и на основе этой одной функции построить все остальные не семь, как сказано выше, а все 16. NOT(A)=A antiOR A и т.д. – дописано уже после опубликования статьи – все мы крепки задним умом).

Но также несложно показать и недостаточность полного набора булевых операций языков программирования (схема 7+1 – см. выше). Проанализируем BASIC-конструкцию:

DIM A(1 TO 100)

...

IF I>0 AND A(I)=3 THEN...

Какой здесь подводный камень? Булевая операция AND по идее должна проверить и утверждение I>0, и утверждение A(I)=3. Но если переменная I равно нулю, а у массив A нет нулевого элемента, то, не полагаясь на "сообразительность" компилятора, программист должен заменить слово AND на слова THEN IF:

IF I>0 THEN IF A(I)=3 THEN...

Здесь дифтонг THEN IF фактически дополняет список булевых операторов языка, подчеркивая недостаточность этого списка.

Обосновать не только недостаточность, но и даже ущербность самого полного набора булевых операций (7 + 1 + IF THEN – см. выше ) можно в несколько ином ключе. Во многих дисциплинах сейчас стараются отказываться от «черно-белых» оценок. Конкретный пример. При социологических опросах теперь ждут от респондентов не “Да”, “Нет” “Не знаю”, а “Да”, “Скорее да, чем нет”, “Скорее нет, чем да” и т.д. Что социология?! В самой точной на свете науке – в математике появилось новое направление: «Теория нечетких множеств» (другой термин – размытые множества, но по-английски звучит более поэтично “fuzzy set” – пушистое множество), оперирующее такими «перлами», как «Скорее 1, чем 2», «Скорее плюс, чем минус» и т.д. В основе теории неявных множеств лежит знаменитый софизм: «Если к горсти зерна добавить еще одно зернышко, превратится ли она в кучу? А если добавить два зерна? А сколько зерен превратят горсть в кучу?» Это вот сколько – типичный представитель fuzzy set, к которому трудно приложить и современную теорию чисел, и саму современную цифровую вычислительную технику. Программирование же – это по своей сути жонглирование нулями и единицами, т.е. крайняя категоричность мироощущения – все богатство цветов и оттенков сводится к черному и белому. Мир же состоит не из куч и не из горстей, а из... неявных множеств, к обсчету которых современные компьютеры приспособлены очень плохо. В этом-то, по-видимому, и будет заключаться один из будущих кризисов теории программирования и, вообще, элементной базы компьютеров.

Хоккеист, атакующий ворота противника, строит в своей голове модель полета шайбы, в которой нет ни единиц, ни нулей. Мы даже не можем понять, с какой стороны к таким моделям подойти с существующей вычислительной техникой. Вот еще одна идея к опробованию и реализации (первая – «Булевый тетрис»). Нужно заменить традиционный черно-белый набор значений булевых переменных:

Отказ	2
Да	1
Нет	0

на, например, такой (назовем его “цветным”):

Отказ	6
Ни да, ни нет	5
Да	4
Скорее да, чем нет	3
И да, и нет	2
Скорее нет, чем да	1
Нет	0

Если у читателя есть время и желание, то он может попытаться составить таблицу действий «цветных» булевых операторов. Вот ее правый верхний угол:

A	B	NOT A	A AND B	A OR B	...
6	6	6	6	?	?
5	5	5	5	?	?
4	4	0	4	?	?
3	3	1	4	?	?
2	2	2	2	?	?
1	1	3	0	?	?
0	0	4	0	?	?
6	5	-	6	?	?
5	4	-	3	?	?
4	3	-	4	?	?
3	2	-	0	?	?
2	1	-	1	?	?
1	0	-	0	?	?
0	6	-	6	?	?
6	5	-	?	?	?
5	4	-	?	?	?

Избыточную недостаточность можно заметить и в наборе встроенных функций языка программирования. Пример. Математика знает шесть прямых тригонометрических функций, на языке BASIC реализованы только три SIN, COS и TAN. Но и эта троица избыточна, если учесть, что TAN – это SIN, деленный на COS. Но и этого недостаточно, если учесть, что попытка расчета секанса нуля через вызов функции пользователя 1/SIN(0), выдаст неправильное сообщение об ошибке: «Деление на нуль», вместо «Неверный аргумент функции».

Избыточную недостаточность можно увидеть и в непростывшей новости – в технологии ООП. Центральным понятием ООП (как средства реализации метода объектно-ориентированного проектирования), наряду с понятием объекта, является понятие класса. Классы группируют в себе ключевые абстракции конкретной предметной области со сходной структурой и сходным поведением. Именно классы описываются в языке Turbo Pascal (версия 5.5 и выше) ключевым словом Object (в языке C++ – ключевым словом Class). Именно классам присущи те свойства, которые составляют суть ООП: абстрагирование, иерархичность (наследование и включение), ограничение доступа (инкапсуляция) и модульность (раздельная компиляция). Здесь триада превращается в тетраду.

Загадка числа три проста. Когда преподаватель заканчивает лекцию, то он, как правило, формулирует три вывода, оговаривает три исключения и диктует три вопроса для экзамена. И не потому, что это близко к истине, а потому, что «правда – хорошо, а счастье лучше». В Computer Science как ни в какой другой области человеческой деятельности даже самая сухая и высокая теория должна быть завернута в блестящую обертку рекламы. А числа же бывают простыми и... изящными (сакральными). Магия изящных чисел охватила и программистов и об этом я уже неоднократно писал. Но дело здесь не только в изяществе.

Читатель, задайте товарищу альтернативный вопрос («Ты идешь в кино?», например) и вы можете получить не два, а как минимум три варианта ответа («Да», «Нет» и «Не знаю»). Уход от вопроса – это тоже ответ. Что-то подобное можно наблюдать и при анализе работы логических выражений. Кроме двух известных значений (Да – Нет, Ненуль – Нуль, True – False) есть и третье, когда значение неопределенно. Такая ситуация может рассматриваться не только как авария, но и как тонкий программистский прием, опирающийся на метод проб и ошибок: если логическое выражение не определено, то выполнение программы идет по новому, третьему пути. Аналогичную картину можно наблюдать и в поведении двоичных элементов памяти компьютера – конденсатор, триггер, участок магнитного или оптического диска, дырка на перфокарте или на перфоленте. Кроме двух базовых состояний (заряжен – разряжен, открыт – закрыт, намагничен – размагничен, проколот-непроколот), генерирующих бит информации, есть и третье – недостаточно заряжен, вышел из строя, плохо намагничен, порван. Компьютер был бы неработоспособен, если б его элементная база опиралась на двоичный код. Машина должна правильно анализировать ход обработки информации (а для этого и существуют контрольные байты и другие хитрости) и ожидать не два, а три варианта ответа на альтернативный вопрос: "Да", "Нет" и "Спроси у кого-нибудь другого" или что-то в этом роде. Нутро компьютера по сути не “черно-белое” (см. выше), а “серое”.

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

Два в степени восемь – это 256. С последним числом ассоциируются ASCII-коды. Но ASCII-таблица ни машиной ни человеком никогда не воспринимается в качестве единого целого, а разбивается на две половинки: верхнюю и нижнюю по 128 символов (два в степени семь) в каждой.

Семерка – это второе магическое (сакральное) число [7]. Примеров компьютерных семерок тоже немало. Приведем курьезный.

В настоящее время пользователи персональных компьютеров переходят от работы в среде DOS к работе в среде Windows, от работы на 286-х, 386-х и 486-х машинах к работе на машинах PowerPC или с процессором Pentium. Люди, формально говоря, меняют число три (DOS, x86) на число семь (Windows, UNIX+OS2=7, Pentium, PowerPC).

У осетрины свежесть, как мы знаем, должна быть первой и последней. Последняя свежесть программных продуктов обычно нумеруется семеркой: MS-DOS 7.0, Microsoft C 7.0, Turbo Pascal 7.0... – седьмые версии, как правило, завершают линию этапных разработок.

База языка Visual Basic – семь структурных управляющих конструкций и семь типов переменных [6]. "Младший брат" языка Visual Basic – язык QBasic, конечно, не "пуп земли" – в этой статье он доминирует лишь из-за своей многотиражности. Мало найдется PC-шек, где вместе с MS-DOS не сидела бы тройка (опять тройка!) файлов qbasic.exe, qbasic.hlp и qbasic.ini, образующих ядро языка QBasic. Кстати, в классическом Pascal'е тоже семь структурных управляющих конструкций.

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

Три вывода

Первый вывод. Нормальный

Правила математики гласят, что триаду булевых выражений начинает OR, затем продолжает AND. Возглавляет же эту иерархию NOT, который сам-то в языках программирования находится на "птичьих правах" и, как отмечено выше, легко может быть заменен антиконъюнкцией.

А вот история из области теоретической физики. Давным-давно считалось, что свет это или (OR) волны (одна точка зрения), или поток частиц (противоположный взгляд). Потом решили, что свет, это и (AND) волны, и частицы. Все зависит от того, какая сторона этой физической субстанции в данный момент описывается. Современный же взгляд заключается в том, что свет – это и не (NOT) волны и не корпускулы, а что-то такое, что мы пытаемся втиснуть в узкие рамки наших представлений о природе вещей. Здесь таится некая "избыточная недостаточность" в гносеологическом плане, определяемая знаменитым соотношением неопределенности Гейзенберга: "Ни при каких обстоятельствах нельзя подсчитать абсолютно точно и координаты и импульс частиц". Возьмем это правило за некий шаблон и сформулируем принцип неопределенности программирования: "Ни при каких обстоятельствах нельзя подсчитать абсолютно точно и необходимое и достаточное число структурных управляющих конструкций (типов переменных, встроенных функций, ключевых слов, операторов и т.д.) языка программирования".

Второй вывод. Философский

Автор никогда бы не осмелился представить на суд читателей свои эти довольно-таки спорные выводы, если б ему на глаза не попался журнал «Химия и жизнь» (N 10 за 1992 г.) с интереснейшей статьей Ю.В.Чайковского «Наука без истории – ремесло убогое». Вот цитата из нее: «Ставший в последние 15 лет модным у нас триадный анализ <...> не сейчас придуман. Он идет от Платона, воспринят христианством (Троица) и разработан Гегелем (триада: тезис-антитезис-синтез). Но если богословы вправе как угодно превозносить Троицу, то ученые обязаны соотносить метод с объектом – если триада неудобна, держаться за нее не надо. <...> Платон, предпочитая триаду, пользовался ею при классификации лишь в половине случаев, другую же половину составляют у него диада, тетрада и пентада».

Третий вывод. Поэтический

Герман сошел с ума. Он сидит в Обуховской больнице в 17-м номере, не отвечает ни на какие вопросы и бормочет необыкновенно скоро: "Тройка, семерка, туз! Тройка, семерка, дама!...

А.С.Пушкин. "Пиковая дама"

Удивительный случай случился со мной: я вдруг позабыл, что идет раньше 7 или 8.

Я отправился к соседям и спросил их, что они думают по этому поводу.

Каково же было их и мое удивление, когда они вдруг обнаружили, что тоже не могут вспомнить порядок счета. 1, 2, 3, 4, 5 и 6 помнят, а дальше забыли.

Даниил Хармс. Сонет

Веками ведь, за годом год,

Из тройственности и единства

Творили глупые бесчинства

И городили огород.

А мало ль вычурных систем

Возникло на такой основе?

Глупцы довольствуются тем,

Что видят смысл во всяком слове.

И.В.Гете. "Фауст"

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

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

Литература:

1. Очков В. Двенадцать программ с дублями и эпиграфами, или триады программирования, а точнее третий лишний, а второй неправильный. Монитор.4’1993

2. Очков В. Turbo Pascal 7.0. Взгляд со стороны. КомпьютерПресс. 7’1993

3. Очков A., Очков В. Visual Basic и формула Вирта (статья с интермедиями и музыкальным дивертисментом) // КомпьютерПресс. 7 и 8’1994

4. Трофимов М. Язык программирования «Эллочка». Монитор. 7 и 8’1993

5. Очков В., Пухначев Ю. 128 советов начинающему программисту. М.: Энергоатомиздат, 1991 – 1-е изд., 1992 – 2-е изд.

6. Брусенцов Н. Микрокомпьютеры. М.: «Радио и связь», 1985

7. Очков В. Искусство – это чувство меры (компьютерный сонет № 1). «Известия» за 9.10.1994