Tarea 1b (Entrega: Jueves 18 de Abril de 2024)

Ya se habrán dado cuenta que ciertos lenguajes tienen tipos estáticos (C/C++, Java, C#, Scala, etc.) y otros tienen tipos dinámicos (Python, Racket, JavaScript, etc.).

En esta tarea van a implementar un lenguaje simple con funciones de primer orden, tipos de datos básicos y pares. Para implementar este lenguaje necesitaremos un parser (lo implementamos en la tarea 1a), y un intérprete, dividiremos el desarrollo de esta tarea en dos partes (más una opcional). Primero, el lenguaje contará sólo con chequeo dinámico de tipos (parte 1), para luego agregar verificación de tipos estáticos (parte 2). Opcionalmente (como bonus), puede agregar contratos dinámicos para funciones (parte 3).

Deben entregar via U-cursos un archivo .zip que contenga los siguientes archivos: p1.rkt, p1-test.rkt, p2.rkt, p2-test.rkt, archivos que deberán contener las funcionalidades solicitadas en cada pregunta y los tests respectivos.

Si lo desea, puede obtener un bonus resolviendo la tercera parte, que es opcional: p3.rkt y p3-test.rkt. Más detalles al final del documento.

Deben entregar vía U-Cursos un único archivo .zip que contenga todos los archivos de su entrega.

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

La gramática BNF del lenguaje se define a continuación:

<prog>   ::= {<fundef>* <expr>}
 
<fundef> ::= {define {<id> <id>*} <expr>}
 
<expr>   ::= <num>
           | <id>
           | <bool>
           | {cons <expr> <expr>}
           | {add1 <expr>}
           | {+ <expr> <expr>}
           | {- <expr> <expr>}
           | {< <expr> <expr>}
           | {= <expr> <expr>}
           | {! <expr>}
           | {&& <expr> <expr>}
           | {|| <expr> <expr>}
           | {fst <expr>}
           | {snd <expr>}
           | {if <expr> <expr> <expr>}
           | {with {<binding>*} <expr>}
           | {<id> <expr>*}
 
<binding> ::= (<id> <expr>)
 

Esta gramática es similar a la presentada en la tarea 1a, con las siguientes diferencias.

• Se agregan dos operadores booleanos extra, estos son && y ||.
• Se agregan pares, los cuales se definen utilizando cons. Las expresiones fst y snd permiten obtienen el primer y segundo elemento, respectivamente (similar a car y cdr de Racket).

Los programas que terminan reducen a valores. Estos pueden ser números, booleanos o pares de valores. Siguiendo las buenas prácticas de desarrollo del curso, se define un tipo de datos inductivo Val para los valores del lenguaje (provisto en el código fuente de la parte 1).

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

{
   {with {{x 3}
          {y {+ 1 2}}}
       {if {= x y} x y}}
}
 
{
   {with {{x 5}
          {y 42}}
       {cons x z}}
}
 
{
   {define {sum x y z} {+ x {+ y z}}}
   {define {cadr x} {fst {snd x}}}
   {with {{x 9}
          {y {cons 1 {cons 3 4}}}}
       {sum x {fst y} {cadr y}} }
}
 
{
   {define {implies p q} {|| {! p} q}}
   {implies #f #t}
}

Observaciones importantes:

• Recuerde que la estructura del BNF dicta la estructura de las funciones que procesan los programas, definiciones, expresiones, etc.
• La semántica del with es la del let de Racket. En particular esto significa que un binding no puede definirse en función de los bindings anteriores del mismo with. Por ejemplo, el siguiente programa lanza un error de identificador libre, pues x no es “visible” desde la expresión nombrada por y:

  {
    {with {{x 2}
           {y {add1 x}}}
        {add1 y}}
  }
 
  >> Free identifier: x
 

En cambio, el siguiente programa si funciona, pues x fue introducido en el with que “engloba” al with donde se usa x.

  {
    {with {{x 2}}
       {with {{y {add1 x}}}
          {add1 y}}
  }
 

• Debe verificar en tiempo de ejecución que los argumentos de los operadores numéricos sean numéricos, que los argumentos de los operadores booleanos sean booleanos, y que los argumentos de los operadores de pares sean pares (En la parte 2 se alineará la verificación dinámica con la verificación estática).
• Considere que la igualdad solo es válida sobre números.
• La condición de una expresión if debe ser un booleano.
• En caso de programas con errores dinámicos de tipo, su intérprete tiene que reportarlos explícitamente, mostrando un mensaje con el siguiente formato:

Runtime type error: expected <type> found <value>

donde <type> ::= Number | Boolean | Pair, y <value> es un valor en sintaxis concreta. Nota: En el código base se provee la función pp-val :: Val → String, que dado un valor retorna un string con su representación en sintaxis concreta. Los errores se levantan con (error msg) (tal como lo hacemos en clase con los identificadores libres).

A continuación se muestran algunos programas que fallan dinámicamente por errores de tipo:

{
  {+ 1 {cons 3 4}}
}
 
>> Runtime type error: expected Number found {cons 3 4}

{
  {&& {+ 1 2} #f}
}
 
>> Runtime type error: expected Boolean found 3

{
  {snd {! #t}}
}
 
>> Runtime type error: expected Pair found #f

{
  {if {cons 2 3}
      1
      0}
}
 
>> Runtime type error: expected Boolean found {cons 2 3}

Recuerde que puede verificar si un test lanza una excepción con test/exn.

• Al aplicar una función, debe verificar en tiempo de ejecución que la función esté definida y que sea aplicada al número correcto de argumentos, de lo contrario debe lanzar un error. Por ejemplo, los siguientes programas lanzan errores:

{
  {foo 2 3}
}
 
>> Undefined function: foo
 
 
{
  {define {bar p} {! p}}
  {bar #t #f}
}
 
>> Arity mismatch: function bar expected 1 arguments, received 2

Teniendo en cuenta todo lo descrito anteriormente, implemente las siguientes funciones:

1. [1.0 pts] interp :: Expr List[Fundef] → Val or error, que interpreta una expresión considerando una lista de funciones definidas al top-level.
2. [0.2 pts] run :: s-expr → Val or error, que toma un programa escrito en sintaxis concreta, lo parsea e interpreta.

El testing recibe 0.3 pts.

En esta parte vamos a extender el lenguaje con anotaciones de tipos y verificación estática de ellos. Las diferencias en la sintaxis del lenguaje respecto de la parte anterior son:

• Las declaraciones de función incluyen anotaciones de tipos en cada uno de sus argumentos y también para el tipo de retorno.
• Las expresiones with pueden incluir anotaciones de tipos en cada identificador introducido.

La nueva sintaxis concreta es la siguiente:

;; <prog> y <expr> no cambian
 
<fundef> ::= {define {<id> <arg>*} : <type> <expr>} 
 
<arg>    ::= {<id> : <type>} 
 
<binding> ::= {<id> [: <type>] <expr>}
 
<type>   ::= Num | Bool | {Pair <type> <type>}

En el BNF utilizamos [ ] para denotar que algo es opcional. Note que with no incluye anotación del tipo del cuerpo y que los tipos de los identificadores son opcionales. Por otro lado, el tipo de retorno de una función siempre debe estar presente, al igual que el de cada uno de sus argumentos.

A continuación puede ver ejemplos de programas en la nueva sintaxis, los que (además) están bien tipados:

{
  {with {{x : Num 5}
         {y : Num 10}} 
     {+ x y}}
}

{
  {with {{x 5}}
     {with {{y : Num {+ x 1}}} 
        {+ x y}}
}

{
  {define {add-pair {p : {Pair Num Num}} {x : Num}} : {Pair Num Num} 
    {cons {+ {fst p} x} {+ {snd p} x}}}
  {add-pair {cons 1 1} 1}
}

{
  {define {id {x : Num}} : Num x}
  {id 5}
}

{
  {define {sum {x : Num} {y : Num} {z : Num}} : Num 
    {+ x {+ y z}}}
  {define {cadr {x : {Pair Num {Pair Num Num}}}} : Num 
    {fst {snd x}}}
  {with {{x 9}
         {y {cons 1 {cons 3 4}}}}
     {sum x {fst y} {cadr y}} }
}

Note que se agregó el nodo <arg> al BNF, el cual especifica la sintaxis concreta de un argumento de función.

1. [0.1 pts] Defina el tipo de datos Arg que representa a un argumento de función en el AST.
2. [0.2 pts] Implemente la función parse-arg que parsea un argumento de función.
3. [0.1 pts] Modifique la función parse-fundef para que utilice parse-arg para parsear los argumentos.

Además de lo anterior, observe que el nodo <binding> en el BNF cambió, y ahora puede incluir una anotación opcional de tipo para el identificador que se introduce.

1. [0.1 pts] Modifique el tipo de datos Binding para que pueda almacenar el tipo del identificador.
2. [0.1 pts] Modifique la función parse-binding para que acepte una anotación opcional de tipo. Nota: Cuando no se especifica el tipo, puede guardar el valor #f en el lugar donde se almacenaría el tipo.