Парадигмы программирования

Стандартное (системное) программирование


Рассматривается наиболее известная парадигма программирования. Предлагается анализ ограничений на структуры управления и информационные потоки при обработке данных. Приведено обоснование дисциплины программирования на стандартных императивно-процедурных языках. Отмечена проблема сопряжения программ, подготовленных на разных языках. Методы расширения функциональных построений применены для моделирования привычного операторно-процедурного стиля программирования и техники работы с глобальными определениями. Обсуждены достоинства структурного программирования, повышающего сходимость процесса отладки программ [[11],[70]].

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

Любые конструкции стандартных языков программирования могут быть введены как функции, дополняющие исходную систему функционального программирования, что делает их вполне легальными средствами в рамках функционального подхода. Надо лишь четко уяснить цену такого дополнения и его преимущества, обычно связанные с наследованием решений и привлечением пользователей. В первых реализациях Лиспа были сразу предложены специальные формы и структуры данных, служащие мостом между разными стилями программирования, а заодно смягчающие недостатки исходной, слишком идеализированной, схемы интерпретации, выстроенной для учебных и исследовательских целей. Важнейшее такого рода средство, выдержавшее испытание временем - prog-форма, списки свойств атома и деструктивные операции, расширяющие язык программирования так, что становятся возможными оптимизирующие преобразования структур данных, программ и процессов, а главное - раскрутка систем программирования [[75]].

Применение prog-выражений позволяет писать "паскалеподобные" программы, состоящие из операторов, предназначенных для исполнения. (Точнее "алголоподобные", т.к.
появились лет за десять до паскаля. Но теперь более известен паскаль.)

Для примера prog-выражения приводится императивное определение функции Length *), сканирующей список и вычисляющей число элементов на верхнем уровне списка. Значение функции Length - целое число. Программу можно примерно описать следующими словами1):

"Это функция одного аргумента L. Она реализуется программой с двумя рабочими переменными u и v. Записать число 0 в v. Записать аргумент L в u. A: Если u содержит NIL, то программа выполнена и значением является то, что сейчас записано в v. Записать в u cdr от того, что сейчас в u. Записать в v на единицу больше того, что сейчас записано в v. Перейти к A"

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

function LENGTH (L: list) : integer; var U: list; V: integer; begin V := 0; U := l; A: if null (U) then LENGTH := V; U := cdr (U); V := V+1; goto A; end;

Переписывая на Лисп, получаем программу:

(defun

LENGTH (lambda (L) (prog (U V) (setq V 0) (setq U L) A (cond ((null U)(return V))) (setq U (cdr U)) (setq V (+ 1 V)) (go A) ))) ))

Prog-форма имеет структуру, подобную определениям функций и процедур в Паскале: (PROG, список рабочих переменных, последовательность операторов и атомов ... ) Атом в списке является меткой, локализующей оператор, расположенный вслед за ним. В приведенном примере метка A локализует оператор, начинающийся с "COND".

Первый список после символа PROG называется списком рабочих переменных. При отсутствии таковых должно быть написано NIL или (). С рабочими переменными обращаются примерно как со связанными переменными, но они не могут быть связаны ни с какими значениями через lambda. Значение каждой рабочей переменной есть NIL, до тех пор, пока ей не будет присвоено что-нибудь другое.

Для присваивания рабочей переменной применяется форма SET.


Чтобы присвоить переменной pi значение 3.14 пишется (SET (QUOTE PI)3.14). SETQ подобна SET, но она еще и блокирует вычисление первого аргумента. Поэтому (SETQ PI 3.14) - запись того же присваивания. SETQ обычно удобнее. SET и SETQ могут изменять значения любых переменных из сиска параметров более внешних функций. Значением SET и SETQ является значение их второго аргумента.

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

GO-форма, используемая для указания перехода (GO A) указывает, что программа продолжается оператором, помеченным атомом A, причем это A может быть и из более внешнего prog.

RETURN - нормальный конец программы. Аргумент return вычисляется, что и является значением программы. Никакие последующие операторы не вычисляются.



function rev (x: list) :List var y, z: list; begin A: if null (x) Then rev := y; Z := cdr (x); if atom (z) then goto B; z := rev (z); B: y := cons (z, y); x := cdr (x); goto A end;

Пример 8.1. Функция REV, обращающая список и все подсписки, столь же естественно пишется с помощью рекурсивного Prog-выражения.

Функция rev обращает все уровни списка, так что rev от (A ((B C) D)) даст ((D (C B))A).

(DEFUN rev (x) (prog (y z)

A (COND ((null x)(return y))) (setq z (CDR x)) (COND ((ATOM z)(goto B))) (setq z (rev z))

B (setq y (CONS z y)) (setq x (CDR x)) (goto A) ))

Атомы, играющие роль меток, работают как указатели помеченного блока.

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

(DEFUN set (x y) (assign x y Alist))

Здесь ASSIGN - модель присваивания переменным, хранящим значения в ассоциативном списке Alist (см. лекцию 2). Работает как замена связанного с данной переменной значения на новое заданное значение. Если пары не было вообще, то новая пара из переменной и ее значения помещается в конце списка Alist, чтобы она могла работать как глобальная.



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

(setq x 'y) (set x 'NEW) (print x) (print y) ; Напечатается Y и NEW.

Пример 8.2.

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

  • Дисциплина логики управления с исключением переходов по меткам.
  • Минимизация использования глобальных переменных в пользу параметров процедур.
  • Полнота условий в ветвлениях, отказ от отсутствия "else".
  • Однотипность результатов, полученных при прохождении через разные ветви.


Общий механизма интерпретации стандартной программы естественно представить как автомат с отдельными таблицами имен для переменных, значения которых подвержены изменениям, и для меток и процедур, определения которых неизменны. Наиболее распространенные языки программирования, такие как Фортран, Паскаль, Си, Бейсик, придерживаются примерно такой семантики при слегка варьируемой строгости контроля типов данных [[83],[85],[28],[29],[17],[47]]. Семантика стандартных императивных языков допускает применение общей абстрактной машины, что объясняет существование многоязыковых систем программирования, поддерживающих общие библиотеки процедур, компонентов и модулей, а также интеграцию с ассемблером [[42],[86],[22]].

  1)

  Примечание. Стилизация примера от МакКарти [[75]].

Содержание раздела