Чтобы продемонстрировать эффективность хвостовой рекурсии, мне нужен способ динамического доступа к глубине стека вызовов в Scheme.
Есть ли способ сделать это? Если нет, есть ли способ сделать это на других основных функциональных языках (OCaml, Haskell и т. д.)?
Racket позволяет хранить значения в стеке вызовов. Вы можете использовать это, чтобы отслеживать глубину. Вот как бы я это сделал:
#lang racket
;;; This module holds the tools for keeping track of
;;; the current depth.
(module depth racket
(provide (rename-out [depth-app #%app])
current-depth)
(define (extract-current-continuation-marks key)
(continuation-mark-set->list (current-continuation-marks) key))
(define (current-depth)
(car (extract-current-continuation-marks 'depth)))
(define-syntax (depth-app stx)
(syntax-case stx ()
[(_depth-app proc args ...)
#'(let ([p (with-continuation-mark 'depth (+ (current-depth) 1)
proc)]
[as (with-continuation-mark 'depth (+ (current-depth) 1)
(list args ...))])
(apply p as))])))
;;; Importing the #%app from the depth module will override
;;; the standard application to use depth-app which keeps
;;; track of the depth.
(require 'depth)
(with-continuation-mark 'depth 0 ; set the initial depth to 0
(let ()
;;; Example: foo is tail recursive
(define (foo n)
(displayln (list 'foo n (current-depth)))
(if (< n 5)
(foo (+ n 1))
'done))
;;; bar is not tail recursive
(define (bar n)
(displayln (list 'bar n (current-depth)))
(if (< n 5)
(cons n (bar (+ n 1)))
'()))
;;; Call the examples
(foo 0)
(bar 0)))
Результат:
(foo 0 2)
(foo 1 2)
(foo 2 2)
(foo 3 2)
(foo 4 2)
(foo 5 2)
(bar 0 2)
(bar 1 3)
(bar 2 4)
(bar 3 5)
(bar 4 6)
(bar 5 7)
'(0 1 2 3 4)
Вывод показывает, что глубина не увеличивается в foo и увеличивается в bar.
(apply p as) в хвостовой позиции. Документы говорят о apply, что данный процесс вызывается в хвостовой позиции по отношению к вызову применения. Другими словами, помимо меток продолжения, стеки вызовов до и после использования модифицированного #%app должны быть эквивалентны.
- person soegaard; 23.11.2015
Стандартного способа сделать это нет.
Оптимизация хвостовых вызовов == без увеличения стека вызовов. Вы демонстрируете это, написав то, что обычно взорвет стек и запустит его.
Вы можете получить короткую трассировку стека при глубоком оповещении об ошибке, но то, как это выглядит, зависит от внедрения.
В CL вы можете отслеживать функции, и вы не увидите вывод последовательных вызовов хвоста, когда он оптимизирован для хвостового вызова.
Ленивые языки не нуждаются в хвостовой рекурсии, поскольку вычисление выполняется по необходимости.
