[[teaching:cc4101:tareas:2024-1:tarea2|<< Volver]]

===== Parte 3. Estrategias de evaluación (2 ptos.) =====

En esta sección van a extender el lenguaje SL 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//. 

La extensión de SL consiste en agregar //modificadores// a los tipos declarados por las funciones funciones, los que especifican el tipo de estrategia a utilizar para los argumentos. A continuación les proveemos una ilustración de este mecanismo y qué es lo que debieran obtener al finalizar esta sección. 
<code scheme>
;; Una función de tipo Num -> Num significa que se aplicará con evaluación temprana.
> (run-p-sl '{with {f {fun {x : Num} -> Num : {+ x x}}}   
                     {f {printn 10}}})  
(result 20 '("10"))   ;; Se imprime una vez, al evaluar el argumento en la aplicación

;; Una función de tipo (lazy Num -> Num), usará evaluación lazy/call-by-need para su argumento.
> (run-p-sl '{with {f {fun {x : {lazy Num}} -> Num : {+ x x}}}   
                     {f {printn 10}}})
(result 20 '("10"))   ;; Se imprime una vez cuando se usa el argumento dentro del cuerpo

;; Una función de tipo (name Num -> Num), usará evaluación name/call-by-name para su argumento.
> (run-p-sl '{with {f {fun {x : {name Num}} -> Num : {+ x x}}} 
                     {f {printn 10}}})
(result 20 '("10" "10"))   ;; Se imprime dos veces, una por cada uso que se hace del argumento, dentro del cuerpo

;; Otro ejemplo de lazy. Note que efectivamente al evaluarla se comporta correctamente.
> (run-p-sl '{with {f {fun {x : {lazy Num} -> Num : 1}}}   
                     {f {printn 10}}})
(result 1 '())   ;; No se imprime porque el argumento nunca se usa dentro del cuerpo
</code>

Las semánticas de evaluación y uso de argumentos con modificadores ''lazy'' y ''name'' se van a realizar mediante la transformación de SL a CL. Es decir, no tienen que cambiar nada en CL, sólo modificar la transformación que les proveemos.
A continuación los guiaremos en el proceso de extender SL con modificadores de tipo, y ajustar la transformación para que sus cambios se reflejen en CL.

==== 3.1 Modificadores ====

Para extender SL con modificadores, considere la siguiente gramática. Note que se agrega la nueva categoría ''<mtype>'' para tipos con modificadores, y se actualiza la definición de funciones para que la use.
<code scheme>
<SL> ::= <num>
         | {+ <SL> <SL>}
         | {if0 <SL> <SL> <SL>}
         | {with {<sym> <SL>} <SL>}
         | <id>
         | {<SL> <SL>}
         | {fun {<sym> : <mtype>} → <mtype> : <SL>}  ;; note el uso de mtype (tipos con modificadores)
         | {printn <SL>}

<mtype> ::= {<mod> <type>} ; tipo con modificador
         | <type>          ; azúcar para evaluación temprana

<mod> ::= lazy   ; call-by-need / lazy
        | name   ; call-by-name

<type> ::= Num
         | {<mtype> -> <mtype>}
</code>

  * (0.1 ptos) Modifique la definición de ''Type'' para que soporte tipos con modificadores (para las distintas estrategias de evaluación no es necesario definir un tipo de dato, puede utilizar símbolos).
  * (0.2 ptos) Modifique el parser (caso función) para que soporte tipos con modificadores, usando una función auxiliar ''parse-mtype''. 
  * Para facilitar lo que sigue, implemente dos funciones auxiliares: ''type-mod'', que dado un tipo retorna su modificador; y ''sl-mod'', que dada una expresión en SL retorna el modificador del tipo de la expresión.

**Hint**: si bien en la sintaxis solo existen dos modificadores, internamente es más conveniente tener 3 (incluyendo uno para eager), así todo tipo tiene un modificador.

<note tip>
  * Se puede pensar ''lazy X'' y ''name X'' como el tipo de las promesas que producen ''X''.
  * Note la definición mutuamente recursiva entre ''<type>'' y ''<mtype>''. Esta definición nos permite crear (entre otros tipos) funciones de tipo ''(lazy Num) -> (name Num)'', es decir, una función que toma como argumento una expresión que produce un Num (sin evaluarla, y la evalua de manera lazy si es necesario), y retorna una expresión que produce un Num (sin evaluarla, y deberá ser evaluada tantas veces como sea utilizada). 
</note>
----

==== 3.2 Chequeo de tipos ====

Ahora tenemos que actualizar la función de chequeo de tipos. Debido a que ahora los tipos incluyen modificadores, la función de ''type-ast'' no es correcta. Más precisamente, note el uso de la función ''check-type'' que chequea si dos tipos son iguales (p.ej. cuando queremos validar que las expresiones de una suma tienen tipo numérico). Dado que la estrategia de evaluación no influye en el tipo subyacente, esta comparación de igualdad es demasiado estricta: por ejemplo es correcto usar un ''{lazy Num}'' donde uno espera un ''Num'' --- ambos siguen siendo expresiones que producen números. 
 
  * (0.2 ptos) Implemente la función ''compatible?'' que, dados dos tipos, determina si son compatibles, es decir, iguales sin considerar sus modificadores.
  * (0.1 ptos) Actualice ''type-ast'' para que considere tipos compatibles, en vez de iguales.
  * (0.1 ptos) Escriba tests que demuestran el buen funcionamiento del typechecker en presencia de modificadores.

----

==== 3.3 Transformación a CL ====

Ahora que el lenguaje soporta tipos con modificadores, es necesario implementar las semánticas correspondientes. Esto se va a realizar en la transformación de un programa SL a un programa CL.
  * (1.0 pto) Modifique la función de transformación para que se apliquen los ajustes necesarios.
  * (0.3 ptos) Escriba tests, usando lo implementado en la Parte 1, que evidencien la nueva funcionalidad. Considere todos los casos posibles (incluyendo con funciones de orden superior!).

<note tip>
Para una correcta transformación, considere las siguientes observaciones:
  * Si se requiere un argumento con estrategia lazy o by-name, y se usa un argumento que tiene evaluación temprana, entonces hay que ajustar la expresión de tal manera que se retrase su evaluación.
  * Una forma de retrasar la evaluación de una expresión ''%%e%%'', es ponerla en el cuerpo de una lambda ''%%(lambda (_) e)%%''. Luego para evaluarla basta aplicar la función.
  * Si se requiere una evaluación temprana y el argumento fue declarado lazy o by-name, entonces es necesario ajustarlo para que efectivamente se evalúe en ese punto.
  * Si tanto la función como el argumento calzan en la estrategia, entonces no hay nada que hacer.
  * Recuerde que la diferencia entre lazy (a.k.a. by-need) y by-name es que la primera evalúa una sola vez la expresión y luego "recuerda" el valor para próximos usos. Acuérdese de lo realizado en la Parte 2 con funciones memoizadas!

</note>