WikiDer > Структурированное программирование Джексона

Jackson structured programming
Пример диаграммы JSP.

Структурированное программирование Джексона (JSP) - метод для структурное программирование разработан британским консультантом по программному обеспечению Майкл А. Джексон и описал в своей книге 1975 г. Принципы разработки программ.[1] Методика JSP заключается в анализе структур данных файлов, которые программа должна читать как ввод и создавать как вывод, а затем создавать проект программы на основе этих структур данных, так что структура управления программой обрабатывает эти структуры данных в естественном виде. и интуитивно понятный способ.

JSP описывает структуры (как данных, так и программ) с использованием трех основных структур: последовательность, итерация и выбор (или альтернативы). Эти структуры изображены в виде (по сути) визуального представления регулярное выражение.

Введение

Майкл А. Джексон Первоначально JSP был разработан в 1970-х годах. Он задокументировал систему в своей книге 1975 года. Принципы разработки программ.[1] В докладе на конференции 2001 г.[2] он представил ретроспективный анализ исходных движущих сил метода и связал его с последующими разработками программной инженерии. Целью Джексона было сделать КОБОЛ программы пакетной обработки файлов легче изменять и поддерживать, но этот метод можно использовать для разработки программ для любых язык программирования который имеет структурированные управляющие конструкции - последовательность, итерацию и выбор («если / тогда / иначе»).

Структурное программирование Джексона было похоже на Структурированное программирование Warnier / Orr[3][4] хотя JSP рассматривал как входные, так и выходные структуры данных, тогда как метод Warnier / Orr фокусировался почти исключительно на структуре выходного потока.

Мотивация к методу

На момент разработки JSP большинство программ представляли собой пакетные программы на языке COBOL, обрабатывающие последовательные файлы, хранящиеся на ленте. Типичная программа считывает свой входной файл как последовательность записей, так что все программы имеют одинаковую структуру - единственный главный цикл, который обрабатывает все записи в файле по очереди. Джексон утверждал, что эта структура программы почти всегда ошибочна, и поощрял программистов искать более сложные структуры данных. В главе 3 Принципы разработки программ[1] Джексон представляет две версии программы: одна разработана с использованием JSP, а другая - с использованием традиционной однопетлевой структуры. Вот его пример, переведенный с COBOL на Java. Целью этих двух программ является распознавание групп повторяющихся записей (строк) в отсортированном файле и создание выходного файла, в котором перечислены все записи и количество раз, которые они встречаются в файле.

Вот традиционная одноконтурная версия программы.

Строка линия;int считать = 0;Строка firstLineOfGroup = значение NULL;// начинаем единственный основной циклв то время как ((линия = в.readLine()) != значение NULL) {    если (firstLineOfGroup == значение NULL || !линия.равно(firstLineOfGroup)) {        если (firstLineOfGroup != значение NULL) {            Система.вне.println(firstLineOfGroup + " " + считать);        }        считать = 0;        firstLineOfGroup = линия;    }    считать++;}если (firstLineOfGroup != значение NULL) {    Система.вне.println(firstLineOfGroup + " " + считать);}

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

Строка линия;int numberOfLinesInGroup;линия = в.readLine();// начинаем внешний цикл: обрабатываем 1 группув то время как (линия != значение NULL) {      numberOfLinesInGroup = 0;    Строка firstLineOfGroup = линия;    // начинаем внутренний цикл: обрабатываем 1 запись в группе    в то время как (линия != значение NULL && линия.равно(firstLineOfGroup)) {        numberOfLinesInGroup++;        линия = в.readLine();    }    Система.вне.println(firstLineOfGroup + " " + numberOfLinesInGroup);}

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

Основной метод

JSP использует полуформальные шаги для фиксации существующей структуры входных и выходных данных программы в структуре самой программы.

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

JSP структурирует программы по четырем типам компонентов:

  • основные операции
  • последовательности
  • итерации
  • выбор

Метод начинается с описания входных данных программы в терминах четырех основных типов компонентов. Затем таким же образом описываются результаты программы. Каждый вход и выход моделируются как отдельные Схема структуры данных (DSD). Чтобы JSP работал для приложений с интенсивными вычислениями, таких как цифровая обработка сигналов (DSP), также необходимо рисовать схемы структуры алгоритмов, которые фокусируются на внутренних структурах данных, а не на входных и выходных.

Затем структуры ввода и вывода объединяются или объединяются в окончательную структуру программы, известную как диаграмма структуры программы (PSD). Этот шаг может включать добавление небольшого количества структуры управления высокого уровня для объединения входов и выходов. Некоторые программы обрабатывают весь ввод перед выводом, в то время как другие читают одну запись, записывают одну запись и выполняют итерацию. Такие подходы должны быть отражены в PSD.

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

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

Простая операция изображена в виде прямоугольника.

Коробка с надписью
Операция

Последовательность операций представлена ​​прямоугольниками, соединенными линиями. В приведенном ниже примере операция A состоит из последовательности операций B, C и D.

Коробка с надписью
Последовательность

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

Поле с надписью
Итерация

Выделение похоже на последовательность, но с кружком в правом верхнем углу каждой дополнительной операции. В этом примере операция A состоит из одной и только одной из операций B, C или D.

Коробка с надписью
Выбор

Рабочий пример

В качестве примера, вот как программист JSP разработал бы и закодировал кодировщик длины прогона. Кодировщик длин серий - это программа, входом которой является поток байтов, который можно рассматривать как происходящий в бежит, где серия состоит из одного или нескольких экземпляров байтов с одинаковым значением. Результатом программы является поток пар байтов, где каждая пара байтов представляет собой сжатое описание выполнения. В каждой паре первый байт - это значение байта, повторяющегося в цикле, а второй байт - это число, указывающее, сколько раз это значение было повторено в цикле. Например, серия из восьми вхождений буквы «A» во входном потоке («AAAAAAAA») создаст «A8» как пару байтов в выходном потоке. Кодеры длин серий часто используются для грубого сжатия растровых изображений.

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

JSP RLE input.png

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

JSP RLE output1.png

Следующий шаг - описать соответствия между компонентами входной и выходной структур.

JSP RLE корреспонденция.png

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

JSP RLE program.png

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

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

Кроме того, на этом этапе условия на итерациях (циклах) и выборках (if-then-else или case-операторы) перечисляются и добавляются в диаграмму структуры программы.

  1. пока байтов больше
  2. пока байтов больше, и этот байт совпадает с первым байтом прогона, и счетчик по-прежнему умещается в байте

Когда диаграмма будет завершена, ее можно будет перевести на любой используемый язык программирования. Вот перевод на C.

#включают <stdio.h>#включают <stdlib.h>int основной(int argc, char *argv[]){    int c;    int first_byte;    int считать;    c = Getchar();   / * получаем первый байт * /    в то время как (c != EOF) {        / * обрабатываем первый байт в прогоне * /        first_byte = c;        считать = 1;        c = Getchar();   / * получить следующий байт * /        / * обрабатываем последующие байты в прогоне * /        в то время как (c != EOF && c == first_byte && считать < 255) {            / * обрабатываем один байт того же значения * /            считать++;            c = Getchar();   / * получить следующий байт * /        }        путчар(first_byte);        путчар(считать);    }    вернуть EXIT_SUCCESS;}

Методы решения сложных задач проектирования

В Принципы разработки программ Джексон распознал ситуации, в которых возникали определенные проблемы проектирования, и предложил методы их решения.

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

Другой вид проблем связан с тем, что Джексон назвал «трудностями распознавания», а сегодня мы бы назвали их проблемами синтаксического анализа. Базовая техника разработки JSP была дополнена операциями POSIT и QUIT, что позволило разработать то, что мы теперь называем анализатором с возвратом.

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

JSP и объектно-ориентированный дизайн

JSP был разработан задолго до того, как стали доступны объектно-ориентированные технологии. Он и его последовательный метод JSD не относитесь к тому, что сейчас называлось бы «объектами», как с совокупностью более или менее независимых методов. Вместо этого, следя за работой C A R Hoare, JSP и JSD описывают программные объекты как совместные процедуры.[5][6]

Смотрите также

использованная литература

  1. ^ а б c Джексон, Массачусетс (1975), Принципы разработки программ, Академический.
  2. ^ Джексон, Массачусетс (2001), JSP в перспективе (PDF), Конференция пионеров SD&M, Бонн, июнь 2001 г., получено 2017-01-26CS1 maint: location (ссылка на сайт)
  3. ^ Варнье, JD (1974), Логическое построение программ, Нью-Йорк: Ван Ностранд Рейнхольд
  4. ^ Орр, К.Т. (1980), "Структурированное программирование в 1980-е годы", Материалы ежегодной конференции ACM 1980 г., Нью-Йорк, штат Нью-Йорк: ACM Press, стр. 323–26, Дои:10.1145/800176.809987, ISBN 978-0897910286
  5. ^ Wieringa, R (декабрь 1998 г.), "Обзор методов и приемов спецификации структурированного и объектно-ориентированного программного обеспечения", Comput Surv, 30 (4): 459–527, CiteSeerX 10.1.1.107.5410, Дои:10.1145/299917.299919.
  6. ^ Хендерсон-Селлерс, Брайан; Эдвардс, Дж. М. (сентябрь 1990 г.), «Жизненный цикл объектно-ориентированных систем», Коммуникации ACM, 33 (9): 142–59, Дои:10.1145/83880.84529.

внешние ссылки