Я думаю, чтобы увидеть, как это может работать в целом , и, в частности, в случаях, когда рекурсивные вызовы не могут превращаться в циклы, стоит подумать о том, как скомпилирован общий язык может работать, потому что проблемы не отличаются.
Давайте представим, как компилятор может превратить эту функцию в машинный код:
(defun foo (x)
(+ x (bar x)))
И давайте предположим, что он ничего не знает о bar во время компиляции. Ну, у него есть два варианта.
- Он может скомпилировать
foo таким образом, что вызов bar переводится как набор инструкций, которые говорят: «найдите определение функции, хранящееся под именем bar, каким бы оно ни было в настоящее время, и упорядочите чтобы вызвать эту функцию с правильными аргументами ".
- Он может скомпилировать
foo таким образом, что есть функция функции на уровне машины для функции, но адрес этой функции остается в качестве заполнителя некоторого вида. И затем он может присоединить некоторые метаданные к foo, которые говорят: «перед вызовом этой функции вам нужно найти функцию с именем bar, найти ее адрес, объединить ее в код в нужном месте, и удалить это метаданные .
Оба эти механизма позволяют определить foo, прежде чем станет известно, что такое bar. И обратите внимание, что вместо bar я мог бы написать foo: эти механизмы также работают с рекурсивными вызовами. Однако они отличаются от этого.
- Первый механизм означает, что каждый раз, когда вызывается
foo, ему нужно выполнить какой-то динамический поиск для bar, что потребует некоторых издержек (но это может быть довольно мало):
- в результате этого первый механизм будет немного медленнее, чем мог бы быть;
- но, как следствие этого, если
bar будет переопределено, то будет выбрано новое определение, что очень желательно для интерактивного языка, которым обычно являются реализации на Лиспе.
- Второй механизм означает, что после того, как
foo имеет все ссылки на другие функции, связанные с ним, вызовы происходят на уровне машины:
- это значит, что они будут быстрыми;
- но это переопределение будет, в лучшем случае, более сложным или, в худшем случае, вообще невозможным.
Вторая из этих реализаций близка к тому, как традиционные компиляторы компилируют код: они компилируют код, оставляя кучу заполнителей со связанными метаданными, указывающими, каким именам соответствуют эти заполнители. linker (иногда называемый загрузчиком ссылок или загрузчиком) затем обрабатывает все файлы, созданные компилятором, а также другие библиотеки кода и разрешает все эти ссылки, в результате чего получается немного кода. который на самом деле может быть запущен.
Очень простая система Lisp может работать полностью по первому механизму (например, я уверен, что именно так работает Python). Более продвинутый компилятор, вероятно, будет работать по некоторой комбинации первого и второго механизма. В качестве примера этого CL позволяет компилятору делать предположения о том, что кажущиеся самостоятельные вызовы в функциях действительно являются самостоятельными вызовами, и поэтому компилятор вполне может скомпилировать их как прямые вызовы (по сути, он скомпилирует функцию а затем связать его на лету). Но при компиляции кода в целом он может вызывать функцию «через имя».
Существуют также более или менее героические стратегии, которые могут делать вещи: например, при первом вызове функции связывают ее, на лету, со всеми вещами, на которые она ссылается, и отмечают в их определений, что если они изменяются, то это тоже нужно отсоединить, чтобы все это повторилось. Подобные уловки когда-то казались неправдоподобными, но компиляторы для языков, таких как JavaScript, все время делают вещи, по крайней мере, такие же странные, как сейчас.
Обратите внимание, что компиляторы и компоновщики для современных систем на самом деле делают нечто более сложное, чем я описал, из-за разделяемых библиотек & c: то, что я описал, более или менее то, что происходило до разделяемой библиотеки.