Как этот код Схемы возвращает значение?

Question

Этот код взят из Sussman и Wisdom's Структура и интерпретация классической механики , его целью является получение (близко к) наименьшей положительной плавающей запятой, которую поддерживает хост-машина. https://github.com/hnarayanan/sicm/blob/e37f011db68f8efc51ae309cd61bf497b90970da/scmutils/src/kernel/numeric.scm

Запуск его в DrRacket приводит к 2.220446049250313e-016 на моей машине.

Мой вопрос, что заставляет его даже возвращать значение? Этот код является хвостовой рекурсивной, и в некоторый момент имеет смысл, что компьютер больше не может делить на 2. Почему он не выдает?

(define *machine-epsilon*
  (let loop ((e 1.0))
     (if (= 1.0 (+ e 1.0))
         (* 2 e)
         (loop (/ e 2)))))
*machine-epsilon*

Answer 1

Этот код является хвостово-рекурсивным, и в какой-то момент имеет смысл, что компьютер больше не может делить на 2. Почему он не выдает?

Нет, идея другая: в какой-то момент компьютер все еще может разделить на 2, но результат (e) становится неотличимым от 0 [upd: только в контексте сложения с плавающей точкой - очень хорошо пункт, упомянутый в комментарии] (e + 1.0 = 1.0, это именно то, что проверяет предложение if). Мы точно знаем, что предыдущий e все еще был больше нуля «с точки зрения машины» (иначе мы бы не добрались до текущей точки выполнения), поэтому мы просто возвращаем e*2.

Answer 2

Цель этого кода - , а не , чтобы найти наименьшее число с плавающей точкой, которое может поддерживать машина: это найти наименьшее число с плавающей точкой, epsilon такое, что (= (+ 1.0 epsilon) 1.0) является ложным. Это число полезно, потому что это верхняя граница ошибки, которую вы получаете при добавлении чисел. В частности, вы знаете, что, скажем, (+ x y) находится в диапазоне [(x + y) * (1 - epsilon), (x + y) * (1 + epsilon)], где во втором выражении + & c означают идеальные операции над числами.

В частности, (/ *machine-epsilon* 2) является совершенно точным числом, как и (/ *machine-epsilon* 10000) например, и (* (/ *machine-epsilon* x) x) будет очень близко к *machine-epsilon* для многих разумных значений x. Это просто тот случай, когда (= (+ (/ *machine-epsilon* 2) 1.0) 1.0) соответствует действительности.

Я недостаточно знаком со стандартами с плавающей точкой, но число, о котором вы, вероятно, думаете, это то, что Common Lisp называет least-positive-double-float (или его варианты) , В Racket вы можете получить некоторое приближение к этому с помощью

(define *least-positive-mumble-float*
  ;; I don't know what float types Racket has if it even has more than one.
  (let loop ([t 1.0])
    (if (= (/ t 2) 0.0)
        t
        (loop (/ t 2)))))

Я не уверен, разрешено ли это вызывать исключение: на практике это не так, и он получает разумный ответ.

Answer 3

Эта форма let-привязки является синтактическим c сахаром для рекурсии.

Вы можете избегать использования слишком большого количества синтаксиса, пока не овладеете языком и не будете писать как можно больше, используя язык ядра, чтобы сосредоточиться на существенной проблеме. Например, в полном тексте SICP никогда не указывается этот синтаксис c sugar для итерации.

Определение r6rs для итерации: здесь .

Answer 4

Это становится понятнее, когда вы избавляетесь от запутанной именованной нотации let.

(define (calculate-epsilon (epsilon 1.0))
  (if (= 1.0 (+ 1.0 epsilon))
      (* epsilon 2)
      (calculate-epsilon (/ epsilon 2))))

(define *machine-epsilon* (calculate-epsilon))

Это то, что код делает на самом деле. Итак, теперь мы видим, для чего хорошо названное выражение let. Он определяет локально функцию и запускает ее. Просто то, что название функции loop было очень неточным и запутанным, а присвоение имени epsilon e - очень неудачный выбор. Именование - это самая важная вещь для читаемого кода.

Таким образом, этот пример SICP должен служить примером неправильного выбора имен. (Хорошо, возможно, они сделали это намеренно, чтобы обучить студентов).

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