Quando um programa “entrelaça definição e uso”?

Question

A nota de rodapé nº 28 do SICP diz o seguinte:

As definições incorporadas devem vir primeiro em um corpo de procedimento. A gerência não se responsabiliza pelas consequências da execução de programas que entrelaçam definição e uso.

O que exatamente isso significa? Compreendo:

• " definições " para se referir às criações de procedimentos e atribuições de valores.
• " um corpo de procedimento ", conforme definido na seção 1.1.4 . É o código que vem depois da lista de parâmetros na definição de um procedimento.
• " Definições incorporadas devem vir primeiro em um corpo de procedimento " para significar ' quaisquer definições que são feitas e usadas no corpo de um procedimento devem vir antes de qualquer outra coisa '.
• " entrelaçar definição e uso " para significar ' chamar um procedimento ou valor atribuído antes de ter sido definido ;'

No entanto, esse entendimento parece contradizer as respostas a esta pergunta , que tem respostas que posso resumir como ' o erro ao qual sua citação se refere é sobre o uso de definições no início do corpo de um procedimento que dependem de definições que também estão no início desse corpo '. Isso me deixou triplamente confuso:

1. Essa interpretação contradiz claramente o que eu disse acima, mas parece ter fortes evidências - regras do compilador - por trás disso.
2. SICP parece feliz em colocar definição em um corpo com outras definições que as usam. Basta olhar para o sqrtprocedimento logo acima da nota de rodapé !
3. À primeira vista, parece-me que o verdadeiro erro do autor da pergunta vinculada foi tratar num-prodcomo um valor em sua definição de nume não como um procedimento. No entanto, o autor claramente fez com que funcionasse, então provavelmente estou errado.

Então, o que realmente está acontecendo? Onde está o mal-entendido?

Answer 1

Na definição / código de um determinado procedimento,

• "definições internas" são formulários que começam com define.
• "um corpo de procedimento" são todos os outros formulários após os formulários que começam com define.
• "definições embutidas devem vir primeiro em um corpo de procedimento" significa que todos os defineformulários internos devem ir primeiro, depois todos os outros formulários internos. Uma vez que um defineformulário não interno aparece, não pode aparecer um defineformulário interno depois disso.
• "nenhum uso entrelaçado" significa nenhum uso de qualquer nome antes de ser definido. Imagine que todas as defineformas internas são reunidas em um equivalente letrece seguem suas regras.

Ou seja, nós temos,

(define (proc args ...)
   ;; internal, or "embedded", definitions
   (define a1 ...init1...)
   (define a2 ...init2...)
   ......
   (define an ...initn...)
   ;; procedure body
   exp1 exp2 .... )

Any pode ser usado em qualquer uma das expressões, mas apenas dentro de uma expressão lambda. ^(*) Caso contrário, se referiria ao valor de while está sendo definido, e isso é proibido, pois quaisquer nomes são considerados ainda não definidos enquanto qualquer uma das expressões está sendo avaliada.aiinitjaiajaiinitj

---

^(*) Lembre-se que (define (foo x) ...x...)é o mesmo que (define foo (lambda (x) ...x...)). É por isso que as definições nesse sqrtprocedimento no livro que você menciona estão OK - são todas lambdaexpressões, e qualquer uso de nome dentro de uma expressão lambda só irá realmente se referir ao valor desse nome quando o valor da expressão lambda - uma função lambda - ser chamada, não quando aquela expressão lambda está sendo avaliada, produzindo aquela função lambda que é seu valor.

---

O livro é um pouco vago no início com a semântica precisa de sua linguagem, mas no Scheme o código acima é equivalente a

(define proc 
   (lambda (args ...)
      ;; internal, or "embedded", definitions
      (letrec ( (a1 ...init1...)
                (a2 ...init2...)
                ......
                (an ...initn...) )
        ;; procedure body
        exp1 exp2 .... 
        )))

como pode ser visto explicado, por exemplo, aqui , aqui ou aqui .

---

Por exemplo,

                                   ;; or, equivalently,
(define (my-proc x)                (define my-proc
                                     (lambda (x)
   (define (foo) a)                     (letrec ( (foo (lambda () a))
   (define a x)                                   (a x) )
   ;; my-proc's body                       ;; letrec's body
   (foo))                                  (foo))))

primeiro avalia a expressão lambda,, (lambda () a)e associa o nome fooao resultado, uma função; essa função se referirá ao valor de a quando (foo)será chamada , então está tudo bem que haja uma referência a adentro dessa expressão lambda - porque quando essa expressão lambda é avaliada, nenhum valor de aé imediatamente necessário, apenas a referência ao seu valor futuro , sob o nome a, está presente lá; ou seja, o valor que a terá depois de todos os nomes em que letrecforem inicializados e o corpo de letrecfor inserido. Ou seja, quando todos os defines internos forem completados e o corpo próprio do procedimento my-procfor inserido.

Portanto, vemos que fooestá definido, mas não é usado durante as inicializações; aé definido, mas não é usado durante as inicializações; portanto, está tudo bem. Mas se tivéssemos

(define (my-proc x)
   (define (foo) x)    ; `foo` is defined as a function
   (define a (foo))    ; `foo` is used by being called as a function
   a)

então aqui fooé definido e usado durante as inicializações do interno, ou "incorporado", defines; isso é proibido no Scheme. É sobre isso que o livro está alertando: as definições internas só são permitidas para definir coisas, mas seu uso deve ser adiado para depois, quando terminarmos com os se internos definee entrarmos no corpo completo do procedimento.

Answer 2

Isso é sutil e, como a nota de rodapé e a pergunta que você faz referência implicam, as sutilezas podem variar dependendo da implementação de uma linguagem específica.

Essas questões serão abordadas com muito mais detalhes posteriormente no livro (Capítulos 3 e 4) e, geralmente, o texto evita o uso de definições internas para que essas questões possam ser evitadas até que sejam examinadas em detalhes.

Uma diferença fundamental entre o código acima da nota de rodapé:

(define (sqrt x)
  (define (good-enough? guess)
    (< (abs (- (square guess) x)) 0.001))
  (define (improve guess)
    (average guess (/ x guess)))
  (define (sqrt-iter guess)
    (if (good-enough? guess)
        guess
        (sqrt-iter (improve guess))))
  (sqrt-iter 1.0))

e o código na outra pergunta:

(define (pi-approx n)
  (define (square x) (* x x))

  (define (num-prod ind) (* (* 2 ind) (* 2 (+ ind 1)))) ; calculates the product in the numerator for a certain term
  (define (denom-prod ind) (square (+ (* ind 2 ) 1))) ;Denominator product at index ind

  (define num (product num-prod 1 inc n))
  (define denom (product denom-prod 1 inc n))

é que todas as definições no primeiro são definições de procedimento , enquanto nume denomsão definições de valor . O corpo de um procedimento não é avaliado até que o procedimento seja chamado. Mas uma definição de valor é avaliada quando o valor é atribuído.

Com uma definição de valor:

(define sum (add 2 2))

(add 2 2)será avaliado quando a definição for avaliada, se assim for, addjá deve estar definido. Mas com uma definição de procedimento:

(define (sum n m) (add n m))

um objeto de procedimento será atribuído, summas o corpo do procedimento ainda não foi avaliado, portanto add, não precisa ser definido quando sumé definido, mas deve ser na hora em que sumé chamado:

(sum 2 2)

Como eu disse, há muito sublty e muita variação, então não tenho certeza se o seguinte é sempre verdadeiro para todas as variações de esquema, mas dentro do 'esquema SICP' você pode dizer ...

Válido (ordem de avaliação de defines não significativo):

;procedure body
(define (sum m n) (add m n))
(define (add m n) (+ m n))
(sum 2 2)

Também válido:

;procedure body
(define (sum) (add 2 2))
(define (add m n) (+ m n))
(sum)

Normalmente inválido (a ordem de avaliação de defines é significativa):

;procedure body
(define sum (add 2 2))
(define (add m n) (+ m n))

Se o seguinte é válido depende da implementação:

;procedure body
(define (add m n) (+ m n))
(define sum (add 2 2))

E, finalmente, um exemplo de definição e uso do entrelaçamento , se isso funciona também depende da implementação. IIRC, isso funcionaria com o Scheme descrito no Capítulo 4 do livro se a digitalização tiver sido implementada.

;procedure body
(sum)
(define (sum) (add 2 2))
(define (add m n) (+ m n))

É complicado e sutil, mas os pontos principais são:

1. as definições de valor são avaliadas de forma diferente das definições de procedimento,
2. o comportamento dentro dos blocos pode ser diferente dos blocos externos,
3. há variação entre as implementações do esquema,
4. o livro foi projetado para que você não precise se preocupar muito com isso até o Capítulo 3,
5. o livro cobrirá isso em detalhes no Capítulo 4.

Answer 3

Você descobriu uma das dificuldades do esquema. E de ceceio. Devido a esse tipo de questão do ovo e da galinha, não existe um único ceceio, mas apareceram muitos ceceios.

Se os formulários de ligação não estiverem presentes no código em uma letrec-logic em R5RS e letrec*-logic em R6RS, a semântica é indefinida . Ou seja, tudo depende da vontade do implementador do esquema.

Veja o artigo Fixing Letrec: A Faithful Mas Efficient Implementation of Scheme's Recursive Binding Construct .

Além disso, você pode ler as discussões da lista de discussão de 1986 , quando não havia consenso geral entre os diferentes implementadores do esquema.

Além disso, no MIT foram desenvolvidas 2 versões de esquema - a versão do aluno e a versão de desenvolvimento dos pesquisadores, e eles se comportaram de forma diferente quanto à ordem dos defineformulários.