Найти свободные переменные в лямбда-выражении

Кто-нибудь знает, как я могу определить свободные переменные в выражении лямбда? Свободные переменные - это переменные, которые не являются частью параметров лямбда.

Мой текущий метод (который ни к чему не приводит) заключается в том, чтобы просто использовать автомобиль и cdr для прохождения выражения. Моя основная проблема заключается в том, чтобы выяснить, является ли значение переменной или если она является одной из примитивов схемы. Есть ли способ проверить, что-то оценивает одну из встроенных функций схемы? Например:

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

Я использую схему MIT.

Ответ 1

[EDIT 4] Отказ от ответственности; или, оглядываясь назад через год:

Это действительно очень плохой способ решить эту проблему. Он работает как очень быстрый и грязный метод, который выполняет основную задачу OP, но не выдерживает никаких случаев использования "реальной жизни". Пожалуйста, ознакомьтесь с обсуждением в комментариях к этому ответу, а также другим ответом, чтобы понять, почему.

[/EDIT]

Это решение, вероятно, является менее идеальным, ~~, но оно будет работать для любой лямбда-формы, которую вы хотите передать в среде REPL мит-схемы~~ (см. правки). Документация для используемых процедур найдена на сайте doc.deu. 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))))))

EDIT: Пример использования:

(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: Как отметил Сэм в комментариях, это не будет означать, что символы, ограниченные в let под лямбдой, имеют какое-либо значение. Не уверен, что для этого есть легкое исправление. Итак, мое утверждение об этом, принимающее любой lambda, неверно и должно быть больше похоже на "Любой простой lambda, который не содержит новых форм привязки"... о хорошо.

Ответ 2

Для любых программ MIT Scheme нет никакого способа сделать это. Одна из проблем заключается в том, что функция, которую вы описываете, не может работать. Например, это не использует примитив схемы and:

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

но он, безусловно, использует символ 'and.

Другая проблема заключается в том, что многие вещи, такие как and, являются специальными формами, которые реализуются с помощью макросов. Вы должны знать, что все макросы в вашей программе расширяются, чтобы определить, какие переменные используются в вашей программе.

Чтобы выполнить эту работу, вам необходимо ограничить набор программ, которые вы принимаете в качестве входных данных. Лучший выбор - ограничить его "полностью расширенными" программами. Другими словами, вы хотите убедиться, что на вкладке free-variables нет никаких применений макросов, оставшихся на входе.

Для этого вы можете использовать функцию expand, предоставляемую многими системами Scheme. К сожалению, из онлайн-документации, это не выглядит так, как MIT Scheme предоставляет эту функцию. Если вы можете использовать другую систему, Racket предоставляет функцию expand как local-expand, который корректно работает внутри макросов.

Racket фактически также предоставляет реализацию функции free-variables, о которой вы просите, которая, как я описал, требует полностью расширенных программ в качестве входных данных (например, вывода expand или local-expand). Вы также можете увидеть исходный код.

Подробное обсуждение вопросов, связанных с полным расширением исходного кода, см. в этой предстоящей статье Флаттом, Калпеппером, Дараем и Финдлером.