haskell - evaluacion perezosa python

Extraña evaluación perezosa de GHCi

Question

Defino dos listas recursivas para números pares e impares en ghci de la siguiente manera:

> let evens = 0:map (+1) odds; odds = map (+1) evens

Y luego consulto a los thunks usando :sp

> :sp evens
evens = _
> :sp odds
odds = _
> take 5 evens
[0,2,4,6,8]
> :sp evens
evens = 0 : 2 : 4 : 6 : 8 : _
:sp odds
odds = _

Observe cómo las odds thunk no se evalúan, aunque los evens se han evaluado para el quinto elemento. Puedo pensar en una explicación intuitiva para esto. odds deben ser invocadas explícitamente para ser evaluadas:

> take 5 odds
[1,3,5,7,9]
>:sp odds
odds = 1 : 3 : 5 : 7 : 9 : _

Sin embargo, ahora cuando hago esto:

> take 10 evens
[0,2,4,6,8,10,12,14,16,18]
> :sp evens
evens = 0 : 2 : 4 : 6 : 8 : 10 : 12 : 14 : 16 : 18 : _
> :sp odds
odds = 1 : 3 : 5 : 7 : 9 : 11 : 13 : 15 : 17 : _

¿Observe cómo las odds se evalúan ahora cada vez que se evalúan los evens ? ¿Por qué no se evaluaron las odds la primera vez y se evaluaron la segunda vez y en todas las evaluaciones posteriores? ¿Qué esta pasando?

Answer 1

Esto tiene que ver con la forma en que GHC compila los enlaces recursivos recíprocos (y hay una diferencia entre si los enlaces tienen una firma de tipo explícita o no).

Escribamos el siguiente programa simple que expone el mismo problema pero elimina toda sospecha sobre el papel que podría desempeñar la sobrecarga de enteros o la restricción de monomorfismo:

module MutRec where
ft = False : map not tf
tf = map not ft

Cargando esto en GHCi (estoy usando 7.6.3) produce:

*MutRec> take 5 ft
[False,False,False,False,False]
*MutRec> :sp ft
ft = False : False : False : False : False : _
*MutRec> :sp tf
tf = _

Veamos el código Core para este módulo.

$ ghc -O0 MutRec -fforce-recomp -ddump-simpl -dsuppress-all
[1 of 1] Compiling MutRec ( MutRec.hs, MutRec.o )
==================== Tidy Core ====================
Result size of Tidy Core = {terms: 28, types: 42, coercions: 0}
Rec {
ft1_rkA
ft1_rkA = : False a_rkC
tf1_rkB
tf1_rkB = map not ft1_rkA
a_rkC
a_rkC = map not tf1_rkB
end Rec }
ds_rkD
ds_rkD = (ft1_rkA, tf1_rkB)
ft
ft = case ds_rkD of _ { (ft2_Xkp, tf2_Xkr) -> ft2_Xkp }
tf
tf = case ds_rkD of _ { (ft2_Xkq, tf2_Xks) -> tf2_Xks }

Esto lo explica todo. Las definiciones recursivas entre sí terminan en un bloque de Rec , refiriéndose entre sí directamente. Pero entonces GHC está construyendo un par ds_rkD y vuelve a extraer los componentes del par. Esto es una indirección extra. Explica por qué, después de evaluar parcialmente el ft en GHCi, la parte superior de tf todavía aparecerá como un procesador, incluso si debajo se ha realizado una evaluación. De hecho, podemos verificar que solo hacer una evaluación mínima en tf es suficiente para exponer esto:

*MutRec> take 5 ft
[False,False,False,False,False]
*MutRec> :sp ft
ft = False : False : False : False : False : _
*MutRec> :sp tf
tf = _
Prelude MutRec> seq tf ()
()
Prelude MutRec> :sp tf
tf = True : True : True : True : _

Si agregamos sigantures de tipo explícito a ft y tf o habilitamos la optimización, la construcción de la tupla no ocurre:

$ ghc -O MutRec -fforce-recomp -ddump-simpl -dsuppress-all
[1 of 1] Compiling MutRec ( MutRec.hs, MutRec.o )
==================== Tidy Core ====================
Result size of Tidy Core = {terms: 12, types: 11, coercions: 0}
Rec {
ft1
ft1 = map not tf
ft
ft = : False ft1
tf
tf = map not ft
end Rec }

Ahora GHCi se comportará más naturalmente.

Editar

He mirado las fuentes de GHC para tratar de averiguar la razón de la diferencia en el comportamiento. Parece que es un efecto secundario de cómo funciona la inferencia de tipos para los enlaces polimórficos.

Si una unión es polimórfica pero no tiene una firma de tipo, entonces sus usos recursivos son monomorfos. Esta es una restricción en Hindley-Milner que también implementa GHC. Si desea una recursión polimórfica, necesita una firma de tipo adicional.

Para modelar esto fielmente en el lenguaje Core, el analizador crea una copia monomórfica de cada función recursiva sin anotar. Esta versión monomórfica se usa en las llamadas recursivas, la versión generalizada se usa para llamadas externas. Puede ver esto incluso para una función pequeña como rep (que es una reimplementación de la repeat ). El núcleo desugarado para

rep x = x : rep x

es

rep
rep =
/ (@ a_aeM) ->
letrec {
rep_aeJ
rep_aeJ =
/ (x_aeH :: a_aeM) -> : @ a_aeM x_aeH (rep_aeJ x_aeH); } in
rep_aeJ

El rep externo es polimórfico, de ahí el tipo abstracción / (@ a_aeM) -> al principio. El rep_aeJ interno es monomórfico y se usa en la llamada recursiva.

Si agrega una anotación de tipo explícita a rep

rep :: a -> [a]
rep x = x : rep x

entonces las llamadas recursivas son a la versión polimórfica, y el Core generado se vuelve más simple:

Rec {
rep
rep = / (@ a_b) (x_aeH :: a_b) -> : @ a_b x_aeH (rep @ a_b x_aeH)
end Rec }

Puede ver cómo el argumento de tipo @ a_b se recoge al principio y se vuelve a aplicar a rep en cada llamada recursiva.

La construcción de la tupla que estamos viendo para los enlaces recursivos mutuos es simplemente una generalización de este principio. Usted construye versiones monomórficas internas de las funciones recursivas mutuas, luego las generaliza en una tupla y extrae las versiones polimórficas de la tupla.

Todo esto sucede independientemente de si los enlaces son en realidad polimórficos o no. Es suficiente que sean recursivos. Creo que este comportamiento de GHC es completamente correcto y está bien, en particular porque la optimización se encarga del impacto del rendimiento.