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

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 con elementos extra.

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

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.

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

{
   {+ 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}}
}

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.

Para desarrollar el parser de nuestro lenguaje core, dividiremos su implementación en las siguientes funciones:

1. [0.4 pts] parse-expr que recibe una s-expression y retorna un nodo Expr.
2. [0.2 pts] parse-fundef que recibe una s-expression y retorna un nodo Fundef.
3. [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), 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), 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.

;; <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 extendido pueden ser:

{
   {define {geq x y} {! {< x y}}}
   {define {relu x} {if {geq 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 true}}
       z}
}
{
   {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, verifique que no corresponda con uno ya utilizado por algún procedimiento de Racket.

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

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