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:2025-1:tarea1b [2025/04/05 19:00] – [Parte 1. Lenguaje con funciones de primer orden (1.5 ptos.)] msegurteaching:cc4101:tareas:2025-1:tarea1b [2025/04/09 13:48] (current) – [Tarea 1b (Entrega: 20 de Abril de 2025)] dibanez
Line 1: Line 1:
-====== Tarea 1b (Entrega: TBD) ======+====== Tarea 1b (Entrega: 30 de Abril de 2025) ======
  
 ==== 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 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). +En esta tarea van a implementar un lenguaje simple con funciones de primer orden (es decir, funciones cuya definición es separada de las expresiones normales del lenguaje), tipos de datos básicos y pares. Para implementar este lenguaje necesitaremos un parser (lo implementamos en la tarea 1a), y un intérprete (esta tarea). 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>
  
-Deben entregar via U-cursos **un archivo .zip** que contenga los siguientes archivos: PLACEHOLDER, PLACEHOLDER, PLACEHOLDER, PLACEHOLDER, archivos que deberán contener las funcionalidades solicitadas en cada pregunta y los tests respectivos.+Deben entregar via U-cursos **un archivo .zip** que contenga los siguientes archivos:{{ :teaching:cc4101:tareas:2025-1:t1b:p1.rkt |p1.rkt}}, {{ :teaching:cc4101:tareas:2025-1:t1b:p1-test.rkt |p1-test.rkt}}, {{ :teaching:cc4101:tareas:2025-1:t1b:p2.rkt |p2.rkt}}, {{ :teaching:cc4101:tareas:2025-1:t1b: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: PLACEHOLDER y PLACEHOLDER. Más detalles al final del documento.+Si lo desea, puede obtener un bonus resolviendo la tercera parte, que es opcional: {{ :teaching:cc4101:tareas:2025-1:t1b:p3.rkt |p3.rkt}} y {{ :teaching:cc4101:tareas:2025-1:t1b:p3-test.rkt |pr3-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 PLACEHOLDER.+**Nota:** Le podría ser útil el archivo {{ :teaching:cc4101:tareas:2025-1:t1b: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.
Line 26: Line 26:
 </note> </note>
  
-===== Parte 1. Lenguaje con funciones de primer orden (1.5 ptos.) ===== +===== Parte 1. Lenguaje con funciones de primer orden [1.5 pts.] ===== 
  
-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) con scope léxico, y definiciones de funciones //top-level// de múltiples argumentos.
  
 La gramática BNF del lenguaje se  define a continuación: La gramática BNF del lenguaje se  define a continuación:
Line 37: Line 37:
    
 <expr>   ::= <num> <expr>   ::= <num>
-           | <sym>+           | <id>
            | <bool>            | <bool>
            | {cons <expr> <expr>}            | {cons <expr> <expr>}
-           | {add1 <expr>}+           | {add-one <expr>}
            | {+ <expr> <expr>}            | {+ <expr> <expr>}
            | {- <expr> <expr>}            | {- <expr> <expr>}
Line 52: Line 52:
            | {if <expr> <expr> <expr>}            | {if <expr> <expr> <expr>}
            | {with {<binding>*} <expr>}            | {with {<binding>*} <expr>}
-           | {<sym> <expr>*}+           | {<id> <expr>*}
  
-<binding> ::= {<sym> <expr>}+<binding> ::= {<id> <expr>}
                        
 </code> </code>
  
-Esta gramática es similar a la presentada en la tarea 1a, con las siguientes diferencias. +Esta gramática es similar a la presentada en la tarea 1a, pero se agregan pares. Estos se definen utilizando ''cons''. Las expresiones ''fst'' y ''snd'' permiten obtienen el primer y segundo elemento, respectivamente (similar a ''car'' y ''cdr'' de Racket).
-  * <del>Se agregan dos operadores booleanos extra, estos son ''&&'' y ''||''.</del> -> Se quita +
-  * Se agregan pares, los cuales se definen utilizando ''cons''. Las expresiones ''fst'' y ''snd'' permiten obtienen el primer y segundo elemento, respectivamente (similar a ''car'' y ''cdr'' de Racket).+
  
 Los programas que terminan reducen a valores. Estos pueden ser números, booleanos o pares de valores. Siguiendo las buenas prácticas de desarrollo del curso, se define un tipo de datos inductivo ''Val'' para los valores del lenguaje (provisto en el código fuente de la parte 1).  Los programas que terminan reducen a valores. Estos pueden ser números, booleanos o pares de valores. Siguiendo las buenas prácticas de desarrollo del curso, se define un tipo de datos inductivo ''Val'' para los valores del lenguaje (provisto en el código fuente de la parte 1). 
 +
 +<code scheme>
 +(deftype Val
 +    (numV n)
 +    (boolV b)
 +    (pairV lV rV)
 +)
 +</code> 
  
 Algunos ejemplos de programas válidos para el lenguaje descrito pueden ser: Algunos ejemplos de programas válidos para el lenguaje descrito pueden ser:
Line 182: Line 188:
 Teniendo en cuenta todo lo descrito anteriormente, implemente las siguientes funciones: Teniendo en cuenta todo lo descrito anteriormente, implemente las siguientes funciones:
  
-  - **[1.2 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.+  - **[1.2 pts]** ''interp :: Expr List[Fundef] Env -> Val or error'', que interpreta una expresión considerando una lista de funciones definidas al top-level.
   - **[0.3 pts]** ''run :: s-expr -> Val or error'', que toma un programa escrito en sintaxis concreta, lo parsea e interpreta.   - **[0.3 pts]** ''run :: s-expr -> Val or error'', que toma un programa escrito en sintaxis concreta, lo parsea e interpreta.
  
-<del>El testing recibe **0.3 pts**</del> -> Se quita +----
------+
  
 ===== Parte 2. Verificación estática de tipos (2.5 ptos.) =====  ===== Parte 2. Verificación estática de tipos (2.5 ptos.) ===== 
Line 266: Line 271:
  
 Para poder realizar un checkeo de tipos estático, necesitaremos: Para poder realizar un checkeo de tipos estático, necesitaremos:
-  - **[0.7 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. +  - **[1.0 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.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.6 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.2 pts]** Implementar ''typecheck :: Prog -> Type or error'' 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.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.   - **[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 281: Line 286:
   * 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.
 +  * Note que, cada expresión solo necesita ser checkeada una sola vez, incluso los cuerpos de las funciones.
  
 **Para los errores**: **Para los errores**:
Line 308: Line 314:
  
 ¿Puede efectivamente convencerse de que todo programa que pasa la verificación de tipo no se cae con un error de tipo durante la ejecución? ¿Puede efectivamente convencerse de que todo programa que pasa la verificación de tipo no se cae con un error de tipo durante la ejecución?
- 
-El testing de esta parte recibe **0.5 pts** 
 ---- ----