Tarea 1 (Entrega: 28 de abril de 2019)

Esta tarea se distribuye con un archivo zip base que contiene 3 archivos: main.rkt, tests.rkt, y machine.rkt. Los archivos main.rkt y tests.rkt están incompletos, y en ellos tienen que implementar lo que se solicita en las preguntas siguientes. No deben modificar el archivo machine.rkt: es una implementación completa de la máquina a la cual van a compilar su lenguaje.

Deben entregar via U-cursos un archivo .zip que contenga los archivos main.rkt y tests.rkt.

¡Los tests, los contratos y las descripciones forman parte de su evaluación!

En esta tarea agregaremos anotaciones de tipos a un lenguaje con funciones de primera clase. La sintaxis concreta del lenguaje es la mostrada a continuación:

<s-expr> ::= <num>
         | <id>
         | {+ <s-expr> <s-expr>}
         | {- <s-expr> <s-expr>}
         | {with {<id> : <type> <s-expr>} <s-expr>}
         | {fun {<id> : <type>} [: <type>] <s-expr>}
         | {<s-expr> <s-expr>}         
 
<type> ::= Num
         | {<type> -> <type>}

Note que with no incluye anotación del tipo del cuerpo, y el tipo de retorno de las funciones es opcional (los '[' ']' son parte de la notación BNF, especificando que lo que va adentro es opcional). Por ejemplo, los programas siguientes son válidos:

{with {x : Num 5} {+ x 3}}
 
{fun {x : Num} : Num 
  {+ x 3}}
 
{fun {x : Num}
  {+ x 3}}

• (0.3) Defina la función (parse-type type) que parsea solo la gramática de tipos. Ademas en caso de error, debe retornar el error “Parse error”

  > (parse-type '{{Num -> Num} -> Num})
  (TFun (TFun (TNum) (TNum)) (TNum))
   
  > (parse-type '{Num ->  })
  "Parse error"

• (0.9) Defina la función (parse s-expr) para que acepte la gramática completa del lenguaje. Utilice la función (Parse-type type) en los puntos donde deba identificar tipos. Además, la función parse debe reemplazar el with por una aplicación de función. Ejemplos:

  > (parse '{fun {x : Num} : Num {+ x 1}})
  (fun 'x (TNum) (add (id 'x) (num 1)) (TNum))
   
  > (parse '{with {y : Num 2}
               {+ x y}})
  (app (fun 'y (TNum) (add (id 'x) (id 'y)) #f) (num 2))

Note que se usa #f cuando una función no tiene anotado un tipo de retorno.

• (0.3) Defina la función (prettify type) que tome un tipo y lo escriba en la sintaxis concreta.

  > (prettify (TNum))
  'Num
   
  > (prettify (TFun (TNum) (TFun (TNum) (TNum)))
  '(Num -> (Num -> Num))

Se implementará el chequeo de tipos de una expresión en presencia de funciones de primera clase.

• (1.0) Implemente la función (typeof expr) que calcula el tipo de la expresión dada o falla con un mensaje de error en caso de que la expresión no sea válida. Para la validación, considere lo siguiente:
  • Para una función con el tipo de retorno anotado, se valida que la expresión del cuerpo tenga el mismo tipo que el tipo de retorno declarado.
  • Para una función sin el tipo de retorno anotado, el tipo resultante considera el tipo calculado del cuerpo de la función.
  • Para la aplicación de función se valida que la expresión en posición de función sea efectivamente una función.
  • Para la aplicación de función también se valida que el tipo de la expresión de argumento de la aplicación coincide con el tipo esperado del argumento de la función.
  • Para la aplicación de un operador se valida que sus operandos tengan el tipo correcto.

Los mensaje de error de tipo tienen que seguir el siguiente patrón:

"Type error in expression <E> position <n>: expected <T1> found <T2>"

donde E es la expresión donde ocurrió el error, n es la sub-expresión donde se manifestó, T1 es el tipo esperado y T2 el tipo encontrado. Utilice su función prettify para mostrar errores legibles.

Note que la única forma de tener error de tipo de función, es cuando el tipo de retorno está anotado.

Para el caso cuando hay algún identificador libre, el patrón es:

"Type error: free identifier: <x>"

donde <x> es el identificador libre.

Algunos ejemplos:

  > (typeof (parse '{fun {x : Num} : Num 5}))
  (TFun (TNum) (TNum))
  > (typeof (parse '{fun {x : Num} x}))
  (TFun (TNum) (TNum))
  > (typeof (parse '{{fun {x : Num} x} 1}))
  (TNum)
  > (typeof (parse '{fun {x : Num} : {Num -> Num} 10}))
  "Type error in expression fun position 1: expected (Num -> Num) found Num"
  > (typeof (parse '{1 2}))
  "Type error in expression app position 1: expected (T -> S) found Num"
  > (typeof (parse '{{fun {x : Num} : Num {+ x x}} {fun {x : Num} : Num 5}}))
  "Type error in expression app position 2: expected Num found (Num -> Num)"
  >(typeof (parse '{fun{x : Num}{+ x {fun{z : Num} 1}}}))
  "Type error in expression + position 2: expected Num found (Num -> Num)"
  > (typeof (parse 'y))
  "Type error: free identifier: y"

Note que debe manejar identificadores adecuadamente, considere la implementación de un ambiente que almacene tipos.

• (0.5) Implemente la función (typecheck s-expr) que retorna el tipo de un programa, en un formato legible:

>(typecheck '3)
'Num
 
>(typecheck  '{fun {f : Num} : Num 10})
'(Num -> Num)
 
>(typecheck  '{+ 2 {fun {x : Num} : Num x}})
  "Type error in expression + position 2: expected Num found {Num -> Num}"

Ahora vamos a compilar nuestro lenguaje a una máquina abstracta basada en stack. La máquina es similar a la conocida SECD¹⁾, la cual no trabaja con identificadores, sino que solo con índices. La máquina SECD consume una lista de instrucciones, utiliza un stack para almacenar datos temporales y posee un ambiente que, a diferencia del ambiente visto normalmente en el curso, es un arreglo con valores sin identificadores. La máquina SECD ya está definida en el archivo machine.rkt. La función (exec-machine ins-list) le permitirá ejecutar una lista de instrucciones en la máquina.

> (exec-machine (list (INT-CONST 6) (INT-CONST 1) (ADD)))
7
> (exec-machine (list (INT-CONST 3) (CLOSURE (list (ACCESS 0) (RETURN))) (APPLY)))
3 

Tome un tiempo para experimentar con la función exec-machine y el set de instrucciones antes de realizar los próximos ejercicios.

Una forma de eliminar nombres de variables o identificadores de una expresión, es usando índices De Bruijn. Anteriormente vimos que la máquina SECD trabaja solo con índices, por lo que en esta sección vamos a hacer el paso de identificadores a dichos números, usando indices De Bruijn²⁾.

• (1.5) Implemente la función deBruijn que toma una expresión y la recorre reemplazando los identificadores no libres, con los índices De Bruijn (nodos (acc n)) manteniendo el scope léxico. La salida de esta función no debería tener nodos del tipo fun, ni id. En su lugar debería contener nodos del tipo fun-db y acc. El resto de los nodos no varía.

Hint: le podría ser útil recordar que el intérprete visto en clases usa un ambiente para asociar identificadores a valores.

> (deBruijn 
   (parse '{+ 1 {with {x : Num 1}
                           {with {y : Num 2}
                                 {+ x y}}}}))
(add
 (num 1)
 (app
  (fun-db
   (app (fun-db (add (acc 1) (acc 0))) (num 2)))
  (num 1)))
 
> (deBruijn (add (num 1) (id 'x)))
"Free identifier: x"

Vamos a abordar la compilación del AST de una expresión al set de instrucciones de la SECD. A continuación se presenta el esquema de compilación que permite hacer el paso del AST de una expresión a una lista de instrucciones (revise el archivo machine.rkt, todas las definiciones están comentadas y puede encontrar la sintaxis completa de las instrucciones). Note que solo es el paso a notación polaca inversa:

C((num n)) = (INT-CONST n)
C((add a1 a2)) = C(a2);C(a1);(ADD)
C((sub a1 a2)) = C(a2);C(a1);(SUB)
C((app f a)) = C(a); C(f);(APPLY)

La compilación de un nodo (acc n) es la siguiente:

C((acc n)) = (ACCESS n)

La compilación de una función puede ser inferida del ejemplo a continuación:

> (compile (deBruijn (parse '{{fun {x : Num} : Num
                                   {+ x 10}} {+ 2 3}})))
(list
 (INT-CONST 3)
 (INT-CONST 2)
 (ADD)
 (CLOSURE (list (INT-CONST 10) (ACCESS 0) (ADD) (RETURN)))
 (APPLY)) 

• (1.0) Implemente la función (compile expr) que dada una expresión con índices De Bruijn genera la lista de instrucciones siguiendo el esquema de compilación descrito anteriormente.

• (0.5) Implemente la función (typed-compile s-expr) que se encarga de todo el proceso de generación de código desde un programa, considerando el parsing, la validación de tipos, y la transformación con índices De Bruijn. Note que esta función solo genera código de maquina si la expresión esta bien tipada, sino produce el error correspondiente.