Accessing call stack depth in Scheme

Question

In order to demonstrate the effectiveness of tail recursion, I would like a way to access the depth of the call stack dynamically in Scheme.

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

Answer 1

Racket allows you to store values in the call stack. You can use this to keep track of the depth. Here 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)))

The output is:

(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 doesn't increase in foo and that it does in bar.

Answer 2

There is no standard way of doing it.

Tail call optimization == no call stack increase. You demonstrate it by writing what normally would blow the stack and run it.

You might get a short stack trace when signalling an error deep in, but how it looks like is implentation specific.

In CL you can trace functions and you'll see no output on consecutive tail calls when it's tail call optimized.

Lazy languages do not need tail recursion since evaluation is by need.