Проблема с интерпретатором SICP 1.25

1) DrRacket

2) https://inst.eecs.berkeley.edu/~cs61a/sp15/assets/interpreter/scheme.html

Использование обоих интерпретаторов выше для версии Хакера с аргументами (expmod 11 17 17) дает разные ответы. 11 для DrRacket (в соответствии с процедурой) и 0 для inst.eecs.berkeley.edu

Внизу включен пример оценки. Подстановка всех (< base m) в оба интерпретатора дает разные ответы при использовании inst.eecs.berkeley.edu и, следовательно, приводит к сбою всего timed-prime-test для этого интерпретатора.

Мой вопрос: в чем заключается основная проблема этого интерпретатора? Это проблема из-за ошибки в интерпретации? Другой метод оценки между ними?

(define (expmod base exp m)
  (remainder (fast-expt base exp) m))
(define (fast-expt b n)
  (cond ((= n 0) 1)
        ((even? n) (square (fast-expt b (/ n 2))))
        (else (* b (fast-expt b (- n 1))))))
(define (even? n)
  (= (remainder n 2) 0))
(define (square x)
  (* x x))

(remainder (fast-expt 11 17) 17)
(remainder (* 11 (fast-expt 11 16)) 17)
(remainder (* 11 (square (fast-expt 11 8))) 17)
(remainder (* 11 (square (square (fast-expt 11 4)))) 17)
(remainder (* 11 (square (square (square (fast-expt 11 2))))) 17)
(remainder (* 11 (square (square (square (square (fast-expt 11 1)))))) 17)
(remainder (* 11 (square (square (square (square (* 11 (fast-expt 11 0))))))) 17)
(remainder (* 11 (square (square (square (square (* 11 1)))))) 17)
(remainder (* 11 (square (square (square (square 11))))) 17)
(remainder (* 11 (square (square (square 121)))) 17)
(remainder (* 11 (square (square 14641))) 17)
(remainder (* 11 (square 214358881)) 17)
(remainder (* 11 45949729863572161) 17)
(remainder 505447028499293771 17)

Ссылка на онлайн-SICP

https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book-Z-H-11.html#call_footnote_Temp_78

Обратите внимание, что expmod сначала вычисляет мощность p=base^exp, а затем находит модуль. Это означает, что временный результат p может быть очень большим. Настолько велик, что не может быть точно представлен с помощью чисел с плавающей запятой. Вместо этого вы должны написать вариант вашего fast-expt, который вычисляет по модулю каждого временного результата. Таким образом, все числа в вычислении будут ниже модуля - и вы получите правильный результат также в реализации схемы Беркли.

soegaard 04.08.2018 21:40
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
1
1
79
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Таким образом, хотя DrRacket имеет Язык SICP, где должен работать код SICP, язык Racket по умолчанию несовместим со Scheme. Это близко, так что у этих двух языков больше общего, чем у Java и C#, но их следует признать разными языками. Racket поддерживает Scheme. И #!r5rs, и #!r6rs.

Ваш онлайн-переводчик может иметь только базовую функциональность схемы и, возможно, только числа с плавающей запятой. Только для R7RS требуется полная числовая башня, поэтому большие числа могут стать плавающими. Проведенный мною очень простой тест показал, что число очень быстро стало неточным:

(/ 1 2) ; ==> 0.5

С полной числовой башней ответом будет рациональное точное число 1/2. Оценка call/cc и exact->inexact дала ошибку, поэтому интерпретатор не соответствует требованиям для стандартных отчетов схемы.

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

Другие вопросы по теме