Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
teaching:cc4101:tareas:2015-2:tarea3 [2015/10/17 23:40] – [(2.0)((Divididos en 1 para de ''%%deBruijn%%'' y 1 para''%%compile%%'')) Compilación] racruzteaching:cc4101:tareas:2015-2:tarea3 [2016/03/25 18:42] (current) – old revision restored (2015/10/31 14:36) fmosso
Line 43: Line 43:
 </code> </code>
 Tome un tiempo para experimentar con la función ''%%machine%%'' y el set de instrucciones antes de realizar los próximos ejercicios. Tome un tiempo para experimentar con la función ''%%machine%%'' y el set de instrucciones antes de realizar los próximos ejercicios.
-==== (1.0) Índices De Bruijn ====+==== Í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 Bruijn((La explicación detallada de como funcionan se puede encontrar en la sección 3.5 del [[http://cs.brown.edu/~sk/Publications/Books/ProgLangs/2007-04-26/plai-2007-04-26.pdf|PLAI]])). 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((La explicación detallada de como funcionan se puede encontrar en la sección 3.5 del [[http://cs.brown.edu/~sk/Publications/Books/ProgLangs/2007-04-26/plai-2007-04-26.pdf|PLAI]])).
-  - 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. <code scheme>+  - (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. <code scheme>
 > (deBruijn  > (deBruijn 
    (parse '{+ 1 {with : Num {x : Num 1}    (parse '{+ 1 {with : Num {x : Num 1}
Line 59: Line 59:
          
 > (deBruijn (add (num 1) (id 'x))) > (deBruijn (add (num 1) (id 'x)))
-;Arroja error "unbound indentifier"+;Arroja error "unbound identifier"
 </code> </code>
  
-==== (1.0) De AST a código de máquina ====+==== 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. 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:  <code> 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:  <code>
Line 83: Line 83:
                                    {< x 10}} {+ 2 3}})))                                    {< x 10}} {+ 2 3}})))
 (list (list
- (INT_CONST 2) 
  (INT_CONST 3)  (INT_CONST 3)
 + (INT_CONST 2)
  (ADD)  (ADD)
- (CLOSURE (list (ACCESS 0) (INT_CONST 10) (LESS) (RETURN)) (MTFun (MTNum) (MTBool)))) + (CLOSURE (list (INT_CONST 10) (ACCESS 0) (LESS) (RETURN)) (MTFun (MTNum) (MTBool))) 
- (APPLY))                                  + (APPLY)) 
 </code> </code>
 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: 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:
Line 93: Line 93:
      * ''%%TBool%%'' a ''%%MTBool%%''      * ''%%TBool%%'' a ''%%MTBool%%''
      * ''%%TFun%%'' a ''%%MTFun%%'' aplicando la transformación recursivamente al tipo del argumento y al tipo de retorno      * ''%%TFun%%'' a ''%%MTFun%%'' aplicando la transformación recursivamente al tipo del argumento y al tipo de retorno
-  - 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+  - (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
 ===== (0.5) Sistemas de Tipos Simple ===== ===== (0.5) Sistemas de Tipos Simple =====
 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. 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.
Line 111: Line 111:
  
 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: 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 ''%%Any%%''. Es decir que frente a tipos distintos en las ramas el resultado es Any.+  * La existencia de ''%%Any%%'' permite tipear ''%%{if #t 1 #f}%%'' como del tipo ''%%TAny%%''((variante del tipo Type para Any)). 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 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 la aplicación de función, el tipo del argumento puede ser subtipo del tipo declarado del argumento de la función.
Line 160: Line 160:
   - Actualice la función ''%%çompile%%'' para que genere un ''%%CHECKCAST%%'' para un expresión ''%%cast%%''. <code scheme>   - Actualice la función ''%%çompile%%'' para que genere un ''%%CHECKCAST%%'' para un expresión ''%%cast%%''. <code scheme>
 > (compile (parse '{cast Num (and #t #f)})) > (compile (parse '{cast Num (and #t #f)}))
-(list (BOOL_CONST #t) (BOOL_CONST #f) (AND) (CHECKCAST (MTNum)))+(list (BOOL_CONST #f) (BOOL_CONST #t) (AND) (CHECKCAST (MTNum)))
 </code> </code>
   - 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.   - 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.