Table of Contents

Tarea 2 (Entrega: 17 de Junio de 2024)

Estrategias de evaluación

Como vieron en clases, los lenguajes de programación pueden tener distintas estrategias para evaluar los argumentos con los que se llama a una función. La gran mayoría de los lenguajes (C, Java, Python, JS, etc.) evalúan los argumentos de manera temprana (eager), es decir, al momento de la aplicación. Por otro lado, lenguajes como Haskell o bash utilizan una estrategia perezosa (lazy o call-by-need), en el que se retarda la evaluación de las expresiones hasta el momento en que es realmente necesario usarlas, evitando evaluar más de una vez la expresión si el argumento es usado varias veces. Una variante perezosa es la semántica call-by-name donde se evalúa la expresión de argumento cada vez que se necesita. Algunos lenguajes, como Scala, proveen mecanismos para elegir selectivamente qué estrategia usar (Scala es eager por defecto, pero soporta lazy val con semántica perezosa, y permite especificar que ciertos argumentos se pasen con la semántica call-by-name).

El objetivo final de esta tarea es extender un lenguaje, llamado SL (Surface Language), que adopta evaluación temprana por defecto, para que se pueda especificar la estrategia de evaluación de cada argumento si es necesario, ya sea con semántica call-by-need o call-by-name, usando anotaciones de tipos. SL es un lenguaje de más alto nivel, con tipos estáticos y with, que está implementado mediante una transformación a un lenguaje de (un poco) más bajo nivel CL (Core Language), que no tiene ni tipos ni with. La idea general de la implementación es de usar una transformación de programas SL a programas CL para realizar las distintas estrategias de evaluación. Note que está técnica es muy similar a la manera en la cual Scala implementa los features de by-name y by-need.


Les entregamos implementaciones de CL y SL, que tendrán que extender. Antes de empezar la tarea, miren en detalle la introducción a SL y CL para familiarizarse con el código que les entregamos.


Partes

  1. Testing de efectos (2 ptos) El lenguaje CL incluye una primitiva para imprimir en pantalla (útil para poder observar si se evalúa una expresión, y cuántas veces). Se darán cuenta que escribir pruebas (tests) para corroborar que se imprime lo esperado requiere de un soporte adicional. En esta primera parte, agregarán una forma de testear el efecto de imprimir usando una técnica que usa alcance dinámico.
  2. Memoización (2 ptos) En la segunda parte, extenderán CL con funciones memoizadas, es decir, funciones que “recuerdan” los resultados que produjeron para los argumentos que ya recibieron en el pasado. Esas funciones especiales serán útiles para resolver la parte 3.
  3. Estrategias de evaluación (2 ptos) La tercera parte consiste en agregar modificadores de tipos a SL para especificar la estrategia de evaluación a usar, y realizar estos modificadores mediante una modificación de la transformación de programas SL a CL.

Consulte las normas de entrega de tareas en http://pleiad.cl/teaching/cc4101. Recuerden que tienen que seguir la metodología vista en las primeras clases y dejar sus funciones debidamente documentadas.

Deben entregar via U-cursos un archivo .zip que contenga los siguientes archivos: core.rkt, surface.rkt, env.rkt y tests.rkt, archivos que deberán contener las funcionalidades solicitadas en cada pregunta y los test respectivos.