Differences

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

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
teaching:cc4101:tareas:xyz:tarea1b [2024/04/08 14:55] – [Parte 1. Lenguaje con funciones de primer orden (1.5 ptos.)] gricciteaching:cc4101:tareas:xyz:tarea1b [2024/04/30 18:08] (current) – gricci
Line 1: Line 1:
-====== Tarea 1b (Entrega: Jueves 18 de Abril de 2023 - fecha por confirmar) ======+====== Tarea 1b (Entrega: Domingo 21 de Abril de 2024) ======
  
 ==== Lenguaje con tipos estáticos ==== ==== Lenguaje con tipos estáticos ====
Line 5: Line 5:
 Ya se habrán dado cuenta que ciertos lenguajes tienen tipos estáticos (C/C++, Java, C#, Scala, etc.) y otros tienen tipos dinámicos (Python, Racket, JavaScript, etc.). Ya se habrán dado cuenta que ciertos lenguajes tienen tipos estáticos (C/C++, Java, C#, Scala, etc.) y otros tienen tipos dinámicos (Python, Racket, JavaScript, etc.).
  
-En esta tarea van a implementar un lenguaje simple con funciones de primer orden, tipos de datos básicos y pares. Para implementar este lenguaje necesitaremos un parser (lo implementamos en la tarea 1a), y un interprete, dividiremos el desarrollo de esta tarea en dos partes (más una opcional). Primero, el lenguaje contará sólo con chequeo dinámico de tipos (parte 1), para luego agregar verificación de tipos estáticos (parte 2). Opcionalmente (como bonus), puede agregar contratos dinámicos para funciones (parte 3). +En esta tarea van a implementar un lenguaje simple con funciones de primer orden, tipos de datos básicos y pares. Para implementar este lenguaje necesitaremos un parser (lo implementamos en la tarea 1a), y un intérprete, dividiremos el desarrollo de esta tarea en dos partes (más una opcional). Primero, el lenguaje contará sólo con chequeo dinámico de tipos (parte 1), para luego agregar verificación de tipos estáticos (parte 2). Opcionalmente (como bonus), puede agregar contratos dinámicos para funciones (parte 3). 
  
 ---- ----
Line 14: Line 14:
 </note> </note>
  
 +**Distribución de Puntaje**
  
-Deben entregar via U-cursos **un archivo .zip** que contenga los siguientes archivos: ''{{ :teaching:cc4101:tareas:2024-1:p1.rkt |p1.rkt}}'', ''{{ :teaching:cc4101:tareas:2024-1:p1-test.rkt |p1-test.rkt}}'', ''{{ :teaching:cc4101:tareas:2024-1:p2.rkt |p2.rkt}}'', ''{{ :teaching:cc4101:tareas:2024-1:p2-test.rkt |p2-test.rkt}}'', archivos que deberán contener las funcionalidades solicitadas en cada pregunta y los tests respectivos.+Esta tarea tiene **4 pts** en total, que se dividen de la siguiente manera: 
 +  * 3 pts por implementación (subdividido como especifica el enunciado). 
 +  * 0.5 pts para testing. 
 +  * 0.5 pts para calidad de código.
  
-Si lo desea, puede obtener un bonus resolviendo la tercera parte, que es opcional: ''{{ :teaching:cc4101:tareas:2024-1:p3.rkt |p3.rkt}}'' y ''{{ :teaching:cc4101:tareas:2024-1:p3-test.rkt |p3-test.rkt}}''. Más detalles al final del documento.+Deben entregar via U-cursos **un archivo .zip** que contenga los siguientes archivos: ''{{ :teaching:cc4101:tareas:2024-1:tarea1b:p1.rkt |p1.rkt}}'', ''{{ :teaching:cc4101:tareas:2024-1:tarea1b:p1-test.rkt |p1-test.rkt}}'', ''{{ :teaching:cc4101:tareas:2024-1:tarea1b:p2.rkt |p2.rkt}}'', ''{{ :teaching:cc4101:tareas:2024-1:tarea1b:p2-test.rkt |p2-test.rkt}}'', archivos que deberán contener las funcionalidades solicitadas en cada pregunta y los tests respectivos. 
 + 
 +Si lo desea, puede obtener un bonus resolviendo la tercera parte, que es opcional: ''{{ :teaching:cc4101:tareas:2024-1:tarea1b:p3.rkt |p3.rkt}}'' y ''{{ :teaching:cc4101:tareas:2024-1:tarea1b:p3-test.rkt |p3-test.rkt}}''. Más detalles al final del documento. 
 + 
 +**Nota:** Es libre de implementar el intérprete usando sustitución inmediata o diferida (con ambientes), en cuyo caso podría serle útil el archivo {{ :teaching:cc4101:tareas:2023-1:env.rkt |env.rkt}}
  
 Deben entregar vía U-Cursos **un único archivo .zip** que contenga todos los archivos de su entrega. Deben entregar vía U-Cursos **un único archivo .zip** que contenga todos los archivos de su entrega.
  
 <note important> <note important>
-  * Recuerde incluir tests con cobertura de todos los casos relevantes para todas las funciones que implemente, pues esto se considerará en la evaluación.+  * Recuerde incluir tests con cobertura de todos los casos relevantes para todas las funciones que implemente y aquellas que extienda, pues esto se considerará en la evaluación.
 </note> </note>
-===== Parte 1. Lenguaje con funciones de primer orden (1.5 ptos.) ===== + 
 +===== Parte 1. Lenguaje con funciones de primer orden (1.1 ptos.) ===== 
  
 En esta parte, vamos a implementar un lenguaje que incluye primitivas útiles (números, booleanos, pares, y operadores simples), identificadores locales (''with'' con una cantidad arbitraria de identificadores), y definiciones de funciones //top-level// de múltiples argumentos. En esta parte, vamos a implementar un lenguaje que incluye primitivas útiles (números, booleanos, pares, y operadores simples), identificadores locales (''with'' con una cantidad arbitraria de identificadores), y definiciones de funciones //top-level// de múltiples argumentos.
Line 52: Line 61:
            | {<id> <expr>*}            | {<id> <expr>*}
  
-<binding> ::= (<id> <expr>)+<binding> ::= {<id> <expr>}
                        
 </code> </code>
Line 111: Line 120:
   }   }
   </code>   </code>
 +Además de lo anterior, asumiremos por simplicidad que en los bindings de un mismo ''with'' no pueden haber repeticiones/reintroducciones de identificadores. **No es necesario que verifique este punto**, puede simplemente asumir que es parte del contrato. Por ejemplo, el comportamiento del siguiente programa estaría indefinido:
 +<code scheme>
 +  {
 +     {with {{x 2}
 +            {x 4}}
 +        x}
 +  }
 +</code>
   * Debe verificar en tiempo de ejecución que los argumentos de los operadores numéricos sean numéricos, que los argumentos de los operadores booleanos sean booleanos, y que los argumentos de los operadores de pares sean pares (En la parte 2 se alineará la verificación dinámica con la verificación estática).   * Debe verificar en tiempo de ejecución que los argumentos de los operadores numéricos sean numéricos, que los argumentos de los operadores booleanos sean booleanos, y que los argumentos de los operadores de pares sean pares (En la parte 2 se alineará la verificación dinámica con la verificación estática).
   * Considere que la igualdad solo es válida sobre números.   * Considere que la igualdad solo es válida sobre números.
Line 172: Line 189:
 Teniendo en cuenta todo lo descrito anteriormente, implemente las siguientes funciones: Teniendo en cuenta todo lo descrito anteriormente, implemente las siguientes funciones:
  
-  - **[0 pts]** ''interp :: Expr List[Fundef] -> Val or error'', que interpreta una expresión considerando una lista de funciones definidas al top-level. +  - **[0.9 pts]** ''interp :: Expr List[Fundef] -> Val or error'', que interpreta una expresión considerando una lista de funciones definidas al top-level. Si lo desea, puede implementar ''interp'' usando ambientes (sustitución diferida). Recuerde actualizar la firma de la función si elige dicha opción. 
-  - **[0 pts]** ''run :: s-expr -> Val or error'', que toma un programa escrito en sintaxis concreta, lo parsea e interpreta.+  - **[0.2 pts]** ''run :: s-expr -> Val or error'', que toma un programa escrito en sintaxis concreta, lo parsea e interpreta.
  
 ----- -----
-===== Parte 2. Verificación estática de tipos (2.5 ptos.) ===== + 
 +===== Parte 2. Verificación estática de tipos (1.9 ptos.) ===== 
  
 En esta parte vamos a extender el lenguaje con anotaciones de tipos y verificación estática de ellos. Las diferencias en la sintaxis del lenguaje respecto de la parte anterior son: En esta parte vamos a extender el lenguaje con anotaciones de tipos y verificación estática de ellos. Las diferencias en la sintaxis del lenguaje respecto de la parte anterior son:
Line 186: Line 204:
 ;; <prog> y <expr> no cambian ;; <prog> y <expr> no cambian
  
-<fundef> ::= {define {<id> {arg}*} : <type> <expr>} +<fundef> ::= {define {<id> <arg>*} : <type> <expr>} 
    
 <arg>    ::= {<id> : <type>}  <arg>    ::= {<id> : <type>} 
Line 205: Line 223:
      {+ x y}}      {+ x y}}
 } }
 +</code> 
 +<code scheme>
 { {
   {with {{x 5}}   {with {{x 5}}
Line 211: Line 230:
         {+ x y}}         {+ x y}}
 } }
 +</code> 
 +<code scheme>
 { {
   {define {add-pair {p : {Pair Num Num}} {x : Num}} : {Pair Num Num}    {define {add-pair {p : {Pair Num Num}} {x : Num}} : {Pair Num Num} 
Line 217: Line 237:
   {add-pair {cons 1 1} 1}   {add-pair {cons 1 1} 1}
 } }
 +</code> 
 +<code scheme>
 { {
   {define {id {x : Num}} : Num x}   {define {id {x : Num}} : Num x}
   {id 5}   {id 5}
 } }
 +</code> 
 +<code scheme>
 { {
   {define {sum {x : Num} {y : Num} {z : Num}} : Num    {define {sum {x : Num} {y : Num} {z : Num}} : Num 
Line 232: Line 254:
      {sum x {fst y} {cadr y}} }      {sum x {fst y} {cadr y}} }
 } }
- 
 </code> </code>
  
Line 238: Line 259:
  
 Note que se agregó el nodo ''<arg>'' al BNF, el cual especifica la sintaxis concreta de un argumento de función. Note que se agregó el nodo ''<arg>'' al BNF, el cual especifica la sintaxis concreta de un argumento de función.
-  - **[0.0 pts]** Defina el tipo de datos ''Arg'' que representa a un argumento de función en el AST. +  - **[0.1 pts]** Defina el tipo de datos ''Arg'' que representa a un argumento de función en el AST. 
-  - **[0.0 pts]** Implemente la función ''parse-arg'' que parsea un argumento de función. +  - **[0.2 pts]** Implemente la función ''parse-arg'' que parsea un argumento de función. 
-  - **[0.0 pts]** Modifique la función ''parse-fundef'' para que utilice ''parse-arg'' para parsear los argumentos.+  - **[0.1 pts]** Modifique la función ''parse-fundef'' para que utilice ''parse-arg'' para parsear los argumentos.
  
 Además de lo anterior, observe que el nodo ''<binding>'' en el BNF cambió, y ahora puede incluir una anotación opcional de tipo para el identificador que se introduce. Además de lo anterior, observe que el nodo ''<binding>'' en el BNF cambió, y ahora puede incluir una anotación opcional de tipo para el identificador que se introduce.
  
-  - **[0.0 pts]** Modifique el tipo de datos ''Binding'' para que pueda almacenar el tipo del identificador. +  - **[0.1 pts]** Modifique el tipo de datos ''Binding'' para que pueda almacenar el tipo del identificador. 
-  - **[0.0 pts]** Modifique la función ''parse-binding'' para que acepte una anotación opcional de tipo. **Nota:** Cuando no se especifica el tipo, puede guardar el valor ''#f'' en el lugar donde se almacenaría el tipo.+  - **[0.1 pts]** Modifique la función ''parse-binding'' para que acepte una anotación opcional de tipo. **Nota:** Cuando no se especifica el tipo, puede guardar el valor ''#f'' en el lugar donde se almacenaría el tipo.
  
  
Line 251: Line 272:
  
 Para poder realizar un checkeo de tipos estático, necesitaremos: Para poder realizar un checkeo de tipos estático, necesitaremos:
-  - **[0.0 pts]** Implementar la función ''typecheck-expr :: Exp -> Type/err'' que toma una expresión y nos retorna su tipo, o lanza un error. +  - **[0.6 pts]** Implementar la función ''typecheck-expr :: Exp Env List[Fundef] -> Type or error'' que toma una expresión, un ambiente y una lista de definiciones de funciones, y retorna el tipo de la expresión o lanza un error. 
-  - **[0.0 pts]** Implementar ''typecheck-fundef :: Fundef -> Type/err'' que recibe una definición de función de primer orden y nos retorna su tipo, o lanza un error. +  - **[0.4 pts]** Implementar ''typecheck-fundef :: Fundef List[Fundef] -> Type or error'' que recibe una definición de función y una lista de definiciones de funciones, y retorna el tipo de retorno de la función, o lanza un error. 
-  - **[0.0 pts]** Implementar ''typecheck :: Prog -> Type/err'' que toma un programa y nos retorna su tipo, o lanza un error. +  - **[0.2 pts]** Implementar ''typecheck :: Prog -> Type or error'' que toma un programa y nos retorna su tipo, o lanza un error. 
-  - **[0.0 pts]** Extender la función ''run'' para que verifique el tipo del programa (este paso puede fallar) antes de interpretarlo.+  - **[0.1 pts]** Extender la función ''run'' para que verifique el tipo del programa (este paso puede fallar) antes de interpretarlo. Note que tendrá que hacer pequeñas modificaciones a la función ''interp'' para que pueda procesar el nuevo AST con anotaciones de tipo. Unicamente los casos para el ''with'' y aplicaciones de función se verán afectados.
  
  
Line 266: Line 287:
   * Para ''%%with%%'' se verifica que todos los argumentos cumplan con el tipo declarado y el tipo resultante será el del cuerpo de la expresión. Si los identificadores no tienen tipo explícito, entonces se les asigna el de la expresión asociada.   * Para ''%%with%%'' se verifica que todos los argumentos cumplan con el tipo declarado y el tipo resultante será el del cuerpo de la expresión. Si los identificadores no tienen tipo explícito, entonces se les asigna el de la expresión asociada.
   * En la aplicación de función se valida que el número de argumentos coincide, y que el tipo de los argumentos coincide con los tipos esperados de la función aplicada. El tipo resultante de una aplicación es el tipo de retorno de la función aplicada.   * En la aplicación de función se valida que el número de argumentos coincide, y que el tipo de los argumentos coincide con los tipos esperados de la función aplicada. El tipo resultante de una aplicación es el tipo de retorno de la función aplicada.
- 
-**Comportamiento del typecheck**: 
-  * Necesitará almacenar en un ambiente el tipo de las variables introducidas por algún bind para poder completar el typecheck. 
-  * El typecheck de un operador unario o binario verifica que el tipo de los datos que recibe correspondan con los tipos de los datos que se esperan para ese operador. 
-  * El typecheck de un with verifica para cada binding que la expresión cumpla con el tipo declarado para esa variable, en caso de que la variable no tenga un tipo declarado, este se obtiene a partir de la expresión. 
-  * El typecheck de la aplicación de una función de primer orden verifica cumple con la aridad de la función, y que el tipo de los parámetros que recibe correspondan con los tipos declarados en su firma. 
  
 **Para los errores**: **Para los errores**:
-  * Los errores de identificadores libres (o funciones no definidas). Este error debe detectarse estáticamente.+  * Los errores de identificadores libres, funciones no definidas y errores de aridad deben ahora detectarse estáticamente. El formato de los mensajes de error es el mismo que se especificó en la parte 1.
   * Los mensajes de error de tipo detectados estáticamente tienen que seguir el siguiente patrón:    * Los mensajes de error de tipo detectados estáticamente tienen que seguir el siguiente patrón: 
 <code scheme>"Static type error: expected T1 found T2"</code> donde ''T1'' es el tipo esperado y ''T2'' el tipo encontrado. <code scheme>"Static type error: expected T1 found T2"</code> donde ''T1'' es el tipo esperado y ''T2'' el tipo encontrado.
Line 280: Line 295:
 Algunos ejemplos (no representan todos los casos, es de su responsabilidad entregar //test suites// completos): Algunos ejemplos (no representan todos los casos, es de su responsabilidad entregar //test suites// completos):
  <code scheme>  <code scheme>
-  >  (typecheck '{3})+  >  (typecheck (parse-prog '{3}))
   (numT)  </code> <code scheme>   (numT)  </code> <code scheme>
-  > (typecheck '{{define {f {p : Bool}} {if p 23 42}} +  > (typecheck (parse-prog '{{define {f {p : Bool}} {if p 23 42}} 
-                          {f {< 3 4}}})+                             {f {< 3 4}}}))
   (numT) </code> <code scheme>      (numT) </code> <code scheme>   
-  > (typecheck '{{define {one {x : Num}} 1} +  > (typecheck (parse-prog '{{define {one {x : Num}} 1} 
-                          {one #t}})+                             {one #t}}))
   "Static type error: expected Num found Bool" </code> <code scheme>   "Static type error: expected Num found Bool" </code> <code scheme>
-  > (typecheck '{{< 10 #t}})+  > (typecheck (parse-prog  '{{< 10 #t}}))
   "Static type error: operator < expected Num found Bool"</code> <code scheme>   "Static type error: operator < expected Num found Bool"</code> <code scheme>
-   > (typecheck '{{if 73 #t #t}})+   > (typecheck (parse-prog '{{if 73 #t #t}}))
   "Static type error: expected Bool found Num"</code> <code scheme>   "Static type error: expected Bool found Num"</code> <code scheme>
-  > (typecheck '{{with {{x : Num 5} {y : Num #t} {z : Num 42}} +  > (typecheck (parse-prog '{{with {{x : Num 5} 
-                            z}})+                                    {y : Num #t} 
 +                                    {z : Num 42}} 
 +                                 z}}))
   "Static type error: expected Num found Bool"</code>   "Static type error: expected Num found Bool"</code>
  
Line 300: Line 317:
 ---- ----
  
-===== Parte 3. Contratos en funciones de primer orden (por definir) =====+===== Parte 3. Contratos en funciones de primer orden (1 pt. de bonus) =====
  
 <note important> <note important>
-Esta parte es de realización opcional. Si la desarrolla correctamente obtendrá las felicitaciones de su profesor y auxiliares.+Esta parte es de realización **opcional**. Si la desarrolla correctamente obtendrá un bono de **1 pt** que podrán agregar a la nota de cualquiera de las tareas. 
 </note> </note>
  
-Ahora vamos a añadir verificación dinámica mediante contratos a las funciones de nuestro lenguaje. El único cambio en la sintaxis del lenguaje se ve reflejado en la definición de funciones, donde ahora se puede definir además un contrato para cada argumento:+El propósito de esta parte es añadir verificación dinámica mediante contratos a las funciones de nuestro lenguaje. El único cambio en la sintaxis del lenguaje se ve reflejado en la definición de funciones, donde ahora se puede definir además un contrato para cada argumento:
  
 <code scheme> <code scheme>
Line 316: Line 333:
 Un contrato corresponde a un predicado, una función que recibe exactamente un argumento y retorna un booleano. Un ejemplo de programa válido puede ser: Un contrato corresponde a un predicado, una función que recibe exactamente un argumento y retorna un booleano. Un ejemplo de programa válido puede ser:
 <code scheme> <code scheme>
-{{define {positive {x : Num}} {< 0 x}}+{{define {positive {x : Num}} : Bool {< 0 x}}
  {define {sub {x : Num @ positive} {y : Num}} : Num  {define {sub {x : Num @ positive} {y : Num}} : Num
            {- y x}}            {- y x}}
Line 330: Line 347:
 "Runtime contract error: <v> does not satisfy <contract>" "Runtime contract error: <v> does not satisfy <contract>"
 </code> donde ''<v>'' es el valor al que se le aplicó el contrato <contract> el nombre de este. </code> donde ''<v>'' es el valor al que se le aplicó el contrato <contract> el nombre de este.
-  * Una función usada como contrato **debe** aceptar un solo argumento de cualquier tipo válido y **debe** retornar un valor de tipo ''Bool''. En caso de no cumplir esta condición se debe lanzar un error con el siguiente patrón: <code scheme>+  * Una función usada como contrato **debe** aceptar un solo argumento de cualquier tipo válido y **debe** retornar un valor de tipo ''Bool''. Esta verificación debe realizarse estáticamente y, en caso de no cumplir dicha condición, se debe lanzar un error con el siguiente patrón: <code scheme>
 "Static contract error: invalid type for <c>" "Static contract error: invalid type for <c>"
 </code>  donde ''<c>'' es el nombre del contrato que no tipa. </code>  donde ''<c>'' es el nombre del contrato que no tipa.
Line 346: Line 363:
  {+ {pair-div {cons 30 5}} {pair-div {cons 60 0}}}  {+ {pair-div {cons 30 5}} {pair-div {cons 60 0}}}
 } }
-"Runtime contract error: (60,0) does not satisfy pair-non-zero?"+"Runtime contract error: {cons 60 0} does not satisfy pair-non-zero?"
 </code> </code>
  
Line 356: Line 373:
 "Static contract error: invalid type for add" "Static contract error: invalid type for add"
 </code> </code>
 +