Tarea 3

Esta tarea se distribuye con tres ficheros start.rkt, machine.rkt y tests.rkt (mediante U-Cursos). Considere las definiciones del archivo start.rkt y escriba sus funciones en él. Escriba sus tests en el archivo test.rkt adjunto. Ambos ficheros deben ser entregados vía U-Cursos. Los tests forman parte de su evaluación! Consulte las normas de entrega de tareas en http://pleiad.cl/teaching/cc4101.

En esta tarea haremos extensión a un lenguaje con funciones de primera clase con tipos. La gramática del lenguaje es la mostrada a continuación:

<expr> ::= <num>
         | <bool>
         | <id>
         | {+ <expr> <expr>}
         | {- <expr> <expr>}
         | {= <expr> <expr>}
         | {< <expr> <expr>}
         | {and <expr> <expr>}
         | {or <expr> <expr>}
         | {not <expr>}
         | {if <expr> <expr> <expr>}
         | {with : <TYPE> {<id> : <TYPE> <expr>} <expr>}
         | {fun {<id> : <TYPE>} : <TYPE> <expr>}
         | {<expr> <expr>}         
 
<TYPE> ::= Num
         | Bool
         | {<TYPE> -> <TYPE>}

1. (0.4) Defina la función (parse-t s-expr) que parsea solo la gramática de tipos que se inicia del no terminal <TYPE>.

   > (parse-t '{{Num -> Num} -> Bool})
   (TFun (TFun (TNum) (TNum)) (TBool))

2. (0.6) Modifique¹⁾ la función (parse expr) para que acepte la gramática con números, booleans y funciones de primera clase con tipos. Utilice la función (parse-t s-expr) en los puntos donde deba identificar tipos. La función parse debe reemplazar el with por una aplicación de función como se ha visto en clases

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

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 una 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. Considere usar la definición de la máquina SECD del 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) (INT_CONST 2) (ADD) (SUB)))
-3

Tome un tiempo para experimentar con la función 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. (1.0) 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.

   > (deBruijn 
      (parse '{+ 1 {with : Num {x : Num 1}
                              {with : Num {y : Num 2}
                                    {+ x y}}}}))
   (add
    (num 1)
    (app
     (fun-db
      (app (fun-db (add (acc 1) (acc 0)) (TFun (TNum) (TNum))) (num 2))
      (TFun (TNum) (TNum)))
     (num 1)))
    
   > (deBruijn (add (num 1) (id 'x)))
   ;Arroja error "unbound identifier"

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(b) -> BOOL_CONST b
C(n) -> ACCESS n
C({+ a1 a2}) = C(a2);C(a1);ADD
C({- a1 a2}) = C(a2);C(a1);SUB
C({< a1 a2}) = C(a2);C(a1);LESS
C({= a1 a2}) = C(a2);C(a1);EQ
C({and a1 a2}) = C(a2);C(a1);AND
C({or a1 a2}) = C(a2);C(a1);OR
C({not a1}) = C(a1);NOT
C({f a}) = C(a); C(f); APPLY
C({if c tb fb}) = C(c); IF(C(tb),C(fb))

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

> (compile (deBruijn (parse '{{fun {x : Num} : Bool
                                   {< x 10}} {+ 2 3}})))
(list
 (INT_CONST 3)
 (INT_CONST 2)
 (ADD)
 (CLOSURE (list (INT_CONST 10) (ACCESS 0) (LESS) (RETURN)) (MTFun (MTNum) (MTBool)))
 (APPLY)) 

En el ejemplo anterior se puede notar que los tipos que entiende la máquina no se crean con los constructores de Type. Los tipos en la máquina esta definidos con el deftype MType por lo que debe hacerse una transformación de los tipos de Type a MType. Las reglas para la transformación son:

• TNum a MTum
• TBool a MTBool
• TFun a MTFun aplicando la transformación recursivamente al tipo del argumento y al tipo de retorno

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

En la tarea anterior se abordó el chequeo de tipos en el lenguaje de predicados. En esta ocasión extenderemos el chequeo de tipos de una expresión en presencia de funciones de primera clase.

1. Extienda⁴⁾ la función (typeof expr) que recibe un nodo del AST y retorna el tipo correspondiente a la expresión o falla con TYPE_ERROR en caso de que la expresión no sea valida por validación de tipos considerando lo siguiente:
   • Para una función se válida que la expresión del cuerpo tenga el mismo tipo declarado en el retorno de la función. En caso de pasar la validación el tipo resultante es (TFun targ tbody), donde targ es el tipo del argumento y tbody es el tipo de retorno de la función.
   • Para la aplicación de función se valida que el primer argumento es efectivamente una función y que el tipo del segundo argumento de la aplicación (argumento real) coincide con el tipo del argumento (formal) de la función. En dicho caso la aplicación tiene el tipo del retorno de la función.

  > (typeof (parse '{fun {f : Num} : Bool #t}))
  (TFun (TNum) (TBool))
  > (typeof (parse '{{fun {f : Num} : Bool #t} #t}))
  ;Arroja error "TYPE_ERROR"
 

Vamos a introducir el tipo Any a nuestro lenguaje. Esto significa que vamos a comenzar a considerar relaciones de subtipo. En la literatura relacionada, la relación de subtipos se escribe A <: B y se lee como A es subtipo de B.

Considere para esta pregunta las relaciones Num <: Any y Bool <: Any y que para todo tipo A se tiene A <: A.

Implemente la función (typeof-with-sub expr) que recibe un nodo del AST y retorna el tipo correspondiente a el o falla con TYPE_ERROR en caso de que la expresión no sea válida. Considere que (typeof-with-sub expr) se comporta igual que la función (typeof expr) de la pregunta anterior, salvo por:

• La existencia de Any permite tipear {if #t 1 #f} como del tipo TAny⁵⁾. Es decir que frente a tipos distintos en las ramas el resultado es TAny.
• En la definición de función, el cuerpo puede ser subtipo del tipo declarado de salida de la función
• En la aplicación de función, el tipo del argumento puede ser subtipo del tipo declarado del argumento de la función.

En esta sección considere que A -> B <: Any. La noción de subtipos de funciones es muy simple y nos permite expresar relaciones con otras funciones. En esta tarea vamos a soportar: A -> B <: C -> D si B <: D y C <: A. Veamos en acción esta relación

{with : Any {f : {Num -> Num}
                  {fun {x : Num} : Num x}}
         {with : Any {g : {Num -> Any}
                        {fun {x : Num} : Any #f}}
               {with : Any {applyTo1 : {{Num -> Any} -> Any}
                                     {fun {x : {Num -> Any}} : Any {x 1}}}
                     {applyTo1 g}}}}

En este caso reemplazar g por f en el argumento de applyTo1, es válido pues f es más específico en su tipo de retorno, por lo que cualquier función que acepta la salida de g necesariamente acepta la salida de f.

{with : Num {f : {Num -> Num}
                  {fun {x : Num} : Num x}}                                 
         {with : Num {h : {Any -> Num}
                        {fun {x : Any} : Num 5}}
               {with : Num {applyTo1 : {{Num -> Num} -> Num}
                                     {fun {x : {Num -> Num}} : Num {x 1}}}
                     {applyTo1 f}}}}

Aquí ocurre que por el tipo del argumento, reemplazar en esa expresión f por h también es válido pues si f puede ser aplicado a un Num, con mayor razón una función que espera un tipo más general, en este caso Any. Entienda la función typeof-with-sub para que incluya esta relación de subtipos de funciones

Vamos a explicar como se comportan los cast con un ejemplo en Java

public void foo(Object obj){
  String str = (String)obj;
}

En este caso el programador está intentando hacer un cast de Object a String. Esto tiene dos implicancias sobre el lenguaje. Primero, el cast funciona estáticamente como una forma que tiene el programador de expresarle al sistema de tipos que cierto valor tiene cierto tipo, permitiendole en este caso asignar obj (que es originalmente un Object) a un identificador que espera un String. Segundo, el lenguaje no puede asegurar que el programador no se equivocó, por lo tanto añade en el bytecode generado, una pequeña validación de tipos en runtime que, en caso de fallo lanza un ClassCastException.

Considere:

{with : Num {id : (Any -> Any)
            {fun {x : Any} : Any x}}
        {+ 1 {id 2}}}

Este programa es rechazado por el sistema de tipos pues {f 2} tiene tipo Any y no Num. Podemos agregar un cast para decirle al sistema de tipos que el resultado si es un Num para que ahora el sistema de tipos acepte el programa:

{+ 1 {cast Num {id 2}}}

En tiempo de ejecución, tal como en el caso en Java, puede ocurrir que el elemento casteado no retorne un Num. Para evitar que la maquina terminare con un SEGFAULT se hace una válida dinámica en la máquina para un cast.

1. Implemente la función (typeof-with-cast expr) que recibe un nodo del AST y retorna el tipo correspondiente a él o falla en caso de que la expresión no sea válida. Considere que (typeof-with-cast expr) se comporta igual que la función (typeof-with-sub expr) de la pregunta anterior, salvo que ahora trabajará con casts. Además:
   • Añada cast a la gramática y al AST de expresiones
   • Modifique las funciones parse y deBruijn para soportar el nuevo nodo cast

     > (parse '{cast Num #f})
     (cast (TNum) (bool #f))

2. Actualice la función çompile para que genere un CHECKCAST para un expresión cast.

   > (compile (parse '{cast Num (and #t #f)}))
   (list (BOOL_CONST #f) (BOOL_CONST #t) (AND) (CHECKCAST (MTNum)))

3. Implemente la función (typed-compile s-expr) que se encarga de todo el proceso de generación de código desde una S-Expr, considerando el parsing, la nueva validación de tipos, la transformación con índices De Bruijn y el paso a listas de instrucciones que considera incluir la instrucción (CHECKCAST type) para hacer validación dinámica de tipos.

El siguiente ejemplo no se puede ejecutar actualmente pues el sistema de tipos lo rechaza.

{with : Bool {id : (Any -> Any)
                           {fun {x : Any} : Any x}}
                {with : Bool {g : ((Bool -> Bool) -> Bool)
                                {fun {f : (Bool -> Bool)} : Bool {f #t}}}
                      {with : Bool {f : (Bool -> Bool)
                                      {fun {x : Bool} : Bool x}}
                            {g {id f}}}}}

Esto sería solucionable si pudiésemos también castear funciones de la siguiente la forma:

{cast (Bool -> Bool) {id f}}

Teniendo una forma de castear funciones, podemos hacer que el sistema de tipos acepte el código anterior.

{with : Bool {id : (Any -> Any)
                          {fun {x : Any} : Any x}}
               {with : Bool {g : ((Bool -> Bool) -> Bool)
                               {fun {f : (Bool -> Bool)} : Bool {f #t}}}
                     {with : Bool {f : (Bool -> Bool)
                                     {fun {x : Bool} : Bool x}}
                           {g {cast (Bool -> Bool) {id f}}}}}}

Para que la máquina sea capaz de realizar un cast entre funciones, debe implementar la función (m-subtype? mT1 mT2) del fichero machine.rkt. La función m-subtype? evalúa a #t si mT1 es subtipo de mT2 incluyendo la noción de subtipos entre funciones

> (m-subtype? (MTFun (MTNum) (MTNum))
              (MTFun (MTNum) (MTAny)))
#t