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, y operadores simples), 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>}
 
<expr>   ::= <num>
           | <id>
           | {add1 <expr>}
           | {+ <expr> <expr>}
           | {- <expr> <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.

Para esta parte, se proveen las definiciones de los tipos de datos que representan los nodos del AST y los test necesarios para el lenguaje core.

Observaciones importantes:

• Recuerde que la estructura del BNF dicta la estructura de las funciones que procesan los programas, definiciones, expresiones, etc.
• Cuando el BNF incluye un nodo con * (cero o más ocurrencias), pueden usar map para procesar los elementos.

En esta parte, vamos a extender el lenguaje core con algunas primitivas extra (booleanos, y operadores booleanos simples), e identificadores locales (with con una cantidad arbitraria de bindings).

Las extensiones sintácticas del lenguaje se presentan en el siguiente BNF.

;; <prog> y <fundef> no cambian
 
<expr>   ::= ...
           | <bool>
           | {< <expr> <expr>}
           | {= <expr> <expr>}
           | {! <expr>}
           | {if <expr> <expr> <expr>}
           | {with {<binding>*} <expr>}
 
<binding> ::= (<id> <expr>)
 
<bool> ::= #t | #f

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.