Differences
This shows you the differences between two versions of the page.
Previous revision | |||
— | teaching:cc4101:tareas:2018-1:tarea1 [2020/03/09 17:51] (current) – ↷ Page moved from teaching:cc4101:tareas:2018-1_x:tarea1 to teaching:cc4101:tareas:2018-1:tarea1 etanter | ||
---|---|---|---|
Line 1: | Line 1: | ||
+ | ====== Tarea 1 (Entrega: 30 de abril de 2018) ====== | ||
+ | |||
+ | |||
+ | Esta tarea se distribuye con un archivo zip {{ : | ||
+ | |||
+ | Deben entregar via U-cursos **un archivo .zip** que contenga los archivos main.rkt y tests.rkt. | ||
+ | |||
+ | <note important> | ||
+ | |||
+ | **¡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: | ||
+ | < | ||
+ | | <id> | ||
+ | | {+ < | ||
+ | | {with {<id> : < | ||
+ | | {fun {<id> : < | ||
+ | | {< | ||
+ | |||
+ | < | ||
+ | | {< | ||
+ | </ | ||
+ | Note que '' | ||
+ | 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}} | ||
+ | </ | ||
+ | |||
+ | * (0.3) Defina la función '' | ||
+ | > (parse-type '{{Num -> Num} -> Num}) | ||
+ | (TFun (TFun (TNum) (TNum)) (TNum)) | ||
+ | |||
+ | > (parse-type '{Num -> }) | ||
+ | "Parse error" | ||
+ | </ | ||
+ | * (0.9) Defina la función '' | ||
+ | > (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)) | ||
+ | </ | ||
+ | |||
+ | **Note que se usa '' | ||
+ | |||
+ | * (0.3) Defina la función '' | ||
+ | > (prettify (TNum)) | ||
+ | 'Num | ||
+ | |||
+ | > (prettify (TFun (TNum) (TFun (TNum) (TNum))) | ||
+ | '(Num -> (Num -> Num)) | ||
+ | </ | ||
+ | |||
+ | ===== 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 '' | ||
+ | * 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 < | ||
+ | </ | ||
+ | |||
+ | 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 < | ||
+ | </ | ||
+ | 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"</ | ||
+ | |||
+ | **Note que debe manejar identificadores adecuadamente, | ||
+ | |||
+ | * (0.5) Implemente la función '' | ||
+ | |||
+ | <code scheme> | ||
+ | > | ||
+ | 'Num | ||
+ | |||
+ | > | ||
+ | '{Num -> Num} | ||
+ | |||
+ | > | ||
+ | "Type error in expression + position 2: expected Num found {Num -> Num}" | ||
+ | |||
+ | |||
+ | </ | ||
+ | |||
+ | |||
+ | |||
+ | |||
+ | |||
+ | ===== 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:// | ||
+ | La función '' | ||
+ | > (machine (list (INT-CONST 6) (INT-CONST 1) (ADD))) | ||
+ | 7 | ||
+ | > (machine (list (INT-CONST 3) (CLOSURE (list (ACCESS 0) (RETURN))) (APPLY))) | ||
+ | 3 | ||
+ | </ | ||
+ | **Tome un tiempo para experimentar con la función '' | ||
+ | ==== Í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:// | ||
+ | * (1.5) Implemente la función '' | ||
+ | **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 | ||
+ | | ||
+ | {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" | ||
+ | </ | ||
+ | ==== 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: | ||
+ | |||
+ | C(n) = INT-CONST n | ||
+ | C({+ a1 a2}) = C(a2); | ||
+ | C({f a}) = C(a); C(f); APPLY | ||
+ | |||
+ | </ | ||
+ | |||
+ | La compilación de un nodo '' | ||
+ | < | ||
+ | C(n) = ACCESS n | ||
+ | |||
+ | </ | ||
+ | La compilación de una función puede ser inferida del ejemplo a continuación: | ||
+ | > (compile (deBruijn (parse '{{fun {x : Num} : Num | ||
+ | {+ x 10}} {+ 2 3}}))) | ||
+ | (list | ||
+ | | ||
+ | | ||
+ | (ADD) | ||
+ | | ||
+ | | ||
+ | </ | ||
+ | |||
+ | |||
+ | * (1.0) Implemente la función '' | ||
+ | |||
+ | * (0.5) Implemente la función '' | ||
+ | |||
+ | |||