Проблема с круговым определением в схеме - PullRequest
Новая
       30

Проблема с круговым определением в схеме

2 голосов
/ 13 мая 2010

В настоящее время я работаю через SICP, используя Guile в качестве основного языка для упражнений. Я обнаружил странное поведение при выполнении упражнений в главе 3.5. Я воспроизвел это поведение, используя Guile 1.4, Guile 1.8.6 и Guile 1.8.7 на различных платформах, и я уверен, что это не относится к моим настройкам.

Этот код работает нормально (и вычисляет e): 

  (define y (integral (delay dy) 1 0.001))
  (define dy (stream-map (lambda (x) x) y))
  (stream-ref y 1000)

Следующий код должен дать идентичный результат: 

  (define (solve f y0 dt)
    (define y (integral (delay dy) y0 dt))
    (define dy (stream-map f y))
    y)
  (stream-ref (solve (lambda (x) x) 1 0.001) 1000)

Но выдает сообщение об ошибке: 

standard input:7:14: While evaluating arguments to stream-map in expression (stream-map f y):
standard input:7:14: Unbound variable:
y ABORT: (unbound-variable)

Таким образом, при внедрении в определение процедуры (define y ...) не работает, в то время как вне процедуры в глобальной среде в REPL она работает нормально.

Что я здесь не так делаю? При необходимости я также могу опубликовать вспомогательный код (то есть определения интеграла, карту потоков и т. Д.). За исключением системно-зависимого кода для cons-stream, все они в книге. Моя собственная реализация cons-stream для Guile выглядит следующим образом: 

(define-macro (cons-stream a b)
  `(cons ,a (delay ,b)))

Ответы [ 3 ]

2 голосов
/ 14 мая 2010

У вас не может быть внутренних DEFINE, которые зависят друг от друга; спецификация языка прямо заявляет это (R5RS 5.2.2):

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

Вы можете думать об этом, как будто переводчик собирает все ОПРЕДЕЛЕНИЯ и оценивает их перед телом в случайном порядке. Поскольку порядок является случайным, не должно быть никаких взаимозависимостей, если вы ожидаете, что он будет работать.

К определению SOLVE (# 71) даже добавлена ​​сноска, в которой говорится, что она не будет работать на всех схемах.

Вы должны написать код так, чтобы одно определение очень четко входило в сферу действия другого, как для вложенных LET: 

(define (solve f y0 dt)
  (let ((y (integral (delay dy) y0 dt)))
    (let ((dy (stream-map f y)))
      y)))
1 голос
/ 14 мая 2010

Ключевое различие между тем, что происходит, когда вы оцениваете определения одно за другим в REPL, и когда вы помещаете их в solve, заключается в том, что в первом случае они оцениваются последовательно, поэтому y выражается (stream-map <some-function> y) относится к уже в области, тогда как с внутренними определениями или letrec, это еще не доступно.

Как ни странно, схема MIT, которую я использовал при прохождении через SICP, не имела такой проблемы в то время и до сих пор обрабатывает letrec, а внутренняя определяет по-другому: 

;; this is an error
(letrec ((xs '(1 2 3)) (ys (map (lambda (x) (+ x 1)) xs))) ys)

;; this is still an error (and is treated as such by Guile),
;; yet evaluates to (2 3 4) in MIT Scheme
(let () (define xs '(1 2 3)) (define ys (map (lambda (x) (+ x 1)) xs)) ys)

Я не уверен насчет оригинального «Пересмотренного отчета об алгоритмической языковой схеме» или R2RS, но, по крайней мере, из R3RS по внутренним определениям должны были быть эквивалентны letrec. Очевидно, эта особенность среды MIT повлияла на книгу ... или, может быть, все наоборот.

0 голосов
/ 15 мая 2010

Следуя идее в комментариях (ссылаясь на цитату из R5RS 4.2.2), я теперь обернул определения "y" и "dy" в (lambda () ...) s: 

  (define (solve f y0 dt)
    (define (y) (integral (delay (dy)) y0 dt))
    (define (dy) (stream-map f (y)))
    (y))

Это гарантирует, что часть <init> каждого определения может быть оценена без обращения к циклически определенным переменным, поскольку определения являются процедурами, а не выражениями с другими переменными, как в исходном случае.

Теперь код, конечно, намного медленнее (поскольку функции будут упакованы рекурсивно), и размер стека необходимо увеличить, но следующее работает и дает правильный результат: 

  (debug-set! stack 2000000)
  (stream-ref (solve (lambda (x) x) 1 0.001) 1000)

В аналогичной модификации пример кода Михала работает, как только определяются процедуры, а не переменные: 

  (let ()
    (define (xs) '(1 2 3))
    (define (ys) (map (lambda (x) (+ x 1)) (xs)))
    (ys))

работает на Guile 1.8.6.

...