Должен ли код с батутом и Y комбинатором работать в lisp с динамической областью действия?

Question

У меня есть lisp в javascript, который похож на схему. Может использоваться с лексическими и динамическими областями. Я не был уверен, как работает динамическая область действия, и кажется, что все в порядке, но этот код не работает, когда область действия динамическая:

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

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

Мой список с демонстрацией здесь https://jcubic.github.io/lips/, но код, который делает эту работу для лексической области еще не опубликован, поэтому он не будет работать. (он находится в ветке devel, и я могу создать демонстрационную версию codepen с его помощью или с помощью фрагмента стека).

Answer 1

Нет. Батутные и Y комбинаторы работают с затворами.

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

В лексическом контексте это переменные, захваченные при создании лямбды. Таким образом, код:

(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, тогда как в динамической области действия test - это то, что связано ближе всего, поэтому это локальная переменная 10. Также при звонке:

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

Теперь Common Lisp имеет динамическую область видимости и лексическую область видимости. Динамически изменяемая переменная - это переменная, которая определена для верхнего уровня с defvar, defparameter или объявлена ​​специальной. Это настолько подвержено ошибкам, что у нас есть специальное наименование для таких переменных, используя *earmuffs*.

Схема имеет параметры, которые являются изменяемыми объектами, и существует синтаксис для обновления и восстановления ее, чтобы она действовала как динамическая переменная.

EDIT

Я проверил ваш лексический и динамический язык, и оба, кажется, работают как задумано.

Answer 2

Я не понимаю, как trampoline может работать с динамической областью видимости.

Упрощенная оценка:

(define Y ...)

Теперь Y привязано (к некоторому значению).

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

Теперь trampoline связан с (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).

Нам нужно позвонить trampoline. По определению trampoline выше мы связываем f с ... и возвращаем (lambda args (let ((result (apply f args))) ...)).

Мы возвращаемся с trampoline и отменяем привязку f.

Теперь нам нужно оценить ((lambda args (let ((result (apply f args))) ...)) n 1) (применяя возвращаемое значение от trampoline к n и 1).

n в настоящее время связан с 1000, поэтому это выражение становится ((lambda args (let ((result (apply f args))) ...)) 1000 1). Чтобы выполнить вызов, мы связываем args с (1000 1).

Теперь нам нужно оценить (apply f args) (чтобы связать результат с result как часть let). apply находится в стандартной библиотеке. args был просто связан с (1000 1) выше. Но для f.

нет привязки

В этот момент мы должны выдать ошибку: единственная привязка f, которую мы видели до сих пор, была во время вызова trampoline (где 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, как и ожидалось.