Конспект установочных лекций по комплексному курсу Информатика, Теория информации
Объявления функций
Идентификаторы используются не только как держатели мест и имена для элементов данных, но и как обозначения функций. Аналогично объявлению элемента, идeнтификаторы для функций объявляются ("принимаются соглашения") с помощью записи вида
fct f= (s1x1, ..snxn) s: E и говорят об объявлении функции
или соглашении о функции. В объявлении функции одновременно и вводится идентификатор для функции, функциональность которой задастся, и специфицируется ход (процесс) вычисления отображения.
Синтаксис объявления функций очень схож с объявлениями элементов. Правда, требуется, чтобы правая часть всегда была абстракцией функции. Точная функциональность в левой части объявления не требует задания, поскольку она непосредственно может быть установлена из правой части. Достаточно в левой части задать лишь ключевое слово fct. <объявление_функции>::== fct <идентификатор>=<абстракция функции>.
В отличие от упомянутого ранее ограничения на объявления элементов допускается рекурсивное объявление функции. Объявление функции называется рекурсивным,
если объявляемый идентификатор функции встречается в правой части объявления. С помощью объявления функции устанавливается (задается) вычислительное предписание для вычисления соответствующей функции. Поэтому говорится также об объявлении вычислительного предписания,
чтобы подчеркнуть алгоритмический характер объявления функции.
Объявление функции в своей интерпретации не отличается существенно от объявления элемента. Как и объявления элементов, объявления функций используются для соглашения о функциях. Как и соглашения об элементах, они осуществляют связь идентификатора функции с отображением, которое обозначается (определяется) с помощью правой части.
Операционально (нерекурсивное) объявление функции в каком-либо блоке может быть разъяснено с помощью подстановки (развертывание, англ. unfold): [fct f=F;E]
Это правило не может применяться для рекурсивных объявлений функций, в которых идентификатор 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. Свободные идентификаторы х в теле вычислительного предписания при динамическом связывании связываются с ближайшим внешним объявлением х, которое охватывает место вызова функции в вычислительном предписании. Имеются ЯП, которые - в противовес введенному нами языку -используют динамическое связывание идентификаторов. Однако это приводит к сложным правилам анализа программ и, вообще говоря, рассматривается как неблагоприятное обстоятельство.
