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:2016-2:tarea2 [2016/10/26 15:46] – [P1 - Estructuras Inductivas y Pattern Matching (2.0pt)] fmossoteaching:cc4101:tareas:2016-2:tarea2 [2016/11/21 11:21] (current) – [P2 - Análisis de Terminación (3.0pt)] fmosso
Line 1: Line 1:
 ====== Tarea 2 ====== ====== Tarea 2 ======
  
-Esta tarea se distribuye con dos ficheros base.rkt y tests.rkt ({{ :teaching:cc4101:resources:tareas:2016-2:base.zip |base tarea 1}}). 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:tareas:2016-2:basetarea220162.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. Consulte las normas de entrega de tareas en http://pleiad.cl/teaching/cc4101.
  
-En esta tarea vamos a construir un lenguaje similar al visto en clases con distintas funcionalidades. Use el archivo base.rkt como punto de partida.+En esta tarea se le pide construir un lenguaje capaz de definir sus propios tipos. Use el archivo base.rkt como punto de partida.
  
-===== P1 - Estructuras Inductivas y Pattern Matching (2.0pt) =====+===== P1 - Estructuras Inductivas y Pattern Matching (3.0pt) =====
  
 En esta primera parte defina un lenguaje con funciones de primera clase de múltiples argumentos, en donde los únicos otros valores son estructuras definibles por el usuario.  En esta primera parte defina un lenguaje con funciones de primera clase de múltiples argumentos, en donde los únicos otros valores son estructuras definibles por el usuario. 
Line 118: Line 118:
 </code> </code>
  
-=== Recursión ===+==== Recursión ====
  
 Funciones definidas con ''def'' pueden ser recursivas y tener más de un argumento. Funciones definidas con ''def'' pueden ser recursivas y tener más de un argumento.
 +
  
 <code scheme> <code scheme>
Line 141: Line 142:
 </code> </code>
  
-=== Funciones ===+==== Funciones ====
  
 Las funciones se representan por el simbolo lambda: Las funciones se representan por el simbolo lambda:
Line 148: Line 149:
           {t : bool}           {t : bool}
           {f : bool}}           {f : bool}}
-       {fun {x : bool} x})+       {fun {x : bool} x}})
 > "λ" > "λ"
 </code> </code>
  
-A continuación se presenta la gramática BNF del lenguaje. 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. +Con esto en mente, defina lo siguiente:
- +
-<code scheme> +
-<prog> ::= {<def>* <expr>} +
- +
-<def> ::= {deftype <id> {<id> : <type>}+} +
-        | {def <id> {<id> : <type>}* : <type> <expr>} +
- +
-<type> ::= <id> +
-         | {<type>+ -> <type>} +
- +
-<expr> ::= <id> +
-         | {fun {<id> : <type>}+ <expr>} +
-         | {match <expr> {<case>+}} +
-         | {<expr> <expr>*} +
- +
-<case> ::= {case <pattern> => <expr>} +
- +
-<pattern> ::= <id> +
-            | {<id> <id>*} +
- +
-</code>+
  
   - Defina el AST para soportar programas del lenguaje. Note que un programa es una lista de definiciones seguida de una expresión. Dos tipos de definiciones son posibles ''deftype'' y ''def''.   - Defina el AST para soportar programas del lenguaje. Note que un programa es una lista de definiciones seguida de una expresión. Dos tipos de definiciones son posibles ''deftype'' y ''def''.
-  - Defina la función ''parser :: s-expr -> Expr'' que parsea el lenguaje +  - Defina la función **''%%parser :: s-expr -> Expr%%''** que parsea el lenguaje 
-  - Defina la función ''interp :: Expr Env -> Val'' que evalua un programa con semántica eager. +  - Defina la función **''%%interp :: Expr x Env -> Val%%''** que evalua un programa con semántica eager. 
-  - 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. Es recomendable definir una función auxiliar que le permita pasar de su representación de estructuras a la notación de los ejemplos con Strings.+  - 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. Es recomendable definir una función auxiliar que le permita pasar de su representación de estructuras a la notación de los ejemplos con Strings.
  
-===== P2 - Sistema de Tipos (2.0pt) =====+**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.
  
-Para el lenguaje de esta tarea, se solicita crear un sistema de tipos. Los tipos del lenguaje corresponden a los tipos definidos con ''deftype'' y a los creados con el constructor de tipos ''->''. 
  
-Las definiciones de funciones llevan anotado el tipo de retorno, pues es necesario para verificar la correctitud de funciones recursivas. 
- 
-Defina un sistema de tipos con la función ''typeof :: s-expr -> String'' que retorna el tipo de un programa o termina en error según los siguientes casos: 
- 
-  - ''(error "TYPE ERROR: wrong argument type")'' : En caso de que algún argumento no tenga el tipo esperado para el tipo de entrada de la función en una aplicación. 
-  - ''(error "TYPE ERROR: application of a non-function")'' : Cuando se intente aplicar un valor que no es función. 
-  - ''(error "TYPE ERROR: non-uniform pattern")'': En caso de que los patrones de un match no sean del mismo tipo. 
-  - ''(error "TYPE ERROR: non-uniform match return type")'': Si los tipos de retorno de match no son del mismo tipo. 
-  - ''(error "TYPE ERROR: incomplete match")'':  Si no todos los constructores de tipo están cubiertos por un match. 
-  - ''(error "TYPE ERROR: wrong return type")'': Si en una definición 'def' el tipo de retorno es distinto al tipo declarado. 
-  - ''(error "TYPE ERROR: redefinition")'': Si existen dos ''deftype'', constructores o ''def'' con el mismo nombre. 
-  - ''(error "TYPE ERROR: incorrect constructor type")'': Si el tipo de salida de un constructor no corresponde al tipo que define su ''deftype''. 
- 
-Nuevamente, el output de la función es un ''String''. Ejemplos: 
- 
-<code scheme> 
-(typeof '{{deftype nat  
-           {O : nat} 
-           {S : {nat -> nat}}} 
-        {O}}) 
-> "nat" 
-</code> 
-Los constructores tienen tipos de función con ''->''. La ausencia de argumentos se representa por ''()'' como sigue: 
-<code scheme> 
-(typeof '{{deftype nat  
-                    {O : nat} 
-                    {S : {nat -> nat}}} 
-                  O}) 
-"() -> nat" 
-</code> 
-<code scheme> 
-(test/exn (typeof '{{deftype bool  
-                         {t : bool} 
-                         {f : bool}} 
-                      {deftype nat  
-                         {O : nat} 
-                         {S : {nat -> nat}}} 
-                      {S {t}}}) 
-          "TYPE ERROR: wrong argument type") 
-</code> 
  
-===== P3 - Análisis de Terminación (2.0pt) =====+===== P2 - Análisis de Terminación (3.0pt) =====
  
-Tener un lenguaje donde los valores son estructuras inductivas permite detectar casos de recursión estructural, lo que permite concluir sintácticamente cuando una función termina. Por ejemplo en el siguiente caso es posible saber que la función ''even'' termina sin ejecutarla, pues sus posibles retornos son valores directos o llamados recursivos con argumentos que corresponden a sub-estructuras:+Tener un lenguaje donde los valores son estructuras inductivas permite detectar casos de recursión estructural, lo que permite concluir sintácticamente cuando una función termina. Por ejemplo, en el siguiente caso es posible saber que la función ''even'' termina sin ejecutarla, pues sus posibles retornos son valores directos o llamados recursivos con argumentos que corresponden a sub-estructuras:
  
 <code scheme> <code scheme>
Line 262: Line 201:
 Pues si bien un caso de ''match'' corresponde a un constructor aplicado sin argumentos, el otro caso corresponde a una llamada donde el argumento no se reduce. Pues si bien un caso de ''match'' corresponde a un constructor aplicado sin argumentos, el otro caso corresponde a una llamada donde el argumento no se reduce.
  
-Implemente la función ''terminate :: s-expr -> String''  que intenta decidir si un programa termina o no. La función ''terminate'' debe verificar cada ''def'' según sigue:+Implemente la función **''terminate :: s-expr -> String''**  que //intenta// decidir si un programa termina o no. La función ''terminate'' debe verificar cada ''def'' según la siguiente lógica:
  
   - Si la función no es recursiva, termina   - Si la función no es recursiva, termina
Line 270: Line 209:
  
  
-Para la realización de está pregunta puede asumir que las verificaciones de tipo ya fueron realizadas. Por ejemplo ya no debe preocuparse de los casos donde no están definidos todos los patrones de un ''match''.+Para está pregunta puede asumir que las verificaciones de tipo ya fueron realizadas. Por ejemplo ya no debe preocuparse de los casos donde no están definidos todos los patrones de un ''match''.
  
 <code scheme> <code scheme>
Line 284: Line 223:
                   {case {S n3} => {match n1                   {case {S n3} => {match n1
                                     {{case {O} =>    {weird n3 {S n1}}}                                     {{case {O} =>    {weird n3 {S n1}}}
-                                     {case {S n4} => {weird n4 n2}}}}}}}}+                                     {case {S n4} => {weird n4 n3}}}}}}}}
              {O}})              {O}})
 > "terminate"              > "terminate"             
 </code> </code>
  
-En el caso anterior existen dos llamadas recursivas a ''weird''. La primera llamada recursiva ''{weird n3 {S n1}}'' disminuye en el primer argumento, pero no necesariamente en el segundo y la segunda llamada recursiva ''{weird n4 n2}'' disminuye en ambos argumentos. Por lo tanto la función reduce en el primer argumento.+En el caso anterior existen dos llamadas recursivas a ''weird''. La primera llamada recursiva ''{weird n3 {S n1}}'' disminuye en el primer argumento, pero no necesariamente en el segundo y la segunda llamada recursiva ''{weird n4 n3}'' disminuye en ambos argumentos. Por lo tanto la función reduce en el primer argumento.
  
 <code scheme> <code scheme>