| Next revision | Previous revision |
| teaching:cc4101:tareas:2022-1:tarea2:parte2 [2022/05/04 15:57] – created tdiaz | teaching:cc4101:tareas:2022-1:tarea2:parte2 [2023/05/08 15:33] (current) – [Parte 2. Memoización (2 ptos.)] tvallejos |
|---|
| * (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.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.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.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. |
| | |
| | <note>La librería functools de Python 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> |
| |
| Para implementar la tabla de memoización de una función, usen una tabla de hash ([[https://docs.racket-lang.org/reference/hashtables.html|documentación]]), que permite asociar llaves a valores (las llaves y valores pueden ser de cualquier tipo). A continuación, les dejamos un resumen de la interfaz. | Para implementar la tabla de memoización de una función, usen una tabla de hash ([[https://docs.racket-lang.org/reference/hashtables.html|documentación]]), que permite asociar llaves a valores (las llaves y valores pueden ser de cualquier tipo). A continuación, les dejamos un resumen de la interfaz. |
| * (0.5 ptos) Usando lo realizado en la Parte 1, implemente tests que evidencien que una función memoizada efectivamente no vuelve a ejecutar su cuerpo cuando la vuelven a aplicar con el mismo argumento. | * (0.5 ptos) Usando lo realizado en la Parte 1, implemente tests que evidencien que una función memoizada efectivamente no vuelve a ejecutar su cuerpo cuando la vuelven a aplicar con el mismo argumento. |
| |
| | <note important>Considere la función con memoización ''doble''. Si un programa ejecutara |
| | <code>{doble {printn 3}} |
| | {doble {printn 3}} |
| | </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> |
| |
| | **Observaciones**: |
| | * Los valores que usan como keys en un hash no pueden ser (o contener) valores mutables ((ver [[https://docs.racket-lang.org/reference/hashtables.html#(elem._(caveat._mutable-keys))|documentación]] sobre hash tables y valores mutables.)). Para evitar esto, por ejemplo si usan los valores del lenguaje como llaves, y que estos incluyen clausuras con hash, pueden definir una función para generar una versión immutable de esas clausuras (''%%hash->list%%'' convierte un hash en lista immutable).((ver [[https://docs.racket-lang.org/reference/hashtables.html#%28def._%28%28lib._racket%2Fprivate%2Fbase..rkt%29._hash-~3elist%29%29|documentación]] sobre conversion de hash tables a listas.)) |
| | * Cada ''mfun'' tiene su propia memoria. |
