====== Tarea 1 (Entrega: 5 de Mayo 2017) ======


Esta tarea se distribuye con un archivo zip {{ :teaching:cc4101:resources:tareas:2017-1:base.zip |base}} que contiene 3 archivos: main.rkt, tests.rkt, y machine.rkt. Los archivos main.rkt y tests.rkt son incompletos, y en ellos tienen que implementar lo que se solicita en las preguntas 1, 2, y 3. **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 antes mencionados

Consulte las normas de entrega de tareas en http://pleiad.cl/teaching/cc4101.

**¡Ojo que los tests forman parte de su evaluación!**
===== 1. Funciones de primera clase con tipos declarados [1.5pt] ===== 
En esta tarea haremos extensión a un lenguaje con funciones de primera clase con tipos. La gramática del lenguaje es la mostrada a continuación: <code scheme>
<expr> ::= <num>
         | <id>
         | {+ <expr> <expr>}
         | {with {<id> : <type> <expr>} <expr>}
         | {fun {<id> : <type>} [: <type>] <expr>}
         | {<expr> <expr>}         

<type> ::= Num
         | {<type> -> <type>}
</code>
Fíjense que ''%%with%%'' no incluye anotación del tipo del cuerpo, y para las funciones, es opcional especificar el tipo de retorno. 
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.6) Defina la función ''%%(parse-type s-expr)%%'' 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 expr)%%'' para que acepte la gramática completa del lenguaje. Utilice la función ''%%(parse-type s-expr)%%'' 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.


===== 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 es efectivamente una función y que el tipo de la expresión de argumento de la aplicación coincide con el tipo esperado del argumento de la función.

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. 

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: No type for identifier <x>"
</code>

 donde <x> es el identificador libre

por ejemplo:
 
  <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} : {Num -> Num} 10}))
  "Type error in expression fun position 1: expected {Num -> Num} 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 'y))
  "Type error: No type for identifier: y"  
  </code>

    * (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 una 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 esta definida en el archivo machine.rkt.
La función ''%%(machine ins-list)%%'' le permitirá ejecutar una lista de instrucciones en la máquina. <code scheme>
> (machine (list (INT-CONST 6) (INT-CONST 1) (ADD)))
7
</code>
Tome un tiempo para experimentar con la función ''%%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 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 lenguaje original a listas de instrucciones. Note que solo es el paso a notación polaca inversa:  <code>

C(n) = INT-CONST n
C({+ a1 a2}) = C(a2);C(a1);ADD
C({f a}) = C(a); C(f); APPLY

</code>

La compilación de un nodo ''%%(acc n)%%'' es la siguiente:
<code>
C(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 dado 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.