====== Tarea 1a (Entrega: Miércoles 3 de abril del 2024) ======

==== Parsing de Lenguaje con Funciones top-level ====

En esta tarea, implementaremos el parser para un lenguaje funcional con funciones top-level, tipos de datos básicos e identificadores locales (with). Para hacer una aproximación más gradual al problema, dividiremos el desarrollo en un lenguaje core que luego extenderemos.

<note important>
Consulte las normas de entrega de tareas en http://pleiad.cl/teaching/cc4101.
Recuerden que tienen que seguir la metodología [[https://users.dcc.uchile.cl/~etanter/preplai/defun.html|vista en las primeras clases]] y dejar sus funciones debidamente documentadas.
</note>

Deben desarrollar su tarea en base a los siguientes archivos:
  * ''{{ :teaching:cc4101:tareas:2024-1:t1a.rkt |t1a.rkt}}'': Aquí deberán implementar todas las funcionalidades pedidas en cada pregunta.
  * ''{{ :teaching:cc4101:tareas:2024-1:t1a-test.rkt |t1a-test.rkt}}'': Aquí se le proveen tests iniciales para el lenguaje core, y deberán añadir nuevos tests para las funciones desarrolladas o extendidas.

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

----


===== 1) Parser del Lenguaje Core [0.8 pts] =====

En esta parte, vamos a implementar el parser para 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.

<code scheme>
<prog>   ::= {<fundef>* <expr>}

<fundef> ::= {define {<id> <id>*} <expr>}

<expr>   ::= <num>
           | <id>
           | {add1 <expr>}
           | {+ <expr> <expr>}
           | {- <expr> <expr>}
           | {<id> <expr>*}
</code>

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 core pueden ser:

<code scheme>
{
   {+ 3 {- 5 -4}}
}
{
   {define {sum x y z} {+ x {- y z}}}
   {add1 {sum -2 5 1}}
}
{
   {define {triple x} {+ x {+ x x}}}
   {define {add2 x} {+ 2 x}}
   {add2 {triple 2}}
}
</code>

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

Para desarrollar el parser, dividiremos su implementación en las siguientes funciones:
  - **[0.4 pts]** ''parse-expr'' que recibe una s-expression y retorna un nodo ''Expr''.
  - **[0.2 pts]** ''parse-fundef'' que recibe una s-expression y retorna un nodo ''Fundef''.
  - **[0.2 pts]** ''parse-prog'' que recibe una s-expression y retorna un nodo ''Prog''.

**Observaciones importantes**:
  * Cuando el BNF incluye un nodo con * (cero o más ocurrencias), el nodo del AST correspondiente lleva una lista de los elementos. Luego, pueden usar ''map'' para procesar esos elementos.
  * Fíjese en los tests provistos para ver ejemplos de nodos construidos por las distintas funciones de parsing.


===== 2) Parser del Lenguaje Extendido [1.2 pts] =====


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

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

<code scheme>
;; <prog> y <fundef> no cambian

<expr>   ::= ...
           | <bool>
           | {< <expr> <expr>}
           | {= <expr> <expr>}
           | {! <expr>}
           | {if <expr> <expr> <expr>}
           | {with {<binding>*} <expr>}

<binding> ::= (<id> <expr>)
</code>

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

<code scheme>
{
   {define {>= x y} {! {< x y}}}
   {define {relu x} {if {>= x 0} x 0}}
   {relu 42}
}
{
   {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 #t}}
       {if z
           {add1 x}
           {- y 2}}}
}
{
   {with {{x 3}
          {y {+ 1 2}}}
       {if {= x y} x y}}
}
</code>


**Observaciones importantes**:
  * Recuerde que la estructura del BNF dicta la estructura de las funciones que procesan los programas, definiciones, expresiones, etc.
  * Puede incluir los booleanos de una manera similar a como se introducen los números, reutilizando los booleanos de Racket.
  * Al definir los nombres de los constructores del lenguaje, verifique que no sean ya utilizados por Racket, para evitar confusiones.
  

=== Nuevos nodos para el AST ===
  - **[0.1 pts]** Defina el tipo ''Binding'' que corresponde al nodo ''<binding>'' en el BNF, que representa la asociación entre un identificador y una expresión.
  - **[0.2 pts]** Extienda el tipo de datos ''Expr'' con nuevos constructores para las expresiones que se añadieron al lenguaje.

=== Extender el Parser ===
  - **[0.1 pts]** Implemente la función ''parse-binding'' que recibe una s-expression y retorna un nodo ''Binding''.
  - **[0.4 pts]** Extienda la función ''parse-expr'' con casos para las nuevas expresiones.

<note important>
  * Recuerde incluir tests para las funciones ''parse-binding'' y ''parse-expr'', con cobertura de todos los casos relevantes, pues se considerará en la evaluación **[0.4 pts]**.
</note>