Tarea 2

Esta tarea se distribuye con dos ficheros base.rkt y tests.rkt (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.

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.

<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

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.

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.

(run '((deftype nat 
          (O : nat)
          (S : (nat -> nat)))
       (O)))
> "(O) : nat"            

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.

(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"

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

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

(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"            

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:

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

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

(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"         

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.

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

(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"

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:

(run '((deftype bool 
          (t : bool)
          (f : bool))
       (fun (x : bool) x)))
> "λ"

Con esto en mente, se pide que:

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.

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

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

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

(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)

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.

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.