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

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

Разбить на страницы
Показывать лекцию целиком

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

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

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

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

Для примера prog-выражения приводится императивное определение функции ]. :

"Это функция одного аргумента 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;

Функция 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.

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

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

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

    Страницы:

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

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

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

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

    Для примера prog-выражения приводится императивное определение функции ]. :

    "Это функция одного аргумента 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;

    Функция 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.

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

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

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

    Предыдущее занятие Следующее занятие
    Вернуться к учебному плану
    ^