====== Tarea 2 ======

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 =====


El objetivo de esta tarea es construir un lenguaje 

  * 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 **múltiples argumentos** y **anotaciones de tipo**.


A continuación se presenta la gramática BNF del lenguaje y las especificaciones para los aspectos mas importantes del mismo.

<code scheme>
<prog>    ::= (<def>* <expr>)

<def>     ::= (deftype <id> (<id> : <type>)+)   ;tipo inductivo
            | (def <id> (<id> : <type>)* : <type> <expr>)   ;función de primer orden

<type>    ::= <id>
            | (<type>+ -> <type>)

<expr>    ::= <id>    ;identificador
            | (fun (<id> : <type>)+ <expr>)    ;función (anónima) de primera clase
            | (match <expr> (<case>+))    ;pattern matching
            | (<expr> <expr>*)    ;aplicación

<case>    ::= (case <pattern> => <expr>)

<pattern> ::= <id>    ;matcheo sobre un identificador
             | (<id> <id>*)    ;matcheo sobre (la aplicación de) un constructor

</code>

Recuerde que para una cadena ''w'', ''w+'' representa una secuencia de al menos un ''w'', mientras que ''w*'' representa una secuencia posiblemente vacía de ''w'''s.

=== Tipos inductivos ===

Un tipo de datos inductivo se define a través de una cláusula ''deftype'', proveyendo el nombre del tipo y los  constructores asociados.  

**Ejemplo 1. ** En el siguiente ejemplo el programador define los números naturales a través de un tipo inductivo ''nat'' y dos constructores ''O'' y ''S'', que  simbolizan el 0 y el sucesor de un natural, respectivamente.

<code scheme>
(run '((deftype nat 
          (O : nat)
          (S : (nat -> nat)))
       (O)))
> "(O) : nat"            
</code>

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''. 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''. 


**Ejemplo 2. ** El tipo ''expr'' definido abajo posee dos constructores, ''num'' y ''add'', cada uno de los cuales utiliza dos argumentos de tipo ''expr'' para construir otro valor de tipo ''expr''.

<code scheme>
(run '((deftype nat 
               (O : nat)
               (S : (nat -> nat)))
             (deftype expr 
               (num : (nat -> expr))
               (add : (expr expr -> expr)))   
             (add (num (S (O))) (num (O)))))
> "(add (num (S (O))) (num (O))) : expr"
</code>

Para la resolución de la tarea podemos asumir que nunca se van a proveer dos definiciones distintas para un mismo tipo inductivo.

=== Funciones de primer order y pattern matching ===

Podemos definir funciones de primer orden (para recordar la diferencia entre funciones de primer orden y de primera clase, ver contenido de la //Clase de Cátedra 8//) a través de la cláusula ''def''. Las funciones así definidas incluyen anotaciones de tipo para sus argumentos y valor de retorno. El lenguaje también soporta pattern matching, a través de la cláusula ''match''. 

**Ejemplo 3. ** La función ''pred'' definida a continuación 

<code scheme>
(run '((deftype nat
          (O : nat)
          (S : (nat -> nat)))
       (def pred (n : nat) : nat
               (match n
                 ((case (O) => (O))
                  (case (S n1) => n1))))
       (pred (S (O)))))
> "(O) : nat"            
</code>

utiliza pattern matching para determinar su valor de retorno. Al momento de interpretar un pattern matching, se espera que primero se reduzca el elemento sobre el cual matchear, en este caso ''n'', para luego ir comprobando uno a uno con qué patrón coincide. Dicha comprobación se debe hacer en el mismo orden en que se presentan los patrones.  Si en un ''case'' el patrón incluye un identificador libre, éste funciona como un //binding// para el cuerpo del caso (ejemplo ''(case (S n1) => n1)'').

En caso de no encontrarse ningún patrón que matchee, debe lanzarse un error:

<code scheme>
(test/exn 
 (run '((deftype bool 
          (t : bool)
          (f : bool))
       (def not (b : bool) : bool
                (match b
                 ((case (t) => (f)))))
       (not (f)))
   "match error")
</code>

En cualquier caso, un identificador siempre puede servir para hacer match de los casos restantes:

<code scheme>
(run '((deftype day 
         (monday : day)
         (tuesday : day)
         (wednesday : day)
         (thursday : day)
         (friday : day)
         (saturday : day)
         (sunday : day))
       (deftype bool
         (t : bool)
         (f : bool))
       (def weekday (d : day) : bool
         (match d
           ((case (saturday) => (f))
            (case (sunday) => (f))
            (case otherday => (t)))))
       (weekday (monday))))
> "(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 ===

Funciones definidas con ''def'' pueden ser recursivas y tener más de un argumento.


<code scheme>
(run '((deftype bool 
          (t : bool)
          (f : bool))
       (deftype nat 
          (O : nat)
          (S : (nat -> nat)))
       (def not (b : bool) : bool
                (match b
                 ((case (t) => (f))
                  (case (f) => (t)))))
       (def even (n : nat) (b : bool) : bool 
               (match n
                 ((case (O) => b)
                  (case (S n1) => (even n1 (not b))))))
       (even (S (S (S (O)))) (t))))
> "(f) : bool"
</code>

=== Funciones de primera clase ===

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>
(run '((deftype bool 
          (t : bool)
          (f : bool))
       (fun (x : bool) x)))
> "λ"
</code>


===== Tareas a realizar =====

Con esto en mente, se pide que:

== P1 (0.75 Pt) ==
Defina la sintaxis abstracta para soportar el lenguaje. Note que un programa es una lista de definiciones seguida de una expresión. Dos tipos de definiciones son posibles ''deftype'' y ''def''.


== P2 (1.25 Pt) ==
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
 
<code scheme>
(match '(1 2 3 4 5 6 7)
    [(list 1 a ... 7) a])
> '(2 3 4 5 6)
</code>

<code scheme>
(match '(1 2 3 4 5 6 7)
    [(list 1 a ..2 7) a])
> '(2 3 4 5 6)
</code>

<code scheme>
(match '(1 2 3 4 5 6 7)
    [(list 1 a ..6 7) a])
> match: no matching clause for '(1 2 3 4 5 6 7)
</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>

== 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. Se requiere que el lenguaje soporte recursión para las funciones de primer orden (es decir, las definidas a través de un ''def'').

**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 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**: 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.