Differences

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

--- teaching:cc4101:tareas:2016-1:tarea1 [2016/03/29 01:31] – created fmosso
+++ teaching:cc4101:tareas:2016-1:tarea1 [2016/04/17 00:03] (current) – [Tarea 1 (Entrega: 20 de Abril 2016)] fmosso
@@ Line 1: / Line 1: @@
-tarea
+====== Tarea 1 (Entrega: 20 de Abril 2016) ======
+Esta tarea se distribuye con un archivo zip {{:teaching:cc4101:tareas:2016-1:2016-tarea1ver2.zip|}} que contiene **3 carpetas A, B, y C**, correspondientes a los conjuntos de archivos que tienen que entregar. Noten que la carpeta C es para entregar la pregunta opcional (bonus) descrita al final de la tarea.
+    * La **carpeta A** 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.
+    * La **carpeta B** contiene solamente machine.rkt, identico al de la carpeta A. Ahí tendrán que poner los archivos main.rkt y tests.rkt que correspondan a lo que se solicita en la pregunta 4.
+    * La **carpeta C** viene vacía. Si optan por no hacer la pregunta opcional, tendrán que poner ahí los tres archivos main/tests/machine según corresponda para resolver el problema planteado.
+Deben entregar via U-cursos **un archivo .zip** que contenga las carpetas ante mencionada (obviamente, si no hacen la pregunta opcional, da lo mismo si incluyen o no la carpeta C en su entrega).
+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 [1pt] =====
+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>
+         | <bool>
+         | <id>
+         | {+ <expr> <expr>}
+         | {- <expr> <expr>}
+         | {= <expr> <expr>}
+         | {< <expr> <expr>}
+         | {and <expr> <expr>}
+         | {or <expr> <expr>}
+         | {not <expr>}
+         | {if <expr> <expr> <expr>}
+         | {with {<id> : <type> <expr>} <expr>}
+         | {fun {<id> : <type>} [: <type>] <expr>}
+         | {<expr> <expr>}
+<type> ::= Num
+         | Bool
+         | {<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.4) 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} -> Bool})
+(TFun (TFun (TNum) (TNum)) (TBool))
+> (parse-type '{Num ->  })
+"Parse error"
+</code>
+  - (0.6) 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. Compilación [2pt]=====
+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)))
+
+</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.0) 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 interprete 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(b) = BOOL-CONST b
+C(n) = ACCESS n
+C({+ a1 a2}) = C(a2);C(a1);ADD
+C({- a1 a2}) = C(a2);C(a1);SUB
+C({< a1 a2}) = C(a2);C(a1);LESS
+C({= a1 a2}) = C(a2);C(a1);EQ
+C({and a1 a2}) = C(a2);C(a1);AND
+C({or a1 a2}) = C(a2);C(a1);OR
+C({not a1}) = C(a1);NOT
+C({f a}) = C(a); C(f); APPLY
+C({if c tb fb}) = C(c); IF(C(tb),C(fb))
+</code>
+La compilación de una función puede ser inferida del ejemplo a continuación: <code scheme>
+> (compile (deBruijn (parse '{{fun {x : Num} : Bool
+                                   {< x 10}} {+ 2 3}})))
+(list
+ (INT-CONST 3)
+ (INT-CONST 2)
+ (ADD)
+ (CLOSURE (list (INT-CONST 10) (ACCESS 0) (LESS) (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.
+===== 3. 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 valida. Para la validación, considere lo siguiente:
+     * Para el if ambas ramas deben ser del mismo tipo, es decir al tipear ''%%{if #t 1 6}%%'' debe ser del tipo TNum, en cambio ''%%{if #t 1 #f}%%'' debe retornar un mensaje de error
+     * Para una función con el tipo de retorno anotado, se válida 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.
+Para el caso cuando hay algún identificador libre, el patrón es:
+<code scheme>
+"Type error in expression id position 1: No type for identifier <x>"
+</code>
+ donde <x> es el identificador libre
+por ejemplo:
+  <code scheme>
+  > (typeof (parse '{fun {f : Num} : Bool #t}))
+  (TFun (TNum) (TBool))
+  > (typeof (parse '{fun {f : Num} #t}))
+  (TFun (TNum) (TBool))
+  > (typeof (parse '{fun {f : Num} : Bool 10}))
+  "Type error in expression fun position 3: expected Bool found Num"
+  > (typeof (parse '{{fun {f : Num} : Bool #t} #t}))
+  "Type error in expression app position 2: expected Num found Bool"
+  > (typeof (parse 'y))
+  "Type error in expression id position 1: No type for identifier: y"
+  </code>
+    * (0.3) 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} : Bool #t})
+'{Num -> Bool}
+>(typecheck  '{+ 2 #t})
+  "Type error in expression + position 2: expected Num found Bool"
+>(typecheck  '{if #t 1 #t})
+  "Type error in expression if position 3: expected Num found Bool"
+</code>
+  * (0.2) 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.
+===== 4. Sistema de tipos con subtipos [1.5pt] =====
+//Recuerde: esta pregunta se entrega en la carpeta B//
+Vamos a aumentar la expresividad de nuestro sistema de tipos introduciendo una forma básica de //sub-tipado//.((Para más información sobre sub-tipado https://en.wikipedia.org/wiki/Subtyping))
+La relación de subtipos se escribe ''%%A <: B%%'' y se lee como A es subtipo de B (o equivalentemente, que B es supertipo de A).
+La intuición es que es válido usar una expresión de tipo A donde se espera una expresión de tipo B.
+Introducimos el tipo Any como supertipo universal. Es decir, para todo tipo T, tenemos ''%%T <: Any%%''.  Note que la relación de subtipado es reflexiva, i.e. ''%%T <: T%%''.
+Tener ''%%Any%%'' permite admitir más programas. Por ejemplo, una expresión condicional donde las dos ramas son de tipos distintos (como ''%%{if #t 1 #f}%%''), ahora puede ser considerada valida, asignándole el tipo ''%%Any%%''.
+Como otro ejemplo, la función ''%%{fun {x : Any} x}%%'' tiene el tipo ''%%{Any -> Any}%%'', y por ende se le puede pasar cualquier valor como argumento.
+Algo interesante surge al considerar tipos de funciones. La regla es que un tipo de función ''%%A -> B%%'' es subtipo de ''%%C -> D%%'' si ''%%C <: A%%'' y ''%%B <: D%%''.
+Notar que la relación de sub-tipado de los tipos de los cuerpos esta en el mismo sentido (//variante//) que la relación de sub-tipado de las funciones, pero que esta invertida (//contravariante//) para los tipos de los argumentos. La intuición es que si tenemos la función f con el tipo ''%%A -> B%%'', entonces sabemos que f acepta elementos de tipo ''%%A%%'', claramente f también acepta cualquier elemento de cualquier tipo ''%%C%%'', que es subtipo de ''%%A%%''. El tipo de f tambien nos dice que retorna elementos de tipo ''%%B%%'', también podemos ver estos elementos de retorno como si pertenecieran a cualquier supertipo ''%%D%%'' de ''%%B%%''. Es decir, para cualquier función f de tipo ''%%A -> B%%'' tambien puede ser vista como del tipo ''%%C -> D%%''.((Una visión alternativa es que es seguro permitir que una función de tipo ''%%A -> B%%'' sea usada en un contexto donde otro tipo ''%%C -> D%%'' es esperado mientras que ninguno de los argumentos que podrían ser pasados sorprendan a la función (''%%C <: A%%''), y que ninguno de los resultados que retorna la función sorprenda al contexto (''%%B <: D%%'').))
+    * (1.0) Extienda la definición de los tipos para soportar ''%%Any%%'', y modifique ''%%typeof%%'' para que soporte sub-tipado.
+Si bien el sub-tipado permite aceptar más programas, tener un valor del tipo ''%%Any%%'' es poco útil, ya que no se puede usar ni como función, ni como booleano o número.
+Por ejemplo:
+<code scheme>
+  {+ {{fun {x : Any} x} 1}
+}
+</code>
+es rechazado por el sistema de tipo, ya que ''%%{{fun {x : Any} x} 1}%%'' tiene el tipo ''%%Any%%''.
+Para solucionar este problema, los lenguajes de programación con subtipos incluyen mecanismos que permiten que el programador le fuerce la mano al sistema de tipos: decirle que una expresión de un tipo ''%%T1%%'' pueda ser considerada de otro tipo ''%%T2%%''. En algunos lenguajes, como C o Haskell, esas //coerciones// se consideran sin más control, y por ende puede llevar el programa a caerse de manera incontrolada en tiempo de ejecución. En otros, como los //casts// de Java, se hace una verificación en tiempo de ejecución para evitar comprometer la ejecución.
+En esta parte, tienen que implementar coerciones, sin verificación dinámica (agregar verificación dinámica se deja como pregunta opcional al final de esta tarea).
+    * (0.5) agregue al lenguaje la expresión ''%%(coerce <type> <expr>)%%''. El tipo de una expresión de coerción es el tipo dado en primera posición, ignorando el tipo de la expresión envuelta. Por ejemplo:
+<code scheme>
+>(typecheck '{coerce Num #t})
+'Num
+>(typecheck '{+ {coerce Num {if #t 2 #t}} 3})
+'Num
+>(typecheck '{coerce Num {+ 1 #t}})
+'Num
+</code>
+Note que compilar una coerción significa "botar" el coerce, dejando solo la expresión envuelta. Compruebe lo que pasa cuando hacen una coerción errada y ejecutan el programa compilado.
+===== Bonus: Safe Coerce [+1pt] =====
+//Recuerde: esta pregunta es opcional, si la hace, se entrega en la carpeta C//
+Para evitar que una coerción invalida lleve la máquina de ejecución a un estado errado, se le pide que modifiquen su tarea para que las coerciones sean safe: tal como un cast en Java, se verifica dinámicamente que el tipo real del valor es compatible con el tipo de la coerción.