代码之家 › 专栏 › 技术社区 › jcubic

用trampoline和Y combinator编写的代码应该在lisp中使用动态范围吗?

dynamic-scope lexical-scope lisp

1

jcubic · 技术社区 · 7 年前

我在javascript中有lisp,它类似于scheme。它可以用于词法和动态范围。我不确定动态范围是如何工作的,它看起来没问题,但当范围是动态的时,这段代码不起作用:

(define Y
    (lambda (h)
       ((lambda (x) (x x))
           (lambda (g)
              (h (lambda args (apply (g g) args)))))))

(define (trampoline f)
    (lambda args
       (let ((result (apply f args)))
           (while (eq? (type result) "function")
               (set result (result)))
            result)))

(define (! n)
     ((trampoline (Y (lambda (f)
          (lambda (n acc)
             (if (== n 0)
                 acc
                 (lambda ()
                     (f (- n 1) (* n acc)))))))) n 1))

(print (! 1000))

当范围是词法的时候,它工作得很好。当作用域是动态的时,这个代码应该工作吗?现在它什么也不做,我也不知道为什么,但是我想在我开始调试之前确保这段代码能正常工作,并因此中断我的动态范围。

我的lisp演示在这里 https://jcubic.github.io/lips/ 但是使这项工作适用于词法范围的代码还没有发布,所以它将无法工作。(它在devel分支中,我可以用它或使用堆栈片段创建codepen演示)。

2 回复 | 直到 7 年前

1

2

melpomene 7 年前

我不知道怎么做 trampoline 可以使用动态范围。

简化评估:

(define Y ...)

现在 Y (与某个值)有关。

(define (trampoline f)
    (lambda args
       (let ((result (apply f args)))
           ...)))

现在 蹦床 (lambda (f) (lambda args (let ((result (apply f args))) ...))) .

(define (! n)
     ((trampoline ...) n 1))

! 一定会 (lambda (n) ((trampoline ...) n 1)) .

(print (! 1000))

我们首先评估内部调用,所以需要解决 ! 1000

! 在我们的约束之上 n 到 1000 评估 ((trampoline ...) n 1) .

. 根据定义 蹦床 f 到 ... 然后回来 (lambda args (let ((result (apply f args))) ...))

我们从 蹦床 f

((lambda args (let ((result (apply f args))) ...)) n 1) 蹦床 到 n 和 1

n 当前绑定到 ,所以这个表达式变成 ((lambda args (let ((result (apply f args))) ...)) 1000 1) . 执行我们绑定的调用 args (1000 1) .

现在我们需要评估 (apply f args) (将结果绑定到 result let ). apply 在标准库中。 参数 只是注定要 (1000 1)

此时我们应该抛出一个错误: f 到目前为止我们看到的是 蹦床 (其中 f f 未绑定。

实时演示(使用Perl版本的代码,其中所有绑定都是手动动态的): https://ideone.com/DWjwBj

它爆炸了,就像预测的那样: Can't use an undefined value as a subroutine reference 为了这条线 local $result = $f->(@args); 因为 $f 未绑定。

如果将所有绑定更改为词法(替换所有出现的 local 通过 my ), $fac->(5) 120 一如预期。

2

Sylwester 7 年前

动态范围没有闭包,因此引用自由变量的过程/函数意味着程序调用堆栈中具有该名称的任何变量。

在词法范围中,它是创建lambda时捕获的变量。因此,代码:

(define test 10)

(define (make-adder test)
  (lambda (v) (+ test v)))

(define add20 (make-adder 20))

(add20 5) 
; ==> 25 in lexical scope
; ==> 15 in dynamic scope

原因很简单。函数返回的函数 make-adder 20 作为 test 测试 是最接近的,所以它是局部变量 10 . 打电话时也要注意:

(let ((test 30))
  (add20 5))
; ==> 25 in lexical scope
; ==> 35 in dynamic scope

现在常见的Lisp有动态范围和词法范围。动态范围变量是用 defvar defparameter *earmuffs* .

Scheme的参数是可变的,并且有语法来更新和恢复它,这样它就可以作为一个动态变量。

编辑

我已经测试了你的词法和动态lisp,两者似乎都按预期工作。