Tarea 1

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

1. (0.5) Implemente la función (repeat lst k) que repite los elementos de una lista k veces usando foldr, map y la función range vista en la Auxiliar 1. Ejemplo:

   > (repeat '(a b c) 3)                       
   '(a a a b b b c c c)

2. (0.7) Defina una función (groupby selector lst) que permita agrupar los elementos de una lista basado en un criterio de selección. Ejemplos:

   > (groupby cdr 
              '(("Scorsese" . 72 ) 
                ("Tarantino" . 53)
                ("John" . 19)
                ("Peter" . 72)
                ("Robert" . 19)))                   
   '((72 ("Scorsese" . 72) ("Peter" . 72))
     (53 ("Tarantino" . 53))
     (19 ("John" . 19) ("Robert" . 19)))
    
   > (groupby (λ (x) (modulo (string->number x) 3))
              '("21" "5" "34" "5" "89" "47" "28"))                    
   '((0 "21") (2 "5" "5" "89" "47") (1 "34" "28"))

3. (0.8) Utilizando la función (apply fun args) de Racket, implemente la función (curry-n f) que dado una función f retorna su versión currificada. Para determinar la cantidad de parámetros que espera la función f, utilice la función procedure-arity provista en Racket (puede asumir que la función f recibe un número fijo de parámetros). Ejemplos:

   > (define f (curry-n (λ (x y z) (+ x y z))))                                                  
   > (((f 2) 5) 20)
   27
    
   > (define g (curry-n (λ (x) (* x x))))
   > (g 3)
   9
    
   > (define y (curry-n (λ () (* 20 5))))
   > (y)
   100

Nota: obviamente, no pueden usar la función curry de Racket!

Considere un lenguaje imperativo en el cual un programa es una lista de instrucciones. Las instrucciones son:

• {var id e}: Define la variable global de nombre id y le asocia el valor de la expresion e. Si la variable que se está intentando definir ya fue previamente definida por una instrucción var, se debe arrojar el error “variable already defined”.
• {set id e}: Reasigna la variable de nombre id con el valor de la expresión e. Si se realiza una asignación a una variable que no haya sido previamente definida por una instrucción var, se debe arrojar el error “free variable”.
• {while e exprs}: Ejecuta exprs siempre y cuando el valor de la expresión e no sea cero.
• {return e}: Instrucción que detiene la ejecución y retorna el valor de la expresión e. En todo programa la última expresión debe ser return, en caso contrario se debe arrojar el error “no return expression found”.

Considere que los programas tienen una memoria global mutable que es implementada con una tabla de hash donde cada id se asocia a un valor. Refierase al manual de Racket para obtener información acerca de cómo utilizar tablas de hash en Racket.

A modo de ejemplo, considere los siguientes programas implementados en nuestro lenguaje imperativo:

> (run '{{var X 10}
         {var Y {+ 5 X}}
         {return {+ X Y}}})
25
 
> (run '{{var X (+ 2 8)}
         {var Y 1}
         {var Z X}
         {while Z
           {{set Y {* Y Z}}
            {set Z {- Z 1}}}}
         {return Y}})
3628800

1. (0.5) Defina la gramática BNF del lenguaje, realizando una clara distinción entre programas (Prog), instrucciones (Instr) y expresiones (Expr). Considere las siguientes operaciones aritméticas: + - *.
2. (0.5) Defina (usando deftype) las estructuras de datos necesarias para poder construir una representación de la sintaxis abstracta de un programa.
3. (0.5) Defina un parser para el lenguaje.
4. (1.0) Defina un interprete para el lenguaje, usando una tabla de hash global para manejar el estado de las variables.
5. (0.5) Defina la función run :: Prog → Num que ejecuta un programa y retorna el valor de una expresión return, o un error si corresponde.
6. (1.0) Para evitar errores de variables ya definidas y/o no definidas, defina una función var-check :: Prog → List[string] que analiza un programa (sin ejecutarlo!), y retorna una lista de los errores de variables presentes en el programa. Si el programa no contiene errores, retorna la lista vacía.

Nota: recuerden que para definir una función que procesa una estructura compuesta, tienen que usar funciones auxiliares para los sub-componentes (en el contexto de la tarea: programas, instrucciones, expresiones).