Esta tarea se distribuye con dos ficheros base.rkt y tests.rkt (base tarea 2). Considere las definiciones del archivo base.rkt y escriba sus funciones en él. Escriba sus tests en el archivo tests.rkt adjunto. Ambos ficheros deben ser entregados vía U-Cursos. Los tests forman parte de su evaluación! Consulte las normas de entrega de tareas en http://pleiad.cl/teaching/cc4101.

En esta tarea se le provee el lenguaje MiniScheme+, que corresponde a un intérprete extendido con sistema de tipos estático. Además, MiniScheme+ incorpora el uso de primitivas¹⁾. A continuación se presenta un breve tour de las características de MiniScheme+:

1. Funciones de primera clase con argumentos múltiples: las funciones y las expresiones with pueden tener 0 o más argumentos, por ejemplo:

   > (run '(+ 1 ((fun ([x : Num] [y : Num]) (+ x y)) 1 2)))
   4

2. Definiciones usando local y define: la expresión local permite realizar definiciones de identificadores usando define. Por ejemplo:

   > (run '(local ((define x 10)
                       (define y x))
                 (+ x y)))
   20

Observe que define sólo puede usarse en la zona de declaraciones de una expresión local. Para más detalles, consulte la implementación y tests provistos.

Extienda MiniScheme para soportar asignación (:=) y secuencia de instrucciones (seqn):

(local ([define x 10])
    (+ x
       (seqn (:= x 4)
             x)))
>14

Agregue ambas expresiones al lenguaje, y extienda el verificador de tipo para soportar asignación y secuencia. Introduzca el tipo TVoid. El tipo de una asignación es TVoid y el tipo de una secuencia es el tipo de la ultima expresión.

Indicación: Para implementar mutación, tiene que cambiar la implementación de los ambientes: en vez de usar una lista de asociaciones (ie. lista de pares) en cada frame, use ahora una tabla de hash. Vea la documentación Racket sobre tablas de hash.

En la versión actual, la verificación de tipos definida en typeof es “desechable”: dado un AST, retorna su tipo o arroja un error, y luego se olvida de lo que hizo. En la práctica, hay varias transformaciones que se hacen sobre un AST, para las cuales la información de tipos es muy importante. Esto incluye a varios tipos de optimizaciones, y también a extensiones del lenguaje mismo. Veremos un ejemplo de este último caso en la subsiguiente sección.

Para preparar el terreno, en esta parte, tiene que cambiar la forma en la cual se realiza la verificación de tipos. En vez de ser una función typeof :: Expr Env → Type, tiene que definir la verificación como la función type :: Expr Env → Expr: retorna una expresión donde en cada sub-expresión tiene su información de tipo guardada.

• Modifique la definición del AST Expr para que cada nodo tenga un atributo type, que pueda ser o #f o un Type.

• Modifique el parser para que inicialice todos los nodos del AST con #f en su atributo type.

• Modifique el interprete para que ignore los atributos type de los nodos.

• Modifique la función typeof :: Expr → Type Para que ahora, dado un Expr, retorna el valor de su attributo type.

• Defina la función type :: Expr Env → Expr, que produce un nuevo árbol con la información de tipos en cada nodo, o arroja un error si corresponde.

Si bien el manejo de ambientes y local/define en MiniScheme permite definir y ejecutar funciones recursivas, el sistema de tipos no es capaz de verificar dichas definiciones. Por ejemplo, tipar el siguiente programa genera un error:

(local ([define fact (fun ([n : Num])
                          (if (zero? n) 1
                              (* n (fact (- n 1)))))])
  (fact 10))

Aquí, no es suficiente asegurarse que fact esté en el ambiente de tipos; la pregunta es ¿que tipo debería tener? Mientras hasta ahora hemos inferrido el tipo de retorno de las funciones, hacerlo en presencia de definiciones recursivas es bastante más complejo. Al igual que Scala, vamos a optar por una solución más simple, que consiste en exigir que el programador específique el tipo de retorno de las funciones recursivas. Por ejemplo:

(local ([define fact (fun ([n : Num]) : Num
                          (if (zero? n) 1
                              (* n (fact (- n 1)))))])
  (fact 10))

• Modifique el parser para soportar anotación del tipo de retorno de una función. Este parámetro es opcional, es decir, en el caso en que se específique, el parser debe inicializar el atributo type del nodo fun correspondiente.

Uno de los mecanismos muy útiles para proveer extensibilidad en un lenguaje es la posibilidad de pasar parametros por nombre (call-by-name). Cuando uno llama una función que espera su parametro por nombre, el parámetro no se evalua, sino que se crea una clausura (sin argumento) que encapsula la computación del parámetro correspondiente. Luego, en el cuerpo de la función, cada vez que se usa el nombre del argumento, se evalua la expresión asociada. En Scala, call-by-name está usado para permitir la definición de operadores de control customizados (como while, do-unless, etc.), para proveer una librería de streams, y varias otras APIs.

En esta sección, tiene que extender el lenguaje para que soporte call-by-name, de una manera similar a como está realizado en Scala: en vez de extender el interprete, call-by-name está soportado a través de una transformación del programa que hace uso de la información de tipos para generar un programa equivalente. Este programa se ejecuta con el mismo interprete del programa.

• Extienda el lenguaje de tipos de MiniScheme para soportar el tipo (Lazy T), donde T es un tipo. Por ejemplo, el loop while se puede agregar a MiniScheme usando call-by-name de la siguiente manera:

  (local
     ([define while (fun ([cond : (Lazy Bool)]
                          [body : (Lazy Void)]) : Void
                        (if cond
                            (seqn body
                                  (while cond body))
                            (void)))]
      [define i 10])
    (while (> i 0)
           (seqn
            (displayln (number->string i))
            (:= i (- i 1)))))          

• Extienda type para que acepte programas con tipos Lazy.

• Defina la función de transformación cbn-trans :: Expr → Expr que encapsula dentro de una función la computación del parámetro correspondiente. ²⁾

Indicaciónes:

• No tiene que hacer ninguna modificación al interprete.
• La información de tipos le indica donde/cuando tiene que hacer modificaciones.

Use el soporte para call-by-name para definir Streams, y la siguientes funciones:

• stream-hd :: Steam[T] -> T : retorna la cabeza de un stream.
• stream-tl :: Steam[T] -> Steam[T]stream-tl: retorna la cola de un stream.
• stream-take :: Num x Steam[T] -> List[T]: que retorna una lista con los primeros n elementos de stream.