УДК 519.6:681.3
Москва 1988
Методические указания по программированию в диалоговой системе структурированного программирования ДССП представляют собой учебный материал для пользователей, осваивающих эту систему. Указания включают изложение методики нисходящего конструирования программы и процедурной восходящей проверки ее правильности.
Материал рассчитан на студентов и аспирантов факультета ВМиК МГУ, а также других пользователей ДССП.
Составители:
Н.П.Брусенцов, В.Б.Захаров, И.А.Руднев, С.А.Сидоров, Н.А.Чанышев
Отв. редактор
Н.П.Брусенцов
Рецензенты:
канд. физ.-мат. наук, доцент С.Н.Разумовский
канд. физ.-мат. наук А.Л.Александров

Методические указания

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

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

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

Продемонстрируем технику создания программ в ДССП на простом примере программы, моделирующей работу двоичного сумматора. Полагаем, что слагаемые a, b и сумма s представлены 16-компонентными векторами битов вида a(15..0). Программа покомпонентно вычисляет значение суммы s, учитывая перенос cJ в текущий разряд из предшествующего младшего разряда, согласно таблице двоичного сложения

aJ bJ cJ | sJ cJ+1 --------------------- 0 0 0 | 0 0 1 0 0 | 1 0 0 1 0 | 1 0 1 1 0 | 0 1 0 0 1 | 1 0 1 0 1 | 0 1 0 1 1 | 0 1 1 1 1 | 1 1

В результате работы программы получается значение суммы s по модулю 2**16 и сохраняемая в вершине стека операндов цифра c16 переноса за пределы установленного формата числа. Готовая программа имеет следующий вид. PROGRAM $BINADD [Сложение двоичных чисел] B10 15 BIT VCTR A [слагаемое a(15..0)] 15 BIT VCTR B [слагаемое b(15..0)] 15 BIT VCTR S [сумма s(15..0)] VAR J [указатель разряда] :: : ADD [] START [0] 16 DO BITADD [c16] ; [START - нач. установка, BITADD - сложение в текущем разряде, c16 - перенос из ст. разряда]

: START [] !0 J 0 [0] ; [J=0; c0=0 - перенос в мл. разряд] : BITADD [cJ] SBIT [cJ] CBIT [cJ+1] !1+ J [cJ+1] ; [SBIT - вычисляет sJ, CBIT - вычисляет cJ+1] : SBIT [cJ] C [cJ,cJ] J A J B [cJ,cJ,aJ,bJ] '+' '+' [cJ,sJ] J ! S [cJ] ; : CBIT [cJ] BR0 C0 C1 [cJ+1] ; : C0 [] J B [bJ] BR0 0 AJ [0/aJ] ; : C1 [] J B [bJ] BR0 AJ 1 [aJ/1] ; : AJ [] J A [aJ] ; UNDEF

Программа $BINADD, как и всякая ДССП-программа, состоит из заголовка, описаний данных, определений процедур, а также отдельных команд (например, B10 - "Десятичный ввод/вывод").

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

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

Описания данных естественно предпосылать определениям процедур обработки этих данных. Каждое описание данного в ДССП содержит ключевой мнемокод (VAR, CNST, VCTR, ARR), за которым следует имя описываемого данного. Перед ключевым мнемокодом может находиться атрибут, специфицирующий базовый формат элементов данного (BIT, BYTE, DBL, по умолчанию TWOBYTE - 16-битное слово), а также некоторые другие атрибуты (FIХ, ACT, EMPTY, ::) и необходимые числовые параметры (максимальные значения индексов). В описаниях констант после имени находится список значений, оканчивающийся точкой с запятой.

В программе $BINADD имеется четыре описания данных. Слагаемые a, b и сумма s описаны как 16-компонентные векторы битов A,B и S. Указатель рассматриваемого двоичного разряда, т. е. индекс компоненты вектора, представлен 16-битной переменной J.

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

В рассматриваемой программе всего восемь определений процедур. Певое определяет процедуру ADD, представляющую действия, выполняемые программой в целом. Эта процедура включает в себя процедуру START и 16-кратное повторение процедуры BITADD. Процедура START производит начальную установку указателя J и цифры c0 переноса в младший разряд, сохраняемой в вершине стека. Процедура BITADD осуществляет сложение в одном двоичном разряде и изменяет текущее значение J, увеличивая его на 1. В нее вложны: процедура SBIT, вычисляющая значение J-го разряда суммы, и процедура CBIT, вычисляющая значение переноса в J+1 разряд. Процедура CBIT в зависимости от значения тестируемого ею переноса cJ сводится к выполнению оной из двух условно вложенных в нее процедур C0 и C1, каждая из которых определена с использованием условно вложенной процедуры AJ. Атрибут :: перед определением процедуры ADD гарантирует сохранность ее имени в словаре при очистке подсловаря $BINADD командой CLEAR $BINADD, удаляющей все другие, не обладающие атрибутом :: имена процедур и данных из этого подсловаря.

Команды, из которых состоят тела процедур, это либо просто мнемокоды операций, имена процедур, литералы и имена данных, либо ключевые мнемокоды с требуемым по смыслу каждого из них количеством дополнений - имен, мнемокодов, литералов. Например, ключевой мнемокод RP, означающий многократное повторение (repeat), требует одного дополнения, которым может быть имя повторяемого действия (операции, процедуры) или обозначение (имя, литерал) данного, значение которого подлежит многократной засылке в стек операндов. Мнемокод ! требует после себя имени переменной (массива) и означает присваивание этой переменой (элементу массива) значения, взятого из стека. Мнемокод BR0 требует двух дополнений, из которых выбирается первое, если взятое из стека значение равно нулю, а в противном случае второе.

В программе $BINADD составные команды с ключевыми мнемокодами содержатся почти во всех определениях процедур:

16 DO BITADD - выполнить BITADD 16 раз,

!0 J - присвоить переменной J значение 0,

!1+ J - увеличить значение переменной J на 1,

J ! S - присвоить J-ой компоненте вектора S взятое из стека значение,

BR0 C0 C1 - если взятое из стека равно 0, то выполнить C0, иначе выполнить C1,

BR0 AJ 1 - если взятое из стека равно 0, то выполнить AJ, иначе заслать в стек 1.

Составные команды выделяют в тексте программы, помещая перед и после каждой из них по 2-3 пробела. Таким же образом отделяется тело процедуры от ее заголовка. Определения процедур и группы определений, детализирующих какую-либо процедуру, отделяются друг от друга пустыми строками.

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

KE E <ВК> Если прежнее содержимое буфера требуется сохранить, то предварительно выполняется команда

OE <номер файла> <ВК> - сохранить текст из буфера в указанном файле.

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

Однако, прежде, чем формировать и компилировать программу $BINADD, следует обратить внимание на то, что в ней используется формат данных BIT, которого нет в базовой версии ДССП. Необходимо нарастить систему дополнительно загружаемой процедурой обработки формата BIT. Для этого надо скопировать содержащий эту процедуру файл в буфер редактора, удалить из него все не относящееся к требуемой процедуре и, перейдя в режим процессора ДССП, выполнить команду PF.

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

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

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

СУ/Е PF <ВК>

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

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

В рассматриваемой программе в первую очередь должны проверяться определения процедур START и AJ, в которых не используются определяемые в программе процедуры. Дальнейший порядок проверки может быть следующим: C0, C1, CBIT, SBIT, BITADD, ADD.

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

aJ bJ | c0 ------------- 0 0 | 0 1 0 | 0 0 1 | 0 1 1 | 1

Процедура CBIT должна формировать из заданной в вершине стека цифры cJ с учетом aJ и bJ цифру cJ+1 переноса в следующий разряд:

aJ bJ cJ | cJ+1 ----------------- 0 0 0 | 0 1 0 0 | 0 0 1 0 | 0 1 1 0 | 1 0 0 1 | 0 1 0 1 | 1 0 1 1 | 1 1 1 1 | 1

Процедура SBIT проверяется по таблице, определяющей цифры суммы в двоичном сумматоре с тремя входами:

aJ bJ cJ | sJ ---------------- 0 0 0 | 0 1 0 0 | 1 0 1 0 | 1 1 1 0 | 0 0 0 1 | 1 1 0 1 | 0 0 1 1 | 0 1 1 1 | 1

Для практического проведения проверки следует присвоить подходящие значения слагаемым a и b, воспользовавшись, например, следующей процедурой:

: INAB [] CR ."a=" TIN [a] 0 ' A D !T CR ."b=" TIN [b] 0 ' B D !T [] ;

Проверку, скажем, процедуры C0 можно произвести теперь, присвоив слагаемым a и b двоичные значения

B2 INAB <ВК> a=1010 <ВК> b=1100 <ВК> и определив вспомогательную процедуру C : C0- [] C0 2 TON !1- J [] ;

Четырехкратное выполнение этой процедуры проверяет правильность C0 на всех возможных сочетаниях значений aJ и bJ:

3 ! J 4 DO C0- <ВК> 1 0 0 0

Аналогичным образом проверяется правильность процедур C1, CBIT. Для проверки остальных процедур, присваивающих значения разрядам суммы, а также процедуры ADD в целом удобно использовать вспомогательную процедуру выдачи значения суммы на дисплей:

: OUTS [] CR ."s=" 0 ' S D @ 16 TON [] ;

На завершающем этапе правильность программы доказывается исчерпывающим для двоичного сумматора тестом, например, так:

B2 INAB <ВК> a=01111000111101010 <ВК> b=00111101111001100 <ВК> ADD OUTS <ВК> s=00110110110110110

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

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

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

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

В частности, для преобразования нашей программы двоичного сложения в программу, выполняющую вычитание a-b, достаточно изменить в ней процедуру AJ, включив в нее операцию обращения NOT:

: AJ [] J A NOT [not(aj)] ;

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

PROGRAM $BINADD B10 FIX VAR N ."N=" TIN [N] ! N [] [Задание длины операндов] N 1- [N-1] C C [N-1,N-1,N-1] [N-1,N-1,N-1] BIT VCTR A [Слагаемое a(N-1..0)] [N-1,N-1] BIT VCTR B [Слагаемое b(N-1..0)] [N-1] BIT VCTR S [Сумма s(N-1..0)] VAR J [Указатель разряда] :: : ADD [] START [0] N DO BITADD [cN] ;

Библиография

  1. Брусенцов Н.П., Захаров В.Б., Руднев И.А., Сидоров С.А., Чанышев Н.А. Развиваемый адаптивный язык РАЯ диалоговой системы программирования ДССП. - М.: Изд-во Моск. ун-та, 1987. - 80 с.
  2. Диалоговые микрокомпьютерные системы/ Под ред. Н.П.Брусенцова, А.М.Шаумана. - М.: Изд-во Моск. ун-та, 1986. - 148 с.
  3. Брусенцов Н.П. Микрокомпьютеры. - М.: Наука, 1985. - 206 с.
  4. Программное оснащение микрокомпьютеров/ Под ред. Н.П.Брусенцова, С.П.Маслова. - М.: Изд-во Моск. ун-та, 1982. - 128 с.
  5. Златкус Г.В. Диалоговая система структурированного программирования для микрокомпьютеров. Диссертация на соискание ученой степени кандидата физ.-матем. наук. - М.: МГУ, 1982. - 107 с.
  6. Руднев И.А. Исследование путей и реализация на основе ДССП целвой компиляции программ для встраиваемых микропроцессоров. Диссертация на соискание ученой степени кандидата физ.-матем. наук. - М.: МГУ, 1986. - 98 с.
  7. Сидоров С.А. Исследование мобильности ДССП и разработка средств ее переноса. Диссертация на соискание ученой степени кандидата физ.-матем. наук. - М.: МГУ, 1987. - 110 с.