Racket EXPT использует хвостовую рекурсию?

Question

Если я попробую это в Ракетке:

(expt 2 1000)

Я получу число во много раз больше, чем все атомы во вселенной:

10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376

Я даже схожу с ума (expt 2 10000), что все еще занимает всего секунду на моем ноутбуке T450.Насколько я понимаю, это возможно только из-за рекурсии хвоста.Это правильно?Если это так, является ли хвостовая рекурсия Ракета чисто функциональным программированием или скрытые побочные эффекты происходят за кулисами?Кроме того, когда я вижу Common Lisp's loop, основан ли он на хвостовой рекурсии под капотом?В общем, я думаю, мне интересно, как возможны эти умения рекурсии / зацикливания.

Answer 1

Кроме того, когда я вижу цикл Common Lisp, основан ли он на хвостовой рекурсии под капотом?

Это деталь реализации, но, скорее всего, нет.Во-первых, CL уже допускает блоки TAGBODY, что делает LOOP выразимым в терминах конструкций CL.

Например, если я макрорасширяю простой LOOP:

(loop)

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

;; SBCL
(BLOCK NIL (TAGBODY #:G869 (PROGN) (GO #:G869)))

;; CCL
(BLOCK NIL (TAGBODY #:G4 (PROGN) (GO #:G4)))

;; JSCL
(BLOCK NIL (TAGBODY #:G869 (PROGN) (GO #:G869)))

;; ECL
(BLOCK NIL (TAGBODY #:G109 (PROGN) (GO #:G109)))

;; ABCL
(BLOCK NIL (TAGBODY #:G44 (GO #:G44)))

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

При этом реализация TAGBODY с хвостовой рекурсией кажется выполнимой.Например, JSCL разрезает выражения внутри tagbody на разные методы для каждой метки, и эти методы вызываются при использовании go: https://github.com/jscl-project/jscl/blob/db07c5ebfa2e254a0154666465d6f7591ce66e37/src/compiler/compiler.lisp#L982

Более того, если я позволю loop работать длянекоторое время переполнение стека не происходит.В этом случае, однако, это происходит не из-за устранения хвостового вызова (который, AFAIK, не реализован во всех браузерах).Похоже, что код для tagbody всегда имеет неявный цикл while, и что go выдает исключения для tagbody для отлова.

Answer 2

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

Похоже, что вы концентрируетесь здесь на возможностиРакетка (и схема) для вычисления с очень большими числами.Это потому, что по умолчанию Racket и Scheme используют «bignums» для представления целых чисел.Пакеты с функциональностью bignum доступны для многих языков, включая C, но они могут выполнять дополнительную работу на языках без сборки мусора, поскольку их представления не имеют ограниченного размера.

Answer 3

Racket использует библиотеку C для реализации больших целых чисел (bignums).Библиотека называется GMP:

https://gmplib.org/manual/Integer-Exponentiation.html

Теперь случай 2 ^ n довольно легко реализовать в двоичном представлении.Вам нужен только 1, а затем ноль.То есть GMP может очень быстро вычислить число.