Clever Geek Handbook

Accessing the depth of the call stack in a diagram

To demonstrate the efficiency of tail recursion, I would like to dynamically access the depth of the call stack in the Schema.

Is there a way to do this? If not, is there a way to do this in other mainstream functional languages ​​(OCaml, Haskell, etc.)?

+3


source to share


2 answers


Racket allows you to store values ​​on the call stack. You can use this to track depth. This is how I would do it:

#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)))

Output:



(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)

The output shows that the depth is not increasing at foo

and that it is at bar

.

+2


source


There is no standard way to do this.

Optimizing tail calls == increasing call stack. You demonstrate this by writing something that would normally hit the stack and run it.

You can get a short stack trace when you signal an error, but what it looks like is injection specific.



In CL, you can keep track of functions and you won't see the output of sequential tail calls when optimizing the tail call.

Lazy languages ​​don't need tail recursion, as evaluation is by necessity.

+3


source






More articles:


All Articles