在lambda表达式中查找自由变量

Question

有谁知道我怎么能找出lambda表达式中的自由变量？自由变量是不属于lambda参数的变量.

我当前的方法(让我无处可去)是简单地使用car和cdr来完成表达式.我的主要问题是确定一个值是一个变量还是它是一个scheme原语.有没有办法测试某些东西是否计算出一个scheme的内置函数？例如:

(is-scheme-primitive? 'and)
;Value: #t

我正在使用麻省理工学院计划.

Answer 1

对于任意MIT Scheme程序,没有任何方法可以做到这一点.一个问题是您描述的功能无法正常工作.例如,这不使用'scheme primitive' and:

(let ((and 7)) (+ and 1))

但它肯定使用符号'and.

另一个问题是很多东西,比如and,是用宏实现的特殊形式.您需要知道程序中的所有宏是什么扩展到甚至弄清楚程序中使用了哪些变量.

要使其工作,您需要限制您接受的程序集作为输入.最好的选择是将其限制为"完全扩展"的程序.换句话说,您希望确保在free-variables函数的输入中没有使用任何宏.

为此,您可以使用expand许多Scheme系统提供的功能.不幸的是,从在线文档来看,它看起来并不像MIT Scheme提供的这个功能.如果您能够使用其他系统,则Racket提供的expand功能以及local-expand在宏内部正常工作的功能.

实际上,Racket还提供了您要求的free-variables功能的实现,正如我所描述的,它需要完全扩展的程序作为输入(例如输出expand或local-expand).您也可以看到源代码.

有关完全扩展源代码所涉问题的详细讨论,请参阅Flatt,Culpepper,Darais和Findler 即将发表的论文.

Answer 2

[编辑4]免责声明；或者，一年后回顾：

这实际上是解决这个问题的一个非常糟糕的方法。它是一种非常快速和肮脏的方法，可以实现 OP 的基本目标，但不能经受任何“现实生活”用例。请参阅此答案以及其他答案的评论中的讨论以了解原因。

[/编辑]

这个解决方案可能不太理想，但它适用于您想要在 mit-scheme 的 REPL 环境中提供的任何 lambda 形式（请参阅编辑）。我使用的过程的文档可以在mit.edu 文档站点上找到。 get-vars接受一个引号lambda并返回一个对的列表。每对的第一个元素是符号，第二个元素是 返回的值environment-reference-type。

(define (flatten lst)
  (cond ((null? lst) ())
        ((pair? (car lst)) (append (flatten (car lst)) (flatten (cdr lst))))
        (else
          (cons (car lst) (flatten (cdr lst))))))

(define (get-free-vars proc-form)
  (let ((env (ge (eval proc-form user-initial-environment))))
    (let loop ((pf (flatten proc-form))
               (out ()))
      (cond ((null? pf) out)
            ((symbol? (car pf))
             (loop (cdr pf) (cons (cons (car pf) (environment-reference-type env (car pf))) out)))
            (else
              (loop (cdr pf) out))))))

编辑：用法示例：

(define a 100)

(get-vars '(lambda (x) (* x a g)))
 => ((g . unbound) (a . normal) (x . unbound) (* . normal) (x . unbound) (lambda . macro))

编辑2：更改代码以防止environment-reference-type使用符号以外的其他内容进行调用。

编辑3：正如 Sam 在评论中指出的那样，这不会看到 lambda 下的 let 中绑定的符号具有任何值..不确定是否有一个简单的解决方案。所以，我关于这种采取任何的说法lambda是错误的，应该读得更像“任何lambda不包含新绑定形式的简单”......哦，好吧。