Конспект установочных лекций по комплексному курсу Информатика, Теория информации



Связывание (свободных) идентификаторов: абстракция функций - часть 5


В частности, х не должен быть заменяемым в (m x) n: Е. Такое вхождение идентификатора х называется (аналог ситуации с кванторами) связанным вхождением.

Для большей ясности определим более точно, когда идентификатор х в выражение Е входит свободно: идентификатор х наверняка является свободным it выражении Е, ecли имеет место следующее:

·

Е состоит точно из идентификатора х;

·         Е состоит из одною указателя функции f(e1, .... Eт) и х входит свободно по крайней мере в одно из выражений e1, .... Eт

или в функциональное выражение для F;

·         Е есть абстракция функции вида(s1x1, ..snxn) sn+1: Е' и х входит свободно в Е'

и отличается от идентификаторов х; для 1 <=

i <= n;

·         Е имеет вид

if С then E else E'fi

и х входит свободно в С, Е или Е'.

Если х отлично от у и х не является свободным в ЕО, то справедливо

((m х) n:

Е)[ЕО/у] = (m х) n: (Е[ЕО/у]).

Справедливость условия "х не является свободным в ЕО" всегда может быть обеспечена посредством

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

В абстракции функции (s1x1, ..snxn) sn+1: Е создаются связывания для формальных параметров относительно их вхождения в тело Е. Связывание для идентификатора относится всегда к области связанности или, точнее, к каждому свободному вхождению соответствующего идентификатора в область связанности. Для приведенной выше абстракции функции областью связанности для идентификатора х; является выражение Е.

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

Пример (вложенное связывание). В выражении

(*) (nat х) nat: (((nat х) nat: х * х) (х + 1))

связывание х во внутренней абстракции функции вложено. Выражение (*) равносильно выражению (после переименования х во внутренней области связанности)

(nat х) nat: (((nat у) nat: у * у) (х + 1)).

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

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

(nat х, nat у) nat: if х < у then у else х fi

описывает функцию выбора наибольшего из двух натуральных чисел.

Вычисление полинома (по схеме Горнера) при заданных коэффициентах а0, ..., an

описывается через

(nat х) nat: (...(an * х + an-1) * х + ... + a1) * х + а0.

Формальные параметры являются держателями мест для исходных данных, которые необходимы для выполнения вычислений.




Содержание  Назад  Вперед