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




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


где

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

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

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

х: Е и тогда говорят о
-абстракции.

В связи с абстракциями функции появляются некоторые (вопросы, такие, как связывание и подстановки

идентификаторов. Как уже неоднократно отмечалось, конкретный выбор идентификатора х в абстракции вида

х: Е пли ((m x) n: Е несуществен. Можно х заменить на любой другой идентификатор у, в предположении, что у сам не входит свободно в Е ("нe имеется конфликтов в обозначениях"). Тогда (m y) n: Е[y/x] семантически эквивалентно с вышеприведенным выражением. Систематическое переименование формальных параметров в
-исчислении называют также
-редукцией.

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

-редукции, приводило бы к различным результатам.


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