Блог

Я знаю о рекурсии, но я не знаю, как это возможно. Я использую следующий пример для дальнейшего объяснения моего вопроса.

 (def (pow (x, y))
     (cond ((y = 0) 1))
           (x * (pow (x , y-1))))
  

Приведенная выше программа написана на языке Lisp. Я не уверен, правильный ли синтаксис, поскольку я придумал его в своей голове, но он подойдет. В программе я определяю функцию pow, и в pow она вызывает саму себя. Я не понимаю, как она способна это делать. Из того, что я знаю, компьютер должен полностью проанализировать функцию, прежде чем ее можно будет определить. Если это так, то компьютер должен выдавать неопределенное сообщение, когда я использую pow, потому что я использовал его до того, как он был определен. Принцип, который я описываю, действует при использовании x в x = x 1, когда x не был определен ранее.

Компиляторы намного умнее, чем вы думаете. Компилятор может включить рекурсивный вызов в это определение:

 (defun pow (x y)
  (cond ((zerop y) 1)
        (t (* x (pow x (1- y))))))
  

в goto конструкцию для повторного запуска функции с нуля:

 Disassembly of function POW
(CONST 0) = 1
2 required arguments
0 optional arguments
No rest parameter
No keyword parameters
12 byte-code instructions:
0     L0
0     (LOADamp;PUSH 1)
1     (CALLS2amp;JMPIF 172 L15)              ; ZEROP
4     (LOADamp;PUSH 2)
5     (LOADamp;PUSH 3)
6     (LOADamp;DECamp;PUSH 3)
8     (JSRamp;PUSH L0)
10    (CALLSR 2 57)                       ; *
13    (SKIPamp;RET 3)
15    L15
15    (CONST 0)                           ; 1
16    (SKIPamp;RET 3)
  

Если бы это была более сложная рекурсивная функция, которую компилятор не может развернуть в цикл, он бы просто снова вызвал функцию.

Из того, что я знаю, компьютер должен полностью проанализировать функцию, прежде чем ее можно будет определить.

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

Функция — это просто блок кода. Это название просто help, поэтому вам не нужно вычислять точный адрес, по которому она в конечном итоге окажется. Язык программирования преобразует имена в то, куда программа должна перейти для выполнения.

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

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

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

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

Давайте представим, как компилятор мог бы превратить эту функцию в машинный код:

 (defun foo (x)
  (  x (bar x)))
  

И давайте предположим, что она ничего не знает о bar на момент компиляции. Ну, у нее есть два варианта.

1. Она может компилироваться foo таким образом, что вызов bar преобразуется в набор инструкций, которые говорят: «найдите определение функции, хранящееся под именем bar , каким бы оно ни было в данный момент, и организуйте вызов этой функции с правильными аргументами».
2. Она может компилироваться foo таким образом, что происходит вызов функции на машинном уровне, но адрес этой функции оставляется в качестве некоторого заполнителя. И затем она может присоединить некоторые метаданные к foo , в которых говорится: «перед вызовом этой функции вам нужно найти функцию с именем bar , найти ее адрес, вставить его в код в нужном месте и удалить эти метаданные.

Оба этих механизма позволяют foo быть определенными до того, как станет известно, что bar есть. И обратите внимание, что вместо bar я мог бы написать foo : эти механизмы также имеют дело с рекурсивными вызовами. Однако они отличаются друг от друга.

• Первый механизм означает, что при каждом foo вызове ей необходимо выполнять какой-то динамический поиск для bar , что повлечет за собой некоторые накладные расходы (но эти накладные расходы могут быть довольно небольшими):
  • как следствие этого первый механизм будет немного медленнее, чем мог бы быть;
  • но, также как следствие этого, если bar будет переопределено, то будет принято новое определение, что является очень желательной вещью для интерактивного языка, которым обычно являются реализации Lisp.
• Второй механизм означает, что после того, foo как все ее ссылки на другие функции будут связаны с ней, вызовы будут выполняться на машинном уровне:
  • это означает, что они будут быстрыми;
  • но это переопределение будет, в лучшем случае, более сложным или, в худшем случае, вообще невозможным.

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

Очень простодушная система Lisp может работать полностью по первому механизму (я почти уверен, что именно так работает Python, например). Более продвинутый компилятор, вероятно, будет работать с помощью некоторой комбинации первого и второго механизмов. В качестве примера этого CL позволяет компилятору делать предположения о том, что кажущиеся самозвонки в функциях на самом деле являются самозвонками, и поэтому компилятор вполне может скомпилировать их как прямые вызовы (по сути, он скомпилирует функцию, а затем свяжет ее «на лету»). Но при компиляции кода в целом он может вызывать «через имя» функции.

Существуют также более или менее героические стратегии, которые things могли бы использовать: например, при первом вызове функции связать ее «на лету» со всеми вещами, на которые она ссылается, и отметить в их определениях, что если они изменятся, то эту вещь также нужно отключить, чтобы все повторилось снова. Такого рода трюки когда-то казались неправдоподобными, но компиляторы для таких языков, как JavaScript, делают вещи, по крайней мере, такие сложные, как это, постоянно.

Обратите внимание, что компиляторы и компоновщики для современных систем на самом деле выполняют нечто более сложное, чем я описал, из-за разделяемых библиотек и c: то, что я описал, более или менее соответствует тому, что происходило до разделяемой библиотеки.