Problema com definição circular no esquema

Question

Atualmente estou trabalhando no SICP usando Guile como idioma principal para os exercícios.Encontrei um comportamento estranho ao implementar os exercícios do capítulo 3.5.Reproduzi esse comportamento usando Guile 1.4, Guile 1.8.6 e Guile 1.8.7 em diversas plataformas e tenho certeza de que não é específico da minha configuração.

Este código funciona bem (e calcula e):

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

O seguinte código deve dê um resultado idêntico:

  (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)

Mas gera a mensagem de erro:

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)

Portanto, quando incorporado em uma definição de procedimento, o (define y ...) não funciona, enquanto fora do procedimento no ambiente global no REPL funciona bem.

O que estou fazendo de errado aqui?Posso postar o código auxiliar (ou seja, as definições de integral, mapa de fluxo etc.), se necessário, também.Com exceção do código dependente do sistema para cons-stream, eles estão todos no livro.Minha própria implementação de cons-stream para Guile é a seguinte:

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

Answer 1

A principal diferença entre o que acontece quando você avalia as definições uma por uma no REPL e quando você as coloca dentro solve é que no primeiro caso eles são avaliados sequencialmente, portanto o y a expressão (stream-map <some-function> y) refere-se já está no escopo, enquanto com definições internas ou letrec, ainda não está disponível.

Curiosamente, o esquema MIT, que usei ao passar pelo SICP, não tinha esse problema naquela época e ainda trata letrec e interno define de forma diferente:

;; 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)

Não tenho certeza sobre o "Relatório revisado sobre esquema de linguagem algorítmica" original ou R2RS, mas pelo menos do R3RS nas definições internas deveriam ser equivalentes a letrec.Aparentemente esta peculiaridade do ambiente do MIT influenciou o livro...ou talvez seja o contrário.

Answer 2

Você não pode ter DEFINEs internos que dependam um do outro;a especificação da linguagem afirma explicitamente isso (R5RS 5.2.2):

...deve ser possível avaliar cada expressão de cada definição interna em um corpo sem atribuir ou referir o valor de qualquer variável sendo definido.

Você pode pensar nisso como se o intérprete estivesse coletando todos os DEFINES e avaliando-os antes do corpo em ordem aleatória.Como a ordem é aleatória, não pode haver interdependências se você espera que funcione.

Há até uma nota de rodapé anexada à definição do SOLVE (#71) que diz que não funcionará em todos os esquemas.

Você tem que escrever o código de forma que uma definição esteja claramente no escopo da outra, como acontece com LETs aninhados:

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

Answer 3

Seguindo a ideia nos comentários (referindo-se à citação do R5RS 4.2.2), agora envolvi as definições de "y" e "dy" em (lambda () ...)é:

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

Isto garante que o <init> parte de cada definição pode ser avaliada sem referência às variáveis ​​circulares definidas, uma vez que as definições são procedimentos e não expressões com outras variáveis ​​como no caso original.

Agora o código é certamente muito mais lento (já que as funções serão agrupadas recursivamente) e o tamanho da pilha precisa ser aumentado, mas o seguinte funciona e produz o resultado correto:

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

---

Com uma modificação semelhante, o código de exemplo de Michał funciona assim que se definem procedimentos em vez de variáveis:

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

funciona no Guile 1.8.6.