方案展开过程调用 [英] Scheme expand procedure calls

问题描述

给定一个函数，例如斐波那契递归的树递归实现，我如何显示对诸如 (fib 5) 之类的表达式求值的每个步骤?

Given a function such as the tree-recursive implementation of the fibonacci recurrence, how could I show each step in the evaluation of an expression such as (fib 5)?

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1)
                 (fib (- n 2))))))

比如我想输出:

(fib 5)

(+ (fib 4) (fib 3))

(+ (+ (fib 3) (fib 2)) (+ (fib 2) (fib 1)))

(+ (+ (+ (+ (fib 1) 0) (fib 1) (+ (fib 1) 0)) (+ (+ (fib 1) 0) (fib 1)))

(+ (+ (+ (+ 1 0) 1 (+ 1 0)) (+ (+ 1 0) 1))

我知道使用 quasiquoting，你可以部分评估一个表达式，如:

I know that using quasiquoting, you can partially evaluate an expression, as in:

`(+ ,(* 3 4) (- 0.1 2))   ; evaluates to -┐
(+ 12 (- 0.1 2))          ;          <----┘

然而，我一直无法用这个来展示评估中的每一步.我知道我可以修改像 Peter Norvig 的 lis.py 这样的方案解释器，但我想要一种方法它在语言本身内.我该怎么做?

However, I have not been able to use this to show each step in the evaluation. I know I could modify a scheme interpreter like Peter Norvig's lis.py, but I would like a way to do it within the language itself. How can I do this?

推荐答案

你的意思是，像这样?

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else `(+ ,(fib (- n 1))
                  ,(fib (- n 2))))))

例如:

(fib 5)
=> '(+ (+ (+ (+ 1 0) 1) (+ 1 0)) (+ (+ 1 0) 1))

当然，上面只会返回评估的final结果.使用 Racket 中的内置步进器，您可以看到每个中间步骤.有关如何查看此答案的一些方法，它也恰好显示了斐波那契函数.

Of course, the above will return only the final result of the evaluation. Using a built-in stepper like the one in Racket, you can see each intermediate step. For a little how-to see this answer, which happens to show the fibonacci function, too.

这篇关于方案展开过程调用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！