Библиографическое описание:

Хайруллин И. Х. Принцип локальной обработки и его проявления в математике и программировании // Молодой ученый. — 2009. — №9. — С. 34-36.

Разработка программного обеспечения — сложная деятельность, требующая основательной теоретической подготовки и большого практического опыта [2, 3]. В статье освещается одна из причин этой сложности, связанная с субъективной сложностью восприятия больших программных систем, которая названа принципом локальной обработки. Дано неформальное определение принципа локальной обработки. К сожалению, на сегодняшний момент трудно дать строгое определение, поэтому для пояснения интуиции принципа в статье даны примеры проявлений принципа локальной обработки в физиологии, математике, программировании. Также эти примеры являются доводом в пользу гипотезы, что принцип локальной обработки совместно с необходимостью решать все более сложные задачи является одной из важных причин эволюции методов программирования и ее методологии.

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

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

Именно в этом видится причина необходимости разработки и использования различных методов разделения сложности, как в программировании, так и математике. Одним из самых распространенных является построение сложных систем методом (де)композиции. Пусть имеется функция f: S→N, сопоставляющая системе из множества S определенную сложность. (Мы не конкретизируем строение этой функции.) Имеется пороговая сложность kпрг. Системы со сложностью больше пороговой сложны для уверенного оперирования и анализа.

Пусть дана система a и f(a) > kпрг. В этом случае осуществляют декомпозицию a, т.е. выражают ее через более простые подсистемы. Формально это можно записать так: a = h(b1, …, bl), где f(h) < kпрг, f(b1) < f(a), …, f(bl) < f(a). Важно отметить, что относительная простота h, как показала практика, подразумевает небольшое число аргументов (т.е. l мало). Далее применяют декомпозицию к подсистемам bi. Процесс заканчивается, когда подсистемы становятся достаточно простыми.

Пример из физиологии. Емкость оперативной памяти человека довольно мала и составляет 7±2 простых объекта (типа букв, цифр), что называется эффектом Миллера (см. [3]). А для сложных объектов (типа образов, доводов, сравнений) — всего 4±2 (эффект Эльштейна).

Примеры из математики. В математических теориях запечатлен опыт решения сложных задач. Сейчас будут рассмотрены несколько примеров разделения сложности.

1. Рассмотрим понятие функции. Она отражает зависимость значения от аргумента (аргументов). Причем интересен следующий факт: несмотря на то, что существуют функции одного аргумента f(x), двух f(x,y), трех f(x,y,z), четырех f(x,y,z,t), нет функций от 75 аргументов. Вместо этого рассматривают функции многих аргументов f(x1, …, xn) или f(x), где x = (x1, …, xn), восприятие которых визуально (и ментально) не отличается от функции одного аргумента, имеющего структуру (в данном случае — вектор).

2. Замена переменных при решении уравнений. Пусть нужно решить уравнение

.

Осуществим замену переменных . Исходное уравнение сведется к виду . Используя известное свойство среднеарифметического, получим решение y = 1. После чего остается решить уравнение .

3. Аксиоматические теории. Они состоят из базовых объектов, аксиом, выражающие их свойства, правил вывода и теорем, полученных из аксиом путем применения правил вывода. Причем здесь можно заметить следующие количественные характеристики: небольшое число базовых объектов, небольшое число аксиом, небольшое число правил вывода. С целью сократить размер доказательства редкую теорему доказывают, используя одни лишь аксиомы. Наоборот, интенсивно используют уже доказанные теоремы. Также доказательство большой теоремы разбивают на леммы. В результате получаются небольшие по размеру доказательства.

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

5. Машина Тьюринга. Исторически эту модель вычислений Тьюринг создавал на основе анализа того, какие действия производят люди при выполнении вычислений. Можно указать два проявления принципа локальной обработки в машине Тьюринга. Во-первых, головка в каждый момент времени обозревает лишь одну ячейку ленты. Таким образом, слово, записанное на ленте, обрабатывается поэлементно, локально, а не все целиком. Во-вторых, любое вычисление представляется как композиция элементарных операций чтения и записи ячейки ленты и движения головки по ленте (см. [4]).

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

Далее рассматриваются проявления принципа локальной обработки в методах разработки программ.

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

Такой подход был вполне достаточен для маленьких, простых программ. Однако с ростом сложности программ возникли проблемы. Их причина — сложность графа управления. Оператор goto позволяет описывать произвольные графы, и с ростом размера программ эти графы становились все более запутанными. Такие сложные графы переходов получили название «блюдо спагетти».

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

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

a)         последовательное выполнение операторов используется для определения композиции отдельных операторов;

b)         условный оператор определяет функцию разбора случаев;

c)         самым сложным является анализ циклов. Для этой цели можно использовать метод индукции или инвариант цикла.

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

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

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

В реальности, правда, все не так гладко.

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

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

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

2. Модульное и объектно-ориентированное программирование.

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

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

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

Заключение

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

Литература

1.         Дал У., Дейкстра Э., Хоор К. Структурное программирование. — 1-е изд. — М.: Мир, 1975. С. 28–32.

2.         Brooks, F. P. No Silver Bullet — Essence and Accidents of Software Engineering // IEEE Computer. 1987, Vol. 20, № 4. P. 10–19.

3.         Dijkstra, E. W. The humble programmer, Turing Award lecture. — 1972. — Режим доступа: http://www.cs.utexas.edu/users/EWD/ewd03xx/EWD340.PDF, свободный.

4.         Miller, G. A. The Magical Number Seven, Plus or Minus Two: Some Limits on our Capacity for Processing Information // Psychological Review. 1956, №63. P. 81–97

5.         Turing, A. M. On Computable Numbers, with an Application to the Entscheidungs Problem // Proceedings of the London Mathematical Society. 1936. Ser. 2, 42. P. 230–265

6.         N. Wirth. Program Development by Stepwise Refinement // Communications of the ACM. 1971, № 4. P. 221–227.

Обсуждение

Социальные комментарии Cackle