Differences

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

--- teaching:cc4101:tareas:2016-1:tarea1 [2016/03/28 17:49] – [Índices De Bruijn] 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 1 ======
+====== Tarea 1 (Entrega: 20 de Abril 2016) ======
-Esta tarea se distribuye con tres ficheros start.rkt, machine.rkt y tests.rkt (mediante U-Cursos). Considere las definiciones del archivo machine.rkt (NO! modifique el archivo machine.rkt) y escriba las funciones pedidias en él archivo start.rkt. Escriba sus tests en el archivo test.rkt adjunto. Ambos ficheros (start.rkt y test-rkt) deben ser entregados vía U-Cursos. Los tests forman parte de su evaluación!
-Consulte las normas de entrega de tareas en http://pleiad.cl/teaching/cc4101.
-===== (1.0) Funciones de primera clase con tipos declarados =====
+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>
@@ Line 16: / Line 27: @@
          | {not <expr>}
          | {if <expr> <expr> <expr>}
-         | {with : <TYPE> {<id> : <TYPE> <expr>} <expr>}
+         | {with {<id> : <type> <expr>} <expr>}
-         | {fun {<id> : <TYPE>} : <TYPE> <expr>}
+         | {fun {<id> : <type>} [: <type>] <expr>}
          | {<expr> <expr>}
-<TYPE> ::= Num
+<type> ::= Num
          | Bool
-         | {<TYPE> -> <TYPE>}
+         | {<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}}
-  - (0.4) Defina la función ''%%(parse-t s-expr)%%'' que parsea solo la gramática de tipos que se inicia del no terminal <TYPE>. Ademas en caso de error, debe retornar el error "PARSE ERROR" <code scheme>
+{fun {x : Num} : Num
-> (parse-t '{{Num -> Num} -> Bool})
+  {+ 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-t '{{Num ->  })
+> (parse-type '{Num ->  })
-PARSE ERROR
+"Parse error"
 </code>
-  - (0.6) Defina la función ''%%(parse expr)%%'' para que acepte la gramática con números, booleans y funciones de primera clase con tipos. Utilice la función ''%%(parse-t s-expr)%%'' en los puntos donde deba identificar tipos. La función ''%%parse%%'' debe reemplazar el ''%%with%%'' por una aplicación de función como se ha visto en clases <code scheme>
+  - (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} : Bool #f})
+> (parse '{fun {x : Num} : Num {+ x 1}})
-(fun 'x (TNum) (bool #f) (TBool))
+(fun 'x (TNum) (add (id 'x) (num 1)) (TNum))
-> (parse '{with : Num {y : Num 2}
+> (parse '{with {y : Num 2}
-                                 {+ x y}})
+             {+ x y}})
-(app (fun 'y (TNum) (add (id 'x) (id 'y)) (TNum)) (num 2))
+(app (fun 'y (TNum) (add (id 'x) (id 'y)) #f) (num 2))
 </code>
-===== (2.0) Compilación =====
+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>
@@ Line 48: / Line 74: @@
 ==== Í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.
+  * (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 usar una función auxiliar
+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 : Num {x : Num 1}
+   (parse '{+ 1 {with {x : Num 1}
-                           {with : Num {y : Num 2}
+                           {with {y : Num 2}
                                  {+ x y}}}}))
 (add
@@ Line 59: / Line 86: @@
  (app
   (fun-db
-   (app (fun-db (add (acc 1) (acc 0)) (TFun (TNum) (TNum))) (num 2))
+   (app (fun-db (add (acc 1) (acc 0))) (num 2)))
-   (TFun (TNum) (TNum)))
   (num 1)))
 > (deBruijn (add (num 1) (id 'x)))
-;Arroja error "UNBOUND IDENTIFIER"
+"Free identifier: x"
 </code>
 ==== De AST a código de máquina ====
@@ Line 70: / Line 96: @@
 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(n) = INT-CONST n
-C(b) -> BOOL-CONST b
+C(b) = BOOL-CONST b
-C(n) -> ACCESS n
+C(n) = ACCESS n
 C({+ a1 a2}) = C(a2);C(a1);ADD
 C({- a1 a2}) = C(a2);C(a1);SUB
@@ Line 82: / Line 108: @@
 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>
@@ Line 90: / Line 117: @@
  (INT-CONST 2)
  (ADD)
- (CLOSURE (list (INT-CONST 10) (ACCESS 0) (LESS) (RETURN)) (MTFun (MTNum) (MTBool)))
+ (CLOSURE (list (INT-CONST 10) (ACCESS 0) (LESS) (RETURN)))
  (APPLY))
 </code>
-En el ejemplo anterior se puede notar que los tipos que entiende la máquina no se crean con los constructores de ''%%Type%%''. Los tipos en la máquina esta definidos con el ''%%deftype MType%%'' por lo que debe hacerse una transformación de los tipos de ''%%Type%%'' a ''%%MType%%''. Las reglas para la transformación son:
-     * ''%%TNum%%'' a ''%%MTum%%''
-     * ''%%TBool%%'' a ''%%MTBool%%''
+  * (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.
-     * ''%%TFun%%'' a ''%%MTFun%%'' aplicando la transformación recursivamente al tipo del argumento y al tipo de retorno
-  - (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) Sistemas de Tipos Simple =====
+===== 3. Verificación de Tipos [1.5pt] =====
 Se implementará el chequeo de tipos de una expresión en presencia de funciones de primera clase.
-  - Implemente la función ''%%(typeof expr)%%'' que recibe un nodo del AST y retorna el tipo correspondiente a la expresión o falla con TYPE_ERROR en caso de que la expresión no sea valida por validación de tipos considerando lo siguiente:
+  * (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 una función se válida que la expresión del cuerpo tenga el mismo tipo declarado en el retorno de la función. En caso de pasar la validación el tipo resultante es ''%%(TFun targ tbody)%%'', donde ''%%targ%%'' es el tipo del argumento y ''%%tbody%%'' es el tipo de retorno de la función.
+     * 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 la aplicación de función se valida que el primer argumento es efectivamente una función y que el tipo del segundo argumento de la aplicación (argumento real) coincide con el tipo del argumento (formal) de la función. En dicho caso la aplicación tiene el tipo del retorno de la función.
+     * 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.
-  <code scheme>
+     * 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}))
-  ;Arroja error "TYPE_ERROR"
+  "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>
-     * 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 el mensaje de error "TYPE_ERROR"
+    * (0.3) Implemente la función ''%%(typecheck s-expr)%%'' que retorna el tipo de un programa, en un formato legible:
-===== (1.5) Sistema de tipos con relación de subtipos =====
+<code scheme>
-Vamos a introducir el tipo Any a nuestro lenguaje. Esto significa que vamos a comenzar a considerar relaciones de subtipo. En la literatura relacionada, la relación de subtipos se escribe ''%%A <: B%%'' y se lee como A es subtipo de B.
+>(typecheck '3)
-==== Tipos Simples ====
+'Num
-Considere para esta pregunta las relaciones ''%%Num <: Any%%'' y ''%%Bool <: Any%%'' y que para todo tipo A se tiene ''%%A%%'' <: A.
-Implemente la función ''%%(typeof-with-sub expr)%%'' que recibe un nodo del AST y retorna el tipo correspondiente a el o falla con ''%%TYPE_ERROR%%'' en caso de que la expresión no sea válida. Considere que ''%%(typeof-with-sub expr)%%'' se comporta igual que la función ''%%(typeof expr)%%'' de la pregunta anterior, salvo por:
+>(typecheck  '{fun {f : Num} : Bool #t})
-  * La existencia de ''%%Any%%'' permite tipear ''%%{if #t 1 #f}%%'' como del tipo ''%%TAny%%''((variante del tipo Type para Any)). Es decir que frente a tipos distintos en las ramas el resultado es ''%%TAny%%''.
+'{Num -> Bool}
-  * En la definición de función, el cuerpo puede ser subtipo del tipo declarado de salida de la función
-  * En la aplicación de función, el tipo del argumento puede ser subtipo del tipo declarado del argumento de la función.
+>(typecheck  '{+ 2 #t})
-==== Subtipos de funciones =====
+  "Type error in expression + position 2: expected Num found Bool"
-En esta sección considere que ''%%A -> B <: Any%%''. La noción de subtipos de funciones es muy simple y nos permite expresar relaciones con otras funciones. En esta tarea vamos a soportar: ''%%A -> B <: C -> D%%'' si ''%%B <: D%%'' y ''%%C <: A%%''. Veamos en acción esta relación <code scheme>
-{with : Any {f : {Num -> Num}
+>(typecheck  '{if #t 1 #t})
-                  {fun {x : Num} : Num x}}
+  "Type error in expression if position 3: expected Num found Bool"
-         {with : Any {g : {Num -> Any}
-                        {fun {x : Num} : Any #f}}
+</code>
-               {with : Any {applyTo1 : {{Num -> Any} -> Any}
-                                     {fun {x : {Num -> Any}} : Any {x 1}}}
+  * (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.
-                     {applyTo1 g}}}}
+===== 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>
-En este caso reemplazar ''%%g%%'' por ''%%f%%'' en el argumento de ''%%applyTo1%%'', es válido pues ''%%f%%'' es más específico en su tipo de retorno, por lo que cualquier función que acepta la salida de ''%%g%%'' necesariamente acepta la salida de ''%%f%%''. <code scheme>
+es rechazado por el sistema de tipo, ya que ''%%{{fun {x : Any} x} 1}%%'' tiene el tipo ''%%Any%%''.
-{with : Num {f : {Num -> Num}
-                  {fun {x : Num} : Num x}}
+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.
-         {with : Num {h : {Any -> Num}
-                        {fun {x : Any} : Num 5}}
+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).
-               {with : Num {applyTo1 : {{Num -> Num} -> Num}
-                                     {fun {x : {Num -> Num}} : Num {x 1}}}
+    * (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:
-                     {applyTo1 f}}}}
-</code>
+<code scheme>
-Aquí ocurre que por el tipo del argumento, reemplazar en esa expresión ''%%f%%'' por ''%%h%%'' también es válido pues si ''%%f%%'' puede ser aplicado a un ''%%Num%%'', con mayor razón una función que espera un tipo más general, en este caso ''%%Any%%''.
+>(typecheck '{coerce Num #t})
-Extienda la función ''%%typeof-with-sub%%'' para que incluya esta relación de subtipos de funciones
+'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//
-====(0.5) Typed compile ====
+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.
-Implemente la función ''%%(typed-compile s-expr)%%'' que se encarga de todo el proceso de generación de código desde una ''%%S-Expr%%'', considerando el parsing, la nueva 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.