====== Tarea 1 (Entrega: 28 de abril de 2019) ======


Esta tarea se distribuye con un archivo zip {{ :teaching:cc4101:resources:tareas:2019-1:tarea1:base.zip |base}} que contiene 3 archivos: main.rkt, tests.rkt, y machine.rkt. Los archivos main.rkt y tests.rkt están incompletos, y en ellos tienen que implementar lo que se solicita en las preguntas siguientes. **No deben modificar el archivo machine.rkt**: es una implementación completa de la máquina a la cual van a compilar su lenguaje.

Deben entregar via U-cursos **un archivo .zip** que contenga los archivos main.rkt y tests.rkt.

<note important>Consulte las normas de entrega de tareas en http://pleiad.cl/teaching/cc4101</note>

**¡Los tests, los contratos y las descripciones forman parte de su evaluación!**

===== 1. Funciones de primera clase con tipos declarados [1.5pt] ===== 
En esta tarea agregaremos anotaciones de tipos a un lenguaje con funciones de primera clase. La sintaxis concreta del lenguaje es la mostrada a continuación: <code scheme>
<s-expr> ::= <num>
         | <id>
         | {+ <s-expr> <s-expr>}
         | {- <s-expr> <s-expr>}
         | {with {<id> : <type> <s-expr>} <s-expr>}
         | {fun {<id> : <type>} [: <type>] <s-expr>}
         | {<s-expr> <s-expr>}         

<type> ::= Num
         | {<type> -> <type>}
</code>
Note que ''%%with%%'' no incluye anotación del tipo del cuerpo, y el tipo de retorno de las funciones es opcional (los '[' ']' son parte de la notación BNF, especificando que lo que va adentro es opcional). 
Por ejemplo, los programas siguientes son válidos: <code scheme>
{with {x : Num 5} {+ x 3}}

{fun {x : Num} : Num 
  {+ x 3}}

{fun {x : Num}
  {+ x 3}}
</code>

  * (0.3) Defina la función ''%%(parse-type type)%%'' que parsea solo la gramática de tipos. Ademas en caso de error, debe retornar el error "Parse error" <code scheme>
> (parse-type '{{Num -> Num} -> Num})
(TFun (TFun (TNum) (TNum)) (TNum))

> (parse-type '{Num ->  })
"Parse error"
</code>
  * (0.9) Defina la función ''%%(parse s-expr)%%'' para que acepte la gramática completa del lenguaje. Utilice la función ''%%(Parse-type type)%%'' en los puntos donde deba identificar tipos. Además, la función ''%%parse%%'' debe reemplazar el ''%%with%%'' por una aplicación de función. Ejemplos: <code scheme>
> (parse '{fun {x : Num} : Num {+ x 1}})
(fun 'x (TNum) (add (id 'x) (num 1)) (TNum))

> (parse '{with {y : Num 2}
             {+ x y}})
(app (fun 'y (TNum) (add (id 'x) (id 'y)) #f) (num 2))
</code>

**Note que se usa ''%%#f%%'' cuando una función no tiene anotado un tipo de retorno.**

  * (0.3) Defina la función ''%%(prettify type)%%'' que tome un tipo y lo escriba en la sintaxis concreta.<code scheme>
> (prettify (TNum))
'Num

> (prettify (TFun (TNum) (TFun (TNum) (TNum)))
'(Num -> (Num -> Num))
</code>

===== 2. Verificación de Tipos [1.5pt] =====
Se implementará el chequeo de tipos de una expresión en presencia de funciones de primera clase.
  * (1.0) Implemente la función ''%%(typeof expr)%%'' que calcula el tipo de la expresión dada o falla con un mensaje de error en caso de que la expresión no sea válida. Para la validación, considere lo siguiente:
     * Para una función con el tipo de retorno anotado, se valida que la expresión del cuerpo tenga el mismo tipo que el tipo de retorno declarado.
     * Para una función sin el tipo de retorno anotado, el tipo resultante considera el tipo calculado del cuerpo de la función.
     * Para la aplicación de función se valida que la expresión en posición de función sea efectivamente una función.
     * Para la aplicación de función también se valida que el tipo de la expresión de argumento de la aplicación coincide con el tipo esperado del argumento de la función.
     * Para la aplicación de un operador se valida que sus operandos tengan el tipo correcto.

Los mensaje de error de tipo tienen que seguir el siguiente patrón: 
<code scheme>
"Type error in expression <E> position <n>: expected <T1> found <T2>"
</code>

 donde E es la expresión donde ocurrió el error, n es la sub-expresión donde se manifestó, T1 es el tipo esperado y T2 el tipo encontrado. Utilice su función prettify para mostrar errores legibles.

**Note que la única forma de tener error de tipo de función, es cuando el tipo de retorno está anotado.**

Para el caso cuando hay algún identificador libre, el patrón es:
<code scheme>
"Type error: free identifier: <x>"
</code>
 donde <x> es el identificador libre.

Algunos ejemplos:
 
  <code scheme> 
  > (typeof (parse '{fun {x : Num} : Num 5}))
  (TFun (TNum) (TNum))
  > (typeof (parse '{fun {x : Num} x}))
  (TFun (TNum) (TNum))
  > (typeof (parse '{{fun {x : Num} x} 1}))
  (TNum)
  > (typeof (parse '{fun {x : Num} : {Num -> Num} 10}))
  "Type error in expression fun position 1: expected (Num -> Num) found Num"
  > (typeof (parse '{1 2}))
  "Type error in expression app position 1: expected (T -> S) found Num"
  > (typeof (parse '{{fun {x : Num} : Num {+ x x}} {fun {x : Num} : Num 5}}))
  "Type error in expression app position 2: expected Num found (Num -> Num)"
  >(typeof (parse '{fun{x : Num}{+ x {fun{z : Num} 1}}}))
  "Type error in expression + position 2: expected Num found (Num -> Num)"
  > (typeof (parse 'y))
  "Type error: free identifier: y"</code>

**Note que debe manejar identificadores adecuadamente, considere la implementación de un ambiente que almacene tipos.**

    * (0.5) Implemente la función ''%%(typecheck s-expr)%%'' que retorna el tipo de un programa, en un formato legible:
 
<code scheme> 
>(typecheck '3)
'Num

>(typecheck  '{fun {f : Num} : Num 10})
'(Num -> Num)

>(typecheck  '{+ 2 {fun {x : Num} : Num x}})
  "Type error in expression + position 2: expected Num found {Num -> Num}"


</code>    

===== 3. Compilación [3.0pt]=====
Ahora vamos a compilar nuestro lenguaje a una máquina abstracta basada en stack. La máquina es similar a la conocida SECD(([[https://en.wikipedia.org/wiki/SECD_machine|https://en.wikipedia.org/wiki/SECD_machine]])), la cual no trabaja con identificadores, sino que solo con índices. La máquina SECD consume una lista de instrucciones, utiliza un stack para almacenar datos temporales y posee un ambiente que, a diferencia del ambiente visto normalmente en el curso, es un arreglo con valores sin identificadores. La máquina SECD ya está definida en el archivo machine.rkt.
La función ''%%(exec-machine ins-list)%%'' le permitirá ejecutar una lista de instrucciones en la máquina. <code scheme>
> (exec-machine (list (INT-CONST 6) (INT-CONST 1) (ADD)))
7
> (exec-machine (list (INT-CONST 3) (CLOSURE (list (ACCESS 0) (RETURN))) (APPLY)))
3 
</code>
**Tome un tiempo para experimentar con la función ''%%exec-machine%%'' y el set de instrucciones antes de realizar los próximos ejercicios.**

==== Índices De Bruijn ====
Una forma de eliminar nombres de variables o identificadores de una expresión, es usando índices De Bruijn. Anteriormente vimos que la máquina SECD trabaja solo con índices, por lo que en esta sección vamos a hacer el paso de identificadores a dichos números, usando indices De Bruijn((La explicación detallada de como funcionan se puede encontrar en la sección 3.5 del [[http://cs.brown.edu/~sk/Publications/Books/ProgLangs/2007-04-26/plai-2007-04-26.pdf|PLAI]])).
  * (1.5) Implemente la función ''%%deBruijn%%'' que toma una expresión y la recorre reemplazando los identificadores no libres, con los índices De Bruijn (nodos ''%%(acc n)%%'') manteniendo el scope léxico. La salida de esta función no debería tener nodos del tipo ''%%fun%%'', ni ''%% id%%''. En su lugar debería contener nodos del tipo ''%%fun-db%%'' y ''%%acc%%''. El resto de los nodos no varía. 
**Hint: le podría ser útil recordar que el intérprete visto en clases usa un ambiente para asociar identificadores a valores.**

<code scheme>
> (deBruijn 
   (parse '{+ 1 {with {x : Num 1}
                           {with {y : Num 2}
                                 {+ x y}}}}))
(add
 (num 1)
 (app
  (fun-db
   (app (fun-db (add (acc 1) (acc 0))) (num 2)))
  (num 1)))
    
> (deBruijn (add (num 1) (id 'x)))
"Free identifier: x"
</code>

==== De AST a código de máquina ====
Vamos a abordar la compilación del AST de una expresión al set de instrucciones de la SECD.
A continuación se presenta el esquema de compilación que permite hacer el paso del AST de una expresión a una lista de instrucciones (revise el archivo machine.rkt, todas las definiciones están comentadas y puede encontrar la sintaxis completa de las instrucciones). Note que solo es el paso a notación polaca inversa:  <code>

C((num n)) = (INT-CONST n)
C((add a1 a2)) = C(a2);C(a1);(ADD)
C((sub a1 a2)) = C(a2);C(a1);(SUB)
C((app f a)) = C(a); C(f);(APPLY)

</code>

La compilación de un nodo ''%%(acc n)%%'' es la siguiente:
<code>
C((acc n)) = (ACCESS n)

</code>
La compilación de una función puede ser inferida del ejemplo a continuación: <code scheme> 
> (compile (deBruijn (parse '{{fun {x : Num} : Num
                                   {+ x 10}} {+ 2 3}})))
(list
 (INT-CONST 3)
 (INT-CONST 2)
 (ADD)
 (CLOSURE (list (INT-CONST 10) (ACCESS 0) (ADD) (RETURN)))
 (APPLY)) 
</code>


  * (1.0) Implemente la función ''%%(compile expr)%%'' que dada una expresión con índices De Bruijn genera la lista de instrucciones siguiendo el esquema de compilación descrito anteriormente. 

  * (0.5) Implemente la función ''%%(typed-compile s-expr)%%'' que se encarga de todo el proceso de generación de código desde un programa, considerando el parsing, la validación de tipos, y la transformación con índices De Bruijn. Note que esta función solo genera código de maquina si la expresión esta bien tipada, sino produce el error correspondiente.