| Both sides previous revisionPrevious revisionNext revision | Previous revision |
| teaching:cc4101:tareas:2025-1:tarea2:parte2 [2025/05/14 16:52] – [Parte 2. Memoización (2 ptos.)] dibanez | teaching:cc4101:tareas:2025-1:tarea2:parte2 [2025/06/10 16:09] (current) – etanter |
|---|
| En esta sección van a extender el lenguaje CL con un mecanismo de [[https://es.wikipedia.org/wiki/Memoizaci%C3%B3n|memoización]]. La memoización es una técnica de optimización que permite evaluar más rápidamente llamadas a funciones. Una función memoizada tiene asociada una estructura (p.ej. tabla de hash) donde se van guardando los argumentos con que se ha aplicado la función y el resultado de evaluar la función con esos argumentos. Luego, si se realiza una nueva aplicación con el mismo argumento, basta con acceder a la memoria para obtener el valor computado anteriormente, sin tener que evaluar todo el cuerpo de la función de nuevo. | En esta sección van a extender el lenguaje CL con un mecanismo de [[https://es.wikipedia.org/wiki/Memoizaci%C3%B3n|memoización]]. La memoización es una técnica de optimización que permite evaluar más rápidamente llamadas a funciones. Una función memoizada tiene asociada una estructura (p.ej. tabla de hash) donde se van guardando los argumentos con que se ha aplicado la función y el resultado de evaluar la función con esos argumentos. Luego, si se realiza una nueva aplicación con el mismo argumento, basta con acceder a la memoria para obtener el valor computado anteriormente, sin tener que evaluar todo el cuerpo de la función de nuevo. |
| |
| * (0.3 ptos) Extienda la sintaxis del lenguaje (y por ende, el parser) con la expresión ''{mfun {<id>} <CL>}'' que permite definir una función anónima memoizada. | * (0.4 ptos) Extienda la sintaxis del lenguaje (y por ende, el parser) con la expresión ''{mfun {<id>} <CL>}'' que permite definir una función anónima memoizada. |
| * (0.2 ptos) Extienda el tipo de dato de los valores con un nuevo constructor ''mclosV'' para representar una función memoizada en tiempo de ejecución. La única diferencia con clausuras tradicionales es la presencia de una tabla de memoización. | * (0.3 ptos) Extienda el tipo de dato de los valores con un nuevo constructor ''mclosV'' para representar una función memoizada en tiempo de ejecución. La única diferencia con clausuras tradicionales es la presencia de una tabla de memoización. |
| |
| <note> Un ejemplo de una aplicación de este concepto es la librería functools de Python, que posee un [[https://docs.python.org/3/library/functools.html#functools.lru_cache|decorador]] para memoizar los llamados de función y así ahorrar tiempo cuando se llama periódicamente a función con los mismos argumentos.</note> | <note> Un ejemplo de una aplicación de este concepto es la librería functools de Python, que posee un [[https://docs.python.org/3/library/functools.html#functools.lru_cache|decorador]] para memoizar los llamados de función y así ahorrar tiempo cuando se llama periódicamente a función con los mismos argumentos.</note> |
| </code> | </code> |
| |
| * (1 pto) Modifique el intérprete para que soporte funciones memoizadas. Recuerde que cada aplicación de una función memoizada debe obtener el valor registrado en la tabla de memoización, y de no estarlo, registrarlo para usos posteriores. | * (1.3 ptos) Modifique el intérprete para que soporte funciones memoizadas. Recuerde que cada aplicación de una función memoizada debe obtener el valor registrado en la tabla de memoización, y de no estarlo, registrarlo para usos posteriores. |
| |
| <note important>Considere la función con memoización ''doble'', que evalúa su argumento dos veces. Si un programa ejecutara | <note important>Considere la función con memoización ''double'', que retorna ''{+ x x}'' donde ''x'' es el argumento. Si un programa ejecutara |
| <code>{doble {printn 3}} | <code>{double {printn 3}} |
| {doble {printn 3}} | {double {printn 3}} |
| </code>¿Cuántas veces debería imprimirse el número 3? Piense en la solución antes de ver la respuesta. | </code>¿Cuántas veces debería imprimirse el número 3? Piense en la solución antes de ver la respuesta. |
| ((Se debe imprimir dos veces, CL siempre usa evaluación temprana. Por ende, la función ''doble'' recibe 3, después de que se hace ''printn''. Para la segunda aplicación recibe 3, también después de imprimir con ''printn''. Al recibir el 3 por segunda vez, responde lo que tiene en memoria, pero en este punto el 3 ya fue impreso por segunda vez.))</note> | ((Se debe imprimir dos veces, CL siempre usa evaluación temprana. Por ende, la función ''doble'' recibe 3, después de que se hace ''printn''. Para la segunda aplicación recibe 3, también después de imprimir con ''printn''. Al recibir el 3 por segunda vez, responde lo que tiene en memoria, pero en este punto el 3 ya fue impreso por segunda vez.))</note> |
