Tarea 1a (Entrega: 28 de marzo del 2024)

En esta primera parte de la tarea 1, implementaremos el parser para un lenguaje funcional con funciones top-level, tipos de datos básicos e identificadores locales (with).

Deben desarrollar su tarea en base a los siguientes archivos:

• t1a.rkt: Aquí deberán implementar todas las funcionalidades pedidas en cada pregunta.
• t1a-test.rkt: Aquí deberán escribir los tests para las funciones desarrolladas.

Deben entregar vía U-Cursos un único archivo .zip que contenga los archivos t1a.rkt y t1a-test.rkt.

En esta parte, vamos a implementar un lenguaje que incluye primitivas útiles (números, booleanos, y operadores simples), identificadores locales (with con una cantidad arbitraria de bindings), y definiciones de funciones top-level de múltiples argumentos.

El lenguaje con el que trabajaremos está definido por la siguiente gramática en BNF.

<prog>   ::= {<fundef>* <expr>}
 
<fundef> ::= {define {<id> <id>*} <expr>}
 
<bool> ::= true | false
 
<binding> ::= {<id> <expr>}
 
<expr>   ::= <num>
           | <id>
           | <bool>
           | {add1 <expr>}
           | {+ <expr> <expr>}
           | {< <expr> <expr>}
           | {= <expr> <expr>}
           | {! <expr>}
           | {if <expr> <expr> <expr>}
           | {with {<binding>*} <expr>}
           | {<id> <expr>*}
 

Un programa está compuesto de 0 o más definiciones de funciones, además de una expresión final que sirve de punto de entrada (como el main en C y Java). Una definición de función incluye el nombre de la función, el nombre de los parámetros formales, y finalmente la expresión del cuerpo de la función. Las expresiones siguen la presentación estándar vista en clases.

Algunos ejemplos de programas válidos para este lenguaje pueden ser:

{
   {define {sum x y z} {+ x {+ y z}}}
   {with {{x 9} {y 10} {z 11}}
        {sum x y z} }
}
{
   {with {{x 5} {y 42} {z true}}
         z}
}
{
   {define {triple x} {+ x {+ x x}}}
   {define {add2 x} {+ 2 x}}
   {add2 {triple 2}}
}
{
   {with {{x 3} {y {+ 1 2}}}
         {if {= x y} x y}}
}

Observaciones importantes:

• Recuerde que la estructura del BNF dicta la estructura de las funciones que procesan los programas, definiciones, expresiones, etc.
• Al definir el nombre de los constructores del lenguaje, verifica que no corresponda con uno ya utilizado por algún procedimiento de Racket.
• Recuerda que incluir tests por cada función, con cobertura de todos los casos relevantes, es parte de la metodología de programación, y se considerará en la evaluación.

En esta parte, definiremos los tipos de datos que representarán a los diversos nodos del AST de nuestro lenguaje. Siguiendo la gramática presentada anteriormente, defina lo siguiente:

1. [0.1 pts] El tipo Fundef que representa a la definición de una función top-level.
2. [0.1 pts] El tipo Binding que representa la asociación entre un identificador y un valor.
3. [0.2 pts] El tipo Expr que representa a una expresión del lenguaje.
4. [0.1 pts] El tipo Prog que representa a un programa.

En esta parte, implementaremos el parser para nuestro lenguaje. Para poner en práctica la metodología del curso, dividiremos la implementación del parser en las siguientes funciones:

1. [0.2 pts] parse-fundef que recibe una s-expression y retorna un nodo Fundef.
2. [0.2 pts] parse-binding que recibe una s-expression y retorna un nodo Binding.
3. [0.8 pts] parse-expr que recibe una s-expression y retorna un nodo Expr.
4. [0.3 pts] parse-prog que recibe una s-expression y retorna un nodo Prog.