Вызовы функций, стек, куча и продолжения. Часть 1

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

Общая семантика применения функции

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

Как правило, в языках программирования используются три основные семантические интерпретации применения функции:

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

Заметим, что такая интерпретация всегда приводит к так называемому аппликативному порядку вычислений, когда сначала вычисляются аргументы, а затем к ним применяется функция:

𝑠𝑞(𝑥)=𝑥∗𝑥 ; 𝑓(𝑥,𝑦)=𝑠𝑞(𝑥+𝑦)

𝑓(3,2)=𝑠𝑞(3+2) 

𝑓(3,2)=𝑠𝑞(5) 

𝑓(3,2)=5∗5 

𝑓(3,2)=25 

Передача параметров при этой интерпретации обычно осуществляется по значению или по ссылке.

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

𝑠𝑞(𝑥)=𝑥∗𝑥 ; 𝑓(𝑥,𝑦)=𝑠𝑞(𝑥+𝑦) 

𝑓(3,2)=𝑠𝑞(3+2) 

𝑓(3,2)=(3+2)∗(3+2) 

𝑓(3,2)=5∗(3+2) 

𝑓(3,2)=5∗5 

𝑓(3,2)=25 

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

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

3) Применение функции в функциональных языках. В таком случае запись f(x,y) означает просто саму по себе функциональную зависимость значения функции от её параметров. В функциональных языках функции обычно не имеют побочных эффектов, поэтому могут вычисляться с применением не только аппликативного (или нормального) но и ленивого порядка вычислений. Ленивый порядок вычислений заключается в том, что значение функции вычисляется только в тот момент, когда фактически потребовался её результат. Ленивый порядок вычислений позволяет свободно записывать бесконечные рекурсивные последовательности, так как фактически всегда будет востребовано ограниченное количество их первых членов. Это возможно именно за счёт того, что применение функции в ленивом порядке не является её «вызовом» в том смысле, как мы его понимаем в императивных языках.

Более строго функциональные языки, такие как Haskell, часто ограничиваются ленивым порядком вычислений. Более универсальные языки, такие как Lisp и Scheme, позволяют использовать по выбору программиста и аппликативный, и нормальный, и ленивый порядок (хотя исходно вычисление функций в Лисп-подобных языках аппликативно).

Передача параметров в данной интерпретации обычно осуществляется по значению.

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

Реализация императивного вызова функции в машинном коде

«Стек! Стек!» – захлопали татары ©.

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

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

Прежде всего, в конкретной архитектуре процессора может вообще отсутствовать стек. Самым известным примером такого рода являются мейнфреймы IBM (IBM S/360 … IBM z).

Как происходит императивный вызов нерекурсивной нереентерабельной (т.е. не способной вызываться несколько раз параллельно) функции на IBM z? Очень просто. Адрес возврата сохраняется в регистре общего назначения, параметры передаются через регистры, локальные переменные размещаются в статически выделенной в объектном коде области локальной памяти функции. Всё. Никаких накладных расходов.

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

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

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

Таким образом, стековая модель в общем случае себя показывает более эффективной для последовательных рекурсивных вызовов с ограниченной глубиной, а бесстековая – для нерекурсивных вызовов, рекурсивных вызовов большой глубины или параллельных вызовов. Реально используемые программы, однако, по своему устройству чаще всего соответствуют именно первому случаю.

Реализация императивного вызова функции в модели продолжений

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

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

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