{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "\n", " Tema 10: Evaluación perezosa\n", " \n", "\n", "----------\n", "\n", "[José A. Alonso](https://www.cs.us.es/~jalonso) \n", "[Departamento de Ciencias de la Computación e I.A.](https://www.cs.us.es) \n", "[Universidad de Sevilla](http://www.us.es) \n", "Sevilla, 6 de agosto de 2019" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "> __Notas:__ \n", "+ La versión interactiva de este tema se encuentra en [Binder](https://mybinder.org/v2/gh/jaalonso/Temas_interactivos_de_PF_con_Haskell/master?urlpath=lab/tree/temas/Tema-10.ipynb).\n", "+ Se desactiva el [corrector estilo de Haskell](https://github.com/gibiansky/IHaskell/wiki#opt-no-lint)." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ ":opt no-lint" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Librerías auxiliares**\n", "\n", "+ En este tema se usan las siguientes librerías:" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "import Test.QuickCheck\n", "import Data.List" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Estrategias de evaluación\n", "\n", "**Estrategias de evaluación**\n", "\n", "+ Para los ejemplos se considera la función\n", "\n", "> mult :: (Int,Int) -> Int\n", "> mult (x,y) = x*y \n", "\n", "+ Evaluación mediante paso de parámetros por valor (o por más internos):\n", "\n", "```sesion\n", "mult (1+2,2+3) \n", "= mult (3,5) [por def. de +] \n", "= 3*5 [por def. de mult] \n", "= 15 [por def. de *]\n", "```\n", "\n", "+ Evaluación mediante paso de parámetros por nombre (o por más externos):\n", "\n", "```sesion\n", "mult (1+2,2+3)\n", "= (1+2)*(3+5) [por def. de mult] \n", "= 3*5 [por def. de +] \n", "= 15 [por def. de *]\n", "```\n", "\n", "**Evaluación con lambda expresiones**\n", "\n", "+ Se considera la función\n", "\n", "> mult' :: Int -> Int -> Int\n", "> mult' x = \\y -> x*y \n", "\n", "+ Evaluación:\n", "\n", "```sesion\n", "mult' (1+2) (2+3) \n", "= mult' 3 (2+3) [por def. de +] \n", "= (\\y -> 3*y) (2+3) [por def. de mult'] \n", "= (\\y -> 3*y) 5 [por def. de +] \n", "= 3*5 [por def. de +] \n", "= 15 [por def. de *]\n", "```" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Terminación\n", "\n", "**Procesamiento con el infinito**\n", "\n", "+ Definición de infinito" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "inf :: Int\n", "inf = 1 + inf" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "+ Evaluación de infinito en Haskell:\n", "\n", "```sesion\n", "ghci> inf\n", " C-c C-c Interrupted.\n", "```\n", "\n", "+ Evaluación de infinito:\n", "\n", "```sesion\n", "inf \n", "= 1 + inf [por def. inf] \n", "= 1 + (1 + inf) [por def. inf] \n", "= 1 + (1 + (1 + inf)) [por def. inf] \n", "= ...\n", "```\n", "\n", "**Procesamiento con el infinito**\n", "\n", "+ Evaluación mediante paso de parámetros por valor:\n", "\n", "```sesion\n", "fst (0,inf) \n", "= fst (0,1 + inf) [por def. inf] \n", "= fst (0,1 + (1 + inf)) [por def. inf] \n", "= fst (0,1 + (1 + (1 + inf))) [por def. inf] \n", "= ...\n", "```" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "+ Evaluación mediante paso de parámetros por nombre:\n", "\n", "```sesion\n", "fst (0,inf) \n", "= 0 [por def. fst]\n", "```" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "+ Evaluación Haskell con infinito:" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "0" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "fst (0,inf)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Número de reducciones\n", "\n", "**Número de reducciones según las estrategias**\n", "\n", "+ Para los ejemplos se considera la función" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [], "source": [ "cuadrado :: Int -> Int\n", "cuadrado n = n * n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "+ Evaluación mediante paso de parámetros por valor:\n", "\n", "```sesion\n", "cuadrado (1+2) \n", "= cuadrado 3 [por def. +] \n", "= 3*3 [por def. cuadrado] \n", "= 9 [por def. de *] \n", "```\n", "\n", "+ Evaluación mediante paso de parámetros por nombre:\n", "\n", "```sesion\n", "cuadrado (1+2) \n", "= (1+2)*(1+2) [por def. cuadrado] \n", "= 3*(1+2) [por def. de +] \n", "= 3*3 [por def. de +] \n", "= 9 [por def. de *] \n", "```\n", "\n", "**Evaluación perezosa e impaciente**\n", "\n", "\n", "+ En la evaluación mediante paso de parámetros por nombre los argumentos pueden\n", " evaluarse más veces que en el paso por valor.\n", "\n", "+ Se puede usar punteros para compartir valores de expresiones.\n", "\n", "+ La evaluación mediante paso de parámetros por nombre usando punteros para\n", " compartir valores de expresiones se llama *evaluación perezosa*.\n", "\n", "+ La evaluación mediante paso de parámetros por valor se llama *evaluación\n", " impaciente*.\n", "\n", "+ Evaluación perezosa del ejemplo anterior:\n", "\n", "```sesion\n", "cuadrado (1+2) \n", "= x*x con x = 1+2 [por def. cuadrado] \n", "= 3*3 [por def. de +] \n", "= 9 [por def. de *] \n", "```\n", "\n", "+ Haskell usa evaluación perezosa. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Estructuras infinitas\n", "\n", "**Programación con estructuras infinitas**\n", "\n", "+ `unos` es una lista infinita de unos." ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [], "source": [ "unos :: [Int]\n", "unos = 1 : unos " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "+ Evaluación:\n", "\n", "```sesion\n", "unos \n", "= 1 : unos [por def. unos] \n", "= 1 : (1 : unos) [por def. unos] \n", "= 1 : (1 : (1 : unos)) [por def. unos] \n", "= ...\n", "```\n", "\n", "+ Evaluación en Haskell:\n", "\n", "```sesion\n", "ghci> unos\n", "[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,...\n", "```\n", "\n", "**Evaluación con estructuras infinitas**\n", "\n", "+ Evaluación impaciente:\n", "\n", "```sesion\n", "head unos \n", "= head (1 : unos) [por def. unos] \n", "= head (1 : (1 : unos)) [por def. unos] \n", "= head (1 : (1 : (1 : unos))) [por def. unos] \n", "= ...\n", "```\n", "\n", "+ Evaluación perezosa:\n", "\n", "```sesion\n", "head unos \n", "= head (1 : unos) [por def. unos] \n", "= 1 [por def. head]\n", "```\n", "\n", "+ Evaluación Haskell:" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "1" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "head unos" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Programación modular\n", "\n", "+ La evaluación perezosa permite separar el control de los datos.\n", "\n", "+ Para los ejemplos se considera la función\n", "\n", "```haskell\n", "take :: Int -> [a] -> [a]\n", "take n _ | n <= 0 = []\n", "take _ [] = []\n", "take n (x:xs) = x : take (n-1) xs\n", "```\n", "\n", "+ Ejemplo de separación del control (tomar 2 elementos) de los datos (una lista\n", " infinita de unos):\n", "\n", "\n", "```sesion\n", "take 2 unos \n", "= take 2 (1 : unos) [por def. unos] \n", "= 1 : (take 1 unos) [por def. take] \n", "= 1 : (take 1 (1 : unos)) [por def. unos] \n", "= 1 : (1 : (take 0 unos)) [por def. take] \n", "= 1 : (1 : []) [por def. take] \n", "= [1,1] [por notación de listas]\n", "```\n", "\n", "**Terminación de evaluaciones con estructuras infinitas**\n", "\n", "+ Ejemplo de no terminación:\n", "\n", "```sesion\n", "ghci> [1..]\n", "[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,...\n", "```\n", "\n", "+ Ejemplo de terminación:" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1,2,3]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "take 3 [1..]" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "take 20 [1..]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "+ Ejemplo de no terminación:\n", "\n", "```sesion\n", "ghci> filter (<=3) [1..]\n", "[1,2,3 C-c C-c Interrupted.\n", "```\n", "\n", "+ Ejemplo de no terminación:" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1,2,3]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "takeWhile (<=3) [1..]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**La criba de Erastótenes**\n", "\n", "```\n", "2 3 4 5 6 7 8 9 10 11 12 13 14 15 ... \n", " 3 5 7 9 11 13 15 ... \n", " 5 7 11 13 ... \n", " 7 11 13 ... \n", " 11 13 ... \n", " 13 ... \n", "```\n", "\n", "+ Definición" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [], "source": [ "primos :: [Int ]\n", "primos = criba [2..]\n", " \n", "criba :: [Int] -> [Int]\n", "criba (p:xs) = p : criba [x | x <- xs, x `mod` p /= 0]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "+ Evaluación:" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "take 15 primos" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "+ Cálculo:\n", "\n", "```sesion\n", "primos\n", "= criba [2..] \n", "= criba (2 : [3..])\n", "= 2 : (criba [x | x <- [3..], x `mod` 2 /= 0])\n", "= 2 : (criba (3 : [x | x <- [4..], x `mod` 2 /= 0]))\n", "= 2 : 3 : (criba [x | x <- [4..], x `mod` 2 /= 0, \n", " x `mod` 3 /= 0])\n", "= 2 : 3 : (criba (5 : [x | x <- [6..], x `mod` 2 /= 0, \n", " x `mod` 3 /= 0]))\n", "= 2 : 3 : 5 : (criba ([x | x <- [6..], x `mod` 2 /= 0, \n", " x `mod` 3 /= 0,\n", " x `mod` 5 /= 0]))\n", "= ...\n", "```" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Aplicación estricta\n", "\n", "**Ejemplo de programa sin aplicación estricta**\n", "\n", "+ `(sumaNE xs)` es la suma de los números de \\verb|xs|. Por ejemplo,\n", "\n", "```sesion\n", "sumaNE [2,3,5] == 10 \n", "```" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [], "source": [ "sumaNE :: [Int] -> Int\n", "sumaNE xs = sumaNE' 0 xs\n", " \n", "sumaNE' :: Int -> [Int] -> Int\n", "sumaNE' v [] = v\n", "sumaNE' v (x:xs) = sumaNE' (v+x) xs" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "10" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "sumaNE [2,3,5]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "+ Evaluación:\n", "\n", "```sesion\n", "sumaNE [2,3,5] \n", "= sumaNE' 0 [2,3,5] [por def. sumaNE] \n", "= sumaNE' (0+2) [3,5] [por def. sumaNE'] \n", "= sumaNE' ((0+2)+3) [5] [por def. sumaNE'] \n", "= sumaNE' (((0+2)+3)+5) [] [por def. sumaNE'] \n", "= ((0+2)+3)+5 [por def. sumaNE'] \n", "= (2+3)+5 [por def. +] \n", "= 5+5 [por def. +] \n", "= 10 [por def. +]\n", "```\n", "\n", "**Ejemplo de programa con aplicación estricta**\n", "\n", "+ `(sumaE xs)` es la suma de los números de `xs`. Por ejemplo,\n", "\n", "```sesion\n", "sumaNE [2,3,5] == 10 \n", "```" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [], "source": [ "sumaE :: [Int] -> Int\n", "sumaE xs = sumaE' 0 xs\n", " \n", "sumaE' :: Int -> [Int] -> Int\n", "sumaE' v [] = v\n", "sumaE' v (x:xs) = (sumaE' $! (v+x)) xs" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "10" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "sumaNE [2,3,5]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "+ Evaluación:\n", "\n", "```sesion\n", "sumaE [2,3,5] \n", "= sumaE' 0 [2,3,5] [por def. sumaE] \n", "= (sumaE' \\$! (0+2)) [3,5] [por def. sumaE'] \n", "= sumaE' 2 [3,5] [por aplicación de \\$!] \n", "= (sumaE' \\$! (2+3)) [5] [por def. sumaE'] \n", "= sumaE' 5 [5] [por aplicación de \\$!] \n", "= (sumaE' \\$! (5+5)) [] [por def. sumaE'] \n", "= sumaE' 10 [] [por aplicación de \\$!] \n", "= 10 [por def. sumaE'] \n", "```\n", "\n", "**Comparación de consumo de memoria**\n", "\n", "+ Comparación de consumo de memoria:\n", "\n", "```sesion\n", "ghci> sumaNE [1..1000000]\n", "*** Exception: stack overflow\n", "ghci> sumaE [1..1000000]\n", "1784293664\n", "ghci> :set +s\n", "ghci> sumaE [1..1000000]\n", "1784293664\n", "(2.16 secs, 145435772 bytes)\n", "```" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Plegado estricto**\n", "\n", "+ Versión estricta de `foldl` en el `Data.List`\n", "\n", "```haskell\n", "foldl' :: (a -> b -> a) -> a -> [b] -> a\n", "foldl' f a [] = a\n", "foldl' f a (x:xs) = (foldl' f $! f a x) xs\n", "```\n", "\n", "+ Comparación de plegado y plegado estricto:s\n", "\n", "```sesion\n", "ghci> foldl (+) 0 [2,3,5]\n", "10\n", "ghci> foldl' (+) 0 [2,3,5]\n", "10\n", "ghci> foldl (+) 0 [1..1000000]\n", "*** Exception: stack overflow\n", "ghci> foldl' (+) 0 [1..1000000]\n", "500000500000\n", "```" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Bibliografía\n", "\n", "+ R. Bird. *Introducción a la programación funcional con Haskell*. Prentice\n", " Hall, 2000. \n", " + Cap. Cap. 7: Eficiencia.\n", "\n", "+ G. Hutton. *Programming in Haskell*. Cambridge University Press, 2007.\n", " + Cap. 12: Lazy evaluation.\n", "\n", "+ B. O'Sullivan, D. Stewart y J. Goerzen. *Real World Haskell*. O'Reilly, 2008.\n", " + Cap. 2: Types and Functions.\n", "\n", "+ B.C. Ruiz, F. Gutiérrez, P. Guerrero y J.E. Gallardo. *Razonando con\n", " Haskell*. Thompson, 2004.\n", " + Cap. 2: Introducción a Haskell.\n", " + Cap. 8: Evaluación perezosa. Redes de procesos.\n", "\n", "+ S. Thompson. *Haskell: The Craft of Functional Programming*, Second\n", " Edition. Addison-Wesley, 1999. \n", " + Cap. 17: Lazy programming." ] } ], "metadata": { "kernelspec": { "display_name": "Haskell", "language": "haskell", "name": "haskell" }, "language_info": { "codemirror_mode": "ihaskell", "file_extension": ".hs", "name": "haskell", "pygments_lexer": "Haskell", "version": "8.6.5" } }, "nbformat": 4, "nbformat_minor": 4 }