Понимание подстановки лямбда в Redex

Question

Допустим, в Redex у меня есть следующее определение:

(define-language L
    [e ::= (λ x e) (e e) x]
    [x ::= variable-not-otherwise-mentioned]
    #:binding-forms
    (λ x e #:refers-to x))

Я бы подумал, что выражение (λ y x) x средства:

заменить появление y в x (внутри фигурных скобок в приведенном выше выражении) на x(вне скобок). А поскольку нетy в x, ответ должен быть просто x. потом(λ y x) x y должен вернуться x y. Но:

(default-language L)
(term (substitute (λ y x) x y))
'(λ y«0» y)

почему он возвращает функцию? А что значитy<<0>>жадный? Я не понимаюterm (substitute ..)?

Я тоже не понял этого результата:

(term (substitute (λ y x) x true))
'(λ y«1» true)

Может ли кто-нибудь помочь мне это расшифровать? Я новичок в Racket/Redex.

Answer 1

y«0» а также y«1» просто означает, что пока переменная называется yэто другое y чем тот, который прошел. #:refers-to Флаг используется для того, чтобы формы учитывали замену, исключающую захват.

В общем, идея такая, каким должен быть результат этой программы:

((lambda (x) (lambda (y) x))
 y)

Если эта программа оценивается как 4 или 3? Если использовать простую подстановку, то можно сказать, что программа сводится к:

(lambda (y) y)

Это функция идентичности. Это заметно, если мы, скажем, ограничим y равным 5 и назовем результат:

(let* ([y 5]
       [f ((lambda (x) (lambda (y) x))
            y)])
  (f 6))

Здесь мы ожидаем, что результат будет 5, хотя мы проезжаем 6 в f. Это потому, чтоy в результате указывает на первый y в let*. Вы можете увидеть это, если вы укажетеy в DrRacket.

Чтобы избежать этого, вместо простой замены всех xs в выражении to ys, он переименовывает все идущие вниз подшивки на новые имена, поэтому вместо этого вы получаете:

(lambda (y«0») y)

И теперь ясно, что двое ys в этом выражении разные.