Будет ли рекурсивно вызываемая переменная свободной или связанной?

Question

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

(define (what-kind-of-var? guess x)
    (< (abs (- (square guess) x))
        0.001))

Я вижу, что связанные переменные здесь будут guess а также x, и свободные переменные <, abs, -, а также square. Что если я позвонюwhat-kind-of-var?рекурсивно? Будет ли это связанная переменная, потому что она связывает сама себя?

Спасибо!

Answer 1

Это было бы при динамическом связывании, но у Scheme есть лексическая область видимости.

Но на самом деле это не так. "Свободный" или "связанный" происходит от лямбда-исчисления.what-kind-of-var?является переменным верхним уровнем, называя это выражение лямбды,

(define what-kind-of-var? 
  (lambda (guess x)                        ;; this
     (< (abs (- (square guess) x))
         0.001)))

но в лямбда-исчислении выражения не могут быть названы. Единственный способ вызвать его рекурсивно в лямбда-исчислении - использовать комбинатор Y:

((Y (lambda (what-kind-of-var?)                ;; outer
      (lambda (guess x)                            ;; inner
         (if (< (abs (- (square guess) x))
                0.001)
           guess
           (what-kind-of-var? (+ 1 guess) x)))))
  4 25)

и теперь конечно what-kind-of-var? это связано внутри этого нового лямбда - выражения приY. Он свободен во вложенной внутренней лямбде, но связан во внешней.

Answer 2

• guess а также xпараметры. В конечном итоге они привязываются (к соответствующим аргументам) при применении функции.

• <, abs, -, фактически привязаны к процедурам в исходной среде. Значит, это не свободные переменные.

• square будет свободной переменной при условии, что what-kind-of-var?не определен в его объеме. (Обратите внимание, чтоsqr связан в исходной среде).

• what-kind-of-var? также не является несвязанным, даже если он вызывает себя рекурсивно (при условии, что рекурсия правильно реализована на языке). (define (f param) body) можно рассматривать как (define f (lambda (param) body)

Answer 3

Вам нужно прочитать справочник по логике или лямбда-исчислению, там происхождение понятий переменной.

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

Идея привязки означает, что выделяется место в памяти, и символ переменной обозначает это место. Не каждое привязанное местоположение может быть доступно переменной.

В случае свободных переменных есть много способов привязать их к чему-либо (в языке C некоторые свободные переменные связаны процессом связывания, а некоторые никогда не связаны). В Lisp существует множество способов привязки свободной переменной - динамическое связывание, связывание статического / области видимости или в lisp_N с помощьюN > 2есть много разных способов привязать переменную. Но какова бы ни была реализация переменной, происхождение концепции исходит из математической логики.