Para esta tarea tiene que entregar 3 archivos, uno que contenga la implementación de su tarea, un readmee con las instrucciones para ejecutar su tarea, y un archivo de los test de su tarea. Los tests forman parte de su evaluación! Consulte las normas de entrega de tareas en http://pleiad.cl/teaching/cc4101.

En esta tarea usted deberá implementar un interprete en un lenguaje NO funcional, tal como Java o C. Independiente del lenguaje que utilice se mantienen las reglas de las tareas pasadas, es decir, todo método/función debe tener su comentario y test.

Para claridad los lenguajes prohibidos son: Racket, Scheme, Lisp, Haskell, Scala, ML, OCaml, Coq, Idris, Agda, Rust, Erlang.

Para esta tarea usted recibirá un String como argumento y deberá parsearlo, interpretarlo y retornar el resultado como un String , su lenguaje debe ser capaz de soportar los mismos casos que el lenguaje visto en clases y se deberá caer en los mismos casos.

A continuación se presenta la gramática BNF del lenguaje:

<s-expr> ::= <num>
         | {+ <s-expr> <s-expr>}
         | {- <s-expr> <s-expr>}
         | {if0 <s-expr> <s-expr> <s-expr>}
         | {with {<id> <s-expr>} <s-expr>}
         | <id>
         | {fun {<id>} <s-expr>}
         | {seqn <s-expr> <s-expr>}
         | {set <id> <s-expr>}
         | {<s-expr> <s-expr>}

Usted deberá definir lo siguiente:

1. Defina la función parser :: String -> Expr que parsea el lenguaje
2. Defina la función interp :: Expr x Env -> Val que evalua un programa con semántica eager.
3. Defina la función run :: s-expr -> String que toma un programa fuente y retorna la representación en String del valor resultante de la interpretación con su tipo anotado. Es recomendable definir una función auxiliar que le permita pasar de su representación de estructuras a la notación de los ejemplos con Strings.

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