Mengakses kedalaman tumpukan panggilan di Skema

Untuk mendemonstrasikan efektivitas rekursi ekor, saya ingin cara mengakses kedalaman tumpukan panggilan secara dinamis di Skema.

Apakah ada cara untuk melakukan ini? Jika tidak, apakah ada cara untuk melakukan ini dalam bahasa fungsional utama lainnya (OCaml, Haskell, dll.)?


functional-programming callstack scheme tail-recursion
person Huck Bennett    schedule 18.06.2015    source sumber

Jawaban (2)


arrow_upward
2
arrow_downward

Racket memungkinkan Anda menyimpan nilai dalam tumpukan panggilan. Anda dapat menggunakan ini untuk melacak kedalamannya. Inilah cara saya melakukannya:

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

Outputnya adalah:

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

Outputnya menunjukkan bahwa kedalamannya tidak bertambah di foo dan bertambah di bar.

person soegaard    schedule 20.06.2015
comment
Sebenarnya, ini bukan tumpukan panggilan sebenarnya karena optimasi panggilan ekor wajib dan konversi CPS dari Skema. Sebaliknya, ini menunjukkan kedalaman panggilan yang bersarang dengan memaksakan panggilan untuk dibungkus dalam kode sebelum/sesudahnya. Saya tidak 100% yakin bagaimana hal ini diterapkan, tetapi ada kemungkinan besar bahwa kode semacam ini akan mencegah kode rekursif ekor dikompilasi sebagai iteratif (karena memaksa evaluasi untuk kembali melalui dan memulihkan penghitung kedalaman panggilan setelahnya semua pekerjaan selesai). - person sjamaan; 25.06.2015
comment
Apa yang dimaksud dengan menegakkan dalam konteks ini? - person soegaard; 25.06.2015
comment
@sjamaan Btw - perhatikan bahwa (apply p as) di posisi ekor. Dokumen mengatakan tentang apply bahwa Proc yang diberikan dipanggil pada posisi ekor sehubungan dengan panggilan apply. Dengan kata lain, selain tanda kelanjutan, tumpukan panggilan sebelum dan sesudah menggunakan #%app yang dimodifikasi harus setara. - person soegaard; 23.11.2015

arrow_upward
3
arrow_downward

Tidak ada cara standar untuk melakukannya.

Pengoptimalan panggilan ekor == tidak ada peningkatan tumpukan panggilan. Anda mendemonstrasikannya dengan menulis apa yang biasanya akan menghancurkan tumpukan dan menjalankannya.

Anda mungkin mendapatkan pelacakan tumpukan singkat saat memberi sinyal kesalahan yang mendalam, tetapi tampilannya spesifik untuk implementasi.

Di CL Anda dapat melacak fungsi dan Anda tidak akan melihat keluaran pada panggilan ekor berturut-turut ketika panggilan ekornya dioptimalkan.

Bahasa malas tidak memerlukan rekursi ekor karena evaluasi dilakukan sesuai kebutuhan.

person Sylwester    schedule 18.06.2015