Внутреннее взаимодействие `try` в` fixed-point`

Question

Я читаю fix-point SICP:

#+begin_src emacs-lisp :session sicp :lexical t
(defvar tolerance 0.00001)
(defun fixed-point(f first-guess)
  (defun close-enoughp(v1 v2) 
    (< (abs (- v1 v2)) tolerance))
  (defun try(guess) ;;
    (let ((next (funcall f guess)))
      (if (close-enoughp guess next)
          next
          (try next))))
  (try first-guess))
(fixed-point #'cos 1.0)
#+end_src

#+RESULTS:
: 0.7390822985224024

Из приведенного выше случая я узнал, что одна природа while это абстрактное понятие "попробовать"

#+begin_src ipython :session sicp :results output pySrc/sicp_fixedpoint2.py
import math

def fixed_point(f, guess):
    while True:
        nex = f(guess)
        if abs(guess-nex) < 0.0001:
            return nex
        else:
            guess = nex #local assignment is nature of lambda
print(fixed_point(math.cos, 1))
#+end_src

#+RESULTS:
: 0.7390547907469174

Таким образом, я мог написать итерацию на Python, просто используя эффективное функциональное мышление абстракции.

Когда размышляешь о try, чему это меня учит больше, чем "попробуй - это время в процессе"?

Его можно было бы перестроить без try, но вернуться return fixed_point(f, nex) прямо.

#+begin_src ipython :session sicp :results output :tangle pySrc/sicp_fixedpoint.py
import math
tolerance = 0.00001

def fixed_point(f, guess):
    def good_enoughp(a, b):
        return abs(a-b) < tolerance

    nex = f(guess)
    if good_enoughp(guess, nex):
        return nex
    else:
        return fixed_point(f, nex)    

print(fixed_point(math.cos, 1))
#+end_src

#+RESULTS:
: 0.7390822985224024

Итак, почему SICP представил try здесь, я полагаю, эффективность не может быть главным соображением автора.

Тест с elisp

#+begin_src emacs-lisp :session sicp :lexical t
(defvar tolerance 0.00001)
(defun fixed-point(f guess)
  (defun close-enoughp(v1 v2) ;
    (< (abs (- v1 v2)) tolerance))

  (let ((next (funcall f guess)))
    (if (close-enoughp guess next)
        next
      (fixed-point f next)))
  )
;;(trace-function #'fixed-point)
(fixed-point #'cos 1.0)
#+end_src

#+RESULTS:
: 0.7390822985224024

Работает как положено.

Кажется, что возвращение fixed-point f next немного чище, чем внутренняя итерация с try.

Что здесь рассматривается SICP, чему учат?

Answer 1

Все наоборот: он чище и эффективнее с try потому что не нужно переопределять good-enough-p.

(также вы не должны использовать рекурсию в Python).

---

Версия с try лучше, чем версия, вызывающая верхнюю функцию, fixed-point, потому как fixed-point содержит внутренние определения функций good-enough-p а также try. Простой компилятор скомпилирует его так, чтобы при каждом вызове он действительно создавал эти определения заново, снова и снова, при каждом вызове. Сtry нет такого беспокойства, так как это уже внутри fixed-pointвнутренняя среда, где good-enough-p уже определено, и поэтому try можно просто бежать.

(исправление / уточнение: в приведенном выше коде ваш код рассматривается как схема с внутренним defines вместо Common Lisp с defunкак вы показываете. В конце концов, SICP - это схема. В Common Lisp / ELisp нет даже вопроса - внутренняяdefuns будет всегда выполняться при каждом вызове включающей функции, просто (пере) определяя одни и те же функции на верхнем уровне снова и снова.)

Кстати, я, как ваш перевод петлевого Python, то есть дословный перевод с хвостовой рекурсией Схемы, одного к одному.

Твой whileперевод - это именно то, что должен делать компилятор схемы, учитывая первый рекурсивный код схемы в вашем вопросе. Эти два совершенно одинаковые, вплоть до "ужасногоwhile True ...с escape-символом ", который лично мне очень нравится своей непосредственностью и ясностью. Это означает, что мне не нужно отслеживать, какое значение присваивается какой переменной и какая переменная возвращается в конце - вместо этого значение только что вернулся, как и в схеме.

Answer 2

Схема позволяет переопределить символы верхнего уровня, такие как fixed-point; даже функцияfможет переопределить его! Компиляторы (и интерпретаторы) должны это учитывать и проверять на переопределение каждый вызовfixed-point. С другой стороны,try не виден вне определения fixed-point, так fне может его переопределить. Итак, компилятор (или интерпретатор) может превратить эту хвостовую рекурсивную функцию в цикл.

Answer 3

Я думаю, что естественный способ написать что-то подобное на Python выглядит примерно так:

tolerance = 0.00001

def fixed_point(f, first_guess):
    guess = first_guess
    next_guess = f(guess)
    def close_enough(a, b):
        return (abs(a - b) < tolerance)
    while not close_enough(guess, next_guess):
        guess = next_guess
        next_guess = f(guess)
    return next_guess

Этот:

• использует while цикл, а не рекурсия, как это естественно в Python;
• не использует какие-то ужасные while True ... с побегом, который просто сбивает с толку.

(На самом деле, поскольку вызов функции в Python обычно очень медленный, вероятно, более естественно открыть код вызова для close_enough и полностью удалите локальную функцию.)

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

Мы можем сделать это двумя способами:

• мы можем рассматривать функцию верхнего уровня как вещь, которую мы вызываем рекурсивно;
• мы можем определить некоторую локальную функцию, через которую мы выполняем рекурсию.

Что из этого делать - это действительно выбор, и в данном случае это, вероятно, не имеет большого значения. Однако у второго подхода часто есть существенные преимущества: в целом функция верхнего уровня (функция, которая находится в каком-то интерфейсе, который мы можем показывать людям) может иметь всевозможные дополнительные аргументы, некоторые из которых могут иметь значения по умолчанию и т. on, который мы действительно не хотим постоянно передавать через последующие вызовы к нему; функция верхнего уровня также может вообще не иметь соответствующей сигнатуры аргумента, потому что итерационные шаги могут повторяться по некоторому набору значений, которые получены из аргументов функции верхнего уровня.

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

Вот рекурсивная версия на Python, которая также может сделать сигнатуру функции верхнего уровня немного богаче. Обратите внимание, что такой подход был бы ужасным стилем в Python, поскольку Python не делает ничего особенного с хвостовыми вызовами. Код тоже заваленreturns, потому что Python не является языком выражений (не верьте людям, которые говорят, что Python похож на Lisp: это не так):

default_tolerance = 0.00001

def fixed_point(f, first_guess, tolerance=default_tolerance):
    guess = first_guess
    next_guess = f(guess)
    def close_enough(a, b):
        return (abs(a - b) < tolerance)
    def step(guess, next_guess):
        if close_enough(guess, next_guess):
            return next_guess
        else:
            return step(next_guess, f(next_guess))
    return step(first_guess, f(first_guess))

Что ж, в Scheme это намного естественнее: вот та же функция, написанная на Scheme (фактически, в Racket):

(define default-tolerance 0.00001)

(define (fixed-point f initial-guess #:tolerance (tolerance default-tolerance))
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (define (try guess next)
    (if (close-enough? guess next)
        next
        (try next (f next))))
  (try initial-guess (f initial-guess)))

Единственное, что здесь раздражает, это то, что мы должны запускать итерацию после определения try. Что ж, мы могли бы избежать даже этого с помощью макроса:

(define-syntax-rule (iterate name ((var val) ...) form ...)
  (begin
    (define (name var ...)
      form ...)
    (name val ...)))

А теперь мы можем написать функцию как:

(define (fixed-point f initial-guess #:tolerance (tolerance default-tolerance))
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (iterate try ((guess initial-guess) (next (f initial-guess)))
    (if (close-enough? guess next)
        next
        (try next (f next)))))

Ну на самом деле нам не нужно писать это iterate макрос: он настолько полезен в Scheme, что уже существует как специальная версия let называется 'по имени let':

(define (fixed-point f initial-guess #:tolerance (tolerance default-tolerance))
  (define (close-enough? v1 v2)
    (< (abs (- v1 v2)) tolerance))
  (let try ((guess initial-guess) (next (f initial-guess)))
    (if (close-enough? guess next)
        next
        (try next (f next)))))

И с любой из этих версий:

> (fixed-point cos 0)
0.7390822985224023
> (fixed-point cos 0 #:tolerance 0.1)
0.7013687736227565

---

Наконец, мета-комментарий: я не понимаю, почему вы, кажется, пытаетесь изучить Scheme с помощью Emacs Lisp. Эти два языка совсем не похожи: если вы хотите изучить Scheme, используйте Scheme: существует, вероятно, сотни систем Scheme, почти все из которых бесплатны.