Differences

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

--- teaching:cc4101:tareas:2017-2:tarea2 [2017/09/19 18:16] – folmedo
+++ teaching:cc4101:tareas:2017-2:tarea2 [2017/10/02 18:41] (current) – [Tareas a realizar] folmedo
@@ Line 1: / Line 1: @@
 ====== Tarea 2 ======
-Esta tarea se distribuye con dos ficheros base.rkt y tests.rkt ({{ :teaching:cc4101:tareas:2017-2:base-2017-2-t1.zip |base tarea 2}}). Considere las definiciones del archivo base.rkt y escriba sus funciones en él. Escriba sus tests en el archivo tests.rkt adjunto. Ambos ficheros deben ser entregados vía U-Cursos. Los tests forman parte de su evaluación!
+Esta tarea se distribuye con dos ficheros base.rkt y tests.rkt ({{ :teaching:cc4101:resources:tareas:2017-2:base-2017-2-t2.zip |base tarea 2}}). Considere las definiciones del archivo base.rkt y escriba sus funciones en él. Escriba sus tests en el archivo tests.rkt adjunto. Ambos ficheros 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.
 ===== Presentación del Lenguaje =====
@@ Line 11: / Line 10: @@
   * donde se puedan definir **tipos inductivos** propios (los únicos valores atómicos del lenguaje van a ser de algún tipo definido por el usuario), y
-  * que soporte funciones de primera clase de **múltiples argumentos** y **anotaciones de tipo**.
+  * que soporte funciones de **múltiples argumentos** y **anotaciones de tipo**.
@@ Line 19: / Line 18: @@
 <prog>    ::= (<def>* <expr>)
-<def>     ::= (deftype <id> (<id> : <type>)+)
+<def>     ::= (deftype <id> (<id> : <type>)+)   ;tipo inductivo
-            | (def <id> (<id> : <type>)* : <type> <expr>)
+            | (def <id> (<id> : <type>)* : <type> <expr>)   ;función de primer orden
 <type>    ::= <id>
             | (<type>+ -> <type>)
-<expr>    ::= <id>
+<expr>    ::= <id>    ;identificador
-            | (fun (<id> : <type>)+ <expr>)
+            | (fun (<id> : <type>)+ <expr>)    ;función (anónima) de primera clase
-            | (match <expr> (<case>+))
+            | (match <expr> (<case>+))    ;pattern matching
-            | (<expr> <expr>*)
+            | (<expr> <expr>*)    ;aplicación
 <case>    ::= (case <pattern> => <expr>)
-<pattern> ::= <id>
+<pattern> ::= <id>    ;matcheo sobre un identificador
-             | (<id> <id>*)
+             | (<id> <id>*)    ;matcheo sobre (la aplicación de) un constructor
 </code>
@@ Line 55: / Line 54: @@
 Al ser aplicados, cada constructor genera estructuras de tipo ''nat''. Puede representar sus estructuras como le parezca conveniente pero la función ''run'' siempre debe retornar un String con el tipo correspondiente como en los ejemplos.
-Observe que existen dos tipos de constructores posibles: aquellos con argumentos y aquellos sin argumentos. En el ejemplo, ''O'' corresponde a un constructor que no requiere argumentos y construye un elemento de tipo ''nat''; ''(O : nat)'' es azúcar sintáctico para una función de tipo ''() -> nat'' (esto justifica que la cuarta regla de producción del símbolo no terminal ''<expr>'' sea ''<expr> ::= (<expr> <expr>*)'' y no ''<expr> ::= (<expr> <expr>+)''). El constructor ''S'' usa, en cambio, un elemento de tipo ''nat'' para construir otro elemento de tipo ''nat''.
+Observe que existen dos tipos de constructores posibles: aquellos con argumentos y aquellos sin argumentos. En el ejemplo, ''O'' corresponde a un constructor que no requiere argumentos y construye un elemento de tipo ''nat''. En la salida del intérprete,  ''(O : nat)'' es azúcar sintáctico para una función de tipo ''() -> nat''. Observe, además, que la cuarta regla de producción ''<expr> ::= (<expr> <expr>*)''
+del símbolo no terminal ''<expr>'' permite la aplicación de funciones sin ningún argumento, y por lo tanto ''(O)'' es una expresión bien definida de nuestro lenguaje. El constructor ''S'' usa, en cambio, un elemento de tipo ''nat'' para construir otro elemento de tipo ''nat''.
@@ Line 103: / Line 103: @@
                 (match b
                  ((case (t) => (f)))))
-       (not {f)))
+       (not (f)))
    "match error")
 </code>
@@ Line 129: / Line 129: @@
 > "(t) : bool"
 </code>
+Si un patrón contiene múltiples ocurrencias de un identificador, todas las ocurrencias deben matchear contra el mismo valor (//non-linear pattern matching//). Observe además que la segunda regla de producción del símbolo no terminal ''<pattern>'' es ''<pattern> ::= (<id> <id>*)'' (y no ''<pattern> ::= (<id> <pattern>*)''), por lo que no se requiere soportar patrones anidados.
 === Recursión y múltiples argumentos ===
@@ Line 156: / Line 158: @@
 === Funciones de primera clase ===
-Las funciones de primera clase se introducen con la cláusula ''fun'', pueden tener múltiples argumentos, y a la salida del intérprete se representan con  el símbolo lambda:
+Las funciones de primera clase se introducen con la cláusula ''fun'' y también pueden tener múltiples argumentos con anotaciones de tipo. A la salida del intérprete, toda función se debe representar con el símbolo lambda:
 <code scheme>
@@ Line 176: / Line 178: @@
 == P2 (1.25 Pt) ==
-Defina la función **''%%parser :: s-expr -> Prog%%''** que parsea el lenguaje. El parser debe tomar un programa fuente y transformarlo en su representación abstracta.
+Defina la función **''%%parser :: s-expr -> Prog%%''** que parsea el lenguaje. El parser debe tomar un programa fuente (recuerde que un programa es una lista de definiciones seguida de una expresión) y transformarlo en su representación abstracta.
 Al momento de parsear expresiones de la forma ''w+'' o ''w*'' le puede resultar de utilidad los patrones de la forma ''...'' y ''..k'' que ofrece Scheme. Por ejemplo
@@ Line 198: / Line 200: @@
 </code>
-<note important>Para aclarar cualquier duda sobre el funcionamiento de dichas características, **consulte la documentación de Racket** al respecto [[https://docs.racket-lang.org/reference/match.html|aquí]]</note>
+<note important>Para aclarar cualquier duda sobre el funcionamiento de dichas características, **consulte la documentación de Racket** al respecto [[https://docs.racket-lang.org/reference/match.html|aquí]].</note>
-== P3 (2.25 Pt) ==
+== P3 (2.50 Pt) ==
-Defina la función **''%%interp :: Expr x Env -> Val%%''** que evalúa una expresión bajo un régimen de reducción eager, usando los bindings provistos por el entorno.
+Defina la función **''%%interp :: Expr x Env -> Val%%''** que evalúa una expresión bajo un régimen de reducción eager, usando los bindings provistos por el entorno. Se requiere que el lenguaje soporte recursión para las funciones de primer orden (es decir, las definidas a través de un ''def'').
-== P4 (1.75 Pt) ==
+**Ayuda. ** Piense si el soporte de recursión en las funciones de primer orden requiere algún tratamiento especial o no.
+== P4 (1.50 Pt) ==
 Defina la función **''%%run :: s-expr -> String%%''** que toma un programa fuente y retorna la representación en String del valor resultante de la interpretación con su tipo anotado. Informalmente, los principales pasos de la  función ''run'' serán los siguientes:
-  * Construir un entorno inicial que contenga los bindings correspondientes para cada constructor de los tipos inductivos que se hayan definidos (a través de un ''deftype'') y de las funciones que se hayan definido (a través de un ''def''). Piense bien qué información necesita almacenar en el entorno para cada uno de ellos.
+  * Construir un entorno inicial que contenga los bindings correspondientes para cada constructor de los tipos inductivos que se hayan definido (a través de un ''deftype'') y de las funciones que se hayan definido (a través de un ''def''). Piense bien qué información necesita almacenar en el entorno para cada uno de ellos.
   * Evaluar la expresión "principal" del programa en ese entorno inicial (recuerde que un programa es una lista de definiciones seguida de una expresión "principal").
   * Transformar el resultado de esa evaluación en un String, como se muestra en los ejemplos.
-**Nota**: Observe que la definición de funciones con ''def'' permite múltiples argumentos y por tanto el constructor de tipos ''->'' recibe una lista de tipos en la entrada. Puede asumir que para toda la tarea nunca se van a entregar dos argumentos con el mismo nombre.
+**Nota**: Recuerde que la definición de funciones permiten múltiples argumentos. Puede asumir para toda la tarea que nunca se van a entregar dos argumentos con el mismo nombre.
-===== Tests =====
-<code scheme>
-(terminate '{{deftype bool
-                {t : bool}
-                {f : bool}}
-             {deftype nat
-                {O : nat}
-                {S : {nat -> nat}}}
-             {def even {n : nat} : bool
-                    {match n
-                      {{case {O} => {t}}
-                       {case {S n1} => {match n1
-                                         {{case {O} => {f}}
-                                          {case {S n2} => {even n2}}}}}}}}
-             {even {S {S {O}}}}})
-> "terminate"
-</code>