exercicio 1.5
Adriano Ogata
Estou com dúvida na questão 1.5. É perguntado o comportamento do
interpretador ao avaliar:
(test 0 (p))
Há duas possibilidades de comportamento, conforme o tipo de avaliação:
normal order: ``fully expand and then reduce''
applicative order: ``evaluate the arguments and then apply''
A 'normal order' expandiria até a expressão só conter operadores
primitivos. Como (p) é definido recursivamente, eu esperaria então que
um interpretador que utilizasse 'normal order' ficasse travado ao
expandir (p).
Já usando avaliação 'applicative' isso não aconteceria pois (p) nunca
é necessária, evitando o travamento.
Seria isso?
Og!
Andrei Formiga
>
> Fala pessoal,
>
>
> Estou com dúvida na questão 1.5. É perguntado o comportamento do
> interpretador ao avaliar:
>
> (test 0 (p))
>
> Há duas possibilidades de comportamento, conforme o tipo de avaliação:
>
> normal order: ``fully expand and then reduce''
> applicative order: ``evaluate the arguments and then apply''
>
> A 'normal order' expandiria até a expressão só conter operadores
> primitivos. Como (p) é definido recursivamente, eu esperaria então que
> um interpretador que utilizasse 'normal order' ficasse travado ao
> expandir (p).
"fully expand and then reduce" não significa expandir os argumentos,
nem expandir indefinidamente. Vai expandir a função que está sendo
chamada segundo a definição, e então reduzir, seguindo as regras de
avaliação da linguagem. As definições são:
(define (p) (p))
(define (test x y)
(if (= x 0)
0
y))
então, mostrando a expansão e depois a redução:
(test 0 (p))
=> (if (= 0 0)
0
(p)) -- expansão de test ; agora acabou a
expansão, hora de reduzir
=> 0 -- redução do if e resultado final da avaliação
Note-se que não foi preciso avaliar os argumentos de test (0 e (p))
então não é feita nenhuma chamada a p.
>
> Já usando avaliação 'applicative' isso não aconteceria pois (p) nunca
> é necessária, evitando o travamento.
Na ordem aplicativa os argumentos devem ser completamente avaliados
antes da chamada à função. Portanto, o interpretador vai obter o valor
de 0 (que é 0), depois vai obter o valor da forma (p); para isso é
preciso chamar a função p. Dá para entender o que acontece daí?
A nota teórica relacionada aqui é o seguinte: a ordem normal é mais
"completa" que a ordem aplicativa, no sentido que, se um termo
(expressão da linguagem) tem um valor final, a ordem normal sempre vai
achar esse valor depois de um número finito de passos de avaliação
(redução); já na ordem aplicativa, termos que têm um valor final podem
resultar em loops infinitos, como neste caso. Isso é provado em
qualquer livro sobre o lambda-calculus.
Entretanto, por questões de desempenho, a maioria das linguagens
adotou avaliação aplicativa. Haskell é uma linguagem que usa avaliação
'lazy', que é quase a mesma coisa que avaliação em ordem normal.
--
[]s, Andrei Formiga
Adriano Ogata
>> A 'normal order' expandiria até a expressão só conter operadores
>> primitivos. Como (p) é definido recursivamente, eu esperaria então que
>> um interpretador que utilizasse 'normal order' ficasse travado ao
>> expandir (p).
>
> "fully expand and then reduce" não significa expandir os argumentos,
> nem expandir indefinidamente. Vai expandir a função que está sendo
> chamada segundo a definição, e então reduzir, seguindo as regras de
> avaliação da linguagem.
Hm... certo. Foi aí que me confundi.
> As definições são:
>
> (define (p) (p))
>
> (define (test x y)
> (if (= x 0)
> 0
> y))
>
> então, mostrando a expansão e depois a redução:
>
> (test 0 (p))
> => (if (= 0 0)
> 0
> (p)) -- expansão de test ; agora acabou a
> expansão, hora de reduzir
>
> => 0 -- redução do if e resultado final da avaliação
>
> Note-se que não foi preciso avaliar os argumentos de test (0 e (p))
> então não é feita nenhuma chamada a p.
>
>>
>> Já usando avaliação 'applicative' isso não aconteceria pois (p) nunca
>> é necessária, evitando o travamento.
>
> Na ordem aplicativa os argumentos devem ser completamente avaliados
> antes da chamada à função. Portanto, o interpretador vai obter o valor
> de 0 (que é 0), depois vai obter o valor da forma (p); para isso é
> preciso chamar a função p. Dá para entender o que acontece daí?
Legal, agora entendi. Andrei, valeu pelas explicações e informações.
Bueno, voltar pro sicp... /o/
Og!
Luciano Ramalho
propor uma outra forma de entendê-la:
Dá uma olhada no PDF de um slide que eu publiquei ontem na área de
arquivos do grupo [1]. Daí experimente fazer o mesmo trabalho com as
definições do exercício 1.5, ou seja, escrever lado a lado como seria
a avaliação aplicativa e a avaliação normal das expressões.
[1] http://groups.google.com/group/eipc/files
[ ]s
Luciano
Adriano Ogata
> arquivos do grupo [1]. Daí experimente fazer o mesmo trabalho com as
> definições do exercício 1.5, ou seja, escrever lado a lado como seria
> a avaliação aplicativa e a avaliação normal das expressões.
>
> [1] http://groups.google.com/group/eipc/files
Legal Ramalho, mais explícito só desenhando. Ainda não posso dizer que
entendi 100%, mas tou quase lá... ainda preciso amadurecer as idéias.
Og!