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

Объявления функций


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

fct f= (s1x1, ..snxn) s: E и говорят об объявлении функции

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

Синтаксис объявления функций очень схож с объявлениями элементов. Правда, требуется, чтобы правая часть всегда была абстракцией функции. Точная функциональность в левой части объявления не требует задания, поскольку она непосредственно может быть установлена из правой части. Достаточно в левой части задать лишь ключевое слово fct. <объявление_функции>::== fct <идентификатор>=<абстракция функции>.

В отличие от упомянутого ранее ограничения на объявления элементов допускается рекурсивное объявление функции. Объявление функции называется рекурсивным,

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

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

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

Операционально (нерекурсивное) объявление функции в каком-либо блоке может быть разъяснено с помощью подстановки (развертывание, англ. unfold): [fct f=F;E]

E[F/f].

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

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

[nat х = 1; [fсt f = (nat у) nat: х + у; [nat х = 2; f(3)] ] ]

возникает вопрос: дает вызов f(3) значение 4 или 5? Это зависит от упорядочения вхождения идентификатора х в тело f по отношению к одному из обоих объявлений х.

По вышеприведенному определению f(3) имеет значение 4, так как х в теле функции f связывается через первое объявление со значением 1. Говорят о статическом связывании (англ. static scoping): идентификаторы х, которые входят свободно в вычислительное предписание, связываются ("статически") с помощью ближайшего внешнего объявления х, содержащегося в записи, которая охватывает место описания вычислительного предписания. Это выражается также в приведенном выше правиле вычисления благодаря требованию переименования локальных идентификаторов при конфликте имен.

В противоположность статическому связыванию, динамическое связывание (англ. dynamic scoping) в этом примере f(3) даст значение 5. Свободные идентификаторы х в теле вычислительного предписания при динамическом связывании связываются с ближайшим внешним объявлением х, которое охватывает место вызова функции в вычислительном предписании. Имеются ЯП, которые - в противовес введенному нами языку -используют динамическое связывание идентификаторов. Однако это приводит к сложным правилам анализа программ и, вообще говоря, рассматривается как неблагоприятное обстоятельство.


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