Доступ к глубине стека вызовов в схеме

Question

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

Есть ли способ сделать это? Если нет, есть ли способ сделать это на других основных функциональных языках (OCaml, Haskell и т. Д.)?

Answer 1

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.

Answer 2

Нет стандартного способа сделать это.

Оптимизация вызовов хвоста == увеличение стека вызовов. Вы демонстрируете это, написав то, что обычно ударит стек и запустит его.

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

В CL вы можете отслеживать функции, и вы не увидите выход по последовательным хвостовым вызовам, когда оптимизирован хвостовой вызов.

Ленивые языки не нуждаются в рекурсии хвоста, так как оценка по необходимости.