Tema 10: Evaluación perezosa

Librerías auxiliares

import Test.QuickCheck
import Data.List

1 Estrategias de evaluación

Estrategias de evaluación

mult :: (Int,Int) -> Int
mult (x,y) = x*y 
mult (1+2,2+3)                        
= mult (3,5)        [por def. de +]    
= 3*5               [por def. de mult] 
= 15                [por def. de *]
mult (1+2,2+3)
= (1+2)*(3+5)       [por def. de mult] 
= 3*5               [por def. de +] 
= 15                [por def. de *]

Evaluación con lambda expresiones

mult' :: Int -> Int -> Int
mult' x = \y -> x*y  
mult' (1+2) (2+3) 
= mult' 3 (2+3)      [por def. de +] 
= (\y -> 3*y) (2+3)  [por def. de mult'] 
= (\y -> 3*y) 5      [por def. de +] 
= 3*5                [por def. de +] 
= 15                 [por def. de *]

2 Terminación

Procesamiento con el infinito

inf :: Int
inf = 1 + inf
ghci> inf
  C-c C-c Interrupted.
inf 
= 1 + inf             [por def. inf] 
= 1 + (1 + inf)       [por def. inf] 
= 1 + (1 + (1 + inf)) [por def. inf] 
= ...

Procesamiento con el infinito

fst (0,inf) 
= fst (0,1 + inf)             [por def. inf] 
= fst (0,1 + (1 + inf))       [por def. inf] 
= fst (0,1 + (1 + (1 + inf))) [por def. inf] 
= ...
fst (0,inf) 
= 0           [por def. fst]
ghci> fst (0,inf)
0

3 Número de reducciones

Número de reducciones según las estrategias

cuadrado :: Int -> Int
cuadrado n = n * n
cuadrado (1+2) 
= cuadrado 3      [por def. +] 
= 3*3             [por def. cuadrado] 
= 9               [por def. de *] 
cuadrado (1+2) 
= (1+2)*(1+2)        [por def. cuadrado] 
= 3*(1+2)            [por def. de +] 
= 3*3                [por def. de +] 
= 9                  [por def. de *] 

Evaluación perezosa e impaciente

cuadrado (1+2) 
= x*x con x = 1+2      [por def. cuadrado] 
= 3*3                  [por def. de +] 
= 9                    [por def. de *] 

4 Estructuras infinitas

Programación con estructuras infinitas

unos :: [Int]
unos = 1 : unos  
unos 
= 1 : unos                [por def. unos] 
= 1 : (1 : unos)          [por def. unos] 
= 1 : (1 : (1 : unos))    [por def. unos] 
= ...
ghci> unos
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,...

Evaluación con estructuras infinitas

head unos 
= head (1 : unos)                [por def. unos] 
= head (1 : (1 : unos))          [por def. unos] 
= head (1 : (1 : (1 : unos)))    [por def. unos] 
= ...
head unos 
= head (1 : unos)   [por def. unos] 
= 1                 [por def. head]
ghci> head unos
1

5 Programación modular

Programación modular

take :: Int -> [a] -> [a]
take n _  | n <= 0  = []
take _ []           = []
take n (x:xs)       = x : take (n-1) xs
take 2 unos 
= take 2 (1 : unos)         [por def. unos] 
= 1 : (take 1 unos)         [por def. take] 
= 1 : (take 1 (1 : unos))   [por def. unos] 
= 1 : (1 : (take 0 unos))   [por def. take] 
= 1 : (1 : [])              [por def. take] 
= [1,1]                     [por notación de listas]

Terminación de evaluaciones con estructuras infinitas

ghci> [1..]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,...
ghci> take 3 [1..]
[1,2,3]
ghci> filter (<=3) [1..]
[1,2,3  C-c C-c Interrupted.
ghci> takeWhile (<=3) [1..]
[1,2,3]

La criba de Erastótenes

2 3 4 5 6 7 8 9 10 11 12 13 14 15 ... 3 5 7 9 11 13 15 ... 5 7 11 13 ... 7 11 13 ... 11 13 ... 13 ...

primos :: [Int ]
primos = criba [2..]

criba :: [Int] -> [Int]
criba (p:xs) = p : criba [x | x <- xs, x `mod` p /= 0]
take 15 primos == [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]  
primos
= criba [2..]      
= criba (2 : [3..])
= 2 : (criba [x | x <- [3..], x `mod` 2 /= 0])
= 2 : (criba (3 : [x | x <- [4..], x `mod` 2 /= 0]))
= 2 : 3 : (criba [x | x <- [4..], x `mod` 2 /= 0, 
                                  x `mod` 3 /= 0])
= 2 : 3 : (criba (5 : [x | x <- [6..], x `mod` 2 /= 0, 
                                       x `mod` 3 /= 0]))
= 2 : 3 : 5 : (criba ([x | x <- [6..], x `mod` 2 /= 0, 
                                       x `mod` 3 /= 0,
                                       x `mod` 5 /= 0]))
= ...

6 Aplicación estricta

Ejemplo de programa sin aplicación estricta

sumaNE [2,3,5]  ==  10  
sumaNE :: [Int] -> Int
sumaNE xs = sumaNE' 0 xs

sumaNE' :: Int -> [Int] -> Int
sumaNE' v []     = v
sumaNE' v (x:xs) = sumaNE' (v+x) xs
sumaNE [2,3,5] 
= sumaNE' 0 [2,3,5]           [por def. sumaNE] 
= sumaNE' (0+2) [3,5]         [por def. sumaNE'] 
= sumaNE' ((0+2)+3) [5]       [por def. sumaNE'] 
= sumaNE' (((0+2)+3)+5) []    [por def. sumaNE'] 
= ((0+2)+3)+5                 [por def. sumaNE'] 
= (2+3)+5                     [por def. +] 
= 5+5                         [por def. +] 
= 10                          [por def. +]

Ejemplo de programa con aplicación estricta

sumaE [2,3,5]  ==  10  
sumaE :: [Int] -> Int
sumaE xs = sumaE' 0 xs

sumaE' :: Int -> [Int] -> Int
sumaE' v []     = v
sumaE' v (x:xs) = (sumaE' $! (v+x)) xs
sumaE [2,3,5] 
= sumaE' 0 [2,3,5]          [por def. sumaE] 
= (sumaE' \$! (0+2)) [3,5]  [por def. sumaE'] 
= sumaE' 2 [3,5]            [por aplicación de \$!] 
= (sumaE' \$! (2+3)) [5]    [por def. sumaE'] 
= sumaE' 5 [5]              [por aplicación de \$!] 
= (sumaE' \$! (5+5)) []     [por def. sumaE'] 
= sumaE' 10 []              [por aplicación de \$!] 
= 10                        [por def. sumaE'] 

Comparación de consumo de memoria

ghci> sumaNE [1..1000000]
*** Exception: stack overflow
ghci> sumaE [1..1000000]
1784293664
ghci> :set +s
ghci> sumaE [1..1000000]
1784293664
(2.16 secs, 145435772 bytes)

Plegado estricto

foldl' :: (a -> b -> a) -> a -> [b] -> a
foldl' f a []     = a
foldl' f a (x:xs) = (foldl' f $! f a x) xs
ghci> foldl (+) 0 [2,3,5]
10
ghci> foldl' (+) 0 [2,3,5]
10
ghci> foldl (+) 0 [1..1000000]
*** Exception: stack overflow
ghci> foldl' (+) 0 [1..1000000]
500000500000

7 Bibliografía



Universidad de Sevilla

José A. Alonso Jiménez
Grupo de Lógica Computacional
Dpto. de Ciencias de la Computación e I.A.
Universidad de Sevilla