Table of Contents

Tarea 1 (Entrega: 30 de abril de 2018)

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.

Consulte las normas de entrega de tareas en http://pleiad.cl/teaching/cc4101

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

1. Funciones de primera clase con tipos declarados [1.5pt]

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

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

2. Verificación de Tipos [1.5pt]

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

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: No type for 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} : {Num -> Num} 10}))
  "Type error in expression fun position 1: expected {Num -> Num} 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 'y))
  "Type error: No type for identifier: y"

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

>(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}"

3. Compilación [3.0pt]

Ahora vamos a compilar nuestro lenguaje a una máquina abstracta basada en stack. La máquina es similar a la conocida SECD1), 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 (machine ins-list) le permitirá ejecutar una lista de instrucciones en la máquina.

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

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

Índices De Bruijn

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 Bruijn2).

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"

De AST a código de máquina

Vamos 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 lenguaje original a listas de instrucciones. Note que solo es el paso a notación polaca inversa:

C(n) = INT-CONST n
C({+ a1 a2}) = C(a2);C(a1);ADD
C({f a}) = C(a); C(f); APPLY

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

C(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)) 
2)
La explicación detallada de como funcionan se puede encontrar en la sección 3.5 del PLAI