<< 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.

;; La función se declara de tipo (Num -> Num). Sin modificadores significa evaluación temprana.
> (run-p-sl '{with {f {fun {Num -> Num} {x} {+ x x}}}   
                     {f {printn 10}}})  
(result 20 '("10"))   ;; Se imprime una vez, al evaluar el argumento en la aplicación
 
;; La función se declara (lazy Num -> Num), es decir, se declara el argumento como lazy/call-by-need.
> (run-p-sl '{with {f {fun {{lazy Num} -> Num} {x} {+ x x}}}   
                     {f {printn 10}}})
(result 20 '("10"))   ;; Se imprime una vez cuando se usa el argumento dentro del cuerpo
 
;; La función se declara (name Num -> Num), es decir, se declara el argumento como name/call-by-name.
> (run-p-sl '{with {f {fun {{name Num} -> Num} {x} {+ 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 {{lazy Num} -> Num} {x} 1}}   
                     {f {printn 10}}})
(result 1 '())   ;; No se imprime porque el argumento nunca se usa dentro del cuerpo

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.

<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>}
  • (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.

Observaciones:

  • 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).
  • Se puede pensar lazy X y name X como el tipo de las promesas que producen X.
  • Note también que los modificadores solo se pueden aplicar al dominio y al codominio. Por lo que una funcion no puede tener tipo {lazy {Num → Num}}, pero si tipo {{lazy {Num -> Num}} -> Num} o {Num → {lazy {Num → Num}}}.

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!).
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 es necesario hacer cambios.
  • Recuerde que la diferencia entre lazy 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 1 con funciones memoizadas!