учебники, программирование, основы, введение в,

 

Макеты программ и тесты

Построение теорий при разработке программ
Принимая аксиоматическую теорию множеств за образец грамотно разработанной теории, попробуем проанализировать доказательные положения, полезные при обосновании и выполнении программистских проектов.
Многие построения в теории множеств выполнены над кумулятивной иерархией множеств, инициированной некоторым множеством объектов не множественной природы и пустого множества посредством операции объединения множеств. Кроме того, над множествами определены операции пересечения, дополнения, равенства, вхождения и включения, удовлетворяющие небольшому набору аксиом разной сложности.
Аналогично, структуры, такие как S-выражения, выстроены над атомами, не структурируемыми на компоненты, и пустого списка NIL, посредством операции CONS — консолидации. Над S-выражениями определены операции, позволяющие разбирать структуры на компоненты, сравнивать и анализировать структуры, отличать атомы от структур и пустой список от других данных. Элементарные операции подчинены аксиомам, обеспечивающим обратимость информационной обработки, и техника программирования на уровне строгих функций поддерживает прозрачность определений и скорость отладки.
Рассматривая программы и программные системы как формы представления знаний, трудно удержаться от попытки исследования динамики представления знаний на основе аналогии с развитием программ и программных систем.
Движущими силами этого развития являются: необходимость разных видов эффективной деятельности, потребность в уточнении представления знаний и установление новой информации, которая раньше не попадала в поле зрения или наблюдатель не был готов ее понять. Динамика представления знаний сводится к переходу от одного представления к другому.
Успешность эффективной деятельности ограничена «пропускной способностью» поля зрения. Это ограничение систематически преодолевается посредством обобщения, приводящего к представлениям более высокого порядка — представлениям более мощным, более организованным, например к процедурам, функциям, фреймам, шаблонам, макросам. Последовательность шагов обобщения можно называть индуктивным развитием представления знаний. В методике программирования индуктивное развитие соответствует восходящим методам, «снизу вверх». Как правило, индуктивное развитие имеет некоторые пределы. Такие пределы при возрастании меры информативности используемых средств рассматриваются Д.Скоттом. Интересен случай, когда пределом является теория, достаточная для порождения всей достоверной информации, установленной на данный момент времени. При разработке программ роль такого предела играет система программирования.
В результате индуктивного развития представления знаний наблюдается тенденция к возрастанию доли средств декларативного характера (таких как описания, отношения, формирователи, типы, фреймы, семантические сети, иерархии понятий, аксиоматические системы) в сравнении с долей средств процедурного характера (таких как действия, операции, операторы, процедуры, интерпретаторы, задания). Эта тенденция обуславливает рост эффективности применения дедуктивных методов и может рассматриваться как стимул к переходу от индуктивного развития к дедуктивному. Дедуктивный вывод осуществляет переход от потенциальных знаний к актуальным. Традиционно для этих целей в системах искусственного интеллекта используется метод резолюций, системы продукций и другие средства. Чередование стадий индуктивного и дедуктивного развития можно рассматривать как обоснование выбора метода программирования в зависимости от уровня развития знаний о решаемой задаче (зрелость, уровень изученности).
Применение развиваемых таким образом представлений может потребовать возврата к менее структурированным средствам (например, для упрощения обратной связи с областью, породившей решаемые задачи или для более тонкой детализации реализационных решений). Такой переход является конкретизацией представления знаний. В методике программирования конкретизация соответствует нисходящим методам «сверху вниз».
Независимо осуществляемое развитие приводит к задаче установления эквивалентности между различными системами представления знаний. При решении этой задачи возникают предпосылки для целенаправленного дедуктивного развития, что приводит к выравниванию потенциала систем (вводятся недостающие понятия, выполняются аналогичные построения, реализуются подобные инструменты). Таким образом, выделено четыре типа переходов: индуктивное и дедуктивное развитие, конкретизация и выравнивание. Эта классификация сопоставима с классификацией трансформаций программ в теории смешанных вычислений, предложенной А.П.Ершовым.

Макетирование функций
При разработке больших программ, особенно по нисходящей методике, необходимость в тестировании и отладке возникает отчасти раньше, чем подготовлен текст программы. Макет программы — это некоторый предварительный ее текст, допускающий уточнение — доопределение.
Простейший макет может быть создан из небольшой коллекции тестов, иллюстрирующих поведение программы в наиболее важных точках. Выбор таких точек — необходимая работа, результаты которой многократно используются на всех фазах жизненного цикла программы: при конструировании алгоритмов, автономном тестировании компонентов программы, комплексной отладке программы, демонстрации программы всем заинтересованным лицам, при ее эксплуатации и развитии. Функционирование простых макетов особенно легко реализуется в языках, обладающих унификацией структур данных и функциональных объектов, таких как LISP и SETL.
SETL — язык сверхвысокого уровня, представляет собой попытку активного использования теоретико-множественных понятий в практике программирования.
Согласно концепции этого языка, понятие «функция» обладает двойственной природой. Функция может быть представлена в алгоритмическом стиле — определением процедуры, выполнение которой сопоставляет результат допустимому аргументу. Но столь же правомерно представление функции в виде графика, отображающего аргументы в результаты. Оба представления могут существовать одновременно — это всего лишь две реализации одной функции. Графическое понимание функции включает в себя и табличную реализацию подобно математическим таблицам Брадиса. Кроме того график функции не обязан быть линией — это может быть фигура произвольных очертаний. Следовательно, аргументу может соответствовать множество результатов, лежащих на пересечении вертикали с этой фигурой — графиком функции. При такой трактовке нет ничего удивительного в постепенном накоплении или построении графика функции. Можно задать небольшое множество точек графика, а потом постепенно его пополнять. По замыслу Дж.Шварца, автора языка SETL, такая методика может выполнять роль оптимизации особо сложных вычислений.
Более формальный макет может быть построен из спецификаций функций в виде типовых выражений, задающих описание типов аргументов и результатов. Такой макет может работать как «заглушка» для нереализованных компонентов. Вместо них может работать универсальная функция, проверяющая соответствие фактических аргументов предписанному типу данных и вырабатывающая в качестве результата произвольное данное, соответствующее описанию результата. Этот механизм будет более эффективен в паре с простым макетом из тестов, если результат выбирать из коллекции тестов.
Мемо-функции и тестирование
Не менее ценные следствия из унификации структурных значений и функциональных объектов дает накопительный, кумулятивный эффект ряда сеансов обработки рекурсивных программ, содержащих общие компоненты. Допустимость совместного хранения функциональных определений и тестов для их проверки в общей структуре, например в списке свойств атома, именующего функцию, позволяет строить технологические макеты с множественными определениями, коллекциями тестов и спецификаций, а также с документацией. Такие макеты пригодны для поддержки полного жизненного цикла программы. Они позволяют организовывать оперативное сравнение результатов при обновлении системы функций. На такой основе возможно автоматическое тестирование программ. С практической точки зрения технологические макеты — универсальный инструмент динамической оптимизации прикладных систем.
Представим, что вычисление каждой рекурсивной функции сопровождается сохранением пары "аргумент, результат". После этого можно запустить в дело слегка измененное правило интерпретации функций. Изменение заключается в следующем: прежде чем применять функцию к фактическому аргументу, выполняется проверка, нет ли для этого аргумента уже вычисленного результата. Готовый результат и есть результат функции, а в противном случае все работает как обычно. Механизм сохранения насчитанных результатов функций назван «мемо-функции». Естественно, основанием для его применения является достаточная сложность и частота обработки. Примечательная особенность данного метода — любая сложность очень частых вычислений стремится со временем к линейной.

 
На главную | Содержание | < Назад....Вперёд >
С вопросами и предложениями можно обращаться по nicivas@bk.ru. 2013 г.Яндекс.Метрика