Differences

This shows you the differences between two versions of the page.

@@ Line 1: / Line 1: @@
+====== Tarea 1 (Entrega: 30 de abril de 2018) ======
+Esta tarea se distribuye con un archivo zip {{ :teaching:cc4101:resources:tareas:2018-1: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>}
+         | {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.
+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 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. 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: No type for 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} : {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>
+**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 ''%%(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)))
+> (machine (list (INT-CONST 3) (CLOSURE (list (ACCESS 0) (RETURN))) (APPLY)))
+
+</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 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.